(defstruct btree (key nil) (value nil) (left nil) (right nil))とすると、4つの要素を持つ構造体が定義される。さらに以下のような 関数が自動的に生成される。
struct btree {
char *key;
int value;
struct btree *left;
struct btree *right;
}
Cでは、このような構造体に対して、b.key や b-> key などの
構文でアクセスするのであった。
(defun btree-insert (key value tree)
(if (null tree)
(setf tree (make-btree :key key :value value))
(cond
((string < key (btree-key tree))
(if (btree-left tree)
(btree-insert key value (btree-left tree))
(setf (btree-left tree) (make-btree :key key :value value))))
((string > key (btree-key tree))
(if (btree-right tree)
(btree-insert key value (btree-right tree))
(setf (btree-right tree) (make-btree :key key :value value))))
((string= key (btree-key tree))
(setf (btree-value tree) value)))))
(defun btree-walk (tree &optional (q nil))
(if (null tree) q
(btree-walk (btree-left tree)
(cons (list (btree-key tree) (btree-value tree))
(btree-walk (btree-right tree) q)))))
このプログラムは、以下のように使う。
(setf x (make-btree :key 'kono :value 150 ))
(btree-insert 'takara 90 x)
(btree-insert 'ochi 200 x)
(btree-insert 'yonesu 20 x)
Pure Lisp のプログラムと違って、btree-insert という関数の
値はあまり意味がない。その代わり、変数xの値が変化する。
このようなプログラムを副作用中心のプログラムという。問: このプログラムと以前のtree-insertのプログラムを 比べた利点と欠点を考察せよ。
(defun tree-insert (key value tree)
(if (null tree)
(list (cons key value) nil nil)
(let ((here (car tree))
(left (cadr tree))
(right (caddr tree)))
(cond ((string < key (car here))
(list here (tree-insert key value left) right))
((string > key (car here))
(list here left (tree-insert key value right)))
((string= key (car here))
(list (cons key value) left right))))))
副作用を持つプログラミングも以下のように考えれば、入力と 出力の組合せで表された関数と考えることができる。
入力、関数実行前の変数の値 から 出力、関数実行後の変数の値 への関数したがって、副作用を持つ関数を使ったプログラミングでは関数の 実行順序が重要である。例えば、
(f (g a) (h b) (i c))という関数呼出を考えよう。これを、
(setf z (i c)) (setf y (h b)) (setf x (g a)) (f x y z)というように実行しても、i,h,g に副作用が無ければ、実行結果に 変わりはない。しかし、i,h,g に副作用がある時は、結果が異なる 場合もある。
もし、遅延実行という技術を使うと、Pure LISPの実行順序を、 極めて自由に設定することができる。例えば上の例で f を 一番先に実行するということも可能になる。この性質を並列 計算機に応用したり、計算可能な範囲を理論的に広げたり する研究が行なわれている。(が、あまり実用化は進んでいない)
ただし、以下のような技術がCommon LispやCでも重要である。
一般的に、副作用が無いプログラムの方が安全なプログラムだという ことはできる。しかし、副作用の無いプログラムは実は長い引数 を持つ関数を必要とすることが多く、複雑なプログラム技術を 必要とすることも多い。
副作用のあるプログラムは、実行順序ごとに分けて細かく プログラムされることが多い。defstruct などのサポート があることもあり、Common Lispではこちらのプログラミング が中心である。しかし、defstruct を多用するとプログラム 自身は複雑になることが多い。
(defun integer-list (i)
(if (> i 0)
(cons i (integer-list (- i 1)))
nil))
(defun sum-up (list)
(if (null list) 0
(+ (car list) (sum-up (cdr list)))))
これを、(sum-up (integer-list 100)) などとすれば、1から100
までの和を求めることができる。この方法は、まず、integer-list
が決まった数のリストを生成して、その和を計算する方法である。
逆に、いくつ数を生成するかは考えずに、例えば30000を越える まで足し合わせたいとしよう。こういう場合は、整数の 生成を足し合わせる方から要求すれば良い。これは要求駆動 と呼ばれる実行方法となる。要求駆動はco-routine を使って 実現することができる。
(defun integer-generator (n)
(list n #'(lambda () (integer-generator (+ n 1))))
(defun sum-until (sum limit now)
(if (> sum limit) sum
(let ((next (funcall (second now))))
(sum-until (+ sum (first next)) limit next))))
(sum-until 0 50 (integer-generator 0))
このプログラムは、integer-generator と sum-until という
二つのプロセスが並行に動作していると考えることもできる。
実際、並列Lispなどを使えば、このようなプログラムは
簡単に記述することができる。また、integer-generator の返す値のsecondは、次に返す 値を生成するルーチンを返していると考えることもできる。 これを、integer-generator の継続(continuation)と呼ぶ。 このようにcontinuation を使ってお互いを呼び合うような プログラミングをco-routineという。
問: 1,4,9,16 という整数の2乗の和が最初に1000を越える 値を計算するプログラムを要求駆動型に記述せよ。 問: このプログラムはわざわざfuncallなどを使っているが、 integer-generator をsum-until 内蔵にすれば、もっと簡単に なる。そのような sum-integer-until という関数を書いて見よ。 sum-integer-until と sum-until, integer-generator の組み合わせ の二つのプログラムの利点と欠点について考察せよ。