From a107593b6b362fb68e409c9d7b79427776d137d7 Mon Sep 17 00:00:00 2001 From: LLLL Colonq Date: Tue, 1 Sep 2026 20:59:47 -0400 Subject: pit: Tail call optimization! --- pit/src/native.c | 4 ++-- pit/src/runtime/eval.c | 42 +++++++++++++++++++++++------------------- pit/src/runtime/gc.c | 8 ++++++++ pit/src/runtime/symtab.c | 3 --- 4 files changed, 33 insertions(+), 24 deletions(-) (limited to 'pit/src') diff --git a/pit/src/native.c b/pit/src/native.c index d3f2e95..dbb461d 100644 --- a/pit/src/native.c +++ b/pit/src/native.c @@ -113,8 +113,8 @@ pit_value pit_load_file(pit_runtime *rt, char *path) { check_invariants(rt); if (pit_runtime_print_error(rt)) return PIT_NIL; ret = pit_vm_eval(rt, compiled); check_invariants(rt); if (pit_runtime_print_error(rt)) return PIT_NIL; - pit_gc(rt); - check_invariants(rt); if (pit_runtime_print_error(rt)) return PIT_NIL; + // pit_gc(rt); + // check_invariants(rt); if (pit_runtime_print_error(rt)) return PIT_NIL; } check_invariants(rt); if (pit_runtime_print_error(rt)) return PIT_NIL; return ret; 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); } diff --git a/pit/src/runtime/gc.c b/pit/src/runtime/gc.c index 1cc6547..e96e36b 100644 --- a/pit/src/runtime/gc.c +++ b/pit/src/runtime/gc.c @@ -27,7 +27,9 @@ static pit_value gc_copy_value(pit_runtime *rt, pit_value v) { return v; } } +// #include void pit_gc(pit_runtime *rt) { + // fprintf(stderr, "running gc: heap size is %ld\n", rt->heap->next); rt->frozen_values = 0; rt->frozen_symtab = 0; pit_arena *fromspace = rt->heap; @@ -60,6 +62,11 @@ void pit_gc(pit_runtime *rt) { pit_value *v = pit_vec_get(pit_value)(rt->saved_bindings, i); if (v != NULL) *v = gc_copy_value(rt, *v); /* TODO warn on failure here? */ } + /* the evaluation stack is reachable */ + for (i64 i = 0; i < rt->result_stack->next; ++i) { + pit_value *v = pit_vec_get(pit_value)(rt->result_stack, i); + if (v != NULL) *v = gc_copy_value(rt, *v); /* TODO warn on failure here? */ + } /* recursively populate all reachable values from that initial set */ for (i64 scan = 0; scan < tospace->next; ++scan) { pit_value_heavy *h = pit_arena_get(tospace, scan); @@ -106,4 +113,5 @@ void pit_gc(pit_runtime *rt) { rt->annotations = tospace_ann; rt->annotations_backbuffer = fromspace_ann; pit_hashtable_reset(pit_ref, pit_annotation)(rt->annotations_backbuffer); + // fprintf(stderr, "done! heap size is %ld\n", rt->heap->next); } diff --git a/pit/src/runtime/symtab.c b/pit/src/runtime/symtab.c index 1894208..ca4ecf2 100644 --- a/pit/src/runtime/symtab.c +++ b/pit/src/runtime/symtab.c @@ -104,20 +104,17 @@ void pit_symtab_symbol_mark_special_form(pit_runtime *rt, pit_value sym) { if (!ent) { pit_error(rt, "bad symbol"); return; } ent->is_special_form = true; } -#include void pit_symtab_bind(pit_runtime *rt, pit_value sym, pit_value cell) { /* although we cannot set frozen symbols, we can still bind them temporarily - no need to check */ pit_symtab_entry *ent = pit_symtab_lookup(rt, sym); if (!ent) { pit_error(rt, "bad symbol"); return; } if (pit_vec_push(pit_value)(rt->saved_bindings, ent->value) < 0) pit_error(rt, "binding stack overflow"); ent->value = cell; - fprintf(stderr, "binding: "); pit_dump_to_file(rt, stderr, sym, false); fprintf(stderr, "\n"); } pit_value pit_symtab_unbind(pit_runtime *rt, pit_value sym) { pit_symtab_entry *ent = pit_symtab_lookup(rt, sym); if (!ent) { pit_error(rt, "bad symbol"); return PIT_NIL; } pit_value old = ent->value; if (pit_vec_pop(pit_value)(rt->saved_bindings, &ent->value) < 0) pit_error(rt, "binding stack underflow"); - fprintf(stderr, "unbinding: "); pit_dump_to_file(rt, stderr, sym, false); fprintf(stderr, "\n"); return old; } -- cgit v1.3.1