#概要
Common Lispの入門記事です。
#自己紹介
若草春男。趣味プログラマー。30代男性。他のLispユーザーとの交流はない。つまり、ただの引きこもり。Twitterアカウント: @HaruoWakakusa
#この記事を書いた動機
以前、オビ＝ワン・ケノービに似た名前の技術ライターが関数型プログラミング入門の書籍を出版して関数型言語のお偉方から総スカンを食らい業界を去ったという大事件がありました。自分は全くの無名ですが、こういうファンキーなことをしてもいいんじゃないかと思い立ち、この記事を書くに至りました。
つまりアレです。正確ではないかもしれないけれどもざっくりとした説明をして、Lispというものに親しんで頂きたいと思ったわけです。
#単方向リスト
Lispを理解するためには単方向リスト(Singly Linked List)というデータ構造を理解する必要があります。単方向リストをJavaScriptのコードで表現していきます(JavaScriptが分からない人ごめんなさい)。下のコードをコピペしてhtmlファイルに保存、ブラウザで開いてください。
<!DOCTYPE html>
<html>
<head><title>単方向リストサンプル</title></head>
<body>
<h2>Google Chrome:</h2><p>
1. 右上の設定ボタンから[その他のツール] - [デベロッパーツール]を選択します<br>
2. [Console]の項目を選択し、"> "の箇所に入力していきます。</p>
<h2>Microsoft Edge:</h2><p>
1. 右上の設定ボタンから[開発者ツール]を選択します<br>
2. [コンソール]の項目を選択し、"> "の箇所に入力していきます。</p>
<script>
// これはJavaScriptのコードです
// NIL(またはnull)は単方向リストを表現するための特別なシンボルです。
// NILはCの文字列で言うところの'\0'のようなものです。
// このようなものを一般に「番兵」と呼びます。
const NIL = null;
function cons(car, cdr) {
return [car, cdr];
}
function car(list) {
return list[0];
}
function cdr(list) {
return list[1];
}
function print(obj) {
function toString(obj) {
var res;
// オブジェクトがアトム(数値や文字列など)であれば、そのまま変換する
if (typeof(obj) !== "object") return obj.toString();
// オブジェクトが単方向リストであれば、NILが出るまでcdrをたどる
var res = "(";
if (obj !== NIL) {
res = res + toString(car(obj));
obj = cdr(obj);
}
while (obj !== NIL) {
res = res + " " + toString(car(obj));
obj = cdr(obj);
}
return res + ")";
}
console.log(toString(obj));
}
</script>
</body></html>
consはconstruct(構築する)の略です。NILとconsを用いて単方向リストを構築していきます。
NILは空の単方向リストを示します。NILをprintしてみましょう。
> print(NIL);
()
< undefined
()という文字列が表示されました。その下にあるundefinedはJavaScriptのprint関数が値を返さなかったことを示していますが、今回の場合は問題ないので無視します。
> print(cons(1, NIL));
(1)
> print(cons(1, cons(2, NIL)));
(1 2)
> print(cons(1, cons(2, cons(3, NIL))));
(1 2 3)
少し複雑ですが、consとNILを用いて配列のようなものが表現できていることが分かります。
> print(cons(cons(1, cons(2, NIL)), cons(cons(3, cons(4, NIL)), NIL), NIL))
((1 2) (3 4))
単方向リストでは、行列やアルゴリズムに出てくる「木」（き）のような構造も表現することができます。実行効率・メモリ効率を考慮しなければ、自由なデータ構造を表現することができるというところが単方向リストの特徴になります。
単方向リストはシーケンス(Sequence)の一つです。つまりcarとcdrを用いてデータを順に取り出すことができます。上記のprint関数の中でもcarとcdrを用いてデータを取り出しています。
#Lispとは？
LispはList Processorの略で、この単方向リストの構造を用いてデータを処理する仕組みのことを言います。とにかく、この単方向リストを用いた仕組みのことをLispと呼ぶのでLispにはたくさんの種類があります。Lispは（Lispという言語ではなく）Lisp方言と呼ぶことが多く、それぞれの仕様に応じてプログラミング言語の名前(Common Lisp, Scheme, Clojure, Racket等)が付されています。単にLispと呼ぶ場合は主にCommon Lispのことを指します。
#Common Lispとは？
Lispには多くの方言が存在しますが、Lispの仕様を統一しようという試みによってCommon Lispは誕生しました。Common Lispの仕様にはCLtL1(1984), CLtL2(1990), ANSI Common Lisp(1994)の３種類があります。Common Lispの機能はCLtL2でほぼ固まっています。
Common Lispの処理系としてはSBCL, CLISP, Allegro Common Lisp, LispWorksなどがあります。これらの処理系はCLtL2またはANSI Common Lispの仕様に準拠しつつ、独自の機能も付加しています。
##SBCL
BSDライセンスで公開されており、高速で動作するため非常に人気の高い処理系です。ただ、Windowsとの相性がよくないという弱点があります。
##CLISP
GNUライセンスで公開されており、SBCLに比べると処理速度は遅い処理系です。ただ、Cygwinに搭載されているため、Windowsユーザーでも容易に導入することができます。
##Allegro Common Lisp
商用の処理系であり、日本でもライセンスを導入することができます。制限がついていますが無償版も提供されています。
##LispWorks
商用の処理系であり、日本ではライセンスを購入することができません。ただ、LispWorksのマニュアルであるCommon Lisp HyperSpecは多くのLisperが参照しており、私も常用しています。
#Common Lispって何がすごいの？
強力かつ簡潔なマクロ機能です。また、Common LispはCLtL2の時点でだいたいの仕様が固まっているので、多くの優れた文献(On Lisp, Let Over Lambda等)があります。SchemeはCommon Lispよりも新しいLisp方言ですが、仕様は定期的に更新されているため定本というのがあまりありません。ただ、SICPは優れたLisp入門です。
Common Lispのマクロ機能は非常に強力なのでほとんどのプログラミング言語のパラダイムを簡単に実装することができます。従って、手続き型プログラミングと関数型プログラミングの両方に柔軟に対応し、CLOSという優れたオブジェクト指向の仕組みも用意されています。
関数型プログラミングに比べてマクロプログラミングはマイナーですが、Common Lispを学習しておくと両方に高い知見を持つことができます。
#Common Lispの問題点
Common Lispはメジャー言語ではないのでライブラリのサポートが手薄です。また、Common Lispには並行プログラミングの仕組みがありません。並行プログラミングを行いたい場合はより新しいLisp方言であるClojureを使用します。
#Common Lispの学習法
まず、SICPでSchemeを学習します。これの原著はインターネットで公開されており、日本語訳も有志によって公開されています。また、「計算機プログラムの構造と解釈」という書籍としても入手することもできます。SICPは非常にボリュームが多いですが、２章の終わりまで読了すれば特に問題ありません。Schemeの処理系としてはRacketをお勧めします。RacketはSchemeから派生したLisp方言ですが、古いSchemeであるR5RSも選択することができるのでRacketでSICPを学習するのが一番手っ取り早いです。
次に、Let Over Lambdaを学習します。この本は８章までありますが６章までが英語で公開されています。
Common Lispのドキュメントとしては各処理系のマニュアルを参照するのが正しいのですが、基本的なところはCommon Lisp HyperSpecを参照することで理解することができます。Common Lispには組み込みのマクロ、関数、変数が「シンボル(Symbol)」として用意されています。HyperSpecにおいては、[Contents] - [1. Introduction] - [1.9 Symbols in the COMMON-LISP Package]で検索することができます。
Common Lispのソースコードは(他の言語に比べたら少ないですが)Github上に多数アップロードされていますし、StackOverflow等を使えば疑問を解消することもできます。日本のCommon Lisp(そういえばCLと略するのでした)のコミュニティもありますので、それらに参加したりフォローしたりするのもいいでしょう。
#Common Lispのマクロ実演
CLISPを用いてCommon Lispのマクロのデモンストレーションを行います。Windows上ではCLISPはCygwinを用いれば簡単に導入することができます。MacOS, LinuxにおいてはSBCLを導入したほうが手っ取り早いかもしれません。
[1]> (+ 1 2)
3
これは + 関数で1+2という計算をさせています。通常の言語と異なるのは、演算子というものが用意されておらず、数値計算も全て「前置記法」を用いて行うことです。Lispには演算子という仕組みがありません。演算子がないことによって可読性が少し落ちますがシステム全体を理解しやすくなります。つまりLisp処理系は他の言語よりも仕組みが単純なのです。
ちなみに、この(+ 1 2)という式、つまり命令は単方向リストによって表現されています。また、この括弧に囲まれた表現のことをS式(S-expression)と呼び、Lispへの入力は全てS式で行います。
それではこの(+ 1 2)の構造を調べてみましょう。(+ 1 2)の評価をquote(')を用いて停止させ、変数aに代入します。
[6]> (defvar a '(+ 1 2))
A
[7]> a
(+ 1 2)
[8]> (car a)
+
[9]> (cdr a)
(1 2)
[10]> (car (cdr a))
1
[11]> (cdr (cdr a))
(2)
[12]> (car (cdr (cdr a)))
2
[13]> (cdr (cdr (cdr a)))
NIL
(+ 1 2)をcar, cdrによって分解することができるので、これが単方向リストであることが分かります。quote(')で停止させた式の評価はeval関数を用いて行うことができます。
[14]> (eval a)
3
さて、1から10を足し合わせてみましょう。そのためにはextended loopマクロを使用します。
[15]> (loop for i from 1 to 10 sum i)
55
では、このloopマクロはどのようなことをしているのでしょうか？macroexpandを用いて展開してみましょう。
[16]> (macroexpand '(loop for i from 1 to 10 sum i))
(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
(BLOCK NIL
(LET ((I 1))
(PROGN
(LET ((#:ACCUNUM-VAR-2982 0))
(MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
(TAGBODY SYSTEM::BEGIN-LOOP (WHEN (> I 10) (LOOP-FINISH))
(PROGN (SETQ #:ACCUNUM-VAR-2982 (+ #:ACCUNUM-VAR-2982 I)))
(PSETQ I (+ I 1)) (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
(MACROLET
((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP)))
(RETURN-FROM NIL #:ACCUNUM-VAR-2982))))))))) ;
少し難しい式が出てきてしまいましたね(汗)。それではSBCLでもmacroexpandしてみましょう。
* (macroexpand '(loop for i from 1 to 10 sum i))
(BLOCK NIL
(LET ((I 1))
(DECLARE (TYPE (AND REAL NUMBER) I))
(SB-LOOP::WITH-SUM-COUNT #S(SB-LOOP::LOOP-COLLECTOR
:NAME NIL
:CLASS SB-LOOP::SUM
:HISTORY (SB-LOOP::SUM)
:TEMPVARS (#:LOOP-SUM-390)
:SPECIFIED-TYPE NIL
:DTYPE NUMBER
:DATA NIL)
(TAGBODY
SB-LOOP::NEXT-LOOP
(WHEN (> I '10) (GO SB-LOOP::END-LOOP))
(SETQ #:LOOP-SUM-390 (+ #:LOOP-SUM-390 I))
(SB-LOOP::LOOP-REALLY-DESETQ I (1+ I))
(GO SB-LOOP::NEXT-LOOP)
SB-LOOP::END-LOOP
(RETURN-FROM NIL #:LOOP-SUM-390)))))
T
CLISPとSBCLでは展開の仕方が多少異なることが分かるかと思います。また、Common Lispのマクロをそれぞれ処理系独自のマクロに置き換えているのが分かるかと思います。また、SBCLではdeclareによって変数iを数値型に紐づけているのでこれによって高速化を行うことができます。
先ほどのloopマクロはSQLのクエリに似ています。こういうものをDSL(Domain Specific Language)と呼びます。例えばCのprintfのフォーマットや、文字列マッチングを行う正規表現もDSLですが、Lispにおいてはこれらを実行時ではなくマクロ展開時に評価することができ、これにより高速化することができます。但しこれらのマクロは標準では提供されておらず、パッケージをダウンロードするか自作することになります。
さて、変数bの値を3回デクリメントするということを関数とマクロで実現してみましょう。まず変数bを10にします。
[17]> (defvar b 10)
B
これを3回デクリメントする関数はこのようなものです。
[20]>
(defun decf3 ()
(setq b (1- b))
(setq b (1- b))
(setq b (1- b)))
DECF3
ここで、defunは関数を定義するマクロ、setqは変数に破壊的代入を行うSpecial Formです。Special Formというのは、Common Lispの取り扱う特別な形式で、macroexpandなどで分解できない式のことを言います。
[21]> (decf3)
7
[22]> b
7
decf3関数を評価することで変数bが10から7に変化していることが分かります。次に、同じことを３回行うマクロを記述してみます。
[24]>
(defmacro repeat3 (form) `(progn ,form ,form ,form))
REPEAT3
defmacroはdefunと似ていますが、関数の代わりにマクロを定義するというところが異なります。関数はその引数に値を受け取りますが、マクロは評価前の式を受け取ります。また、マクロの中ではbackquoteまたはquasiquote(`)とunquote(,)のペアを用います。このマクロを展開する時、quasiquoteの中は展開しません。但しquasiquoteの中のunquoteは展開します。ちなみにprognは複数の式を順番に評価するときに用います。Cのブロックのような役割を果たします。
これを用いて先ほどのdecf3の異なるバージョンを書いてみます。
[25]> (defun decf3-b () (repeat3 (setq b (1- b))))
DECF3-B
[26]> (decf3-b)
4
[27]> b
4
repeat3マクロによりデクリメントが３回実行され、変数bが7から4に変化していることが分かります。それでは、マクロと関数がどのように実行されるかを見てみましょう。標準出力に文字列を出力するにはformat関数を用います。format関数が返す値はNILです。
[30]> (format t "I am a Common Lisp.")
I am a Common Lisp.
NIL
printmacroマクロはマクロ展開時に文字列を表示します。
[31]> (defmacro printmacro (str form) (format t str) form)
PRINTMACRO
printfunc関数は関数評価時に文字列を表示します。
[33]> (defun printfunc (str arg) (format t str) arg)
PRINTFUNC
さて、printmacroとprintfuncを入れ子にして実行してみましょう。
[36]>
(printmacro "printmacro: A~%"
(printfunc "printfunc: B~%"
(printmacro "printmacro: C~%"
(printfunc "printfunc: D~%" 1))))
printmacro: A
printmacro: C
printfunc: D
printfunc: B
1
関数の評価前にマクロが展開されます。また、関数は「当然ながら」入れ子の内側から評価されますが、マクロは入れ子の外側から展開されます。
ここまでで、もうお気づきかと思いますが、Common Lispではマクロを用いて関数を定義することができ、関数を用いてマクロを定義することができます。これは、マクロの記述に制限がないということを示しています。大抵の言語では関数を用いてマクロを定義することができません。
しかも、Common Lispのマクロの仕組みはこれだけなのです。こんなに単純なのです。非常にオタク的な比喩になってしまいますが、東方Projectの弾幕がquasiquoteで停止し、unquoteで再び動き出す、というくらい簡潔なものです。正直、この記事の内容を把握していればCommon Lispの学習はそれほど苦なものではないと思います。Common Lispの本質は関数型プログラミングではなくCLOSでもなくマクロなのです。Common Lispの実装の大部分はマクロと関数の組み合わせでできています。
#コンパイル
Common Lispのコードはコンパイルすることができます。SBCLでコンパイルすればCよりも高速に動作させられること請け合いでしょう。ちなみにC言語のよさは、分割コンパイルであり、これにより実行速度とコンパイル速度のバランスを取っています。C++言語のよさは一括コンパイルであり、C言語よりも実行速度を上げることができます。しかしコンパイル時間がかかります。悲しいことにC++の新しいバージョンほどその傾向が強くなります。そしてCommon Lispのよさは、インタプリタとコンパイラを両方使用できることであり、ソースコードの実行速度を段階的に高速化できることです。
#Common Lispを学習した後は？
さて、Common Lispに慣れたらその後はどうすればいいのでしょうか。
##Common Lispでプロダクトを作成する
Common Lispは素晴らしい言語です。もしかしたらあなたはCommon Lispでプロダクトを作成できるかもしれません。Common Lispのライブラリは多少貧弱ですがそれでもなんとかできるかもしれません。Common Lispのユーザーが日本にも少数ですがいます。
##他のLisp方言を試してみる
SchemeはCommon Lispの仕様が巨大すぎることを問題視して再構成されたシステムです。ただ、Common Lispのように不変ではありません。ですがCommon Lispを習得したあなたはSchemeを使いこなすことができるかもしれません。
Clojureは今一番熱いLisp方言です。ClojureはJVM上のLispなのでJavaのライブラリを使用することができます。さらに、並行処理の仕組みもあるのでそちらのほうに興味がある人は是非チャレンジするのがよいかと思います。
RacketはあまりメジャーなLisp方言ではありませんし、QtをベースにしているのでそのコアはLGPLです。ですがRacketはとても導入が簡単なシステムです。Windowsでも安定して動作します。マイナー言語であるのに複雑なインストール手順を必要としていません。趣味プログラマーの人はその簡潔さに感動するかもしれません。
##関数型言語を試してみる
Haksell, OCaml, F#といった関数型言語にチャレンジすることができます。これらの言語はCommon Lispほど自由ではありませんが、関数型プログラミングに加えて静的型付き言語の安全性を獲得することができるでしょう。Common Lispを習得した後にこれらの言語に触ると、Lispと関数型言語の類似性に気が付くことでしょう。