ポール・グレアム Lispの起源 (The Roots of Lisp)
この記事はLisp Advent Calendar 2015 の10日目として書かれました。
- 作者: ポールグレアム,Paul Graham,川合史朗
- 出版社/メーカー: オーム社
- 発売日: 2005/01/01
- メディア: 単行本
- 購入: 109人 クリック: 4,884回
- この商品を含むブログ (582件) を見る
ハッカーと画家で有名なポール・グレアム氏が、ジョン・マッカーシーの1960年のLispのオリジナル論文をCommon Lispで解説した記事を書いていることに最近になって気付いた。
- The Roots of Lisp (www.paulgraham.com) (ソースコード)
かなり古い記事で(2002年)、内容はWikipediaの純LISPの項目と重なるところも多い。しかしながら現在でも非常に重要な記事なので、自分の勉強のためにも訳すことにした。別訳としてはlionfan氏による和訳があるが、こちらは前書き部分のみである。
この記事ではLispを一から定義して、evalを実装するところまでを解説している。ひとたびevalが実装されると、プログラムをあらゆる段階で評価できるようになるので、プログラムを変換してから評価したりできる。これは構文を新たに定義することに他ならないので、その上にどのような言語でも作ることができる。つまり、最も基本的な要素からメタプログラミングの土台を作るところまでを解説することが目的となっている。
この記事を理解できれば、他のどのような言語、計算機の上にも、自分自身でLispを実装できるようになる。一からプログラミング言語を作るという経験は非常に重要なので、ぜひ一度自分自身の手でLispを作ってみてほしい。
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)
最後の式(a b (c) d)は4つの要素を持つリストだが、3番目の要素(c)はそれ自体が1つの要素を持つリストになっている。つまり、リストは入れ子にできる。
算術式1 + 1が値2を持つように、有効なLisp式もまた値を持つ。式eが値vを発生させるとき、それを「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
さて、今や我々はその引数が評価されるようなオペレータatomを手に入れたので、quoteが何のために使われるのかを示すことができる。その目的とは、リストをquoteすることでそのリストを評価から守ることである。atomのようなオペレータに、quoteされてないリストが引数として与えられた場合、それはコードとして扱われる。
(atom (atom 'a)) ; => t
逆に、quoteされたリストは評価から守られるため、単にリストとして扱われる。したがって、次の場合は2要素のリストになり、atomによるテストの結果は偽になる。
(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までの式が順番に評価されていき、各条件式piの値がtになった時点で、それと対応するei式が評価され、その値が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が評価される。次に、各パラメータpiの値が対応する引数aiの値に置き換えられ、それから関数本体部分eが評価される。
((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)
の値となる。言い替えるなら、パラメータは式の中で引数として使われるのと同様にオペレータとしても使われうる。例えば、次の式におけるfは、'aをconsするという関数によって置き換えられ、オペレータとして'(b c)に対して作用する。
((lambda (f) (f '(b c))) (lambda (x) (cons 'a x))) ; => (a b c) ;; 訳注： このコードをCommon Lispで動かすためにはfがオペレータであることを宣言するためにfuncallが必要になる。 ;; Common Lispではパラメータとオペレータでは名前空間が異なるからだ。 ((lambda (f) (funcall f '(b c))) (lambda (x) (cons 'a x)))
これとはまた別に、関数が自分自身を参照できるようにする表記法があり、それによって再帰関数を定義するのが容易になる*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の定義はこうなる。(訳注： Common Lispにはこのlabel記法はないので、実際に動くのは以下のコードとなる。なお、substは組込み関数として既に定義されているため、subst.と置き換えた。ただし、以下で定義しているevalの内部ではlabel記法を扱える)
(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個のアトムを持つリストを使うなどすれば可能ではある
*5: Guy 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.
