/bin/osh

ソフトフェアエンジニアリングしたりデータ分析したりプロジェクトマネジメントの勉強したりする人のブログ

Lisp入門

概要

この記事でわかること

  • Lispの基礎知識
  • Lispのコアとなる部分の考え方
  • Lispがなぜすごいのか

この記事でわからないこと

  • Lispでのアプリケーションの作り方
  • もう1歩踏み込んだラムダ計算の考え(別の記事orLTでやります)

入門じゃないじゃん!と言われる前に言っておくと、入門というのは手取り足取り"Hello World"をするものだけではない。
Lispの考え方、Lispの世界に入門する、という意味で"Lisp入門"としている。

Lisp入門

Lispをちゃんと理解するためにLispがどのような思想で作られたのかを調べた。
今回この記事を書くにあたって、Lispというプログラミング言語が提唱された論文
"Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"を参照した。
この論文が出たのは1960年であり、Lispが考案されたのは1958年だ。
1957年に"広く使われた世界最初の高級言語"と言われるFORTRANが出ているが、それほど古い言語である。
ちなみに論文のタイトルの最後に Part Iとあるが Part IIはない。

Lispの概要

論文の内容の前にLispの基本知識を簡単に説明する。
LISt Processorという意味を持っている。
つまり、Lispの中核はlistなのである。

Lispと聞くと何を思い浮べるだろうか。
おそらく、Lispを少しでも知っている人ならば"かっこ"を思い浮べるだろう。
Lispにとって"かっこ"はとても重要なものだ。
まず、Lispのexpressionは atomlist(pair) から出来ている。
atomとは、"かっこ"と"·"以外の文字が1つ以上繋ったもの(例:foo bar)
listとは、0個以上のexpressionが"かっこ"の中に空白区切りで配置されたもの(例:(foo bar))である。
これがLispを構成する全てと言っても過言ではない。 関数もlistで表されとデータもlistで表される。 Lispでは、関数とデータに本質的な違いはない。 関数もデータである。

Lisp

S式(S-Expressions)

LispはS式(S-Expressions)で表現される。 S式の定義は以下の通りである。

1. atomはS式である。
2. e1とe2がどちらもS式ならば (e1 · e2) はS式

(a · b) という表現はドット対(dotted pair)と呼ばれる。

Elementary S-functions and Predicates

McCarthyはS式を用いて5つのfunctionを定義した。 McCarthyの言うfunctionとは引数の全てが評価されるS式のことを指している。

  1. atom x:xがatomであれば真を、そうでなければ偽を返す。
  2. eq x y:xとyを評価した結果が同じならば真を、そうでなければ偽を返す。
  3. car x:引数にlistをとり、そのlistの先頭を返す。
  4. cdr x:引数にlistをとり、listの先頭以外を返す。
  5. cons x y:xとyのドット対を作る。

これだけあれば様々なlist操作はできるが、プログラミング言語としては不十分である。

Recursive function

先程の5つのfunctionに加えて再帰関数(Recursive function)を書くことができれば、チューリング完全高級言語ができる。 再帰関数を書くために、McCarthyは次の4つを定義している。 (実際にはSUBSTとf[e1;...;en]という表現も同時に定義しているが、コアな部分でないため割愛する。)

  1. QUOTE x:xを評価せずS式自体を返す。
  2. COND (p1 e1)(p2 e2) ... (pn en):条件式(実際はただのS式)とS式のペアの0個以上とり、合致した条件とペアのS式を評価する
  3. LAMBDA (x1 x2 ... xn) e:いわゆるラムダ式。これ自体が関数と同じ働きをし、引数を2つ以上とり、最後の引数はその前の引数をラムダ式の引数とした関数の中身となる。(例:(lambda (a b c) (+ a b c)) (1 3 5))
  4. LABEL x e:eをxで与えられた名前で保持する。

これらの4つがあることによってチューリング完全となる。 実際には不動点コンビネータによってLAMBDAだけで再帰関数が書けるため、チューリング完全のためだけならばLABELはいらない。 McCarthyがこの論文を書いた際には不動点コンビネータが発見されていなかったため、LABELを付けて再帰関数を書いたのだと思われる。

まとめ

Lispの何がすごいか、といえばたった7つ(atom eq car cdr cons quote cond)のオペレータとlambdaでeval関数が書けるところにある。 この論文でeval関数をどう作るかも書いてあるが、この記事の内容とevalの作り方を含めてもたった20ページにしかならない。

また、全てがatomとlistで表現されるためProgrammable programing languageと言われるほど拡張性が高い。 プログラム自体をプログラムできるプログラミング言語なのだ。

この入門記事では、Lispのコアとなるオペレータを紹介してLispの世界に入門した。 途中、ラムダ式不動点コンビネータなどの部分が分かない方もいただろうが、これについてはいつか別の記事で紹介する。