3 ms·

Quoting the author: With Lisp it's always been non-trivial to know when a function is tail-recursive. You can't just blindly count parens, you ha

by shiro 10y ago

Quoting the author: With Lisp it's always been non-trivial to know when a function is tail-recursive. You can't just blindly count parens, you have to try to "run" the function in your mind. To me, Lisp code is just like a tree (well, sometimes DG) and it's statically obvious where the leaves are---no need to "run" the function in mind. But maybe it's just because I get used to it; once you learned, you forget what you saw (or you didn't see) before.

qwertyuiop924 10y ago
It's actually not hard to see if a Scheme function is tail-recursive, for another reason: All Scheme functions are tail recursive. The difference is whether you're building up stack frames by calling a recursive function inside that last form in the function, thus requiring the language to build an extra stack frame for it. The only difficulty in seeing if a function is tail recursive, either way, is just checking for branch instructions. This becomes easier if you wait until the thing's been macroexpanded, and have the lexical environment available so you can tell what names refer to what. Again, Schemes need not bother with this: when you comes across the expression will be the return value, tail-call the outermost function, after collecting the values of all inner functions.
- 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 ago
    I 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 ago
      I 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 ago
        It 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 ago
        I 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 ago
        Yeah, 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
riboflava 10y ago
It can still be non-obvious with an optimizing compiler, or with non-Lisp. I don't see the point in having beginning students think about tail call optimized recursion vs normal recursion unless they're going through SICP. In the end it can totally be a compiler thing. For instance, GCC can optimize this: int factorial(int x) { if (x > 1) return x * factorial(x-1); else return 1; } into this: int factorial(int x) { int result = 1; while (x > 1) result *= x--; return result; } (http://ridiculousfish.com/blog/posts/will-it-optimize.html http://ridiculousfish.com/blog/posts/will-it-optimize.html)
- shiro 10y ago
  When you're using TCO-guaranteed language like Scheme, what's important is you recognize tail position, where TCO is guaranteed. Guaranteed TCO lets you express, for example, state machine using mutually recursive functions. You do see the tail calls as gotos and you heavily rely on that while you're coding. In that regards, I feel that tail call "optimization" is misleading, since it gives an impression that it's some kind of optional bonus the compiler gives to you. The transformation such as your gcc example is, certainly, an "optimization". If you get one, you're lucky; if you don't, fine, you can live with it. Guaranteed tail call elimination is totally different---if you don't have one, you change the way you write code. (So, the blanket statement of "Lisp" might be inappropriate, for it's only a subset of Lisps that has guaranteed TCO.)

by shiro 10y ago

qwertyuiop924 10y ago

It's actually not hard to see if a Scheme function is tail-recursive, for another reason: All Scheme functions are tail recursive. The difference is whether you're building up stack frames by calling a recursive function inside that last form in the function, thus requiring the language to build an extra stack frame for it. The only difficulty in seeing if a function is tail recursive, either way, is just checking for branch instructions. This becomes easier if you wait until the thing's been macroexpanded, and have the lexical environment available so you can tell what names refer to what. Again, Schemes need not bother with this: when you comes across the expression will be the return value, tail-call the outermost function, after collecting the values of all inner functions.

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 ago
  I 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 ago
    I 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 ago
      It 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 ago
        I 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 ago
        Yeah, 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

riboflava 10y ago

It can still be non-obvious with an optimizing compiler, or with non-Lisp. I don't see the point in having beginning students think about tail call optimized recursion vs normal recursion unless they're going through SICP. In the end it can totally be a compiler thing. For instance, GCC can optimize this: int factorial(int x) { if (x > 1) return x * factorial(x-1); else return 1; } into this: int factorial(int x) { int result = 1; while (x > 1) result *= x--; return result; } (http://ridiculousfish.com/blog/posts/will-it-optimize.html http://ridiculousfish.com/blog/posts/will-it-optimize.html)

shiro 10y ago
When you're using TCO-guaranteed language like Scheme, what's important is you recognize tail position, where TCO is guaranteed. Guaranteed TCO lets you express, for example, state machine using mutually recursive functions. You do see the tail calls as gotos and you heavily rely on that while you're coding. In that regards, I feel that tail call "optimization" is misleading, since it gives an impression that it's some kind of optional bonus the compiler gives to you. The transformation such as your gcc example is, certainly, an "optimization". If you get one, you're lucky; if you don't, fine, you can live with it. Guaranteed tail call elimination is totally different---if you don't have one, you change the way you write code. (So, the blanket statement of "Lisp" might be inappropriate, for it's only a subset of Lisps that has guaranteed TCO.)