ラムダ計算とは上記のラムダ記法を用いてベータ変換を繰り返す計算の事です。注意・正確にはアルファ変換もありますが、ここでは割愛します。満たすラムダ式の事です。そのラムダ式Mを何度適用しても元のラムダ式とベータ等号になる関係です。誤解を恐れずにやや柔らかい言葉で言うと以下のような関係の事です。再帰的にいつまでも続きます。Yコンビネータのラムダ式は以下のように与えられます。このYコンビネータのラムダ式を用い、(式3)を証明しておきます。(1)から(2)のベータ変換は、ラムダ式Yの束縛変数yをMで置き換えています。x))で置き換えています。(3)から(4)は(2)で定義したラムダ式M'を用いて書き直しています。M'の関係も成り立つ事より導かれます。数学的な定理はこのようになっています。実際にプログラミングの世界でYコンビネータを使う際には以下のような変換だけを考えておけば十分です。このスコープで名前変換する場合に使用するためのハッシュテーブルです。(lambda式やlet式の"lambda"と"let"と引数のS式は変換対象から外しています)。引数に変換対象となるkeyが一致するかどうかのチェックをしています。letの引数とkeyが一致した場合は特に変換せずにS式を返しています。keyの文字列で新たに束縛されているので、ベータ変換の定義から変換出来ません。beta-reductionを呼び出しています。その中で34行目から39行目と40行目から43行目で実際にkeyとS式を変換しています。45行目と46行目でretがlistならば逆順にセットしなおしています(retには逆順でlistに追加されていくため)。S式を削っていたのでそれを元に戻しています。最後に53行目で変換後(変換されていなければそのまま)のS式を返しています。Yコンビネータが動くインタープリタは、ラムダ式をベータ変換していく事で実装出来ます。理論で説明しましたが、ベータ変換は式に対する評価は行いません。束縛変数の置換が行われるだけで、実際の式の評価は別に必要です。ベータ変換された式はまたラムダ式となるので、いついかなるタイミングで式の評価をしても問題ありません。そこで、sLispではベータ変換が完全に終了したらそこで式の評価をするような戦略としています。どこかでベータ変換が終わるような仕組みが必要です。それにはYコンビネータに与えるラムダ式側に仕組みが必要です。実際、階乗計算をさせるような関数の場合は以下のようになります。その結果とnを掛けた数字を返しています。普通の階乗計算をさせる関数と違い、fact0自身は再帰的な処理をしません。再帰を発生させるのはYコンビネータの役目となります。関数fを評価しないので、ここで再帰の連鎖が止まるようになっています。肝心のYコンビネータのS式は以下のようになります。(式4)と全く同じ式です。sLispでベータ変換及び評価していってみます。ある瞬間の継続とは、その瞬間以前の計算結果を使ってその後計算すべき物の事です。2)に5を掛ける」と表せます。すれば例1と同じ結果を得られます。schemeやsLispでは、継続はデータとして生成し使う事が出来ます。継続の生成にはcall-with-current-continuationやcall/ccメソッドを使います。sLispではcall/ccです。この例2をみてください。部分式にcall/ccメソッドがあります。このcall/ccメソッドが生成する継続です。この継続はcall/cc内部のlambdaの引数ccに渡されます。例2ではcall/ccのlambda式内部で継続ccが使われていません。このような場合、call/ccメソッドは内部の式を評価して返します。この例では先ほどの例2と違い、継続ccがcall/ccメソッドのlambda式で使われています。評価結果である10を返します。これは継続の特徴である、「継続が呼ばれたらトップレベルの次のS式に評価が移る」という性質に依ります。いう命令も含まれていることを意味しています。継続は保存しておくことも出来ます。例4のように継続ccを変数hogeに保存しておくと、その継続をあとで使いまわす事が出来ます。ような動作をさせる事も可能です。それではsLispにおける継続の実装を見ていきましょう。slisp-callcc-parseは与えられたS式をパースし終わって、構文木が作成された後に呼ばれます。引数に与えられるexpはその構文木です。exp)で得られるリストはトップレベルのS式のリストです。それぞれのS式を探索し、call/ccが見つかればthrowしてslisp-callcc-parseを終了します。このようにsLispでは今のところcall/ccが一つしか書けません。4行目で呼んでいるslisp-callcc-getccが実質、継続の本体です。なり、9行目で継続用のlambda式を生成しています。ここで変数名に"variable-for-callcc"を使っています。かぶらないであろう変数名"variable-for-callcc"を明示的に指定しています。lambda式の生成が出来たら、10行目でそれをスコープ用ハッシュテーブルenvに"callcc"というkeyでpushしています。このcallccというkeyも他の変数名とかぶってはいけません。サンプル3は継続の本体です。与えられた構文木expにcall/ccメソッドがあるかどうか再帰的にチェックしています。いうリストを返しています。23行目slisp-get-callccで取得しています。S式と、call/ccが見つかったという印のtのlistを返します。見つからなかった場合は引数で渡したS式と、全く同じ物と見つからなかった印のnilのlistを返します。継続の概念と実装を説明していきました。ラムダ式だけで再帰を表現出来るという1点においてのみ意味があります。全ての計算には、等価なラムダ式が存在するという事の一端としてご紹介しました。実装に関しては今回お見せした例のようにそれぞれ数十行程度で実現出来ます。Lispが強力で素晴らしいかわかっていただけたかと思います。次回はelispの実装をemacsのソースコードを元に解説していきたいと思います。はじめに今回は著者がelispで書いたLispインタープリタsLispを元にLispの世界を紹介していきます。ラムダ計算、Yコンビネータやschemeで有名な継続をsLispの実装を元に解説します。sLispのソース全文を記載したgithubへのリンクを書いておくので興味のある方は実際に動かしてみてください。22.2.1上のみで動作検証をしています。ラムダ計算Yコンビネータは、プログラミング言語Lispが基礎としている理論「ラムダ計算」に深く関係しているため、まずは簡単にラムダ計算について説明します。ラムダ記法ラムダ計算を知るにはまずラムダ記法を知る必要があります。ラムダ記法は"関数"の記述を簡便に扱うための記法です。ような関数fが与えられた時、それをラムダ記法で書くと以下のようになります。xこの式中の\を「ラムダ」と読みます。ドット(.)より右側の式は関数本体を表します。ラムダは変数xが関数本体で束縛されている事を表しています。このように関数の引数(プログラミングの世界では仮引数)となっている変数の事を束縛変数と呼びます。変数はa,b,xのどれが「束縛変数」であるかを明示できる事があげられます。bこのラムダ式の場合、xが束縛変数でa,bは束縛されていない変数です。3)関数呼び出し時に実引数で値が決まる変数(プログラミングの用語を使うと仮引数)が束縛変数です。定義2.1.1によりあげておきます。形式を関数抽象と呼び、MNの形式をMのNに対する関数適用と呼びます。reduction)次に以下のようなラムダ式を考えます。M)のラムダ式Nに対する適用です。このラムダ式を、ラムダ式Mに含まれている変数xを全てラムダ式Nで置き換える事をベータ変換と呼び、以下のように記述します。Mの式中のxを全てNで置き換えられた式を意味します。CやJavaなどの世界で関数呼び出しやメソッド呼び出しの実引数というと、値やオブジェクトをイメージしがちですがラムダ計算(及びそれを基礎にしている関数型言語)の世界では実引数には値の他に関数自体を渡す事が出来ます。1)のようなイメージになります。この記法を用いてベータ変換を以下のように再帰的に定義します。)を以下のように定義しておきます。