5 ms·

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

taeric 6y ago
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?
fishmaster 6y ago
Not true, SBCL definitely has TCO.
mrtranscendence 6y ago
Clojure is so close. I never understood why it went for a special form rather than proper TCO.
- pimeys 6y ago
  If I remember correctly it is a restriction of JVM. That's why Scala also needs a special annotation for TCO.
  - patrickthebold 6y ago
    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.
    - waynesonfire 6y ago
      Your post got me curious and I did some googling. I think this explains it, https://softwareengineering.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization 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.
- iLemming 6y ago
  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/tXdcmbiv4g0J https://groups.google.com/g/clojure/c/4bSdsbperNE/m/tXdcmbiv...
vitus 6y ago
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).
- kazinator 6y ago
  > 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.
  - vitus 6y ago
    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.)
  - msla 6y ago
    > 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 http://www.sbcl.org/getting.html#compile
deleted 6y ago
[deleted]
Igelau 6y ago
> 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?
- lgessler 6y ago
  Right, though there are some additional caveats, e.g. that it can't be used to implement TCO for mutual recursion
User23 6y ago
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.
oblio 6y ago
Aren't those basically 90% of the Lisps used in production environments, though? :-(
johnnycerberus 6y ago
Isn't Project Loom going to solve that problem for Clojure?

taeric 6y ago

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?

fishmaster 6y ago

Not true, SBCL definitely has TCO.

mrtranscendence 6y ago

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

pimeys 6y ago
If I remember correctly it is a restriction of JVM. That's why Scala also needs a special annotation for TCO.
- patrickthebold 6y ago
  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.
  - waynesonfire 6y ago
    Your post got me curious and I did some googling. I think this explains it, https://softwareengineering.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization 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.
iLemming 6y ago
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/tXdcmbiv4g0J https://groups.google.com/g/clojure/c/4bSdsbperNE/m/tXdcmbiv...

vitus 6y ago

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

kazinator 6y ago
> 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.
- vitus 6y ago
  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.)
- msla 6y ago
  > 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 http://www.sbcl.org/getting.html#compile

deleted 6y ago

[deleted]

Igelau 6y ago

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

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

User23 6y ago

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.

oblio 6y ago

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

johnnycerberus 6y ago

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