Common Lisp, Scheme, Gauche, Clojureを勉強する前に

前置き

タイトル通りですが、Lispファミリーの言語を勉強する前に知っておきたい基礎知識をまとめます。どれも入門書で言及されるような事柄ですが、説明が欠けていたり不十分だったりして、納得できないことも多いので、自分用にまとめてみました。「勉強する前に」と言うより、勉強するときに併用すると良いかもしれません。

Lispファミリー

Lispには様々な方言があります。まとめて「Lisp族」と呼んだりします。例を挙げます。

Common Lisp(CL)
統一Lisp規格みたいなもの? Lisp処理系が乱立して、バラバラに機能強化が行われた状態を改善しようとした成果。
Scheme
軽量コンパクトを信条としたLisp仕様。Common Lispと共に、Lisp方言の主流と言える。
Gauche
川合史朗氏によるScheme処理系。独自の機能拡張あり。
Clojure
JVM上で動くLisp方言。()だけでなく、[]や{}も使うところが異色。

どの方言も、コードをひと目見ればLispと分かります。その程度には似ていますが、全く別々の言語なので、(SchemeとGaucheを除けば)コードに互換性はありません。本記事の内容にも、一部のLisp方言にしか当てはまらないような事項が含まれていますので、ご注意下さい。

REPL

REPL(Read-Eval-Print Loop)は、Lispのインタープリタです。以下を繰り返します。

  1. プログラム(S式)を読み
  2. Lispフォームとして評価し
  3. 結果を出力する

S式

S式(Symbolic expression)とは、Lisp処理系が処理するプログラムの最小単位です。つまりLispプログラムは、S式の集合です。

S式の例
1
#\a                          ;;文字としての a
"Hello"
(+ 1 2)
(car (quote (1 2 3)))
[1 2 3]                      ;;Clojureのベクタ。
{:name "Tom", :age "18"}     ;;Clojureのマップ。

Lisp処理系の中では、まずリーダ(Reader)が、S式を1つずつ読みながら構文木を作っていきます。このとき、リーダマクロの変換処理も行います。リーダマクロは、主に糖衣構文(Syntactic sugar)として用意された、S式の表記法です。

リーダマクロの例
(car '(1 2 3))               ;;'(1 2 3)は、(quote (1 2 3))に変換される。
#'foo                        ;;ClojureのVarクオート。(var foo)に変換される。

糖衣構文ってのは、タイプ数を減らすための簡略表記です(プログラマを甘やかすのでsugar)。構文木については「マクロ」の節で説明しますが、処理系がプログラムを管理するための内部構造のことです。

Lispフォーム

厳密な定義とは異なるかもしれませんが、Lispフォーム(あるいは単にフォーム(form))とは、Lisp処理系が実行するプログラムの単位(構文木の、枝ひとつ分)です。具体的には、リスト形式のS式をリーダが読むとフォームになる、と考えて良いでしょう。ただし、すべてのリストが正しいLispフォームとは限りません。例えば下記コードの2行目は、S式としては正しいですが、Lispフォームではありません。

(+ 1 2)            ;;このS式は、正しいLispフォームとして評価される。
(1 2 3)            ;;このS式は、正しいLispフォームではない。

なぜなら、Lispでは、リストは関数適用と解釈されるからです。フォームの先頭要素は関数名でなければなりません。

関数適用

Lispがリストを評価するとき、先頭要素を関数とみなし、その関数を残りの要素へ適用します。

(+ 1 2)            ;;結果は3。
(car '(1 2 3))     ;;carはリストの先頭要素を取り出す関数。結果は1。

リストの要素が別のリストだった場合、内側のリストもやはり関数適用と解釈され、その結果を使って、外側のリストを評価します。

(+ (* 3 4) (* 5 6))          ;;42
(car (cdr '(1 2 3)))         ;;cdrは先頭要素を取り除いたリストを返す。結果は2。

「リストは関数適用」というルールには2つの例外があります。特殊フォームとマクロです。

特殊フォーム

特殊フォーム(Special form)は、見た目は関数適用とソックリです。Clojureの例を示します。

(if (> 3 1) "greater" "less or equal")                     ;;"greater"
(quote (1 2 3))                                            ;;(1 2 3)

関数適用との大きな違いは、引数の評価条件です。関数適用では、事前に全ての引数を評価してから関数を適用しますが、特殊フォームの場合は全ての引数が評価されるとは限りません。

上記の例で、if特殊フォームは、第1引数の評価結果が真なら第2引数を評価し、偽なら第3引数を評価して、評価結果をifの結果とします。またquote特殊フォームは、第1引数を評価せず、文字通りそのままをquoteの結果とします。

特殊フォームのラインナップは処理系によって異なりますが、数は20~30個程度でしょう。ユーザが特殊フォームを定義することはできません。

なお特殊フォームは、「特殊形式」と訳される場合もあります。

マクロ

マクロも、関数とソックリです。例えばClojureには、whenというマクロがあります。

(when (> 3 1) (pr "greater") 3)        ;;"greater"が表示され、3が返る。

特殊フォームと同様、引数の評価条件はマクロごとに異なります。whenマクロの場合、第1引数の評価結果が真の場合は残りの引数を順に評価し、最後の評価結果をwhenの結果とします。第1引数が偽ならwhenの結果はnilとなります。

特殊フォームと違うのは、マクロはユーザが定義できる、という点です。また、マクロはファーストクラスオブジェクトではありません(なので、関数の引数にマクロを指定したり、関数がマクロを返すことはできない)。C/C++を知っている人なら、#define MIN(x,y) ((x)<(y)?(x):(y)) みたいなプリプロセッサマクロを使ったことがあると思いますが、Lispのマクロはもっと強力らしいです。

マクロが実行されるのは、リーダがS式を読んで構文木を作ったあとです。構文木にマクロ呼び出しのフォームが含まれる場合、それらを実行して、結果で置き換えていきます。whenマクロはif特殊フォームとdo特殊フォームで定義されており、上記のコードを実行した結果は以下のようになります。

(if (> 3 1) (do (pr "greater") 3))

このような置き換えを、マクロ呼び出しが無くなるまで繰り返します(マクロの中で別のマクロを呼んでいる可能性があるので、1周では終わらない)。これをマクロ展開(Macro expansion)と呼びます。深入りはしませんが、マクロ定義の中では、構文クオートやアンクオートといったリーダマクロを使います。REPLのRead-Eval-Printと対応付けるなら、マクロ展開が行われるのはReadとEvalの間です。Readの最後と考えても、Evalの最初と考えても良いと思いますが、大事なのは、マクロ展開は、関数や特殊フォームの適用よりも前に行われるということです。

ここまでの説明で構文木という言葉を使ってきましたが、構文木とは、Lisp処理系がプログラムを内部で管理するためのデータ構造です。例を図示します(アバウトですが)。

構文木

マクロを使うと、リーダが作ったこのデータ構造の一部分を変形することができます。whenがifとdoに変形されたように。構文木は、「木」というくらいなので木構造です。木構造は、(ネストした)リストで表現されます。Lispはリスト処理が得意です。すなはち、マクロがあれば、プログラムを自由に変形できるということになります。JavaScriptがDOMツリーを自由に変形するのと似てなくもないですね。

コマンドとオペレータ

関数、特殊フォーム、及びマクロは、いずれもLispフォームで、見た目もソックリでした。それぞれ、引数の評価条件が異なるので、コードを書くときや読むときは、どれを相手にしているのか意識する必要があります。

一方、3つを総称するときは、「コマンド」とか「オペレータ」という用語を使うことが多いようです。「ifコマンド」とか「andオペレータ」といった感じです。ifコマンドを先頭要素に持つフォームは「ifフォーム」です。

carとcdr(とconsセル)

リストの先頭要素を取り出す関数がcar、リストから先頭を除いた残りを得る関数がcdrです。こういった奇妙な名前は、最初にLispが実装されたコンピュータIBM 704のアーキテクチャに由来しています。

IBM 704の1語は36bitで、ある種の命令を実行するとき、この36bitを4つのパートに分けて使うようになっていたそうです。

  • Prefix part(3bit)
  • Decrement part(15bit)
  • Tag part(3bit)
  • Address part(15bit)

一般にプログラム内では、リストをセルの連なりとして表現します。1つのセルは、1つの値と次のセルへのポインタを持ちます。

セル

IBM 704の1語にはアドレス(15bit)が2つ収まるため、1つのセルを管理するのに都合が良いです。そこで、Address partにセルの値へのアドレスを持たせ、Decrement partに次のセルへのアドレスを持たせるようにしたのです。

リスト

この結果、先頭要素を取り出すのがcar(Contents of the Address part of Register number)、残りを返すのがcdr(Contents of the Decrement part of Register number)となったそうです。

セルを作る関数も存在します。cons関数は、Address partとDecrement partに値をセットして1つのセルを作ります(consはConstructに由来)。このことから、Lispではセルのことをconsセルと呼びます。以下、Gaucheのコード例です。

gosh> (cons 1 '())
(1)
gosh> (cons 1 '(2 3))
(1 2 3)

また、セルは2つの値を保持することから、ペア(pair)、あるいは「対」と呼ばれることもあります。これに対し、数値や文字などの単一の(つまりペアじゃない)データのことはアトム(atom)と呼びます。

ドット対

cons関数はセルを作りますが、このとき、Decrement partにアトムを指定することも可能です。

gosh> (cons 1 2)
(1 . 2)
gosh> (cons '() 2)
(() . 2)

こうして作成されたセルは、2つの値をドット(.)で連結して表記します。このことから、セルのことをドット対(dotted pair)と呼ぶこともあります。セルの別名が多いですね(consセル、ペア、ドット対、…)。

実は、リストもドット対の一種です。ドット対のDecrement partには何を指定してもよく、たまたま対や空リストを指定した場合はリストが生成される、ということです。ドット対の右側にいろんな値を指定して評価してみましょう(クオートするのを忘れずに。そうしないと関数適用と解釈されます)。

gosh> '(1 . 2)
(1 . 2)
gosh> '(1 . ())
(1)
gosh> '(1 . (2 3))
(1 2 3)
gosh> '(1 . (2 . (3 . ())))
(1 2 3)

ちなみにClojureは、セルやドット対という概念を捨てています。Clojureにもcons関数はありますが、第2引数にアトムを指定することはできません。

クオートの使いどころ

Lispのコードを書き始めると、クオートすべきかどうか迷うことが良くあります。また、コードを読んでて、何でクオートしなくて大丈夫なんだろう、と感じることも多いです。ここでは、迷わせるポイントを挙げてみます。

まず、いろんなS式について、それを評価するとどうなるか整理します。

S式の種類評価結果
数値それ自身
文字それ自身
文字列それ自身
Schemeの()それ自身
Clojureのnilそれ自身
キーワード(:で始まるシンボル)それ自身
シンボルシンボルにバインドされた値
リスト(先頭要素が関数)関数適用した結果
リスト(先頭要素が特殊フォーム)特殊フォームを適用した結果
リスト(先頭要素がマクロ)マクロ展開した結果
Clojureのベクタやセットなど各要素を評価した結果からなるベクタやセットなど

注意点の1つ目は、「それ自身に評価されるものは、クオートする必要がない」という点です。クオートしてもしなくても同じ結果になるなら、クオートしません。

gosh> 1
1
gosh> '1
1
gosh> "Hello"
"Hello"
gosh> '"Hello"
"Hello"
gosh> ()
()
gosh> '()
()

注意点の2つ目は、「関数適用の引数は、クオートしない限り、すべて評価される」です。よって、評価結果でなくリテラルそのままを関数に渡したいならクオートします。関数が何を欲しがっているか判断するには、その関数の仕様を調べるしかありません。

最後の注意点は、「特殊フォームやマクロの引数は、クオートしない」です(ウソかも)。引数を評価するかどうかは、特殊フォームやマクロごとに決まるので、クオートしても意味が無いです。

クオートとは逆ですが、評価してほしいのに評価されないというケースもありますね。この場合は、evalやapplyを使うんでしょうね。

Lisp-1とLisp-2

Lisp方言の中でも、変数名と関数名を同じ名前空間で管理するものをLisp-1と呼び、別々の名前空間で管理するものをLisp-2と呼びます。例えば、SchemeやClojureはLisp-1で、Common LispはLisp-2です。

Lisp-1では、stringやlistのような変数名を避ける必要があります。同名の、より上位の(例えば組み込みの)関数を隠してしまう危険があるためです。Lisp-2では、そういった心配はありません。一方、Lisp-2にもデメリットがあるようです(詳しく語ることはできませんが)。

Last modified:2013/07/24 20:24:31
Keyword(s):
References:[FP: 関数型プログラミング]
This page is frozen.