Add a note.

2 files changed, 312 insertions, 0 deletions

diff --git a/notes/260825-code-gc.md b/notes/260825-code-gc.md
new file mode 100644
index 0000000..9593d15
--- /dev/null
+++ b/notes/260825-code-gc.md
@@ -0,0 +1,311 @@
+# 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.
diff --git a/notes/index.md b/notes/index.md
index d303d5a..b81f20b 100644
--- a/notes/index.md
+++ b/notes/index.md
@@ -40,3 +40,4 @@
 * [Virtual memory overcommit](260821-overcommit.html)
 * [Releasing vmem, reloaded](260821-release2.html)
 * [Releasing vmem, again](260822-release3.html)
+* [Memory management of code](260825-code-gc.html)