このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

JavaScriptで学ぶ・プログラマのためのラムダ計算 問題集

アイコンがずばりラムダ・マーク id:mindさんが、はてなブックマークコメントで曰く:

ぉ! 問題集希望♪

そうですね。「JavaScriptで学ぶ・プログラマのためのラムダ計算」の節ごとに練習問題を入れておけばよかったな、と、ちょっと高階、じゃなくて後悔。このエントリーで練習問題を提供しましょう。JavaScriptの実行環境に関しては「もっともお手軽な対話的JavaScript処理系」を参照してください。

1. JavaScriptの関数リテラル

例に挙げたsquareは、「square(x) = x×x」という中学数学風の関数定義を二通りの方法でJavaScritpに翻訳したものです。同様に以下の関数定義を、JavaScritp関数として二通りの方法で定義してください。

  1. double(x) = 2×x
  2. sqsum(x, y) = x×x + y×y

次の式(ラムダ計算の用語では適用した形)を、関数名を使わずに、JavaScriptの関数リテラル(function式)で書いてください。

  1. double(4)
  2. sqsum(2, 3)

2. ラムダ式ってなんだ

  1. 関数doubleと関数sqsumをラムダ式に直してください。
  2. 省略できる丸括弧を取り除いて、できるだけ簡略なラムダ式にしてください。
  3. ラムダ式の括弧を省略できる場合と省略できない(または省略するのが好ましくない)場合について、自分なりの基準を考えてください。

3. ラムダ計算の体系と適用操作

squareに4を適用(伝統に忠実な言葉使いなら「4にsquareを適用」)した形をラムダ式で書けば、(λx.x*x)(4) です。同様に、次の適用を関数名を一切使わずにラムダ式で書いてください。

  1. doubleに4を適用
  2. sqsumに、2と3を適用
  3. doubleにzを適用
  4. doubleに、「sqsumに、2と3を適用」した形を適用
  5. sqsumに、「doubleに4を適用」した形と「doubleにzを適用」した形を適用

4. ラムダ式の例をいくつか

練習問題は特にありません。JavaScriptインタープリタで遊んでみてください。

5. β変換 -- ラムダ計算のキモ!

  1. 「ラムダ計算の体系と適用操作」の問題で得られた5つの“適用した形の式”に対して、β変換を可能な限り続けて実行してください。足し算や掛け算の実行は行わないでください。
  2. β変換がすべて終わった後で足し算/掛け算を行う方法と、足し算/掛け算が出来るときはすぐさま行う方法で、答(最終結果)が変わりますか? 実験してみてください。
  3. (…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. 中間まとめ、まだ続きがあるよ

次回は、説明のなかに練習問題を挟み込むことにします。