Docs

Bytecode & VM

Overview

Eta compiles Core IR into a flat sequence of Instructions grouped into BytecodeFunction objects. The VM is a classic stack-based interpreter with a separate frame stack for function calls. All values on the stack are 64-bit NaN-boxed LispVals.

Key sources: bytecode.h · vm.h · emitter.h

BytecodeFunction

Every lambda (and every module’s top-level init) compiles to a BytecodeFunction:

struct BytecodeFunction {
    std::vector<Instruction> code;        // the instruction stream
    std::vector<LispVal>     constants;   // constant pool (literals, func indices)
    uint32_t                 arity;       // required parameter count
    bool                     has_rest;    // accepts variadic rest arg?
    uint32_t                 stack_size;  // frame size (locals + temporaries)
    std::string              name;        // debug name (e.g., "my-module:my-func" or "<lambda@my-module:12:7>")
};

struct Instruction {
    OpCode   opcode;
    uint32_t arg;   // meaning depends on opcode
};

Functions are stored in a BytecodeFunctionRegistry (thread-safe, std::deque-backed for pointer stability). Closures reference functions by index rather than raw pointer.

Opcode Reference

Data Movement

Control Flow

Closures

Arithmetic & Primitives

Exception Handling

The catch/raise forms compile to this pattern:

;; (catch 'err body)
SetupCatch  (tag_const_idx << 16 | offset_to_after_handler)
  <emit body>
PopCatch                        ; normal exit — discard frame
Jump        past_handler
  <handler: caught value already on stack>

Unification / Logic Variables

These opcodes implement Robinson-style structural unification directly in the VM. See Logic Programming for a full description of the semantics.

Trail invariant: the trail is a per-VM std::vector<LispVal> that records the boxed reference of every logic variable that was bound. TrailMark / UnwindTrail implement Prolog choice-point semantics without requiring a separate WAM-style stack.

Example — binding and backtracking:

;; (define x (logic-var))
MakeLogicVar         ; → HeapObj(lvar, id=7)
StoreGlobal  N
Pop

;; (define m (trail-mark))
TrailMark            ; → Fixnum(0)   trail is empty
StoreGlobal  M
Pop

;; (unify x 42)
LoadGlobal   N       ; push HeapObj(7)
LoadConst    K       ; push Fixnum(42)
Unify                ; deref both, bind lv[7]→42, trail=[HeapObj(7)], push #t
Pop

;; (unwind-trail m)
LoadGlobal   M       ; push Fixnum(0)
UnwindTrail          ; trail.size()=1 > 0 → pop HeapObj(7), reset lv[7].binding=nullopt

;; (logic-var? (deref-lvar x))
LoadGlobal   N       ; push HeapObj(7)
DerefLogicVar        ; lv[7].binding=nullopt → push HeapObj(7) (still a lvar)
CallBuiltin "logic-var?"   ; → #t

Tape-Based Reverse-Mode AD

The VM provides tape-based (Wengert list) reverse-mode automatic differentiation. When a tape is active, the arithmetic opcodes Add, Sub, Mul, Div and the builtins exp, log, sqrt, sin, cos transparently record every operation involving a TapeRef operand onto the active tape.

Tape-aware arithmetic: When do_binary_arithmetic detects that either operand is a TapeRef, it:

1. Looks up the primals from the active tape
2. Computes the forward result
3. Appends a new tape entry recording the operation, operand indices, and the primal result (~32 bytes)
4. Returns a new TapeRef pointing to the appended entry

The builtins exp, log, sqrt, sin, cos follow the same pattern. The backward pass (tape-backward!) sweeps the tape in reverse, accumulating adjoints via the chain rule — zero closures allocated.

See AAD documentation for a full description and European Option Greeks for a worked example.

End-to-End Example

Let’s trace the compilation and execution of a small program:

Source

(module example
  (begin
    (defun add1 (x) (+ x 1))
    (add1 41)))

Stage 1 — Expand

defun is desugared to define + lambda:

(module example
  (begin
    (define add1 (lambda (x) (+ x 1)))
    (add1 41)))

Stage 2 — Semantic Analysis (Core IR)

The analyzer produces these IR nodes for the module init function:

toplevel_inits:
  [0] Set { target: Global(slot=N), value: Lambda { ... } }
  [1] Call { callee: Var(Global(N)), args: [Const(41)] }

Lambda "add1":
  params: [x → Local(0)]
  stack_size: 2
  body: Call { callee: Var(Global(+)),   ← builtin "+" at its fixed global slot
               args: [Var(Local(0)),     ← x
                      Const(1)] }
  tail: true  (the call is in tail position of the lambda body)

Stage 3 — Emit Bytecode

add1 lambda → example:add1:

  constants: [ <fixnum 1> ]
  arity: 1, has_rest: false, stack_size: 2

  0: LoadLocal    0        ;; push x
  1: LoadConst    0        ;; push 1
  2: Add                   ;; push (+ x 1)
  3: Return                ;; return result

Note

With etac -O, (+ x 1) in tail position is lowered to the specialized rather than a TailCall to the + builtin — the emitter optimizes known arithmetic into dedicated opcodes.

Module init → example_init:

  constants: [ <func_index:0>, <Nil>, <fixnum 41> ]
  arity: 0, has_rest: false, stack_size: N

  ;; (define add1 (lambda (x) (+ x 1)))
  0: MakeClosure  (0 << 16 | 0)   ;; make closure from func_index 0, 0 upvals
  1: StoreGlobal  N                ;; globals[N] = add1
  2: Pop                           ;; discard set! result

  ;; (add1 41)
  3: LoadConst    2                ;; push 41
  4: LoadGlobal   N                ;; push add1 closure
  5: Call         1                ;; call add1(41)
  6: Pop                           ;; discard expr result (module init)

  ;; Module init returns nil
  7: LoadConst    1                ;; push Nil
  8: Return

Stage 4 — VM Execution Trace

Executing: example_init
  pc=0  MakeClosure(0,0)  → creates Closure{func=&example:add1, upvals=[]}
                            pushes HeapObject(id=…) onto stack
  pc=1  StoreGlobal(N)    → globals[N] = pop()   (add1 closure stored)
  pc=2  Pop               → discard nil from set!
  pc=3  LoadConst(2)      → push 41
  pc=4  LoadGlobal(N)     → push Closure(add1)
  pc=5  Call(1)           → pop callee, set up new frame:
                            frame = {func=example:add1, fp=top-1, pc=0}

Executing: example:add1  (fp points to stack slot with 41)
  pc=0  LoadLocal(0)      → push stack[fp+0] = 41
  pc=1  LoadConst(0)      → push 1
  pc=2  Add               → pop 1, pop 41, push 42
  pc=3  Return            → pop 42, restore caller frame, push 42

Back in example_init:
  pc=6  Pop               → discard 42
  pc=7  LoadConst(1)      → push Nil
  pc=8  Return            → execution complete, result = Nil

Result: (add1 41) evaluates to 42. ✓

Call Stack Model

Each Frame stores:

Frame Kinds

Tail-Call Elimination

When the emitter detects a call in tail position (Node::tail == true), it emits TailCall or TailApply instead of Call / Apply.

Regular Call:

push args → push callee → Call(argc)
  → save current frame to frame stack
  → set up new frame

Tail Call:

push args → push callee → TailCall(argc)
  → overwrite current frame's stack slots with new args
  → reset pc to 0
  → NO new frame pushed

This means recursive functions like:

(defun loop (n acc)
  (if (= n 0) acc
      (loop (- n 1) (+ acc n))))

run in O(1) stack space — the frame stack never grows.

Closure Creation & Upvalue Patching

MakeClosure

When a lambda captures variables from an enclosing scope, the emitter:

1. Pushes each captured variable’s current value onto the stack
2. Emits MakeClosure with the function index and upvalue count

LoadLocal  2          ;; push captured var 'x' (local slot 2 in parent)
LoadUpval  0          ;; push captured var 'y' (upval 0 in parent)
MakeClosure (idx<<16 | 2)  ;; create closure with 2 upvals

The VM allocates a Closure object on the heap containing a pointer to the BytecodeFunction and a vector of upvalue LispVals.

PatchClosureUpval (Letrec Self-Reference)

For letrec bindings where a lambda refers to itself:

(letrec ((f (lambda (n) (if (= n 0) 1 (f (- n 1))))))
  (f 5))

At MakeClosure time, f isn’t defined yet (its slot contains Nil). The emitter generates:

MakeClosure  ...       ;; creates closure with stale upval for 'f'
StoreLocal   slot      ;; store closure in f's local slot
LoadLocal    slot      ;; push the closure (for patching)
LoadLocal    slot      ;; push itself as the new upval value
PatchClosureUpval  0   ;; closure.upvals[0] = closure itself

Function Resolution

Closures store function references as indices (not raw pointers) for safety. The FUNC_INDEX_TAG (bit 63) distinguishes function indices from regular LispVal constants:

constexpr uint64_t FUNC_INDEX_TAG = 1ULL << 63;

inline LispVal encode_func_index(uint32_t index) {
    return FUNC_INDEX_TAG | static_cast<uint64_t>(index);
}

When MakeClosure encounters a function-index constant, it calls the FunctionResolver callback (wired by the Driver) to look up the BytecodeFunction* from the BytecodeFunctionRegistry.