Lisp HUG Maillist Archive

WG: Ack function hanging LWL 4.4

> -----Ursprüngliche Nachricht-----
> Von: owner-lisp-hug@lispworks.com
> [mailto:owner-lisp-hug@lispworks.com] Im Auftrag von Sean Ross
> Gesendet: Dienstag, 1. März 2005 09:20
> An: lisp-hug@lispworks.com
> Betreff: Ack function hanging LWL 4.4 
> 
> 
> 
> Hi,
> 
> I've run across a problem when running the following ack
> function on LWL 4.4
> 
> (defun ack (m n)
>   (declare (fixnum n m) (values fixnum)
>            (optimize (speed 3) (debug 0) (safety 0)))
>   (cond
>    ((zerop m) (1+ n))
>    ((zerop n) (ack (1- m) 1))
>    (t (ack (1- m) (ack m (1- n))))))
> 
> (compile 'ack)
> 
> 
> Running (ack 3 10) causes the editor the hang
> indefinitely (or it at least seems that way).
> 
> Running (ack 3 10) in a console image ends up
> in the return value being printed out but then
> the image dies without an error.
> 
....
> 
> I'm assuming that the (safety 0) declaration is involved in
> this, but with safety > 0 a stack overflow error is signalled.
> 
> I've also noticed the same thing happening when computing
> factorials using a naive algorithm. Is it possible to get 
> this to work while keeping the recursive algorithm or is this a known 
> limitation?
> 
> 
> Thanks, 
>   Sean.
> 
....

Sean,

obviously your recursion needs a lot of stack space. Here especially I
would re-think the recursion. I deleted the declare form and ran you
function on (ack 3 3) from the listener.

This already triggers a "Recursive stack overflow" error. Now you can
increase stack space as described in
http://www.lispworks.com/documentation/lw44/CLWUG-W/html/clwuser-w-368.h
tm#pgfId-864137

With this setting stack size to 64K you are able to calculate (ack 3 6)
- with some noticeable execution time. (ack 3 7) will again trigger
"Recursive stack overflow". This is why I think you have to re-think
your recursion. Small numbers already require enormeous stack size.

It is not a good idea to set safety to 0. Of course error checking is
reduced to the minimum in this case. Your code does not consider stack
space and thus in this respect is not free of errors. Errors don't go
away just because you close your eyes :)


Andreas



Updated at: 2020-12-10 08:53 UTC