4 ms·
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)
by 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 agoAha, 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
- junke 6y ago- What is my purpose? - You bootstrap SBCL https://www.reddit.com/r/LispMemes/comments/bduwrl/you_bootstrap_sbcl/ https://www.reddit.com/r/LispMemes/comments/bduwrl/you_boots...
- lmm 6y agoThere are Python implementations that avoid that problem as well, e.g. Stackless Python.