more-magic.net
http://www.pipeline.com/~hbaker1/
which includes the "Cheney on the M.T.A." paper (http://www.pipeline.com/~hbaker1/CheneyMTA.html) and a bunch of other interesting things (mostly with a lispy flavour). A few specific examples:
http://www.pipeline.com/~hbaker1/Prag-Parse.html -- a nice technique (not invented by Baker) for simple parsing tasks, and a neat Lisp implementation.
http://www.pipeline.com/~hbaker1/LazyAlloc.html -- you might notice that the "M.T.A." paper is subtitled "CONS should not CONS its arguments, part II"; this is the original "CONS should not CONS its arguments" and is also about allocating things on the stack that you might not expect to be stack-allocatable.
http://www.pipeline.com/~hbaker1/Use1Var.html -- "use-once" variables (related to "linear logic", which is not Baker's creation), not a million miles from C++'s auto_ptr/unique_ptr but Baker was advocating this stuff as early as 1993.
And some other interesting things due to people other than Baker, such as a copy of the famous HAKMEM (http://www.pipeline.com/~hbaker1/hakmem/hakmem.html).
It's a very cool system, and this article is awesome. I find garbage collectors fascinating.
https://news.ycombinator.com/item?id=7361947
http://jlongster.com/Open-Sourcing-My-Gambit-Scheme-iOS-Game...
On top of this, the generated code is said to be portable C.
I've skimmed through the papers mentioned in the article years ago, but gave up understanding them. This article is golden if I really want to understand what's going on in a real-world use of the techniques described in those papers.
(1) Scheme is dynamically typed, not statically, so some operations need to operate on objects whose properties are not known at compile time and which need to be constructed/wrapped. The same does not necessarily hold for a statically typed language.
(2) C is not really designed to be the target language of a compilation process. In particular, there's no portable access to stack frames, so any mechanism that inspects the stack (in this case, for precise garbage collection) needs to recreate the necessary machinery. If you target a representation that is actually designed for this purpose (such as LLVM), a lot of these problems go away. Likewise, C does not have native support for continuations, tail calls, or a number of other mechanisms that more sophisticated backends do support.
(3) The compiler does not need to generate human readable code; code generation that targets C is generally not concerned with producing minimal output, since the C optimizer will strip away superfluous stuff, so the focus is more on keeping the backend simple.
But in the given example, shouldn't the compiler be able to see, via a simple analysis, that this function is only being applied to lists of numbers?
> since the C optimizer will strip away superfluous stuff
That's a huge assumption; in practice I have not seen any optimisation that would take that Scheme-compiled C program and turn it into one a C programmer would write (if there was, I think it could certainly make Scheme a lot more popular), and I've been looking at compiler output for over two decades now. There has been improvement but not that much. There's also the question "why even generate 'superfluous stuff' if it's going to disappear anyway?"
To paraphrase an old saying, "with great flexibility comes great complexity."
No, that's the beauty and curse of dynamic languages such as the Scheme mentioned here. Of course, you could do special optimizations, such as inlining bindings that never get used out of scope or defining special functions that don't operate on real Lisp data structures but plain C structures, but they add extra complexity and duplicated logic to the compiler. I'm sure those kind of optimizations would be out of scope of this article.
> in practice I have not seen any optimisation that would take that Scheme-compiled C program and turn it into one a C programmer would write
Obviously Scheme code is going to look different than C code, they're different languages. I think the point being made was that it's okay to emit some C code that's a little extra verbose, doing things like defining extra vars and such, knowing that the compiler will simplify many such things.
> There's also the question "why even generate 'superfluous stuff' if it's going to disappear anyway?"
To keep the compiler's implementation simple and understandable. The more complex output it has to produce, the harder it is to read/write/debug.
I am not talking about optimizations that require understandings of the source language. But, for a simple example, a Pascal-ish language may have the statement
x := (a+b)*(c+d)
_t1 = a + b;
_t2 = c + d;
_t3 = _t1 * _t2;
x = _t3;
Note that this is just one of many things that contribute to the verbosity of compiler output, not even necessarily a major one in this case.
Awesome read. Thanks.
http://www.printfriendly.com/print/?source=site&url=http%3A%...
You lose some worthy css (code syntax coloring) but otherwise it's pretty nice. (requires javascript)