Henry Baker

you might enjoy this classic then: http://www.pipeline.com/~hbaker1/LinearLisp.html

Perhaps a few points of clarification are in order, my original comment had too many different threads mixed together. I will first try to expand on my remarks on copying and then try to respond to some of the things you said. When you look at the categories in use by mathematicians a surprisingly large number of them are not cartesian, this is true in particular of the categories relevant to physics, where both the category of symplectic manifolds (relevant to classical mechanics) and Hilbert spaces (relevant to Quantum Mechanics) are monoidal and not cartesian. In both cases you therefore can not copy states. Moreover in physics things are local in the sense that the dynamics of a physical system is usually determined by differential equations. That means there is typically no situation where you have to retain much of the state of the system for a long time in order to simulate its behavior. Even for complicated things like PDE simulations, what you really do is approximate some infinite dimensional function space locally with finite dimensional vector spaces. The state space in each step of the simulation is some tensor product. So while a computer certainly allows you to do it, it isn't really natural to constantly copy state in such simulations. Abstractly a Fortran 77 program could probably described by a collection of morphisms in some traced monoidal category, so it doesn't seem too far off from the mathematics it was invented to implement, although ultimately it…

Pretty cool, but 2 pointers of overhead per object is a lot. The linked-list approach to garbage collection is also going to produce a lot of memory fragmentation compared to arena-based collectors. The docs also suggest calling `ugc_step` multiple times per allocation. So this isn't a high performance solution, but the code is clean and easy to read. Related reading: http://www.pipeline.com/~hbaker1/NoMotionGC.html

The reasoning behind the naming is outlined here: http://www.pipeline.com/~hbaker1/CheneyMTA.html. It's a fun read and once you see the lyric it's based on, it makes a lot more sense.

The illustrious Henry Baker, based on the slightly earlier (and extremely influential) Linear Logic. http://www.pipeline.com/~hbaker1/LinearLisp.html There's a conceptual relationship to SSA (static single assignment) http://en.wikipedia.org/wiki/Static_single_assignment_form

There is no special call stack manipulation in the CL condition system. It's built on top of dynamic scoping and normal catch/throw unwinds; see http://www.pipeline.com/~hbaker1/MetaCircular.html for block/return-from on top of catch/throw.

See also: http://www.pipeline.com/~hbaker1/CheneyMTA.html It looks like work/research in this area has been going on for at least ~20 years.

I recommend Lisp In Small Pieces (LISP) by Christian Queinnec and Compiling with Continuations by Andrew Appel if you're interested in writing a functional compiler. Also: http://matt.might.net/articles/cps-conversion/ http://lucacardelli.name/Papers/BasicTypechecking.pdf http://library.readscheme.org/page1.html https://research.microsoft.com/pubs/67083/spineless-tagless-gmachine.p… http://www.pipeline.com/~hbaker1/CheneyMTA.html

> but if there are no normal returns involved, nothing on the stack will ever be deallocated, and your program is effectively just one giant memory leak. This is true, but there is the glorious exception which is "Cheney on the MTA": http://www.pipeline.com/~hbaker1/CheneyMTA.html [https://news.ycombinator.com/item?id=7417906] This describes a way of implementing a scheme->C compiler using CPS which allows the C functions to never return, and doesn't blow the stack. When the stack gets big enough, you do a garbage collection run, copying live data to a new stack. Then, you reset the stack pointer using a judiciously chosen argument to alloca().

Here are some relevant papers from Henry Baker on garbage collection: Lively Linear Lisp -- 'Look Ma, No Garbage! http://home.pipeline.com/~hbaker1/LinearLisp.html NREVERSAL of Fortune[1] -- The Thermodynamics of Garbage Collection http://www.pipeline.com/~hbaker1/ReverseGC.html

Interesting... I still feel that this is for the most part merely deferring the free-ing work to when you next allocate an object. It may succeed in getting the "free" cost down to a single instruction--checking a mark bit--but it is still a cost per dead object that a copying GC wouldn't have to pay. (The difference may be, as some say, "academic".) It does have the slight advantage of reducing the maximum pause time due to sweeping down to being proportional to live objects rather than garbage. Also, what if you want to allocate a large object? You might have to skip over some unmarked cells. Either you'd waste the memory, or you would probably want to put them on a free-list of some sort, in which case you are doing more than just bumping a pointer and checking for a mark. ... I see, it says "equally-sized chunks of memory". Still, that's a cool idea. As mark-and-sweep goes, anyway. :-} I'm rather more fond of copying garbage collectors--I like the determinism, the fact that (normally) the memory address of each object after a full copying GC will depend only on the structure of the graph of objects, and not on the memory addresses of the objects prior to the GC. (In other words, it destroys the information "what the memory address of each object was before this GC". This implies a somewhat higher inherent cost, to eliminate this entropy. See [1] for musings about the relation of this to thermodynamics.) In particular, whether you have fragmentation issues…

Henry Baker's "Cheney on the M.T.A." paper (which is the basis for the stuff described here) is very nice. There's a collection of Baker's research papers here: 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).