Hacker News Reader

Comment by etaioinshrdlu | Hacker News Reader

It seems like a lot of Lisps don't do tail call optimization either though, such as Emacs lisp, common lisp, and Clojure.

View on HN

That was the point of the lecture talking about how their system /could/ do this. I get the impression that scheme was one of the first languages that mandated that, though I suspect someone with a better view of history can correct that.

For common lisp, I thought it was just not required, but that it was common to do so?

True!

Although, a more nuanced point: it may not be required by the Common Lisp spec, but that's not to say that it's not done.

clisp:

    [1]> (defun f (n) (if (<= n 0) n (f (- n 1))))
    F
    [2]> (f 1000000)
    
    *** - Lisp stack overflow. RESET

sbcl:

    * (defun f (n) (if (<= n 0) n (f (- n 1))))
    F
    * (f 1000000)
    0

(Apparently clisp does do some tail call optimization, but I can't figure what it'd be used for other than an non-terminating loop such as a REPL, if it doesn't even handle this simple case properly.)

Heck, even GCC can do tail call optimization for C, even though that's definitely not in the spec.

    #include <stdio.h>
    
    int f(int n) {
      if (n <= 0) {
        return n;
      }
      return f(n - 1);
    }
    
    int main(int argc, char **argv) {
      printf("%d\n", f(10000000));
    }

Try compiling that with gcc -O0 (wherein you'll get a segfault) vs -O2 (wherein it'll print 0 as hoped).

> Apparently clisp does do some tail call optimization, but I can't figure what it'd be used for other than an non-terminating loop such as a REPL, if it doesn't even handle this simple case properly.)

You simply forgot to compile the code!

    [1]> (defun f (n) (if (<= n 0) n (f (- n 1))))
    F
    [2]> (compile 'f)
    F ;
    NIL ;
    NIL
    [3]> (f 1000000)
    0

The limited form of tail call in CLISP is a feature of its compiler only, not of the interpreter.

SBCL compiles everything, so there is no need.

But SBCL requires an existing Common Lisp installation for bootstrapping, whereas CLISP bootstraps itself just from C thanks to its interpreter.

> But SBCL requires an existing Common Lisp installation for bootstrapping, whereas CLISP bootstraps itself just from C thanks to its interpreter.

The SBCL people claim you can bootstrap SBCL with CLISP.

http://www.sbcl.org/getting.html#compile

- What is my purpose?

- You bootstrap SBCL

https://www.reddit.com/r/LispMemes/comments/bduwrl/you_boots...

Aha, thanks. I had found some docs that indicated that clisp supports TCO, but it wasn't clear to me how to make that work.

(I am nominally familiar with Common Lisp, but have never used it in a serious capacity.)

There are Python implementations that avoid that problem as well, e.g. Stackless Python.

Clojure is so close. I never understood why it went for a special form rather than proper TCO.

This is what Rich said about TCO in Clojure in 2010:

```quote:

When speaking about general TCO, we are not just talking about recursive self-calls, but also tail calls to other functions. Full TCO in the latter case is not possible on the JVM at present whilst preserving Java calling conventions (i.e without interpreting or inserting a trampoline etc).

While making self tail-calls into jumps would be easy (after all, that's what recur does), doing so implicitly would create the wrong expectations for those coming from, e.g. Scheme, which has full TCO. So, instead we have an explicit recur construct.

Essentially it boils down to the difference between a mere optimization and a semantic promise. Until I can make it a promise, I'd rather not have partial TCO.

Some people even prefer 'recur' to the redundant restatement of the function name. In addition, recur can enforce tail-call position.

```endquote

https://groups.google.com/g/clojure/c/4bSdsbperNE/m/tXdcmbiv...

If I remember correctly it is a restriction of JVM. That's why Scala also needs a special annotation for TCO.

That's not quite right. In Scala, the annotation is there so you get a complier error if it does not do the optimization. It doesn't affect when the compiler actually does the annotation.

As you can imagine, there are cases where the developer is counting on the optimization but the code isn't such that it can be made.

Your post got me curious and I did some googling. I think this explains it,

https://softwareengineering.stackexchange.com/questions/1576...

Looks like it's a scalac optimization that doesn't always work hence the need for the annotation to give the developer feedback.

There is also a link to a Closure discussion board exploring why Clojure doesn't have the annotation, by design. I didn't read it as I'm not that interested.

Not true, SBCL definitely has TCO.

The Common Lisp standard doesn't mandate tail call optimization, but it also doesn't even mandate garbage collection. It can be safely assumed that any non-toy implementation will include both.

> Clojure

It's been a while since I've messed with Clojure, but I thought Clojure had a function specifically for tail calls. I think it was recur?

Right, though there are some additional caveats, e.g. that it can't be used to implement TCO for mutual recursion

Aren't those basically 90% of the Lisps used in production environments, though? :-(

Isn't Project Loom going to solve that problem for Clojure?

Reply on news.ycombinator.com