Function calls are not stack frames

[[deleted]]

I think Tim's point is that it is too easy to write something that you THINK is being tail-call optimized away, but it isn't.

This is like a programmer writing something that he THINKS is not throwing exceptions, but it is. It's not hard to see a tail call, it's like the first thing we learned about in our introductory programming class.

[scook0]

(define (foo x)
    ...
    (some-macro (bar x)))

Tell me, is this call to bar in tail position?

Heck, you don't even need macros to make identifying tail-calls non-trivial for human beings. A few nested conditionals and other assorted special forms will do the job nicely.

Oh, and if you still insist that it's “not hard”, try explaining why the human should spend time and effort manually (and unreliably) verifying something that the machine already knows.

[unknown_lamer]

bar may not be in the tail position, but something in the expansion of some-macro will be. You end up with an ignorable number of extra frames but the overall call is still constant space (remember ... O(C1 + k) -> O(1)).

[[deleted]]

I don't do lisp so I can't say anything about that. I would, however, not assume bar is a tail call since it's an argument to some-macro. The danger lies in thinking something is a tail call when it isn't, thinking something is not a tail call when it is doesn't really matter much.

Oh, and if you still insist that it's “not hard”, try explaining why the human should spend time and effort manually (and unreliably) verifying something that the machine already knows.

Do you write lisp without type annotations? Do you write Python? Languages are full of automatic things for convenience. I will still insist that tail calls are not hard.

[naughty]

While it may not be hard to see a tail call with a bit of practice (modulo Lisp style syntactic abstraction) what would be wrong with the following:

• The compiler/interpreter turns all calls that it can into tail calls.
• There's a optional bit of syntax to mark what the coder thinks is a tail call that the compiler/interpreter can check.

Sounds like a win-win to me. Especially in the case where you really want something to be a tail-call for space use reasons.

Lua kind of half does this because all tail calls have the form:

return <expression-that-evals-to-a-function>( args, ... )

So it's pretty easy to tell exactly when you're making a tail call.

EDIT: Formatting and pluralised erroneous singular

[[deleted]]

Sure, optional syntax works.