なんだこれは

はてなダイアリーから移転しました。

clozure cl 1.9 on Macで遊んでいたら、Stack over flow した話

lisp

大きい数を計算できる、common lispで遊んでみることにした。

※この計算内容に意味はありません。

(defun f (n)
  (1+ n))

(defun b (m n)
  (cond ((<= m 0) (f n))
	((<= n 0) (b (1- m) 1))
	( t       (b (1- m) (b m (1- n))))))

これで、(b 4 4)を計算すると stack over flow になる。
スタックを減らすために計算結果をキャッシュできるようにメモ化してみた。

(defvar *table* (make-hash-table :test #'equal))

(defun b-memo (m n)
  (let* ((key (list m n))
	 (val (gethash key *table* nil)))
    (unless val
      (setf val (cond ((<= m 0) (f n))
		      ((<= n 0) (b-memo (1- m) 1))
		      ( t (let ((l (b-memo m (1- n))))
			    (b-memo (1- m) l)))))
      (setf (gethash key *table*) val))
    val))

それでもやっぱり (b-memo 4 4)で死ぬ。

しかたがないので、順番に進めていけば、メモを成長させるとうまくいくかも？

CL-USER> (b-memo 3 10)
8189
CL-USER> (b-memo 3 20)
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x3020026800DD>.
CL-USER> (b-memo 3 11)
16381
CL-USER> (b-memo 3 12)
32765
CL-USER> (b-memo 3 13)
65533
CL-USER> (b-memo 3 14)
131069
CL-USER> (b-memo 3 15)
Invoking restart: Retry SLIME REPL evaluation request.
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x3020026E2C8D>.
CL-USER> (b-memo 2 10000)
20003
CL-USER> (b-memo 2 20000)
40003
CL-USER> (b-memo 2 40000)
80003
CL-USER> (b-memo 2 80000)
160003
CL-USER> (b-memo 2 100000)
200003
CL-USER> (b-memo 2 200000)
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x3020037ADC2D>.
CL-USER> (b-memo 2 150000)
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x3020037A068D>.
CL-USER> (b-memo 2 125000)
250003
CL-USER> (b-memo 2 130000)
260003
CL-USER> (b-memo 2 150000)
300003
CL-USER> (b-memo 2 160000)
320003
CL-USER> (b-memo 2 170000)
340003
CL-USER> (b-memo 2 180000)
360003
CL-USER> (b-memo 2 190000)
380003
CL-USER> (b-memo 2 200000)
400003
CL-USER> (b-memo 2 210000)
420003
CL-USER> (b-memo 2 220000)
440003
CL-USER> (b-memo 2 240000)
480003
CL-USER> (b-memo 2 260000)
520003
CL-USER> (b-memo 2 290000)
580003
CL-USER> (b-memo 3 15)
262141
CL-USER> (b-memo 3 16)
524285
CL-USER> (b-memo 3 20)
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x30200563F2BD>.
CL-USER> (b-memo 3 18)
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x302005774A9D>.
CL-USER> (b-memo 3 17)
Invoking restart: Return to SLIME's top level.
; Evaluation aborted on #<CCL::STACK-OVERFLOW-CONDITION #x3020056319DD>.