はじめに
ラムダ式の構文解析にあたりテスト駆動型で進めたところがうまくいきましたので、書き記します。ラムダ式みたいな単純なものであってもパーサはそれなりにややこしいです。テストがとても役に立ちました。
ラムダ式の定義
以下は高橋正子先生の「計算論 計算可能性とラムダ計算」でのラムダ式の定義です。ｐ６３より引用
（１）変数x0,x1,...はλ式である。
（２）Mがλ式でｘが変数のとき、(λx.M)はλ式である。
（３）MとNがλ式のとき（MN)はλ式である。
インタプリタではアルファベットの1文字を変数という仕様としました。a,b,...,Zの各1文字が変数です。
λは^で代用することとしました。 (^x,M) のようになります。内部表現はタプルを使って{:^,:x,:M)のようにします。λ式にλ式を適用する場合にはリストで表記することとしました。(xy) は [:x, :y] となります。
省略記法
λ式がネストするとカッコがとても多くなり見づらくなります。そこで下記の省略記法が用いられます。ｐ６４
（１） λx1,x2...xn.M = (λx1,(λx2,(...(λxn,M)...))) (n>=1)
（２） M1,M2,M3...Mn = ((...((M1,M2),M3)...)Mn) (n==2)
インタプリタでは ^xyz.x や (xy) ((^x.x)(^y.y)) のような表記となります。
テストケース
ちゃんとBNFとか書いてから慎重にすればいいのでしょうけれど、私はけっこう行き当たりばったりです。そうするとこっちを修正するとあっちがおかしくなって・・・ということなってしまいます。
そこでテストを先に書いて、こうなってほしいというものを先に用意しました。
test "parse test" do
assert Lambda.parse('xy\n',[]) == [:x, :y]
assert Lambda.parse('(xy)\n',[]) == [:x, :y]
assert Lambda.parse('^x.y\n',[]) == [{:^, :x , :y}]
assert Lambda.parse('^x.(^y.y)\n',[]) == [{:^, :x, {:^, :y, :y}}]
assert Lambda.parse('(^x.x)(^y.y)\n',[]) == [{:^ , :x , :x},{:^, :y, :y}]
assert Lambda.parse('^x.xy\n',[]) == [{:^,:x,[:x,:y]}]
assert Lambda.parse('xyz\n',[]) == [[:x,:y],:z]
assert Lambda.parse('abcd\n',[]) == [[[:a,:b],:c],:d]
assert Lambda.parse('(^xy.x)\n',[]) == [{:^,:x,{:^,:y,:x}}]
assert Lambda.parse('(^xyz.x)\n',[]) == [{:^ ,:x,{:^,:y,{:^,:z,:x}}}]
assert Lambda.parse('(xy)z\n',[]) == [[:x,:y],:z]
end
テスト駆動開発の良さ
単純なコードですとテストなんかテキトーでもなんとかなってしまってました。動かしながら試行錯誤のスタイルです。しかし、こんな簡単なλ式ですがパーサはあちこち弄りながら修正をして改良していきます。そうすると１つを直すと他のうまくいっていたものが動かなくなるということがよくあります。修正のイタチごっこのようで効率が悪くなります。最初からテストケースを用意してそれがとりあえず動くことを確認しつつ改良するとイタチごっこの無駄がなくなります。
全コード
パーサなどの全コードはGithubに置いておきます。順次改良を重ねています。β変換、簡約ができるところまでが目標です。
参考文献
計算論 高橋正子 著
