Tociyuki::Diary RSSフィード

tociyuki によるPerl・Rubyのコード説明を中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館
 | 

2013年02月17日

[]LISP 1.5 での FUNARG 導入から第一級オブジェクトとしてのクロージャの発見まで

懐古趣味の続きです。

マッカーシー先生の 1960 年 LISP (LISP 1) は、論文の題名が示すように、 明示的に不動点コンビネータを評価しなくても、 単純なやりかたで再帰呼び出しを可能にする方法を示したのがポイントでした。 その単純なやりかたとは、ラムダ式を環境にセットしておいてから評価することによって、実行時の環境から自分自身を取り出すという乱暴な方法でした。 これの問題はラムダ式に自由変数が含まれるとき、 環境のどこにその自由変数が束縛されているのかが実行時まかせになることです。 その結果、 λ式に自由変数を含むλ式を引数で渡したときのλ算法の置換評価とは結果が異なる場合が生じます。 これを funarg 問題と呼びます。

この funarg 問題への対処として、 早くも 1962 年の LISP 1.5 に function 特殊形式が導入されます。 そのような問題が生じる場合には、 λ式を quote せずに function するようにと。

⇒ John, McCarthy et al. LISP 1.5 Programmer's Manual, MIT Press, 1962, 21 ページ

We also need a special rule to translate functional arguments into S-expression. If fn is a function used as an argument, then it is translated into (FUNCTION fn*).

Example

    (CHANGE (LAMBDA (A) (MAPLIST A (FUNCTION
        (LAMBDA (J) (CONS (CAR J) (QUOTE X))) )))

An examination of evalquote shows that QUOTE will work instead of FUNCTION, provided that there are no free variables present. An explanation of how the interpreter processes the atomic symbol FUNCTION is given in the Appendix B.

function 特殊形式の評価手順は Appendix B に M-式で記述されたインタープリタに追加されています。

⇒ 同上 70 ページ、71 ページ

eval[form;a]=[
    略
    eq[car[form];FUNCTION]→list[FUNARG;cadr[form];a];
    略]
apply[fn;args;a]=[
    略
    eq[car[fn];FUNARG]→apply[cadr[fn];args;caddr[fn]];
    eq[car[fn];LAMBDA]→eval[caddr[fn];nconc[pair[cadr[fn];args];a]];
    略]

eval の第一引数 form は評価される式、 第二引数 a は環境です。 function 特殊形式はラムダ式と環境を結びつけ funarg のラベリングをします。 funarg ラベルのついた式を apply で関数適用すると、 結びついている環境で、 ラムダ式を関数適用します。 ところで、 このロジックを scheme の超循環評価器のコードと見比べると、 LISP 1.5 での function を lambda へ換え、 funarg を procedure へ換え、 apply の funarg と lambda の評価部分を一体にして、 procedure を評価するようにすることで同じになります*1

LISP 1.5 には、 クロージャなる用語は使われていない上に、 function 評価が静的スコープであるという記述もまだ現れていません。 funarg と同じ仕掛けは、 同じ 1962 年にエドガー・ダイクストラが ALGOL60 の入れ子手続きを実現するために導入しており、 経緯は明らかではないものの、 1960 年初頭に funarg 問題の解決と静的スコープの導入の等価性から 第一級オブジェクトとしてのクロージャの発見に至った模様です。 そうした中で、どうやら、クロージャの語を論文で最初に使ったのはランディンのようです。

⇒ P. J. Landin, The Mechanical Evaluation of Expressions, 1964

316 ページ

Also we represent the value of a λ-expression by a bundle of information called a closure, comprising the λ-expression and the environment relative to which it was evaluating.

このように、 λ式と環境をくっつけたものをクロージャと呼んでいます。 そして、 クロージャをλ計算に用いる方法として SECD マシンを提唱し、 このマシンでλ式を評価すると必ずクロージャを作ることと、 関数適用とはクロージャへ実引数の適用をする仕組みであると説明が続きます。 その中には、 再帰呼び出しを実現するための循環参照をもつ環境を生成する方式も含まれていて、 Y 操作と名づけています。 もちろんこれはハスケル・カリーが発見した Y コンビネータを意識してのことで、 LISP1 で動的スコープで実現していた再帰呼び出しから、 静的スコープでの環境からクロージャ、クロージャからそれが含まれている環境への循環参照による再帰呼び出しへの実現への移行がここでおこなわれます。 静的スコープでも LISP1 の label、 現代での letrec の実現は可能になり、 ランディンが SECD マシンで提唱したやりかたは、やがて ML 言語処理系での letrec へ、 scheme 処理系での set! による環境の破壊操作で循環参照を生成する方式へ受け継がれます。 また、 ランディンは抽象的に述べるにとどめた Y 操作も、SECD マシンの実装で DUM と RAP 命令として現実のものになります。

ランディンは論文をこう結びます。

⇒ P. J. Landin, 同上, 1964

Closures are roughly the same as McCarthy's FUNARG lists (1962) and Dijkstra's PARD's (1962). (This method of evaluating a λ-expression is to be constrasted with literal substitution such as is used in Church's normalization process, in Gilmore's (1963) machine, and in Dijkstra's (1962) mechanism).

λ算法と静的スコープとクロージャの間の等価性の発見と、 λ式の評価とはクロージャの生成であることが発見されたのは、 1960 年初頭のほんの数年のできごとだったようです。

*1:LISP 1.5 ではセルを節約する破壊操作の nconc を、 LISP 1 と scheme は非破壊操作の append を使う差があります。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/tociyuki/20130217/1361121598
 |