アイコンがずばりラムダ・マーク なid:mindさんが、はてなブックマークコメントで曰く:
ぉ! 問題集希望♪
そうですね。「JavaScriptで学ぶ・プログラマのためのラムダ計算」の節ごとに練習問題を入れておけばよかったな、と、ちょっと高階、じゃなくて後悔。このエントリーで練習問題を提供しましょう。JavaScriptの実行環境に関しては「もっともお手軽な対話的JavaScript処理系」を参照してください。
1. JavaScriptの関数リテラル
例に挙げたsquareは、「square(x) = x×x」という中学数学風の関数定義を二通りの方法でJavaScritpに翻訳したものです。同様に以下の関数定義を、JavaScritp関数として二通りの方法で定義してください。
- double(x) = 2×x
- sqsum(x, y) = x×x + y×y
次の式(ラムダ計算の用語では適用した形)を、関数名を使わずに、JavaScriptの関数リテラル(function式)で書いてください。
- double(4)
- sqsum(2, 3)
2. ラムダ式ってなんだ
- 関数doubleと関数sqsumをラムダ式に直してください。
- 省略できる丸括弧を取り除いて、できるだけ簡略なラムダ式にしてください。
- ラムダ式の括弧を省略できる場合と省略できない(または省略するのが好ましくない)場合について、自分なりの基準を考えてください。
3. ラムダ計算の体系と適用操作
squareに4を適用(伝統に忠実な言葉使いなら「4にsquareを適用」)した形をラムダ式で書けば、(λx.x*x)(4) です。同様に、次の適用を関数名を一切使わずにラムダ式で書いてください。
- doubleに4を適用
- sqsumに、2と3を適用
- doubleにzを適用
- doubleに、「sqsumに、2と3を適用」した形を適用
- sqsumに、「doubleに4を適用」した形と「doubleにzを適用」した形を適用
4. ラムダ式の例をいくつか
練習問題は特にありません。JavaScriptインタープリタで遊んでみてください。
5. β変換 -- ラムダ計算のキモ!
- 「ラムダ計算の体系と適用操作」の問題で得られた5つの“適用した形の式”に対して、β変換を可能な限り続けて実行してください。足し算や掛け算の実行は行わないでください。
- β変換がすべて終わった後で足し算/掛け算を行う方法と、足し算/掛け算が出来るときはすぐさま行う方法で、答(最終結果)が変わりますか? 実験してみてください。
- (…x…)は変数xを含む(しかし変数yは含まない)任意の式として、(λx.(…x…))(y) をβ変換すると、何を行ったことになりますか? square, doubleで実験してみてください。
3番目の問題は、出題者(檜山)の意図が汲み取りにくいかもしれません。関連することを次回に説明する予定です。
6. β変換を何度か実行してみる
はてなダイアリーの変な仕様への対策と見やすさのために、丸括弧だけでなく角括弧('['と']')も使います。次の式に対して、β変換を続けて実行してください。
- (λx.1)[(λx.[x(x)])(λx.[x(x)])]
ここで、x(x) は「xにxを適用した形」です。その意味を深く考えないで(考えてもいいですけど、適当に切り上げてください)、機械的に置き換え操作を実行してください。この式に対して、β変換をちょうど5回行って最終結果に到達する計算手順は在りますか? 在れば実行してください。ちょうど3回ではどうでしょう? ちょうど1回、ちょうど100回では?
7. 中間まとめ、まだ続きがあるよ
次回は、説明のなかに練習問題を挟み込むことにします。