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