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:[email protected]?subject=Unsubscribe
