Hi Samuel,

> (de trampoline (F . @)

good idea, that looks better than having to pass the arguments as a
list.

> # 
> http://stackoverflow.com/questions/12186672/how-can-i-prevent-my-ackerman-function-from-overflowing-the-stack
>
> (de ack/t (M N R S)
>   (default R '())
>   (if (> (length R) 0)
>     (unless S
>       (setq M (pop 'R) ) )
>     (push 'R M) )
>   (cond ((=0 (length R) ) (done N) )
>         ((= M 0) (continue ack/t M (+ N 1) R) )
>         ((= M 1) (continue ack/t M (+ N 2) R) )
>         ((= M 2) (continue ack/t M (+ (* N 2) 3) R) )
>         ((= N 0) (continue ack/t (- M 1) 1 R T) )
>         (T
>           (push 'R (- M 1) )
>           (continue ack/t M (- N 1) R T) ) ) )
>
> Honestly, I hate my Ackermann implementation, not because its
> performance is bad ( (trampoline ack/t 3 8000) takes 1.970 sec and
> 10.287 sec in 32-bit and ersatz, respectively), but because I have
> had a nagging suspicion that there must something better than using a
> stack rather than a plain atom for storing intermediate values.

The Ackermann function can't be implemented using a constant space loop
so you need some kind of non-trivial storage.

> One problem for me is that the other solution that has been presented
> involves making the continue function return functions instead of
> lists, which would mean I would have to rewrite the trampoline
> function.

I'm not sure what you mean.  Picolisp functions _are_ lists.  And the
'continue' function in fact returns functions (together with the
arguments that will be applied in the next iteration).

> That's the thing: Hlavaty's trampoline function is too gosh darn
> _elegant_ for me to rewrite. I mean, seriously, the way it manages to

Thank you for the compliment;-) I would like to blame picolisp for the
elegance:-D

> Thus, should I really complain that ack/t uses a stack if it means
> that the underlying bouncing principles are still maintained.

What happens with the Ackermann is that in order to avoid stack overflow
(which happens by implicitly allocating storage on the C stack) you make
the allocation explicit and move it from the C stack to the picolisp
heap.

> Unless, of course, if using stacks in this context is stupid in the
> first place.

It's not stupid, it's necessary.

Some stylistic suggestions:

(de ack/t (M N R S)
  (when R
    (unless S
      (setq M (pop 'R)) )
    (push 'R M) )
  (cond ((not R) (done N))
        ((= M 0) (continue ack/t M (+ N 1) R))
        ((= M 1) (continue ack/t M (+ N 2) R))
        ((= M 2) (continue ack/t M (+ (* N 2) 3) R))
        ((= N 0) (continue ack/t (- M 1) 1 R T))
        (T (continue ack/t M (- N 1) (cons (- M 1) R) T)) ) )

Note, I haven't tested your function, only changed some visual stuff:-)

Good luck!

Tomas
-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to