Hacker News new | comments | show | ask | jobs | submit login
Bone Lisp – Lisp Without Garbage Collection (github.com)
113 points by spraak on June 7, 2016 | hide | past | web | favorite | 85 comments



Since ulisp (lisp for Arduino) came up on HN the other day, I've been trying to implement a lisp in C with garbage collection that will run on my x86 machine (your usual macbook).

It being my first ever "real" c program, I'm not quite there yet. Very curious to read more source code of small languages, preferably things that are implemented in one file only.


If you just want a GC, here's a tiny one I wrote:

https://github.com/munificent/mark-sweep

And an article I wrote about it:

http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar...

This was the inspiration for uLisp's GC (http://www.ulisp.com/show?1AWG). :)

If you want a more full-featured but still small language in C, you could take a look at Wren:

http://wren.io/

https://github.com/munificent/wren


I am using your blog post about the mark and sweep-GC for my program! Thank you for publishing it! Very informative, entertaining and to-the-point. Thank you!


You're welcome! I'm glad you enjoyed it. It was a lot of fun to write.


Perhaps you'd enjoy some of my old Forth projects. I designed a portable VM with a Forth-based development toolchain and standard library. Included among the programs I wrote using this system were a variety of compilers and interpreters.

FiDo, a tiny JIT compiler: https://github.com/JohnEarnest/Mako/blob/master/demos/FiDo.f...

A Logo interpreter: https://github.com/JohnEarnest/Mako/blob/master/demos/Loko/L...

A garbage collector used by a number of games and programs: https://github.com/JohnEarnest/Mako/blob/master/lib/Algorith...

A custom systems programming language targeting the VM (Java) https://github.com/JohnEarnest/Mako/tree/master/tools/Stroye...


Wow, a full blown Logo interpreter written in Forth! Very cool! Nice looking code. Thanks for sharing!


Loko (and many of the other programs) can be run interactively here:

http://johnearnest.github.io/Mako.js/?rom=Loko

Unfortunately some browsers have decided that backspace should navigate back, which makes typing at the Loko REPL rather awkward.


Depending on how neurotic you want to get, Andrew Appel spent years working on SML and other functional programming language compilers and has written a few books about how to do it well. Namely, Compiling with Continuations:

http://www.amazon.com/Compiling-Continuations-Andrew-W-Appel...

and Modern Compiler Implementation in ML:

https://www.cs.princeton.edu/~appel/modern/ml/

There's a certain kind of equivalence between continuations and SSA. Mostly, I bring that up because if you go down the rabbit hole of designing a compiler in C, you'll find talk of SSA, but continuations are somewhat advantageous for designing functional compilers. If you're just looking to design an interpreter, Ben Pierce's book Types and Programming Languages does a good job at showing how to put together a simple functional language both theoretically and practically:

https://www.cis.upenn.edu/~bcpierce/tapl/


Have a look at this if you want a guide: http://www.buildyourownlisp.com


Have you looked at scheme from scratch[1]?

[1] http://peter.michaux.ca/articles/scheme-from-scratch-introdu...



All the other comments here are good. You might also want to take some advice from the SICL-project -- don't bootstrap from C, bootstrap from (a) lisp. If not Common Lisp, maybe Racket?

(Not that writing a lisp is a bad way to learn C of course!)

[1] "A Modern Implementation of the Common Lisp LOOP Macro", European Lisp Symposium https://www.youtube.com/watch?v=ZJr81DtSwUc

https://github.com/robert-strandh/SICL


Very bare-bones implementation in one source file (+ 1 header) https://github.com/pedro-onate/eva/tree/84a62881c610ef23f9f1....

Later versions include GC, and bytecode compiler + VM.

Edit: I highly recommend SICP (dense, but elegant), and Matt Might's blog as resources.



Look here is a Racket (My Favorite Lisp) https://github.com/fraimondi/racket-asip

A Racket client for the Arduino Service Interface Protocol (ASIP)


Have you looked at lisp500 ?


Norvig's lispy (lisp in python) is a good one, http://norvig.com/lispy.html


This makes me wonder whether it would be worthwhile to design languages with no garbage collection or manual deallocation. Non-stack memory can be allocated but never freed, and memory exhaustion would be fatal.

We might be at the point where this is an acceptable simplification for very fine grained processes and services. Has anyone explored this model?


I'm exploring something similar in my project: https://github.com/akkartik/mu. Where C was designed as a more portable+expressive assembly language, Mu is designed as a more portable+safe assembly language. You have to manually manage memory, but you can't ever end up corrupting your heap or using pointers after free. I provide these guarantees by allocating a refcount with every single allocation. The only way to reclaim memory is to clear a pointer. If you happen to still have other pointers to the allocation you won't actually reclaim it.

Given this setup I can prototype programs without thinking about memory at all. When my program runs out of memory I start measuring allocations and insert the odd pointer clear at strategic places until I don't, then I continue on my merry way. 99.9% of programs we write don't require thinking of "no memory leaks" as a black-and-white cast-iron guarantee.

This setup also provides a really nice teaching experience where students can learn about pointers and write all sorts of programs without ever running into weird bugs due to use-after-free or overflowing bounds. However it adds some overhead akin to a realtime GC: everytime you copy a struct you have to increment refcounts of any pointers nested arbitrarily deep within it (Mu maintains a flattened bitmap for each type to make this not utterly suck). Sum types get even crazier, because you might have a pointer at offset x depending on the state of the tag at offset y, and so on. I'll try to measure the overhead at some point..


>The only way to reclaim memory is to clear a pointer. If you happen to still have other pointers to the allocation you won't actually reclaim it.

Elegant! It's funny though, on persistent storage we sort of invented this decades ago in the form of hard links. You can have as many hard links as you want to a file, and the file will only be deleted when all links are removed and all file handles are closed.


Yes, reference counting is one of those things that keeps coming up everywhere.


This is basically "leaky" reference counting, yeah?


Yes, the mechanism is exactly reference counting. However, the goal is totally different. Typically refcounting is used for automatic memory management. Here the goal is safe manual management. (The different goal means that refcounting's well-known inability to collect cycles is irrelevant, among other things.)


This is probably already possible in several language implementations just by telling them to turn off their garbage collector.

After all, the essential rule behind garbage collection is that all variables are available to a program for ever - yet the implementation is allowed to clear up memory if it can prove that a value can never be retrieved again (for instance, because all references to it have gone out of scope).

It has also crossed my mind that a large number of small, terminating programs might well be better off running to completion without any collection taking place. But language implementors are pretty smart - probably quite a lot of the small programs you have in mind already /do/ run right through without ever doing any garbage collection.


You could just use C (or any other non-GC language) and opt out of freeing your memory. That it is done sometimes (not always intentionally, of course). The DMD Compiler for example:

"DMD does memory allocation in a bit of a sneaky way. Since compilers are short-lived programs, and speed is of the essence, DMD just mallocs away, and never frees. This eliminates the scaffolding and complexity of figuring out who owns the memory and when it should be released. (It has the downside of consuming all the resources of your machine if the module being compiled is big enough.)"

http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...


The Qt C++ also allocates but never free a certain amount of memory. A lot of programs and libraries take the view that if you're going to allocate memory and keep using till the end, why bother freeing it?

The downside to this is it makes it difficult to use tools like Valgrind that trace memory allocation in one's own program.


There are two significant downsides to freeing blocks of memory that are in use when program exits: 1) it's completely wasted effort to track who should free some global structure that gets allocated and then exists until program ends (global singletons, various caches...) 2) freeing all objects when program exits puts completely unnecessary pressure on OS's VM subsystem (it's not so long ago that closing long-running firefox or openoffice caused linux desktop to just freeze and swap for few seconds)

Maybe I'm in minority but in C I tend to flag unnecessary free()'s before program exit in code reviews (There is not much that you can do about that in "safe" languages like C++).


I'm not saying this somewhat common method is necessarily bad.

I'd just mention it makes tracking memory allocation harder for an end-user of an application framework that does. In those instances, it might be nice to, say, disable this approach with compiler flag or something.

Edit: it also depends on how concerned you are with memory leaks. Making sure every single allocation has a delete attached is a simple rule. The rule of "every allocation has a delete, except the allocations we're sure will last for the life of the program", making sure that rule is followed seems a little harder and presents a "mental overhead". This kind of thing probably depends on how prone to memory leaks your program is (I've seen big, messy, memory leak prone programs where "oh this one isn't deleted 'cause of optimization" would make the leak-detective's job just that much harder).


Hash consing is a 1970s Lisp technique for supporting this that was recently rediscovered as "string interning": https://en.wikipedia.org/wiki/Hash_consing

In general copy-on-write schemes would be useful for this, and some persistent data structures can be as well.

JonL White wrote a paper about this idea in 1980: http://3e8.org/pub/scheme/doc/lisp-pointers/v1i3/p17-white.p... (favorite quote: "GC Once a Year: Enough?")

Rivest and Shamir wrote an interesting paper on write once memory in 1982 that I feel might have some non-obvious applications to this: https://people.csail.mit.edu/rivest/RivestShamir-HowToReuseA...

Linear types (http://home.pipeline.com/~hbaker1/LinearLisp.html) is a closely related idea in terms of avoiding garbage collection that has very useful concurrency properties. Most time-of-check-to-time-of-use and kernel/userspace race conditions would be prevented by using linear types for system call arguments. IMO linear types have enough benefits outside of memory management to make the trade-off of using them worth it vs the other techniques mentioned above.


Another interesting possibility for an immutable language would be a generational copying allocation with two young generations and no collection of the old generation. Immutability would guarantee that you only have to scan the young generations, two young generations would catch practically all of the ephemeral garbage, and so long as they are small enough to fit a close level of cache, collection would be really fast.


Immutable languages tend to produce more garbage in the old generation than mutable languages such that this approach is not going to work reasonably (easy to find useful piece of software written in mutable language that produces no garbage in the old generation, while any state changes in immutable languages will invariably produce garbage).

On the other hand, generational GC is almost trivial to implement for immutable languages, exactly because there is no need for write-barrier. BEAM's GC is perfect example of how trivial can well performing GC be in that case (and good study material that is perfectly relevant for runtimes with mutable objects).


I believe there was a comment here recently about someone writing software for airplanes, mentioning how after power up, and when the plane was in the air, no new allocations were allowed. So it's not unheard of.

Speaking of safe software, I came across a free chapter/snippet on memory and safety in Ada[1]:

"(...)Restrictions

There is a general mechanism for ensuring that we do not use certain features of the language and that is the pragma Restrictions. Thus if we write

   pragma Restrictions(No_Dependence =>
     Unchecked_Deallocation);
then we are asserting that the program does not use Unchecked_Deallocation at all – the compiler will reject the program if this is not true.

There are over forty such restrictions in Ada 2005 which can be used to give assurance about various aspects of the program. Many are rather specialized and relate to multitasking programs. Others which concern storage generally and are thus relevant to this chapter are

  pragma Restrictions(No_Allocators);
  pragma Restrictions(No_Implicit_Heap_Allocations);
The first completely prevents the use of the allocator new as in new Cell'( ... ) and thus all explicit use of the heap. Just occasionally some implementations might use the heap temporarily for objects in certain awkward circumstances. This is rare and can be prevented by the second pragma.

Hint: Ada is also a high level language that allows low-level programming, and might be fun for writing a lisp ;-)

[1] http://www.adacore.com/adaanswers/gems/gem-43-safe-and-secur...


See for example Structured Programming with Limited Private Types in Ada: Nesting is for the Soaring Eagles, by Henry G. Baker.

(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39....)


An aside:

Tolpin and Toft designed an extension to the functional language ML which used region based memory managed instead of traditional garbage collection for ML.

This lifted the lifetimes of variables into ML's type system (!!!) while the underlying implementation IIRC could achieve O(1) memory behaviour except when an exception occurred.

While this sounds amazing, there were draw-backs on the implementation / theory as certain optimisations were near necessary to get good performance. I.E. word sized integers had to live in the heap as opposed to registers. Another issue was that loops had to be restructured from idiomatic ML style to a slightly different one, other the region inference logic would cause O(N) allocations in a loop which would otherwise use O(1) allocations.

http://www.elsman.com/pdf/retro.pdf

or "Tauplin and Toft region based memory management retrospective" should lead you to the paper.


Just check Ada and Spark.

The main issue is that in most cases the complexity increase is not worth the trouble.

So such languages end up being used in embedded systems and high integrity deployments. Usually where human lifes are at risk.


Just because memory can be freed doesn't mean it has to; the programmers can choose not to.

The mode of not freeing has been explored in programs that are short-lived and run on top of an OS that reliably cleans up memory. For instance, system utilities and compilers and such.

Got a C program that crashes due to premature allocation, according to Valgrind, and it is hard to figure out why? It it just a short-lived utility that does some job and exits? Then just #define free(p) ((void) 0) and rebuild.


Or because it's considerably faster—if you don't have to deallocate, you can just reserve a bunch of pages on startup and use a stupid simple bump allocator.

Actually, D's compiler more or less works this way: http://www.drdobbs.com/cpp/increasing-compiler-speed-by-over...


I have seen a program, which meticulously freed everything on shutdown, take over a minute to actually do so under a large and complex test case involving lots of data. In production use, this would be a complete waste of CPU cycles.



> The mode of not freeing has been explored in programs that are short-lived

[fork, allocate, exit] is a very valid and robust pattern leveraging the OS as a garbage collector.

This kind of pattern reminds me of crash-as-an-operation-mode software.


That's a fine solution, but you're going to cause some weenie manager's head to explode.

Also, some hapless intern is going to copy a chunk of code out of your project in their new project and then give you hell because their program leaks memory like crazy.

Also, some mid level manager is going to decide that all code must be run through static analysis and come out cleanly and you're going to have a bad day.


Good luck explaining that one in the code review :p


https://blogs.msdn.microsoft.com/oldnewthing/20100809-00/?p=... I don't know anyone who has practically implemented it though.


This project uses reference counting to deallocate memory, so memory is being freed when it is no longer used.

However, the paradigm you're referring to is interesting. Short-living processes that allocate little memory could work. Also, servers could use this model: create a slab of memory for each request, and allocate memory on that slab when processing the request. When the request is completed, you can free the entire slab at once. I know the Ur language does something like this.


I did this 20 years ago. My allocator had multiple regions (slabs) that were tuned to specific allocation patterns and lifetimes, with different algorithms for managing block size, fragmentation handling, and freeing. We could turn on detailed allocation/free logging, which included the file/line the action took place. From this we could put the system under load and then identify allocation hotspots and build models on block size and lifetimes and tune the allocators from that. It was pretty cool.


Your take on the server usage of this idea is widely implemented. But the usual approach is not to allocate large block of memory and allocate from that, but to wrap malloc() with function that adds headers that track purpose of the allocated block and then free all still live blocks when the purpose ceases to exists. Both Apache and Samba uses generalized mechanisms for this (apr_pool and talloc, respectively), while PostgreSQL does the same thing in somewhat ad-hoc manner.


This is called regions and was quite common a few decades ago.


Which are used by Bone Lisp:

It uses explicit regions instead of garbage collection.

Explicit regions are both very simple and very fast, but how far can one get with them? I want to find out, so I am developing this interpreter.

So we've come full circle.


To come full circle we would need people to accept the great research done at Burroughs, DEC/Olivetti, Royal Navi, Xerox PARC, Genera, ETHZ, MSR... in what concerns safe systems programming.


But are there any non-paywalled digital accesspoints to this?


Lots of them.

All research of Interlisp-D, Smalltalk and Mesa/Cedar at Xerox PARC:

https://archive.org/details/bitsavers_xerox

Stéphane Ducasse also maintains the original Smalltalk manuals on his legacy books:

http://stephane.ducasse.free.fr/FreeBooks.html

Oberon at ETHZ:

http://www.ethoberon.ethz.ch/books.html

If you want to see how the latest incarnation of Oberon used to look like:

http://www.progtools.org/article.php?name=oberon&section=com...

For Modula-3 it is a bit harder, because of DEC/Olivetti being acquired by Compaq, which was then acquired by HP. So lots of sites are full with broken links.

So the older books are a better source than the Internet.

But still you can get some info here:

http://www.modula3.org/

http://ftp.labs.hp.com/ftp/pub/dec/SRC/

http://www-spin.cs.washington.edu/

Burroughs overview:

http://www.smecc.org/The%20Architecture%20%20of%20the%20Burr...

It lives on as Unisys MCP mainframes. There are some more informations when searching for it.

Algol-68RS used at Royal Navy:

https://en.wikipedia.org/wiki/ALGOL_68RS

This is just a small taste. If one cares about history of computing there are lots of other resources scattered around the web and libraries.


Cool, thanks!


Could probably do this in Lua or other embedding-oriented languages where it's easy to create and discard interpreters willy nilly in the host environment.


its been common practice in embedded/real-time systems to make everything static.

dynamic memory allocation is frowned upon... to many issues with fragmentation and non-deterministic behaviour.


How would it change the design of the language though, compared to a language with garbage collection?


I don't think it would. Implementation of the language would be easier, though, and I suspect that knowing that memory is not reclaimable might act as a beneficial constraint on design.


Is that what individual Erlang processes do?


As someone who hasn't dealt with Lisp since the 1980's, help me out here. Immutable structures and Lisp seems to be incompatible, as Lisp's lists are about the most mutable things you'll ever see.

If, for example, I want to put a value into the middle of a list, would I be doing something akin to. . .

MyList = MyList.firstHalf + NewValue + MyList.secondHalf?

And how doesn't this become a horrible bottleneck?


You can represent the list as a zipper data structure[1]. The idea is to represent a "cursor" pointing to some point in the list as a triple: (list of points before, point at current position, list of points after). So a zipper for an arbitrary list "xs" pointing to the beginning would be (() (car xs) (cdr xs)). There are some things you can do to handle the case with empty lists, which I'll leave to the reader :).

Given a zipper (as x bs) you can move the cursor right (rather, compute the zipper with the cursor one step further to the right, since we're purely functional) as ((cons x as) (car bs) (cdr bs)). You can insert a new element "y" into you current position by computing (as y (cons x bs)). If you discard the old version of the zipper every time you move or insert, this will use the same amount of memory as just storing the list, and you get insertions in O(N) time and O(1) memory. There's a whole field devoted to making data structures like this for purely functional languages, and this zipper concept extends itself rather naturally to trees.

[1]https://en.wikipedia.org/wiki/Zipper_%28data_structure%29


They are not necessarily incompatible. Historically, Lisp pairs are mutable, but that doesn't have to be the case. See Clojure, it is Lisp-like, with most data structures immutable.

Your example is not possible in an immutable list. Also note that this reassigning of variables is a red flag even in standard Lisps. In fact, variables are not that common. The most common way of referencing something for later usage is the let form, which already creates new "variables" anyway. Just eliminate ways to reassign them (setf?).

What you would do is to create a new list containing the elements you want. You may or may not want to give it a new name afterwards. Most likely, you'll use as it is and pass on to some other function.

I can't comment on this particular implementation. But it does not necessarily have to be a bottleneck. In fact, by having immutable data structures, that means that you can share data like crazy, without fear of anything being replaced where it should not. All sorts of optimizations are enabled that wouldn't be possible otherwise. If this implementation uses them, it's another matter entirely. No idea.


Generally you build the new list using the tail of the old list (which is unchanged), your inserted value, and each of the values in front inserted onto that. So, immutability is preserved. Any existing references will not see their values changed. And the new references will share some memory with the old ones (how much depends on where in the list the value was inserted).

You can learn more in Okasaki's great book: http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...


Actually Common Lisp and Scheme have a clear distinction between mutating and non-mutating list functions. They even have a naming schema to distinguish between, and most books focus on the non-mutating, in Common Lisp speak "nondestructive" list functions. Functions like append, remove do not mutate the input list, but (partially) new lists, which can share sublists with the input lists. For example (append a b) returns a list which contains a copy of a and the original b.


I wonder if you could use ropes[0].

[0] https://en.wikipedia.org/wiki/Rope_%28data_structure%29


I may be misreading this, but isn't that an example of lists being immutable rather than pervasive mutability?


Do not put a value into a middle of a list.

Read Chris Okasaki, "Purely functional data structures" for better options.


structural sharing is what clojure does. But you can have immutable data structures in old lisps if you only use cons, car and cdr, avoiding set-car and set-cdr.


Garbage collection should be in the hardware.


Intel tried this in the early 80s: https://en.wikipedia.org/wiki/Intel_iAPX_432


Wow, the iAPX 432 sounds really cool. It contains a lot of ideas that I wish had taken off. Pity it failed.

That failure might prove that those ideas were bad. But I think it just proves that MS-DOS compatibility is really, really important.

Weep for humanity.


I always see those failures more as political than technical.

How mankind would be if there weren't a few lunatics that kept on trying to fly and fail?

Just to cite one example from many.


You are so right. One cannot succeed in technology outside of politics.


And SMBX.


It would be cool if the garbage collector could be written in the language itself.


In this case a garbage collector is unnecessary. In this Lisp, list structures are immutable, which means it is impossible to create a list with a cycle. Thus, the interpreter can use basic reference counting without fear that anything will leak.


In Haskell, data are immutable and yet cyclic structures are possible.

  allOnes = 1 : allOnes


This is possible in Haskell because it allows for lazy evaluation. In a strict language, immutability means you can't form cycles.


While non-strict evaluation helps with forming cyclic structures in general, in this specific example it is not required. You just need a language that allows names to appear in their bindings, such as in C:

  struct node { int x; struct node *next; } allOnesList = { 1, &allOnesList }, *allOnes = &allOnesList;


For normal lisp implementations, allowing names to appear in their own definitions requires lexical environment frame to be mutable, which breaks the assumption that all notionally on-heap objects are immutable.

This observation is somewhat relevant to the weird semantics of "lexical" scoping in Python, because the obvious semantics would cause cycle between frame object and function defined in it's scope.


Haha, I hadn't thought of that! That ability to create self-referential data is the main factor. That isn't really possible in lisp without some sort of letrec function, which this lisp shouldn't support. You would also have to watch out for recursive function definitions. Usually, the function body will just contain the symbol that refers to the function, which conceptually is similar to a straight pointer to the function, and someone might try to optimize it that way.

In fact, with more thought, I realized the lazy evaluation is actually orthogonal to forming cyclic data. The "allOnes = 1 : allOnes" line doesn't necessarily form a cycle (depending on the interpreter/compiler, I imagine ghc and any other sensible implementation will form a cycle). Naively, this will just create a thunk which will get repeatedly evaluated, generating a long list of ones.

EDIT: Nevermind, you're right.


Thunks don't get repeatedly evaluated, sorry. Just once at most.


Can't rplaca rplacd and setf destructively modify list structures?

https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node150.html


How about closures? Don't they allow cycles to be formed?


I think because everything is immutable and because lexical scoping I can't figure how this would happen other than a direct cycle which I think the reference counting might be able to figure out.

I am curious as well though. Maybe you could show an example?


It's been done as other comments pointed out. But the fact that you can do it is mildly interesting, isn't it? It's a sort of bootstrapping problem.

Obviously you can't trigger full GC in your GC code. So you have to write GC code in such a way that it won't trigger GC or, in some cases, very limited mode of GC that you know is safe to perform at that point. It is trickier in languages that implicitly allocates. Traditionally, Lisp programmers are pretty aware of what operation would allocate and good at avoiding them. Plus, an implementation often provide a primitive to turn off GC in certain regions. Another approach is to design a subset of language with guaranteed safety properties and implement the core part of GC with it.


I've seen this in various Lisp implementations. And the Boehm collector is written in C for C.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: