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

[Camm Maguire]

Greetings!

Matt Kaufmann <address@hidden> writes:

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

Yes, thanks for the reminder.  Am still waiting for a comprehensive
suggestion as to the size of the static stacks.  If we have none, then
I will just commit this *=4 on an ad hoc basis.

Take care,

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

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah