読者です 読者をやめる 読者になる 読者になる

Adventure in Unlambda 解説 その2

前回の続きです。今回は Adventure のゲーム部分の実装について解説します。

乱数

Adventure では様々なところで乱数が使われています。例えば辞書に無い単語を入力すると、3種類の中からランダムに選ばれたメッセージを表示します。
擬似乱数の生成には、7ビットの 線形帰還シフトレジスタ を使っています。

(defmacro rand-7
  ((lambda-rec rec (b0 b1 b2 b3 b4 b5 b6)
       (icons b0
              (rec b1 b2 b3 b4 b5 b6 (xor b0 b1))))
   K (K I) K K K (K I) K))

K がビット 1、(K I) がビット 0 を表します。これで、rand-7 は周期が 127 のランダムなビットの無限リストになります(前回説明した、icons で遅延リストを作るテクニックです)。この無限リストは後述のグローバル変数テーブルの中に入っていて、必要なときに必要なだけビット列を取り出して使います。
Unlambda では実行のたびに乱数の種を異なる値にセットする方法が無いので、Adventure に最初から全く同じコマンド列を入力すると毎回結果が同じになってしまいます。
乱数に関するコードは rand.scm に入っています。

入力パーサ

Adventure は 1-2 単語のコマンドしか受け付けないので、入力された文字列から単語を認識するのがパーサの主な仕事になります。認識できる単語は別名も含めると全部で 284 語あります。
Adventure のコマンドは先頭 5 文字のみで認識されます。つまり、"jewel" も "jewels" も "jewelry" も同じ単語として認識されます。これはオリジナルの Adventure が書かれた PDP-10 が 36 ビットワードアーキテクチャで、7 ビットの文字コードを 5 文字分パックして単語を処理していたことに由来します。

単語のパーサには、以下の機能が必要です。

  • 単語を認識したら、その単語に関連付けられた値を返す。
    • 4文字以下の単語は、単語の後に空白か改行がある場合に認識する。
    • 5文字以上の単語は、5文字目が一致した時点で認識し、空白か改行まで読み飛ばす。
  • 認識できない単語の場合は、空白か改行まで読み飛ばす。
  • いずれの場合も、入力された文字列を後で表示できるよう覚えておかなければならない。

実装の説明に入ります。まず、「リーダーオブジェクト」を定義します(突然のオブジェクト指向)。このオブジェクトは脱出継続 cont (コンストラクタに渡される)と部分入力文字列 p (初期値は空)を保持しており、次の2つのメソッドを持ちます。

  1. 引数 f をとり、標準入力から1文字読み、新しい(p を更新した)リーダーオブジェクトを引数に f を呼び出す。
  2. 引数 val をとり、次の空白か改行文字まで読み飛ばし(このとき読んだ文字を p に追加していく)、(cons p val) を引数に cont を呼び出す。

最初のメソッド(reader I f) で、2番目のメソッド(reader V val) で呼び出せます。
リーダーオブジェクトの定義は以下のようになります。

(defmacro (reader-core cont)
  ((lambda-rec rec (p b)
     (if b  ; b の値で処理を切り替える
         (let ((next (rec (! (S p)))))  ; ここで p に現在の文字を追加
           (K (lambda (f) (f next))
              (@ I)))
         (lambda (val)
           ; 空白まで読み飛ばして val を返す
           (let loop ((p p))
             (if (read-char=? #\space #\newline)
                 (cont (cons p val))
                 (loop (K (! (S p))
                          (@ I))))))))
   I))   ; p の初期値

パーサ本体では、文字で場合分けをしながらリーダーオブジェクトを転がしていきます。以下は "N" と "NE" のみを認識するパーサのコード例です。単語が認識できない場合は、単語の値として V を返すものとします。

(call/cc
 (lambda (cont)
   ((lambda (reader)
      (((read-char=? #\n #\N) reader I        ; 最初の文字が 'N' なら
        (lambda (reader)
          (((read-char=? #\space #\newline)   ; 2文字目が空白なら
            reader V <word-value N>)          ; "N"を認識
           ((read-char=? #\e #\E) reader I    ; 2文字目が 'E' なら
            (lambda (reader)
             ((read-char=? #\space #\newline) ; 3文字目が空白なら
              reader V <word-value NE>)       ; "NE"を認識
             (reader V V)))                   ; NE? -- 認識できない
           (reader V V))))                    ; N? -- 認識できない
       (reader V V)))                         ; ? -- 認識できない
    (reader-core cont))))   ; リーダーオブジェクトを作る

実際のコードではまず(Scheme 上で)単語辞書から Trie を構築し、それから上のようなコードへ再帰的に変換します。
詳しくは parser.scm を参照してください。

移動表

Adventure には約 130 の部屋(屋外もありますが)があり、繋がっている部屋同士は特定の単語を入力することで行き来できます。
オリジナルの FORTRAN 版 Adventure では、部屋の繋がりはデータファイルにこんな感じで書かれています。

1       2       2       44      29
1       3       3       12      19      43
1       4       5       13      14      46      30
1       5       6       45      43
1       8       63

1 列目は移動元の部屋番号、2 列目は移動先の部屋番号です。残りの列は、その移動を発生させる単語の番号です。例えば部屋 1 で 63 番の単語が入力されると部屋 8 へ移動する、という具合です。2 列目に特殊な数値を入れることで、移動可能となる条件を指定したり(例えば鍵のかかった扉を通り抜けて進むことはできません)、移動する代わりにメッセージを表示したりすることもできます。
Unlambda 版ではこの表を、関数のテーブル(リストのリスト)として表現しています。

(nth 単語番号 (nth 移動元部屋番号 travel-table))

で得られる関数を実行すると、条件を判断して移動先の部屋番号を返したりメッセージを表示したりします。
オリジナルでは "back" と入力したとき行ける場所や NPC の移動場所も同じテーブルで管理していますが、Unlambda 版ではこれらは専用のテーブルを使っています。

部屋と移動表に関しては room.scm を参照してください。

オブジェクト

ここで言うオブジェクトは、ランプや鍵などのゲームに登場するアイテムのことです。扉のように持ち運びできないオブジェクトもあります。
各オブジェクトは 3 つの属性を持ちます。

  • PLACE: オブジェクトがある部屋の番号(主人公が持っているなら V コンビネータ
  • PROP: オブジェクトの状態(扉なら開いているか鍵がかかっているか)
  • BASE: オブジェクトを持ち運びできるかどうか。複数の部分に分かれたオブジェクトの管理にも使われる。

オリジナルの Adventure では PLACE とは別に、部屋ごとにその部屋にあるオブジェクトをリンクリストの形で持っています。Unlambda 版ではこれをサボっていて、部屋にあるオブジェクトの一覧を得たい時には毎回 PLACE をスキャンしています。これによって、ちょっとした非互換が起こります。部屋にあるオブジェクトを表示するとき、オリジナルではリンクリストの先頭から順に表示していきますが、Unlambda 版ではオブジェクト番号の若い方から表示します。これでもほとんどの場合は問題ありませんが、ある特定の状況ではちょっと変な順番で状況を説明しているように見えることがあります。

オブジェクトに関しては object.scm を参照してください。

World データ構造

Adventure では、数十個のグローバル変数でゲームの状態を保持しています。前述のオブジェクトの属性や乱数生成器の状態、主人公の現在位置などです。
しかし Unlambda にはそもそもグローバル変数というものがありません。データは関数の引数や戻り値として渡していくしかありません。また、データ構造を破壊的に変更することもできません。そこでどうするかというと、

  • すべてのグローバル変数をまとめたデータ構造を作る(これを world と呼ぶことにします)
  • グローバル変数の書き換えは、「worldを引数に取り、変更後の world を別オブジェクトとして返す」関数として実現する

もう少し具体的に見て行きましょう。グローバル変数 g1〜g4 があるとします。それらの初期値を i1〜i4 とすると、初期状態の world を作るコードは以下のようになります。

(defmacro initial-world
  (cons (cons i1
              i2)
        (cons i3
              i4)))

このように、world は cons を使った 2分木の形でデータを保持します。world から値を取り出すマクロは以下のように定義できます。

(defmacro (g1 world) (car (car world)))
(defmacro (g2 world) (cdr (car world)))
(defmacro (g3 world) (car (cdr world)))
(defmacro (g4 world) (cdr (cdr world)))

値をセットするマクロは以下のようになります。ちょっと長いので g1 のコードのみ示します。第 2 引数の f は、g1 の古い値をとって新しい値を返す関数です。

(defmacro (set-g1 world f)
  (world
   (lambda (l r)
     (cons (l
            (lambda (l r)
              (cons (f l) r)))
           r))))

(上のコードでは car/cdr を使わずにペアから値を取り出しています。cons の定義が (lambda (a b f) (f a b)) なので、ペアに 2 引数をとる関数を渡せば中身を取り出すことができます。)

Unlambda 版 Adventure には、(頑張って減らした結果)35個のグローバル変数があります。world はバランスした 2 分木ではなく、頻繁にアクセスされる変数が浅い位置に来るようハフマン木を使っています。variable.scm には、2分木の構造を与えると上のようなアクセサマクロを定義してくれる Scheme コードがあります。

暗黙の world

さて、world を使うことでグローバル変数を表現できましたが、しばらくプログラムを書いてみたところ、変数にアクセスするたびに world を引数にしたマクロを呼びださなければならないのでコードが world だらけになってしまいました。そこで、通常のアクセサマクロに加えて、world を暗黙に参照するマクロも定義するようにしました。例えば g1 の場合、以下のようになります。

(defmacro $g1 (g1 world))
(defmacro ($set-g1 f) (set-g1 world f))

これで、グローバル変数 g1 の値を取り出したい時は $g1 と書くだけで、現在のスコープにある world 変数から値を取り出せます。自由変数をもつマクロは一見危険に見えますが、今回の場合は「world 構造は必ず world という名前の引数名にする」というルールを守ることで特に問題なく便利に使えました。

let-world

オリジナルの Adventure コードが下のような形をしていたとします。

何かをする
変数 g1 に v1 をセット
変数 g2 に v2 をセット
別の何かをする

これをマクロ言語に翻訳すると、こんな感じになります。

(begin
  (何かをする)
  (let ((world ($set-g1 (K v1))))
    (let ((world ($set-g2 (K v2))))
      (別の何かをする))))

(別の何かをする) の部分では、world には新しい g1 と g2 の値が入っているのがポイントです。このパターンを少し簡単に書くために、let-world というマクロを定義しています。let-world を使うと、上の例は以下のように書けます。

(begin
  (何かをする)
  (let-world (($set-g1 (K v1))
              ($set-g2 (K v2)))
    (別の何かをする)))

World の実装については variable.scm を参照してください。

メイン制御ループ

これで部品は揃いました。最後に、Adventure のメイン制御ループについて解説します。ここで入力コマンドの解釈、コマンドに対応する動作の実行、毎ターンごとの処理などが行われます。

Adventure は巨大なスパゲッティプログラムです。制御の移動はもっぱら goto 文で行われます。お手本にした CWEB 版も、文書化されているため読みやすくなってはいますが、結局のところメインの処理は千数百行の巨大な関数です。
関数型言語で goto をシミュレートする普通の方法は、相互末尾再帰を使うことです。goto のラベルごとに関数を作って、対応するラベルから始まる処理を実装します。goto 文は対応する関数の呼び出しに置き換えます。Unlambda 版 Adventure ではもうひと工夫加えて、「手続きテーブル」を使っています。これは単なる関数のリストで、各関数は「world を引数にとり、(次に実行する手続きのインデックス, 更新した world)のペアを返す」ようになっています。関数の中では必要に応じて入出力を行うこともあります。
駆動ループは非常に簡単です。

(defrecmacro (trampoline label world)
  (let ((result ((nth label program-table) world)))
    (trampoline (car result) (cdr result))))

(defmacro main
  (trampoline entry-point initial-world))

program-table が手続きテーブル、entry-point が最初に実行する関数のインデックス、initial-world が初期状態の world です。
この仕組みによって、相互再帰のために関数をコード中で持ち回る必要がなくなります。制御を移動したいときは、飛び先の関数インデックスと現在の world をペアとして返すだけです。さらに重要なことですが、こうして関数を手続き単位で分離することでテストも容易になります。
手続きテーブルの定義は proc.scm にあります。ベースにした CWEB 版の段落番号をコメントに入れてあるので、CWEB 版を参照しながら読むと理解しやすいと思います。

ユニットテスト

まともなプログラミング言語なら、テストくらい書けなければいけません。もちろん Unlambda はまともな言語なのでテストが書けます。
Adventure のユニットテストでは、手続きテーブルの手続き単位でテストします。パーサなどは手続きに埋め込まれるので、間接的にテストできます。
テストケースの例を示します。これはプレイヤーが "west" と累計 10 回入力した時に表示されるメッセージをテストしています。

; define-test マクロでテストケースを定義する。
; parse-label はテストする手続き、west-messageはテストケース名。
(define-test 'parse-label "west-message"
  ; テストケースは 3 つの要素からなる。
  ; 1. テストしたい状況に合わせて、world を初期状態から変更する。
  '(($set-word12 (K (cons (motion-word-with-aux W I) V)))  ; "west" を入力したことにする
    ($set-west-count (K (cons1 V))))                       ; カウントダウン変数 west-count を 1 にする
  ; 2. 手続きを呼び出したあと、テストしたい内部状態をダンプする。
  ;    print-stars は与えられた church 数を出力するマクロ。
  '((print-stars cont)                         ; cont は次に実行される手続きの番号
    (print-stars (cons1-length $west-count)))  ; west-count を調べる
  ; 3. 期待される出力結果。手続きが副作用として出力する文字列と、
  ;    2 でダンプした出力をチェックする。
  (list " If you prefer, simply type W rather than WEST.\n"  ; 手続きの出力
        'look-at-word1   ; cont の値
        0))              ; west-count の値

このテストを実行するとき、まず次のようなコードが生成されます。

(let ((world initial-world))
  (let-world (1 の内容)
    ((<指定された手続き> world)
     (lambda (cont world)
       (2 の内容)))))

これがその場で Unlambda コードに変換され、Unlambda インタプリタで実行されます。その出力と 3 で指定された期待値から作られた文字列を比較して、一致していればテストは成功です。
Unlambda はすべてが関数型なので、型エラーというものが(実行時でさえも)ありません。そのためデバッグが非常に困難です。テスト無しでこの規模のプログラムを作ることはできなかったと思います。
ユニットテストのコードは test.scm にあります。4000 行以上あり、コード全体の 4 割の大きさです。

感想

Esoteric language で大真面目にでかいプログラムを作ってみる、というのは前々からやりたいと思っていて、Unlambda ならゴルフでノウハウも溜まっているし気合入れてやるかー、と思い立ってから完成まで丸々 2 ヶ月かかってしまいました。

Adventure を題材に選んだのは

  • 標準入出力だけで実現できる
  • インタラクティブなゲームだから non-trivial な感じが出せる
  • ちょっとした中二ごころ("xyzzy" の元ネタとかカッコよくね?みたいな)

といった理由でした。最初に FORTRANソースコード見たときは挫けそうになりましたが。

実際作ってみると、ゴルフ程度の規模のプログラムでは出てこない種類の問題が色々出てきました。コマンドを実行するたびに重くなるプログラム(world を書き換えるとき間違えて遅延リストになっていた)、加速度的に遅くなるコンパイル(分割コンパイルで対応)、理解不能な挙動をするバグ(南を表す "S" と S コンビネータの名前が被ってた)、等々。始めたときは現実的な実行速度・コードサイズで実現できるかどうか分からなくてヒヤヒヤしてましたが、最終的にはいい感じに収まってくれました。

あと、今回のようにミニ言語を少しずつ拡張しながら作っていくやり方のときはやっぱり Lisp 系便利だなと思いました。Unlambda に変換されるマクロ言語と、マクロ言語に構文を追加するマクロと、マクロ言語のマクロを生成する Scheme コードが混じり合っていて、読んでいる方は混乱するかもしれませんが書いているときは快適でした。

そんなわけで、得意な esolang がある人は何か大きめのプログラムを書いてみると新しい発見があって楽しいんじゃないかと思います。