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
