Refactor into monorepo

21 files changed, 558 insertions, 0 deletions

diff --git a/pit/include/lcq/pit.h b/pit/include/lcq/pit.h
new file mode 100644
index 0000000..8ff46c8
--- /dev/null
+++ b/pit/include/lcq/pit.h
@@ -0,0 +1,11 @@
+#ifndef LCOLONQ_PIT_H
+#define LCOLONQ_PIT_H
+
+#include <lcq/prelude.h>
+#include <lcq/pit/utils.h>
+#include <lcq/pit/lexer.h>
+#include <lcq/pit/parser.h>
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/library.h>
+
+#endif
diff --git a/pit/include/lcq/pit/arena.h b/pit/include/lcq/pit/arena.h
new file mode 100644
index 0000000..18d7f96
--- /dev/null
+++ b/pit/include/lcq/pit/arena.h
@@ -0,0 +1,45 @@
+#ifndef LCOLONQ_PIT_ARENA_H
+#define LCOLONQ_PIT_ARENA_H
+
+#include <lcq/prelude.h>
+
+typedef i64 pit_arena_index;
+
+static inline uintptr_t pit_align_down(uintptr_t addr, uintptr_t align) {
+    return addr & ~(align - 1); /* easy! just zero the low bits */
+}
+static inline uintptr_t pit_align_up(uintptr_t addr, uintptr_t align) {
+    return (addr + align - 1) /* increment past the next aligned address... */
+        & ~(align - 1); /* ...and then zero the low bits */
+}
+typedef struct {
+    i64 elem_size, /* size of one element */
+        capacity, /* capacity in of data in bytes - only used to reset */
+        next, /* index (in elements) of next element to insert */
+        back; /* index (in bytes) one past the end of data. */
+    /* back starts at capacity, and decreases as you alloc_back */
+    u8 data[];
+} pit_arena;
+
+/* create a new arena in a buffer of buf_len size in bytes that stores elements of elem_size */
+pit_arena *pit_arena_new(u8 *buf, i64 buf_len, i64 elem_size);
+
+/* remove all elements from an array */
+void pit_arena_reset(pit_arena *a);
+
+/* allocate space for one or multiple elements, and return the index of the first element */
+pit_arena_index pit_arena_alloc_index(pit_arena *a);
+pit_arena_index pit_arena_alloc_array_index(pit_arena *a, i64 num);
+
+/* allocate space for one or multiple elements, and return a pointer */
+void *pit_arena_alloc(pit_arena *a);
+void *pit_arena_alloc_array(pit_arena *a, i64 num);
+
+/* retrieve a pointer to the element(s) at a given index */
+void *pit_arena_get(pit_arena *a, pit_arena_index idx);
+
+/* allocate arbitrary bytes on the "back" of the arena.
+   this can be an arbitrary size in bytes */
+void *pit_arena_alloc_back(pit_arena *a, i64 sz);
+
+#endif
diff --git a/pit/include/lcq/pit/lexer.h b/pit/include/lcq/pit/lexer.h
new file mode 100644
index 0000000..d10d9c2
--- /dev/null
+++ b/pit/include/lcq/pit/lexer.h
@@ -0,0 +1,36 @@
+#ifndef LCOLONQ_PIT_LEXER_H
+#define LCOLONQ_PIT_LEXER_H
+
+#include <lcq/prelude.h>
+
+typedef enum {
+    PIT_LEX_TOKEN_ERROR=-1,
+    PIT_LEX_TOKEN_EOF=0,
+    PIT_LEX_TOKEN_LPAREN,
+    PIT_LEX_TOKEN_RPAREN,
+    PIT_LEX_TOKEN_LSQUARE,
+    PIT_LEX_TOKEN_RSQUARE,
+    PIT_LEX_TOKEN_DOT,
+    PIT_LEX_TOKEN_QUOTE,
+    PIT_LEX_TOKEN_INTEGER_LITERAL,
+    PIT_LEX_TOKEN_STRING_LITERAL,
+    PIT_LEX_TOKEN_SYMBOL,
+    PIT_LEX_TOKEN__SENTINEL
+} pit_lex_token;
+
+typedef struct {
+    char *input;
+    i64 len; /* length of input */
+    i64 start, end; /* bounds of the current token */
+    i64 line, column; /* for error reporting only; current line and column */
+    i64 start_line, start_column; /* for error reporting only; line and column of token start */
+    char *error;
+} pit_lexer;
+
+void pit_lex_cstr(pit_lexer *ret, char *buf);
+void pit_lex_bytes(pit_lexer *ret, char *buf, i64 len);
+i64 pit_lex_file(pit_lexer *ret, char *path);
+pit_lex_token pit_lex_next(pit_lexer *st);
+const char *pit_lex_token_name(pit_lex_token t);
+
+#endif
diff --git a/pit/include/lcq/pit/library.h b/pit/include/lcq/pit/library.h
new file mode 100644
index 0000000..dc57655
--- /dev/null
+++ b/pit/include/lcq/pit/library.h
@@ -0,0 +1,12 @@
+#ifndef LCOLONQ_PIT_LIBRARY_H
+#define LCOLONQ_PIT_LIBRARY_H
+
+#include <lcq/pit/runtime.h>
+
+void pit_install_library_essential(pit_runtime *rt);
+void pit_install_library_io(pit_runtime *rt);
+void pit_install_library_plist(pit_runtime *rt);
+void pit_install_library_alist(pit_runtime *rt);
+void pit_install_library_bytestring(pit_runtime *rt);
+
+#endif
diff --git a/pit/include/lcq/pit/parser.h b/pit/include/lcq/pit/parser.h
new file mode 100644
index 0000000..c2f1597
--- /dev/null
+++ b/pit/include/lcq/pit/parser.h
@@ -0,0 +1,21 @@
+#ifndef LCOLONQ_PIT_PARSER_H
+#define LCOLONQ_PIT_PARSER_H
+
+#include <lcq/pit/lexer.h>
+#include <lcq/pit/runtime.h>
+
+typedef struct {
+    pit_lex_token token;
+    i64 start, end;
+    i64 line, column; /* for error reporting */
+} pit_parser_token_info;
+
+typedef struct {
+    pit_lexer *lexer;
+    pit_parser_token_info cur, next;
+} pit_parser;
+
+void pit_parser_from_lexer(pit_parser *ret, pit_lexer *lex);
+pit_value pit_parse(pit_runtime *rt, pit_parser *st, bool *eof);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime.h b/pit/include/lcq/pit/runtime.h
new file mode 100644
index 0000000..d9311b2
--- /dev/null
+++ b/pit/include/lcq/pit/runtime.h
@@ -0,0 +1,96 @@
+#ifndef LCOLONQ_PIT_RUNTIME_H
+#define LCOLONQ_PIT_RUNTIME_H
+
+#include <lcq/prelude.h>
+#include <lcq/pit/utils.h>
+#include <lcq/pit/vec.h>
+#include <lcq/pit/arena.h>
+#include <lcq/pit/lexer.h>
+
+typedef u64 pit_value;
+typedef i64 pit_symbol; /* a symbol at runtime is an index into the runtime's symbol table */
+typedef i64 pit_ref; /* a reference is an index into the runtime's arena */
+PIT_DECLARE_VEC(pit_value)
+
+struct pit_runtime;
+
+/* symbol table entries. these are created/looked up when you intern a symbol */
+typedef struct {
+    pit_value name; /* ref to bytestring */
+    pit_value value; /* ref to cell */
+    pit_value function; /* ref to cell */
+    bool is_macro, is_special_form, is_keyword;
+} pit_symtab_entry;
+PIT_DECLARE_VEC(pit_symtab_entry)
+
+/* annotation attached to (some) heavy values detailing things like line numbers */
+typedef struct {
+    i64 line, column;
+} pit_annotation;
+typedef struct {
+    pit_ref ref;
+    pit_annotation annotation;
+} pit_annotated_ref;
+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 */
+typedef struct {
+    enum {
+        PIT_RUNTIME_EVAL_INS_LITERAL,
+        PIT_RUNTIME_EVAL_INS_APPLY
+    } sort;
+    union {
+        pit_value literal;
+        struct { i64 arity; pit_annotated_ref *annotation; } apply; 
+    } 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);
+
+typedef struct pit_runtime {
+    /* interpreter state */
+    pit_arena *heap; /* all heavy values, bytestrings, and arrays. */
+    /* bytestrings and arrays are allocated at the end (descending), heavy values are allocated at the front */
+    /* this allows us to iterate over only heavy values at the front (useful in Cheney's algorithm for GC */
+    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 */
+    /* 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 */
+    /* bookkeeping */
+    /* "frozen" values offsets: values before these offsets are immutable, and we can reset here later */
+    i64 frozen_values, frozen_symtab;
+    pit_value error; /* error value - if this is non-nil, an error has occured! only tracks the first error */
+    i64 source_line, source_column; /* for error reporting only; line and column of token start */
+    i64 error_line, error_column; /* line and column of token start at time of error */
+} pit_runtime;
+pit_runtime *pit_runtime_new(u8 *buf, i64 len);
+
+void pit_runtime_freeze(pit_runtime *rt); /* freeze the runtime at the current point - everything currently defined becomes immutable */
+void pit_runtime_reset(pit_runtime *rt); /* restore the runtime to the frozen point, resetting everything that has happened since */
+bool pit_runtime_print_error(pit_runtime *rt); /* return true if an error has occured, and print to stderr */
+
+#define pit_debug_trace(rt, v) pit_debug_trace_(rt, "Trace [" __FILE__ ":" PIT_STR(__LINE__) "] %s\n", v)
+void pit_debug_trace_(pit_runtime *rt, char *format, pit_value v);
+pit_value pit_error_get(pit_runtime *rt);
+void pit_error(pit_runtime *rt, char *format, ...);
+
+/* repl / file loading */
+pit_value pit_load_file(pit_runtime *rt, char *path);
+void pit_repl(pit_runtime *rt);
+
+#include <lcq/pit/runtime/value.h>
+#include <lcq/pit/runtime/symtab.h>
+#include <lcq/pit/runtime/dump.h>
+#include <lcq/pit/runtime/macroexpand.h>
+#include <lcq/pit/runtime/eval.h>
+#include <lcq/pit/runtime/gc.h>
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/dump.h b/pit/include/lcq/pit/runtime/dump.h
new file mode 100644
index 0000000..581cba0
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/dump.h
@@ -0,0 +1,10 @@
+#ifndef LCOLONQ_PIT_RUNTIME_DUMP_H
+#define LCOLONQ_PIT_RUNTIME_DUMP_H
+
+#include <lcq/pit/runtime.h>
+
+/* pretty-print a pit value
+   if readable is true, try to produce output that can be machine-read (quotes on strings, etc) */
+i64 pit_dump(pit_runtime *rt, char *buf, i64 len, pit_value v, bool readable);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/eval.h b/pit/include/lcq/pit/runtime/eval.h
new file mode 100644
index 0000000..3dc9e3c
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/eval.h
@@ -0,0 +1,8 @@
+#ifndef LCOLONQ_PIT_RUNTIME_EVAL_H
+#define LCOLONQ_PIT_RUNTIME_EVAL_H
+
+#include <lcq/pit/runtime.h>
+
+pit_value pit_eval(pit_runtime *rt, pit_value e);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/gc.h b/pit/include/lcq/pit/runtime/gc.h
new file mode 100644
index 0000000..49921f0
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/gc.h
@@ -0,0 +1,8 @@
+#ifndef LCOLONQ_PIT_RUNTIME_GC_H
+#define LCOLONQ_PIT_RUNTIME_GC_H
+
+#include <lcq/pit/runtime.h>
+
+void pit_gc(pit_runtime *rt);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/macroexpand.h b/pit/include/lcq/pit/runtime/macroexpand.h
new file mode 100644
index 0000000..bc1f756
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/macroexpand.h
@@ -0,0 +1,8 @@
+#ifndef LCOLONQ_PIT_RUNTIME_MACROEXPAND_H
+#define LCOLONQ_PIT_RUNTIME_MACROEXPAND_H
+
+#include <lcq/pit/runtime.h>
+
+pit_value pit_macroexpand(pit_runtime *rt, pit_value top);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/symtab.h b/pit/include/lcq/pit/runtime/symtab.h
new file mode 100644
index 0000000..ac60523
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/symtab.h
@@ -0,0 +1,27 @@
+#ifndef LCOLONQ_PIT_RUNTIME_SYMTAB_H
+#define LCOLONQ_PIT_RUNTIME_SYMTAB_H
+
+#include <lcq/pit/runtime.h>
+
+pit_symtab_entry *pit_symtab_lookup(pit_runtime *rt, pit_value sym);
+pit_value pit_symtab_intern(pit_runtime *rt, u8 *nm, i64 len);
+pit_value pit_symtab_intern_cstr(pit_runtime *rt, char *nm);
+pit_value pit_symtab_symbol_name(pit_runtime *rt, pit_value sym);
+bool pit_symtab_symbol_name_match(pit_runtime *rt, pit_value sym, u8 *buf, i64 len);
+bool pit_symtab_symbol_name_match_cstr(pit_runtime *rt, pit_value sym, char *s);
+pit_value pit_symtab_get_value_cell(pit_runtime *rt, pit_value sym);
+pit_value pit_symtab_get_function_cell(pit_runtime *rt, pit_value sym);
+pit_value pit_symtab_get(pit_runtime *rt, pit_value sym);
+void pit_symtab_set(pit_runtime *rt, pit_value sym, pit_value v);
+pit_value pit_symtab_fget(pit_runtime *rt, pit_value sym);
+void pit_symtab_fset(pit_runtime *rt, pit_value sym, pit_value v);
+bool pit_symtab_is_symbol_macro(pit_runtime *rt, pit_value sym);
+void pit_symtab_symbol_mark_macro(pit_runtime *rt, pit_value sym);
+void pit_symtab_mset(pit_runtime *rt, pit_value sym, pit_value v);
+bool pit_symtab_is_symbol_special_form(pit_runtime *rt, pit_value sym);
+void pit_symtab_symbol_mark_special_form(pit_runtime *rt, pit_value sym);
+void pit_symtab_sfset(pit_runtime *rt, pit_value sym, pit_value v);
+void pit_symtab_bind(pit_runtime *rt, pit_value sym, pit_value v);
+pit_value pit_symtab_unbind(pit_runtime *rt, pit_value sym);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value.h b/pit/include/lcq/pit/runtime/value.h
new file mode 100644
index 0000000..5820bbd
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value.h
@@ -0,0 +1,59 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_H
+
+#include <lcq/prelude.h>
+#include <lcq/pit/runtime.h>
+
+/* the basic value type - it's just a u64 */
+enum pit_value_sort {
+    PIT_VALUE_SORT_DOUBLE  = 0, /* 0b00 - double */
+    PIT_VALUE_SORT_INTEGER = 1, /* 0b01 - NaN-boxed 49-bit integer */
+    PIT_VALUE_SORT_SYMBOL  = 2, /* 0b10 - NaN-boxed index into symbol table */
+    PIT_VALUE_SORT_REF     = 3  /* 0b11 - NaN-boxed index into "heavy object" arena */
+};
+enum pit_value_sort pit_value_sort(pit_value v);
+u64 pit_value_data(pit_value v);
+
+/* nil is always the symbol with index 0 */
+#define PIT_NIL 0xfff4000000000000 /* 0b1111111111110100000000000000000000000000000000000000000000000000 */
+#define PIT_T   (PIT_NIL+1)
+
+/* "heavy" values, the targets of refs */
+typedef pit_value (*pit_nativefunc)(struct pit_runtime *rt, pit_value args, void *data);
+typedef struct {
+    enum pit_value_heavy_sort {
+        PIT_VALUE_HEAVY_SORT_CELL=0, /* value cell - basically, a "location" referred to by a variable binding */
+        PIT_VALUE_HEAVY_SORT_CONS, /* cons cell - a pair of two values */
+        PIT_VALUE_HEAVY_SORT_ARRAY, /* fixed-size array of values */
+        PIT_VALUE_HEAVY_SORT_BYTES, /* bytestring */
+        PIT_VALUE_HEAVY_SORT_FUNC, /* Lisp closure */
+        PIT_VALUE_HEAVY_SORT_NATIVEFUNC, /* native function */
+        PIT_VALUE_HEAVY_SORT_NATIVEDATA, /* native data (C pointer) */
+        PIT_VALUE_HEAVY_SORT_FORWARDING_POINTER /* forwarding pointer to to-space (during GC) */
+    } hsort;
+    union {
+        pit_value cell;
+        struct { pit_value car, cdr; } cons;
+        struct { pit_value *data; i64 len; } array;
+        struct { u8 *data; i64 len; } bytes;
+        struct { pit_value env; pit_value args; pit_value arg_rest_nm; pit_value body; } func;
+        struct { pit_nativefunc f; void *data; } nativefunc;
+        struct { pit_value tag; void *data; } nativedata;
+        i64 forwarding_pointer;
+    } in;
+} pit_value_heavy;
+
+pit_value pit_value_new(struct pit_runtime *rt, enum pit_value_sort s, u64 data);
+
+bool pit_value_eq(pit_value a, pit_value b);
+bool pit_value_equal(pit_runtime *rt, pit_value a, pit_value b);
+
+#include <lcq/pit/runtime/value/small.h>
+#include <lcq/pit/runtime/value/cell.h>
+#include <lcq/pit/runtime/value/cons.h>
+#include <lcq/pit/runtime/value/bytes.h>
+#include <lcq/pit/runtime/value/array.h>
+#include <lcq/pit/runtime/value/func.h>
+#include <lcq/pit/runtime/value/nativedata.h>
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/array.h b/pit/include/lcq/pit/runtime/value/array.h
new file mode 100644
index 0000000..0e5dd64
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/array.h
@@ -0,0 +1,15 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_ARRAY_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_ARRAY_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* heavy value - array */
+bool pit_value_is_array(pit_runtime *rt, pit_value a);
+pit_value pit_value_array_new(pit_runtime *rt, i64 len);
+pit_value pit_value_array_from_buf(pit_runtime *rt, pit_value *xs, i64 len);
+i64 pit_value_array_len(pit_runtime *rt, pit_value arr);
+pit_value pit_value_array_get(pit_runtime *rt, pit_value arr, i64 idx);
+pit_value pit_value_array_set(pit_runtime *rt, pit_value arr, i64 idx, pit_value v);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/bytes.h b/pit/include/lcq/pit/runtime/value/bytes.h
new file mode 100644
index 0000000..cef5bed
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/bytes.h
@@ -0,0 +1,16 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_BYTES_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_BYTES_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* heavy value - bytes */
+
+bool pit_value_is_bytes(pit_runtime *rt, pit_value a);
+pit_value pit_value_bytes_new(pit_runtime *rt, u8 *buf, i64 len);
+pit_value pit_value_bytes_new_cstr(pit_runtime *rt, char *s);
+pit_value pit_value_bytes_new_file(pit_runtime *rt, char *path);
+bool pit_value_bytes_match(pit_runtime *rt, pit_value v, u8 *buf, i64 len);
+i64 pit_value_bytes_copy(pit_runtime *rt, pit_value v, u8 *buf, i64 maxlen);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/cell.h b/pit/include/lcq/pit/runtime/value/cell.h
new file mode 100644
index 0000000..01c503e
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/cell.h
@@ -0,0 +1,14 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_CELL_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_CELL_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* heavy value - cell */
+
+bool pit_value_is_cell(pit_runtime *rt, pit_value a);
+pit_value pit_value_cell_new(pit_runtime *rt, pit_value v);
+pit_value pit_value_cell_get(pit_runtime *rt, pit_value cell, pit_value sym);
+void pit_value_cell_set(pit_runtime *rt, pit_value cell, pit_value v, pit_value sym);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/cons.h b/pit/include/lcq/pit/runtime/value/cons.h
new file mode 100644
index 0000000..e7f030a
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/cons.h
@@ -0,0 +1,23 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_CONS_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_CONS_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* heavy value - cons/list */
+bool pit_value_is_cons(pit_runtime *rt, pit_value a);
+pit_value pit_value_cons(pit_runtime *rt, pit_value car, pit_value cdr);
+pit_value pit_value_cons_car(pit_runtime *rt, pit_value v);
+pit_value pit_value_cons_cdr(pit_runtime *rt, pit_value v);
+void pit_value_cons_setcar(pit_runtime *rt, pit_value v, pit_value x);
+void pit_value_cons_setcdr(pit_runtime *rt, pit_value v, pit_value x);
+
+pit_value pit_value_list(pit_runtime *rt, i64 num, ...);
+i64 pit_value_list_len(pit_runtime *rt, pit_value xs);
+pit_value pit_value_list_append(pit_runtime *rt, pit_value xs, pit_value ys);
+pit_value pit_value_list_reverse(pit_runtime *rt, pit_value xs);
+pit_value pit_value_list_contains_eq(pit_runtime *rt, pit_value needle, pit_value haystack);
+pit_value pit_value_list_contains_equal(pit_runtime *rt, pit_value needle, pit_value haystack);
+pit_value pit_value_list_plist_get(pit_runtime *rt, pit_value k, pit_value vs);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/func.h b/pit/include/lcq/pit/runtime/value/func.h
new file mode 100644
index 0000000..852c90d
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/func.h
@@ -0,0 +1,15 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_FUNC_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_FUNC_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* heavy value - func / nativefunc */
+bool pit_value_is_func(pit_runtime *rt, pit_value a);
+bool pit_value_is_nativefunc(pit_runtime *rt, pit_value a);
+pit_value pit_value_func_lambda(pit_runtime *rt, pit_value args, pit_value body);
+pit_value pit_value_nativefunc_new_with_data(pit_runtime *rt, pit_nativefunc f, void *data);
+pit_value pit_value_nativefunc_new(pit_runtime *rt, pit_nativefunc f);
+pit_value pit_value_apply(pit_runtime *rt, pit_value f, pit_value args);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/nativedata.h b/pit/include/lcq/pit/runtime/value/nativedata.h
new file mode 100644
index 0000000..f8ffa4e
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/nativedata.h
@@ -0,0 +1,12 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_NATIVEDATA_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_NATIVEDATA_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* heavy value - nativedata */
+bool pit_value_is_nativedata(pit_runtime *rt, pit_value a);
+pit_value pit_value_nativedata_new(pit_runtime *rt, pit_value tag, void *d);
+void *pit_value_nativedata_get(pit_runtime *rt, pit_value tag, pit_value v);
+
+#endif
diff --git a/pit/include/lcq/pit/runtime/value/small.h b/pit/include/lcq/pit/runtime/value/small.h
new file mode 100644
index 0000000..957a670
--- /dev/null
+++ b/pit/include/lcq/pit/runtime/value/small.h
@@ -0,0 +1,31 @@
+#ifndef LCOLONQ_PIT_RUNTIME_VALUE_SMALL_H
+#define LCOLONQ_PIT_RUNTIME_VALUE_SMALL_H
+
+#include <lcq/pit/runtime.h>
+#include <lcq/pit/runtime/value.h>
+
+/* the small values that can be NaN-boxed: doubles, integers, symbols */
+
+#ifndef PIT_NO_DOUBLE
+double pit_value_as_double(pit_runtime *rt, pit_value v);
+bool pit_value_is_double(pit_runtime *rt, pit_value a);
+pit_value pit_value_double_new(pit_runtime *rt, double d);
+#endif
+
+i64 pit_value_as_integer(pit_runtime *rt, pit_value v);
+bool pit_value_is_integer(pit_runtime *rt, pit_value a);
+pit_value pit_value_integer_new(pit_runtime *rt, i64 i);
+pit_value pit_value_bool_new(pit_runtime *rt, bool i);
+
+pit_symbol pit_value_as_symbol(pit_runtime *rt, pit_value v);
+bool pit_value_is_symbol(pit_runtime *rt, pit_value a);
+pit_value pit_value_symbol_new(pit_runtime *rt, pit_symbol s);
+
+pit_ref pit_value_as_ref(struct pit_runtime *rt, pit_value v);
+bool pit_value_is_ref(pit_runtime *rt, pit_value a);
+pit_value pit_value_ref_new(struct pit_runtime *rt, pit_ref r);
+pit_value pit_value_ref_heavy_new(struct pit_runtime *rt);
+pit_value_heavy *pit_value_ref_deref(struct pit_runtime *rt, pit_ref p);
+bool pit_value_is_ref_heavy_sort(struct pit_runtime *rt, pit_value a, enum pit_value_heavy_sort e);
+
+#endif
diff --git a/pit/include/lcq/pit/utils.h b/pit/include/lcq/pit/utils.h
new file mode 100644
index 0000000..4bea479
--- /dev/null
+++ b/pit/include/lcq/pit/utils.h
@@ -0,0 +1,39 @@
+#ifndef LCOLONQ_PIT_UTILS_H
+#define LCOLONQ_PIT_UTILS_H
+
+#include <stdarg.h>
+#include <stddef.h>
+#include <lcq/prelude.h>
+
+/* macro helpers */
+#define PIT_CONCAT(a, b) a ## b
+#define PIT_STRSTR(x) #x
+#define PIT_STR(x) PIT_STRSTR(x)
+
+/* implementations of needed libc functions */
+/* ctype */
+static inline bool pit_libc_ctype_isdigit(int a) { return a >= '0' && a <= '9'; }
+static inline bool pit_libc_ctype_islower(int a) { return a >= 'a' && a <= 'z'; }
+static inline bool pit_libc_ctype_isupper(int a) { return a >= 'A' && a <= 'Z'; }
+static inline bool pit_libc_ctype_isalpha(int a) { return pit_libc_ctype_islower(a) || pit_libc_ctype_isupper(a); }
+static inline bool pit_libc_ctype_isprint(int a) { return a >= 0x20 && a <= 0x7f; }
+static inline bool pit_libc_ctype_isspace(int a) { return a == ' ' || a == '\r' || a == '\n' || a == '\t'; }
+
+/* string */
+static inline size_t pit_libc_string_strlen(char *s) {
+    size_t idx = 0;
+    while (s[idx] != 0) ++idx;
+    return idx;
+}
+static inline u8 *pit_libc_string_memcpy(u8 *dest, u8 *src, size_t n) {
+    size_t i = 0;
+    for (; i < n; ++i) dest[i] = src[i];
+    return dest;
+}
+int pit_libc_string_vsnprintf(char *str, size_t size, char *format, va_list ap);
+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)
+
+#endif
diff --git a/pit/include/lcq/pit/vec.h b/pit/include/lcq/pit/vec.h
new file mode 100644
index 0000000..82276f1
--- /dev/null
+++ b/pit/include/lcq/pit/vec.h
@@ -0,0 +1,52 @@
+#ifndef LCOLONQ_PIT_VEC_H
+#define LCOLONQ_PIT_VEC_H
+
+#include <lcq/prelude.h>
+#include <lcq/pit/utils.h>
+
+#define pit_vec(ty) pit_vec__ ## ty ## __type
+#define pit_vec_new(ty) pit_vec__ ## ty ## __new
+#define pit_vec_reset(ty) pit_vec__ ## ty ## __reset
+#define pit_vec_get(ty) pit_vec__ ## ty ## __get
+#define pit_vec_push(ty) pit_vec__ ## ty ## __push
+#define pit_vec_pop(ty) pit_vec__ ## ty ## __pop
+
+#define PIT_DECLARE_VEC(ty) \
+    typedef struct { \
+        i64 capacity, next; \
+        u8 data[]; \
+    } pit_vec(ty); \
+    static __attribute__ ((unused)) pit_vec(ty) *pit_vec_new(ty)(u8 *buf, i64 buf_len) { \
+        uintptr_t base = (uintptr_t) buf; \
+        uintptr_t aligned = pit_align_up(base, sizeof(void *)); \
+        pit_vec(ty) *ret = (pit_vec(ty) *) aligned; \
+        uintptr_t data = aligned + (i64) sizeof(pit_vec(ty)); \
+        i64 offset = (i64) data - (i64) base; \
+        i64 remaining = (i64) (buf_len - offset); \
+        ret->next = 0; \
+        ret->capacity = remaining; \
+        if ((ret->next + 1) * (i64) sizeof(ty) > ret->capacity) return NULL; \
+        return ret; \
+    } \
+    static __attribute__ ((unused)) void pit_vec_reset(ty)(pit_vec(ty) *s) { \
+        s->next = 0; \
+    } \
+    static __attribute__ ((unused)) ty *pit_vec_get(ty)(pit_vec(ty) *s, i64 i) { \
+        i64 idx = i * (i64) sizeof(ty); \
+        if (idx + (i64) sizeof(ty) > s->capacity) return NULL; \
+        return (ty *) &s->data[idx]; \
+    } \
+    static __attribute__ ((unused)) i64 pit_vec_push(ty)(pit_vec(ty) *s, ty x) { \
+        i64 idx = s->next++ * (i64) sizeof(ty); \
+        if (idx + (i64) sizeof(ty) > s->capacity) { return -1; } \
+        *((ty *) &s->data[idx]) = x; \
+        return s->next - 1; \
+    } \
+    static __attribute__ ((unused)) i64 pit_vec_pop(ty)(pit_vec(ty) *s, ty *v) { \
+        i64 idx = (s->next - 1) * (i64) sizeof(ty); \
+        if (s->next == 0 || idx + (i64) sizeof(ty) > s->capacity) return -1; \
+        *v = *((ty *) &s->data[idx]); \
+        return --s->next; \
+    }
+
+#endif