TaPL読む3.5
前回が10/5で眩暈しそう。半年以上前…
今回は6章を読んだ…けど実装はまだ。なのでタイトルは3.5にした。
何に苦しんでいたのかというと、ラムダ計算のパーサーが書けずにいた。
7章をチラ見すると、例えば「λx. a b」のような式を内部で「TmAbs(TmApp(a b))」と扱うらしい。しかしTaPLはパーサーなんかはぱっと作れる人に向けた本なのか知らないが、その変換方法は書いていない。 ちょっと前(もはやこれも「ちょっと前」ではない)にS式風の電卓を書いて遊んでたので、できるかもと挑戦したが、ラムダ抽象と関数適用と括弧で結合強度が入り乱れるものをどうすることもできずに撃沈。
それで完全に投げ出していたが、その後に
で、結合強度ごとに関数を分けて再帰することでうまくパースできることを知った。これは本当にめちゃくちゃ感動した。天才か?
まあそのあとも何度か撃沈したが、今回めでたくできたので小躍りしながらブログを書いている。入力をグローバル変数で引き回すためにStateモナドを使ってみて、ちょっとStateモナドと親しくなれた気分になった。
他助かったのは以下の2つ;
- ループをうまく書くのにfixを使う方法
- Debug.Traceの存在。printfするのにも型で悩むのがしんどすぎて困ってたけど、今回
のおかげで投げ出さずに済んだ。適当にtrace (show 変数) ()で変数が見れるの神。
~~~
ここから愚痴(このために書いているので実質本編)
ラムダ計算の実装において、「λ」の扱いはだるいなと思ったので、λx. a b
をx. a b
とした。こうすると、ラムダ抽象はx.
という式または単項演算子に見える。
式と見たときは関数適用が左結合なので、x. a b = (x. a) b
となってしまい、他の束縛子(∀とか∃とか)のように文末まで適用される性質を持たせられていない。没。
単項演算子と見た場合は結合強度が最弱のものとしてx. a b = x. (a b)
とすれば望んだように適用される。やったぜ。
次にc x. a b
を考える。x.
は結合強度が最弱の単項演算子なので、…?これ無理じゃない?
関数適用の強度が強い!って思うと(c x. a) b
に見えてくるけど、これってx. a
の強度がb
に勝ってしまってるし、c (x. a b)
だとc
が負けてる…ちょっと調べたけどわからなかった。
こうなった原因の一つに関数適用が空白で書かれてる点があると思ってて、というかラムダ計算のパーサーのつらさの6割くらいはこれだった(つらすぎてこんなわけのわからない文章を書いている)。「a b」が「a*b」だっただけでぐっと楽になっていたと思う。
ほらこうすればc x. a b
も、c*x. a*b
となって…あれ、逆効果?
…ラムダ束縛をx.
としたときに演算子に見えてしまったことが全ての間違いだったかもしれない。束縛子は文末まで伸びる特殊な括弧だと思えばc x. a b = c (x. a b)
となって解釈が定まる。
これを書き始めたときは、「~でラムダ束縛子を右結合の二項演算子と見たらうまくいくんですよ~ww」って書くつもりだったのに、何にも理解してなかったことがわかってとてもつらい。せっかく幸せ気分だったのに…