初めての人のためのLISP (第6講-第7講)

初めての人のためのLISP[増補改訂版]のメモです.
最初:初めての人のためのLISP (第1講-第5講) - もうカツ丼でいいよな

第6講 またも再帰するから再帰なのだ(p.82-)

関数による例が多いので長め.

リストの長さ

次の関数lengthにより定義されるものをリストの長さとする.

(defun length(x)
       (cond ((null x) 0)       ;; 空リストの長さは0
             (t (1+ (length (cdr x)))))) ;; 自身のcdrの長さに1を足したものがそのリストの長さ
  • cdrを順にとっていったとき,carに現れるS式をトップレベルの要素と呼ぶ
  • リストの長さはトップレベルの要素数に等しい
  • 上記定義ではアトムの長さは求められない(アトムのcarやcdrはエラーになる)
リストから指定の要素を取り出す

次の関数nthはリストxのn番目の要素を返す.

(defun nth (n x)
       (cond ((< n 0) (error 'illegal-argument 'nth n x)) ;; nが負の場合はエラー
             (t (nth2 n x))))
(defun nth2 (n x)
       (cond ((null x) (error 'overrun 'nth n x)) ;; nが要素の長さを超えたときはエラー
             ((= n 0) (car x))  ;; nが0の場合はcar(第0要素)を返す
             (t (nth2 (1- n) (cdr x))))) ;; nが1以上の場合はnとリストの長さを1減らして再帰呼び出し
  • nilのcarはエラー,nilのcdrはnilとする
    • nilのcarをとるような場合はプログラムのミスを疑うべき
アトムの個数

atom-countはリスト中のアトムの個数を返す.

(defun atom-count (x)
       (cond ((null x) 0)               ;; nilは数えない
             ((atom x) 1)               ;; xがアトムなら1
             (t (+ (atom-count (car x)) ;; carに含まれるアトムの個数と
                   (atom-count (cdr x)))))) ;; cdrに含まれるアトムの個数を足す
  • (x)などのアトムの個数が2になってしまうのでnilはカウントしない
  • (() x)に含まれるアトムの個数は1で良いのか?
    • carに出現するnilはカウントしなくていいのか?

carに出現するnilをアトムとしてカウントする*1

(defun my-atom-count (x)
       (cond ((null x) 0)
             ((atom x) 1)
             ((null (car x)) (1+ (my-atom-count (cdr x))))
             (t (+ (my-atom-count (car x))
                   (my-atom-count (cdr x))))))
(atom-count '((nil a) nil b))   ;; => 2
(my-atom-count '((nil a) nil b));; => 4
再帰を用いたプログラムのコツ
  1. 最も簡単なケース,自明なケースについて直接答えを書き下す
  2. そうでない場合,問題を一段だけ簡単な問題(例えばリストの長さを1減らす)に帰着できないか考える
  3. 一段簡単な問題に帰着したとき,問題の構造が以前と同様ならば再帰法が使用できる
  4. 与えられた問題を順々に簡単な問題へ帰着していったとき,最終的に必ず自明なケースにたどり着くことを確認する(負数の扱いなどに注意)
S式は再帰的構造を持つ

S式とは何かを再度確認

  1. アトムはS式である
  2. 0個以上並べたS式を括弧でくくったものはS式である

以下も同義

  1. nilはリストである
  2. S式とS式をconsしたものはリストである
  3. nil,アトム,リストはS式である
リストの連結

2つのリストを繋げた新しいリストを返すappend.

(defun append (x y)
       (cond ((null x) y)
             (t (cons (car x) (append (cdr x) y)))))
  • yはそのまま
  • xの最後の要素から順にconsしていく

例えば(append (a b) (c d))は次のように展開される.

(append '(a b) '(c d))          ;; => (a b c d)
;;; 以下の式と同じ
(cons 'a (cons 'b '(c d)))      ;; => (a b c d)
  • appendの第2引数をnilにすると第1引数に与えたリストのコピーが得られる
    • (append x (append y))とするとyもコピーされる
    • それぞれトップレベルの要素をconsしていくだけなので,厳密な意味でのコピーではない

すべての要素をコピーする関数copyは次のように定義

(defun copy (x y)
       (cond ((atom x) x)
             (t (cons (copy (car x))
                      (copy (cdr x))))))
リストの逆転

与えられたリストのトップレベルの要素を逆転したリストを返す関数reverse

(defun reverse (x) (rev2 x nil))
(defun rev2 (x y)
       (cond ((null x) y)       ;; xの要素が無くなったら終了
             (t (rev2 (cdr x) (cons (car x) y))))) ;; xのcarをyにcons
  • yにはxのcarがリストの先頭方向へ向かって付け加えられていく
  • xのcarが取れなくなったとき,yには逆転したxが入っている
  • ここでのyのような変数を累積変数と呼ぶ
末尾再帰

appendやcopyは最後に自分自身を呼び出す際,その呼出の結果をconsしている.つまり,自分自身の呼び出しがそのまま最終結果になっているわけではない.
一方,rev2は自分自身の呼び出しがそのまま最終結果になっている.
そのまま最終結果となるような再帰呼び出しのことを末尾再帰と呼ぶ.
末尾再帰は繰り返し処理(第7講で説明)に変換できる.

第7講 go, go, go..., do, do, do..., loop, loop, loop..., やっぱりOは丸い(p.100-)

いわゆる「繰り返し」の話

特殊形式prog

普通に考えるとリストの長さを求めるのに再帰など使わない.次のように考えるのが自然.

  1. カウンターを0にセット
  2. リストが空ならカウンターの値を返す
  3. リストを元のリストのcdrにし,カウンターを1増やして2に戻る

初期のLispに用意されていたprogという形式を用いると次のように書ける.

(defun length (x)
       (prog (count)            ;; prog中だけで使う変数の宣言
             (setq count 0)
        loop (cond ((null x) (return count)))
             (setq x (cdr x))
             (setq count (1+ count))
             (go loop)))

prog形式は次の形式を持つ.

(prog 変数宣言
      [名前1] 文1
      [名前2] 文2
      ...
      [名前n] 文n)
  • 変数宣言で宣言した変数はprog内のみで有効であり,またsetqにより何度も値が書き換えられることを前提としている
  • 変数宣言は省略できないので必要がなければ()を指定する
    • 変数の初期値は通常nilになる
  • [名前]はgoタグと言い,goの飛び先を示す.必要がなければ省略できる.
  • returnを使うとprogの途中から抜け出せる

progは次の機能を統合した特殊形式といえる.

  1. ある範囲でのみ使える変数の宣言
  2. go
  3. return
  4. 不定個の式を上(左)から順に評価する

prog自体は現在でも使えるものの,progの機能がそれぞれ独立して与えられるようになったため,progが使われることは殆どなくなった(cf. prog - cadr - Seesaa Wiki(ウィキ)).

progn

progの4つの機能のうち4はprognという独立した形式として与えられている.

(progn 式1 式2 ... 式n)

prognは与えられた式を左から順に評価していき,式nの結果を返す.
cond節の帰結部はprognと書かなくてもprognであると解釈され,暗黙のprognと呼ばれる.

do

lispで使われる繰り返しの特殊形式

(do ((変数1 [初期値1 [ステップ1]])
     (変数2 [初期値2 [ステップ2]])
     ...
     (変数n [初期値n [ステップn]]))
    (条件 [出口 ...])
    本文1
    本文2
    ...
    本文m)
  1. 変数1〜nを初期値1〜nで初期化する(省略時はnil)
  2. 条件を評価し,真ならば[出口 ...]に書かれたS式を順に実行し,結果を返して終了(省略時はnilが返る)
  3. 条件が偽のとき,本文1〜mのS式を順に評価
  4. 変数1〜nの値をステップ1〜nの評価結果に更新(ステップ省略時はなにもしない)
  5. 2に戻る

(cf. Common Lisp 入門)
doを用いると関数lengthを次のように記述できる.

(defun length (x)
       (do ((count 0 (1+ count))) ;; 初期値0,繰り返しごとに1増加
           ((null x) count)       ;; xがnilなら終了
           (setq x (cdr x))))     ;; 繰り返しごとにxを1つ短くする

次のように本文なしでも記述できる.

(defun length(x)
       (do ((count 0 (1+ count)) 
            (lst x (cdr lst)))  ;; 初期値x,繰り返しごとに1つ短くする
           ((null lst) count))) ;; lstが空になったら終了
andとor
(and P1 P2 ... Pn)

(cond (P1 (cond (P2 ... (cond (Pn t)) ...))))

とほぼ同じ意味で,条件式が全て真(非nil)の時真になる.返り値はPnの値であることが多い.

(or P1 P2 ... Pn)

(cond (P1 t) (P2 t) ... (Pn t))

とほぼ同じ意味で,条件式のうち一つでも真があればそこで評価を終了して真になる.返り値は真になった条件式Piの値を返すことが多い.

*1:これはテキスト中における「読者への宿題」で,テキストには「関数を2種類用意するとよい」と書いてある.2種類用意する方法がパッと思い付かない…