+TITLE: SPAIK

The SPAIK Lisp implementation:

plus.lisp

+begin_src lisp

(defun plus (&rest xs) (let ((s 0)) (dolist (x xs) (set s (+ s x))) s))

+end_src

call.rs

+begin_src rust

use spaik::spaik::Spaik; use spaik::error::Error;

fn apifunccall() -> Result<(), Error> { let mut vm = Spaik::new()?; vm.load("plus")?; let (x, y, z) = (1, 2, 3); let result: i32 = vm.call("plus", (x, y, z, 4, 5))?; assert_eq!(result, 15); }

+end_src

The implementation includes the following main parts:

• CHASM: generates virtual ISAs from a simple description of op-codes
• R8VM: Stack-based virtual machine
  • Supports tracebacks on errors
• NKGC: Moving tri-color mark-compact garbage collector
• NUKE: Allocation tools for the garbage collector
  • These allocation utilities are written in C
• COMPILER: Single-pass compiler and macro-expander.
• SINTERN: String-interner
• ERROR: Structural error type for gradually building errors upwards through the call stack.
• SPAIK: Public API.

See ~lisp/test.lisp~ and the ~tests/*.lisp~ files for an example of a non-trivial macro, and ~lisp/self.lisp~ for a non-trivial program.

• Usage of ~unsafe~ This crate heavily utilizes ~unsafe~, this is required for the following operations:

* Accessing GC-memory directly *SPAIK uses a moving garbage-collector, meaning that pointers are not necessarily valid after a call to ~gc.collect()~, even if the pointer is known to be part of the root set. External references to GC-allocated memory need to use indirection (see ~SPV~ type,) but this indirection is not used inside the VM and GC internals because of the overhead.

Instead, the VM and GC maintain the following invariant

+begin_quote

A ~PV~ value retrieved from the garbage collector arena may not be used after ~gc.collect()~ runs.

+end_quote

In practice this invariant is very easy to uphold in the internals. The ~unsafe~ blocks themselves are sometimes hidden behind macros for convenience.

+begin_src rust

// An example of unsafe GC memory access, done ergonomically using a macro withrefmut!(vec, Vector(v) => { let elem = v.pop().unwrapor(PV::Nil); self.mem.push(elem); Ok(()) }).maperr(|e| e.op(Builtin::Pop.sym()))?;

+end_src

** Accessing VM program memory Program memory needs to be randomly accessed -- fast. But by default, Rust will use bounds-checking on arrays. This bounds-checking is usually cheap enough, but not for this particular use-case. The VM also only supports relative jumps, which would have required two additions when using indexing, but only one when using pointer arithmetic.

This optimization relies on:

• The correctness of the compiled bytecode, i.e that the compiler does not produce out-of-bounds jumps.
• On-the-fly changes to the bytecode may invalidate the pointer, so all operations that /may/ result in program memory reallocation must reset the pointer.
  • Return-pointers pushed onto the SPAIK call stack are indices, not raw pointers, for this reason.

* Converting between ~u8~ discriminants and ~enum Thing~ *SPAIK often needs to convert integer discriminants into enums, and vice-versa. For this it uses ~unsafe { mem::transmute(num) }~.