Adventure in Unlambda 解説 その1

Adventure in Unlambda のコード解説です。(ゲームのネタバレはありません。)

はじめに

Adventure のプログラムは Gauche で実行可能な Scheme プログラムを使って生成されています。ソースコードは全部で1万行弱(テスト含む)で、生成される Unlambda コードは約 600KB。ちなみに元となった CWEB 版gccコンパイルすると 100KB 程度になります。
以下の説明は、すでに Unlambda の基本的な動作について知っている読者を想定しています。Unlambda についての解説は 公式サイトこちら を参照してください。

マクロ言語

これだけの規模のプログラムを生の Unlambda で書くのはちょっと大変(控えめな表現)なので、Unlambda に変換できるマクロ言語を定義することから始めます。マクロ言語の目的は以下の3つです。

1. S式から Unlambda 形式への変換

(S I I) のような S式 で表現されたプログラムを ``sii のような Unlambda 形式に変換します。S式のほうが(Unlambdaよりは)読みやすく、Scheme でコードを扱うのが簡単になるためです。

2. ラムダ式の除去

マクロ言語でラムダ式を書けるようにして、Unlambda コードを生成する際に SKI コンビネータ表現へと変換します。変換の方法は Unlambda 公式ページ で解説されています。
複数の変数をもつラムダ式は自動的にカリー化されます。例えば、(lambda (a b) (b a))(lambda (a) (lambda (b) (b a))) と等価です。

3. マクロ展開

Lisp のマクロに似た仕組みです。制御構造や各種のシンタックスシュガー、また単なる関数定義の代わりにも使います。
マクロ言語内では S, K, I, V(大文字)などの名前で Unlambda の組み込み関数を使えます。Scheme の文字オブジェクト #\x は Unlambda の文字出力関数 .x に変換されます。
マクロ言語を展開する Scheme コードは unlc.scm で定義されています。マクロ言語を使うと以下のようなプログラムが書けます。

#!/usr/local/bin/gosh
; "yes" を無限に出力する Unlambda コードを生成する
(require "./unlc.scm")
(defmacro yes-loop
  ((lambda (x) (x x))
   (lambda (f)
     (#\y #\e #\s #\newline I (f f)))))
(print-as-unl 'yes-loop)   ; ```sii``s`d`k````.y.e.sri``sii を出力

生成された Unlambda コードに d (delay) が含まれていますが、これは 2 番目の lambda 式の中身("yes\n" を出力する部分)が、引数 f が与えられるまで実行されないようにするためです。通常の(Scheme プログラマが期待するような)実行順序になるよう、変換器が面倒を見てくれます。
ちなみに上のような (lambda (x) (x x)) を使って再帰を実現するイディオムはよく使われるので、lambda-rec という構文も用意しています。(Y コンビネータを使ってもいいのですが、こちらの方がコンパクトです。)

基本的な制御構造

次にマクロを使っていくつか Scheme 風の制御構造を定義します。以下で紹介するマクロは lib.scm に含まれています。

let

ローカル変数を定義する制御構造です。let 式は簡単に lambda 式に変換できます。

(let ((var1 val1)
      ..
      (varn valn))
  body)
=>
((lambda (var1 .. varn) body)
 val1 .. valn)
真偽値、if

Unlambda の慣習にならい、true を i 、false を v コンビネータで表現します。if 式は Unlambda 公式ページ で解説されているように、

(((S (K call/cc)) ((S (K (S (K (K (K I)))))) ((S S) (K (K K)))))) <b> <then> <else>)

で <b> が true のとき <then> が、false のとき <else> が返ります。頭が痛くなりそうですね。実際の if マクロは <then> と <else> の片方しか実行されないようにダミーの lambda を入れて、以下のような定義になっています。

(defmacro *if* (((S (K call/cc)) ((S (K (S (K (K (K I)))))) ((S S) (K (K K)))))))
(defmacro (if b then else)
  ((*if*
    b
    (lambda (**if-dummy**) then)
    (lambda (**if-dummy**) else))
   I))
begin

複数の式を順番に実行します。

(begin e1 e2 ... en-1 en)
=>
(K I e1
 (K I e2
   (...
    (K I en-1 en)...)))
文字列出力

以下は "Hello, world!" を出力する Unlambda プログラムです。

`.!`.d`.l`.r`.o`.w`. `.,`.o`.l`.l`.e`.Hi

実はこれはもっと短くすることができます。anarchy golf の最短は 36Byte で、こんな感じです。

`.!`.d`.l`.r``.w`. `.,``.l`c`.H.e.oi

c (call/cc) を使うのがポイントです。また、S コンビネータを使って文字をコピーすると縮められる場合もあります。lib.scm で定義されている compress-string 関数は、こうしたテクニックを使って短い文字列出力コードを生成します。(といっても5〜10%くらいしか縮みませんが。)unl ファイルを覗いたとき文字列が簡単に読めないようにする難読化の目的も兼ねています。
マクロ言語では、(string "Hello, world!") と書くと "Hello, world!" を表示して引数をそのまま返す関数を作れます。

基本的なデータ構造

データ構造もマクロを使って定義しますが、 Unlambda ではすべてが関数なので、関数でデータ構造を表現する方法を考えないといけません。

cons, car, cdr

値のペアを作ったり、ペアからどちらかの値を取り出したりできるデータ構造です。(car (cons a b)) が a を返し、(cdr (cons a b)) は b を返します。
cons を使うとリスト構造を作れます。例えば x, y, z の 3 要素を持つリストは、(cons x (cons y (cons z nil))) と表現できます。

(defmacro cons (lambda (a b f) (f a b)))
(defmacro (icons a b) (lambda (_f) (_f a b)))  ; inlined cons
(defmacro (car x) (x (lambda (a b) a)))
(defmacro (cdr x) (x (lambda (a b) b)))
(defmacro nil V)
(defmacro (pair? x) (x (lambda (a b) I)))  ; ペアならIを返し、nilならVを返す
(defmacro (null? x) (not (pair? x)))

cons と icons の違いはちょっと微妙です。icons は引数 a と b をインライン化するので、例えば

(icons (#\a I) V)

(lambda (_f) (_f (#\a I) V))

と展開され、_f として何かが適用されるまで (#\a I) は実行されません("a" が出力されません)。これに対して

(cons (#\a I) V)

((lambda (a b f) (f a b)) (#\a I) V)

と展開されるので、(#a I) が評価され "a" が出力されてから結果の値が cons の第 1 引数になります。不用意にインライン版を使うと中身を参照するたびに計算を行う非効率なデータ構造ができてしまうので注意が必要ですが、うまく使うと遅延リストが簡単に作れたりもします。

チャーチ数

関数で自然数を表現する方法です。ラムダ式を使って書くと以下のようになります。

0 = (lambda (s z) z)
1 = (lambda (s z) (s z))
2 = (lambda (s z) (s (s z)))
3 = (lambda (s z) (s (s (s z))))
...

つまり、自然数 n のチャーチ数は、引数 s と z をとり z に s を n 回適用する関数です。
チャーチ数を使うと、例えば以下のようにしてリスト lst の n 番目の要素を取り出すことができます。

(defmacro (nth n lst)
  (car (n cdr lst)))

ちょっとトリッキーですが、リスト lst の n 番目の要素を x で置き換えたリストを返す関数も書けます。

(defmacro (set-nth n x lst)
  ((n (lambda (g lst)
        (cons (car lst) (g (cdr lst))))
      (lambda (lst)
        (cons x (cdr lst))))
   lst))

churchnum.tbl ファイルに 0 から 1024 までのチャーチ数表現が定義されています。これは anarchy golf 用に作ったもので、Unlambda に変換したときなるべく短くなるようにしています。こんなところにも call/cc が出てくるのが Unlambda らしくて面白いです。

以下はチャーチ数に対する演算の例です。

(defmacro (zero? n) (n V I))  ; ゼロならIを返し、正の数ならVを返す
(defmacro (nonzero? n) (n (K I) V))  ; その逆
(defmacro (succ n)   ; n+1
  (lambda (s z) (s (n s z))))
(defmacro (add x y)  ; x+y
  (lambda (s z) (x s (y s z))))
(defmacro (mul x y)  ; x*y
  (lambda (s z) (x (y s) z)))
(defmacro (pred n)   ; n-1
  (lambda (s z)
    (((n (lambda (g h) (h (g s)))) (lambda (x) z)) I)))

(defmacro (T x y) (y x))
(defmacro (= m n)   ; mとnが等しければI、異なるならVを返す
  ((m (T I) (n T (K I))) V))

(defrecmacro (length xs)   ; リストxsの長さを返す
  (if (pair? xs)
      (succ (length (cdr xs)))
      (K I)))  ; (K I) = (lambda (s z) z) = 0

比較関数 = などはインライン化されて何百回も使われるため、ちょっと頑張ってゴルフしてあります。どうやって動くのか考えてみると面白いでしょう。

つづく

以上で、Unlambda へ変換できるマクロ言語でプログラムを書く準備ができました。次回はいよいよ Adventure 本体のコードについて解説します。