Re: Bouncing on trampolines (so cool...)
Hi all, I didn't bother with trampolines so far, but add some comments to On Thu, May 16, 2013 at 12:00:20AM +0800, Samuel Dennis Borlongan wrote: ... http://stackoverflow.com/questions/12186672/how-can-i-prevent-my-ackerman-function-from-overflowing-the-stack ... The bad thing with overflowing your stack is ... well, overflowing your stack. But you may as well overflow your heap, so nothing is gained. As it is recommended for PicoLisp anyway to set 'ulimit -s unlimited', the stack will use as much memory as is physically available, like the heap. The recursive version is usually faster than the one using an explicit stack, but uses perhaps a little bit more memory because each recursion level takes several stack lokations. Let's take the standard Ackermann function (de ack (M N) (cond ((=0 M) (inc N)) ((=0 N) (ack (dec M) 1)) (T (ack (dec M) (ack M (dec N ) ) Eliminating tail-recursion gives (de ack2 (M N) (loop (T (=0 M) (inc N)) (NIL (=0 N) (ack (dec M) (ack M (dec N (dec 'M) (one N) ) ) Both functions show roughly the same speed, : (bench (ack 4 1)) 249.465 sec - 65533 : (bench (ack2 4 1)) 252.487 sec - 65533 though the less-recursive function is slightly slower (as expected). If we go - as usually recommended - for the iterative version with an explict stack, (de ack3 (M N) (for (Stack (cons M) Stack) (if (=0 (setq M (pop 'Stack))) (inc 'N) (push 'Stack (dec M)) (if (=0 N) (one N) (push 'Stack M) (dec 'N) ) ) ) ) things get significantly slower: : (bench (ack3 4 1)) 312.028 sec - 65533 The fastest is - as expected and described - the cheating version: (de ack4 (M N) (for (Stack (cons M) Stack) (cond ((=0 (setq M (pop 'Stack))) (inc 'N)) ((= 1 M) (inc 'N 2)) ((= 2 M) (setq N (+ 3 (* 2 N (T (push 'Stack (dec M)) (if (=0 N) (one N) (push 'Stack M) (dec 'N) ) ) ) ) ) With that we get : (bench (ack4 4 1)) 0.000 sec - 65533 : (bench (length (ack4 4 2))) 0.981 sec - 19729 (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) Are you sure? Here I get : (bench (length (ack4 3 8000))) 0.018 sec - 2410 and even on my humble Netbook with a slow Atom CPU (pil32): : (bench (length (ack4 3 8000))) 0.213 sec - 2410 ♪♫ Alex Side note (though this doesn't really matter for the speed): It is never wise to use 'length' to detect short lists. Better replace (if (=0 (length R)) ..)with (if R ..) or (if (= (length R) 3) ..) with (if (cddr R) ..) to avoid possibly counting along long lists. -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Bouncing on trampolines (so cool...)
On Thu, May 16, 2013 at 01:33:54PM +0200, Alexander Burger wrote: : (bench (ack 4 1)) 249.465 sec - 65533 : (bench (ack2 4 1)) 252.487 sec - 65533 though the less-recursive function is slightly slower (as expected). Oops, forget that! Not as expected ... the opposite would be expected. But the values are very close anyway. ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Bouncing on trampolines (so cool...)
Re: side-note (bench (length (ack4 3 8000))) (32-bit Cygwin) 0.070 sec (bench (length (trampoline ack/t 3 8000))) (32-bit Cygwin) 2.010 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, before =0 and length invocation removal) 9.625 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, after =0 invocation removal) 4.981 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, after =0 and length invocation removal) 0.123 sec I therefore conclude that ack/t was programmed badly. My fault. Also, efficient programming in Ersatz apparently _relies_ on things that might speed up a little. Trampolines are still fun, though. New version: (de ack/t (M N R S) (default R '()) (if 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 (push 'R (- M 1) ) (continue ack/t M (- N 1) R T) ) ) ) Thanks for the comments! P.S. For the sake of context and gratuitous post-scripts, most of my work is done using Ersatz PicoLisp with LispIDE / Notepad++ on Windows workstations that run pre-release Java 8 and 108-tab Firefox. Again, thanks! Samuel Dennis R. Borlongan On Thu, May 16, 2013 at 7:33 PM, Alexander Burger a...@software-lab.dewrote: Hi all, I didn't bother with trampolines so far, but add some comments to On Thu, May 16, 2013 at 12:00:20AM +0800, Samuel Dennis Borlongan wrote: ... http://stackoverflow.com/questions/12186672/how-can-i-prevent-my-ackerman-function-from-overflowing-the-stack ... The bad thing with overflowing your stack is ... well, overflowing your stack. But you may as well overflow your heap, so nothing is gained. As it is recommended for PicoLisp anyway to set 'ulimit -s unlimited', the stack will use as much memory as is physically available, like the heap. The recursive version is usually faster than the one using an explicit stack, but uses perhaps a little bit more memory because each recursion level takes several stack lokations. Let's take the standard Ackermann function (de ack (M N) (cond ((=0 M) (inc N)) ((=0 N) (ack (dec M) 1)) (T (ack (dec M) (ack M (dec N ) ) Eliminating tail-recursion gives (de ack2 (M N) (loop (T (=0 M) (inc N)) (NIL (=0 N) (ack (dec M) (ack M (dec N (dec 'M) (one N) ) ) Both functions show roughly the same speed, : (bench (ack 4 1)) 249.465 sec - 65533 : (bench (ack2 4 1)) 252.487 sec - 65533 though the less-recursive function is slightly slower (as expected). If we go - as usually recommended - for the iterative version with an explict stack, (de ack3 (M N) (for (Stack (cons M) Stack) (if (=0 (setq M (pop 'Stack))) (inc 'N) (push 'Stack (dec M)) (if (=0 N) (one N) (push 'Stack M) (dec 'N) ) ) ) ) things get significantly slower: : (bench (ack3 4 1)) 312.028 sec - 65533 The fastest is - as expected and described - the cheating version: (de ack4 (M N) (for (Stack (cons M) Stack) (cond ((=0 (setq M (pop 'Stack))) (inc 'N)) ((= 1 M) (inc 'N 2)) ((= 2 M) (setq N (+ 3 (* 2 N (T (push 'Stack (dec M)) (if (=0 N) (one N) (push 'Stack M) (dec 'N) ) ) ) ) ) With that we get : (bench (ack4 4 1)) 0.000 sec - 65533 : (bench (length (ack4 4 2))) 0.981 sec - 19729 (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) Are you sure? Here I get : (bench (length (ack4 3 8000))) 0.018 sec - 2410 and even on my humble Netbook with a slow Atom CPU (pil32): : (bench (length (ack4 3 8000))) 0.213 sec - 2410 ♪♫ Alex Side note (though this doesn't really matter for the speed): It is never wise to use 'length' to detect short lists. Better replace (if (=0 (length R)) ..)with (if R ..) or (if (= (length R) 3) ..) with (if (cddr R)
Re: Bouncing on trampolines (so cool...)
Hi Samuel, (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, before =0 and length invocation removal) 9.625 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, after =0 invocation removal) 4.981 sec (bench (length (trampoline ack/t 3 8000))) (64-bit Ersatz on Java 8, after =0 and length invocation removal) 0.123 sec Thanks! Interesting, I wouldn't have expected the effect be so big. The stacked list in 'R' must be very long then. ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Bouncing on trampolines (so cool...)
On Thu, May 16, 2013 at 04:33:49PM +0200, Alexander Burger wrote:
though the less-recursive function is slightly slower (as expected).
Oops, forget that! Not as expected ... the opposite would be expected.
But the values are very close anyway.
One more oops!!
Though it doesn't matter much for the speed, I just noticed that 'ack2'
was wrong! It recursed on 'ack' instead of itself ('ack2').
So for the records, this is the corrected version:
(de ack2 (M N)
(loop
(T (=0 M) (inc N))
(NIL (=0 N) (ack2 (dec M) (ack2 M (dec N
(dec 'M)
(one N) ) )
♪♫ Alex
--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Bouncing on trampolines (so cool...)
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
