Bone Lisp – Lisp Without Garbage Collection

Have you looked at scheme from scratch[1]?

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

Have you looked at lisp500 ?

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

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

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

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

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...

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

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/

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.

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

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.

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...

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

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

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.

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.

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.

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.

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..

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.

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.

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.

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...

Is that what individual Erlang processes do?

I wonder if you could use ropes[0].

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

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

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

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...

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

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.

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.

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

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.

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

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.

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

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.