I suspect it does tail calls on Safari as Safari is the ONLY browser to completely implement ES6+ and implement proper tail calls (I'd note that it's not the only ES6+ compliant implementation, but most of the rest are aimed at microcontrollers or embedding).
Huh, that in turn means that - server-side or for scripts - this should run better on Bun than on Node (or Deno), because Bun is based on JavaScriptCore and actually handles taill call optimization well[1]
I might be confused, but do you mean "it doesn't do tail call optimization"? "Doing tail calls" is a bit of a strange phrase, if I understand the concept of what a tail call is—I'm under the impression that a tail call is just a call, that happens to be the final action in its scope. If a language can do "calls" at all then it can "do tail calls."
Yes, you're correct about the more general meaning. But in the Scheme world "doing tail calls" means something like being "properly tail recursive" (see https://www.gnu.org/software/guile/manual/html_node/Tail-Cal... for more details). It's not appropriate to call it an optimization because it's a foundational property of the language.
It's best to call it "Tail Call Elimination". It's not a nice-to-have optimization in Scheme as using tail calls is the only way to iterate (do is a convenience built on tail calls), it's a necessity for any non-toy Scheme implementation.
- The only optimization that completely eliminates calls is inlining, so it is misleading. An optimized tail call still has some trappings of a call, like a control transfer somewhere else, with arguments.
- In Scheme lingo, the procedure calls so optimized are called tail calls; they are produced, and thus not eliminated. When the goto is taken, the procedure is said to be making a tail call, or tail calling. In assembly language, if you hand coded such a goto, you might put in a comment saying "this is a tail call", so it's not just Scheme lingo.
You know this, but being explicit helps the casual reader:
The "elimination" in "tail call elimination" refers to the "elimination" of the call frame.
In languages like C each call pushes a frame to the call stack. When the called procedure is done, execution returns to the site of the call. In a tail call there is no work to done, so the frame is now removed and execution continues where the previous frame points. But ... if we simply never omit the call frame, then executation then exectuation automatically returns to the parent frame.
The spec talks about allowing an "unbounded number of active tail calls".
In an implementation with frames, it means tail calls can't just keep pushing frames.
Seen in isolation "tail call elimination" doesn't seem like a big deal, but combined with "real macros" (structural, scope-respecting macros) it is possible to implement control structures as a user without worrying about stack overflow.
In Scheme slang, a tail call is a procedure call that has been turned into a kind of goto, and so doesn't require a new stack frame or return linkage.
The term "tail call optimization" still makes sense, but refers to the production of tail calls out procedure calls that occur in the tail position, not to the reduction/elimination of tail calls.
Yes, this was an issue of me knowing general terminology (where this idea, or similar ones, show up in Haskell and Clojure, for example) but not the more specific parlance of Scheme. I'm happy to learn!
Author here. That's why it's not listed on the official scheme.org website as one of the implementations. I was told that to me called Scheme, you need TCO and continutations.
I made one attempt to implement them some time ago but failed. The code was not working. I based my implementation on someone else code. And later turned out that the call/cc that I based my code pm was not even full continuations and failed my test case.
Most Toy Scheme implementations don't have TCO and call/cc so I can't use them as a reference. But I have an implementation that is really promising that implemented them, the code is very minimal and I can base my code on that.
Sorry, I don't quite understand what you mean by 'doesn't do tail calls', I tried the stupid fib and it ran fine (well, okay, slowly but fine). Does it translate to JS and depend on the implementation to provide tail call optimisation/elimination?
Seems like TCO is is hard to do in browser JS, that's surprising. It's kind of a deal killer for basing a functional language on. JVM too for that matter.
Not hard at all. Chrome had it implemented, removed it, then added it back, but only for WASM.
They disliked that it didn't leave stack frames in some cases.
Apple refused to break the JS backward-compatibility guarantee and implemented as-per the spec and Chrome refused to turn on their implementation for users unless it added a special keyword to identify it as a tail call.
Chrome dev's emotional investment and resulting stubbornness has split the JS community and made their implementation incompatible with the spec. They are 100% in the wrong here.
FF objected because they didn't want to do the work, but they're now doing that work making proper tail calls work in WASM, so their objection is irrelevant now. MS objected that Windows APIs made PTC slow, but they now use Chrome, so they don't have an excuse today either.
There's nothing inherently insecure about proper tail calls and that is pure FUD.
That just leaves Google. They chose to die on the hill of syntactic tail calls and are still refusing to implement the spec. The only reason left is their pride and emotional investment in STC.
Even back then, Safari was implementing and had more marketshare than Edge and FF combined (now 2.5x their combined market share with FF only having around 3% share today).
I'm tired of bad excuses and want them to actually implement the now 8 year old spec properly.
I'm sorry you are so attached to implementation details but that hardly detracts from the general usability of a language. Clojure is hosted both on the JVM and JavaScript and is, all things considered, both usable and popular enough of a Lisp and it definitely doesn't have TCO. You can bail out to using "loop" if you're that perf sensitive.
It's not an implementation detail if you can't do recursion in constant stack space. The underlying VM should allow all CS primitives, and the guest can add constraints as it wants.
How is that not an implementation detail? You can't really inspect the stack at runtime in a useful way. It's literally just performance and yeah you might run out of memory somewhere but that's true of every language detail, some languages are more efficient than others. I'm getting downvoted but I think my comment stands. Clojure is a perfectly useful example of a language without TCO. It's not necessary, it's a detail. And as a long time developer, there hasn't been a single time where I cared if my stack took constant space or not. It has never mattered.
lips> (let ((a (begin (define b 4) 5)))
(+ a b))
9
lips> b
4
I mentioned this regarding a previous version and the author said it was deliberate. I feel it breaks lexical context and is icky in general. Scheme has definition context, and loosening it is probably a good thing - but not further than "to all bodies".
LIPS has documentation builtin into every function. You can see the docstring when you hover over the name of the symbol in the REPL. It also has auto-indent. Also if you press enter you can get back and modify previous lines of code. History doesn't repeat lines only full S-Expressions so it's easy to rerun a big chunk of code.
Even though Try Gambit is a REPL it's not very user-friendly.
The try.gambitscheme.org web app has most of these features and more:
- REPL history with up/down arrows (explained on the landing page's README)
- You can use the "help" procedure to browse the full documentation
- TAB key for autocompletion
- In addition to the REPL there is a code editor to edit programs stored in the browser
- The system supports multiple threads, one REPL per thread
- There is a builtin tutorial to learn the basics of Scheme with examples executable in the REPL with a single click on a "run" button
- The REPL supports single stepping the execution of code
- Easy interface to JS with the SIX syntax extension, e.g. (let ((msg "hello")) \console.log(`msg, 1+2/3))
- The error messages are clear and precise giving the file and line number and highlighting in yellow the piece of code (in the REPL or file) that raised the exception. Just try this in both systems to see the difference:
> (define (f x) (/ 1 (* x x)))
> (f 5)
> (f "hello") ;; the * procedure will raise an exception and highlight "(* x x)"
- in Gambit History works on lines not S-Expressions like in LIPS
- With LIPS you don't need any new syntax to integrate with JavaScript you just use JavaScript directly (let ((msg "hello") (console.log msg)) SIX syntax doesn't look like Scheme.
- Help popup documentation, with LIPS you have documentation directly in the REPL (when you hover over the symbol) and you can access docstring as strings and assign them to values.
- You can create new syntax similar to scheme vectors and make representation the same as code
- You can manipulate almost everything in the language like environments that you can modify
- LIPS show stack trace not one line which gives an error that makes it easier to find where the error happens.
- The Bookmarks allow to run the REPL on every page even PDF files with R7RS spec.
- You can actually run the code that uses quotes (’ The apostrophe symbol) from the spec if you use syntax extension to add new syntax.
