2011-06-17 (金)
朝起きて，safiiのところに．マンションの前まで行って入れてもらおうとしたら，コンビニまでおにぎり．
中華．
夜は帰って寝る．
*風邪
まだ37℃くらいあるけど，とりあえず動く．声は出ない．
*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ターンが必要．大きな数字は適当なスロットに作っておいて，使うときに参照するというのが良さそう．
これは良いのですが，既にスロットに作ってある関数に数値を渡したいときも，カードを１枚ずつしか置けないので少し面倒．
スロットにfという関数が既に作成されていて，f(2)を呼びたい場合，dbl(succ(zero))を渡す必要があるのだけど，fに対して何か渡そうとすると，最初のカードを渡した時点でfが評価されてしまう．zeroを渡せば，f(0)が呼ばれてしまうし，dblを渡せばf(dbl)が評価(ｆが数字しか受け取れない関数ならエラーに)されてしまう．
ここで，コンビネータというものの出番で，
S(K(S(K(f))(dbl)))(succ)(zero)
という風に，最初にKにfを渡して，それをSに．さらにSの２つ目の引数にdblを…という感じで適用していけば，最後にSの３つ目の引数に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があれば，何でもできるらしい．
ここまで苦労して関数を呼ぶことになるのだけど，実行するとスロットには関数の評価結果しか残らない．別のスロットを参照する関数はあるので，使いまわしたい処理は別の場所に作っておくか，上手く自分自身を返す関数にしておく必要があるっぽい．