オーバーフローする flatten
エントリータイトル変更しました。
「オーバーフローしない」-->「オーバーフローする」
●On Lisp の flatten はスタック溢れを起す
(defun flatten-a (lis) (labels ((rec (x acc) (cond ((null x) acc) ((atom x) (cons x acc)) (t (rec (car x) (rec (cdr x) acc)))))) (rec lis nil)))
我が家の環境 (Ubuntu10.04LTS + Clozure CL) だと要素数 ５万３千強でスタックが溢れる。下から２行目の右側の rec 再帰呼出しは返却値をそのまま返さず、他の関数に引数として渡している。しかし実は「他の関数」ではなく、渡している先はこれまた rec なので、これはこれでやっぱり末尾再帰のような気がする。
でも、スタックが溢れる。
※訂正:上記の cond 式の最後の行の２つ rec は、左側だけが末尾再帰扱いのようです。
そもそも Common Lisp では末尾再帰の最適化は仕様に無いらしいけど、でも実際は最適化してくれる処理系もあるとかなんとか...。どっちなんだ。
ぐーぐる先生で調べてみると、こんな記事を見付けた。
でも、この記事のコメントを見ると、"ちゃんと末尾再帰になっているように見えます" と Shiro さんが書いている。うーん、やはり最適化されると思ってよいのか...な...？
●スタック溢れしない flatten は無いのか？
再びぐーぐると、こんなのがあった。
2009-02-12 今日も Emacs Lisp @ cocoatomo衝動日記より
(defun flatten2 (tree) (reverse (flatten-rec tree nil))) (defun flatten-rec (tree stack) (if tree (if (atom tree) (cons tree stack) (flatten-rec (cdr tree) (flatten-rec (car tree) stack))) stack))
この flatten は要素数 100万のリストでもスタック溢れを起すことなく処理してくれる。ということはやはり末尾再帰最適化は行われているということかな。
試みに on Lisp のコードと何が違うのか調べるためコードを変形してみて、驚いた。
;; On Lisp のコード (defun flatten-a (lis) (labels ((rec (x acc) (cond ((null x) acc) ((atom x) (cons x acc)) (t (rec (car x) (rec (cdr x) acc)))))) (rec lis nil))) ;; cocoatomo さんのコードを変形したもの (defun flatten-b (lis) (labels ((rec (x acc) (cond ((null x) acc) ((atom x) (cons x acc)) (t (rec (cdr x) (rec (car x) acc)))))) (reverse (rec lis nil))))
再帰関数 rec の形は両者ともほとんど同じ。違うのは cond 式の最後の二重再帰呼出しの (car x) と (cdr x) が入れ替っているだけ。たったこれだけの違いで、スタック溢れを回避できている。残念ながらこの理由は、今の僕には理解できない...。
※訂正：flatten-b も末尾再帰ではない。対象リストのネストが深ければスタックオーバーフローになる。
●蛇足。私の書いた flatten
On Lisp の flatten がスタック溢れを起すと知って私が書いたのはこれでした。
(defun flatten-c (lis) (flet ((iter (x acc) (cond ((null x) acc) ((atom x) (cons x acc)) (t (append (flatten-c x) acc))))) (reduce #'iter lis :initial-value nil :from-end t)))
reduce です。高階関数万歳。
Common Lisp には reduce-back も、 reduce-right もありませんが、キーワード引数 :from-end で reduce が右畳込み関数になるんですね。Common Lisp らしいところでしょうか。他にも :start :end で畳込む範囲まで指定できます。そんなの使う場面が思い浮びませんが。
ところでこの reduce 版 flatten も変則的な再帰をしてるように見えます。flatten-c は reduce を call し、reduce が iter をコールして、iter が flatten-c を callしてます。
flatten-c --> reduce --> iter --> flatten-c --> reduce --> iter --> ...
しかも iter の中の flatten-c 呼出しは末尾再帰の形になっていません。戻値を append にわたしています。
でも、これスタック溢れしないです。
reduce を介することで、単なる再帰呼出とは違うメモリ割当になってるんでしょうか...これもよくわからない。
※訂正：残念ならがこれも flatten-b 同様 スタック溢れます。明らかに末尾再帰ではないので当然ですが...
● 追記
よくよく考えたら、flatten-c と、 flatten-a, b は再帰するタイミングが異っているような気がします。flatten-c も再帰がかさむようなリストに適用すれば、やはりスタック溢れを起すように思えます。
あとで確認する。
● 追記２
確認した。
結論から言うと
テスト用コード
(defun make-flat-list (n) (loop for x from 1 to n collect x)) (defun make-deep-list (n) (let ((lis 'a)) (dotimes (k n lis) (setq lis (list lis))))) (defun test1 (n flatten) (time (progn (funcall flatten (make-flat-list n)) t))) (defun test2 (n flatten) (time (progn (funcall flatten (make-deep-list n)) t)))
結果
(test1 100000 #'flatten-a) ;=> オーバーフロー (test1 100000 #'flatten-b) ;=> OK (test1 100000 #'flatten-c) ;=> OK (test2 100000 #'flatten-a) ;=> OK (test2 100000 #'flatten-b) ;=> オーバーフロー (test2 100000 #'flatten-c) ;=> オーバーフロー
flatten-a はネストの深いリストに対して有効だが、要素数が多いリストには弱い。
flatten-b,c は要素数が多いリストに対して有効だが、ネストの深いリストには弱い。
結局、次のような再帰の形は末尾再帰とは言えない。
(labels ((rec (x acc) ... (rec ... (rec ...))))
多重再帰している rec のうち、左側は末尾再帰であり ClozureCL では最適化される。しかし右側の再帰はやはり非末尾再帰扱いのようです。flatten-a は car部の再帰処理が末尾再帰で cdr部の再帰処理は非末尾再帰だったわけです。そのため cdr が深くなるフラットなリストでオーバーフローし、 car部が深くなるディープなリストに強かった。 flatten-b は、car と cdr の記述が逆だったので性質も正反対だった、というわけです。
