Common Lispプログラミング一時間体験講座

この記事は，プログラミング言語のCommon Lisp，および，LISP系言語全般をほとんど知らない，けれども他の言語でプログラミングに触れた経験がある人向けに，最低限の記述方法と応用例をまとめたものです．※わかる人向け：普通のリスト処理解説

#主に想定される読者

• 普段使用しているプログラミング言語でリスト処理ができるが，関数型プログラミングに基づくリスト処理記述が何をしているのかよくわからない．
• プログラミングは極めているがLISP系言語はよく知らないので，『知っている言語』を増やすため，とりあえずどういう記述方法か知っておきたい．

※拙作記事『Schemeプログラミング一時間体験講座』の姉妹版ですが，こちらではラムダ計算や数値演算は扱わず，リスト処理を中心に解説しています．

#Common Lisp記述の実行
言語処理系としてはSBCLやGNU CLISPがあります．この記事では，主にSBCLの対話モード（REPL）で解説します（『*』はプロンプトです）．UNIXシェルから起動する場合は，GNU readlineの機能を付加するrlwrapで起動すると便利です．対話モードを終了する時は(exit)を実行します．

$ rlwrap sbcl
...
* (exit)
$

『JDoodle』などのWeb実行環境でも良いかもしれませんが，対話モードと同様の実行結果を表示するには(print ... )で括る必要があります．

なお，Common Lispではありませんが，記事の内容と同等のことが，Emacs Lisp（GNU Emacsの機能拡張言語）やScheme（処理系としては，Gauche，GNU Guile，SCM，等）など，他のLISP系言語の処理系でも実行できます．記号や基本関数が異なりますが，既にインストールされているものがあれば，そちらを用いても良いでしょう．
→番外：GNU EmacsのEmacs Lisp対話モードでの実行
→番外：Julia処理系組み込みのFemtoLispを用いた実行

#基本的な記述方法

##リスト
Common Lispに限らずLISP系言語では，基本的なデータ構造として『リスト』を多く用います．複数の要素をまとめて扱いますので配列に似ていますが，後述の『ドット対』によって，要素は先頭から芋づる式に連なっています．このため，先頭から要素を順番にたどって様々な処理を行うのに向いているデータ構造です．

次の記述は，リスト構造を示した例です．括弧と空白で要素の連なりを表現しています．なお，リストの要素としてリストを設けることができます．

* '(Hello nice to meet you)
(HELLO NICE TO MEET YOU)
* '((Sato Aug 10) (Suzuki Jan 24) (Naito Nov 05))
((SATO AUG 10) (SUZUKI JAN 24) (NAITO NOV 5))

'（シングルクォート）は，後述の『関数』の実行と区別するために付けています．記号としてのアルファベットは大文字と小文字の区別がなく，対話モードの表示では全て大文字となる場合がほとんどです．

##リスト操作
carはリストの先頭の要素を，cdrはリストの先頭の要素を取り除いたリストを返します．なお，carとcdrはあらかじめ用意された『関数』であり，リスト表現の最初の要素として記述しますが，関数を実行することを示すため，リスト表現には 'を付けずに記述します．

* (car '(Hello nice to meet you))
HELLO
* (car (cdr '(Hello nice to meet you)))
NICE
* (cdr (cdr '(Hello nice to meet you)))
(TO MEET YOU)
* (car (cdr (cdr '(Hello nice to meet you))))
TO

関数は数学のそれと同じく，関数実行を行った結果を別の関数の引数として指定することができます．このため，cdrを繰り返し実行した後にcarを実行することによって，先頭からの任意の場所にある要素をリストから取り出すことができます．

指定したリスト構造や関数実行の結果は，defparameterを用いて名前を付けることができます．

* (defparameter L '((Sato Aug 10) (Suzuki Jan 24) (Naito Nov 05)))
L
* (car (car (cdr (cdr L))))
NAITO

carとcdrの逆，すなわち，ひとつの要素とリストを組み合わせるにはconsを用います．第一引数に先頭の要素を，第二引数にリストを指定します．consは，リストの要素を結合するわけではないことに注意して下さい．また，要素としての記号を名前と区別するため，ここでも '（シングルクォート）を用いています．

* (cons 'a '(b c))
(A B C)
* (defparameter M '((Eng 100) (Chem 87)))
M
* (cons '(Math 30) (cdr M))
((MATH 30) (CHEM 87))

##ドット対
consは，要素とリストの組合せだけでなく，要素と要素の組合せとすることもできます．

* (cons 'a 'b)
(A . B)
* (car (cons 'a 'b))
A
* (cdr (cons 'a 'b))
B

このように，ふたつのみの要素で構成されるデータ構造を，『ドット対（dot pairs）』または『コンスセル（cons cells）』と呼びます．ドット対は，要素が連なるリスト構造を構成するための基本的な単位となっており，リストは本来，次の実行例のようにドット対の連なりで構成されています．

* (cons 'Hello (cons 'nice (cons 'to (cons 'meet (cons 'you '())))))
(HELLO NICE TO MEET YOU)

最後のドット対の'()は要素のないリスト，すなわち空リストで，それ以降のドット対がない＝リストの最後となることを示しています．リストを作成する処理を行う際には，このようなドット対によるリスト構造を生成することになります．ただし，要素を並べてリストを作成する場合は，list関数を用いることも可能です．

* (list 'Hello 'nice 'to 'meet 'you)
(HELLO NICE TO MEET YOU)

また，ドット対はリスト表現と同じく，'を用いて直接記述することもできます．

* '(a . b)
(A . B)
* (car '(a . b))
A
* (cdr '(a . b))
B
* (defparameter D '((Eng . 100) (Chem . 87)))
D
* (car D)
(ENG . 100)
* (cdr (car D))
100
* (car (cdr D))
(CHEM . 87)
* (cdr (car (cdr D)))
87

##条件式と条件分岐
リストや要素が等しいか否かを確認するための関数equalがあり，『条件式』として成立していればT，成立していなければNILという特別な記号を返します．

* (defparameter N '((address . 352-1021) (name . Takahashi)))
N
* (equal 'address (car (car N)))
T
* (equal 'name (car (car N)))
NIL
* (equal '(address . 352-1021) (car N))
T

この条件式を利用して，ifを用いた条件分岐が記述できます．条件式と，その条件式がTの時に行わせたい処理，NILの時に行わせたい処理を指定します．NILの時の処理は省略でき，条件式が成立しなかった時はNILを返します．

* (defparameter Subjects '((100 . Chem) (200 . Math) (300 . Lang)))
SUBJECTS
* (if (equal (cdr (car Subjects)) 'Chem) (car (car Subjects)) 'fail)
100
* (if (equal (cdr (car Subjects)) 'Math) (car (car Subjects)) 'fail)
FAIL
* (if (equal (cdr (car Subjects)) 'Math) (car (car Subjects)))
NIL

##関数の定義
defunを用いて関数を定義することができます．関数の名前，引数の名前のリスト，関数処理本体を記述していきます．

* (defun CheckChem (L) (if (equal (cdr (car L)) 'Chem) (car (car L)) 'fail))
CHECKCHEM
* (CheckChem '((100 . Chem) (200 . Math) (300 . Lang)))
100

関数は，自分自身を呼び出して処理を行う『再帰関数』としても定義できます．次は，引数に指定したリスト構造を先頭から次々とチェックし，該当する要素が見つかった際に対応する記号を返す関数の定義例です．

* (defun GetValue (L k) (if (equal L '()) '() (if (equal (car (car L)) k) (cdr (car L)) (GetValue (cdr L) k))))
GETVALUE
* (defparameter Items '((Apple . 120) (Orange . 97) (Lemon . 210)))
ITEMS
* (GetValue Items 'Orange)
97
* (GetValue Items 'Nashi)
NIL

ところで，プログラム記述は通常，改行や不要な空白は無視されますので，括弧の対応さえ正確であれば，字下げや改行などを用いて見やすくすることができます．

* (defun GetItem (L k)
    (if (equal L '())
        '()
        (if (equal (car (car L)) k)
            (cdr (car L))
            (GetItem (cdr L) k))))
GETITEM
* (defparameter Table '((101 . Apple) (102 . Orange) (103 . Lemon)))
TABLE
* (GetItem Table 102)
ORANGE
* (GetItem Table 104)
NIL

#応用例

##連想リスト
基本的な記述方法の例で何度か登場した『ドット対によるキーワードと値の組合せの集合』は，連想リストと呼ばれています．他のプログラミング言語では連想配列，辞書型，ハッシュとして実現され，Common Lispでもそのようなデータ構造が用意されていますが，ドット対のリストも連想リストとしてよく利用されています．

たとえば，先に定義したGetValueやGetItemに相当する汎用関数としてassoc，（carではなく）cdrに対応する要素を指定してドット対を取り出すrassocがあります．

* (defparameter Lists '((Apple . 120) (Orange . 97) (Lemon . 210)))
LISTS
* (assoc 'Orange Lists)
(ORANGE . 97)
* (cdr (assoc 'Lemon Lists))
210
* (rassoc 97 Lists)
(ORANGE . 97)
* (car (rassoc 97 Lists))
ORANGE

ここで，キーワードのリストと値のリストを用意し，要素の順番に合わせて連想リストを作る関数mkassocを定義してみましょう．

(mkassoc '(hoge hage hige) '(10 20 30))
=> ((hoge . 10) (hage . 20) (hige . 30)) が作られる

まず，引数として指定されたリストaとbのどちらか一方，または両方が，要素なしの空リスト'()だった時は，空リストを返すと考えます．

条件式を『または』で結びつける時はor，『かつ』で結びつける時はandですが，これらも関数ですので，条件式を引数としてとります．空リストか否かは，先の例では(equal x '())としていましたが，(null x)を用いることもできます．

(if (or (null a) (null b)) '() ...

上記のorが成り立たない時は，aとbの両方に少なくともひとつの要素があるということですから，次は，それぞれの先頭の要素をcarで取り出してドット対を作ることを考えます．

(cons (car a) (car b))

そして，残りの要素をもつリストはそれぞれcdrで取得できますので，関数自身であるmkassocを呼び出して同じ処理（再帰処理）を行わせることにします．

(mkassoc (cdr a) (cdr b))

(cons (car a) (car b))をリストの先頭要素，(mkassoc (cdr a) (cdr b))をリストの残りの要素をもつリストとすれば，consを用いて目的の連想リストを生成することができます．

(cons (cons (car a) (car b))
      (mkassoc (cdr a) (cdr b)))

以上の記述を組み合わせれば，関数mkassocをdefunで定義することができます．

* (defun mkassoc (a b)
    (if (or (null a) (null b)) '()
        (cons (cons (car a) (car b))
              (mkassoc (cdr a) (cdr b)))))
MKASSOC
* (defparameter L (mkassoc '(hoge hage hige) '(10 20 30)))
L
* L
((HOGE . 10) (HAGE . 20) (HIGE . 30))
* (cdr (assoc 'hage L))
20
* (car (rassoc 30 L))
HIGE

##Map
関数型プログラミングで有名な処理に『リストの各要素を引数にして指定した関数を実行し，その結果を再びリストにして返す』というものがあります．通称『Map』と呼ばれていますが，Common Lispではmapcarという関数として用意されています．

実のところ，このmapcarを用いると，先のmkassocと同じ処理が簡単にできてしまいます．

* (mapcar #'cons '(hoge hage hige) '(10 20 30))
((HOGE . 10) (HAGE . 20) (HIGE . 30))

ここで，#'は関数を別の関数の引数として渡すための記号です．関数定義は，リストなどのデータに付けられる名前の定義とは扱いが異なるため，特別な指定が必要になります．上記の実行例を，consとlistで記述した処理に置き換えると，次のようになります．

* (list (cons 'hoge '10) (cons 'hage '20) (cons 'hige '30))
((HOGE . 10) (HAGE . 20) (HIGE . 30))

Mapは，別の関数を引数にとることから，様々な目的に利用することができます．仕組みは先のmkassocと同じで，引数のリスト構造を先頭の要素から順番に再帰的に処理を行います．これは，リスト構造がドット対によって，先頭の要素から連なっている再帰構造をもつデータであり，リスト処理を行う関数も再帰的に行うと良いためです．

先のmkassocを基にした独自のmap関数mymapを定義すると次のようになります（ただし，引数としてリストを必ずふたつとるバージョンとなります）．

* (defun mymap (f a b)
    (if (or (null a) (null b)) '()
        (cons (funcall f (car a) (car b))
              (mymap f (cdr a) (cdr b)))))
MYMAP
* (mymap #'cons '(hoge hage hige) '(10 20 30))
((HOGE . 10) (HAGE . 20) (HIGE . 30))
* (mymap #'equal '(a b c d e) '(a a c c e))
(T NIL T NIL T)

funcallは，先の#'と同じく，受け取った引数を関数として呼び出すための特別な指定です．

##Filter
連想リストから，あるキーワードをもつ値だけのリストを生成する，いわゆる『Filter』処理を行いたいと考えます．このFilterも，関数型プログラミングでは有名な処理のひとつです．

リストの要素全てをチェックすることからmapcarを用いたいところですが，mapcarは各要素に指定した関数を実行するだけですので，たとえば次のように，判断する関数を独自に定義しても，他のキーワードをもつ要素がNILとなり，うまくいきません．

* (defparameter L (mapcar #'cons '(o o i a i a o) '(1 2 10 20 3 30 4)))
L
* L
((O . 1) (O . 2) (I . 10) (A . 20) (I . 3) (A . 30) (O . 4))
* (defun o (x) (if (equal (car x) 'o) (cdr x)))
O
* (mapcar #'o L)
(1 2 NIL NIL NIL NIL 4)

Mapとは処理内容が異なる関数を独自に定義することもできますが，ここでは，Common Lispで用意されているremove-if-not関数を使用してみましょう．この関数は，TかNILの値を返す関数を引数としてとり，リストからNILとなる要素を除外したリストを返します．

今回は，該当する要素のみを取り出したいので，『何が該当するか』をTかNILの値で返す関数ocheckを定義して使用しています．

* L
((O . 1) (O . 2) (I . 10) (A . 20) (I . 3) (A . 30) (O . 4))
* (defun ocheck (x) (equal (car x) 'o))
OCHECK
* (remove-if-not #'ocheck L)
((O . 1) (O . 2) (O . 4))
* (mapcar #'cdr (remove-if-not #'ocheck L))
(1 2 4)

なお，独自に定義した関数filterの記述例は次の通りです．同じく検索を行うassocに相当するGetValue，GetItemの定義にとてもよく似た構成となっています．

* (defun filter (f a)
    (if (null a) '()
        (if (funcall f (car a))
            (cons (car a) (filter f (cdr a)))
            (filter f (cdr a)))))
FILTER
* (defun ocheck (x) (equal (car x) 'o))
OCHECK
* (filter #'ocheck '((O . 1) (O . 2) (I . 10) (A . 20) (I . 3) (A . 30) (O . 4)))
((O . 1) (O . 2) (O . 4))

##Reduce
Reduce（またはFold）と呼ばれている処理は，引数として関数とリスト，そして初期値をとって『畳み込み』を行います．Mapがリストの要素それぞれに指定した関数を実行するのに対し，Reduceはリストの要素を指定した関数で連鎖的に実行していきます．連鎖的に処理を行うことから，ふたつの引数をとる関数をReduceの引数として指定することになります．

Common Lispでは，そのままreduceという名前の関数が用意されています．たとえば，ふたつのリストの要素をまとめてひとつのリストにする処理をreduceで行うと次のようになります．

* (reduce #'cons '(a b c) :initial-value '(d e f g) :from-end T)
(A B C D E F G)

これは，consのみで記述した次と同じ処理を行います．

* (cons 'a (cons 'b (cons 'c '(d e f g))))
(A B C D E F G)

すなわちreduceは，指定したリスト構造'(a b c)の後ろの要素:from-end Tから指定した関数consを初期値:initial-value '(d e f g)に対して行ったことになります．

次は，ふたつのリストの要素をまとめるreduceの処理を関数concatで定義し，更にそのconcatを用いて，『リストのリスト』，すなわち，二次元リストの要素を一次元の要素の並びのリストにするreduceの処理を関数flatとして定義し，実行した例です．

* (defun concat (a b) (reduce #'cons a :initial-value b :from-end T))
CONCAT
* (defun flat (d) (reduce #'concat d :initial-value '() :from-end T))
FLAT
* (flat '((a b) (c d e) (f) (g h i)))
(A B C D E F G H I)

先と同じく，concatおよびconsに置き換えると，次のようになります．最終的な処理結果が，ドット対による単純なリスト構造となることがわかります．

(flat '((a b) (c d e) (f) (g h i)))
=> (concat '(a b) (concat '(c d e) (concat '(f) (concat '(g h i) '()))))
=> (cons 'a (cons 'b (cons 'c (cons 'd (cons 'e (cons 'f (cons 'g (cons 'h (cons 'i '())))))))))
=> (A B C D E F G H I)

なお，Common Lispにはconcatに相当する関数appendが用意されています．

* (append '(1 2 3) '(4 5))
(1 2 3 4 5)
* (reduce #'append '((a b) (c d e) (f) (g h i)) :initial-value '() :from-end T)
(A B C D E F G H I)

また，上記のreduceの利用例と同じ処理を行う関数myreduceを独自定義した例が次の記述です．比較的単純な構成であることがわかります．

* (defun myreduce (f L i)
    (if (null L) i
        (funcall f (car L) (myreduce f (cdr L) i))))
MYREDUCE
* (myreduce #'cons '(a b c) '(d e f g))
(A B C D E F G)
* (myreduce #'append '((a b) (c d e) (f) (g h i)) '())
(A B C D E F G H I)

#まとめ
Common Lispのプログラミングについて，リスト処理を中心に体験してきました．理解してほしいのは，Map/Filter/Reduce機能を用いたリスト処理を行うのが関数型プログラミングというわけではなく，それらは関数型プログラミングによって実現されている機能の一例である，ということです．

最後に，Pythonのリスト内包表記である

>>> tuple((x, y) for x in (1,2,3) for y in (7,8,9) if x + y < 11)
((1, 7), (1, 8), (1, 9), (2, 7), (2, 8), (3, 7))

と同等の処理を行う記述を，独自定義したFilter/Reduce関数のみで実現した例を紹介して終わりにしたいと思います．

* (defun filter (f a) (if (null a) '() (if (funcall f (car a)) (cons (car a) (filter f (cdr a))) (filter f (cdr a)))))
FILTER
* (defun myreduce (f L i) (if (null L) i (funcall f (car L) (myreduce f (cdr L) i))))
MYREDUCE
* (defun concat (a b) (myreduce #'cons a b))
CONCAT
* (defun f1 (x L) (if (null L) '() (cons (list x (car L)) (f1 x (cdr L)))))
F1
* (defun f2 (L1 L2) (if (null L1) '() (cons (f1 (car L1) L2) (f2 (cdr L1) L2))))
F2
* (defun list-ch (L1 L2) (myreduce #'concat (f2 L1 L2) '()))
LIST-CH
* (defun ltcheck (x) (< (+ (car x) (car (cdr x))) 11))
LTCHECK
* (filter #'ltcheck (list-ch '(1 2 3) '(7 8 9)))
((1 7) (1 8) (1 9) (2 7) (2 8) (3 7))

#番外：GNU EmacsのEmacs Lisp対話モードでの実行
M-x ielmで対話モードが起動します．コマンドとしてemacs -e 'ielm'で直接起動しても良いでしょう．終了は，C-x C-cでGNU Emacs本体ごと終了できます．

*** Welcome to IELM ***  Type (describe-mode) for help.
ELISP> 

最初に，(require 'cl-lib)を実行します．

ELISP> (require 'cl-lib)
cl-lib

記号や関数は，次のように読み替えて下さい．

Common Lisp	Emacs Lisp
大文字・小文字区別なし	大文字・小文字区別あり
defparameter	setq
T	t（小文字）
NIL	nil（小文字）
mapcar	cl-mapcar
remove-if-not	cl-remove-if-not
reduce	cl-reduce

次は，Reduce関数を用いた実行例です．

ELISP> (cl-reduce #'cons '(a b c) :initial-value '(d e f g) :from-end t)
(a b c d e f g)

#番外：Julia処理系組み込みのFemtoLispを用いた実行
オプションとして--lispを指定してJulia処理系を起動すると，FemtoLispの対話モードが起動します．下記は，rlwrapと共に起動（および終了）している例です．

$ rlwrap julia --lisp
;  _
; |_ _ _ |_ _ |  . _ _
; | (-||||_(_)|__|_)|_)
;-------------------|----------------------------------------------------------

> (exit)
$

文法や記号の多くはSchemeの仕様に沿っていることから，記号や関数は次のように読み替えて下さい．

Common Lisp	FemtoLisp（Scheme）
大文字・小文字区別なし	大文字・小文字区別あり
defparameter	define
T	#t
NIL	#f
equal	equal?
defun	define（引数指定にも違いあり）
rassoc	FemtoLispでは要独自定義
mapcar	map
#'	不要
funcall	不要
null	null?
remove-if-not	filter
reduce	FemtoLispでは要独自定義

関数定義もdefineを用いますが，関数の名前と引数の名前をひとつのリスト表現とすることで，関数を実行する時と同じ形式にします．

> (define (CheckChem L) (if (equal? (cdr (car L)) 'Chem) (car (car L)) 'fail))
#fn("6000r1|MNc0>660|MM;c1;" [Chem fail] CheckChem)

> (CheckChem '((100 . Chem) (200 . Math) (300 . Lang)))
100

FemtoLispにrassoc関数はありませんので（assocはあります），独自に定義します．

> (define (rassoc k L)
    (if (null? L) '()
        (if (equal? (cdr (car L)) k)
            (car L)
            (rassoc k (cdr L)))))
#fn("7000r2}\x8540_;}MN|>650}M;e0|}N42;" [rassoc] rassoc)

> (define Lists '((Apple . 120) (Orange . 97) (Lemon . 210)))
((Apple . 120) (Orange . 97) (Lemon . 210))

> (assoc 'Orange Lists)
(Orange . 97)

> (cdr (assoc 'Lemon Lists))
210

> (rassoc 97 Lists)
(Orange . 97)

> (car (rassoc 97 Lists))
Orange

関数を別の関数の引数として渡すための記号や，受け取った引数を関数として呼び出すための特別な指定は必要ありません．

> (define (mymap f a b)
    (if (or (null? a) (null? b)) '()
      (cons (f (car a) (car b))
            (mymap f (cdr a) (cdr b)))))
#fn("9000r3}A17602g2A640_;|}Mg2M32e0|}Ng2N33K;" [mymap] mymap)

> (mymap cons '(hoge hage hige) '(10 20 30))
((hoge . 10) (hage . 20) (hige . 30))

> (mymap equal? '(a b c d e) '(a a c c e))
(#t #f #t #f #t)

FemtoLispにReduce関数はありませんので（他のScheme処理系では標準ライブラリ等で用意されています）独自に定義します．利用方法は，Common Lispの独自定義例と同じです．

> (define (myreduce f L i) (if (null? L) i (f (car L) (myreduce f (cdr L) i))))
#fn(":000r3}\x8550g2;|}Me0|}Ng23342;" [myreduce] myreduce)

> (myreduce cons '(a b c) '(d e f g))
(a b c d e f g)

#備考

##登場した関数・記号
( ) 空白 ' car cdr cons defparameter . list equal if T NIL defun or and null mapcar #' funcall remove-if-not reduce append print

##記事に関する補足

• リスト処理＆再帰関数中心とするため，lambdaは出さないようにしました．setqとdefvarはどうしよう…．体験講座だから別にいいかな．
• 番外等にあるように，Common LISPに限らず，LISP系言語全般（RacketやPicoLispを含む）で体験できる内容なので，『LISPプログラミング一時間体験講座』でも良いかもとか．でも，方言や処理系による予約語・関数名の違いが結構あるし…うーん．
• とはいえ，ClojureとHyはこの記事で言うリスト構造がないので対象外かな．やはりドット対（コンスセル）が使えないと…．

##変更履歴

• 2020-08-27：まとめを追加
• 2020-08-27：応用例でFilter関数，Reduce関数の独自定義を追加
• 2020-08-26：FemtoLispの記号・関数の違いを整理
• 2020-08-25：Emacs Lispの記号・関数の違いを整理
• 2020-08-24：JDoodle利用例画像を追加
• 2020-08-24：記事に関する補足に追記（対応方言・処理系）
• 2020-08-23：Julia処理系組み込みのFemtoLispを用いた実行方法を追加
• 2020-08-23：GNU EmacsのEmacs Lisp対話モードでの実行方法を追加
• 2020-08-22：remove-ifではなくremove-if-notを使用した例に変更
• 2020-08-22：ドット対（コンスセル）の説明追加および連想リストの書き直し（コメントより）
• 2020-08-21：初版公開