more-magic.net

CPS is a very bad idea in JS at present.

CPS in scheme works because proper tail call optimization exists, so your call stack doesn't explode. In current JS, the only way to make that work is performing a nextTick or setTimeout on every single function which trashes performance of simple things due to exiting your code back to the event loop all the time.

<stands on soapbox>

There's a special place in hell reserved for companies that deviate from standards because of petty disagreements. Proper tail calls have been a part of the JS spec for 5 versions now. They are implemented in Safari and in popular embedded engines like duktape. MS and Firefox refused to implement. They were in v8 behind a flag, but were removed.

v8 devs pitched a fit about stack traces disappearing (even though they disappear across the event loop anyway). The webkit team showed that Chicken scheme's shadow stack works just fine and it's been in production for a long time now (without any issues I'd add). Instead, they insisted that they wanted to revise the standard to require marking tail-recursive functions.

They also talked about decreased performance, but JSC team seems to have implemented it with a minimal performance impact, so it's definitely possible. More importantly, JS is a language to make development easy -- we have wasm in development for when speed becomes an issue and it's faster anyway (the label proposal would have also solved the issue by giving devs a choice).

They then dropped…

right. Brace yourself, you're in for a long ride.

If you want to get in-depth on Cheney on the MTA, I'd reccomend Peter Bex's article on the Chicken GC (http://www.more-magic.net/posts/internals-gc.html), and the original paper, "CONS should not CONS its arguments, part II: Cheney on the MTA". But I'll do my best to sum it up here.

Cheney on the MTA is a really neat hack that allows for cheap continuations, realtively efficient C compilation of Scheme code, and an effective garbage collection scheme.

Effectively, with CMTA, you have a generational GC, but the first generation is stack allocated. When the stack allocations run out of space, all the data is copied out to the heap, into the second generation of GC. This is super effective because most data is only allocated for a short time, so it never goes out to heap, and your accesses are closer together, and also on the stack, so there's less chance of a cache miss. But it gets better: In Scheme, a program's continuation (think basically its instruction pointer and stack state) can be reified as an actual data structure. However, since you're GCing the stack already, this doesn't causr any overheard, or at least not nearly as much as it does in, say, Guile, which has to copy the stack every single time a continuation is created.

The reason it's called Cheney on the MTA is because it uses Cheney's algorithm for GC, and because it's using the stack to hold data, popping the stack would invalidate program state, so it…

Note that Chicken has a very interesting garbage-collection algorithm called "Cheney on the MTA". Basically, the stack is the heap, and no function ever returns. The compiler converts every program to continuation-passing style, where instead of a function returning, it tail-calls a continuation. When the stack exhausts its limit, the runtime longjmps back to a trampoline. Variables captured by the current continuation form the roots of a copying generational GC - the runtime traces every pointer from them and copies the live objects to the heap. The stack then unwinds, with every uncopied object being garbage that gets re-used the next time the stack grows.

It's pretty amazing that it works, particularly in relatively portable C. Also gets fairly decent performance, too: as Schemes go Chicken is one of the faster ones.

https://www.more-magic.net/posts/internals-gc.html

https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7143

"High level" is in the eye of the beholder, but I don't know that C is the best example to pick on: Before LLVM it was pretty common to target C as your portable assembly language.

Just to give an example, I think GHC targets C-- as one of
the steps in its transformations, and still outputs C when you're porting it to a new platform or building a cross-compiler. I don't know that it's useful to say that GHC ceases to be a compiler when you use it to target weird platforms.

And the Chicken Scheme compiler outputs C code[1] that doesn't look like a human wrote it: The C code uses a trampoline to organize function calls, and it periodically garbage-collects your stack cleaning up old frames as you call functions.

[1] http://www.more-magic.net/posts/internals-gc.html

>> My understanding is that Clojure is meant to be Scheme like, but it is not fully compliant to a Scheme spec, my only guess is due to JVM specific nuances, but I could be wrong.

Clojure's syntax and semantics are quite different from Scheme and Common Lisp:

https://clojure.org/reference/lisps

https://www.more-magic.net/posts/thoughts-on-clojure.html

Most differences are due to design choices, not merely JVM nuances. A few differences are due to JVM limitations at the time that Clojure was designed.

I don't think any attempt was made to comply with a Scheme spec.

Only highly abstract languages like Brainfuck

https://esolangs.org/wiki/Brainfuck

which are too simple to have WTFs, although you might say the whole thing is a WTF. I think AVR-8 assembler is WTF free, but I'd like a more powerful macro assembler which would probably introduce a WTF.

Common Lisp is full of WTFs, I went through many stages of grief reading Graham's On Lisp but most notable was "if he was using Clojure he wouldn't be fighting with nconc". People have problems with Clojure too

https://www.more-magic.net/posts/thoughts-on-clojure.html