the basic players in the hither virtual machine are the stack (of which there are really two) and the cell. The stacks hold cells, and the cells are the data.

Here’s how cells are defined.

  pub const Cell = struct {
      pub const Tag = enum(u2) {
          slice,
          integer,
          number,
          builtin,
      };

      tag: Tag,
      slice_is: enum(u2) {
          string,
          word,
          definition,
      } = .string,
      data: packed union {
          slice: packed struct {
              address: u32,
              length: u32,
          },
          integer: i64,
          number: f64,
          builtin: *const fn (*Hither) Error!void,
      },
  };

Zig has “tagged” unions, so in theory the tag field could be replaced by writing something like Cell = union(enum) {…}; but that ends up wasting a lot of space on the tag. “Packed” unions, however, do not have a tag, letting us sneak in the slice_is enum into some of the tag’s space.

(By the way, I think Rust and/or Typescript uses the word “enum” for what is more or less what Zig and C would call a “union”, and reserves “enum” for a type which “enumrates” a list of constant values.)

Anyway, the data field takes up 8 bytes (well, assuming pointers aren’t any bigger than that lol), which can either be a function pointer, a floating point number, an integer, or a “slice” pointing to some data that exists on hither’s “heap”, more about which later.

Ah, this is a good place to mention something: hither doesn’t have a “bytecode” layer. Maybe it should? Who knows, certainly not me. All of this is to say—the builtins are functionally the only “actual code” that hither can run. The hither interpreter looks up words in a hash table and pushes the result of that lookup onto the stack.

The stack, by the way, is a Zig off-the-shelf special, a std.MultiArrayList(Cell). In Zig, MultiArrayList is a neat generic data structure that performs a “struct of arrays” transform on data automatically. That is, under the hood, a std.MultiArrayList(Cell) has three lists, one for tag, slice_is and data. This saves a little memory and is just conceptually really cool.

The first version of hither was true to the conceptual description of Forth that I read about on Forth's website: essentially anything and everything hither related lived on a single stack, one big blob of data sectioned off relevantly. Although I never ran into issues, I began to feel a little guilty about my usage of the “pad” and “dictionary”, the former mostly a place to store strings and the latter a place to store “compiled” hither definitions. Since I didn’t have a good way to tell whether or not a definition or string was “in use”, every lambda, every little string lived as long as hither did.

Since the hither interpreter has a well-defined “end of execution” moment every time the interpreter finishes parsing a line, garbage collection seemed like a great fit. I followed this post on writing a garbage collector in C, although ended up trying to slightly “Ziggify” the resulting code. Also, my “heap” is entirely pre-allocated and does not grow—it wouldn’t be too much harder to let it grow, as the link above demonstrates, but I didn’t want to.

Here is the Heap struct

  pub const Heap = struct {
      used: ?*Header,
      free: ?*Header,
      buf: [*]align(@sizeOf(Header)) u8,
      capacity_in_headers: usize,

      pub const Header = struct {
          size_in_headers: u32,
          used_size_in_bytes: u32,
          next: ?*Header,

          comptime std.debug.assert(@alignOf(Header) < @sizeOf(Header));
      };
  };

used and free are the heads of linked lists, with elements drawn from buf. A Header delimits a chunk of memory from buf, counting itself, and keeping track of how much of itself in bytes is actually in use. It’s very important (hence the compile-time assertion) that Headers are happy to be aligned a little smaller than their size.

test {
    std.testing.log_level = .debug;
    var u: u32 = 40;
    std.log.debug("0x{x}", .{@intFromPtr(&u)});
}

pub fn tag(header: *Header) void {
    if (isPtrTagged(header.next)) return;
    header.next = @ptrFromInt(@intFromPtr(header.next) + @alignOf(Header));
}

fn markAndSweep(hither: *Hither) void {
    // mark
    for (hither.dictionary.keys()) |key| {
        const addr = hither.heap.addressOf(key.ptr) catch continue;
        const header = hither.heap.containingInUseHeader(addr) orelse continue;
        header.tag();
    }
    for (hither.dictionary.values()) |cell| hither.tagContainingHeader(cell);
    // sweep
    var used = hither.heap.used;
    while (used) |ptr| {
        used = Heap.Header.unTagPtr(ptr.next);
        if (Heap.Header.isPtrTagged(ptr.next)) continue;
        hither.heap.discard(ptr);
    }
    used = hither.heap.used;
    while (used) |ptr| : (used = ptr.next) {
        ptr.next = Heap.Header.unTagPtr(ptr.next);
    }
}