2011-05 << 2011-06 >> 2011-07

2011-06-17 (金)

*ICFPC 2011 Lambda: The Gathering

今回は,カードゲームか.今までで一番関数型言語が意味を持つICFPかもしれない.問題がとても読みやすいのは書いているのが日本人なのと,ルール自体はすぐ理解できるし,変な解析をする必要はなさそう.

Lambda: The Gathering

カードゲームなのですが,用意されているカードが全て関数.

256個のスロットごとにライフ(vitality)が割り当てられていて,ここにカードをセットしていって実行するという感じ.

カードゲームとして効果がある関数が,相手のスロットのvitalityを1削るとか,自分のvitalityを犠牲に相手を攻撃するとか,そのまま使えないものばかりなので,スロットに複数枚のカードを積んでいく必要がある.

そもそも,関数に渡す値もカードで作らないといけないので,好きな場所を攻撃するためには,かなりのターン数を要する.zero(0)とsucc(+1する)とdbl(*2する)が用意されているので,こいつらを使って好きな値を作ることができる.

42 = dbl(succ(dbl(dbl(succ(dbl(dbl((succ(zero)))))))))

という感じに表現できるので,zeroを最初にスロットに入れてsuccを適用して,dblを…という操作が必要なので42という数字を作るために9ターンが必要.大きな数字は適当なスロットに作っておいて,使うときに参照するというのが良さそう.

これは良いのですが,既にスロットに作ってある関数に数値を渡したいときも,カードを1枚ずつしか置けないので少し面倒.

スロットにfという関数が既に作成されていて,f(2)を呼びたい場合,dbl(succ(zero))を渡す必要があるのだけど,fに対して何か渡そうとすると,最初のカードを渡した時点でfが評価されてしまう.zeroを渡せば,f(0)が呼ばれてしまうし,dblを渡せばf(dbl)が評価(fが数字しか受け取れない関数ならエラーに)されてしまう.

ここで,コンビネータというものの出番で,

S(K(S(K(f))(dbl)))(succ)(zero)

という風に,最初にKにfを渡して,それをSに.さらにSの2つ目の引数にdblを…という感じで適用していけば,最後にSの3つ目の引数にzeroが渡された時点で,色々起きて,最終的にf(dbl(succ(zero)))が呼ばれる.

このすごく便利なSとかKという関数は,関数型言語の世界ではコンビネータと呼ばれていて,

  • S h i j : h(i)(j(i)) を返す
  • K x y : xを返す(yを捨てることができる)
  • I x : xをそのまま返す

というS,K,Iがあれば,何でもできるらしい.

ここまで苦労して関数を呼ぶことになるのだけど,実行するとスロットには関数の評価結果しか残らない.別のスロットを参照する関数はあるので,使いまわしたい処理は別の場所に作っておくか,上手く自分自身を返す関数にしておく必要があるっぽい.

2011-05 << 2011-06 >> 2011-07