JavaScriptでラムダ計算の仕組みを学ぶ教材

関数型プログラミングの理解を深めるために、OCamlの本を読んでいます。

プログラミングの基礎 (Computer Science Library)

「簡約」について調べていたら、分かりやすい説明の記事がありました。

tarao.hatenablog.com

ラムダ計算は, 多くのプログラミング言語, とくに関数型言語の原形になっています. ラムダ計算について理解しておくことは, 多くのプログラミング言語の習得に役立つでしょう.

ラムダ計算はチューリング完全で, 計算能力としてはふつうのプログラミング言語と同じです. ラムダ計算で計算を書く訓練をしておくことは, 任意の計算を関数のみを使って(他の制御構文を用いずに)書くときに役立ちます. ふつうに書いたら煩雑な処理を, 関数型言語のやり方で書くとすっきりすることが多々あり, コードを自由自在に書くためには必須の考え方と言えるでしょう.

ラムダ計算の式を項(term)と言います. 項は変数, 抽象, 適用のいずれかです.

変数(variable)はふつう1文字で書きます. 変数には関数内の束縛変数(bound variable)か自由変数(free variable)かという区別があります.

関数を作る構文を抽象(abstraction)と言います.

関数を呼び出すことを適用(application)と言います.

ラムダ計算の式を実行することを簡約(reduction)と言います.

簡約できる部分が複数あるときは, どこから簡約しても構いません.

これ以上簡約できない項のことを正規形(normal form)と言い, どのような順序で簡約しても正規形は必ず同じ形になります.

ただし, どんな項でも簡約していけば正規形になるというわけではありません. たとえば, 無限ループするような項もあります.

で、ここからが肝？

必要な道具がなければ手持ちの材料で作り上げてしまうという発想がなるほど納得。

ラムダ計算に自然数はありません. 「ありません」では困るので, 項を使って自然数を定義します. 以下のように定義された自然数をチャーチ数(Church numeral)と言います.

0 = λsz.z
1 = λsz.s z
2 = λsz.s (s z)
3 = λsz.s (s (s z))
・
・
・
n = λsz.sn z  # snはsをn回適用

以下、こんな調子でプログラミングに必要な道具、仕組みを「項」（変数、抽象、適用）の組合せから定義していくようです。

演算も定義できます.

ラムダ計算にデータ構造はないので, 項を使って作ります.

条件分岐

ラムダ計算には真偽値もifもないので, 項を使って作ります.

ループ

ループは基本的に再帰呼出しで書きます. ただし, 再帰呼出しの構文は無いので, 不動点コンビネータ(fixed-point combinator)を使います. 有名なものはYコンビネータで, 次のような項です.

（話の上では）「なるほど、基本的な動作原理はこうなっているのか？」とスッキリ理解できたような気分になります。（理解したとは言ってない）

ま、少なくとも基本的な用語の意味については押さえておくことができるので、後々関数型言語の話を読むときに役にたちます。

ラムダ計算についてザックリとした説明は、Lispの本にもありました。

入門Common Lisp―関数型4つの特徴とλ(ラムダ)計算

(p.152)　第8章　λ計算

この本の説明をさらに短く要約したようなかんじで、「参考書のまとめみたいで分かりやすいな！」と思いました。

さらに、ラムダ計算の仕組みをJavaScriptを使って確認してみるツールも用意されていました。

tarao.hatenablog.com

tarao.github.io

このツールに上記のラムダ式をコピペすると、簡約の様子が確認できます。

JavaScriptは、関数を値として扱うことができるプログラミング言語なので、関数型プログラミングが実践できます。

この説明の難点は、書かれた時期（2010年頃？）がES2015登場以前だったので、関数の表記が古い＝ちょっと見づらいかな～？という点です。（※個人の感想）

functionではなくてアロー関数式「=>」で書き直せば、より関数型っぽく見えるのではないか？と思いました。

…上から目線っぽい言い回しでスミマセン。m(__)m

developer.mozilla.org

ラムダ計算の基本を理解する上で内容はとても良い教材だと思うので、練習がてら時間があるときにアロー関数式で書き換えて勉強してみたいと思います。

有益な情報提供、どうもありがとうございました。

twitter.com