Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« bk1_to_amazon | トップページ | else 節のインデント »

2009-11-04

クォート付きリストの罠

マクロの魅力が知りたくて Common Lisp を勉強してます。

きっかけは「LET OVER LAMBDA」という本を買ったこと。
ポール・グレアム氏のコラム(「ハッカーと画家」)を読んで以来、
Lisp の知られざるパワーの源であるらしい「マクロ」の威力を
ぜひ知りたいと思っていたのですが、そのマクロのテクニックに関する本です。

しかし、この本、いわゆる「マクロ・ジェネレーティング・マクロ」の連続で、 Common Lisp に慣れていない身ではちんぷんかんぷん。 結局、4章で挫折しました・・・ -・- -・- -・- -・- Common Lisp の基礎はポール・グレアム氏の「ANSI Common Lisp」でおさらい したのですが、マクロに関してはごく基本的なことしか分からないまま。 というわけで、気を取り直して、今度は "On Lisp" にトライすることにしました!
せっかくなので、サンプルコードを xyzzy で打ち込んでみることに。 やっぱり手を動かすと理解が早い気がするのです。 で、まだマクロまでたどり着いていないのですが、 ユーティリティ関数のところでちょっとした罠にはまったので、 後学のためにもメモしておきます。 -・- -・- -・- -・- 図 4.2 (p.49) で "filter" という関数の定義が示されています。
(defun filter (fn lst) (let ((acc nil)) (dolist (x lst) (let ((val (funcall fn x))) (if val (push val acc)))) (nreverse acc)))
dolist でリストをなめながら途中経過を変数に蓄積して、 最後に結果を nreverse する、という定石コードになっています。 実行するとこんな感じ↓
> (filter #'evenp '(1 2 3 4 5)) (t t) > (filter #'oddp '(1 2 3 4 5)) (t t t) > (filter #'zerop '(1 2 3 4 5)) nil
これはこれでいいのですが、せっかくリストを一から作っているのに 最後に nreverse する手間がもったいない気がしてなりません。 # 単に Lisp に慣れていないだけかもしれませんが・・・ で、自分なりにコードを考えてみたのが次のコード↓
(defun my-filter-wrong (fn lst) (let ((acc '(nil))) (labels ((rec (lst tail) (if (null lst) (cdr acc) (let ((val (funcall fn (car lst)))) (cond (val (setf (cdr tail) (list val)) (rec (cdr lst) (cdr tail))) (t (rec (cdr lst) tail))))))) (rec lst acc))))
ところが、この関数を実行してみると、妙な挙動をします。
> (my-filter #'evenp '(1 2 3 4 5)) (t t) > (my-filter #'oddp '(1 2 3 4 5)) (t t t) > (my-filter #'zerop '(1 2 3 4 5)) (t t t)
zerop を指定すると nil が返るはずが、なぜか前回の結果が返ってきます。 変数 acc は let で作ったローカル変数のハズなのに、 なぜか状態が残ってしまっているようです。 しばらく悩んだのですが、この問題はまさに「On Lisp」の 3.3 章で 注意されていた罠でした。 正しいコードは以下の通り↓
(defun my-filter (fn lst) (let ((acc (list nil))) (labels ((rec (lst tail) (if (null lst) (cdr acc) (let ((val (funcall fn (car lst)))) (cond (val (setf (cdr tail) (list val)) (rec (cdr lst) (cdr tail))) (t (rec (cdr lst) tail))))))) (rec lst acc))))
つまり、let で代入している初期値が「クォート付きリスト」(p.38) なので、 その実体は関数定義時に生成されたインスタンスそのものになってしまい、 それに対する破壊的操作が「関数の内部状態」として残ってしまったのでした。 実は、元のコードは「関数がクォート付きリストを返すべきではない」という ルールを思いっきりやぶっているので、言ってみれば二重の意味でバグってます。 返値に破壊的操作を施すと関数の挙動が変わってしまいますし、 そもそも返値を引数にして評価するとエラーになってしまいます↓
> (let ((lst (my-filter-wrong #'evenp '(1 2 3 4 5)))) (my-filter-wrong #'zerop lst)) ★エラー★
これじゃ、参照透過性なんてあったもんじゃありません。 -・- -・- -・- -・- 今回の問題は Lisp 風のコードをC言語風(ポインタを直接扱うコード)に したのが直接の原因なので、そのうち Lisp な思考ができるようになれば 関係なくなるのかもしれませんが、「Common Lisp ってやっぱり難しいなぁ」 と改めて思ったのでしたー

« bk1_to_amazon | トップページ | else 節のインデント »