Unlambdaインタプリタを作った

Unlambdaインタプリタの性能を気にする人というのもあまりいないと思いますが、ELVMをセルフビルドすると何日もかかったり、AtCoderをUnlambdaで解いてみたら時間制限が厳しかったという話を見て、まあ速いインタプリタあるといいよねと思っていました。

Unlambdaの高速なインタプリタといえばEmil Jeřábek氏のunl.cがあり、公式のc-refcntインタプリタの50〜100倍も高速です。 ただこのインタプリタはコードが結構複雑で、これを改造して何かを作るというのは大変です(unlambda-dcのときにやろうとして断念しました…)。

というわけで自作のインタプリタをいちから書いてみました。

https://github.com/irori/unlambda

ベンチマーク

以下の3つのプログラムで、unl.cと実行時間を比較しました。

結果です。unl.cより1.6倍~2.2倍速いようです。

プログラム unl.c 自作インタプリタ
adventure 0.72s 0.41s
lisp 2.05s 1.28s
elvm-8cc 44.3s 20.1s

ちなみにELVMはBrainfuck(付属のbfoptを使ったとき)より速くなりました。Unlambdaはやればできる子。

実装

ソースコードC言語で600行ほどで、そのうち半分くらいがメモリ管理コードです。以下、工夫した点を紹介します。

ガベージコレクション

Unlambdaプログラムの実行中に作られるオブジェクトグラフは循環しないので、参照カウンタでメモリ管理ができます。実際、多くの(GCを持たない言語で実装された)Unlambdaインタプリタは参照カウンタ方式を採用しています。

しかしUnlambdaの実行では頻繁にオブジェクトの生成・破棄が繰り返されるので、参照カウンタの操作は結構なオーバーヘッドになります。またunl.cがしているように、参照カウンタの操作を省略できるところは省略したり、カウンタが1のときはオブジェクトを上書きして再利用するなどの最適化を入れるとコードが複雑化してしまいます。

今回実装したインタプリタでは世代別GCを採用しました。新世代はオブジェクト256k個分の領域を2つ用意してコピーGCを行い、このマイナーGCを2回生き延びたオブジェクトは旧世代領域に移動します。旧世代領域がいっぱいになると、メジャーGCとして全体に対してマークスイープGCを行います。

Unlambdaで世代別GCは非常に有効で、プログラムにもよりますが、マイナーGCで99%以上のオブジェクトを回収できることが多いです。全体の実行時間に占めるGCの割合も1%程度に抑えられました。

世代別GCでは通常、旧世代領域から新世代領域への参照を追跡するためにライトバリアが必要になります。ですがこのインタプリタでは一旦作られたオブジェクトが書き換わることはないため、旧世代から新世代への参照は発生しません。ライトバリアが不要なので、評価器ではGCのことをあまり気にせずコードを書けます(コピーGCでアドレスが変わる点は注意が必要ですが)。

コンビネータの置き換え

※ 以下の説明はUnlambdaやLazy Kなどでプログラムを書いたことがないとわかりにくいかもしれません。

Unlambdaの組み込み関数Sは、引数を関数適用の両辺に分配する働きをします。例えば、`fgという式の中で外から渡される値xを使いたいとき、元の式を``Sfgに書き換えてやると、xが渡されたとき```Sfgx``fx`gxとなり、fgの両方にxを渡す形にできます。fgがもっと複雑な式で、その部分式でxを使いたい場合は同様の変換をfgにも行えばいいわけです。

実際はfgの両方でxが必要になることはあまりなくて、どちらか一方では値を捨てたくなることが多いです。そんなときは組み込み関数Kの出番です。fの中でxが不要であれば、``Sfgf`Kfに置き換えて、``S`Kfgにします。これに値xを渡すと、```S`Kfgx```Kfx`gx``f`gxとなり、xgだけに渡ります。同様にgの中でxが不要であれば、g`Kgに書き換えると、```Sf`Kgx``gx``Kgx``fxgとなり、xfだけに渡されます。

これらの場合のSKの働きを1ステップで実行するコンビネータを考えることができて、B, Cコンビネータとして知られています。

  ```Bfgx = ```S`Kfgx = `f`gx
  ```Cfgx = ```Sf`Kgx = ``fxg

これらはUnlambdaの組み込み関数ではないのでプログラムを書くときには使えませんが、インタプリタ内部でSKの組み合わせをこれらの「軽い」コンビネータに置き換えることで高速化を図れます。

具体的には、Sに第1引数あるいは第2引数が与えられた時点で、それがKの部分適用(引数ひとつを与えられた状態)であればBまたはCに置き換えます。式の評価の結果書き換え可能な形になることもあるので、構文解析時にパターンマッチするだけでは不十分です。

今回実装したインタプリタでは、BCに加えて以下のT, Vコンビネータへの置き換えもしています。(Unlambdaの組み込み関数vとは別物です)

  ``Txy = ```SI`Kxy = `yx
  ```Vxyz = ```S`Tx`Kyz = ``zxy

Tは第2引数を第1引数に適用するコンビネータで、Vへの置き換えの中間段階として導入しました。VはUnlambdaでオブジェクトのペアを表現するときによく使われる表現 (cons) です。ペアをS, K, Iの組み合わせでなく単一のオブジェクトとして表せるため、メモリの節約になります。特にELVMでUnlambdaにコンパイルされたプログラムは非常に多くのペアを作るためこの最適化が有効で、ELVMのセルフビルドをするとunl.cでは2.6GBのメモリが必要だったのが、1.2GB程度で済むようになりました。


  1. make unl を実行すると生成される8cc.c.eir.unlを使用

UnlambdaでVMを実装する(後編)

Esolang Advent Calendar 2016 3日目の記事です。

今回は、前編で説明したデータ構造を使って、どうやってEsolang VMの実行をシミュレートするUnlambdaプログラムを構成するかを解説します。 

実装方針

まずいくつかのコンセプトを説明します。

VMの状態

実行中のVMの「状態」を表すデータ構造を定義します。といっても単なるリストで、

[regs, memory, add, sub, eq, lt, load, store, putc, getc]

という形をしています。最初の要素regsレジスタの値のリストで、[PC, A, B, C, D, BP, SP]の順に並んでいます。2番目の要素memoryは前編で説明したメモリを表す2分木です。3番目以降の要素は「ライブラリルーチン」で、コンパイルされたコードはこれらの関数を呼び出して計算を実行します。(前編で説明したincなどはサイズが小さいので、コンパイルするときに毎回埋め込んでいます。)

命令の実行

VMは命令を実行するごとに、レジスタやメモリの状態が変化していきます。しかし関数型言語であるUnlambdaにはデータ構造を破壊的に書き換える方法は存在しません。 そこで今回の実装では、VMの各命令を「VMの状態を引数に取り、命令実行後の新しいVMの状態を返す」関数として実現します。

メインループ

プログラムの実行は初期状態のVMからはじめて、以下を繰り返すことで実現できます。

  • 現在のVMの状態におけるPCレジスタの値を使ってコード領域を参照し、対応する関数を得る
  • PCに1を加えた新しいVMの状態を作り、その関数に適用する
  • 関数の戻り値を新しいVMの状態とし、最初に戻る

前回、メモリは2分木で表現されていることを説明しましたが、プログラムもPCの値から関数へのマッピングと考えられるので、メモリと同様に2分木で表現します。(データ領域のメモリとは別の木になります。)命令のフェッチはメモリのロードと同じように、この2分木をPCのアドレスを使って辿ることで実現できます。

プログラムの中でジャンプ命令が実行されると、PCの値が書き換わったVMの状態が返ってくるので次のループではジャンプ先のPCが参照されます。そうでない場合は、2番目のステップでPCに1が足されているので直後の命令が実行されます。

ELVMバックエンドの作成

それでは、実際のELVMバックエンドのコードを見ていきます。

プログラム全体の構造

Unlambdaコード生成の起点となる関数がtarget_unlです。 最初のunl_emit_tick(2)は関数適用演算子`を2つ出力するだけです。その後unl_emit_core, unl_emit_text, unl_emit_dataの3つの関数を順に呼んでいます。つまりプログラム全体は``<core><text><data>となり、coreにtextとdataを適用した形になります。

命令をUnlambdaにコンパイルする

unl_emit_text関数はELVM IR形式の命令列をUnlambdaの関数へとコンパイルして出力します。

ELVMのコード領域の表現はちょっと変わっていて、基本ブロック内の複数の命令がひとつのPC(プログラムカウンタ)に入っています。基本ブロック内の命令列I1, I2, ..., Inをそれぞれ関数にコンパイルしたものをf1, f2, ..., fnとすると、あるVMの状態vmから基本ブロック実行後の状態vm'を得る関数は以下のように書けます。

vm' = fn(...(f2(f1(vm))))

Unlambdaバックエンドでは基本ブロックごとにひとつの関数(上のf1, f2, ..., fnの合成関数)を生成して、プログラム全体はそれらの関数のリストとして出力します。このリストがVM Coreに渡されると2分木に展開され、メインループで使用されます。

基本ブロックのコンパイル

基本ブロックのコンパイルunl_emit_chunk関数で行います。ELVM IR命令I1, I2, ..., Inは連結リストとして引数instに渡されますが、出力はfn, ..., f2, f1の順で書き出したいのでまずリストを反転しています。それぞれの命令のコンパイルunl_emit_op関数で行い、全体の式は

compose(fn, (..., compose(f2, f1)))

という形になります。composeは関数を合成する関数で、compose(f,g)(x) = f(g(x))になります。

命令のコンパイル

unl_emit_op関数はELVM IRの命令ひとつをUnlambdaの関数に変換して出力します。 例として、putc AレジスタAの値を文字として出力)という命令がどのようにコンパイルされるか見てみましょう。

命令はVMの状態を引数にとり、新しいVMの状態を返す関数としてコンパイルするのでした。putc命令はVMの状態を変更しないので、文字を出力したら渡されたVMをそのまま返せば良さそうです。文字の出力は、VM coreに含まれるライブラリ関数のひとつlib_putcにレジスタの値を渡せば出力してくれます。

というわけで、出力すべき関数の輪郭はこうなります。 組み込み関数kは引数2つを取り1つ目を返すので、この式全体はvmを返すことになります*1

λvm. ((k vm) (lib_putc regA))

ライブラリ関数はVM構造体に含まれていて、lib_putcVM構造体をリストとして見たとき9番目の要素になります。また、regAというのはレジスタAの値で、レジスタリストはVM構造体の先頭要素、レジスタAはレジスタリストの2番目の要素です。したがって上の式は以下のように書き換えできます。

λvm. ((k vm) ((nth 8 vm) (nth 1 (car vm))))

nthはリストの0から数えてn番目を取り出す関数です。 (nth n lst)はnのチャーチ数c(n)を使うと、((c(n) cdr lst) ->car)と書けます。つまりlstにcdrをn回適用した後、carをとる操作です。->carは"後置car"で、単なるkコンビネータです。nthを展開すると、上の式は以下のようになります。

λvm. ((k vm) (((c(8) cdr vm) ->car) ((c(1) cdr (car vm)) ->car)))

carやcdrなどの基本的な関数、24以下の数のチャーチ数などはunl.cの先頭付近にUnlambdaのコード片として定義されています。あとはこの式からラムダ抽象を取り除いて(Un-lambdaして)やれば、Unlambdaの組み込み関数のみを使った形にできます。

ラムダ抽象を取り除く

ラムダ式をUnlambdaの式に変換するには、前編の冒頭で紹介した記事にも記載されている4つの規則を適用します。

規則1: λx.(M N) ≡ ((s λx.M) λx.N)
規則2: λx.x     ≡ i

# 式M の中で x が自由変数として現れないとき
規則3: λx.M     ≡ (k M)
規則4: λx.(M x) ≡ M

どうしてこうなるのか、という説明はこちらをどうぞ。

これを先ほどの式に適用して変数vmに対するラムダ抽象を取り除き、カッコをUnlambdaの適用演算子`に置き換えると以下のようになります。コメントはunl.cで該当部分を出力している関数です。

``s           # case PUTC:
  k           # case PUTC:
 ``s          # unl_lib_putc
   ``s        # unl_lib_putc -> unl_emit_lib
     `c(8)    # unl_lib_putc -> unl_emit_lib
      cdr     # unl_lib_putc -> unl_emit_lib
    `k        # unl_lib_putc -> unl_emit_lib
     ->car    # unl_lib_putc -> unl_emit_lib
  ``s         # unl_emit_value -> unl_getreg -> unl_nth_begin
    ``s       # unl_emit_value -> unl_getreg -> unl_nth_begin
      `k      # unl_emit_value -> unl_getreg -> unl_nth_begin
       `c(1)  # unl_emit_value -> unl_getreg -> unl_nth_begin
        cdr   # unl_emit_value -> unl_getreg -> unl_nth_begin
     car      # unl_emit_value -> unl_getreg
   `k         # unl_emit_value -> unl_getreg -> unl_nth_end
    ->car     # unl_emit_value -> unl_getreg -> unl_nth_end

car, cdr, c(n)などは実際にはunl.c先頭付近で定義されているskiのみからなる文字列が出力されます。unl.cではラムダ式の生成→ラムダ抽象の除去というステップを経ずに直接コードを生成しているため読みにくいですが、上で考えたラムダ式に対応する関数が出力されています。

以上 putc A のコード出力を例に説明しましたが、ほかの命令も似たような考え方でUnlambdaの関数にコンパイルできます(レジスタの書き換えとかちょっと面倒ですが)。

データ領域のコンパイル

target_unlに渡されるModule構造体のdataメンバには、メモリの初期値が0番地から順に入っています。unl_emit_data関数は各番地の値をUnlambdaでの数値表現(24要素のリスト)に変換し、Unlambdaのリストとして出力します。このリストはVM coreへの引数となり、初期化ルーチンによってメモリの2分木表現へと展開されます。

VM core

unl_emit_core関数は固定の共通コードを出力します。共通コードはひとつの関数になっていて、unl_emit_textが出力した関数のリストとunl_emit_dataが出力したデータ領域のリストを引数に取り、以下の処理を実行します。

  • コードと初期データを2分木に展開する
  • レジスタリスト、メモリ、ライブラリルーチンを含む最初のVM構造体を作る
  • VMの初期状態からメインループを開始する

固定コードは全体で50KBほどで、そのうちgetc, putc用のライブラリ関数は単純な繰り返しが多いのでunl.c内で生成しています。それ以外の部分(5.5KB)はunlcore.hに文字列として書かれています。

まとめ

この記事では前後編の2回に分けて、UnlambdaでELVM IRのプログラムをどのように実行するか解説してきました。ポイントをまとめると、

  • Unlambdaではすべては関数、ペアやリストといったデータ構造も関数で表現する。
  • 数値は24要素のリストで表現する。
  • メモリは2分木で表現する。破壊的書き換えはできないので、メモリに書き込むと新しい2分木が生成される。
  • VMの命令は、VMの状態を引数にとり新しい状態を返す関数にコンパイルされる。

こうして並べてみるといかにも遅そうですが、実際最初のバージョンはBrainfuckの10倍くらい遅くて、最適化してだいぶマシになりましたがまだBrainfuckより遅いです。ELVMのセルフホストのテスト (check_selfhost.sh) が終わるのに20日(!)かかりました。

Unlambda以外の関数型esolangでバックエンドを作る際も、ここで紹介した考え方の多くは適用できるはずです。ELVMバックエンド作成チュートリアルとして、@hak7a3さん(TeXバックエンド作者)の記事や@Linda_ppさん(Vim scriptバックエンド作者)の記事も参考になります。皆さんもぜひお気に入りのesolangでELVMバックエンドを作ってみて下さい。

*1:Haskellなどの文法に馴染みがないと読みにくいと思いますが、第1引数がvmで第2引数が (lib_putc regA) です。

UnlambdaでVMを実装する(前編)

Esolang Advent Calendar 2016 2日目の記事です。

ELVMにUnlambdaバックエンドを実装して、C言語のプログラムをUnlambdaに変換できるようにした話です。ちょっと長くなったので2回に分けました。

Unlambdaとは

UnlambdaはBrainfuckの関数型版とでもいうべき言語で、関数適用演算子`s, k, iなど少数の組み込み関数だけを使ってプログラムを書きます。

Unlambdaには変数すら無いので直接プログラミングするのは厳しくて、普通はラムダ式を使ってプログラムを書いて、あとからラムダを取り除く(だからUn-lambdaなのですね)変換をかけてやります。とはいえ、組み込み関数とその簡単な組み合わせで何ができるのか把握しておくと、小さくて速いプログラムが書けます。

Unlambda言語について - Qiita

この記事自体はUnlambdaを知らなくても、若干の関数型言語の知識があれば読めると思います。

ELVMとは

ELVMはesolang用のコンパイラ基盤で、高級言語(現在はC言語のみ)から各種のesolang用コードに変換できます。Cコンパイラ自体をコンパイルしてBrainfuckで動くCコンパイラを作ったり、Unlambdaで動くviを作ったりできます。

仕組みについてはid:shinichiro_hさんの記事スライドが詳しいですが、C言語のプログラムを一旦ELVM IRと呼ばれる単純な仮想マシンの命令列にコンパイルして、ELVM IRからBrainfuckやUnlambdaなどのターゲット言語に変換します。

仮想マシンの仕様はここにありますが、概要としては

  • 24bitレジスタ6つ
  • 24bitアドレスのメモリ。ひとつのメモリセルに24bitの値を格納できる
  • 使える命令は mov, add, sub, load, store, setcc, jcc, putc, getc, exit

という感じです。esolangで実装しやすいように非常に単純な仕様になっています。

Unlambdaでデータ構造を表現する

さてレジスタとかメモリとか言われても、Unlambdaには関数しかありません。組み込みの整数すらありません。なんとか関数を使ってさまざまなデータ構造を表現する必要があります。

ペア

最も基本的なデータ構造として、2つの値を保持するペアを考えます。これはUnlambda言語のサイトにも書かれていますが、cons, car, cdr の3つの関数で実現できます。

# ペア <x, y> を作る
cons = λxyf.fxy = ``s``s`ks``s`kk``s`ks``s`k`sik`kk

# ペア <x, y> から x を取り出す
car = λp.p(λxy.x) = ``si`kk

# ペア <x, y> から y を取り出す
cdr = λp.p(λxy.y) = ``si`k`ki

consはx, y, fの3つの引数を取り、fxyを適用する関数です。普通はxyのみをまず適用してペアを作り、fは値を取り出すときにcarかcdrによって与えられます。

carは引数pを取り、p(λxy.x)を適用します。(λxy.x)は引数を2つとり、1つ目の引数を返す関数です*1pはconsで作ったペアなので、consのf(λxy.x)を入れるとペアの最初の要素が返ってくるのがわかると思います。同様にcdrはペアの2つ目の要素を取り出します。

リスト

リストはペアを使って作ることができます。要素 e1, e2, ..., en を持つリストは以下のように表現します。

[e1, e2, ..., en] = (cons e1 (cons e2 (... (cons en v)...)))

Lispでリストを作るときと同じですね。リストの終端にはUnlambdaの組み込み関数vを使います。

数値

Unlambdaでの数値表現の定石はチャーチ数ですが、大きな数を使うと遅くなってしまうため、24ビット整数を扱う必要があるELVMには向いていません。

そこで数値の表現としては24要素のリストを使い、各要素はUnlambdaの組み込み関数を使って、`kiで0のビット、kで1のビットを表すことにします。要素は下位ビットから並べます。例えば3の2進表現は11なので、以下のように表現できます。

[k, k, `ki, ..., `ki]  # 24要素のリスト
= (cons k (cons k (cons `ki (... (cons `ki v)...))))

ELVMのシンプルな仕様のおかげで、必要な算術演算は数個だけ(add, sub, eq, lt)です。

例: inc関数

数値を扱う処理の例として、数値に1を加える関数incの実装を見てみましょう。(ELVMにはincやdecといった命令はありませんが、スタック操作などでインクリメント/デクリメントが多用されるため専用の処理を用意しています。)説明のため、記法や変数名は変えてあります。

incRec = cons (λt. (cons `ki) (t incRec))
              (cons k)
inc n = n incRec

…意味がわかりませんね。ペアや数値の関数としての表現をフル活用して最適化しているため分かりづらくなっています。読み解いてきましょう。

主な処理は再帰関数incRecのほうに書かれていて、incは与えられた数値にincRecを適用しているだけです。(数値は関数で表現されているので適用できるのです。)数値nがリスト[b1, b2, ..., b24]だとすると、inc n[b1, b2, ..., b24] incRecになります。リストはペアで表現されているので、これはつまり(cons b1 (cons b2 ...)) incRecと同じです。

さてペアもまた関数で表現されているのでした。cons x y f = f x yなので、上の式の一番外側のconsを展開するとincRec b1 (cons b2 ...)になります。incRecの定義を展開すると、

(cons (λt. (cons `ki) (t incRec)) (cons k)) b1 (cons b2 ...)

となります。複雑になってきましたがもう少し辛抱してください。さらに先頭のconsを展開すると以下のようになります。

(b1 (λt. (cons `ki) (t incRec)) (cons k)) (cons b2 ...)

b1はincの引数nの最下位ビットで、0なら`ki、1ならkです。もしb1が`kiなら、`kiは引数を2つ取り2つ目の引数を返すので、

(cons k) (cons b2 ...)

となり、これがincの結果になります。リスト[`ki, b2, ..., b24][k, b2, ..., b24]になったので、元の数より1大きい数になっていることがわかります。

次にb1がkの場合を考えます。kは引数を2つ取り1つ目の引数を返す関数なので、b1を適用した結果は

(λt. (cons `ki) (t incRec)) (cons b2 ...)

になります。ラムダ式を適用してt(cons b2 ...)を代入すると、

(cons `ki) ((cons b2 ...) incRec)

となり、これは最下位ビットが`kiつまり0で、2番目以降のビット列をintRecで1加算したもの、つまり繰り上がりの処理です。こちらも元の数に1を足した結果になることがわかります。これで大体うまくいきそうですが、再帰の終了条件らしきものがありません。nのすべてのビットが1だった場合何が起こるのでしょうか?

リストの終端はvを使って表すのでした。これを上の式に当てはめると、最上位ビットb24が1だった場合の再帰の最終段は

(cons `ki) (v incRec)

となり、(v incRec)vですからそれ以上の再帰は起こらず、結果として24個の要素すべてが`kiのリスト、つまり数値0が返ります。

このように、ちょっとトリッキーでしたがちゃんと24ビット整数に1を加える処理になっていることがわかります。

メモリ

ELVMは24ビットアドレスのメモリ空間を持ち、各アドレスには24ビットの数値を格納できます。 メモリもペアを使って表現しますが、今度はリストではなく2分木を使います。

メモリ全体は高さ24の完全2分木になります。メモリを参照するときはアドレスを1ビットずつ見ていき、0なら左の子、1なら右の子を辿っていきます。メモリに値を格納するときは、根から対象アドレスの経路にあるノードのみが書き換えられ、他のノードは再利用されるのでそれほど効率は悪くありません。関数型データ構造というやつですね。

ちなみに初期化時のメモリは左の子と右の子が同じノードを指すDAGになっていて、値が書き込まれた部分だけが本当の2分木になります。多くのプログラムはメモリを目一杯使わないので、これでUnlambdaインタプリタの消費メモリ量を節約できます。

前編のまとめ

今回はELVM Unlambdaバックエンド実装の下準備として、様々なデータ構造を関数のみを使って実現する方法を解説しました。inc関数の処理を詳しく見ることで、すべてが関数であるUnlambdaでプログラミングするときの雰囲気を感じていただけたと思います。

明日の後編ではいよいよUnlambdaバックエンドの実装を見ていきます。

*1:これはUnlambdaの組み込み関数 k そのものです。

EsoLang vi

https://github.com/irori/elvi

BrainfuckやUnlambdaで動くvi風エディタができました。 Jody Bruchon氏のviクローンを元にELVMコンパイルできるようにしたものです。

標準入出力しか使えないのでファイルの読み込み・保存はできません。コマンドも最小限しかありませんが、真面目に使うものでもないので構わないでしょう。

数種類のesolang用コードが生成されるので、言語による書き味の違いを試してみると良いでしょう。Whitespaceは滑らか、Unlambdaは重厚な感触になります(まあレスポンスの遅さが違うだけなんですが)。

ELVMのバックエンドによっては実行前に入力をすべて読み込むようになっており、そのような処理系では使えません。残念ながらvi on vimはできません。

実装について。端末のサイズ取得とかカーソル移動とかはエスケープシーケンスで頑張ってます。端末を直接入力モードにするのは標準入出力だけではどうしようもないので、シェルスクリプトで初期設定と後始末してます。

数値を文字列にして出力する部分が速度上のボトルネックになっていた(カーソル移動のエスケープシーケンスとかステータスラインの位置表示に必要)ので、除算を使わずテーブル引きで文字列化するようにしたら大分マシになりました。

rogueとかも移植できるかなと思ってましたが、viでこの速度だとちょっと厳しいかもですね。

8cc.unl

Unlambdaで動くCコンパイラができました。

https://github.com/irori/8cc.unl

id:shinichiro_hさんのbflispで使われている改造版8ccアセンブリ出力からUnlambdaへのトランスレータです。

これで同一のCプログラムをBrainfuckとUnlambdaの両方で動かせます。便利!

ただBrainfuckと比べてもかなり重くて、8ccのセルフコンパイルをすると10GB以上のメモリを消費して37時間かかりました。整数の表現が真偽値24個のリスト(もちろん真偽値もリストも関数で表現される)で結構でかいので、メモリを大量に使うプログラムだと厳しいようです。別の整数表現も試してみたんですが遅かったので断念しました…。

Lazy K でも同じようにやればできると思います。気が向いたらそのうち。

BfLazyK

Lazy K のオリジナルの配布物には bf2lazy.c というファイルが含まれていて Brainfuck プログラムを Lazy K にコンパイルできるのですが、逆に Brainfuck で Lazy K のプログラムを動かす方法はこれまで存在しませんでした。Lazy K で Brainfuck の配列のようなものは比較的簡単に実現できるのに対し、Lazy K の実行はポインタを含む小さなオブジェクトを作っては捨て、作っては捨て…という感じになるので Brainfuck で実現するのは明らかに大変そうです。現実的な速度で動かすのは無理かもしれません。

ところが id:shinichiro_h さんがなんと Lazy K どころか Lisp が動くインタプリタBrainfuck で作ってしまいました。16bit の仮想マシンを定義してそのアセンブリから Brainfuck に変換するというもので、便利なことに仮想マシンアセンブラコードを生成するCコンパイラまで使えます。

Lisp が動くなら Lazy K も動くだろ、ということで以前作った Lazy K インタプリタを仮想 16bit マシン環境で動くようにして Brainfuckコンパイルしてみました。

https://github.com/irori/bflazyk

手を入れたのは主にメモリ管理の部分で、ヒープ領域を固定にしたのと、値の表現でポインタか即値データかを下位ビットで判断していたのを数値比較にした(ビット演算が重いので)のが大きな変更です。 ヒープ領域は 48k ワードありますが、Copying GC のために2分割して片方しか使わないのでメモリ制限は厳しめです。どのくらい厳しいかというと剰余を使うアルゴリズムFizzBuzz を動かしたら 50 あたりでメモリ不足になってしまいました。

実行速度ですが、生成された .bf を bflisp 付属の bfopt.cc で C に変換して gcc で -O なしでコンパイルしたところ Hello, world が48秒、FizzBuzz が22分でした。

lazy2c スクリプトは Lazy K プログラムを埋め込んだインタプリタの .c ファイルを生成します。これを C → Brainfuckコンパイラと組み合わせることで、Lazy K から Brainfuckコンパイラとして使えます。さらに hs2lazy と組み合わせると Haskell から Brainfuck への(超非効率な)コンパイラになりますね。*1

*1:ちなみに Haskell から Brainfuck へ直接変換するコンパイラがあるようです http://www.xanxys.net/hs2bf/

BlokusFS

ブロックスデュオのゲーム木をマウントできる FUSE ファイルシステムを作りました。

https://github.com/irori/BlokusFS

使い方

チェックアウトして src ディレクトリ内のソースをコンパイルします。 FUSE の開発用ライブラリが必要です。

$ sudo apt-get install libfuse-dev   # Ubuntuの場合
$ git clone https://github.com/irori/BlokusFS.git
$ cd BlokusFS
$ make -C src

src/blokusfs にマウントポイントを与えて実行します。

$ mkdir mnt
$ src/blokusfs mnt

これでマウントできました。忘れないうちに書いておくと、使い終わったら fusermount コマンドでアンマウントします。

$ fusermount -u mnt

マウントした状態では mnt の中に大量のディレクトリといくつかのファイルが見えます。

$ src/blokusfs mnt  # もう一度マウント
$ ls -px mnt
35j2/  35k2/  35k7/  35l2/  35l7/  35o3/  35o6/  35q0/  35q2/
44k1/  44k6/  44l1/  44l6/  44m1/  44m6/  44n1/  44n6/  44p0/
...
75j2/  75k3/  75k6/  75l3/  75l6/  75o2/  75o7/  75q1/  75q3/
board  piece  score  value

このファイルシステムでは各ディレクトリがゲームの状態を表していて、ルートディレクトリは初期状態(ピースがまったく置かれていない状態)に対応します。 子ディレクトリは初期状態から先手が打てる手の 4文字コードです。

例えば mnt/66t0 は先手が 66t0 を打った状態になり、その子は後手が選択できる手になります。

$ ls -px mnt/66t0
8Aj2/  8Ak2/  8Ak7/  8Al2/  8Al7/  8Ao3/  8Ao6/  8Aq0/  8Aq2/
99k1/  99k6/  99l1/  99l6/  99m1/  99m6/  99n1/  99n6/  99p0/
...
CAj2/  CAk3/  CAk6/  CAl3/  CAl6/  CAo2/  CAo7/  CAq1/  CAq3/
board  piece  score  value

各ディレクトリにあるファイル board は盤面の状態、piece は各プレイヤーの手持ちピース、score は現在のスコア(置いたマスの数)です。value は盤面の評価値(後述)です。

$ cat mnt/66t0/board
..............
..............
..............
..............
....1.........
....111.......
.....1........
..............
..............
..............
..............
..............
..............
..............
$ cat mnt/66t0/piece
a b c d e f g h i j k l m n o p q r s u
a b c d e f g h i j k l m n o p q r s t u
$ cat mnt/66t0/score
5
0
$ cat mnt/66t0/value
-56

piece と score は1行目が先手、2行目が後手です。

子ディレクトリを辿っていくことでゲームが進んでいきます。子がないディレクトリに到達したところでゲーム終了です。

ブロックスデュオのゲーム木の大きさは 1070 〜 1080 と推定されていますが、これで歩きまわり放題ですね!

評価値

各ディレクトリの value ファイルには、盤面の評価値を hmmm の評価関数で計算した値が入っています。 ただし、後手番のディレクトリでは値の符号を反転しています。つまり先手番では評価値が大きいほうが先手有利、後手番では評価値が大きいほうが後手有利です。これによって探索のコードが簡単になります。

評価値は board ファイルと piece ファイルから計算できるのでファイルシステムに含めなくても良かったんですが、あると便利なので…。

AIを作る

ゲームのルールと評価関数はファイルシステムに組み込まれているので、探索ルーチンを書くだけで AI が作れます。 ファイルシステムにする一番のメリットは言語に依存しなくなることで、ファイルの読み込みとディレクトリの一覧取得ができる言語ならなんでも使えます。 とりあえずシェルスクリプトで書いてみました。

上がネガマックス法、下がネガアルファ法を実装したものです。探索したい局面のディレクトリと探索深さを引数にして実行すると、探索の結果最善と思われる手を出力します。

$ time ai/negaalpha.sh mnt/66t0 2
8Aj2 71
8Ak2 62
8Ak7 51
8Al7 48
9Bk3 47
9Bl3 46
9Bl3
ai/negaalpha.sh mnt/66t0 2  0.97s user 0.98s system 44% cpu 4.362 total

最後の 9Bl3 以外は stderr に出力される途中経過です。

さてシェルスクリプト版は案外簡単に書けてしまったので、別の言語も試してみることにしました。 Makefile です。(GNU make 専用)

$ time make -f ai/negaalpha.mk DIR=mnt/66t0 DEPTH=2
-46 -46 99999 9Bl3  # stderr出力
9Bl3
make -f ai/negaalpha.mk DIR=mnt/66t0 DEPTH=2  0.46s user 0.94s system 15% cpu 9.251 total

ネガマックス版の negamax.mk を解説してみます。コーナーケースの処理等を省くとこんな感じになっています。

depth-1 := $(word $(DEPTH), 0 1 2 3 4 5 6 7 8 9)

ifeq ($(MAKELEVEL), $(depth-1))

negamax: $(DIR)
  sort -n $(DIR)/*/value |head -n1

else

subdirs := $(wildcard $(DIR)/????)
.PHONY: negamax $(subdirs)
tempfile := $(shell mktemp)

negamax: $(subdirs)
  sort -r -n $(tempfile) |head -n1 |sed -e 's/^/-/' -e 's/^--//'
  rm $(tempfile)

$(subdirs):
  $(MAKE) DIR=$@ -f ai/negamax.mk >>$(tempfile)

endif

どうでもいいけどシンタックスハイライト激しすぎですね…。

変数 DIR と DEPTH は外から与えられます。1行目では「depth-1」という名前の変数を定義しています。 DEPTH から 1 を引いた値にしたいのですが、組み込みの算術演算がないので word 関数を使っています。 特殊変数 MAKELEVEL には make の再帰呼び出しの深さが入っているので、例えば DEPTH が 3 なら 2 回目の再帰 (sub-sub-make) で 5 行目の negamax ルールが実行されます。 この場合、DIR のサブディレクトリすべての value ファイルの中で一番小さい値が出力されます。 MAKELEVEL が DEPTH に等しい時に value ファイルを cat したほうが単純ですが、高速化のために一段浅いところで処理しています。

MAKELEVEL が depth-1 より小さい場合は、各サブディレクトリに対して再帰します。$(MAKE) で始まる行がそれで、結果はテンポラリファイルに追記されていきます。 すべての再帰呼び出しの結果が集まったら、negamax ルール(else の中のほう)が実行されて評価値が最大のものが選ばれ、符号反転して出力します。 実際は MAKELEVEL が 0 のときは最大の評価値のディレクトリ名をかわりに出力するなどの処理が入っています。

ちなみに negamax.mk は再帰を並列実行可能なので、マルチコア環境では make に -j オプションをつけると探索が速くなります。

一方ネガアルファ版の negaalpha.mk はループの各実行で α, β の値を受け渡していく必要があるため -j は使えません。 make の変数もループ中に変化させることはできないので、テンポラリファイルに(今までの最良の評価値、α、β、最良の手の4文字コード)の組を入れて awk で頑張るという遅そうな実装になっています。βカットが起こると make の実行が中断されるため何やらエラーっぽいのが出力されますが気にしないでください。

遊ぶ

interface/play ファイルはゲームのフロントエンドです。100行足らずのシェルスクリプトですが、いっちょまえに盤面を色付きで表示したりします。 オプションで AI のプログラムを指定して対戦できます(自分の手は4文字コードを入れないといけないので大変ですが…)。

$ interface/play -v ai/negaalpha.sh -o "make -f ai/negaalpha.mk" mnt

などとすると、シェル対 make の対戦が見られます。

感想

さすがに遅いので本格的な AI には使えないですが、ファイルシステムとして扱えると既存のツールで色々出来て楽しいです。

あと使い終わったらアンマウントしておきましょう。忘れていたらバックアップスクリプトが走ってえらいことになりました。