N.I.S.S.E. Bytecode VM Architecture

Overview

N.I.S.S.E. (Naive Interpreter for Small Shell Erlang) implements a bytecode compilation and execution model, mirroring the architecture of the real BEAM VM. This moves the system from a tree-walking interpreter to a true virtual machine with separate compilation and runtime phases.

Quick Start

Interactive REPL: Press ~ to open the CLI, then type erl and press Enter to launch the browser-based REPL.

The REPL provides an interactive environment for:

Architecture Components

1. Compiler (nisse-compiler.js)

Transforms human-readable Erlang-like source code into bytecode instructions.

Opcodes with Reduction Costs:

Supported Syntax:

Example:

% Main module
print(starting_system)
spawn(worker)
halt

Compiles to:

[
  { op: 10, val: 'starting_system' },
  { op: 8, arg: 'worker' },
  { op: 9 }
]

2. Virtual Machine (nisse-vm.js)

Executes bytecode with process scheduling, memory isolation, and concurrent execution.

Process Structure:

Scheduler:

Code Server:

Execution Model:

while (runnable) {
  1. Dequeue next process from run queue
  2. Grant 10 reduction quota
  3. Execute instructions until quota exhausted
  4. If still runnable, enqueue back to run queue
  5. Repeat
}

3. CLI Shell (nisse-cli.js)

Entry point demonstrating concurrent process execution.

Example Program:

const pingPongCode = `
print(starting_ping_pong)
spawn(player)
spawn(player)
halt
`;

const playerCode = `
start:
print(ping)
print(pong)
goto(start)
`;

vm.load('main', compile(pingPongCode));
vm.load('player', compile(playerCode));
vm.spawn('main');
vm.step();

Output:

--- N.I.S.S.E. VM Booting ---
[<1>] starting_ping_pong
[<1>] Spawned <2>
[<1>] Spawned <3>
[<2>] ping
[<2>] pong
[<3>] ping
[<3>] pong
[<2>] ping
[<3>] pong
...

Call Semantics and Tail Call Optimization

Normal Procedure Call (CALL opcode)

{ op: 2, fn: 'factorial' }  // Cost: 2 reductions

When executing a CALL instruction:

  1. Push current pc (return address) onto call stack
  2. Load target function bytecode into proc.code
  3. Reset pc to 0 (start of function)
  4. Consume 2 reductions (higher cost reflects stack manipulation)

Return (RET opcode)

{ op: 3 }  // Cost: 1 reduction

When executing a RET instruction:

  1. Pop return address from call stack
  2. Restore pc to continue after the call
  3. If stack is empty, terminate process
  4. Consume 1 reduction

Tail Call Optimization (JUMP opcode)

{ op: 4, label: 'loop' }  // Cost: 1 reduction (stack-free)

When executing a JUMP instruction:

  1. Find target label in current bytecode
  2. Update pc directly (no stack push)
  3. Consume 1 reduction (prevents infinite loops from monopolizing CPU)
  4. Enables infinite recursion without stack growth

Example: Tail-Recursive Loop

loop:
  print(ping)
  print(pong)
  goto(loop)  % Tail call - runs forever without stack overflow

Tail calls are "optimized" because they avoid stack growth, not because they're free. Each iteration still costs 1 reduction to ensure fair scheduling. After 10 reductions, the process yields to other processes in the run queue.

Reduction Costs by Operation Type

Category Operation Cost Rationale
Memory MOVE 1 Simple register write
Control JUMP 1 No stack growth, still scheduled fairly
Control JUMP_IF 1 Conditional evaluation
Control RET 1 Stack pop
Function CALL 2 Stack push + context switch
Process SPAWN 3 Process creation overhead
IPC SEND 2 Message passing cost
IPC RECV N/A Suspends if blocking
Math MATH 1 Arithmetic operation
I/O PRINT 1 Output operation
System HALT 0 Process termination

Key Insight: JUMP costs 1 reduction (same as other operations) to prevent CPU monopolization. The "optimization" is zero stack growth, allowing infinite tail recursion. Compare to CALL which costs 2 reductions and grows the stack.

Key Architectural Benefits

Separation of Concerns

Concurrency Model

Performance Characteristics

Erlang/BEAM Fidelity

This architecture mirrors the real BEAM VM:

Running the VM

cd /workspaces/hh/src/code
node nisse-cli.js

Watch two concurrent processes (<2> and <3>) run in interleaved time slices, demonstrating true concurrent execution managed by the VM scheduler.

Future Enhancements

Compiler

VM

Runtime

Comparison: Interpreter vs VM

Tree-Walking Interpreter (Previous)

function evalExpr(ast, env) {
  if (ast.type === 'call') {
    // Parse function name
    // Evaluate arguments
    // Execute function
  }
}

Bytecode VM (Current)

function execute(proc, instr) {
  if (instr.op === OP.CALL) {
    // Direct dispatch to handler
    // No parsing, just execution
  }
}

The bytecode approach eliminates parse overhead on every execution, enables code serialization, and provides clear compilation boundaries for optimization passes.

References

Version: N.I.S.S.E. VM 0.1 Date: 2025-11-26 Author: Happi Hacking