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 参考リンク

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である.

4.1 練習問題

  1. リスト (a () b) の長さはいくつか.
    (解答例)

    3

  2. リスト ((a b) c) の第1番目の要素は何か.
    (解答例)

    (a b)

5 Lispを使ってみる

ここでは,Emacs Lispを使って説明する.

Emacs上で実行するには, Buffersメニューから *scratch* バッファを選択し, 入力の最後に Ctrl-J をタイプすれば良い.

(+ 1 2) [Ctrl-J]
  3

このように,ユーザがシステムと対話しながらシステムを利用することから, このような使用形態は 対話的使用 と呼ばれる.

ユーザが入力する式は,一般的には

(関数名 式12 … 式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 練習問題

  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 練習問題

  1. menu の3番目の要素を求めるにはどうすればよいか.
    (解答例)
    (car (cdr (cdr menu)))
    
  2. menu の第1要素を juice に変更した リストを作るにはどうすればよいか.
    (解答例)
    (cons 'juice (cdr menu))
    
  3. menu の第1要素と第2要素の間に juice を挿入した リストを作るにはどうすればよいか.
    (解答例)
    (cons (car menu) (cons 'juice (cdr menu)))
    
  4. menu の第2要素を取り除いたリストを作るにはどうすればよいか.
    (解答例)
    (cons (car menu) (cdr (cdr menu)))
    
  5. 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 練習問題

  1. リストの2番目の要素と3番目の要素を交換したリストを求める関数 ex23 を定義せよ.
    ヒント: ex12 を利用することを考える.
    (解答例)
    (defun ex23 (x) (cons (car x) (ex12 (cdr x))))
    
  2. リストを左へ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つの数値の大小関係を調べる. string<, string= は 2つの記号の大小関係(アルファベット順)を調べる.
    (< 1 2)
      t
    (string< 'a 'b)
      t
    
  • atom は引数がアトム(記号あるいは数値)かどうかを調べる.
    (atom 1)
      t
    (atom 'a)
      t
    (atom '(a))
      nil
    (atom ())
      t
    

述語の判断結果によって,すなわち条件によって異なる値を返す関数を 作るには,関数 if を用いる.

(if 条件式 式12)

  • 条件式の結果が 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 練習問題

  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)))
    
  2. 与えられた西暦が グレゴリオ暦 でうるう年になるかどうかを判定する関数 leap_year を定義せよ. たとえば (leap_year 2000) の結果は t(leap_year 2100) の結果は nil である.
    (解答例)
    複数の解答例を示す.
    (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=0y%100=0y%400=0うるう年
    nilnilnilnil
    tnilnilt
    ttnilnil
    tttt
    (defun leap_year (y)
      (or (and (= (% y 4) 0) (> (% y 100) 0)) (= (% y 400) 0)))
    

    ある受講生は equal を使う方法を考えてくれた.その場合も簡潔に定義できる.素晴らしい!

  3. (and) の結果は何になると思うか.
    (解答例)
    t
    

    and の単位元は t とするのが自然である.

  4. (or) の結果は何になると思うか.
    (解答例)
    nil
    

    or の単位元は t とするのが自然である.

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 練習問題

  1. 関数 fact を変更して,1から n の和 1+2+…+n を 求める関数 sigma を定義せよ.
    (解答例)
    解答例を示す.
    (defun sigma (n)
      (if (= n 0) 0 (+ n (sigma (- n 1)))))
    
  2. 関数 fact を変更して,1から n の平方和 12+22+…+n2 を 求める関数 sigma2 を定義せよ.
    (解答例)
    解答例を示す.
    (defun sigma2 (n)
      (if (= n 0) 0 (+ (* n n) (sigma2 (- n 1)))))
    
  3. 次の漸化式で定義されるフィボナッチ数を計算する関数 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)))))
    
  4. リストの全要素の積を求める関数 prod を定義せよ.
    (解答例)
    解答例を示す.
    (defun prod (x)
      (if (null x) 1 (* (car x) (prod (cdr x)))))
    
  5. リストの中で一番大きい要素を求める関数 maxelem を定義せよ.
    ヒント:リストの長さが1の時は car が最大要素である. 長さが2以上の時は cdr の最大要素と car との大きい方が 最大要素である.
    (解答例)
    解答例を示す.
    (defun maxelem (x)
      (if (null (cdr x))
          (car x)
          (max (car x) (maxelem (cdr x)))))
    
  6. リストを逆順にしたリストを求める関数 rev を定義せよ.
    ヒント:空リストの逆順は空リストである. 空リストでないときは cdr の逆順と, car だけからなる長さ1のリストとを append したものが全体の逆順である.
    (解答例)
    解答例を示す.
    (defun rev (x)
      (if (null x)
          ()      
          (append (rev (cdr x)) (cons (car x) ()))))
    
  7. 第2引数のリストの要素として第1引数と同じ記号が現れるかどうか調べる 述語 mem を定義せよ. たとえば (mem 'a '(b a c)) の結果は t(mem 'a '(b (a) c)) の結果は nil である.
    ヒント:第2引数が空リストなら結果は nil である. 第2引数が空リストでないときは, 第2引数の car が第1引数と equal なら結果は tequal でないなら第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)))
    ) )
    
  8. ユークリッドの互除法 を用いて, 与えられた2つの正整数の最大公約数を求める関数 gcd を定義せよ.
    (解答例)
    解答例を示す.
    (defun gcd (m n)
      (if (= n 0)
          m
          (gcd n (% m n))))
    

Date: 2013-12-04 15:12:40 JST

Author: 田村直之

Validate XHTML 1.0