3 ms·
I feel that you are working with a different version of "tail recursive" than any I have heard before. Specifically, it is certainly possible to make a non-tai
by taeric 10y ago
I feel that you are working with a different version of "tail recursive" than any I have heard before.
Specifically, it is certainly possible to make a non-tail recursive implementation of fib in Scheme. Curious why you seem to be implying otherwise.
- qwertyuiop924 10y agoI was talking about the mechanics of the compiler/interpreter, at least the original Sussman/Steele implementation. Let's look at Factorial in Scheme. You mentioned Fib, but Factorial is a simpler example, and will suffice. (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) The Scheme compiler/interpreter will detect that the last expression to be evaluated, and thus the return value will be: (* n (fact (- n 1))) Now, you might think that Scheme would detect this as ineligible for TCO, but that's not what happens. In fact, what happens (in pseudo-asm) is this: push *n push $1 call subtract ;;returns t1 on the stack, taken as arg by fact call fact ;;both n, and t1, the args to mult, are on the stack, followed by the return address. jmp mult ;;mult re-uses the stack frame, so it's a tail call. obviously, in a real asm, sub and mul are primitives, not funcalls, but you get the idea. If that didn't make sense, just read, "LAMBDA: The Ultimate Declarative." it explains it better than I could. So yes, all functions in Scheme are TCOed (at least, in the original implementation), it's just that some of the build of stack frames. I don't know if that's how other languages work, but it might be.
- taeric 10y agoI find this... still an odd definition. To quote Sussman/Abelson[1], "An evaluator that can execute a procedure such as sqrt-iter without requiring increasing storage as the procedure continues to call itself is called a tail-recursive evaluator." Specifically, the caller of this function will have to clear out the stack of all operations that were pushed. Something you wouldn't have to do on a tail or non-recursive function. [1] https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html#%_idx_6088 https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.htm...
- qwertyuiop924 10y agoIt is an odd definition, I won't deny that. I was trying to talk about possible implementation, as opposed to the typical definition, so it's possible that I should have used another term. By the way, this is the paper I was talking about. It won't explain my bizarre choice of words, but it might explain what I meant when I said that Scheme tail-call optimizes unconditionally: http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-379.pdf http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-...
- taeric 10y agoI think I see the difference. There are tail call optimizations, and then there is tail call recursion. They are two different things, potentially. Thanks for linking the paper!
- qwertyuiop924 10y agoYeah, there you go. That paper is part of a collection of papers, known as The Lambda Papers. If you enjoyed this one, you'll probably want to read the rest: http://library.readscheme.org/page1.html http://library.readscheme.org/page1.html