Re: Tail call optimization
On Sun, Feb 09, 2025 at 11:32:38PM -0800, Lindsay Lawrence wrote: > In trying to compare tco vs recur for my own use I came up with > the following: > ... Nice examples, thanks a lot! I'd like to point out, however, that recursion and tail call optimization are not fully equivalent. We always need to keep that in mind! The original idea of TCO (not the 'tco' function in PicoLisp) is to avoid that calling the very last function in a function does 1. first push the current address on the stack 2. call that last function 3. pop the return address 4. return from the current function Instead, the code can just *jump* to that last function. This is done by e.g. Scheme, and indeed is faster and avoids growing the stack with each iteration. This optimization is done by the compiler, which modifies the program flow. For the simple case of a single recursive function calling itself: (de f (N) (if (=0 N) (printsp 'OK) (printsp N) (f (dec N)) ) ) : (f 3) 3 2 1 OK -> OK this results in a *loop* and an assignment instead of a real *call*: (de f (N) (loop (T (=0 N) (printsp 'OK)) (printsp N) (setq N (dec N)) ) ) : (f 3) 3 2 1 OK -> OK (for mutually recursive functions it is the same principle) PicoLisp is an interpreter, and performing such code modifications would be extremely inefficient. But for PicoLisp (I think Scheme doesn't even address such issues), there are also other implications. The above example has the call to 'f' only in the body of a single 'if' expression. But what if you have more complicated nestings? Consider this silly but simple example: (de f (N) (finally (printsp N) (out "file" (if (=0 N) (printsp 'OK) (f (dec N)) ) ) ) ) The recursion in the last line properly nests the 'finally' and 'out' calls, closing the output file and executing the 'finally' clause upon each return. We cannot simply jump from the last line of 'f' to the first! It would leave all the output file descriptors open, and never execute any 'finally' clause. So what PicoLisp does is first clean up everything, by first *leaving* all enclosing expressions, and then jumping to the start of the loop. But this results in the above "are not fully equivalent". If we reduce the example to just a 'finally': (de f (N) (finally (printsp N) (if (=0 N) (printsp 'OK) (f (dec N)) ) ) ) : (f 3) OK 0 1 2 3 -> OK Now, if we use 'tco' and 'tc' instead of the recursive call: (de f (N) (tco (N) (finally (printsp N) (if (=0 N) (printsp 'OK) (tc (dec N)) ) ) ) ) : (f 3) 3 2 1 OK 0 -> OK the result is completely different! ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Tail call optimization
On Mon, Feb 10, 2025 at 02:06:52PM +0100, Alexander Burger wrote: > : (let N 99 (bench (tco (N) (or (=0 N) (tc (dec N)) > 0.038 sec > -> 0 For the records - and to show the absurdity of TCO - this is of course the same as : (let N 99 (bench (until (=0 N) (dec 'N 0.032 sec -> 0 ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Tail call optimization
On Sun, Feb 09, 2025 at 02:13:13PM -0800, Lindsay Lawrence wrote: > It is interesting that I don't see much performance difference between tco > and recur in most cases. The difference is better visible if you avoid as much additional processing as possible, and boil it down to the essential 'recur' and 'tco' calls: : (let N 99 (bench (recur (N) (or (=0 N) (recurse (dec N)) 0.067 sec -> 0 : (let N 99 (bench (tco (N) (or (=0 N) (tc (dec N)) 0.038 sec -> 0 ☺/ A!ex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Tail call optimization
On Mon, Feb 10, 2025 at 2:49 AM Alexander Burger wrote: > I'd like to point out, however, that recursion and tail call > optimization are not fully equivalent. We always need to keep that in > mind! > > ... > So what PicoLisp does is first clean up everything, by first *leaving* > all enclosing expressions, and then jumping to the start of the loop. > > ... > If we reduce the example to just a 'finally': > >(de f (N) > (finally (printsp N) > (if (=0 N) > (printsp 'OK) > (f (dec N)) ) ) ) > >: (f 3) >OK 0 1 2 3 -> OK > > Now, if we use 'tco' and 'tc' instead of the recursive call: > >(de f (N) > (tco (N) > (finally (printsp N) > (if (=0 N) >(printsp 'OK) >(tc (dec N)) ) ) ) ) > >: (f 3) >3 2 1 OK 0 -> OK > > the result is completely different! > > Thanks for the insight! This is interesting and really helps my understanding of the mechanics of how tc is implemented in picolisp. /Lindsay
Re: Tail call optimization
On Mon, Feb 10, 2025 at 6:32 AM Alexander Burger wrote: > On Mon, Feb 10, 2025 at 02:06:52PM +0100, Alexander Burger wrote: > > : (let N 99 (bench (tco (N) (or (=0 N) (tc (dec N)) > > 0.038 sec > > -> 0 > > For the records - and to show the absurdity of TCO - this is of course > the same as > > : (let N 99 (bench (until (=0 N) (dec 'N > 0.032 sec > -> 0 > > 👍👍 /Lindsay
Re: Tail call optimization
On Mon, Feb 10, 2025 at 2:49 AM Alexander Burger wrote: > > I'd like to point out, however, that recursion and tail call > optimization are not fully equivalent. We always need to keep that in > mind! > > The original idea of TCO (not the 'tco' function in PicoLisp) is to > avoid that calling the very last function in a function does > > ... > PicoLisp is an interpreter, and performing such code modifications would > be extremely inefficient. > > But for PicoLisp (I think Scheme doesn't even address such issues), > there are also other implications. The above example has the call to 'f' > only in the body of a single 'if' expression. But what if you have more > complicated nestings? > > ... Thanks Alex. I appreciate the insight into picolisp's tco given here. I realized several existing recursive functions I use were trivially convertible and are now able to work with much larger lists. I put a few examples here: swap, mtf (move to front), mft (move from top) https://github.com/thinknlive/picolisp-lisp-basics/blob/master/tco.l /Lindsay
