[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: |
Camm Maguire |
Subject: |
Re: [Gcl-devel] Re: Invocation history stack size for GCL |
Date: |
21 Mar 2002 11:51:12 -0500 |
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