翡翠はコンピュータに卵を生むか

2015-12-10

Lispの起源 (The Roots of Lisp)

この記事はLisp Advent Calendar 2015 の10日目として書かれました。


最近になって、Lisp関係のエッセイをたくさん書いているポール・グレアム氏がマッカーシーの1960年のオリジナルのLisp論文をCommon Lispに直して解説した記事を書いていたことに気付いた。

The Roots of Lisp (www.paulgraham.com) (ソースコード

かなり古い記事で(2002年)、内容はWikipediaの純LISPの項目と重なるところも多いのだが、現在でも重要な記事だと思ったので勉強のためにも訳すことにした。別訳としてはlionfan氏による和訳がある(ただし前書き部分のみ)。

この記事ではLispを一から定義して、evalを実装するところまでを解説している。ひとたびevalが実装されると、プログラムをあらゆる段階で評価できるようになるので、プログラムを変換してから評価したりできる。これは構文を新たに定義することに他ならないので、この上にどのような言語でも作ることができる。つまり、最も基本的な要素からメタプログラミングの土台を作るところまでを解説することが目的となっている。

Lispの起源 (The Roots of Lisp)

1960年、ジョン・マッカーシーは驚くべき論文を発表し、その論文で彼はユークリッドが幾何学でやったのと同じようなことをプログラミングの世界でもやった*1。 彼は少数の単純なオペレータと関数のための記法を与え、そこからどのようにしてプログラミング言語全体を構築できるかを示した。彼はこの言語をリスト処理(List Processing)の意味を込めてLispと呼んだ。なぜなら彼のアイディアの中核の一つは、リストと呼ばれる単純なデータ構造をコードとデータの両方に使うことだったからだ。

マッカーシーが何を発見したかを理解することは、ただ単にコンピュータ史上の一里塚としてだけでなく、今後プログラミングというものがどのように発展していくのかを考える上でのモデルとして価値がある。今までのところ、本当の意味で混じりけなく一貫しているプログラミングモデルは2系統あるように見える。すなわち、CモデルとLispモデルだ。これらはその間に低い沼地をはさんだ2つの高台のように見える。コンピュータがよりパワフルに成長するにつれて、発展を続ける新しい言語達は徐々にLispの山の方を目指して移動してきている。

過去20年間、新しくプログラミング言語をつくるときの人気のレシピは、基本的にはCモデルを採用して、Lispモデルから断片的に動的型付けやガベージコレクションのようなパーツを取ってきてくっつけるというものだった。

この記事で私は可能な限り単純な言葉でマッカーシーが何を発見したのかを説明するつもりでいる。重要な点は、単に誰かが40年前に発見した興味深い理論的な結果について学ぶということではなく、今あるプログラミング言語達が将来的にどこを目指しているのかを示すことにある。Lispが奇妙なのは(実際にはそれがLispの特質を定義しているのだが)、LispがLisp自身によって書けるということだ。これによってマッカーシーが示そうとしたことを理解するために、我々は彼の数学的記法を実行可能なCommon Lispコードに直しながら、彼の足跡をたどっていくことにする。

7つの原始オペレータ

まず始めにを定義する。式はアトムリストのどちらかである。アトムは文字の並びである(例: foo)。リストは0個以上の式から成り、空白で区切られ、括弧でくくられている。ここでいくつか式の例を示す。

foo
()
(foo)
(foo bar)
(a b (c) d)

最後の式は4つの要素を持つリストだが、その3番目の要素はそれ自体が1つの要素を持つリストになっている。つまりリストは入れ子にできる。

算術式1+1が値2を持つように、有効なLisp式もまた値を持つ。もし式eが値vを発生させるなら、それを「eがvを返す」と呼ぶ。次のステップは、どのような種類の式がありうるか、そしてどんな値を返すかを定義することだ。

ある式がリストであるとき、そのリストの最初の要素をオペレータと呼び、それ以降の要素を引数と呼ぶ。今から我々は数学でいう公理のような役割を持つ、7つの原始オペレータを定義していく。すなわち、quote、atom、eq、car、cdr、cons、そしてcondの7つだ。

1. quote

(quote x)はxを返す。読みやすさのために(quote x)を'xと略記する。

(quote a)        ; => a
'a               ; => a
(quote (a b c))  ; => (a b c)
2. atom

(atom x)はxがアトムか空リストのときにアトムtを返し、それ以外では空リスト()を返す。Lispでは慣習的に、真理値を表す際にアトムtを真、空リストを偽とする。

(atom 'a)        ; => t
(atom '(a b c))  ; => ()
(atom '())       ; => t

さて、今や我々はその引数が評価されるようなオペレータを手に入れたので、quoteが何のために使われるのかを示すことができる。それはすなわち、リストをquoteすることでそのリストを評価から守れるということだ。atomのようなオペレータに、quoteされてないリストが一つの引数として与えられた場合、それはコードとして扱われる。

(atom (atom 'a))  ; => t

逆に、quoteされたリストは単にリストとして扱われる。(この場合は2要素のリストだ)

(atom '(atom 'a)) ; => ()

これはちょうど英語における引用符(quote)の使い方と対応する。単にCambridgeと書くとそれは「マサチューセッツ州の人口9万人の街」だが、引用符をつけて"Cambridge"と書くことで「9文字の英単語」になるのだ。他のプログラミング言語はquoteのようなものをほとんど持たないので、ちょっと異質な概念に思えるかもしれないが、それはLispが持つ最も独特な特徴の一つと密接に結びついている。それはすなわち、コードとデータが同じデータ構造によって作り上げられており、quoteオペレータがそれら二つを区別する方法であるということだ。

3. eq

(eq x y)はxとyの値が同じアトムか、両方とも空リストであるときにtを返し、それ以外のときは()を返す。

(eq 'a 'a)   ; => t
(eq 'a 'b)   ; => ()
(eq '() '()) ; => t
4. car

(car x)はxの値がリストであるとして、そのリストの最初の要素を返す。

(car '(a b c))    ; => a
5. cdr

(cdr x)はxの値がリストであるとして、そのリストの最初の要素を除いた残りの全ての要素を返す。

(cdr '(a b c))    ; => (b c)
6. cons

(cons x y)はyの値がリストであるとして、xの値にyの値の要素が続くようなリストを返す。

(cons 'a '(b c))                   ; => (a b c)
(cons 'a (cons 'b (cons 'c '())))  ; => (a b c)
(car (cons 'a '(b c)))             ; => a
(cdr (cons 'a '(b c)))             ; => (b c)
7. cond

(cond (p1 e1) ... (pn en))は以下のように評価される。p1からpnまでの式が順番に評価されていき、p式の値がtになった時点で対応するe式が評価され、その値がcond式全体の値として返される。

(cond ((eq 'a 'b) 'first)
      ((atom 'a) 'second))
; => second

7つの原始オペレータのうち、quoteとcondを除く5つではその引数は常に評価される*2。 この種のオペレータを関数(function)と呼ぶ。

関数の表記法

次に関数を記述するための記法を定義する。関数は (lambda (p1 ... pn) e) のように記述される。ここで p1 ... pn はそれぞれパラメータと呼ばれるアトムであり、eは一つの式である。(各パラメータpiはeの中から参照できる)

((lambda (p1 ... pn) e) a1 ... an)

のように、関数をリストの最初の要素として置く式を関数呼び出しと呼び、その値は以下のように計算される。まず、各引数aiが評価される。それからeが評価されるが、このとき各piの値は直近の関数呼び出しにおける、対応するaiの値になる。

((lambda (x) (cons x '(b))) 'a)
; => (a b)

((lambda (x y) (cons x (cdr y)))
 'z
 '(a b c))
; => (z b c)

次の式のように、

(f a1 ... an)

式の第一要素が原始オペレータでないアトムfで、fの値が関数(lambda (p1 ... pn) e)であるなら、その式の値は

((lambda (p1 ... pn) e) a1 ... an)

の値となる。言い替えるなら、パラメータは式の中で引数として使われるのと同様にオペレータとしても使われうる。

((lambda (f) (f '(b c)))
 '(lambda (x) (cons 'a x)))
; => (a b c)

これとはまた別に、関数が自分自身を参照できるようにする表記法があり、それによって再帰関数を定義するのが容易になる*3。 その記法は次のようなものだ。

(label f (lambda ( p1 ... pn ) e))

これは一つの関数を表しており、基本的には (lambda ( p1 ... pn ) e) のように振る舞うのだが、それに加えて、fがeの中であたかもこの関数のパラメータであるかのように現れたとき、そのfはこのlabel式自体へと評価されるという性質を持っている。

例えば、式x、アトムy、リストzを引数として取り、z中に(任意の深さで)出現するyをxに置き換えたリストを返す関数 (subst x y z) を定義したいとする。

(subst 'm 'b '(a b (a b c) d))
; => (a m (a m c) d)

この関数は以下のように表記できる。

(label subst (lambda (x y z)
	       (cond ((atom z)
		      (cond ((eq z y) x)
			    ('t z)))
		     ('t (cons (subst x y (car z))
			       (subst x y (cdr z)))))))

ここで、 f = (label f (lambda ( p1 ... pn ) e)) を次のように略記する。

(defun f ( p1 ... pn ) e)

そうすることで、substの定義はこうなる。

(defun subst (x y z)
  (cond ((atom z)
	 (cond ((eq z y) x)
	       ('t z)))
	('t (cons (subst x y (car z))
		  (subst x y (cdr z))))))

ちなみに、ここでcond式のデフォルト節をどうやって指定するかが出てきている。最初の要素が'tであるような節は常に成功する。従って、

(cond (x y) ('t z))

は他の言語でいうところの if x then y else z と等価である。

いくつかの補助関数

今や我々は関数の表記法を手に入れたので、7つの原始オペレータを使って、新しい関数を定義していくことにする。まずは、いくつかの共通するパターンに省略形を導入することで便利になるだろう。そこで、carとcdrの組合せに対応する省略形としてcxxxrを使う。ここでxxxの部分はaかdの並びである。例えば、(cadr e)は(car (cdr e))の省略形であり、eの二番目の要素を返す。

(cadr  '((a b) (c d) e))  ; => (c d)
(caddr '((a b) (c d) e))  ; => e
(cdar  '((a b) (c d) e))  ; => (b)

また、(cons e1 ... (cons en '()) ...)の省略形として(list e1 ... en)を使う。

(cons 'a (cons 'b (cons 'c '())))
; => (a b c)
(list 'a 'b 'c)
; => (a b c)

さらにいくつか新しい関数を定義するが、原始オペレータと区別するため、またCommon Lisp組込みの関数との名前衝突を回避するために、これらの関数の名前の最後にはピリオドを付けておくことにする。

1. null.

(null. x) はその引数xが空リストかどうかをテストする。

(defun null. (x)
  (eq x '()))

(null. 'a)  ; => ()
(null. '()) ; => t
2. and.

(and. x y) は両方の引数がtを返すときにtを返し、それ以外の場合は()を返す。

(defun and. (x y)
  (cond (x (cond (y 't) ('t '())))
	('t '())))

(and. (atom 'a) (eq 'a 'a)) ; => t
(and. (atom 'a) (eq 'a 'b)) ; => ()
3. not.

(not. x) はその引数xが()を返すときにtを返し、その引数xがtを返すときに()を返す。

(defun not. (x)
  (cond (x '())
	('t 't)))

(not (eq 'a 'a)) ; => ()
(not (eq 'a 'b)) ; => t
4. append.

(append. x y) は2つのリストを引数に取り、それらを連結したリストを返す。

(defun append. (x y)
  (cond ((null. x) y)
	('t (cons (car x) (append. (cdr x) y)))))

(append. '(a b) '(c d)) ; => (a b c d)
(append. '() '(c d))    ; => (c d)
5. pair.

(pair. x y) は2つの同じ長さのリストを引数に取って、それぞれのリストの対応する位置にある要素のペアからなるリストを返す。

(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
	((and. (not. (atom x)) (not. (atom y)))
	 (cons (list (car x) (car y))
	       (pair. (cdr x) (cdr y))))))

(pair. '(x y z) '(a b c))
; => ((x a) (y b) (z c))
6. assoc.

(assoc. x y) は1つのアトムxと、pair.によって生成される形式のリストyを引数に取って、yの要素のリストのうち、第一要素がxであるようなリストの第二要素を値として返す。

(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
     	  ('t (assoc. x (cdr y)))))

(assoc. 'x '((x a) (y b)))         ; => a
(assoc. 'x '((x new) (x a) (y b))) ; => new

サプライズ: evalの実装

ここまでのところで、リストを連結したり、一つの式を別の式に置き換えるなどの関数を(おそらくはエレガントな表記法で)定義できるようになった。しかしそれが何になるというのだろうか? ここで読者にサプライズがある。実はこの時点で既に我々の言語のためのインタプリタとして働く関数を書くことができる。インタプリタは任意のLisp式を引数に取ってその値を返す関数である。以下がその定義になる。

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom) (atom (eval. (cadr e) a)))
       ((eq (car e) 'eq)   (eq   (eval. (cadr e) a)
			         (eval. (caddr e) a)))
       ((eq (car e) 'car)  (car  (eval. (cadr e) a)))
       ((eq (car e) 'cdr)  (cdr  (eval. (cadr e) a)))
       ((eq (car e) 'cons) (cons (eval. (cadr e) a)
				 (eval. (caddr e) a)))
       ((eq (car e) 'cond) (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
			(cdr e))
		  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
	    (cons (list (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
	    (append. (pair. (cadar e) (evlis. (cdr e) a))
		     a)))))
(defun evcon. (c a)
  (cond ((eval. (caar c) a)
	 (eval. (cadar c) a))
	('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
	('t (cons (eval. (car m) a)
		  (evlis. (cdr m) a)))))

このeval.の定義は、これまでに見てきたどの定義よりも長いので、各部分がどのように働くかを詳細に見ていこう。

この関数は2つの引数を取る。eは評価される式で、aはこれまでに関数呼び出しにおけるパラメータとして出現してきたアトムとその値との対応のリストである。このリストは環境(environment)と呼ばれ、pair.によって生成される形式になっている。pair.やassoc.を書いたのは、これらのリストを構築し、探索する為だったのだ。

eval.の骨格は4つの節からなるcond式である。式をどのように評価するかは、その式がどんな種類かによる。このcond式の最初の節はアトムを取り扱う。もしeがアトムなら、環境の中からその値を見つけてくる。

(eval. 'x '((x a) (y b)))  ; => a

2つ目の節は、aをアトムとして、 (a ...) という形になっている式を取り扱うための別のcond式になっている。このcond式は全ての原始オペレータを含んでおり、それぞれに一つずつ対応する節がある。

(eval. '(eq 'a 'a) '())
; => t

(eval. '(cons x '(b c))
       '((x a) (y b)))
; => (a b c)

これらのうちquoteを除く全てで、引数の値を見つけるために再帰的にeval.を呼んでいる。

最後の2つの節はより複雑になってくる。cond式を評価するために、補助関数evcon.を呼んでいる。evcon.はcond式の節のリストcを再帰的に調べていき、最初の要素(条件部)がtを返すような節を見つけ、二番目の要素の値を返す。

(eval. '(cond ((atom x) 'atom)
	      ('t 'list))
       '((x '(a b))))
; => list

eval.の二番目の節の最後の部分(2つ目のcond式のデフォルト節)は、パラメータとして渡されている関数の呼び出しを取り扱う。これは、 (a ...) という形のアトムaをその値(lambda式かlabel式であるべき)で置き換えて、その結果を評価することによって動作する。従って、

(eval. '(f '(b c))
       '((f (lambda (x) (cons 'a x)))))

(eval. '((lambda (x) (cons 'a x)) '(b c))
       '((f (lambda (x) (cons 'a x)))))

となって、(a b c)を返す。

eval.の最後の二つの節は、式の最初の要素にlambda式またはlabel式を直接置くような関数呼び出しを取り扱う。label式の場合、まず関数名と関数本体のリストを環境に追加し、それからlabel式内部のlambda式によってこのlabel式自身を置き換え、その式に対してeval.を呼ぶことにより評価される。つまり、

(eval. '((label firstatom (lambda (x)
			    (cond ((atom x) x)
				  ('t (firstatom (car x))))))
	 y)
       '((y ((a b) (c d)))))

(eval. '((lambda (x)
	   (cond ((atom x) x)
		 ('t (firstatom (car x)))))
	 y)
       '((firstatom
	  (label firstatom (lambda (x)
			     (cond ((atom x) x)
				   ('t (firstatom (car x)))))))
	 (y ((a b) (c d)))))

になり、実際にはaを返す。

最後に、 ((lambda (p1 ... pn) e) a1 ... an) の形の式は次のようにして評価される。まず引数 (a1 ... an) の値のリスト (v1 ... vn) を得るためにevlis.を呼び、それから (p1 v1) ... (pn vn) を環境の先頭に追加してeを評価する。だから、

(eval. '((lambda (x y) (cons x (cdr y)))
	 'a
	 '(b c d))
       '())

(eval. '(cons x (cdr y))
       '((x a) (y (b c d))))

になり、実際には(a c d)を返す。

まとめ

今や我々はevalがどのようにして動くかを理解したので、立ち戻ってそれが何を意味しているのかを考えてみよう。ここで我々が得たものは、非常にエレガントな計算のモデルである。我々は、ただquote、atom、eq、car、cdr、cons、condのみを使って、eval.を定義することができた。そしてそれは実際に我々の言語を実装するものであり、それを使って我々が欲するどのような追加の関数も定義することができる。

もちろん、既に様々な計算のモデルは存在している。最も有名なものはチューリングマシンだが、チューリングマシンのプログラムはあまり読みやすくなるようには考えられていない。もしあなたがアルゴリズムを記述するための言語を欲しているなら、もっと抽象化するためのなにかしらの手段が欲しいと思うだろう。そしてそれがマッカーシーがLispを定義した狙いの一つなのだ。

1960年に定義された言語に足りないものは多い。まず副作用が無いし、副作用を使うときに便利な順次実行の仕組み(つまりCommon Lispのprogn、Schemeのbegin)もない。実用的な数値もないし*4、ダイナミックスコープもない。しかしこれらの制限は、驚くほどわずかなコードを追加するだけで取り除くことができる。SteeleとSussmanはそれをどうやるかを”The Art of the Interpreter”と呼ばれる有名な論文で示した*5

もしあなたがマッカーシーのevalを理解したのなら、単にプログラミング言語史の一つのステージを理解したという以上のものを理解していることになる。これらのアイディアは今日のLispにおいても意味論的な中核であるからだ。マッカーシーの元論文を研究することは、ある意味で、Lispが本当は何であるのかを我々に示してくれる。Lispはマッカーシーがデザインしたものというよりは発見したものという方が近い。Lispは本来、人工知能やラピットプロトタイピング(あるいは他のそのようなレベルのタスク)のための言語というわけではない。Lispとは計算を公理化しようと試みた結果として得られる何かなのである。

長い時間をかけて、メジアンの言語、つまり全体の中央値のあたりにいるプログラマによって使われる言語は継続してLispに近付いてきている。evalを理解することによって、将来の主流な計算のモデルがおそらくどうなっていくだろうかを理解することができるだろう。

*1"Recursive Functions of Symbolic Expressions and Their Computation by Machine, PartI." Communications of the ACM 3:4, April 1960, pp. 184-195.

*2:quoteとcondで始まる式は異なる評価のされ方をする。quote式が評価されると、その引数は評価されずにそのままquote式全体の値として返される。また、正しいcond式では、条件にマッチした部分式だけが評価され、cond式全体の値として返される。

*3:論理的には、このために新しい表記法を定義する必要はない。ここまでに定義した記法を使って、Yコンビネータと呼ばれる関数を扱う関数を使うことによって再帰関数を定義することができる。マッカーシーはこの論文を書いた時点でYコンビネータについては知らなかったかもしれないが、なんであれlabel記法はより読みやすい。

*4:マッカーシーの1960年版Lispでも、例えば数値nを表現するのにn個のアトムを持つリストを使うなどすれば可能ではある

*5Guy Lewis Steele, Jr. and Gerald Jay Sussman, "The Art of the Interpreter, or the Modularity Complex - Parts Zero, One, and Two," MIT AI Lab Memo 453, May 1978.

nfunatonfunato 2015/12/20 19:45 ご存知の方も多いでしょうが Steeleの "The History of Scheme" (例えば http://deptinfo.unice.fr/~roy/JAOO-SchemeHistory-2006public.pdf)もこの延長線上にある興味深い内容ですね。

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


画像認証

トラックバック - http://d.hatena.ne.jp/masatoi/20151210/1449948614