Unlambda で限定継続

Unlambda

Esolang Advent Calendar 2013 用の記事です。

Unlambda という esoteric language がありまして、s, k, i といった少数の組み込み関数と関数適用演算子 ` のみでプログラムを書くという、Brainfuck の関数型版とでもいうような言語です。

Unlambda の特徴のひとつとして、c (call-with-current-continuation, 略して call/cc) 関数の存在があります。c は「現在の継続を取り出す」関数で、これを使うと例外処理のようなことができたり、ループが書けたり、Hello, world! が短くなったりするのですが、なにしろわかりにくいので Unlambda のとっつきにくさの一因となっています。*1

Unlambda の外に目を向けると、プログラミング言語で継続を扱うやり方は call/cc 以外にも、限定継続あるいは部分継続と呼ばれる方式があります。ざっくり言うと、call/cc による継続はある時点からプログラムを終了するまでの処理を表すのに対し、限定継続は処理の特定の範囲を表したものです。call/cc の代わりに、継続を切り取る起点を指定する reset と、reset した場所からの継続を取り出す shift という2つの制御演算子を使います。*2
この限定継続も call/cc に劣らないわかりにくさで、検索すると解説記事がたくさん出てきます。

そんな shift/reset が call/cc の代わりに Unlambda で使えたらどうだろう、ということで作ってみました。

Unlambda-dc

Unlambda-dc は Unlambda に 2 つの関数、p (reset) と f (shift) を追加し、c (call/cc) を削除したものです。Unlambda-2.0.0 の実装をベースに、C と OCaml のインタプリタを用意しました。

https://github.com/irori/unlambda-dc

p (reset)

関数 p に引数 x を適用すると、x に v を適用します。

  `px => `xv

例えば、`p.a という式は `p.a => `.av => v と評価が進んで、最後のステップで a が表示されます。

役に立たない関数に見えますが、`xv の実行中に f (shift) が呼ばれると特別なことが起こります。

f (shift)

関数 f に引数 x を適用すると、この式から直近で p を実行した場所までの継続を引数にして x を呼び出します。x を実行した後は、直近の p を呼び出した場所に戻ります。

何を言っているかわからないと思いますので、例を見てみましょう。

  `p`d`k````.1f.2.3i

reset の中で ````.1f.2.3i を実行したいのですが、`p````.1f.2.3i と書いたのでは p の適用前に ````.1f.2.3i が評価されてしまうので d と k を使って実行を遅らせています。E=````.1f.2.3i とすると、

  `p`d`kE
  => ``d`kEv  # p の適用
  => ``kEv    # ここで E が評価される
  => Eの値

となり、p の適用が起こってから E が評価されることがわかります。
さて、````.1f.2.3i を実行すると何が起こるでしょうか。まずいちばん内側の `.1f が実行されて 1 が表示され、```f.2.3i になります。
ここで f の適用が起こります。f は現在から p が適用された場所までの継続を取り出し、f に渡された引数にその継続を適用します。いま f の引数は .2 なので、取り出された部分継続を <cont> とすると、`.2<cont> となり、次のステップで 2 が表示されて <cont> が値となります。この <cont> がどこの戻り値になるかというと、なんと p を適用したところに戻ります。つまり .3 は表示されません。
まとめてみます。角括弧は reset した位置を表します。

  `p`d`k````.1f.2.3i
  => [``d`k````.1f.2.3iv]
  => [``k````.1f.2.3iv]
  => [``k```f.2.3iv]    # 1 が表示される
  => `.2<cont>
  => <cont>             # 2 が表示される

この <cont> は何者でしょうか。<cont> は f の適用から直近の reset までの継続、つまりこの例では [``k``@.3iv] になります。@ は f を適用した位置です。この継続に値 x を適用すると、@ を x に置き換えた ``k``x.3iv になります。つまり <cont> は引数 x をとって ``k``x.3iv を実行する関数と同じです。
確かめてみましょう。先ほどのプログラムの外側を ` と .4 で囲んだプログラムを実行すると、

  ``p`d`k````.1f.2.3i.4
  => `[``d`k````.1f.2.3iv].4
     (中略)
  => `[``k``@.3iv].4    # "12" が表示される
  => ``k``.4.3iv
  => ``k`.3iv           # 4 が表示される
  => ``kiv              # 3 が表示される
  => i

となり、"1243" の順で出力されます。

応用編:fib

以下は Unlambda のサイトで最初の例として挙げられている、フィボナッチ数列を一行ずつ * の数として出力するプログラムです。このプログラムは c を使っていないので、Unlambda-dc でもそのまま動きます。

 ```s``s``sii`ki`k.*
  ``s``s`ks
      ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
   `k``s`ksk

これを書き換えて「i を適用するたびにフィボナッチ数をひとつ出力し、次のフィボナッチ数から出力する関数を返す」関数 fib を作ってみます。```<fib>iii と3回適用するとフィボナッチ数列の最初の3つが表示される感じです。

まず、元のプログラム全体を reset で囲みます。上で説明したように、reset の適用前に本体が評価されないように d と k で評価を遅らせます。

`p`d`k
 ```s``s``sii`ki`k.*
  ``s``s`ks
      ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
   `k``s`ksk

次にどこかに shift を入れなければなりませんが、改行を出力している部分に注目します。下から2行目の r は改行を出力して引数を返す関数ですが、これを `d`fr に書き換えます。

`p`d`k
 ```s``s``sii`ki`k.*
  ``s``s`ks
      ``s`k`s`ks``s``s`ks``s`k`s`k`d`fr``s`k`sikk
   `k``s`ksk

`d`fr は適用されると `fr が評価され、f の適用で限定継続が取り出されて `r<cont> となります。r の適用で改行が出力されたあと、p を適用したところ、つまりプログラムの一番外側に戻ってきます。このとき値は残りの計算 <cont> です。
この <cont> に引数を与えると、`fr を実行したところから評価を継続します。いま r (newline関数) を shift を含んだ式に置き換えたので、r と互換性のある値、つまり i を <cont> に渡すことにします（r は改行を出力する以外は i と同じ関数）。i を渡すと再帰がもう1回りして次のフィボナッチ数が出力され、また残りの計算 <cont'> が返ってきます。<cont'> にまた i を渡すと次のフィボナッチ数が出力され <cont''> が返り…と続いていきます。
上のプログラムが fib 関数になります。6 回ほど i を適用してみましょう。

``````
 `p`d`k
  ```s``s``sii`ki`k.*
   ``s``s`ks
       ``s`k`s`ks``s``s`ks``s`k`s`k`d`fr``s`k`sikk
    `k``s`ksk
 iiiiii

実行結果*3:

 
*
*
**
***
*****
********

i を適用する回数を変えると表示される行数が変わります。

（適当な）まとめ

フィボナッチ数列のプログラムの内容をほとんど理解しなくても、ループを1回ずつ止める fib 関数を作ることができました。限定継続を使うと、処理の外側と内側をひっくり返すようなことが簡単にできます。処理があっちこっち飛ぶので理解しにくくなるのが難点ですが、どうせ読めない Unlambda なので気にせず使うといいと思います。

*1:理解してしまえば使うのは難しくなくて、むしろ d (delay) オペレータのほうがハマりやすかったりするのですが。

*2:prompt と control という別の制御演算子を使う流儀もあります。

*3:実はこれ、空行から始まって i の適用より 1 回多い 7 行出力されています。出力のあとに限定継続を返すようにしたため、fib に引数を与える前に最初の行が出力されてしまうためです。

Hello, world!

Lazy-K

http://d.hatena.ne.jp/rst76/20131109/1383953947

399bytes の解説書くのをサボっていたら id:rst76 さんが解読して記事にしてくださいました。なんかすいません…

そして 365bytes! ついに Grass より上に。
http://golf.shinh.org/p.rb?hello+world#ranking

再帰の代わりにチャーチ数は気づいてしかるべきでしたね…

ICFP Programming Contest 2013

https://research.microsoft.com/en-us/events/icfpcontest2013/

今年も楽しくソロ参加でした。ソースコードはこちら。

http://irorin.org/icfpc2013_irori.tar.gz

問題

BV という単純な言語で書かれた 64bit 整数上の関数があります。入力となる数を好きに選んでコンテストのサーバーに送ると結果が返ってくるので、この関数の式を推定してください。ただし、

  • 式の大きさと使われている演算の種類はあらかじめ与えられる。
  • 推定した式が間違っていたら、反例となる入出力の値が返される。
  • いちど問題に挑戦し始めると、5分以内に正解しなければ得点できない。

問題が 1000 問以上あって（途中で増えたりした）、72時間以内に何問解けるかな、という問題でした。

使用言語

ソルバ本体は Haskell で、フロントエンドを Ruby で書きました。
Haskell は数年ぶりに触ったけど意外に忘れてませんでした。Haskell 98 が最新規格じゃなくなっててびっくりしたのは秘密です。
あと、BV の S 式を Haskell の read で読めるように変換するためだけに Scheme もちょっとだけ使いました。
残念ながら Unlambda は今年も出番がありませんでした。

マシン

自宅の PC 2 台 + ラップトップ 1 台。手元の計算資源だけで頑張りました。無課金プレイです。(?)
複数台使ったのは時間内に全問終わらせるためで、同じ問題を並列で解かせたりはしていません。

戦略

4種類の問題 (simple, fold, tfold, bonus) について、それぞれ専用のソルバーを作りました。といってもやってることはほとんど同じで、

  1. 数十個の入力/出力の値のペアを用意します。
  2. Spec にある演算を使って、小さい順に式を生成していきます。式を最適化して重複を取り除きます。
  3. 生成された式を 1 で用意した入力値で評価して、すべて出力値が一致すればその式をサーバーに送信します。mismatch が帰ってきたら 1 のペアに追加して 2 に戻ります。

で、問題のクラスごとに細かい枝狩りなどを入れていきます。細かい工夫などはソースを見てください（めんどくさくなった）。

結果


感想

ICFPC にしては珍しく、関数型言語が活躍しそうな問題でした。難易度調整も絶妙で 3 日間フルに楽しめました。

あと個人的には、今回みたいに手元で実行して結果だけ送信する方式のほうが好みです。AIを提出する方式だと、いろんな状況に対応できるように作りこむのって一人じゃモチベーション的にも時間的にもつらいんですよね。他方この方式だと計算資源を豊富に使える人が有利になっちゃうというのもありそうですが。

Lazy K Playground

Lazy-K

Lazy K もブラウザ上で実行できるようにしたいなぁ、でも JavaScript でインタプリタ実装するの面倒だなぁ、と思っているうちに世の中が進歩して簡単になったので作ってみました。

http://lazy-k.appspot.com/

いくつか例を。

http://lazy-k.appspot.com/p/kyYMG82oRh
http://lazy-k.appspot.com/p/2koJ2YQ9fD

App Engine はコードの保存のために使っているだけで、実行はブラウザ上で行われます。バックグラウンドでインタプリタを動かすのに Web Workers を使っている関係で IE9 以前では動きません。ごめんなさい。

適当なベンチマークもしてみました。ベンチマークといえば円周率、ということで円周率を100桁計算するプログラムです。

http://lazy-k.appspot.com/p/jMQX90iL_S

手元のマシンでは以下のような結果になりました。

Firefox 22 80.1 sec.
Chrome 27 97.4 sec.
IE 10 314 sec.
ネイティブ (lazyk.c) 39.0 sec.

よく言われている通り asm.js に最適化された Firefox 22 ではネイティブの倍程度の実行時間になりました。Chrome も健闘してますね。

JavaScript Unlambda interpreter

Unlambda

http://inazz.jp/unlambda/
inazz さんがブラウザ上で動く Unlambda インタプリタを作っておられます。
実行中の式を表示しながらステップ実行できます。しかも速いです。 Adventure がサクサク動いてびっくりしました。

ICFP Programming Contest 2012

http://icfpcontest2012.wordpress.com/

今年は一人で参加してました。

問題は Boulder Dash 風のゲームを解く AI を作れというもの。TopCoder のマラソン(Marathon Match)にありそうな問題だなーという印象でした。マラソンと違うのは、コンテストの途中でルールの追加が予告されていることと、スコアボードがないので終了まで他のチームの状況がわからないこと。

え、じゃあ適当なマラソンに参加したほうが楽しいんじゃ…などということは考えないようにして、金曜の夜はシミュレータを実装して終わり。

土曜は朝起きたら最初の仕様追加（マップが水没していく）がアナウンスされていたのでシミュレータに実装して、後は lightning division 用に適当な局面評価で探索するソルバーをでっちあげました。

日曜起きると、新たにルールが２つ追加されていました。トランポリンとヒゲ。何だヒゲって。とりあえず追加仕様は置いておいて、寝ている間に思いついた(?)詰み検知ルーチンを実装。やっとまともに問題が解けるようになってきました。

引き続きトランポリンとヒゲの対応をシミュレータと AI に組み込んで、再度全マップを試してみたら contest*.map が解けなくなってる…。初めて git bisect のお世話になりました。これはいかんと思いテストスクリプトを整備。

そうこうしているうちに、次の追加ルールが発表されました。高階岩。これを実装して日曜は終了。

最終日はちょっとモチベーションの維持に失敗した感じでした。だらだらと AI のパラメータをチューニングして、大きいマップで壊れないようにして、駆け込みで幾つかのハックを追加して提出。

提出したソースコード。

配布されたマップでの成績はこんな感じでした。得点/ハイスコア の平均は86%。

マップ 得点 ハイスコア
contest1.map 212 212
contest2.map 281 281
contest3.map 275 275
contest4.map 575 575
contest5.map 1297 1303
contest6.map 1177 1177
contest7.map 869 869
contest8.map 1915 1973
contest9.map 3083 3095
contest10.map 3588 3634
flood1.map 945 945
flood2.map 281 281
flood3.map 846 1303
flood4.map 653 1594
flood5.map 575 575
trampoline1.map 426 426
trampoline2.map 1742 1742
trampoline3.map 554 5477
beard1.map 860 860
beard2.map 4461 4522
beard3.map 628 1789
beard4.map 1830 3103
beard5.map 655 946
horock1.map 745 762
horock2.map 747 747
horock3.map 1582 2406

感想

なんだか不完全燃焼な感じで終わってしまいました。ネタに走るという方向も一瞬考えたのですが、今回の問題で Unlambda とかで何かするのはちょっと難しそうなので諦めました。Befunge 力を上げておけばよかったのか…！
仕様変更に関しては、ゆるい作りにしていたお陰でそれほど困りませんでした。最適化が終わってからひっくり返されてたら発狂してたかもしれませんが。
次回はあまりマラソンっぽくない問題がいいなー。