Haskell Hackathon 2008

情報

Haskell Hackathon 2008に参加してきました。結果的に12時間+αで、Template Instantiationが実装できて、関数型言語がどう動いているのかの理解の着実な第一歩を進められたので大満足です。企画＆参加の皆様ありがとうございました！

Haskellがどう動いているかについては、調べれば調べるほど驚異のメカニズムであることが判明してきたので、マラソンが始まる前から降参状態といった感じでした。そこでもう何かオリジナルなことをするのは一切あきらめて、実装を通じて学ぶという原点に立ち返り、Implementing functional languages: a tutorial、略してIFLT
http://research.microsoft.com/~simonpj/Papers/pj-lester-book/
を教科書として忠実に実装することにしました。言語はもちろん、効率よく実装できて効率よく学べるHaskellで。

いちおう言っとくとコピペはしてないからね！全部キー打って入力したからね！あと肝心のところが演習問題になってたりするから丸写しじゃ動かないんだからね！！！

成果

http://www.geocities.jp/takascience/iflt.zip

こんなのが動くよ！

cons a b cc cn = cc a b;
nil      cc cn = cn;
head list = list K undefined ;
tail list = list K1 undefined ;
drop n xs = if n <= 0 then xs else drop (n-1) (tail xs);
zip as bs = cons (head as + head bs) (zip (tail as) (tail bs));

fib = (cons 1 (cons 1 (zip fib (tail fib))));
main = head (drop 5 fib);

感想

  • String以外に対するパーサをはじめて書いたけどHaskellは型があえばうごくよ！言語であることを改めて実感
  • Core言語の文法はtryを一切使わずに書かれていてすごいなあ
  • 状態遷移ルールなんで(再帰的let以外)簡単に手続き型言語に直せそうだからやってみたいなあ
  • 機会があったらIFLT日本語に訳したいなあ

僕が引っかかったとこ

万に一つ、他の人がIFLTを読んで実装しようとして同じところで引っかかったときヒントになりますように。

many (satisfy isAlphaNum)とかは無限ループに陥る

Parsecの解説 http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html より

暗黙の制約として、順列の中のパーサは空の入力に対して成功するべきではありません (例えば、(many (char 'a')) を使ってはいけません)。

なんで空の入力に対して(char 'a')が成功する仕様なん？？

仕方が無いのでmany1を使って強行突破。

リストのhead同士が足し算できない

2.6.1節のindirectionを解消するための遷移規則(2.9)は次のような意味。

  • primitiveノードを評価しようとした時、引数のどれかがNNumじゃなかったら、計算できない！
    • そこで、引数のうちNNumじゃないノードをstackに代入しといて計算してもらう。
    • 計算結果がindirectionになってるかもしれないので、primitive関数全体を起動する祖先applicationノードをもういちどdumpにつっこんでおく。
    • そうすれば、祖先applicationノードから引数リストが再びstackに構築されたときには、遷移規則(2.8)によりindirectionが解決している。

だもんで、ルール(2.9)でdumpに突っ込むべきなのは一般的に「スタックの一番後ろ(ツリーのいちばん根っこ側)のアドレス1個」です。

2引数以上のプリミティブ関数をつくるときに問題になります。

Boolを実装できない

「Template Instantiationだとcaseはうまいこと実装できないんだ」「ifはうまいこと実装してね」みたいなことが書いてあるのでなんとか自力でやるしかない。ちなみにcaseが作れないとデータ構造が作れないのでリストはconsとnilで表現します。


2項比較演算子 == とかがTrueやFalseを返すようにして、
if c then t else e が c t e になるようにすれば

True x y = x
False x y = y

main = if 1 + 1 == 2 then 41 else 4971

が動くような気がしますが、これだと

main = (==) (1+1) 2 41 4971

みたく、(==)が4引数関数にされてしまうので動きません。

本来なら限定的パターンマッチを作らんといかんところでしょうがどうせ半端なことするならと、

  • (2 + n)引数関数だけど評価済みであることを要求するのは最初の2つの引数だけ
    • 最初の2引数が未評価ならルール(2.9)により差し戻す、このときdumpにつっこむのは(2 + n)番目の引数
    • 最初の2引数が着てたら部分適用して計算結果(は n 引数関数)を第2引数のぶら下がってたところに捻じ込んでおく

たぐいのプリミティブ関数を用意し、最小の変更で実現できました。