1960 年の Lisp

昨日、懐古趣味に浸りつつ John McCarthy Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I(1960) を再読していました。10代終わりの頃に初めて読んだときは、何が書いてあるのか理解するのに苦労したものですが、あれから 30 年経ち、さすがに年の功がついたおかげか、今読むと平易に感じる論文です。
この論文には、原初の LISP インタプリタが記載されています。それを、Common LISP に書き直したものもウェブ上に見つかります。

http://lib.store.yahoo.net/lib/paulgraham/jmc.lisp

ところで論文のインタプリタには良く知られているバグがあるので、そのまま動かせません。何通りかの修正方法があるうち、上のリンク先の実装のバグ修正は 1970 以降の流儀にならっているようです。このやりかたでは、論文記載のトレースの通りには動作しませんが、論文よりもこちらの方が現代の目からみて素直です。

このインタープリタの特徴を列挙してみましょう。

  1. 環境は一本の連想リストで、フレームなしの動的スコープ。連想リストの caar と cadar にそれぞれシンボルと値をくっつける。
  2. 変数は深い束縛。
  3. 単一名前空間
  4. 後の LISP の eval と apply へと分化する前なので、すべてが eval に集約。
  5. apply は実引数に quote をマップして eval に渡すだけの単なるフロントエンド。初期環境は NIL
  6. cond 節の t にクォートが必要。
  7. letrec の簡易版 label 式がある。

5番目は EVALQUOTE と呼ばれていたもので、1980 年頃にも、しぶとく生き残っていた記憶があります。一番外側の括弧は自動的に補われ、これを使うと、次のように M式 感覚で関数適用できて、1960 年論文の記載に近い使い方ができるのが、生き残っていた理由だと思われます。うろ覚えですが、たしかこんな感じで使っていました。今はもはやこんな使い方はしません。

    append [(a b c) (d e f)]
    => (a b c d e f)

さて、動的スコープなので、引数に渡す lambda 式を letrec のような感じに扱えるのが、とても奇妙な感じです。jmc.lisp には apply も read-eval-print-loop もないので、Steel Bank Common Lisp (SBCL) から直接 eval. を叩いてみることにします。eval. の2番目の引数に環境を与えます。この例では空のリストにしています。

$ sbcl --load jmc.lisp
* (eval.
  '((lambda (sublis sub2 null caar cadar)
      (sublis '((x (a b)) (y (b c))) '(a x . y)))

    '(lambda (x y)
      (cond ((atom y) (sub2 x y))
            ('t (cons (sublis x (car y)) (sublis x (cdr y)))) ))
    '(lambda (x z)
      (cond ((null x) z)
            ((eq (caar x) z) (cadar x))
            ('t (sub2 (cdr x) z)) ))
    '(lambda (x) (eq x '()))
    '(lambda (x) (car (car x)))
    '(lambda (x) (car (cdr (car x)))) )
   '() )

(A (A B) B C)

これが動く理由は、静的スコープとはことなり lambda 式を評価するという概念がなく、lambda 式を単なるリストとして扱うためです。lambda 式本体が探る環境は定義時ではなく実行時のものです。sublis を実行しているときは、sublis が動いている環境に lambda 式の引数が含まれているため再帰呼び出しできるわけです。そのため、funargs 問題が発生するペナルティはあるものの、let、let*、letrec、letrec* の区別がありません。とてつもなく素朴です。動的スコープを採用したのは、この辺、深く考えなくても楽に扱えたためなのじゃないかという気もします。

label 式は lambda 式とは違い、label 式が評価された時点の環境で lambda 式をラベル名に束縛してから引数に続いて lambda 本体を評価します。そのため、lambda 本体実行時の環境にはラベル名が存在しているため、lambda 本体を再帰的に実行することができます。

* (eval.
  '((label ff (lambda (x) (cond ((atom x) x) ('t (ff (car x))))))
    '((a . b) . c) )
  '() )

A

最初の例は、環境に lambda 式をあらかじめ変数束縛しておいても実行できます。この場合、label 式にする必要すらありません。

* (eval.
  '(sublis '((x (a b)) (y (b c))) '(a x . y))

  '((sublis (lambda (x y)
      (cond ((atom y) (sub2 x y))
            ('t (cons (sublis x (car y)) (sublis x (cdr y)))) )) )
    (sub2 (lambda (x z)
      (cond ((null x) z)
            ((eq (caar x) z) (cadar x))
            ('t (sub2 (cdr x) z)) )) )
    (null (lambda (x) (eq x 'nil)))
    (caar (lambda (x) (car (car x))))
    (cadar (lambda (x) (car (cdr (car x))))) ) )

(A (A B) B C)

このインタープリタでは関数オペレータがシンボルのとき、実行時に束縛されている値を関数として実引数に適用するため、下記の maplist も動作します。

* (eval.
  '(maplist '((a0 a1) (b0 b1) (c0 c1)) '(lambda (x) (car (car x))))

  '((maplist (lambda (x f)
      (cond
        ((null x) 'nil)
        ('t (cons (f x) (maplist (cdr x) f))) ) ))
    (null (lambda (x) (eq x 'nil)))) )

(A0 B0 C0)