pit: Clean up tree traversals

18 files changed, 289 insertions, 165 deletions

diff --git a/pit/.envrc b/pit/.envrc
index c4b17d7..84c7ede 100644
--- a/pit/.envrc
+++ b/pit/.envrc
@@ -1 +1 @@
-use_flake
+use_flake .#pit
diff --git a/pit/include/lcq/pit.h b/pit/include/lcq/pit.h
index 8ff46c8..3afce9f 100644
--- a/pit/include/lcq/pit.h
+++ b/pit/include/lcq/pit.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_H
 #define LCOLONQ_PIT_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 #include <lcq/pit/lexer.h>
 #include <lcq/pit/parser.h>
diff --git a/pit/include/lcq/pit/arena.h b/pit/include/lcq/pit/arena.h
index 18d7f96..fcaca55 100644
--- a/pit/include/lcq/pit/arena.h
+++ b/pit/include/lcq/pit/arena.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_ARENA_H
 #define LCOLONQ_PIT_ARENA_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 
 typedef i64 pit_arena_index;
 
diff --git a/pit/include/lcq/pit/lexer.h b/pit/include/lcq/pit/lexer.h
index d10d9c2..db452e7 100644
--- a/pit/include/lcq/pit/lexer.h
+++ b/pit/include/lcq/pit/lexer.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_LEXER_H
 #define LCOLONQ_PIT_LEXER_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 
 typedef enum {
     PIT_LEX_TOKEN_ERROR=-1,
diff --git a/pit/include/lcq/pit/runtime.h b/pit/include/lcq/pit/runtime.h
index d9311b2..d981447 100644
--- a/pit/include/lcq/pit/runtime.h
+++ b/pit/include/lcq/pit/runtime.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_RUNTIME_H
 #define LCOLONQ_PIT_RUNTIME_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 #include <lcq/pit/vec.h>
 #include <lcq/pit/arena.h>
@@ -35,20 +35,23 @@ PIT_DECLARE_VEC(pit_annotated_ref)
 void pit_annotation_set(struct pit_runtime *rt, pit_ref ref, pit_annotation annotation);
 pit_annotated_ref *pit_annotation_get(struct pit_runtime *rt, pit_ref ref);
 
-/* "programs"; vectors of "instructions" for a very simple VM used by the evaluator */
+/* entries on a stack used when traversing trees of values */
 typedef struct {
     enum {
-        PIT_RUNTIME_EVAL_INS_LITERAL,
-        PIT_RUNTIME_EVAL_INS_APPLY
+        PIT_TRAVERSAL_ENTRY_VALUE,
+        PIT_TRAVERSAL_ENTRY_DUMP_STRING,
+        PIT_TRAVERSAL_ENTRY_APPLICATION,
     } sort;
     union {
-        pit_value literal;
-        struct { i64 arity; pit_annotated_ref *annotation; } apply; 
+        pit_value value;
+        char *dump_string;
+        struct { i64 arity; pit_annotated_ref *annotation; } application; 
     } in;
-} pit_runtime_eval_ins;
-PIT_DECLARE_VEC(pit_runtime_eval_ins)
-void pit_runtime_eval_program_push_literal(struct pit_runtime *rt, pit_vec(pit_runtime_eval_ins) *s, pit_value x);
-void pit_runtime_eval_program_push_apply(struct pit_runtime *rt, pit_vec(pit_runtime_eval_ins) *s, i64 arity, pit_annotated_ref *annotation);
+} pit_traversal_entry;
+PIT_DECLARE_VEC(pit_traversal_entry)
+void pit_traversal_push_value(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, pit_value x);
+void pit_traversal_push_dump_string(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, char *m);
+void pit_traversal_push_application(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, i64 arity, pit_annotated_ref *annotation);
 
 typedef struct pit_runtime {
     /* interpreter state */
@@ -58,12 +61,12 @@ typedef struct pit_runtime {
     pit_arena *backbuffer; /* additional allocation, the same size as the heap (used by GC) */
     pit_vec(pit_annotated_ref) *annotations;
     pit_vec(pit_annotated_ref) *backtrace; /* we reuse this vector for both backtraces and the GC */
-    pit_vec(pit_symtab_entry) *symtab;/* all symbols */
+    pit_vec(pit_symtab_entry) *symtab; /* all symbols */
     /* temporary/"scratch" memory */
     pit_vec(pit_value) *saved_bindings; /* stack used to save old values of bindings to be restored ("shallow binding") */
     pit_vec(pit_value) *expr_stack; /* stack of subexpressions to evaluate during evaluation */
     pit_vec(pit_value) *result_stack; /* stack of intermediate values during evaluation */
-    pit_vec(pit_runtime_eval_ins) *program; /* intermediate stack-based program constructed during evaluation */
+    pit_vec(pit_traversal_entry) *traversal; /* intermediate stack used during tree traversal */
     /* bookkeeping */
     /* "frozen" values offsets: values before these offsets are immutable, and we can reset here later */
     i64 frozen_values, frozen_symtab;
diff --git a/pit/include/lcq/pit/runtime/value.h b/pit/include/lcq/pit/runtime/value.h
index 5820bbd..fa59a46 100644
--- a/pit/include/lcq/pit/runtime/value.h
+++ b/pit/include/lcq/pit/runtime/value.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_RUNTIME_VALUE_H
 #define LCOLONQ_PIT_RUNTIME_VALUE_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/runtime.h>
 
 /* the basic value type - it's just a u64 */
diff --git a/pit/include/lcq/pit/types.h b/pit/include/lcq/pit/types.h
new file mode 100644
index 0000000..23a1a90
--- /dev/null
+++ b/pit/include/lcq/pit/types.h
@@ -0,0 +1,6 @@
+#ifndef LCOLONQ_PIT_TYPES_H
+#define LCOLONQ_PIT_TYPES_H
+
+#include <lcq/prelude.h>
+
+#endif
diff --git a/pit/include/lcq/pit/utils.h b/pit/include/lcq/pit/utils.h
index 4bea479..6769310 100644
--- a/pit/include/lcq/pit/utils.h
+++ b/pit/include/lcq/pit/utils.h
@@ -2,8 +2,7 @@
 #define LCOLONQ_PIT_UTILS_H
 
 #include <stdarg.h>
-#include <stddef.h>
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 
 /* macro helpers */
 #define PIT_CONCAT(a, b) a ## b
@@ -35,5 +34,6 @@ int pit_libc_string_snprintf(char *buf, size_t len, char *format, ...);
 
 /* assorted utilities and debugging tools */
 #define pit_mul(result, a, b) *result = (i64) (a) * (i64) (b)
+static inline i64 pit_mod(i64 x, i64 m) { return (m + (x % m)) % m; }
 
 #endif
diff --git a/pit/include/lcq/pit/vec.h b/pit/include/lcq/pit/vec.h
index 82276f1..e1f7ab4 100644
--- a/pit/include/lcq/pit/vec.h
+++ b/pit/include/lcq/pit/vec.h
@@ -1,7 +1,7 @@
 #ifndef LCOLONQ_PIT_VEC_H
 #define LCOLONQ_PIT_VEC_H
 
-#include <lcq/prelude.h>
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 
 #define pit_vec(ty) pit_vec__ ## ty ## __type
@@ -49,4 +49,65 @@
         return --s->next; \
     }
 
+#define pit_deque(ty) pit_deque__ ## ty ## __type
+#define pit_deque_new(ty) pit_deque__ ## ty ## __new
+#define pit_deque_get(ty) pit_deque__ ## ty ## __get
+#define pit_deque_reset(ty) pit_deque__ ## ty ## __reset
+#define pit_deque_push_front(ty) pit_deque__ ## ty ## __push_front
+#define pit_deque_push_back(ty) pit_deque__ ## ty ## __push_back
+#define pit_deque_pop_front(ty) pit_deque__ ## ty ## __pop_front
+#define pit_deque_pop_back(ty) pit_deque__ ## ty ## __pop_back
+
+#define PIT_DECLARE_DEQUE(ty) \
+    typedef struct { \
+        i64 capacity, head, len; \
+        ty data[]; \
+    } pit_deque(ty); \
+    static __attribute__ ((unused)) pit_deque(ty) *pit_deque_new(ty)(u8 *buf, i64 buf_len) { \
+        uintptr_t base = (uintptr_t) buf; \
+        uintptr_t aligned = pit_align_up(base, sizeof(void *)); \
+        pit_deque(ty) *ret = (pit_deque(ty) *) aligned; \
+        uintptr_t data = aligned + (i64) sizeof(pit_deque(ty)); \
+        i64 offset = (i64) data - (i64) base; \
+        i64 remaining = (i64) (buf_len - offset); \
+        ret->head = 0; \
+        ret->len = 0; \
+        ret->capacity = remaining / (i64) sizeof(ty); \
+        return ret; \
+    } \
+    static __attribute__ ((unused)) ty *pit_deque_get(ty)(pit_deque(ty) *s, i64 i) { \
+        if (i > s->len) return NULL; \
+        i64 idx = pit_mod(s->head + i, s->capacity); \
+        return &s->data[idx]; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_push_front(ty)(pit_deque(ty) *s, ty v) { \
+        if (s->len + 1 > s->capacity) return -1; \
+        s->len += 1; \
+        s->head = pit_mod(s->head - 1, s->capacity); \
+        s->data[s->head] = v; \
+        return s->head; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_push_back(ty)(pit_deque(ty) *s, ty v) { \
+        if (s->len + 1 > s->capacity) return -1; \
+        i64 idx = pit_mod(s->head + s->len, s->capacity); \
+        s->data[idx] = v; \
+        s->len += 1; \
+        return idx; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_pop_front(ty)(pit_deque(ty) *s, ty *v) { \
+        if (s->len == 0) return -1; \
+        i64 idx = s->head; \
+        *v = s->data[s->head]; \
+        s->head = pit_mod(s->head + 1, s->capacity); \
+        s->len -= 1; \
+        return idx; \
+    } \
+    static __attribute__ ((unused)) i64 pit_deque_pop_back(ty)(pit_deque(ty) *s, ty *v) { \
+        if (s->len == 0) return -1; \
+        i64 idx = pit_mod(s->head + s->len - 1, s->capacity); \
+        *v = s->data[idx]; \
+        s->len -= 1; \
+        return idx; \
+    }
+
 #endif
diff --git a/pit/src/lexer.c b/pit/src/lexer.c
index a2b0c7d..def4084 100644
--- a/pit/src/lexer.c
+++ b/pit/src/lexer.c
@@ -1,5 +1,6 @@
 #include <lcq/pit/utils.h>
 #include <lcq/pit/lexer.h>
+#include <lcq/pit/types.h>
 
 const char *PIT_LEX_TOKEN_NAMES[PIT_LEX_TOKEN__SENTINEL] = {
     /* [PIT_LEX_TOKEN_EOF] = */ "eof",
diff --git a/pit/src/library.c b/pit/src/library.c
index b6b8b42..cbe7f71 100644
--- a/pit/src/library.c
+++ b/pit/src/library.c
@@ -6,7 +6,7 @@
 
 static pit_value impl_sf_quote(pit_runtime *rt, pit_value args, void *data) {
     (void) data;
-    pit_runtime_eval_program_push_literal(rt, rt->program, pit_value_cons_car(rt, args));
+    pit_traversal_push_value(rt, rt->traversal, pit_value_cons_car(rt, args));
     return PIT_NIL;
 }
 static pit_value impl_sf_if(pit_runtime *rt, pit_value args, void *data) {
@@ -45,7 +45,7 @@ static pit_value impl_sf_progn(pit_runtime *rt, pit_value args, void *data) {
         final = pit_eval(rt, pit_value_cons_car(rt, bodyforms));
         bodyforms = pit_value_cons_cdr(rt, bodyforms);
     }
-    pit_runtime_eval_program_push_literal(rt, rt->program, final);
+    pit_traversal_push_value(rt, rt->traversal, final);
     return PIT_NIL;
 }
 static pit_value impl_sf_or(pit_runtime *rt, pit_value args, void *data) {
@@ -57,14 +57,14 @@ static pit_value impl_sf_or(pit_runtime *rt, pit_value args, void *data) {
         if (final != PIT_NIL) break;
         bodyforms = pit_value_cons_cdr(rt, bodyforms);
     }
-    pit_runtime_eval_program_push_literal(rt, rt->program, final);
+    pit_traversal_push_value(rt, rt->traversal, final);
     return PIT_NIL;
 }
 static pit_value impl_sf_lambda(pit_runtime *rt, pit_value args, void *data) {
     (void) data;
     pit_value as = pit_value_cons_car(rt, args);
     pit_value body = pit_value_cons_cdr(rt, args);
-    pit_runtime_eval_program_push_literal(rt, rt->program, pit_value_func_lambda(rt, as, body));
+    pit_traversal_push_value(rt, rt->traversal, pit_value_func_lambda(rt, as, body));
     return PIT_NIL;
 }
 static pit_value impl_m_defun(pit_runtime *rt, pit_value args, void *data) {
diff --git a/pit/src/main.c b/pit/src/main.c
index 157ad87..61b4b9c 100644
--- a/pit/src/main.c
+++ b/pit/src/main.c
@@ -7,6 +7,8 @@
 #include <lcq/pit/runtime.h>
 #include <lcq/pit/library.h>
 
+PIT_DECLARE_DEQUE(double)
+
 int main(int argc, char **argv) {
     i64 sz = 256 * 1024 * 1024;
     u8 *buf = malloc((size_t) sz);
diff --git a/pit/src/native.c b/pit/src/native.c
index fbf8efc..a62f82e 100644
--- a/pit/src/native.c
+++ b/pit/src/native.c
@@ -79,8 +79,8 @@ static void check_invariants(pit_runtime *rt) {
     if (rt->result_stack->next != 0) {
         pit_error(rt, "leaked result_stack memory! %ld", rt->result_stack->next);
     }
-    if (rt->program->next != 0) {
-        pit_error(rt, "leaked program memory! %ld", rt->program->next);
+    if (rt->traversal->next != 0) {
+        pit_error(rt, "leaked traversal memory! %ld", rt->traversal->next);
     }
 }
 pit_value pit_load_file(pit_runtime *rt, char *path) {
diff --git a/pit/src/parser.c b/pit/src/parser.c
index 9c575cb..0f9b167 100644
--- a/pit/src/parser.c
+++ b/pit/src/parser.c
@@ -1,3 +1,4 @@
+#include <lcq/pit/types.h>
 #include <lcq/pit/utils.h>
 #include <lcq/pit/lexer.h>
 #include <lcq/pit/parser.h>
diff --git a/pit/src/runtime.c b/pit/src/runtime.c
index a8428c7..f13adb3 100644
--- a/pit/src/runtime.c
+++ b/pit/src/runtime.c
@@ -36,7 +36,7 @@ pit_runtime *pit_runtime_new(u8 *buf, i64 len) {
     ret->symtab = pit_vec_new(pit_symtab_entry)(pit_arena_alloc_back(a, symtab_size), symtab_size);
     ret->expr_stack = pit_vec_new(pit_value)(pit_arena_alloc_back(a, stack_size), stack_size);
     ret->result_stack = pit_vec_new(pit_value)(pit_arena_alloc_back(a, stack_size), stack_size);
-    ret->program = pit_vec_new(pit_runtime_eval_ins)(pit_arena_alloc_back(a, stack_size), stack_size);
+    ret->traversal = pit_vec_new(pit_traversal_entry)(pit_arena_alloc_back(a, stack_size), stack_size);
     ret->saved_bindings = pit_vec_new(pit_value)(pit_arena_alloc_back(a, stack_size), stack_size);
     ret->frozen_values = 0;
     ret->frozen_symtab = 0;
@@ -99,18 +99,25 @@ pit_annotated_ref *pit_annotation_get(struct pit_runtime *rt, pit_ref ref) {
     return NULL;
 }
 
-void pit_runtime_eval_program_push_literal(pit_runtime *rt, pit_vec(pit_runtime_eval_ins) *s, pit_value x) {
-    pit_runtime_eval_ins ent;
-    ent.sort = PIT_RUNTIME_EVAL_INS_LITERAL;
-    ent.in.literal = x;
-    if (pit_vec_push(pit_runtime_eval_ins)(s, ent) < 0)
-        pit_error(rt, "evaluation program overflow");
+void pit_traversal_push_value(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, pit_value x) {
+    pit_traversal_entry ent;
+    ent.sort = PIT_TRAVERSAL_ENTRY_VALUE;
+    ent.in.value = x;
+    if (pit_vec_push(pit_traversal_entry)(s, ent) < 0)
+        pit_error(rt, "traversal overflow");
 }
-void pit_runtime_eval_program_push_apply(pit_runtime *rt, pit_vec(pit_runtime_eval_ins) *s, i64 arity, pit_annotated_ref *annotation) {
-    pit_runtime_eval_ins ent;
-    ent.sort = PIT_RUNTIME_EVAL_INS_APPLY;
-    ent.in.apply.arity = arity;
-    ent.in.apply.annotation = annotation;
-    if (pit_vec_push(pit_runtime_eval_ins)(s, ent) < 0)
-        pit_error(rt, "evaluation program overflow");
+void pit_traversal_push_dump_string(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, char *m) {
+    pit_traversal_entry ent;
+    ent.sort = PIT_TRAVERSAL_ENTRY_DUMP_STRING;
+    ent.in.dump_string = m;
+    if (pit_vec_push(pit_traversal_entry)(s, ent) < 0)
+        pit_error(rt, "traversal overflow");
+}
+void pit_traversal_push_application(struct pit_runtime *rt, pit_vec(pit_traversal_entry) *s, i64 arity, pit_annotated_ref *annotation) {
+    pit_traversal_entry ent;
+    ent.sort = PIT_TRAVERSAL_ENTRY_APPLICATION;
+    ent.in.application.arity = arity;
+    ent.in.application.annotation = annotation;
+    if (pit_vec_push(pit_traversal_entry)(s, ent) < 0)
+        pit_error(rt, "traversal overflow");
 }
diff --git a/pit/src/runtime/dump.c b/pit/src/runtime/dump.c
index 3d5ec9c..3c1cf13 100644
--- a/pit/src/runtime/dump.c
+++ b/pit/src/runtime/dump.c
@@ -1,100 +1,143 @@
 #include <lcq/pit/runtime/dump.h>
 
-#define CHECK_BUF if (buf >= end) { return buf - start; }
-#define CHECK_BUF_LABEL(label) if (buf >= end) { goto label; }
-i64 pit_dump(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable) {
+typedef bool (*pit_dump_callback)(char *buf, i64 len, void *data);
+i64 pit_dump_with_callback(
+    pit_runtime *rt, char *start, i64 buf_len, pit_value top, bool readable,
+    pit_dump_callback cb, void *data
+) {
+    i64 traversal_reset = rt->traversal->next;
+    char *buf = start;
+    char *end = start + buf_len;
     pit_value_heavy *h = NULL;
-    if (len <= 0) return 0;
-    switch (pit_value_sort(v)) {
-    case PIT_VALUE_SORT_DOUBLE:
-        #ifndef PIT_NO_DOUBLE
-        return pit_libc_string_snprintf(buf, (size_t) len, "%lf", pit_value_as_double(rt, v));
-        #else
-        return pit_string_snprintf(buf, (size_t) len, "<unsupported double>");
-        #endif
-    case PIT_VALUE_SORT_INTEGER:
-        return pit_libc_string_snprintf(buf, (size_t) len, "%ld", pit_value_as_integer(rt, v));
-    case PIT_VALUE_SORT_SYMBOL: {
-        pit_symtab_entry *ent = pit_symtab_lookup(rt, v);
-        if (ent
-            && pit_value_sort(ent->name) == PIT_VALUE_SORT_REF
-            && (h = pit_value_ref_deref(rt, pit_value_as_ref(rt, ent->name)))
-        ) {
-            i64 i = 0;
-            for (; i < h->in.bytes.len && i < len - 1; ++i) {
-                buf[i] = (char) h->in.bytes.data[i];
-            }
-            return i;
-        } else {
-            return pit_libc_string_snprintf(buf, (size_t) len, "<broken symbol %ld>", pit_value_as_symbol(rt, v));
+    pit_traversal_push_value(rt, rt->traversal, top);
+    while (rt->traversal->next > traversal_reset) {
+        pit_traversal_entry ent;
+        i64 len = (i64) (end - buf);
+        if (rt->error != PIT_NIL) goto end;
+        if (pit_vec_pop(pit_traversal_entry)(rt->traversal, &ent) < 0)
+            pit_error(rt, "dump stack underflow");
+        if (rt->error != PIT_NIL) goto end;
+        switch (ent.sort) {
+        case PIT_TRAVERSAL_ENTRY_DUMP_STRING: {
+            for (char *s = ent.in.dump_string; *s != 0 && buf < end; ++s) *(buf++) = *s;
+            break;
         }
-    }
-    case PIT_VALUE_SORT_REF: {
-        pit_ref r = pit_value_as_ref(rt, v);
-        char *end = buf + len;
-        char *start = buf;
-        h = pit_value_ref_deref(rt, r);
-        if (!h) pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
-        else {
-            switch (h->hsort) {
-            case PIT_VALUE_HEAVY_SORT_CELL: {
-                CHECK_BUF; *(buf++) = '{';
-                CHECK_BUF; buf += pit_dump(rt, buf, end - buf, pit_value_cons_car(rt, h->in.cell), readable);
-                CHECK_BUF; *(buf++) = '}';
-                return buf - start;
-            }
-            case PIT_VALUE_HEAVY_SORT_CONS: {
-                pit_value cur = v;
-                CHECK_BUF_LABEL(list_end);
-                do {
-                    if (pit_value_is_cons(rt, cur)) {
-                        CHECK_BUF_LABEL(list_end); *(buf++) = ' ';
-                        CHECK_BUF_LABEL(list_end); buf += pit_dump(rt, buf, end - buf, pit_value_cons_car(rt, cur), readable);
-                    } else {
-                        CHECK_BUF_LABEL(list_end); buf += pit_libc_string_snprintf(buf, (size_t) (end - buf), " . ");
-                        CHECK_BUF_LABEL(list_end); buf += pit_dump(rt, buf, end - buf, cur, readable);
+        case PIT_TRAVERSAL_ENTRY_VALUE: {
+            pit_value v = ent.in.value;
+            switch (pit_value_sort(v)) {
+            case PIT_VALUE_SORT_DOUBLE:
+#ifndef PIT_NO_DOUBLE
+                buf += pit_libc_string_snprintf(buf, (size_t) len, "%lf", pit_value_as_double(rt, v));
+#else
+                buf += pit_string_snprintf(buf, (size_t) len, "<unsupported double>");
+#endif
+                break;
+            case PIT_VALUE_SORT_INTEGER:
+                buf += pit_libc_string_snprintf(buf, (size_t) len, "%ld", pit_value_as_integer(rt, v));
+                break;
+            case PIT_VALUE_SORT_SYMBOL: {
+                pit_symtab_entry *se = pit_symtab_lookup(rt, v);
+                if (se
+                    && pit_value_sort(se->name) == PIT_VALUE_SORT_REF
+                    && (h = pit_value_ref_deref(rt, pit_value_as_ref(rt, se->name)))
+                ) {
+                    i64 i = 0;
+                    for (; i < h->in.bytes.len && i < len - 1; ++i) {
+                        buf[i] = (char) h->in.bytes.data[i];
                     }
-                } while (!pit_value_eq((cur = pit_value_cons_cdr(rt, cur)), PIT_NIL));
-                CHECK_BUF_LABEL(list_end); *(buf++) = ')';
-                list_end:
-                *start = '(';
-                return buf - start;
-            }
-            case PIT_VALUE_HEAVY_SORT_ARRAY: {
-                i64 i = 0;
-                CHECK_BUF_LABEL(array_end);
-                if (h->in.array.len == 0) {
-                    CHECK_BUF_LABEL(array_end); *(buf++) = '[';
-                } else for (; i < h->in.array.len; ++i) {
-                    CHECK_BUF_LABEL(array_end); *(buf++) = ' ';
-                    CHECK_BUF_LABEL(array_end); buf += pit_dump(rt, buf, end - buf, h->in.array.data[i], readable);
+                    buf += i;
+                } else {
+                    buf += pit_libc_string_snprintf(buf, (size_t) len, "<broken symbol %ld>", pit_value_as_symbol(rt, v));
                 }
-                CHECK_BUF_LABEL(array_end); *(buf++) = ']';
-                array_end:
-                *start = '[';
-                return buf - start;
+                break;
             }
-            case PIT_VALUE_HEAVY_SORT_BYTES: {
-                i64 i = 0;
-                if (readable) { CHECK_BUF; buf[i++] = '"'; }
-                i64 maxlen = len - i;
-                for (i64 j = 0; i < maxlen && j < h->in.bytes.len;) {
-                    if (buf[i - 1] != '\\' && (h->in.bytes.data[j] == '\\' || h->in.bytes.data[j] == '"')) {
-                        CHECK_BUF; buf[i++] = '\\';
+            case PIT_VALUE_SORT_REF: {
+                pit_ref r = pit_value_as_ref(rt, v);
+                h = pit_value_ref_deref(rt, r);
+                if (!h) pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
+                else {
+                    switch (h->hsort) {
+                    case PIT_VALUE_HEAVY_SORT_CELL: {
+                        pit_traversal_push_dump_string(rt, rt->traversal, "}");
+                        pit_traversal_push_value(rt, rt->traversal, h->in.cell);
+                        pit_traversal_push_dump_string(rt, rt->traversal, "{");
+                        break;
+                    }
+                    case PIT_VALUE_HEAVY_SORT_CONS: {
+                        i64 expr_stack_reset = rt->expr_stack->next;
+                        pit_value xs = v;
+                        bool first = true;
+                        while (xs != PIT_NIL && pit_value_is_cons(rt, xs)) {
+                            if (pit_vec_push(pit_value)(rt->expr_stack, pit_value_cons_car(rt, xs)) < 0) {
+                                pit_error(rt, "dump expr stack overflow");
+                                goto end;
+                            }
+                            xs = pit_value_cons_cdr(rt, xs);
+                        }
+                        pit_traversal_push_dump_string(rt, rt->traversal, ")");
+                        if (xs != PIT_NIL) {
+                            pit_traversal_push_value(rt, rt->traversal, xs);
+                            pit_traversal_push_dump_string(rt, rt->traversal, " . ");
+                        }
+                        while (rt->expr_stack->next > expr_stack_reset) {
+                            if (first) first = false;
+                            else pit_traversal_push_dump_string(rt, rt->traversal, " ");
+                            pit_value x = PIT_NIL;
+                            if (pit_vec_pop(pit_value)(rt->expr_stack, &x) < 0) {
+                                pit_error(rt, "dump expr stack underflow");
+                                goto end;
+                            }
+                            pit_traversal_push_value(rt, rt->traversal, x);
+                        }
+                        pit_traversal_push_dump_string(rt, rt->traversal, "(");
+                        rt->expr_stack->next = expr_stack_reset;
+                        break;
+                    }
+                    case PIT_VALUE_HEAVY_SORT_ARRAY: {
+                        bool first = true;
+                        pit_traversal_push_dump_string(rt, rt->traversal, "]");
+                        for (i64 i = h->in.array.len - 1; i >= 0; --i) {
+                            if (first) first = false;
+                            else pit_traversal_push_dump_string(rt, rt->traversal, " ");
+                            pit_traversal_push_value(rt, rt->traversal, h->in.array.data[i]);
+                        }
+                        pit_traversal_push_dump_string(rt, rt->traversal, "[");
+                        break;
                     }
-                    else {
-                        CHECK_BUF; buf[i++] = (char) h->in.bytes.data[j++];
+                    case PIT_VALUE_HEAVY_SORT_BYTES: {
+                        i64 i = 0;
+                        if (readable) { buf[i++] = '"'; }
+                        i64 maxlen = len - i;
+                        for (i64 j = 0; i < maxlen && j < h->in.bytes.len;) {
+                            if (buf[i - 1] != '\\' && (h->in.bytes.data[j] == '\\' || h->in.bytes.data[j] == '"')) {
+                                buf[i++] = '\\';
+                            }
+                            else {
+                                buf[i++] = (char) h->in.bytes.data[j++];
+                            }
+                        }
+                        if (readable && i < len - 1) buf[i++] = '"';
+                        buf += i;
+                        break;
+                    }
+                    default:
+                        buf += pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
                     }
                 }
-                if (readable && i < len - 1) buf[i++] = '"';
-                return i;
+                break;
             }
-            default:
-                return pit_libc_string_snprintf(buf, (size_t) len, "<ref %ld>", r);
             }
+            break;
+        }
+        default:
+            pit_error(rt, "unexpected traversal entry"); goto end;
         }
-        break;
-    }
     }
-    return 0;
+end:
+    rt->traversal->next = traversal_reset;
+    return (i64) (buf - start);
+}
+
+i64 pit_dump(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable) {
+    return pit_dump_with_callback(rt, buf, len, v, readable, NULL, NULL);
 }
diff --git a/pit/src/runtime/eval.c b/pit/src/runtime/eval.c
index f5eba97..301d8d0 100644
--- a/pit/src/runtime/eval.c
+++ b/pit/src/runtime/eval.c
@@ -3,11 +3,11 @@
 pit_value pit_eval(pit_runtime *rt, pit_value top) {
     i64 expr_stack_reset = rt->expr_stack->next;
     i64 result_stack_reset = rt->result_stack->next;
-    i64 program_reset = rt->program->next;
+    i64 traversal_reset = rt->traversal->next;
     // pit_vec_reset(pit_annotated_ref)(rt->backtrace);
     if (pit_vec_push(pit_value)(rt->expr_stack, top) < 0)
         pit_error(rt, "evaluation stack overflow");
-    /* first, convert the expression tree into "polish notation" in program */
+    /* first, convert the expression tree into "polish notation" in traversal */
     while (rt->expr_stack->next > expr_stack_reset) {
         pit_value cur = PIT_NIL;
         if (rt->error != PIT_NIL) goto end;
@@ -42,56 +42,56 @@ pit_value pit_eval(pit_runtime *rt, pit_value top) {
                     if (pit_vec_push(pit_value)(rt->expr_stack, fsym) < 0)
                         pit_error(rt, "evaluation stack overflow");
                 }
-                pit_runtime_eval_program_push_apply(rt, rt->program, argcount, ann);
+                pit_traversal_push_application(rt, rt->traversal, argcount, ann);
                 if (is_symbol) {
                     pit_value f = pit_symtab_fget(rt, fsym);
-                    pit_runtime_eval_program_push_literal(rt, rt->program, f);
+                    pit_traversal_push_value(rt, rt->traversal, f);
                 }
             }
         } else if (pit_value_is_symbol(rt, cur)) { /* unquoted symbols: variable lookup */
             pit_symtab_entry *ent = pit_symtab_lookup(rt, cur);
             if (ent->is_keyword) {
-                pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+                pit_traversal_push_value(rt, rt->traversal, cur);
             } else {
-                pit_runtime_eval_program_push_literal(rt, rt->program, pit_symtab_get(rt, cur));
+                pit_traversal_push_value(rt, rt->traversal, pit_symtab_get(rt, cur));
             }
         } else { /* other expressions evaluate to themselves! */
-            pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+            pit_traversal_push_value(rt, rt->traversal, cur);
         }
     }
-    /* then, execute the polish notation program from right to left
+    /* then, execute the polish notation traversal from right to left
        this has the nice consequence of putting the arguments in the right order */
-    for (i64 idx = rt->program->next - 1; idx >= program_reset; --idx) {
-        pit_runtime_eval_ins *ent = pit_vec_get(pit_runtime_eval_ins)(rt->program, idx);
-        if (ent == NULL) pit_error(rt, "evaluation program invalid");
+    for (i64 idx = rt->traversal->next - 1; idx >= traversal_reset; --idx) {
+        pit_traversal_entry *ent = pit_vec_get(pit_traversal_entry)(rt->traversal, idx);
+        if (ent == NULL) pit_error(rt, "evaluation traversal invalid");
         if (rt->error != PIT_NIL) goto end;
         switch (ent->sort) {
-        case PIT_RUNTIME_EVAL_INS_LITERAL:
-            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.literal) < 0)
+        case PIT_TRAVERSAL_ENTRY_VALUE:
+            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.value) < 0)
                 pit_error(rt, "evaluation result stack overflow");
             break;
-        case PIT_RUNTIME_EVAL_INS_APPLY: {
+        case PIT_TRAVERSAL_ENTRY_APPLICATION: {
             pit_value f = PIT_NIL;
             pit_value args = PIT_NIL;
             if (pit_vec_pop(pit_value)(rt->result_stack, &f) < 0)
                 pit_error(rt, "evaluation result stack underflow");
-            for (i64 i = 0; i < ent->in.apply.arity; ++i) {
+            for (i64 i = 0; i < ent->in.application.arity; ++i) {
                 pit_value a = PIT_NIL;
                 if (pit_vec_pop(pit_value)(rt->result_stack, &a) < 0)
                     pit_error(rt, "evaluation result stack underflow");
                 args = pit_value_cons(rt, a, args);
             }
-            if (ent->in.apply.annotation != NULL) {
-                rt->source_line = ent->in.apply.annotation->annotation.line;
-                rt->source_column = ent->in.apply.annotation->annotation.column;
-                pit_vec_push(pit_annotated_ref)(rt->backtrace, *ent->in.apply.annotation);
+            if (ent->in.application.annotation != NULL) {
+                rt->source_line = ent->in.application.annotation->annotation.line;
+                rt->source_column = ent->in.application.annotation->annotation.column;
+                pit_vec_push(pit_annotated_ref)(rt->backtrace, *ent->in.application.annotation);
             }
             if (pit_vec_push(pit_value)(rt->result_stack, pit_value_apply(rt, f, args)) < 0)
                 pit_error(rt, "evaluation result stack underflow");
             break;
         }
         default:
-            pit_error(rt, "unknown program entry");
+            pit_error(rt, "unknown traversal entry");
             goto end;
         }
     }
@@ -101,7 +101,7 @@ end: {
             pit_error(rt, "evaluation result stack underflow");
         rt->expr_stack->next = expr_stack_reset;
         rt->result_stack->next = result_stack_reset;
-        rt->program->next = program_reset;
+        rt->traversal->next = traversal_reset;
         return ret;
     }
 }
diff --git a/pit/src/runtime/macroexpand.c b/pit/src/runtime/macroexpand.c
index 13a4fdd..6252ae1 100644
--- a/pit/src/runtime/macroexpand.c
+++ b/pit/src/runtime/macroexpand.c
@@ -3,7 +3,7 @@
 pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
     i64 expr_stack_reset = rt->expr_stack->next;
     i64 result_stack_reset = rt->result_stack->next;
-    i64 program_reset = rt->program->next;
+    i64 traversal_reset = rt->traversal->next;
     if (pit_vec_push(pit_value)(rt->expr_stack, top) < 0)
         pit_error(rt, "macro expansion stack overflow");
     while (rt->expr_stack->next > expr_stack_reset) {
@@ -23,9 +23,9 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
                     pit_error(rt, "macro expansion stack overflow");
             } else if (is_symbol && pit_symtab_symbol_name_match_cstr(rt, fsym, "defer")) {
                 pit_value args = pit_value_cons_cdr(rt, cur);
-                pit_runtime_eval_program_push_literal(rt, rt->program, pit_value_cons_car(rt, args));
+                pit_traversal_push_value(rt, rt->traversal, pit_value_cons_car(rt, args));
             } else if (is_symbol && pit_symtab_symbol_name_match_cstr(rt, fsym, "quote")) {
-                pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+                pit_traversal_push_value(rt, rt->traversal, cur);
             } else if (is_symbol && pit_symtab_symbol_name_match_cstr(rt, fsym, "lambda")) {
                 pit_value args = pit_value_cons_cdr(rt, cur);
                 pit_value bindings = pit_value_cons_car(rt, args);
@@ -40,8 +40,8 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
                     body = pit_value_cons_cdr(rt, body);
                     argcount += 1;
                 }
-                pit_runtime_eval_program_push_apply(rt, rt->program, argcount + 1, ann);
-                pit_runtime_eval_program_push_literal(rt, rt->program, fsym);
+                pit_traversal_push_application(rt, rt->traversal, argcount + 1, ann);
+                pit_traversal_push_value(rt, rt->traversal, fsym);
             } else {
                 pit_value args = pit_value_cons_cdr(rt, cur);
                 i64 argcount = 0;
@@ -56,46 +56,46 @@ pit_value pit_macroexpand(pit_runtime *rt, pit_value top) {
                     if (pit_vec_push(pit_value)(rt->expr_stack, fsym) < 0)
                         pit_error(rt, "macro expansion stack overflow");
                 }
-                pit_runtime_eval_program_push_apply(rt, rt->program, argcount, ann);
+                pit_traversal_push_application(rt, rt->traversal, argcount, ann);
                 if (is_symbol) {
-                    pit_runtime_eval_program_push_literal(rt, rt->program, fsym);
+                    pit_traversal_push_value(rt, rt->traversal, fsym);
                 }
             }
         } else {
-            pit_runtime_eval_program_push_literal(rt, rt->program, cur);
+            pit_traversal_push_value(rt, rt->traversal, cur);
         }
     }
-    for (i64 idx = rt->program->next - 1; idx >= program_reset; --idx) {
-        pit_runtime_eval_ins *ent = pit_vec_get(pit_runtime_eval_ins)(rt->program, idx);
-        if (ent == NULL) pit_error(rt, "macro expansion program invalid");
+    for (i64 idx = rt->traversal->next - 1; idx >= traversal_reset; --idx) {
+        pit_traversal_entry *ent = pit_vec_get(pit_traversal_entry)(rt->traversal, idx);
+        if (ent == NULL) pit_error(rt, "macro expansion traversal invalid");
         if (rt->error != PIT_NIL) goto end;
         switch (ent->sort) {
-        case PIT_RUNTIME_EVAL_INS_LITERAL:
-            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.literal) < 0)
+        case PIT_TRAVERSAL_ENTRY_VALUE:
+            if (pit_vec_push(pit_value)(rt->result_stack, ent->in.value) < 0)
                 pit_error(rt, "macro expansion stack overflow");
             break;
-        case PIT_RUNTIME_EVAL_INS_APPLY: {
+        case PIT_TRAVERSAL_ENTRY_APPLICATION: {
             pit_value f = PIT_NIL;
             pit_value args = PIT_NIL;
             pit_value app = PIT_NIL;
             if (pit_vec_pop(pit_value)(rt->result_stack, &f) < 0)
                 pit_error(rt, "macro expansion stack underflow");
-            for (i64 i = 0; i < ent->in.apply.arity; ++i) {
+            for (i64 i = 0; i < ent->in.application.arity; ++i) {
                 pit_value a;
                 if (pit_vec_pop(pit_value)(rt->result_stack, &a) < 0)
                     pit_error(rt, "macro expansion stack underflow");
                 args = pit_value_cons(rt, a, args);
             }
             app = pit_value_cons(rt, f, args);
-            if (ent->in.apply.annotation != NULL) {
-                pit_annotation_set(rt, pit_value_as_ref(rt, app), ent->in.apply.annotation->annotation);
+            if (ent->in.application.annotation != NULL) {
+                pit_annotation_set(rt, pit_value_as_ref(rt, app), ent->in.application.annotation->annotation);
             }
             if (pit_vec_push(pit_value)(rt->result_stack, app) < 0)
                 pit_error(rt, "macro expansion stack overflow");
             break;
         }
         default:
-            pit_error(rt, "unknown program entry");
+            pit_error(rt, "unknown traversal entry");
             goto end;
         }
     }
@@ -105,7 +105,7 @@ end: {
             pit_error(rt, "macro expansion stack underflow");
         rt->expr_stack->next = expr_stack_reset;
         rt->result_stack->next = result_stack_reset;
-        rt->program->next = program_reset;
+        rt->traversal->next = traversal_reset;
         return ret;
     }
 }