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

[Matt Kaufmann]

Hi --

Yes, what you say makes sense.  However, in the particular case that prompted
my email to Camm Maguire, multplication of the stacks by 4 (by executing (setq
si::*multiply-stacks* 2) twice) solved the problem.  I was emboldened to try
this because in Allegro CL there was no stack overflow.

-- Matt Kaufmann
   From: Lou Glassy <address@hidden>
   CC: address@hidden, address@hidden, address@hidden
   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))