[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.


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))
     (when (= b 0) (return z))
      (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))
         (rem (* base (expmod base (- exponent 1) modulus))

(defun square(x) (* x x))

reply via email to

[Prev in Thread] Current Thread [Next in Thread]