CL入門 No.6 - LISPの式

LISPの世界にようこそ

Common Lispの基本的な使い方は覚えたでしょうか?
この記事ではLISPの世界の基礎となる考え方を学習することを目的としています。

LISPとは

wikipedia:LISP

LISPとは「LISt Processing」を名前の由来とするプログラミング言語です。
LISPの歴史は古く1956年にジョン・マッカーシーが発表したFORTRAN*1向けリスト操作言語をから始まります。

小さいコアと柔軟な言語仕様が人気の要因となり、
LISPを実行する専用マシンや多くのLISP方言が生まれるほど
活発に利用されてきました。
1994年には多くの方言に分かれていたLISPスーパーセットとして
Common LispANSIで標準化されました。

以降Common Lispは仕様変更されることなく現代まで使われている
枯れて非常に安定したプログラミング言語です。*2

NIL, T, CONS, CAR, CDR

LISPを構築する最も基本的な要素は、
NIL, Tというアトム*3と、CONS, CAR, CDRという操作です。

NIL

LISPの世界はまずNILから始まります。
NILとは、「空リスト」を表すアトムです。

Common Lisp上でNILを表す表記は下記のようにたくさんあります。

NIL
()
'()
'NIL

Common Lispでは、NILは偽*4を表すアトムでもあります。

T

Tは「真」を表すアトムです。
LISPの世界ではNILでないものは全て真ですが、
TはNILでないアトムの代表というわけです。

T
'T

CONS, CAR, CDR

LISPの世界を構築する最小の構造がCONSセル*5と呼ばれるものです。
CONSセルとは、CAR部とCDR部*6に分かれる2個の参照対です。

CONSセルは次のように書くことができます。
この場合A側がCAR部であり、D側がCDR部となります。

(A . D)

しかし上記のように書いてしまうと、
Common Lispはプログラムとして実行しようとしてしまいます。
CONSセルというデータ自体として扱いたい場合は、
'を先頭につけるか、CONSという操作でCONSセルを生成します。

(CONS 'A 'D)
=>(A . D)
'(A . D)
=>(A . D)

CAR側を取り出す操作をCAR,
CDR側を取り出す操作をCDRと言います。

(CAR '(A . D))
=> A
(CDR '(A . D))
=> D

LIST

LISPにおけるLIST構造は、単純な二つのルールで定められています。

  1. NILはLISTである
  2. CDR部がLISTであるCONSセルはLISTである

つまり、CDRを下っていくといずれNILにたどり着く
連結したCONSセルをLISTと呼ぶわけです。

CONSセルの記法を使ってLISTを書くと次のようになります。

'(A . (B . (C . NIL)))
=>(A B C)

通常は略記法として、"("から")"まで
空白文字で区切りながら要素を羅列することでLISTを表現します。

'(A B C D)
=>(A B C D)

QUOTE

さて、ここまで読んだらお気づきでしょうが、
LISPに登場する全てのプログラムはCONSセルで構築されたLIST構造になっています。

つまりLISPのプログラムは全てCONSセルというデータでもあります。
CONSセルで書かれたプログラムを命令ではなくデータとして扱いたい場合、
QUOTEという機能を使います。

(CDR '(A B C D))
=> (B C D)
(QUOTE (CAR (A B C D)))
=> (CAR (A B C D))

READ

READとはテキストデータを読み、プログラムを構築する操作です。
Common LispソースコードとはREADが読み込んで、
Common Lispのプログラムとして実行可能なデータに変換できるテキストデータのことを指します。

()がNILを表すことや、
( . )がCONSセルを表すことなどは、
全てこのREADという関数がそうするように設計されているからです。

リーダーマクロ

とは言えプログラム全てを括弧のみで書いていくことはいささか骨が折れます。
そのため略記法としてリーダーマクロというものが用意されています。

リーダーマクロとは、READ中に特定の文字を読み込んだ時に
特別な挙動をするというREAD関数の機能です。

「'」というリーダーマクロは、
次のデータを読み込んでそれをQUOTEするという機能です。

'(HELLO WORLD)
=>(HELLO WORLD)
(QUOTE '(HELLO WORLD))
=> '(HELLO WORLD)
(QUOTE (QUOTE (HELLO WORLD)))
=> '(HELLO WORLD)

'が(QUOTE ...)の略記法であることが分かるでしょうか?
リーダーマクロによってソースコード
一見CONSセル以外の構造を含んでいるように見えますが、
実際にはREAD時にLISTを構築する操作を分岐させているだけなのです。

これまでのサンプルコードでも'がよく使われていることが分かります。
リーダーマクロを利用することは、
Lispソースコードを書く上で特別なことではありません。

EVAL

READしたデータやQUOTEしたデータをプログラムとして実行したい場合、
EVAL関数を使います。

(EVAL '(CAR '(A B C))
=> A

EVALは特別な関数ではありません。
QUOTEしないデータがプログラムとして実行されてしまうのは、
Common LispソースコードはREADされた後にEVALに渡されているからです。

PRINT

PRINTはREADの逆である、つまりCommon Lispのデータをソースコードに変換する機能です。
PRINTされたソースコードはREADによって同様の構造に再変換されます。

(PRINT '(A B C))
(A B C)
=>(A B C)

まとめ

LISPの世界はシンプルなデータ構造「CONSセル」によって構築されています。
そしてREAD, PRINTによってプログラマと対話し、
EVALによってCONSセルをプログラムとみなし、
QUOTEでCONSセルをデータと見なすようになるのです。

次回はシンボルとパッケージについて解説します。

*1:こちらも古くから使用され続ける由緒正しいプログラミング言語

*2:仕様変更することなく、現代的なプログラミングにも十分に耐えうる柔軟性を持っています。

*3:それ以上分けることの出来ない単一の要素のこと。

*4:「真」と「偽」とは論理を考えるときに正しいかそうでないかという最も単純な2つの値のことです。

*5:CONSという名前は「組み立てる」を意味する英単語Constructの略称を由来としています。

*6:CARとCDRという名前の由来は、LISPが考案された当時のコンピュータのアーキテクチャによるものです。