# 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 -> version = 1234 bindings = 0x2222 -> val = 0x2345 -> -> } { key = 0x3456 -> val = 0x4567 -> -> } { key = 0x5678 -> val = 0x6789 -> > } ]> } 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. But need to think about pointer equality as well, which breaks unless we mask off the "foreign" bits of pointers as part of equality check, making equality more than a single CPU instruction, which is kinda annoying. Then again, a similar issue applies to the rest of the 8 bits used for GC metadata. Oh well, I'll figure it out. ## Another try I won't be able to sleep unless I crack this, so here we go again. * Although constants may be propagated by immediate value or deep copy, procedures otherwise refer to their own module's bindings through lexical capture. Private bindings are copied into the lexicals array by value (which may be a pointer anyway); public bindings are represented by binding box pointers regardless of whether it belongs to this or another module. Crucially, the procedure's code never has a pointer directly copied in; only through a potential deep copy of a propagated constant. This means that even for the module's own public bindings, there's two layers of indirection: 1. Lexicals array, 2. Binding box. And interestingly, imported bindings are treated the same. * Once a module is sealed, intra-module references can be optimized two-fold: Regardless of whether it's a private or a public binding, it's copied directly by-value (may be a pointer anyway) into code. Imported bindings are still treated as before: Double-indirection. I have to say I don't like this double-indirection that remains even when a module is sealed. After agonizing for over an hour, I think I know the solution. A crucial detail to remember about our NaN packing strategy is that there's already separate NaN tags for references to quoted data in optimized code. Regular heap pointers can never actually appear in these optimized code forms. So what if we simply special-cased regular pointers in code? It's really that easy... Actually, we can refine this whole system somewhat. This has led to yet another minor overhaul of our NaN packing scheme, but I won't get into that here. Long story short, there is now an explicit context-dependent meaning of certain NaN tags: Before and after the code optimization pass. This opens up a ton of room and finally we have direct module binding pointers in optimized code. (It's actually a lie that there was previously no room left, but I'm trying to make sure I have a few value ranges left to spare, because you never know when you'll need them.)