I browsed through the NEWS file of CLisp and encountered that clisp does
tail recursion. So far so good.
When I tried the well-known ackermann function
(defun ack (m n)
(cond
((zerop m) (1+ n))
((zerop n) (ack (1- m) 1))
(t (ack (1- m) (ack m (1- n))))))
with the values (ackermann 3 8) in the top-level everything went fine
yet the compiled expression failed with a stack error:
*** - Program stack overflow. RESET
I was wondering as i read in the use-net, that compiled expressions take
less memory and are less stack consuming. And (ackermann 3 8) has a
maximum recursion depth of 2^(3+8)-1 which gives (only?) 2047 recursion
levels.
Anyway, can the ackermann function be properly tail-recursed?
(I asume that (t (ack (1- m) (ack m (1- n))) can not be properly
unnested, at least in clisp)
I run Clisp 2.28 on Windows. I know of editbin comming with Visual
Studio or uname -s in unix environments but appearantly, at leat for me,
there is stg. else going wrong.
Has anyone else encountered strange stack behaviour with clisp and a
hint for me?
PS: I know of (the) more advanced version of this function
(defun ackermann (m n)
(cond ((= m 0) (+ n 1))
((= m 1) (+ n 2))
((= m 2) (+ 3 (* n 2)))
((= m 3) (+ 5 (* 8 (- (expt 2 n) 1))))
(t (cond ((= n 0) (ackermann (- m 1) 1))
(t (ackermann (- m 1) (ackermann m (- n 1))))
))
))
beeing less stack consuming. I am just curious why it didn't worked out.
"Johann H�chtl" <········@bigfoot.com> wrote in message ·····················@bigfoot.com...
>>
> Anyway, can the ackermann function be properly tail-recursed?
No. The ackermann function is not primitive recursive.
(I think someone showed that being primitive recursive
is a necessary, but not sufficient criteria for being iterative.)
Johann H�chtl wrote:
> When I tried the well-known ackermann function
>
> (defun ack (m n)
> (cond
> ((zerop m) (1+ n))
> ((zerop n) (ack (1- m) 1))
> (t (ack (1- m) (ack m (1- n))))))
>
> with the values (ackermann 3 8) in the top-level everything went fine
> yet the compiled expression failed with a stack error:
>
> *** - Program stack overflow. RESET
>
> I was wondering as i read in the use-net, that compiled expressions take
> less memory and are less stack consuming. And (ackermann 3 8) has a
> maximum recursion depth of 2^(3+8)-1 which gives (only?) 2047 recursion
> levels.
>
> Anyway, can the ackermann function be properly tail-recursed?
All the self-calls in ACK are in tail position except for one:
the "inner" one in the final clause of the COND. Unfortunately,
that one gets called rather a lot. :-)
You're right that compiled code is likely to use less stack
than interpreted code. I don't know how stack-efficient CLISP
is.
For what it's worth, I just copied your definition of ACK
into a CLISP window, compiled it and asked for (ACK 3 8), and
it returned 2045 in under a second with no sign of trouble.
That's with CLISP 2.25.1 on a FreeBSD machine with a decent
amount of memory. If I don't compile it first, it takes about
12 times longer, but still completes happily.)
One daft suggestion. You wrote (ACKERMANN 3 8) above. Is it
possible that you have a function named ACK and another named
ACKERMANN, and you called, or compiled, the wrong one?
--
Gareth McCaughan ················@pobox.com
.sig under construc