Specifically, it is certainly possible to make a non-tail recursive implementation of fib in Scheme. Curious why you seem to be implying otherwise.
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.
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...
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-...
Thanks for linking the paper!
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:
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.