「対話によるCommon Lisp入門」第６話まとめノート

本章ではリスト処理を行う関数を再帰を使って書く練習をしながら，関数の処理時間の見積もり方と最適なコードのへの書き換え方を学ぶ．本ページではまず第５話と６話の間に挿入されたLispのコンパイル方法と，第６話で説明されている関数のトレースの仕方についてまとめ，その後，処理時間の見積もり方と，効率的なコードへの書き換えについてまとめる．

Lispのコンパイル方法

REPLで作業をしている時，定義済みの関数や外部ファイルに書かれたプログラムをコンパイルする方法についてまとめる．

関数ごとのコンパイル

fooという名の関数を定義したら，REPLで(compile 'foo)を実行すると関数単位でコンパイルされる．コンパイルされている関数とされていない関数が混在しても問題なく動作する．当然コンパイル済みの関数は早く動く．

(defun foo ....)
(compile 'foo)

slimeを使っている場合，「C-c C-c」でカーソル位置のトップレベルをcomplileする．この場合出力はない．

ファイル単位でのコンパイル

ファイルの内容をすべてコンパイルするにはファイル名を指定して(compile-file "foo.lisp")でコンパイルした後，拡張子を省略したファイル名でプログラムをロードする．

(compile-file "foo.lisp")
(load "foo")

slimeでは「C-c C-k」でバッファ全体（ファイル）をcompileする．

逆アセンブル

コンパイラが変換した機械語は，disassemble関数で逆アセンブルすることができる．

(defun foo .....)
(compile 'foo)
(disassemble 'foo)

slimeでは定義した関数のシンボル上で「C-c M-d (slime-disassemble-symbol)」を実行すると，一時バッファに逆アセンブルした結果が表示される．

関数処理のトレース

trace関数を使うと関数に入る時と出る時の情報が表示される．組込み関数をtraceの引数に渡すとエラーが出るが，自分で定義した関数なら問題ない．

> (defun length$ (lst)
     (length-loop lst 0))
> (defun length-loop (lst count)
     (if (null lst) count
         (length-loop (cdr lst) (+ count 1))))
> (trace length$)      ; length$関数のトレース開始
> (length$ '(a b c))
  0: (LENGTH$ (A B C))
  0: LENGTH$ returned 3
3
> (trace length-loop)  ; length-loop関数のトレース追加
> (length$ '(a b c))
  0: (LENGTH$ (A B C))
    1: (LENGTH-LOOP (A B C) 0)
      2: (LENGTH-LOOP (B C) 1)
        3: (LENGTH-LOOP (C) 2)
          4: (LENGTH-LOOP NIL 3)
          4: LENGTH-LOOP returned 3
        3: LENGTH-LOOP returned 3
      2: LENGTH-LOOP returned 3
    1: LENGTH-LOOP returned 3
  0: LENGTH$ returned 3
3
> (untrace)     ; 全関数のトレース終了．
T

計算時間の見積もり方

オーダー記法と同様，データのサイズに対しどれ位のオーダーで処理時間が増加していくかに興味があるため，以下の方法で見積もる．

データの長さnに比例しない一定時間処理は，何ステップかかっても１と数える．
car, car, cons, null, +, -, *, / 等の基本関数は一定時間で実行できると考える．
長さnのデータ（リスト）に比例してかかる計算時間はnと数える．
同様に長さn^2のデータ（リスト）に比例してかかる計算時間はn^2で数える．

例）リストの長さを求めるlength$関数の計算時間の見積もり．

(defun length$ (lst)
   (length-loop lst 0))
(defun length-loop (lst count)
   (if (null lst) count
       (length-loop (cdr lst) (+ count 1))))

2行目のlength-loopの呼び出し，4行目のnull判断，最終行のlength-loopに渡す引数準備計算は全てリストの長さに依存しないので一定時間と考え，計算時間は合わせて１とカウントする．
リストlstのcdr部分を渡して再帰処理しているlength-loopは引数の長さに依存して処理が決まる．リストの長さnに依存して決まるlength-loopの計算時間を$T(n)$で表すと，一定時間の処理と合わせて，$T(n) = 1 + T(n-1)$で表せる．$T(0)$はnullテストだけで処理時間は１であることを考慮すると以下を得る．

length$の一定時間処理と合わせても定数処理時間は１とカウントするので，length$の処理時間は$1+n$である．

定数時間はいくら合わせても１とする理由は，データ数（リスト長）が増加して行った時，どれくらいのオーダーで処理時間が増えるかに興味があるからだ．結局，length$関数はリスト長nに比例して計算時間が増加していくことを示している．

`append`の処理時間

appendの処理時間を考えるためにappend$を実装してみる．

(defun append$ (lst1 lst2)
   (if (null lst1) lst2
       (cons (car lst1) (append$ (cdr lst1) lst2))))

lst1の長さnだけappend$が再帰的に呼び出されるのでappend$の処理時間はnの関数になる．これを$T(n)$とおくと，2行目のifのテストと3行目の(cons (car lst1)部分は一定時間なので1，再帰呼び出しは$T(n-1)$となるので，$T(n)$は以下を満たす．

\[ \begin{align} T(n) = 1 + T(n-1) \end{align} \]

上式右辺に再帰的に$T(0)$まで代入し，$T(0) = 1$を用いて解くか，以下のように解けば，$T(n) = 1 + n$を得る．

効率的な`reverse`の実装．

リストの要素を逆順に並び替えるには，先頭要素を取り出して，残りの要素を再帰的にreverseで並び替えて，その後ろに最初に取り出した先頭要素を加えれば良い．この時，appendで両者をつなげるか，consで繋げるかで実行時間が変わってくる．先ほど計算したようにappendの計算時間は要素の長さnに比例するが，consなら一定時間で処理できる．

まず，悪い例を挙げて，実際に計算時間を求めてみる．

(defun reverse1 (lst)
   (if (null lst) nil
       (append (reverse1 (cdr lst)) (list (car lst)))))

appendは第１引数の長さに比例するのでn-1の時間がかかる．また，appendに渡す第１引数の準備でreverse1自身がn-1の長さで呼び出される．他の処理は全て一定時間なので１とする．以上を合わせると，reverse1の処理時間$T(n)$は以下を満たす．

従ってreverse1を用いた実装では$n^2$に比例した時間がかかる．

次は良い例． appendではなく一定時間でリスト操作するconsを使う．

(defun reverse2 (let)
   (reverse-loop lst nil))
(defun reverse-loop (lst reversed)
   (if (null lst) reversed
       (reverse-loop (cdr lst)
		     (cons (car lst) reversed))))

この場合の処理時間は，$T(n) = 1 + T(n-1)$になるので，appendの処理時間の計算と同じで，$T(n) = 1 + n$となる．

計算効率に関する教訓

リストの長さnに比例する関数を入れ子にしない！
appendよりconsやlistを使う！

`eq`, `eql`, `equal`の違い

包含関係でいくと$\text{eq}\subset\text{eql}\subset\text{equal}$で，eqで真を返す関係は他の2つでも真となり，eqlで真となる関係はequalでも真となる．すなわち，左から「等しさ」基準が厳しい順に並んでいると考えてよい．

eq—メモリ上で等しいオブジェクトならTを返す．シンボルが同じかどうかをテストする時はこれを使う．Javaオブジェクトの==比較と同じ．
eql—アトムの値が等しければTを返す．数値の場合は型も同じでなければ等しいとはみなされない． Javaのequals()と似ている．
equal—リストの見かけが同じならばTを返す．

シンボルが同じなら同じメモリ上のアドレスを指すので，当然シンボルの値も等しいし，見かけも等しいので，eqでTならeqlでもequalでもTである．

ちなみに=は数値が等しいかどうかを判定するときに使う．==じゃない点に注意！

述語関数

`真偽を返す述語関数が幾つか紹介された．

atom
consp
listp
symbolp
numberp
integerp
null

連想配列

「carがキーでcdrが値とみなしたリスト」から成るリストを連想配列（association list, alist）と呼ぶ．

(assoc キー alist)で連想配列alisの先頭（左）から探して最初に見つかるキーの要素を返す．

`sublis`関数

(sublis alist lst)でlst内のアトムを連想配列内の値と置き換える．

CL-USER> (sublis '((first-name . 太朗)
                   (last-name . 鈴木)
                   (telno . 03-432-323))
                 '((last-name first-name) tel telno))

((鈴木 太朗) TEL |03-432-323|)