はじめに
思い立ってLISP1.5相当の機能をもった処理系を作りました。マッカーシー博士に対する敬意を表すとともに、できるだけシンプルな実装を示すことによりLISPに興味をもってもらいたかったからです。
Funarg問題
実装がほぼできたところでそれを公表しました。するとScheme世界で有名なnils-m-holmからコメント、アドバイスをもらいました。動的スコープのLISP1.5だとFunarg問題について実験ができます。例を紹介していただきました。
例１
(DEFINE ((X (QUOTE IGNORED))))
(DEFINE ((MAPLIST
(LAMBDA (X F)
(COND ((EQ X NIL) NIL)
(T (CONS (F (CAR X)) (MAPLIST (CDR X) F))))))))
(MAPLIST (QUOTE (1 2 3)) (LAMBDA (Y) (CONS Y X)))
;; -> ((1 1 2 3) (2 2 3) (3 3))
例２
; Funarg Problem
(DEFINE ((P (LAMBDA (X) (QUOTE OOPS)))))
(DEFINE ((COMPLEMENT (LAMBDA (P) (LAMBDA (X) (NOT (P X)))))))
;((COMPLEMENT ATOM) (QUOTE FOO )) ==> NIL
;((COMPLEMENT ATOM) (QUOTE (FOO BAR))) ==> NIL
DEFINEとあるのは現代のLispではdefunとなっています。
(DEFINE ((シンボル１ λ式１）（シンボル２ λ式２）．．．） という形式です。
maplistが現代のLISPと引数の順番が逆になっていることに注意してください。
実行例
私の実装は1962年当時パンチカードでLISPが利用されていた様子をシミュレートしています。
punch.lspというファイルをパンチカードとみなして起動時に読み込みます。その後はREPL動作をします。1962年当時は計算結果をプリントアウトして受け取っていたみたいですね。
lisp punch.lsp
LISP 1.5
> (fact 10)
3628800
> (quit)
- Quitting LISP. With respect to John McCarthy. -
lisp funarg.lsp
LISP 1.5
> (MAPLIST (QUOTE (1 2 3)) (LAMBDA (Y) (CONS Y X)))
((1 1 2 3) (2 2 3) (3 3))
> ((COMPLEMENT ATOM) (QUOTE FOO ))
NIL
> ((COMPLEMENT ATOM) (QUOTE (FOO BAR)))
NIL
>
例1の考察
静的スコープに慣れた現代においては奇妙な計算結果です。なぜこのようなことがおきるのでしょうか？問題の根源はMAPLISTを定義しているλ式がλ式を受け取ることにあります。
MAPLISTに与えられるλ式は引数Fに束縛されます。データは引数Xに束縛されます。
ところでλ式においてXは自由変数です。これは本来であれば大域変数であるXを参照すべきところです。ところが、動的スコープにおいては変数は実行順により参照されます。MAPLISTの引数のXの方を参照してしまいます。自由変数であるはずのXはX=（1 2 3)となってしまいます。
例２の考察
これがなかなかややこしいです。どっぷりモダンなLispに慣れているのでどうして？と良く理解できません。そこで実装にステッパーをいれました。(step t) で実行している式と局所変数を表示します。(set nil)で停止です。エンターを入力すると次に進みます。qを入力すると計算を中断します。
> (step t)
T
> ((COMPLEMENT ATOM) (QUOTE FOO ))
((COMPLEMENT ATOM) (QUOTE FOO)) in [] >> (COMPLEMENT ATOM) in [] >>
ATOM in [] >>
COMPLEMENT in [] >>
(LAMBDA (X) (NOT (P X))) in [(P . <subr>)] >>
LAMBDA in [(P . <subr>)] >>
(QUOTE FOO) in [] >>
QUOTE in [] >>
(COMPLEMENT ATOM) in [] >>
ATOM in [] >>
COMPLEMENT in [] >>
(LAMBDA (X) (NOT (P X))) in [(P . <subr>)] >>
LAMBDA in [(P . <subr>)] >>
(NOT (P X)) in [(X . FOO)] >>
(P X) in [(X . FOO)] >>
X in [(X . FOO)] >>
P in [(X . FOO)] >>
(QUOTE OOPS) in [(X . FOO)(X . FOO)] >>
QUOTE in [(X . FOO)(X . FOO)] >>
NOT in [(X . FOO)] >>
NIL
>
ステップ実行を追っていくと引数Pに束縛されていたはずのPの値が途中で消えてしまっています。このため大域定義されているPを参照してしまっています。
MACLISP以後
その後Funarg問題の解決ぬむけて改良がなされていきます。funarg関数を用意しておいて環境を一緒に持たせる方法が考案されています。
さらにSchemeにおいてクロージャが発明されてFunarg問題は全面的解決に至りました。
マッカーシー博士に敬意を表して
1962年といえば日本では昭和37年、まだ鉄腕アトムがテレビ放映される前のことです。その時代にこれだけのことを創案したというのは驚嘆に値します。
改めて博士の天才、鬼才に驚くばかりです。
雑談
Lispをレトロコンピューティングと捉えて歴史的遺物として資料収集の対象にしているLISPマニアがいます。若い頃に聞いた昭和歌謡を懐メロとして楽しむ気持ちもわからないではないのですが・・・
Lispは画期的な発見、発明でした。そして今でも他言語に影響力を及ぼしています。過去の遺物にしてしまうのはいかがなものでしょうか？現在においてもまだ新たなる発見、挑戦の余地があると私は考えています。とは言え、現在の主力はPythonなどです。Lispが実用的に主要言語として使われることはまずないでしょう。チャーチのλ算法と同様に計算機科学の基礎として使われていくだろうし、それがLispらしさだと私は思います。