From a107593b6b362fb68e409c9d7b79427776d137d7 Mon Sep 17 00:00:00 2001
From: LLLL Colonq <llll@colonq>
Date: Tue, 1 Sep 2026 20:59:47 -0400
Subject: pit: Tail call optimization!

---
 pit/src/runtime/eval.c | 42 +++++++++++++++++++++++-------------------
 1 file changed, 23 insertions(+), 19 deletions(-)

(limited to 'pit/src/runtime/eval.c')

diff --git a/pit/src/runtime/eval.c b/pit/src/runtime/eval.c
index f149246..b0b53b6 100644
--- a/pit/src/runtime/eval.c
+++ b/pit/src/runtime/eval.c
@@ -4,7 +4,6 @@
 
 /* add a new stack frame to the vm (with a tag and callsite annotation) */
 static void vm_push_code_func(pit_runtime *rt, pit_value code, pit_value tag, pit_annotation ann, pit_value bound) {
-    fprintf(stderr, "running: "); pit_dump_to_file(rt, stderr, code, false); fprintf(stderr, "\n");
     pit_callstack_entry ent;
     ent.tag = tag;
     ent.ann = ann;
@@ -27,7 +26,6 @@ static void vm_push(pit_runtime *rt, pit_value v) {
     if (pit_vec_push(pit_value)(rt->result_stack, v) < 0) {
         pit_error(rt, "vm stack overflow");
     }
-    fprintf(stderr, "result push!: %ld\n", rt->result_stack->next);
 }
 
 static pit_value vm_pop(pit_runtime *rt) {
@@ -35,7 +33,6 @@ static pit_value vm_pop(pit_runtime *rt) {
     if (pit_vec_pop(pit_value)(rt->result_stack, &ret) < 0) {
         pit_error(rt, "vm stack underflow");
     }
-    fprintf(stderr, "result pop!: %ld\n", rt->result_stack->next);
     return ret;
 }
 
@@ -107,29 +104,35 @@ static bool vm_call(pit_runtime *rt, pit_value f, pit_value args) {
     return true;
 }
 
-/* run one instruction of the VM */
-bool pit_vm_run_one(pit_runtime *rt) {
-start:
-    if (rt->callstack->next < 1) return false;
-    pit_callstack_entry *ent = pit_vec_get(pit_callstack_entry)(rt->callstack, rt->callstack->next - 1);
-    if (ent == NULL) {
-        pit_error(rt, "malformed call stack");
-        return false;
-    }
-    if (ent->code == PIT_NIL) { /* if we encounter an empty stack frame... */
+static void vm_erase_empty(pit_runtime *rt) {
+    pit_callstack_entry *ent = NULL;
+    while ((ent = pit_vec_get(pit_callstack_entry)(rt->callstack, rt->callstack->next - 1))
+        && ent->code == PIT_NIL) {
         pit_value bound = ent->bound;
         while (bound != PIT_NIL) { /* unbind everything we bound for the frame, in reverse */
             pit_symtab_unbind(rt, pit_value_cons_car(rt, bound));
             bound = pit_value_cons_cdr(rt, bound);
         }
         pit_vec_pop(pit_callstack_entry)(rt->callstack, NULL); /* pop the frame, and try again */
-        goto start;
     }
+}
+
+/* run one instruction of the VM */
+bool pit_vm_run_one(pit_runtime *rt) {
+    if (rt->callstack->next < 1) return false;
+    vm_erase_empty(rt);
+    pit_callstack_entry *ent = pit_vec_get(pit_callstack_entry)(rt->callstack, rt->callstack->next - 1);
+    if (ent == NULL) { pit_error(rt, "malformed call stack"); return false; }
+    // for (i64 i = 0; i < rt->callstack->next; ++i) {
+    //     pit_callstack_entry *e = pit_vec_get(pit_callstack_entry)(rt->callstack, i);
+    //     fprintf(stderr, "frame: "); pit_dump_to_file(rt, stderr, e->code, false); fprintf(stderr, "\n");
+    // }
     pit_value ins = pit_value_cons_car(rt, ent->code);
+    // fprintf(stderr, "ins: "); pit_dump_to_file(rt, stderr, ins, false); fprintf(stderr, "\n");
+    // fprintf(stderr, "foo: "); pit_dump_to_file(rt, stderr, pit_symtab_get_function_cell(rt, pit_symtab_intern_cstr(rt, "foo")), false); fprintf(stderr, "\n");
     if (ins == PIT_NIL) { pit_error(rt, "malformed vm instruction"); return false; }
     ent->code = pit_value_cons_cdr(rt, ent->code);
     pit_value op = pit_value_cons_car(rt, ins);
-    fprintf(stderr, "ins: "); pit_dump_to_file(rt, stderr, ins, false); fprintf(stderr, "\n");
     if (pit_symtab_symbol_name_match_cstr(rt, op, "literal")) {
         /* push a lisp value to the vm stack */
         vm_push(rt, pit_value_cons_car(rt, pit_value_cons_cdr(rt, ins)));
@@ -156,6 +159,7 @@ start:
         pit_value c = vm_pop(rt);
         pit_value t = vm_pop(rt);
         pit_value e = vm_pop(rt);
+        vm_erase_empty(rt);
         vm_push_code(rt, c != PIT_NIL ? t : e);
     } else if (pit_symtab_symbol_name_match_cstr(rt, op, "apply")) {
         /* pop an arity n and a function, and then n arguments, and apply the function */
@@ -163,6 +167,7 @@ start:
         pit_value f = vm_pop(rt);
         pit_value args = PIT_NIL;
         while (arity-- > 0) args = pit_value_cons(rt, vm_pop(rt), args);
+        vm_erase_empty(rt);
         if (!vm_call(rt, f, args)) return false;
     } else {
         pit_error(rt, "unknown vm operation");
@@ -176,10 +181,9 @@ pit_value pit_vm_eval(pit_runtime *rt, pit_value v) {
     i64 start = rt->callstack->next;
     vm_push_code(rt, v);
     while (pit_vm_run_one(rt) && rt->callstack->next > start) {
-        // if (rt->expr_stack->next == 0 && rt->compilation_stack->next == 0) {
-        //     fprintf(stderr, "running gc\n");
-        //     pit_gc(rt); /* TODO hack to avoid running GC during macroexpansion */
-        // }
+        if (rt->expr_stack->next == 0 && rt->compilation_stack->next == 0) {
+            pit_gc(rt); /* TODO hack to avoid running GC during macroexpansion */
+        }
     }
     return vm_pop(rt);
 }
-- 
cgit v1.3.1