Re: Performance of Recursion vs Iteration in PicoLisp
Hi Thorsten, The notion of 'tail-recursion' does not have any meaning in an interpreted language like PicoLisp, since its only for compiler optimizations -right? I think you are confusing the terms. What you are probably after is called tail call optimisation (TCO), which is an optimisation that can be applied to tail calls. tail-recursion is definitely one way to name it, there are a lot of usage examples around, e.g. ,-- | http://www.haskell.org/haskellwiki/Tail_recursion `-- but TCO might be a more accurate term, or lets put it like this - many books about compiled languages state that tail-recusrion is important because it enables TCO. no, TCO itself is not about recursion. TCO can be applied even to non-recursive code. You could put it the other way round, TCO makes tail-recursive code more space efficient by reusing stack frames instead of growing the stack. Cheers, Tomas -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
Hi Thorsten, The notion of 'tail-recursion' does not have any meaning in an interpreted language like PicoLisp, since its only for compiler optimizations -right? I think you are confusing the terms. What you are probably after is called tail call optimisation (TCO), which is an optimisation that can be applied to tail calls. There are interpreters that require TCO, e.g. PostScript. In my JavaScript implementation of PostScript http://logand.com/sw/wps/index.html, I used trampoline to implement it http://logand.com/picowiki.html#sec-14 and optimize stack growth. As shown in the examples, one can use the technique in PicoLisp too, althought it doesn't compose well. Cheers, Tomas -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Performance of Recursion vs Iteration in PicoLisp
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. PS The notion of 'tail-recursion' does not have any meaning in an interpreted language like PicoLisp, since its only for compiler optimizations -right? -- cheers, Thorsten -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
Hi Thorsten, 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. OK, let's try. If I run this: # Recursive (bench (do 100 (let (N 100) (recur (N) (if (=0 N) 1 (* N (recurse (dec N))) ) ) ) ) ) # Iterative (bench (do 100 (let N 1 (for I 100 (setq N (* I N)) ) N ) ) ) # Simple (bench (do 100 (apply * (range 1 100)) ) ) then I get: 13.161 sec 7.331 sec 7.413 sec - 9332621544394415268169923885626670049071596826438162146859296389521753229915608941463976156518286253697920827223758251185210916864 So the recursive version takes about twice as long as the other two. The notion of 'tail-recursion' does not have any meaning in an interpreted language like PicoLisp, since its only for compiler optimizations -right? Yes. ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
(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. AlexG 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. PS 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
Re: Performance of Recursion vs Iteration in PicoLisp
Alexander Burger a...@software-lab.de writes: Hi Alex, 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. OK, let's try. If I run this: # Recursive (bench (do 100 (let (N 100) (recur (N) (if (=0 N) 1 (* N (recurse (dec N))) ) ) ) ) ) # Iterative (bench (do 100 (let N 1 (for I 100 (setq N (* I N)) ) N ) ) ) # Simple (bench (do 100 (apply * (range 1 100)) ) ) then I get: 13.161 sec 7.331 sec 7.413 sec - 9332621544394415268169923885626670049071596826438162146859296389521753229915608941463976156518286253697920827223758251185210916864 So the recursive version takes about twice as long as the other two. Thanks, nice to know. I find that interesting enough that I would like to add it to the 'Recursion' Wiki article - what do you think? -- cheers, Thorsten -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
Alex Gilding alex.gild...@talktalk.net writes: Hi Alex (Gilding), You actually have that the opposite way around. [...] Very interesting read, thank you for the info. -- cheers, Thorsten -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
Hi Alex, (If you can forgive a PicoLisp n00b shoving his face into the discussion...) Sure! Welcome anytime :) 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 I disagree. Thorsten's question was if it makes sense in an _interpreter_. And I think it does _not_ make sense, because you cannot do TCE while interpreting List structures. You have to do it in the compiler, as it requires some analysis of the code structure. In general, I think recursion is overvalued. It used to excite computer scientists in the dark ages of computing, causing awe and wonder when a subroutine was able to call itself. In a languge like PicoLisp, recursion is only necessary when you have recursive data structures (like trees), and those cases are typically not tail recursive. For most common cases you directly write a loop with 'do', 'loop', 'while', 'until', 'for' etc., which let you express more clearly what the code is supposed to do. PicoLisp's dynamic scope rules mean that a function's activation can Please avoid the term dynamic scope. There is no such thing in PicoLisp. PicoLisp has dynamic binding. Scope is concerned about the _visibility_ of symbols. And normal (internal) symbols always have a global scope in PicoLisp. Transient symbols have a file-local scope, while external symbols have a DB-wide scope (which usually spans many processes or even remote machines). Binding is concerned about how _values_ are assigned to symbols. This is also a bit explained in the FAQ: http://software-lab.de/doc/faq.html#dynamic or http://software-lab.de/doc/faq.html#closures The Scheme people seem to always confuse this, because Scheme has no clear separation between symbols (which have a distinct identity in real Lisp) and their bindings. When you write the name of a variable in Scheme, it is just a name for a value on the stack frame, and afaik there is no binding of a symbol involved. ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
Hi Thorsten, Thanks, nice to know. I find that interesting enough that I would like to add it to the 'Recursion' Wiki article - what do you think? Good idea! And thanks for the article! ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
On 10/05/2013 16:19, Alexander Burger wrote: you cannot do TCE while interpreting List structures. You have to do it in the compiler, as it requires some analysis of the code structure. One could always look ahead and try to analyse the s-expression's structure while executing it... this probably wouldn't perform very well though. I think we are thinking the same thing, just from different perspectives :). You could conceivably write an interpreter for pure list data that eliminated tail calls, because you can write an interpreter that can do anything, but it wouldn't be an optimisation because of the extra overhead. Please avoid the term dynamic scope. There is no such thing in PicoLisp. PicoLisp has dynamic binding. Indeed, sorry about that. Still, using the correct term, unless I'm gravely mistaken the presence of it necessarily forbids one from even considering general TCE, as it would demand messing with the bindings at the wrong times. Anyway, I think PicoLisp's incredible dynamic programming power can probably supply better solutions than asking the interpreter to do TCE for you (e.g. a self-compiling function that you define in recursive form and rewrites itself to use iteration the first time it runs; I have no idea to do this but I'm sure someone already has). AlexG -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: Performance of Recursion vs Iteration in PicoLisp
Hi Alex, you cannot do TCE while interpreting List structures. You have to do it in the compiler, as it requires some analysis of the code structure. One could always look ahead and try to analyse the s-expression's structure while executing it... this probably wouldn't perform very well though. Yes, exactly. That's what I meant. It somehow violates the idea of the interpreter. It wouldn't perform very well, but it would of course solve one issue you mentioned before: The stack overflow. I think we are thinking the same thing, just from different perspectives :). You could conceivably write an interpreter for pure list data that eliminated tail calls, because you can write an interpreter that can do anything, but it wouldn't be an optimisation because of the extra overhead. True. PicoLisp. PicoLisp has dynamic binding. ... Still, using the correct term, unless I'm gravely mistaken the presence of it necessarily forbids one from even considering general TCE, as it would demand messing with the bindings at the wrong times. To my understanding, this would not be a problem. Given that we take the trouble of making the interpreter TCE-able, it could probably manipulate the symbol bindings too, by 'setq'-ing them to new values instead of 'bind'-ing them (saving their values to the stack before setting them). To my feeling, TCE would be very inappropriate for PicoLisp, as it is rather against the spirit: It makes things complicated, does something behind the screen which is not controlled by the programmer, and does inefficient things where there is a better, straight-forward and faster solution (i.e. explicitly write a loop statement, where you want to loop). ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
