Re: [Gcl-devel] Re: Invocation history stack size for GCL

[Lou Glassy]

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))