Lisp 系の言語で繰り返しといえば、Scheme では named-let などの再帰定義、Common Lisp では dotimes, dolist, do やループマクロでしょうか。もちろん、Scheme の規格 R7RS にも do は規定されていますが、Common Lisp よりも使う機会は少ないように思います。今回は繰り返しにおける Common Lisp と Scheme の違いについて簡単に説明します。
Common Lisp には do と do* という繰り返しを行うためのマクロがあります。do と do* の違いは変数の初期化と更新処理を並列に行うか逐次的に行うかだけで、let と let* の違いとよく似ています。簡単な例を示しましょう。使用する処理系は SBCL (ver 2.0.1) です。
* (let ((x 0)) (do ((x 1 (1+ x)) (y x x)) ((< 5 x)) (print (list x y)))) (1 0) (2 1) (3 2) (4 3) (5 4) NIL * (let ((x 0)) (do* ((x 1 (1+ x)) (y x x)) ((< 5 x)) (print (list x y)))) ; ; ワーニング (省略) ; (1 1) (2 2) (3 3) (4 4) (5 5) NIL
do の場合、y の初期値は let で定義した x の値 0 になります。これに対し、do* の場合は do* で定義した x の初期値 1 が y の初期値になります。更新処理も同様です。do の場合、y の値は更新前の x の値となり、do* の場合は更新後の x の値となります。
これらのプログラムは下記のプログラムと同じ動作になります。
* (let ((x 0))
(let ((x 1) (y x))
(block nil
(tagbody loop
(if (< 5 x) (return))
(print (list x y))
(psetq x (1+ x) y x)
(go loop)))))
(1 0)
(2 1)
(3 2)
(4 3)
(5 4)
NIL
* (let ((x 0))
(let* ((x 1) (y x))
(block nil
(tagbody loop
(if (< 5 x) (return))
(print (list x y))
(setq x (1+ x) y x)
(go loop)))))
;
; ワーニング (省略)
;
(1 1)
(2 2)
(3 3)
(4 4)
(5 5)
NIL
do は let で変数の初期化を行い、psetq で変数の更新処理を行いますが、do* の場合は let* と setq で行うわけです。ここで psetq と psetf を簡単に説明しておきましょう。
Common Lisp の場合、代入を並行に行うマクロ psetq や psetf を使うと、テンポラリ変数を使わなくても値を交換することができます。
psetq symbol1 value1 symbol2 value2 ...
psetq はシンボル symbol1 に value1 を評価した結果を代入し、symbol2 に value2 を評価した結果を代入する、というように値を順番に代入します。このとき、psetq は setq と違って代入した値の影響をうけません。簡単な例を示します。
(setq x 100 y 200) => 200 x => 100 y => 200 (psetq x y y x) => nil x => 200 y => 100
psetq で x に y の値 200 を代入し、そのあとで x の値を y に代入しています。このとき x の値は 200 ではなく、代入される前の値 100 のままなのです。したがって、y に代入される値は 100 になります。
psetf は setf と同様に指定された場所へ値を代入しますが、setf と違って代入した値の影響をうけません。psetf は nil を返します。簡単な例を示します。
(setq board '(1 2 3 4)) => (1 2 3 4)
(psetf (nth 0 board) (nth 3 board)
(nth 3 board) (nth 0 board)) => nil
board => (4 2 3 1)
このように、psetq や psetf を使うと簡単に値を交換することができます。
Scheme の場合、Common Lisp の go のようなジャンプ命令がないので、do は letrec を使って定義するのが一般的です。簡単な例を示しましょう。使用する処理系は Gauche (ver 0.9.10) です。
gosh[r7rs.user]> (let ((x 0)) (do ((x 1 (+ x 1)) (y x x)) ((< 5 x)) (display (list x y))))
(1 0)(2 1)(3 2)(4 3)(5 4)#t
gosh[r7rs.user]> (let ((x 0))
(letrec ((iter (lambda (x y)
(cond ((>= 5 x)
(display (list x y))
(iter (+ x 1) x))))))
(iter 1 x)))
(1 0)(2 1)(3 2)(4 3)(5 4)#<undef>
Scheme の規格 R7RS に do* はありませんが、let* を使って同様な動作を行わせることは可能です。次のリストを見てください。
リスト : do* と同様の動作をするプログラム
(let ((x 0))
(letrec ((iter (lambda (x y)
(cond ((>= 5 x)
(display (list x y))
(let* ((x (+ x 1)) (y x))
(iter x y)))))))
(let* ((x 1) (y x))
(iter x y))))
let* で逐次的に変数の値を書き換えて、それを局所関数 iter に渡します。実行例を示します。
gosh[r7rs.user]> (let ((x 0))
(letrec ((iter (lambda (x y)
(cond ((>= 5 x)
(display (list x y))
(let* ((x (+ x 1)) (y x))
(iter x y)))))))
(let* ((x 1) (y x))
(iter x y))))
(1 1)(2 2)(3 3)(4 4)(5 5)#<undef>
今回は let* を使いましたが、set! で変数の値を破壊的に書き換えても同様の動作を実現することができます。
ところで 参考 URL によると、Common Lisp の do は変数の値を破壊的に書き換えるため、Scheme の do と動作が異なる場合があるとのことです。簡単な例を示しましょう。
gosh[r7rs.user]> (map (lambda (x) (x)) (do ((i 0 (+ i 1)) (a '())) ((< 4 i) a) (set! a (cons (lambda () i) a)))) (4 3 2 1 0)
do の本体でクロージャ (lambda () i) を生成してリストに格納します。Scheme の場合、do は再帰で実装されているので、繰り返すたびに変数 i の環境は新しく生成され、それがクロージャに保存されます。したがって、map でクロージャを評価すると (4 3 2 1 0) となります。
Common Lisp (SBCL) の場合は次のようになります。
* (mapcar #'(lambda (x) (funcall x)) (do ((i 0 (1+ i)) (a nil)) ((< 4 i) a) (push #'(lambda () i) a))) (5 5 5 5 5)
Common Lisp の do は変数 i の環境を 1 回だけ生成し、繰り返しのたびに i の値を破壊的に書き換えています。この場合、クロージャに保存される環境はみな同じものであり、その値を破壊的に書き換えているので、mapcar でクロージャを評価するとすべて同じ値 (5) になるわけです。ちなみに、SBCL は dotimes でも同じ結果になります。
* (let ((a nil)) (mapcar #'(lambda (x) (funcall x)) (dotimes (i 5 a) (push #'(lambda () i) a)))) (5 5 5 5 5) * (let ((a nil)) (mapcar #'(lambda (x) (funcall x)) (dolist (i '(1 2 3 4 5) a) (push #'(lambda () i) a)))) (5 4 3 2 1)
CLISP の場合、dolist も同じに結果になります。
> (let ((a nil)) (mapcar #'(lambda (x) (funcall x)) (dotimes (i 5 a) (push #'(lambda () i) a)))) (5 5 5 5 5) > (let ((a nil)) (mapcar #'(lambda (x) (funcall x)) (dolist (i '(1 2 3 4 5) a) (push #'(lambda () i) a)))) (5 5 5 5 5)
SBCL と CLISP では dolist の実装方法が異なっていると思われます。Common Lisp で繰り返し (do, do*, dotimes, dolist など) とクロージャを組み合わせて使う場合はご注意くださいませ。
それでは簡単な例題として、リストの総和を求める関数 sum-list を Common Lisp と Scheme で作ってみましょう。
リスト : 総和を求める
;;; Common Lisp 版
(defun sum-list (xs)
(do ((xs xs (cdr xs))
(a 0 (+ a (car xs))))
((null xs) a)))
;;; Scheme 版
(define (sum-list xs)
(let loop ((xs xs) (a 0))
(if (null? xs)
a
(loop (cdr xs) (+ a (car xs))))))
gosh[r7rs.user]> (sum-list '(1 2 3 4 5)) 15
* (sum-list '(1 2 3 4 5)) 15
apply (apply + xs, apply #'+ xs) や畳み込み (fold や reduce など) を使ったほうが簡単ですが、あえて繰り返しでプログラムしています。ここで仕様を変更して、負の要素があったら -1 を返すことにしましょう。Scheme 版は末尾再帰なので、簡単にプログラムすることができます。
リスト : 総和 (Scheme)
(define (sum-list1 xs)
(let loop ((xs xs) (a 0))
(cond ((null? xs) a)
((negative? (car xs)) -1)
(else (loop (cdr xs) (+ a (car xs)))))))
gosh[r7rs.user]> (sum-list1 '(1 2 3 -4 5)) -1
negative? でリストの要素 (car xs) が負かチェックして、そうであれば loop を再帰呼び出しせずに -1 を返すだけです。
Common Lisp で繰り返しから脱出する場合は return を使うと簡単です。
リスト : 総和 (Common Lisp)
(defun sum-list1 (xs)
(do ((xs xs (cdr xs))
(a 0 (+ a (car xs))))
((null xs) a)
(if (minusp (car xs))
(return -1))))
* (sum-list1 '(1 2 3 -4 5)) -1
Common Lisp の場合、do, dotimes, dolist などの本体は暗黙の block (タグは nil) に囲まれていて、return や return-from nil で繰り返しから脱出することができます。リストの要素 (car xs) が負ならば、(return -1) を評価して、繰り返しから脱出します。この場合、do の返り値は return の引数 (-1) になります。
次は、リストのリストを行列とみなして、行列の要素の総和を求める関数 sum-matrix を定義しましょう。sum-matrix は負の要素を見つけたら -1 を返します。
リスト : 行列の総和
;;; Scheme 版
(define (sum-matrix xs)
(let loop1 ((xs xs) (a 0))
(if (null? xs)
a
(let loop2 ((ys (car xs)) (b 0))
(cond ((null? ys)
(loop1 (cdr xs) (+ a b)))
((negative? (car ys)) -1)
(else (loop2 (cdr ys) (+ b (car ys)))))))))
;;; Common Lisp 版
(defun sum-matrix (xs)
(do ((xs xs (cdr xs))
(a 0))
((null xs) a)
(do ((ys (car xs) (cdr ys)))
((null ys))
(if (minusp (car ys))
(return-from sum-matrix -1)
(incf a (car ys))))))
gosh[r7rs.user]> (sum-matrix '((1 2 3) (4 5 6))) 21 gosh[r7rs.user]> (sum-matrix '((1 2 3) (4 -5 6))) -1
* (sum-matrix '((1 2 3) (4 5 6))) 21 * (sum-matrix '((1 2 3) (4 5 -6))) -1
Scheme 版は name-let で二重ループを実現しています。負の要素を見つけたら loop1 や loop2 を再帰呼び出しせずに -1 を返すだけです。Common Lisp の場合、関数の本体は暗黙の block (タグは関数名) で囲まれているので、(return-from sum-matix -1) を評価すれば二重ループを脱出して -1 を返すことができます。
Common Lisp の場合、block のタグはレキシカルスコープです。高階関数から return-from で脱出することができます。次のリストを見てください。
リスト : リストの総和
;;; Common Lisp 版
(defun sum-list11 (xs)
(reduce #'(lambda (a x)
(if (minusp x)
(return-from sum-list11 -1)
(+ a x)))
xs
:initial-value 0))
* (sum-list11 '(1 2 3 4 5 6)) 21 * (sum-list11 '(-1 2 3 4 5 6)) -1 * (sum-list11 '(1 2 3 4 5 -6)) -1
畳み込みを行う関数 reduce に渡すラムダ式の中で、要素 x が負ならば return-from で -1 を返します。タグ sum-list11 はレキシカルスコープなので、ラムダ式の中から参照することができ、return-from でそのブロックから脱出することができます。
また、return-from tag をラムダ式に包んで他の関数に渡すこともできます。この場合、渡されたラムダ式を実行すると、tag で指定した block から脱出することができるのです。次のリストを見てください。
リスト : 行列の総和
;;; Common Lisp 版
(defun sum-list2 (failure xs)
(do ((xs xs (cdr xs))
(a 0 (+ a (car xs))))
((null xs) a)
(if (minusp (car xs))
(funcall failure))))
(defun sum-matrix1 (xs)
(do ((xs xs (cdr xs))
(a 0 (+ a (sum-list2 #'(lambda () (return-from sum-matrix1 -1))
(car xs)))))
((null xs) a)))
* (sum-matrix1 '((1 2 3) (4 5 6) (7 8 9))) 45 * (sum-matrix1 '((1 2 3) (4 5 6) (-7 8 9))) -1
sum-matrix1 は行列 xs から 1 行ずつ取り出して sum-list2 に渡します。このとき、(return-from sum-matrix1 -1) を包んだラムダ式もいっしょに渡します。Common Lisp はレキシカルスコープなので、ラムダ式の中からタグ sum-matrix1 を参照することができます。
次に、sum-list2 でリストの要素が負の場合、渡されたラムダ式 failure を評価します。すると、制御は sum-matrix1 に戻って -1 を返すことができます。
この動作は Scheme の継続 (call/cc) による大域脱出とよく似ています。Scheme で同様のプログラムを作ると次のようになります。
リスト : 行列の総和 (Scheme)
(define (sum-list2 failure xs)
(let loop ((xs xs) (a 0))
(cond ((null? xs) a)
((negative? (car xs)) (failure -1))
(else (loop (cdr xs) (+ a (car xs)))))))
(define (sum-matrix1 xs)
(call/cc
(lambda (bk)
(let loop ((xs xs) (a 0))
(if (null? xs)
a
(loop (cdr xs) (+ a (sum-list2 bk (car xs)))))))))
gosh[r7rs.user]> (sum-matrix1 '((1 2 3) (4 5 6) (7 8 9))) 45 gosh[r7rs.user]> (sum-matrix1 '((1 2 3) (4 5 6) (7 -8 9))) -1
call/cc で継続を取り出して変数 bk にセットし、それを sum-list2 に渡します。sum-list2 では、要素が負であれば継続 failure を評価して -1 を返します。
Common Lisp と ISLisp は、catch, throw による例外処理をサポートしているので、block とラムダ式を使って大域脱出をプログラムすることはないでしょうが、高階関数などで処理を中断させたい場合、この方法を使うことができます。
Common Lisp では block のタグをレキシカルスコープで管理しますが、同様に tagbody と go のタグ (ジャンプ先) もレキシカルスコープで管理します。go をラムダ式に包んで他の関数に渡すこともでき、そのラムダ式を評価するとそのタグにジャンプすることができます。
簡単な例を示しましょう。
* (defun foo (x) (tagbody (let ((f #'(lambda () (go exit)))) (funcall x f) (print 1)) exit (print 2))) FOO * (foo #'(lambda (f) (funcall f))) 2 NIL * (foo #'(lambda (f) f)) 1 2 NIL
関数 foo の引数 x は関数で、その引数に go exit を包んだラムダ式を渡します。foo に渡す関数の中で引数 f を評価すると、go exit が実行されるので、tagbody のタグ exit に制御が移ります。したがって、(funcall x f) のあとの (print 1) は実行されません。
引数 f を評価しない場合、(print 1) が実行されて、そのあとに (print 2) が実行されます。なお、普通のプログラムで tagbody と go を使うことは滅多にありません。ましてや、このような使い方をすることはまずないと思います。tagbody と go を安易に使用してはいけません。くれぐれもご注意くださいませ。