path: root/notes/260825-code-gc.md

# Memory management of code

_August 2026_

If you're implementing an interpreter for a homoiconic language like
Lisp that is also garbage collected, there's the issue that, since
code is data, code is subject to GC.

That's a problem if you care about GC efficiency, because a program
isn't likely to have its code change much after it's been loaded up.
You may be modifying a module of code at run-time, meaning that some
parts of the module's code become dead, but that's a rare exception.

So, most of the time, you'd be scanning lists that make up the code
over and over again, even though they are very unlikely to ever die.

A generational GC makes this less bad, since the lists making up the
code will be promoted to some "ancient" generation eventually, but
perhaps there's a good solution that doesn't have to rely on that.

As part of my plan to transform code expressions into an optimized
form that's similar to bytecode, I will already be changing the type
tags on NaN-packed representations of code forms.  The GC might then
simply ignore these.

Let's consider the consequences...

Start by looking at the in-memory representation of a module after
said optimization has been performed:

    {
      name = 0x1111 -> <list: (my cool module)>
      version = 1234
      bindings = 0x2222 -> <hash_table: [
        {
          key = 0x1234 -> <identifier: foo>
          val = 0x2345 -> <box: 0x3333> -> <code: (let ((a b)) c)>
        }
        {
          key = 0x3456 -> <identifier: bar>
          val = 0x4567 -> <box: 0x4444> -> <array: [x y z]>
        }
        {
          key = 0x5678 -> <identifier: MY_CONSTANT>
          val = 0x6789 -> <box: <fixnum: 12345678>>
        }
      ]>
    }

Hopefully that's somewhat reasonable of a graphic.  The module is
presumably something like a struct, that may have a name and version
and whatnot, and then a pointer to a hash table which maps identifier
(pointer) keys to box (pointer) values.  The boxing of the values is
so that other modules have a stable address to point to; the binding
table getting resized and having all its contents moved won't break
references to this module's bindings from an importing module, and
neither will rebinding an identifier cause breakage.  If a binding
gets removed, it should not really be removed from the table but
rather have its value box be overridden with some kind of dummy
"undefined" value; otherwise things become unsafe.

In this example, the bindings include a code form, an array, and a
fixnum constant.

The GC would walk the bindings table, making sure to mark the array,
and traverse it too if it's a Value array, but it would skip over the
pointer to the optimized code form, which it refuses to traverse.

This means the entire graph of objects that make up a code form must
not be collected, and must not contain pointers to outside the graph.
It's a self-contained object graph that's "pinned" in memory.

Another way to look at this is in terms of ownership semantics: All
objects in the code form graph are owned by the module, exclusively.
They may not be shared.

Given this invariant, modifying the module by rebinding 'foo' to new
code can safely explicitly deallocate the old code form.  We can have
manual memory management in the runtime for this particular case.

But how to ensure the invariant?  There are three concerns:

1. Code forms must not contain direct pointers to the values of the
   bindings of another module; not even to the boxes.

   This is solved by having a dedicated NaN representation for these
   kinds of module binding references, that aren't seen as a pointer
   by the GC.  The current NaN-packing scheme doesn't actually have
   room for this, but I'm thinking of using a trick where a module's
   top-level is considered a lexical environment and any procedure
   that references its bindings is a closure; our NaN packing scheme
   has a dedicated representation for "reference to lexical variable
   capture" so that works elegantly.

       (define foo (list x y z))

       (define (bar) (print foo))

   In the above, `bar` is bound to a code form containing a lexical
   variable reference to `foo`; the recursive `free()` calls on the
   code form graph skips over these lexical references.

   The same principle applies to imported bindings; they are simply
   considered part of the top-level lexical environment of a module,
   within which a procedure definition is simply a matter of binding
   an identifier to the result of a lambda expression.

2. Programmers must not abuse datum labels to construct code forms
   whose object graph shares some structure with code/data forms
   outside the code form.  If you do that, it's your fault:

       (define (foo a b) (* 2 #%1234=(+ a b)))

       (define (bar a b) (* 4 #%1234%))

   I mean, come on...  Use a macro.  If you do this, then rebind the
   `bar` procedure, the runtime will recursively free the old graph,
   leading `foo` to be left with a dangling pointer.  Exciting, or
   rather terrifying!  This really isn't how you write code on the
   regular, so I don't think it would happen to anyone by accident
   during serious software development.

3. Programmers must not manually construct code forms whose object
   graph has shared references.  If you do that, it's your fault:

       ;; foo refers to some heap object from elsewhere
       (let ((code `(lambda () ,foo)))
         (module-bind! '(my module) 'foo (eval code)))

   To be honest, this isn't an unlispy thing to do.  What if someone
   unwittingly does it, not realizing it's illegal?  I don't see any
   way to check against it; maybe we just have to live with certain
   foot-guns like this in the language for the sake of efficiency?

   Is there at least a way the programmer can fix this code?  Yes,
   using an explicit copy operation on foo.

I think this covers all pathological cases.  Given the above rules,
code forms should be possible to be excluded from GC logic.

I've thought about whether it would make sense to apply this to any
top-level binding to a heap object, but I don't think so.  Consider:

    (define full-data '(foo bar (baz bat)))

    (define part (list-ref full-data 2)) ;shortcut to (baz bat)

Now, if you redefine `full-data` you almost certainly want to also
redefine `part`, but the thing is, if `full-data` is redefined while
`part` isn't yet, for whatever reason, you don't want a segfault or
silently have `part` start pointing to arbitrary data that just so
happened to fill the spot in memory that `(baz bat)` used to occupy.
There's no clean solution but to have these objects be GC-managed.

At least until a module is "frozen" which I will get to now.


## Generalizing

This idea could actually be generalized to entire modules.  This may
make it unnecessary to special-case code forms in the GC logic.

Modules would have a "frozen" or "sealed" flag which, when enabled,
causes the entire module to be treated as a closed graph that is
skipped by GC traversal and pinned in memory.

It could still be swapped out entirely, manually freeing the entire
old object graph of the module.  This requires similar invariants as
above, just applied to the whole module.

This would resolve two issues from above: Since code forms can now
have pointers to other objects in the module, immutable top-level
bindings can have their value copied directly into the code of a
procedure.  The value in question may still be a pointer, but one
indirection layer is removed, and the lexical capture array of the
procedure is shortened.  The second resolved issue is insignificant,
because it's just the datum label crap.  Nobody needs that, but hey,
it would be possible.

The issue with manually constructed code forms remains: If you do
that, then freeze the module, then swap the entire thing for a new
version, then the old graph of objects will be manually freed, which
may include an object you had a reference to from outside the module.

Now that I think about it, perhaps `module-bind!` or whatever should
simply perform an implicit copy on the object it's provided.  That's
fairly clean of a solution, I guess.  There could be some override,
which skips the copying, for those who like to live dangerously (or
maybe even know what they're doing).


## Combining

It may be useful to always apply this optimization to code forms,
regardless of whether a module is frozen, but then also allow this
module freezing optimization, since it adds further value.

I've also thought about the ability to "statically link" modules in
the past; let's see how that might interact with this optimization:

For a module that's being linked to dynamically, being frozen or not
merely affects internal optimizations within that module: Whether the
immutable top-level bindings can be copied by value into code forms.
There's just one catch: Swapping out the entire frozen module for a
new version must reuse the boxes of the binding table, or else other
modules pointing to these end up with dangling pointers.  And if some
binding doesn't exist in the new version, it must be created anyway,
with a dummy "undefined" value inside the box, so that the code of
other modules trying to resolve that binding will cleanly error, and
not segfault or be corrupted by silently starting to point to some
arbitrary object that happened to take the position of the old box.

As for static linking, let's consider what that means in terms of
language semantics first: It's almost like copy-pasting the code of
the statically linked module into the linking module, just with one
major difference, which is that mutable state is shared with other
modules that statically link the same version of the same module.

In other words, if module S defines `foo` as a binding to a mutable
heap object, then modules A and B that statically link to S must be
able to observe mutations to said heap object.

How does that interact with freezing?

For frozen modules, it's simple: Instead of referring to the binding
boxes of the linked module, you get freedom to refer directly to the
values of the bindings, since they are frozen.  The module must also
have its current version be permanently pinned in memory, so if the
whole thing gets swapped out, any modules that had statically linked
the old version continue working.  They just don't observe the swap.

I'm trying to think about how statically linking a non-frozen module
would behave, and it leaves me a confused mess.  A non-frozen module
can't even refer to its own top-level bindings by value, so any other
module obviously can't either.  Either static linking should not be
allowed on non-frozen modules, or it should create a frozen version
pinned in memory...  Probably best to just disallow it.


## Private bindings

In some previous note, I had shown an example like this:

    (define foo 1)

    (let bar 2)

    (define (test) (print foo) (print bar))

    ;; --- becomes optimized into ---

    (define foo 1)

    (define (test) (print foo) (print 2))

Here, the `let` forms create private bindings, and as an optimization
they get copied into code that references them.  That could still be
viable, but only if the private binding has a non-heap value, since
copying in a pointer to a heap value would cause that heap value to
become freed if the procedure is freed, as part of the manual memory
management of top-level procedures.

If it's a pointer to immutable data, then the entire data could be
copied in, but that's a topic for another day, because I don't yet
know how to deal with mutability and immutability of heap types,
except for some like interned strings that are always immutable.


## Summary

* Modules are normally GC roots, and their binding table is traversed
  normally.

* Except for code forms, which are skipped by the GC, and have their
  whole object graph pinned in memory.  They are freed if redefined,
  with recursive `free()` on the entire object graph; as such, they
  must not have pointers to shared data in their graph, except for
  their lexical captures array that is freed non-recursively.

* As a small optimization, references to private non-heap values can
  still be copied into code forms by value, and possibly immutable
  heap objects (by deep copy) as well.

* Modules can be frozen, which pins the entire object graph of the
  module in memory, and deregisters the module from GC roots.  This
  enables optimization of internal top-level references.  The entire
  frozen module can be swapped out, which frees it recursively, but
  the new version must reuse binding boxes for existing identifiers,
  even creating dummy ones with "undefined" for removed bindings.

* Frozen modules can be statically linked, which ensures that it will
  remain pinned in memory even if swapped out for a new version; any
  references to its bindings can now be optimized by copying the box
  value (could still be a pointer) rather than having to point to the
  box to observe changes from having the entire module swapped out.

How do we detect that a statically linked module can be freed due to
all linking modules being gone as well?  There's a few options:

1. Don't.  Statically linked means stays in memory forever.  Eh...

2. Reference counting.  Must disallow cycles, or they leak.  May be
   acceptable to disallow cyclic static linking.

3. Just have a dedicated mark & sweep for modules?

This article ended up being *way* longer than I expected, so I think
I'll call it quits here.  I think a simple little mark & sweep of a
global modules list would be quite fine though.  To be clear I don't
mean going into the modules; just the modules themselves.  So this
would be a very quick and easy operation.


## Wait...

I've made a crucial mistake: If statically linking a module means
having direct pointers to its data, and the linking module is frozen,
that would mean the recursive free goes into the other module.  Ugh!

We really need a better way to detect boundaries between modules.

OK, here's an idea: Given that we have a bunch of as of yet barely
defined bits in our heap pointer NaN types, we could have one bit
meaning "pointer to another module's data" or more generally some
"foreign" data indicator.

For example, heap NaN pointers all have 8 bits currently reserved for
indeterminate purposes.  (Probably tri-color marking & generations.)
One of these could be sacrificed for this purpose.

Would be used in two ways:

1. Intra-module references to private bindings: Copy the value into
   the code, set the foreign bit if it's a pointer; recursive free
   won't touch it.

2. References to statically linked modules: Copy the value of the
   binding into the code of this module, set foreign bit if pointer;
   recursive free won't touch it.

Something like that would work, I think.