ICFP Programming Contest 2014

http://icfpcontest.org/

うーん今年はあまりうまくいきませんでした。

今年の題材はパックマンで、プレイヤー側の AI を SECD マシン風のコードで、敵側を普通の 8 ビット CPU 風のコードで書けというもの。

金曜の夜は問題文(やたら長い)を読んでコードは書かず就寝。いつものパターンなら朝になると仕様のバグが取れてやりやすくなっているはず。

土曜はとりあえず順当に Lisp 風言語から AI CPU へのコンパイラを書く。SICP を引っ張り出してきて末尾再帰のやりかたを復習したり。それなりに動くコンパイラができたのが午後 3 時くらいで、そこから 6 時間で lightning division 用の AI を書く。方針としては、

  • マップの各マスを通った回数を覚えておいて、一番少ない方向に進む
  • 自分から直線上に敵がいたらそちらへは進まない

という感じ。Lightning division が終わって追加のタスク(敵側の AI を書く)が発表されたので、方針を考えつつ寝る。

日曜は敵側 CPU 用のアセンブラと AI を書く。適当にプレイヤーを追いかけるようにしたら前日に書いた AI が思ったより弱いことがわかってしょんぼり。プレイヤー側の AI にちびちび修正を入れるがあまりうまくいかない。AI の作り方とかよくわからんのよね……。このあたりから集中力が切れてきて、だらだらし始める。

月曜起きるとスコアボードができていた。自分の AI を送ってみるも全然ダメでしょんぼり。外はいい天気だなあ、有給だし遊びに行こうかなあ。

そんな感じでしょんぼりなまま終了。提出物はこちらになります。

今回は手も足も出なかった(というほどでもないけど)ので、上位チームはどんな AI を書いてたのか気になります。やっぱり真面目にゲーム状態を計算してたりするんでしょうか。自分は tick の計算とか面倒で逃げちゃったんですが。

Lazy K で Lisp インタプリタ

https://github.com/irori/lazyk-lisp
http://lazy-k.appspot.com/p/ptHm_GwfAY

Lazy K でも Lisp インタプリタを作ってみました。

機能は Unlambda 版とだいたい同じですが call/cc が無くなり、代わりに set でグローバル変数に代入できるようになりました。局所変数の書き換えは大変すぎるので断念しました…。

今回はジェネレータとして、以前作った Haskell → Lazy K トランスレータを使いました。200 行ほどの Haskell コードを変換して 300kb の Lazy K プログラムになりました。ジェネレータの抽象度が高い分、Unlambda 版よりかなり大きくなってしまいました。一方インタプリタのコーディングは単なる Haskell なのでこっちの方が楽でした。(モナドが使えないとか let でパターンが使えないとか、エラーメッセージが殆どノーヒントとか色々制限はありますが。)

ちなみに lisp.hs は正しい Haskell プログラムなので、GHC でもコンパイルできます。当たり前ですがコンパイルしたものはずっと速いです。

遅い理由のひとつはシンボルを文字列のまま扱ってるからで、Unlambda 版と同様にシンボルテーブルを作って整数比較で済むようにすればもう少し速くなると思います。

Unlambda で Lisp インタプリタ

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

3 連休だったので Unlambda で Lisp インタプリタを作ってみました。

Adventure を作ったときのコードジェネレータを流用して、今回新たに書いたコードは 400 行ちょっとでした。生成された Unlambda プログラムは 35kb ほど。

構文は quote, if, lambda, defun が、組み込み関数は基本的なリスト用関数 (cons, car, cdr) と四則演算が使えます。代入はありませんが、代わりに call/cc を使えるようにしてみました。数値は非負整数のみ使えます。内部表現はチャーチ数なので大きい数を作ると大変なことになります。全体的にエラー処理が甘いので壊れた式を入れるとおかしくなりがちです。

次回は Lazy K で Lisp インタプリタを作る予定です。

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!

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を提出する方式だと、いろんな状況に対応できるように作りこむのって一人じゃモチベーション的にも時間的にもつらいんですよね。他方この方式だと計算資源を豊富に使える人が有利になっちゃうというのもありそうですが。