[qwertyuiop924]

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]

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]

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]

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.htm...

[qwertyuiop924]

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-...

[taeric]

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]

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