Hacker News Reader

Hacker News

Comment by noelwelsh | Hacker News Reader

Full thread

noelwelsh

The github page has more information: https://github.com/racketscript/racketscript

And to answer the questions every Schemer will have, no the runtime doesn't yet support tail calls or continuations.

View on HN

Continuations I can live without, but is Scheme at all usable without tail calls?

Not normal idiomatic Scheme, but I suppose some programs might have in-practice stack usage bounded not too high.

A Wasm target of the Chez/Racket compiler might be an easier way to get fast and proper evaluation in Web browsers.

tail calls are a foreign concept to me, and I assume that's because I'm coming from JIT scripts where that's not a common way to think of optimization. Just reading a bit of what they are, it sounds like you're branching within a function to others that return something of the same type - common enough - but get a huge memory/ processing bonus when you branch as long as the sending function doesn't continue? Is that sort of it? I'm really intrigued as to how and where this plays a big role in day to day coding or whether it's just an optimization once you refactor everything at the end.

Basically it is just another way of doing gotos, while keeeping the abstraction of function calls, without the space required for recursion stack data structures.

Having this as guarantee allows all the control flow concepts to be reduced to recursion and function calls.

A kind of purity when we reduce a programing language to the basic set of primitives that provide the building blocks to create any kind of programming paradigm, this is in a way the beauty of Scheme, moreso than Lisp.

Specifically, loops are a special case (with special syntax) of tail calls for language that don't support tail calls properly.

However as great as tail calls are they can't practically implement all control flow concepts. Eg they aren't really all that great for modelling exceptions, I think.

Fair point, however exceptions have their roots on continuations.

I would agree with sibling, and expand his comment a bit. Tail calls are just the specialization of continuation passing (or of having reified continuations programmer accessible. Actually, all control flow is the application of a continuation. So while I agree that tail calls are not used as the basis for exceptions, the parent concept of continuation passing does.

TCO is a runtime feature that enables code authors to write functions that call out to other functions in such a way that the stack size is not increased. If you’ve ever crossed the `RangeError: Maximum Call Stack Size Exceeded` error, it’s possible that the executed code could’ve benefitted from TCO. TCO is especially invaluable for writing recursive functions (without it, recursion is almost always a bad idea, IMHO).

TCO is technically in the ECMAScript specification (since 2015) but hasn’t been implemented across browsers or runtimes (with a few exceptions).

Dr. Axel has written a good explainer of TCO in the context of Javascript here https://2ality.com/2015/06/tail-call-optimization.html

This can be worked around using trampolines.

This is the first time I've heard of "trampolines". How interesting.

Do you use this strategy for implementing recursion? Are there consequences or trade offs?

For others who are curious, see

1) https://stackoverflow.com/questions/25228871/how-to-understa..., and 2) https://raganwald.com/2013/03/28/trampolines-in-javascript.h...

Check "Using ParentheC to Transform Scheme Programs to C or How to Write Interesting Recursive Programs in a Spartan Host (Program Counter)" for more about trampolines.

It's not the only strategy though.

https://stackoverflow.com/q/6003037/23567

You would do this inside a transpiler, rather than manually.

It is one of the few languages where tail calls are part of the language specification, so not really.

its the only way to do loops without blowing your call stack in scheme. technically yes as long as you're not doing anything interesting

Currently, the compiler does a dumb conversion to JS for loop of self tail calls. So if you call `map` on list of 1000000 items, your stack wont blow up. But I understand it is not enough for many non-trivial codebases. We were interested in doing more general TCO, and had some ideas around using trampolines (or iirc detecting mutually recursions and then trying to generate potentially a bit faster code). Had limited time, and was maybe too hopeful that eventually TCO will actually be supported by browsers (as it is part of standard).

Reply on news.ycombinator.com