Lispプログラミング入門
Table of Contents
1 Lispの概要
- 1957年頃に米国MITのJohn McCarthyらにより開発された
- LISt Processor (リスト処理言語)の省略で, AIプログラム等の記述・開発に適している
- 多数の方言が存在するが,標準版として1984年に Guy L. Steele Jr. が中心となってCommon Lispを設計した
- Lisp言語の一種であるSchemeも広く用いられている
- Clojureという新しい言語も出ている
1.1 参考リンク
- An Introduction to Programming in Emacs Lisp
- On Lisp
- 初めての人のためのLISP (Amazon, OPAC)
- Scheme
- The Scheme Programming Language (Amazon, OPAC)
- プログラミング言語SCHEME
(Amazon)
The Scheme Programming Languageの日本語訳 - Structure and Interpretation of Computer Programs (SICP)
(Amazon, OPAC)
大変有名な教科書 - 計算機プログラムの構造と解釈
(Amazon, OPAC)
SICPの日本語訳 (HTML版) - Gaucheプログラミング(立読み版) (at Karetta)
- Clojure
- プログラミング言語論
- 神戸大学工学部システム工学科第4講座で開発された計算機
- 神戸大学Lispマシン,Prologマシンなどを紹介
2 Lispの特徴
- 記号処理言語 , リスト処理言語
-
データとして,記号(シンボル)を取り扱うことができる. また,リストと呼ばれる可変長のデータの列を取り扱うことができる.
- 関数型言語
-
Lispでは新たな関数を定義することによってプログラムを作り上げていく. すなわち,Lispのプログラムは関数定義の集まりである. LispやPrologは,FORTRANやBASICなどの手続き型言語とは異なり, 非手続き型言語と呼ばれる.
- 対話的使用 , 会話形使用
-
Lispシステムの使用形態は対話的である. すなわち,ユーザはLispシステムを立ち上げたあと, システムと会話するような形で命令を与え, 関数を定義したり実行したりできる.
3 記号
Lisp, Prologなどの言語では, 記号 (シンボル,symbol)をデータとして取り扱うことができる. 記号を取り扱える言語は 記号処理言語 と呼ばれることがある.
記号処理言語はデータとして数値だけしか取り扱えない言語に比較して, より自然に問題を表現できる.
記号は英数字等を1文字以上続けた名前で表される.ただし,数値として
見なされるもの ( 123
, +1
など)は省く.
X coffee B52 - N-Tamura
英字の大文字と小文字は区別しない. いくつかのLispシステムでは漢字も使用できる.
記号および数値は アトム (atom)と呼ばれる.
4 リスト
Lisp, PrologなどのAI用言語では,記号や数値の列を データとして取り扱うことができる.
この列は リスト (list)と呼ばれる. リストは,その 要素 (element)を空白で区切って並べたものを カッコでくくって表す.たとえば
(jan 31 1957 thu) (pi 3.14)
であり,一般的には
(要素1 要素2 … 要素n)
と書く.
- リストの要素の個数 n は,そのリストの 長さ (length)と呼ばれる. 前の例では,リストの長さはそれぞれ4と2である.
- 要素i をリストの 第i要素 (i-th element)と呼ぶ.
たとえば,最初の例での第3要素は
1957
である. - 要素のないリスト(長さが0のリスト)は 空リスト (empty list)と呼ばれる.
空リストは記号
nil
で表すこともできる.() nil
- リストの要素が,またリストであってもよい.
(coffee milk (orange juice)) ((a (b) (c (d))) (e () f))
上の例でのリストの長さはそれぞれ3と2である.
5 Lispを使ってみる
ここでは,Emacs Lispを使って説明する.
Emacs上で実行するには,
Buffersメニューから *scratch*
バッファを選択し,
入力の最後に Ctrl-J
をタイプすれば良い.
(+ 1 2) [Ctrl-J] 3
このように,ユーザがシステムと対話しながらシステムを利用することから, このような使用形態は 対話的使用 と呼ばれる.
ユーザが入力する式は,一般的には
(関数名 式1 式2 … 式n)
という 関数 (function)の形である.
- 式i は 引数 (argument) と呼ばれる.
引数が,また式であってもよい.
たとえば,関数 log sin 1 の値は次のようにして計算できる.
(log (sin 1)) -0.1726038
- リストを引数とする関数も使用できる. リストを引数とする場合には,リストの前に クォート (引用符,クォーテションマーク,quotation mark)をつける.
- たとえば,
(length '(coffee milk (orange juice))) 3 (length '((a (b) (c (d))) (e () f))) 2
ここで,
length
はリストの長さを求める関数である. +
,*
,log
,length
などのように, Lispシステムであらかじめ用意されている関数は 組込関数 (built-in function)と呼ばれる.
5.1 練習問題
- 与えられた2つのリストの長さの合計を求めるにはどうすればよいか.
- (解答例)
- たとえば以下のようにする.
(+ (length '(a b c)) (length '(d e)))
6 変数
関数 setq
を使うと,記号に値を代入できる.
(setq x (* 12 34)) 408 (+ x 56) 464 (setq menu '(tea coffee milk)) (tea coffee milk) (length menu) 3 (setq x (length menu)) 3
一般的には
(setq 変数 値)
と書く.変数としては任意の記号,値としては任意の式が書ける.
7 リスト処理関数
数多くあるリストを処理する組込関数のうち,いくつかを紹介する.
append
は2つのリストを連結したリストを求める関数である. なお空リスト()
はクォートを省いてもよい.(append '(a b) '(c d)) (a b c d) (append '(a (b c)) '(d () e)) (a (b c) d () e) (append '(a b c) '()) (a b c) (append () '(a b c)) (a b c)
reverse
はリストの要素を逆順に並べ変えたリストを求める関数である.(reverse '(a b c d)) (d c b a) (reverse '(a (b c) d)) (d (b c) a)
sort
はリストを一定の順序(昇順,降順,アルファベット順など)に したがって並べ変えたリストを求める関数である.(sort '(3 1 4 2) '<) (1 2 3 4) (sort '(3 1 4 2) '>) (4 3 2 1) (sort '(tamura banbara kumamoto) 'string<) (banbara kumamoto tamura)
これらの関数は,以下で述べるような より基本的な関数の組合せで作られている.
8 基本リスト処理関数
- 先頭要素を求める関数
car
- 残りのリストを求める関数
cdr
- 先頭に要素を加えたリストを作る関数
cons
8.1 先頭要素を求める関数 car
関数 car
はリストの先頭の要素(第1要素)を求める.
(car '(a b c)) a (car '((a b) (c d))) (a b) (setq menu '(tea coffee milk)) (tea coffee milk) (car menu) tea
8.2 残りのリストを求める関数 cdr
関数 cdr
はリストの先頭の要素を除いた
残りのリスト(第2要素以降のリスト)を求める.
(cdr menu) (coffee milk) (cdr (cdr menu)) (milk) (cdr (cdr (cdr menu))) nil (car (cdr menu)) coffee
(car (cdr menu))
でmenu
の第2要素を求めることができる.
8.3 先頭に要素を加えたリストを作る関数 cons
関数 cons
は,
第1引数を第2引数のリストの前につけたリストを求める.
(cons '(a b) '(c d)) ((a b) c d) (cons 'cocoa menu) (cocoa tea coffee milk) (cons 'cocoa (cdr menu)) (cocoa coffee milk)
(cons '(a b) '(c d))
の結果は((a b) c d)
で,(append '(a b) '(c d))
の結果(a b c d)
とは異なることに注意する.- 第2引数がリストでない場合も
cons
を実行することは可能だが, リストでないデータ構造が得られる. 詳しくは Lispのデータ構造 を参照.
リストに対する基本的な操作は,
以上の car
, cdr
, cons
の3つの関数で行える.
8.4 練習問題
menu
の3番目の要素を求めるにはどうすればよいか.- (解答例)
-
(car (cdr (cdr menu)))
menu
の第1要素をjuice
に変更した リストを作るにはどうすればよいか.- (解答例)
-
(cons 'juice (cdr menu))
menu
の第1要素と第2要素の間にjuice
を挿入した リストを作るにはどうすればよいか.- (解答例)
-
(cons (car menu) (cons 'juice (cdr menu)))
menu
の第2要素を取り除いたリストを作るにはどうすればよいか.- (解答例)
-
(cons (car menu) (cdr (cdr menu)))
menu
の第1要素と第2要素を交換したリストを作るにはどうすればよいか.- (解答例)
-
(cons (car (cdr menu)) (cons (car menu) (cdr (cdr menu))))
9 関数定義
Lispでは既存の関数を用いて,新たな関数を自分で定義することができる.
たとえば,引数として与えられた
リストの2番目の要素を求める関数 nibanme
は,
関数 defun
を使って次のようにして定義する.
(defun nibanme (x) (car (cdr x))) nibanme (nibanme '(a b c)) b
一般的には
(defun 関数名 (仮引数1 … 仮引数n) 関数本体)
と書く.
このように定義した関数は, Lispシステムにすでにある組込関数と同様に使用できる.
以下では,リストの2番目の要素を取り除いたリストを求める
関数 del2
を定義し,それと関数 nibanme
を用いて,
リストの1番目の要素と2番目の要素を交換したリストを求める関数
ex12
を定義する.
(defun del2 (x) (cons (car x) (cdr (cdr x)))) (defun ex12 (x) (cons (nibanme x) (del2 x))) (del2 '(a b c)) (a c) (ex12 '(a b c)) (b a c)
実は,Lispでは以下のような組込関数があらかじめ用意されている.
(defun caar (x) (car (car x))) (defun cadr (x) (car (cdr x))) (defun cdar (x) (cdr (car x))) (defun cddr (x) (cdr (cdr x)))
9.1 練習問題
- リストの2番目の要素と3番目の要素を交換したリストを求める関数
ex23
を定義せよ.
ヒント:ex12
を利用することを考える.- (解答例)
-
(defun ex23 (x) (cons (car x) (ex12 (cdr x))))
- リストを左へ1つ回転させたリストを求める関数
rotate
を定義せよ. たとえば(rotate '(a b c d))
の結果は(b c d a)
である. 与えられるリストの長さは1以上としてよい.
ヒント:(a b c d)
から(b c d a)
を得るには,(append '(b c d) '(a))
と考える.append
の第2引数はリストでなければならない.(cons 'a ())
とすれば長さ1のリスト(a)
が得られることを用いる.(append '(b c d) '(a))
ではなく(cons '(b c d) '(a))
とすると, 結果が((b c d) a)
となり(b c d a)
にはならないことに注意する.- (解答例)
-
(defun rotate (x) (append (cdr x) (cons (car x) ())))
10 述語と条件
Lispのある種の関数は条件判断を行うためのもので,
特に 述語 (predicate)と呼ばれる.
述語は判断の結果が真ならば t
を,偽ならば nil
を返す.
null
は引数が空リストかどうか調べる述語である.(null ()) t (null 'a) nil (null nil) t (null '(a)) nil
=
は2つの引数が同一の数値であるかどうか調べる述語である.(= 1 2) nil (= 2 (+ 1 1)) t (= 'a 'b) ERROR
equal
は2つの引数が同一の記号やリストであるかどうか調べる述語である. 数値の場合も利用できる.(equal 'a 'b) nil (equal 'a (car '(a b))) t (equal '(b) (cdr '(a b))) t (equal 2 (+ 1 1)) t
(null x)
と(equal x ())
は同じ意味である./=
は2つの数値が等しくない時に真になる(/= x y)
と(not (= x y))
は同じ意味である.<
,>
,<=
,>=
は2つの数値の大小関係を調べる.string<
,string=
は 2つの記号の大小関係(アルファベット順)を調べる.(< 1 2) t (string< 'a 'b) t
atom
は引数がアトム(記号あるいは数値)かどうかを調べる.(atom 1) t (atom 'a) t (atom '(a)) nil (atom ()) t
述語の判断結果によって,すなわち条件によって異なる値を返す関数を
作るには,関数 if
を用いる.
(if 条件式 式1 式2)
- 条件式の結果が
nil
以外なら 式1 の計算結果を,nil
の時は 式2 の計算結果を値とする(if (null 'a) 1 2) 2 (setq x '(a b)) (a b) (if (>= (length x) 2) (car (cdr x)) x) b
if
を使うと,2つの数値の大きい方を返す関数ookiihou
を定義できる.(defun ookiihou (x y) (if (> x y) x y)) (ookiihou 3 7) 7
組込関数
max
を利用すると同じことが行える.and
,or
,not
で,複数の述語の結果を組合せる論理演算を行える.
10.1 練習問題
- 2つの数値を要素とする長さ2のリストを昇順に並べ変えたリストを
求める関数
sort2
を定義せよ. たとえば(sort2 '(3 2))
の結果は(2 3)
,(sort2 '(2 3))
の結果は(2 3)
である.- (解答例)
- 複数の解答例を示す.
(defun sort2 (x) (if (< (car x) (cadr x)) x (ex12 x))) (defun sort2 (x) (if (< (car x) (cadr x)) x (cons (cadr x) (cons (car x) nil)))) (defun sort2 (x) (cons (min (car x) (cadr x)) (cons (max (car x) (cadr x)) nil)))
- 与えられた西暦が グレゴリオ暦 でうるう年になるかどうかを判定する関数
leap_year
を定義せよ. たとえば(leap_year 2000)
の結果はt
,(leap_year 2100)
の結果はnil
である. なおyをxで割った余りは(% y x)
で求められる.- (解答例)
- 複数の解答例を示す.
(defun leap_year (y) (if (= (% y 4) 0) (if (= (% y 100) 0) (if (= (% y 400) 0) t nil) t) nil)) (defun leap_year (y) (if (= (% y 400) 0) t (if (= (% y 100) 0) nil (if (= (% y 4) 0) t nil)))) (defun leap_year (y) (if (= (% y 400) 0) t (if (= (% y 100) 0) nil (= (% y 4) 0))))
if ではなく and, or を利用して定義すればさらに簡潔になる. その場合,以下のような真理値表を元に考えると良い.
y%4=0 y%100=0 y%400=0 うるう年 nil nil nil nil t nil nil t t t nil nil t t t t (defun leap_year (y) (or (and (= (% y 4) 0) (> (% y 100) 0)) (= (% y 400) 0)))
ある受講生は equal を使う方法を考えてくれた.その場合も簡潔に定義できる.素晴らしい!
(and)
の結果は何になると思うか.- (解答例)
-
t
and の単位元は t とするのが自然である.
(or)
の結果は何になると思うか.- (解答例)
-
nil
or の単位元は nil とするのが自然である.
11 再帰的定義
数学では,定義の中に自分自身が現れることがある. たとえば n の階乗は次のように定義される. \begin{eqnarray*} n! & = & \left\{ \begin{array}{ll} 1 & (n=0) \\ n\times (n-1)! & (n\geq1) \end{array} \right. \end{eqnarray*} このように定義の中に自分自身が現れる定義を, Lispでは 再帰的定義 (recursive definition)と呼ぶ.
たとえば,階乗を求める関数 fact
は次のように定義できる.
1: (defun fact (n) 2: (if (= n 0) 1 (* n (fact (- n 1)))))
(fact 10) 3628800
リストの要素の合計を求める関数 sum
は次のように定義できる.
1: (defun sum (l) 2: (if (null l) 0 (+ (car l) (sum (cdr l)))))
(sum '(1 9 8 9)) 27
2つのリストを連結したリストを求める関数 app
は次のように定義できる.
1: (defun app (x y) 2: (if (null x) 3: y 4: (cons (car x) (app (cdr x) y))))
(app '(a b) '(c d)) (a b c d)
実は,この関数は append
と同じことを行う.
11.1 練習問題
- 関数
fact
を変更して,1から n の和 1+2+…+n を 求める関数sigma
を定義せよ.- (解答例)
- 解答例を示す.
(defun sigma (n) (if (= n 0) 0 (+ n (sigma (- n 1)))))
- 関数
fact
を変更して,1から n の平方和 12+22+…+n2 を 求める関数sigma2
を定義せよ.- (解答例)
- 解答例を示す.
(defun sigma2 (n) (if (= n 0) 0 (+ (* n n) (sigma2 (- n 1)))))
- 次の漸化式で定義されるフィボナッチ数を計算する関数
fib
を定義せよ. \begin{eqnarray*} fib(n) & = & \left\{ \begin{array}{ll} n & (n<2) \\ fib(n-1)+fib(n-2) & (n\geq 2) \end{array} \right. \end{eqnarray*}- (解答例)
- 解答例を示す.
(defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
- リストの全要素の積を求める関数
prod
を定義せよ.- (解答例)
- 解答例を示す.
(defun prod (x) (if (null x) 1 (* (car x) (prod (cdr x)))))
- リストの中で一番大きい要素を求める関数
maxelem
を定義せよ.
ヒント:リストの長さが1の時はcar
が最大要素である. 長さが2以上の時はcdr
の最大要素とcar
との大きい方が 最大要素である.- (解答例)
- 解答例を示す.
(defun maxelem (x) (if (null (cdr x)) (car x) (max (car x) (maxelem (cdr x)))))
- リストを逆順にしたリストを求める関数
rev
を定義せよ.
ヒント:空リストの逆順は空リストである. 空リストでないときはcdr
の逆順と,car
だけからなる長さ1のリストとをappend
したものが全体の逆順である.- (解答例)
- 解答例を示す.
(defun rev (x) (if (null x) () (append (rev (cdr x)) (cons (car x) ()))))
- 第2引数のリストの要素として第1引数と同じ記号が現れるかどうか調べる
述語
mem
を定義せよ. たとえば(mem 'a '(b a c))
の結果はt
,(mem 'a '(b (a) c))
の結果はnil
である.
ヒント:第2引数が空リストなら結果はnil
である. 第2引数が空リストでないときは, 第2引数のcar
が第1引数とequal
なら結果はt
,equal
でないなら第2引数のcdr
について調べる.- (解答例)
- 解答例を示す.
(defun mem (x y) (if (null y) nil (if (equal x (car y)) t (mem x (cdr y))))) (defun mem (x y) (if (null y) nil (or (equal x (car y)) (mem x (cdr y))) ) )
- ユークリッドの互除法 を用いて,
与えられた2つの正整数の最大公約数を求める関数
gcd
を定義せよ.- (解答例)
- 解答例を示す.
(defun gcd (m n) (if (= n 0) m (gcd n (% m n))))