Hacker News Reader

Comment by nabla9 | Hacker News Reader

The problem with tail calls is that they are implicit. That's why it's usually called tail call optimization. There is nothing in the syntax to indicate that you actually have a tail call. You may have made a mistake and it actually blows up the stack.

If I remember correctly, there was briefly discussed interesting proposal to add explicit tail calls into Python almost decade ago. You would use keyword or syntax to perform tail-calls explicitly (not the tail call decorator hack). This would make tail calls actual looping construct.

View on HN

Tail calls were made explicit in Clojure, with the recur construct. It had more to do with the JVM than syntactic benefits, but it turns out to be a decent idea.

"recur" can be used for self-call in tail position, but does not help with the general case where you may want to jump to another function.

Tail calls do not just deal with recursive functions, in general TCO works on any function call in tail position. Maybe a more general recur construct (maybe called "jump") would be a good idea, but then you'd have to remember to use it.

Clojure is limited by the JVM, hence the need for recur. However, between it and trampoline you get most of the way to what TCO offers, albeit with the need for the programmer to be explicit.

While there isn't special form for tailcall, they are not implicit. If the recursive call does something with the result, it's not a tailcall. Unless you are being cute with closures, it's already explicit in the AST.

  --> return myself(...)       # tail call
  --> return var * myself(...) # not a tail call

But there is indeed something to be said about a construct that enforces the tail call guarantee. The point of SICP's scheme though is to keep the number of language constructs to a minimum for educational purposes.

the following is also tailcall:

    x = f(a)
    ... 
    ...
    return x

That's definitely not a tail call, and even with a smart compiler it's pretty hard that it would get optimized into "return f(a)".

If "x" is declared there and never mutated in the subsequent code, and the code in the "..." doesn't perform any side effects, then such an optimization could occur... but then again, if the code in the "..." in your example didn't perform any side effects, it'd be dead code.

Better examples:

Both

    If (b == 3):
        x = f(a)
    else:
        x = g(a)
    return x

and

    if (b == 3):
        x = f
    else:
        x = g
    return x(a)

are equivalent to:

    if (b == 3):
        return f(a)
    else:
        return g(a)

In every example the function call is in the tail position semantically. In the the two cases syntactically. The loop construct is hidden.

That's not right, unless the "... ..." is empty, and even then, it depends on whether x is a global variable, and even if it isn't, it depends on the language.

Tail calls are semantic, not just an optimization, at least in languages like Scheme. Also, blowing the stack only applies to language implementations that have a fixed stack size, it's not a universal truth. In Scheme, a call stack is an implementation detail, and some implementations dynamically allocate stack space to accommodate recursive procedures. For example, here's a simple implementation of 'map':

    (define (map proc lst)
      (if (null? lst)
        '()
        (cons (proc (car lst)) (map proc (cdr lst)))))

You might look at this and go "that's bad! it will blow the stack when the list is too long!". Well, some Schemes will dynamically grow the stack so that this straightforward code translates to an efficient process that doesn't hit arbitrary stack limits. Otherwise the programmer would have to contort this into an iterative, tail-recursive process, which would involve building the list backwards and reversing it at the end.

Apparently some implementations have tail-recursion modulo cons. You spot a tail-recursive function where the result is placed in the cdr, and you compile your code so that it chains cells by calling "set-cdr!"

For example (using CL), the code could be turned into two auxiliary map%% and map% functions (map% would be what a call to map expands into).

    (defun map%% (cons function list)
      (declare (optimize (speed 3) (debug 1) (safety 1))
               (type function function)
               (type list list)
               (type cons cons))
      (when list
        (map%% (setf (cdr cons)
                     (list (funcall function (first list))))
               function
               (rest list))))
    
    (defun map% (function list)
      (let ((fresh (cons nil nil)))
        (map%% fresh function list)
        (rest fresh)))

Testing TCO:

    (map% #'1+ '#1=(5 6 8 4 5 1 3 . #1#))

    Heap exhausted, game over.

> You would use keyword or syntax to perform tail-calls explicitly

That's what I did in my Forth dialect; I called it "goto".

It's debatable whether tail calls should be classified as an optimisation. In my view, they should be part of the operational semantics.

I try to use the phrase "tail call optimisation" when an implementation may perform it but the language doesn't require it, and "tail call elimination" when the language requires it (and hence any implementation which doesn't is non-conforming).

Reply on news.ycombinator.com