(If you can forgive a PicoLisp n00b shoving his face into the discussion...)

You actually have that the opposite way around. Tail call elimination (tail recursion is just one special case of tail calls) is a *semantic* rule that says that a function's activation no longer has any influence on anything after its final call has been engaged. Since it has no influence on anything, it is also guaranteed to be safe to remove it from the stack - this is not really optimisation so much as a necessary implementation requirement, because if you left it on the stack it would affect proceedings by eventually contributing to the very-observable behaviour that is overflow (you could also go stackless). So Scheme interpreters need to implement it fully, because they still have stacks (or stacklike heaps...). There are usually more powerful ways for a high-performance compiler to optimise code, anyway (the best Scheme compilers will happily leave tail calls in sometimes if it means they can use other optimisations).

PicoLisp's dynamic scope rules mean that a function's activation can influence other calls just by existing though, and therefore directly contradicts the first assumption of TCE; in the general case it is never safe to remove PicoLisp frames from the stack until they're actually returning for good, because you might be removing bindings that would otherwise be seen by the tail call.

So whether a language is interpreted or compiled makes relatively little difference to the importance of TCE. Whether a language has dynamic scope, or some other non-Scheme-like rule, makes all the difference. You could probably write a transformer that could safely eliminate _some_ tail calls from PicoLisp, but I doubt it would be a trivial matter (actually it would probably require godlike flow analysis) and it might place a lot of restrictions upon the allowable code.


On 10/05/2013 14:43, Thorsten Jolitz wrote:
Hi List,

since I just wrote a little Wiki article about recursion in PicoLisp, I
would be curious about how recursion performs in comparison to iteration
in PicoLisp.


The notion of 'tail-recursion' does not have any meaning in an
interpreted language like PicoLisp, since its only for compiler
optimizations -right?

UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to