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

[Camm Maguire]

Greetings!

Lou Glassy <address@hidden> writes:

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

This is an interesting example -- thanks!  I think we should get to
the bottom of why these differ.  Either the whole idea of static
stacks is problematical in such an instance, and unlikely case IMHO
which nevertheless would have terrible consequences, or you happen to
be triggering another example of a mysterious gcl bug arising from
memory corruption triggered by certain apparently random paths through
the code.  In addition to the example you cite below, other
observations in this category are

1. The miscompilation with gcc-3.0
2. The solve bug depending on the loop variable name
3. My own experiences with segfaults going away when tracepoints are
        set in gdb.  

I've added this to the bug task list on the website -- hopefully this
will help us remember to track this down.

Take care,

> 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