The Lone Lisp Heap

https://www.matheusmoreira.com/articles/lone-lisp-heap

by stevekemp • 2 months ago

94 30 2 months ago

PaulHoule• 2 months ago

You can learn a lot developing a language and runtime but you will reach a point when you'll realize you can go back and do it all better.

matheusmoreira9• 2 months ago

No doubt. The second attempt is always better. My initial plan was to write a complete first implementation in C so that it's always possible to bootstrap the language, then write a compiler inside the lisp itself, or write a Rust version. Hope I somehow manage to do it all before I die of old age.

zabzonk• 2 months ago

The second attempt is always better.

Um, see The Second System Effect.

https://en.wikipedia.org/wiki/Second-system_effect

exe34• 2 months ago

Aha I've been semi-vibe-coding a scheme for esp32c3 and linux at the same time, and forgoing the libc too, so baremetal c. I went with a slightly awkward approach for allocation, with heap being seen as pages, and within pages, fixed size objects of size 8, 16 or 32 bytes. A pair is two words, and either bitpacked or pointer to another object. I'm not far in, vaguely following the Peter Michaux approach.

cultofmetatron• 2 months ago

this is my favorite thing about agentic coding. its super easy to build a v1 and get the system to a point where it does what you want which means you learn what you need for the v2 much faster

mhb• 2 months ago

Also building furniture.

NetMageSCW• 2 months ago

Flashbacks to when I implemented a new storage system for a Lisp/Prolog system while porting the core code from Pascal to C. We stuck with linked list of pages so we could keep pointers and gain some speed over array indexing for every object access.

matheusmoreira9• 2 months ago

That's cool! Can you post more details? In my benchmarks the contiguous heap dramatically improved cache utilization. How did you obtain higher performance with linked lists?

dullcrisp3• 2 months ago

I don’t know too much about this, but strictly based on the name I assumed that you should use a heap. Is that not right?

matheusmoreira9• 2 months ago

Do you mean heap, the data structure?

https://en.wikipedia.org/wiki/Heap_(data_structure)

That is indeed nowhere to be found in the article. Heap is also used to refer to dynamically allocated memory, which used to be implemented via a heap segment.

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

https://en.wikipedia.org/wiki/Data_segment#Heap

dullcrisp3• 2 months ago

Yeah upon looking it up it appears to have nothing to do with the data structure.

When they were doing a linear scan to find a large enough free block I was waiting for a heap to come into the picture, but apparently it’s not done that way.

Someone2• 2 months ago

FTA: “Lone is a lisp interpreter written in freestanding C. There is no dynamic memory allocation in freestanding C. There is no such thing as malloc. There is no libc. There is only me and the code. If I wanted malloc, I would have to write it myself.

[…]

mmap is awesome but Linux's got something even more awesome: mremap, which makes it almost trivial to manage the page-based heap.“*

⇒ they are using “freestanding” in a non-standard way. Usually, it means running on bare metal without an OS (https://en.wikipedia.org/wiki/Standalone_program: “A standalone program, also known as a freestanding program, is a computer program that does not load any external module, library function or program and that is designed to boot with the bootstrap procedure of the target processor – it runs on bare metal”

shakna• 2 months ago

They're using "freestanding" as in "-ffreestanding" [0].

"C built to compile with freestanding mode", rather than "C built to run bare metal".

[0] https://gcc.gnu.org/onlinedocs/gcc/C-Dialect-Options.html#in...

matheusmoreira9• 2 months ago

Freestanding as in freestanding C. Lone passes the -ffreestanding -nostdlib flags. No external modules, libraries, functions or programs are loaded by the interpreter.

It's true that lone doesn't run on bare metal. I chose Linux for pragmatic and philosophical reasons. I'm not sure lone would ever have printed hello world if I hadn't chosen to build on top of Linux, which is also the only kernel with a stable binary interface. No other system lets you avoid the libc.

Someone2• 2 months ago

Of course you’re free to make your own choices, but I find it weird to accept relying on many lines of Linux kernel code and then not wanting to reuse a relatively small number of lines of an existing malloc.

The reverse (running on bare metal and tweaking an existing malloc to run on it) looks way more logical to me.

No other system lets you avoid the libc.

On most OSes [1] it’s relatively easy to write a libOS that just wraps the system calls. Your only dependency would be on the mapping to syscall numbers.

[1] OpenBSD is/may be (I don’t know the status of these) an exception. See https://man.openbsd.org/pinsyscalls.2, https://lwn.net/Articles/949078/

throwaway58670• 2 months ago

Such a delight to read a technical article, and about something outside the hype cycle.

I also liked the color scheme.

matheusmoreira9• 2 months ago

Thank you! I'm glad you enjoyed it. I'm already writing the next one!

adelmotsjr• 2 months ago

As a Brazilian, i'll let my nationalism escape a little bit to say that it is awesome to see such an incredible work done by a fellow brasileiro. This gives me the same feeling of awesomeness that I get when I see José Valim's work on Elixir.

I only wish I could be as diligent and focused to do a thing like this, because I think it would be so much fun. I bought the Crafting Interpreters book a while ago, but still haven't got time to actually go through with it.

Well, maybe one day...

matheusmoreira9• 2 months ago

Thanks, that's high praise! I highly recommend Crafting Interpreters. Bob Nystrom is among my favorite authors. You should read his blog too.

quibono• 2 months ago

If I'm not mistaken there's also the author of Starlette / FastAPI

The Lone Lisp Heap

Related Stories