yippie

10 files changed, 156 insertions, 43 deletions

diff --git a/doc/0/0-value.md b/doc/0/0-value.md
index 4bb7e0c..16e1a58 100644
--- a/doc/0/0-value.md
+++ b/doc/0/0-value.md
@@ -166,21 +166,21 @@ with small payload values here: There is room for over 268 Million 16-bit types
 The final 51-bit range is used for various internal purposes by the Zisp
 interpreter, mostly related to transparent code optimization.
 
-  000   :: Pointer to heap object as constant
+    000   :: Pointer to heap object as constant
 
-  001   :: Pointer to list values as constant
+    001   :: Pointer to list values as constant
 
-  010   :: Pointer to istr object as constant
+    010   :: Pointer to istr object as constant
 
-  011   :: Immediate short string as constant
+    011   :: Immediate short string as constant
 
-  100   :: Local variable reference by index
+    100   :: Local variable reference by index
 
-  101   :: Pointer to constant function-call expression
+    101   :: Pointer to constant function-call expression
 
-  110   :: Pointer to variable function-call expression
+    110   :: Pointer to variable function-call expression
 
-  111   :: Pointer to special-form or macro-call expression
+    111   :: Pointer to special-form or macro-call expression
 
 Forbidden Value #4, Positive Infinity, is avoided thanks to the fact that heap
 pointers always have a non-zero heap-type tag.  (See further above.)
diff --git a/doc/0/1-parse.md b/doc/0/1-parse.md
index 101a3b6..32ffa2f 100644
--- a/doc/0/1-parse.md
+++ b/doc/0/1-parse.md
@@ -260,14 +260,14 @@ the parser to generate a list with the structure:
     (#PQSTR <STRING>)   ;; <STRING> is visual aid, not syntax
 
 The decoder, using default settings, would emit this string verbatim as a value.
-Then, during code evaluation, this would be seen as an identifier.  In this way,
+Then, during code execution, this would be seen as an identifier.  In this way,
 pipe-quoted strings are equivalent to bare strings in functionality.
 
 It is important to understand that the decoder sits between the parser and the
-[evaluator](3-eval.html), and in opposition to Lisp and Scheme tradition, it is
-common for the evaluator to receive values that are not valid as a datum; here,
-a string unto itself that may not be a valid datum.  Yet, it is valid as an
-identifier for the purposes of the evaluator.
+[interpreter](3-execute.html), and in opposition to Lisp and Scheme tradition,
+it is common for the interpreter to receive values that are not valid as data;
+here, a string unto itself that may not be a valid datum.  Yet, it is valid as
+an identifier value for the purposes of the interpreter.
 
 ### Double-quoted
 
@@ -524,7 +524,7 @@ Notes:
 
 * Syntax sugar can combine arbitrarily.  Some examples follow.  Any of these may
   or may not actually have a meaning in code; some might simply end up producing
-  an error during decoding, or later evaluation of code.
+  an error during decoding, or later execution, of code.
 
       #{...}            -> (#HASH (#BRACE ...))
 
diff --git a/doc/0/index.md b/doc/0/index.md
index f0da216..844729c 100644
--- a/doc/0/index.md
+++ b/doc/0/index.md
@@ -20,9 +20,9 @@ compiling code.
    over data received from the parser, enriching it with more complex
    value types, and handling primitive source code transforms.
 
-3. [Eval](3-eval.html)
+3. [Execute](3-execute.html)
 
-   Code is evaluated within a mutable module context, on which it can
+   Code is executed within a mutable module context, on which it can
    have side effects such as creating new definitions or establishing
    links to other modules.
 
diff --git a/src/main.zig b/src/main.zig
index 592d317..e601020 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -39,5 +39,7 @@ pub fn main() !u8 {
         try zisp.io.print(writer, datum);
         try writer.writeAll("\n");
         try writer.flush();
+
+        if (datum.isList()) try zisp.value.list.free(datum);
     }
 }
diff --git a/src/zisp/gc/ListPool.zig b/src/zisp/gc/ListPool.zig
index 6c34074..a843ae5 100644
--- a/src/zisp/gc/ListPool.zig
+++ b/src/zisp/gc/ListPool.zig
@@ -14,52 +14,70 @@ const Alloc = std.mem.Allocator;
 const ArrayList = std.ArrayListUnmanaged;
 
 const value = @import("../value.zig");
+const seg_stack = @import("seg_stack.zig");
 
 const Value = value.Value;
+const SegStack = seg_stack.SegStack;
 
 const Self = @This();
 
-// How many Value elements fit in a block. A good value should be 512, since
-// each Value is 8 bytes: 512 * 8 = 4 KiB
+/// How many Value elements fit in a block. A good value should be 512, since
+/// each Value is 8 bytes: 512 * 8 = 4 KiB
 const block_value_cap = 512;
 
-// Initial capacity of ArrayList of pointers to filled blocks.  Also 512, since
-// pointers are 8 bytes as well.
-const def_full_blocks_cap = 512;
-
 const Block = [block_value_cap]Value;
 
 alloc: Alloc,
 
 current_block: *Block,
-current_index: usize,
+current_index: usize = 0,
 
-full_blocks: ArrayList(*Block),
+full_list: SegStack(*Block, 4096),
+free_lists: [7]SegStack([*]Value, 512),
 
 pub fn init(alloc: Alloc) !Self {
     return .{
         .alloc = alloc,
         .current_block = try alloc.create(Block),
-        .current_index = 0,
-        .full_blocks = try .initCapacity(alloc, def_full_blocks_cap),
+        .full_list = try .init(alloc),
+        .free_lists = .{
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+            try .init(alloc),
+        },
     };
 }
 
 pub fn deinit(self: *Self) void {
+    for (self.free_lists) |l| l.deinit(self.alloc);
+    while (self.full_list.pop(self.alloc)) |block| self.alloc.destroy(block);
+    self.full_list.deinit(self.alloc);
     self.alloc.destroy(self.current_block);
-    for (self.full_blocks) |block| self.alloc.destroy(block);
-    self.full_blocks.deinit(self.alloc);
 }
 
 fn newBlock(self: *Self) !void {
-    try self.full_blocks.append(self.alloc, self.current_block);
+    try self.full_list.push(self.alloc, self.current_block);
     self.current_block = try self.alloc.create(Block);
     self.current_index = 0;
 }
 
-pub fn create(self: *Self, len: u3) ![*]Value {
+fn popFree(self: *Self, len: u3) ?[*]Value {
+    return self.free_lists[len - 1].pop(self.alloc);
+}
+
+fn pushFree(self: *Self, len: u3, ptr: [*]Value) !void {
+    try self.free_lists[len - 1].push(self.alloc, ptr);
+}
+
+pub fn allocVals(self: *Self, len: u3) ![*]Value {
     std.debug.assert(len != 0);
 
+    if (self.popFree(len)) |ptr| return ptr;
+
     if (len > block_value_cap - self.current_index) {
         try self.newBlock();
     }
@@ -67,3 +85,15 @@ pub fn create(self: *Self, len: u3) ![*]Value {
     defer self.current_index += len;
     return @ptrCast(&self.current_block[self.current_index]);
 }
+
+pub fn freeVals(self: *Self, len: u3, ptr: [*]Value) !void {
+    std.debug.assert(len != 0);
+
+    try self.pushFree(len, ptr);
+}
+
+pub fn freeList(self: *Self, list: Value) !void {
+    const len = value.list.getLenTag(list);
+    const ptr = value.list.getValPtr(list);
+    try self.freeVals(len, ptr);
+}
diff --git a/src/zisp/gc/seg_stack.zig b/src/zisp/gc/seg_stack.zig
new file mode 100644
index 0000000..0867892
--- /dev/null
+++ b/src/zisp/gc/seg_stack.zig
@@ -0,0 +1,84 @@
+//! Segmented linked list backed stack
+
+const std = @import("std");
+
+const Alloc = std.mem.Allocator;
+
+/// Segmented linked list backed stack
+pub fn SegStack(T: type, seg_max_bytes: usize) type {
+    const seg_size: usize = (seg_max_bytes - @sizeOf(usize)) / @sizeOf(T);
+
+    comptime {
+        if (seg_size < 4) {
+            @panic("Surely you didn't want to have segments this small?");
+        }
+    }
+
+    const Node = struct {
+        const Self = @This();
+
+        prev: ?*Self = null,
+        elts: [seg_size]T = undefined,
+
+        pub fn new(alloc: Alloc) !*Self {
+            const self = try alloc.create(Self);
+            self.* = .{};
+            return self;
+        }
+    };
+
+    return struct {
+        const Self = @This();
+
+        head: *Node,
+        idx: usize = 0,
+
+        // To prevent "thrashing" we don't immediately deallocate the current
+        // node when it's emptied but rather save it aside.
+        aside: ?*Node = null,
+
+        pub fn init(alloc: Alloc) !Self {
+            return .{ .head = try .new(alloc) };
+        }
+
+        pub fn deinit(self: *Self, alloc: Alloc) void {
+            if (self.aside) |aside| alloc.destroy(aside);
+            var node: ?Node = self.head;
+            while (node) |n| {
+                alloc.destroy(n);
+                node = n.prev;
+            }
+        }
+
+        pub fn push(self: *Self, alloc: Alloc, elt: T) !void {
+            if (self.idx == seg_size) {
+                if (self.aside) |aside| {
+                    self.head = aside;
+                    self.aside = null;
+                } else {
+                    const prev = self.head;
+                    self.head = try .new(alloc);
+                    self.head.prev = prev;
+                }
+                self.idx = 0;
+            }
+            self.head.elts[self.idx] = elt;
+            self.idx += 1;
+        }
+
+        pub fn pop(self: *Self, alloc: Alloc) ?T {
+            if (self.idx == 0) {
+                if (self.head.prev) |prev| {
+                    if (self.aside) |aside| alloc.destroy(aside);
+                    self.aside = self.head;
+                    self.head = prev;
+                    self.idx = seg_size;
+                } else {
+                    return null;
+                }
+            }
+            self.idx -= 1;
+            return self.head.elts[self.idx];
+        }
+    };
+}
diff --git a/src/zisp/io/Printer.zig b/src/zisp/io/Printer.zig
index 4b06005..abc4ebc 100644
--- a/src/zisp/io/Printer.zig
+++ b/src/zisp/io/Printer.zig
@@ -237,13 +237,7 @@ fn printListDirect(p: *Printer, len: u3, vals: [*]Value) !void {
             close = "}";
             i = 1;
         },
-        else => {
-            if (vals[0].isRune()) {
-                try p.printRune(vals[0]);
-                i = 1;
-            }
-            try p.write("(");
-        },
+        else => try p.write("("),
     }
 
     if (len != 0) {
diff --git a/src/zisp/value.zig b/src/zisp/value.zig
index 4ff683a..4ce6cd2 100644
--- a/src/zisp/value.zig
+++ b/src/zisp/value.zig
@@ -265,15 +265,11 @@ pub const Value = packed union {
         const ptr_bits: u20 = hi16_tag_ptr;
         const tag_bits: u20 = @intFromEnum(ht);
         if (hi20_bits != ptr_bits << 4 | tag_bits) return null;
-
-        // A zero payload value here would actually indicate that the value is
-        // not a pointer at all, but the Positive cqNaN value; this is totally
-        // fine, because @ptrFromInt() turns zero into null anyway.
         return @ptrFromInt(v.bits << 20 >> 16);
     }
 
     /// Checks for a pointer and returns the value and tag separately, or null
-    /// if this isn't a pointer at all.  Could be useful for a dispatch table.
+    /// if this isn't a pointer or null.  Could be useful for a dispatch table.
     pub fn getPtrAny(v: Value) ?struct { Zptr, HeapType } {
         const hi16_bits: u16 = @intCast(v.bits >> 48);
         if (hi16_bits != hi16_tag_ptr) return null;
diff --git a/src/zisp/value/list.zig b/src/zisp/value/list.zig
index d040a34..52c665e 100644
--- a/src/zisp/value/list.zig
+++ b/src/zisp/value/list.zig
@@ -26,7 +26,7 @@ pub fn assert(v: Value) void {
 pub fn new(alloc: Alloc, pool: ?*ListPool, vals: []const Value) !Value {
     var len_tagged_ptr: u48 = undefined;
     if (vals.len < 8 and pool != null) {
-        const ptr = try pool.?.create(@intCast(vals.len));
+        const ptr = try pool.?.allocVals(@intCast(vals.len));
         for (vals, 0..) |v, i| ptr[i] = v;
         len_tagged_ptr = @intCast(@intFromPtr(ptr) | vals.len);
     } else {
@@ -38,6 +38,11 @@ pub fn new(alloc: Alloc, pool: ?*ListPool, vals: []const Value) !Value {
     return .{ .list = .{ .len_tagged_ptr = len_tagged_ptr } };
 }
 
+// TODO: this is just a test
+pub fn free(list: Value) !void {
+    try gc.mainListPool().freeList(list);
+}
+
 pub fn getLenTag(v: Value) u3 {
     return @truncate(v.bits);
 }
diff --git a/update-html.sh b/update-html.sh
index e611006..9c74b9c 100755
--- a/update-html.sh
+++ b/update-html.sh
@@ -40,6 +40,8 @@ md2ht() {
         if [ "$nav" ]
         then
             sed "1 a $nav" < "$src" | markdown2 -x "$ext"
+        else
+            markdown2 -x "$ext" < "$src"
         fi
         echo "</body>"
         echo "</html>"