マンガの中で考えた、ラムダ計算をしてくれるプログラムを作っ
て見ました。ただし、作りやすさなどから、文法は違ちゃっています。

パーサジェネレータは使っていませんし…。

プログラムは以下にあります。

評価順序とか、書き方とか、エラー表示とか、色々とかなりいい加減なので、 細かいツッコミはなしでお願いします。

なんちゃってBNFを書いておくと、以下のような感じです。

<式> = <ラムダ式>|<ペア>|<変数>

<ラムダ式> = Lambda <変数>.<式>

<ペア> = (<式> <式>)

<変数> = [a-zA-z]+

<ペア> に、 (<ラムダ式> <式>)

の様に書くと、ベータ変換をしてくれます。 ペアの左側にある式から優先して評価されます。

たとえば、こんな式が書けます。

(Lambda x.(x x) Lambda x.(x x))

チューリング完全！ですが、まあ、コレでプログラムを書く、というのは無いですかね…。

言語は C++ です。(動作確認は、Debian stretch の g++ 6.3.0 でしています)C++ を書いたのは久しぶりなのですが、文法がだいぶ変わっていて焦りました。NULL がだめになっているとか…。