[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Gcl-devel] Re: Invocation history stack size for GCL
From: |
Lou Glassy |
Subject: |
Re: [Gcl-devel] Re: Invocation history stack size for GCL |
Date: |
Fri, 08 Mar 2002 12:33:57 -0700 |
A small side-note about the Invocation history stack...
(This is a maybe.)
If you write tail-recursive Lisp code, and if GCL cannot
figure out it's tail-recursive, then ***ZOT*** I think you get
an overflow on the invocation history stack - too many functions
in the middle of execution at the same time.
In the example below, I would get invocation history stack overflow
when running expmod-rec, but not with expmod-iter. The overflow problem may
be related to the glitch I found with EVENP, but my spider-sense
is telling me it's probably more related to tail-recursion elimination,
or the lack thereof.
So - I am wondering if increasing stack sizes will just postpone some
bugs, rather than fixing them. If GCL's ability to do tail-recursion
elimination is the same as the gcc compiler's, then some programs will
still make the new (larger-stack-equipped) GCL croak.
Just a thought.
-lou
Example of iterative vs tail-recursive code. The former works in
GCL 2.4.0, the latter slags with a invocation history stack overflow.
;;; do modular exponentiation - get (B**E) mod M.
;;; general driver
(defun expmod (base exponent modulus)
(expmod-iter base exponent modulus))
;;; iterative algorithm (aye, matey, this be bletcherous)
(defun expmod-iter (x b n)
(let ((z 1)
(b b)
(x x))
(loop
(when (= b 0) (return z))
(loop
(when (not (= (rem b 2) 0)) (return))
(setf b (/ b 2))
(setf x (rem (* x x) n)))
(setf b (- b 1))
(setf z (rem (* z x) n)))))
;;; tail-recursive algorithm from SICP
(defun expmod-rec (base exponent modulus)
(cond ((= exponent 0) 1)
((evenp exponent)
(rem (square (expmod base (floor (/ exponent 2)) modulus))
modulus))
(t
(rem (* base (expmod base (- exponent 1) modulus))
modulus))))
(defun square(x) (* x x))