I'm currently playing a modified version of Hlavaty's trampoline function
which accepts functions with multiple parameters (
http://code.google.com/r/srborlongan-picolisp/source/browse/java/trampoline.l)
:
(de trampoline (F . @)
(let A (rest)
(use R
(loop
(NIL
(car (setq R (apply F A) ) )
(cdr R) )
(setq
F (car R)
A (cdr R) ) ) ) ) )
So far, I've successfully created test functions for mutual recursion,
factorial, fibonacci, and ackermann. Comments that precede function
definition are to be regarded as inspiration for said function.
(de even/t (N)
(if (=0 N)
(done T)
(continue odd/t (- N 1) ) ) )
(de odd/t (N)
(if (=0 N)
(done)
(continue even/t (- N 1) ) ) )
(de fact/t (N R)
(default
R 1)
(if (< N 2)
(done R)
(continue fact/t (- N 1)
(* R N) ) ) )
#
http://www.solutionsiq.com/resources/agileiq-blog/bid/72880/Programming-with-Groovy-Trampoline-and-Memoize
(de fib/t (N R S)
(default
R 1
S 1)
(if (< N 2)
(done R)
(continue fib/t (- N 1)
S (+ R S) ) ) )
#
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.
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.
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 use basic list
manipulation to replace what would have been continuous function unwrapping
in other languages.
Thus, should I really complain that ack/t uses a stack if it means that the
underlying bouncing principles are still maintained.
Unless, of course, if using stacks in this context is stupid in the first
place.
P. S.
I apologize for the length and relative lack of quality of this post.
I'm actually feeling quite sleepy (GMT +8).
The sleepier I get, the more hyperactive I get.
Thus, long post.
P.P.S.
DaanSystem's LispIDE is cool.
Samuel Dennis R. Borlongan
