ButterStack 🧈📚

ButterStack is an experimental stack-based virtual machine written in Go that can compile and execute Lisp-like S-expressions. It provides a complete execution environment with its own bytecode instruction set, object system, and runtime.

⚠️ This project is experimental and still under development. Expect missing features, rough edges, and breaking changes.

Overview

ButterStack is a stack-based virtual machine that can:

• Compile S-expressions to bytecode instructions
• Execute bytecode on a stack-based architecture
• Manage memory with a dynamic object system
• Handle functions with local scoping and call frames
• Support variables with global and local variable tables
• Provide control flow through conditional jumps and loops

The VM accepts Lisp-like S-expression syntax as input, which gets compiled to bytecode and executed on the virtual machine.

Architecture

ButterStack consists of four main components that form a complete compilation and execution pipeline:

1. Lexer (parser/lexer.go)

The lexer tokenizes S-expression input, breaking it down into meaningful tokens:

• Parentheses: ( and ) for S-expression structure
• Symbols: Function names, variable names, operators
• Numbers: Integers (42) and floats (3.14)
• Strings: String literals with escape sequence support ("hello world")
• Comments: Ignored during tokenization (; to end of line)

2. Parser (parser/parser.go)

The parser takes tokens from the lexer and builds an Abstract Syntax Tree (AST) of S-expressions:

• Atoms: SymbolAtom, IntAtom, FloatAtom, StringAtom, BooleanAtom
• Lists: Nested S-expressions representing function calls and expressions
• Multiple Expressions: Support for parsing multiple top-level expressions

3. Compiler (butter/compiler.go)

The compiler transforms the AST into bytecode instructions for the virtual machine:

• Two-pass compilation: First pass generates code, second pass resolves labels
• Special Forms: Handles set, begin, print, if, while, func
• Function Management: Generates function definitions with proper scoping
• Label Resolution: Manages jumps and function calls with label patching

4. Virtual Machine (butter/machine.go)

The VM executes the compiled bytecode using a stack-based architecture:

• Stack Operations: Push/pop values for computation
• Call Stack: Manages function calls with local variable scoping
• Variable Table: Global and local variable storage
• Instruction Execution: Processes bytecode instructions sequentially

Virtual Machine Architecture

The ButterStack VM is a stack-based virtual machine that operates on these principles:

1. Values are pushed onto a stack
2. Operations pop values from the stack, compute results, and push results back
3. Instructions are executed sequentially with support for jumps and calls

VM Components

• Stack: Stores all values and intermediate computation results ([]Object)
• Program Counter (PC): Points to the current instruction being executed
• Variable Table: Global variables (map[string]Object)
• Call Stack: Function call frames with local variables ([]CallFrame)
• Stack Pointer (SP): Points to the top of the value stack

Object System

The VM uses a dynamic object system (butter/object.go) with these types:

• TypeInt64: 64-bit integers
• TypeFloat64: 64-bit floating point numbers
• TypeString: UTF-8 strings
• TypeBool: Boolean values (#t/#f)
• TypeFunc: Function objects (contain bytecode Program)
• TypeNil: Null/empty values

Instruction Set

Instruction	Operand	Description
OP_PUSH	Object	Push a value onto the stack
OP_POP	-	Pop the top value from stack
OP_DUP	-	Duplicate top stack value
OP_SWAP	-	Swap top two stack values
OP_OVER	-	Copy second stack value to top
OP_ROT	-	Rotate top three stack values
OP_LOAD	String	Load variable value onto stack
OP_STORE	String	Store top stack value in variable
OP_CALL	String/Int	Call function by name or address
OP_RET	-	Return from function
OP_JZ	Int	Jump to address if top value is zero/false
OP_JMP	-	Conditional jump (pops boolean from stack)
OP_GOTO	Int	Unconditional jump to address
OP_ADD	-	Pop two values, push sum
OP_MINUS	-	Pop two values, push difference
OP_MUL	-	Pop two values, push product
OP_DIV	-	Pop two values, push quotient
OP_MOD	-	Pop two values, push modulo (integers only)
OP_EQ	-	Pop two values, push equality test
OP_NE	-	Pop two values, push inequality test
OP_GT	-	Pop two values, push greater-than test
OP_LT	-	Pop two values, push less-than test
OP_GTE	-	Pop two values, push greater-or-equal test
OP_LTE	-	Pop two values, push less-or-equal test
OP_AND	-	Pop two booleans, push logical AND
OP_OR	-	Pop two booleans, push logical OR
OP_NOT	-	Pop boolean, push logical NOT
OP_PRINT	-	Pop and print top value
OP_HALT	-	Stop execution

S-Expression Input Examples

The VM accepts Lisp-like S-expressions as input:

Basic Syntax

; Print a simple message
(print "Hello, ButterStack!")

; Arithmetic operations
(print (+ 2 3))        ; Output: 5
(print (* 4 5))        ; Output: 20
(print (- 10 3))       ; Output: 7

; Variables (using 'set' not 'define')
(set x 42)
(print x)              ; Output: 42

; Conditional expressions
(if (> x 0)
    (print "positive")
    (print "not positive"))

; Multiple expressions in sequence
(begin
    (print "First")
    (print "Second")
    (print "Third"))

Functions

; Define a function
(func add (a b)
    (+ a b))

; Call the function
(print (add 5 3))      ; Output: 8

; Function with multiple statements
(func greet (name)
    (begin
        (print "Hello")
        (print name)))

(greet "ButterStack")  ; Output: HelloButterStack

; Recursive function
(func factorial (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

(print (factorial 5))  ; Output: 120

Generated Bytecode Examples

When the VM compiles S-expressions, it generates bytecode instructions. Here are some examples:

Simple Arithmetic: (+ 2 3)

000: PUSH 2            ; Push integer 2 onto stack
001: PUSH 3            ; Push integer 3 onto stack
002: ADD               ; Pop 3,2; push 5
003: HALT              ; Stop execution

Variable Operations: (set x 42) (print x)

000: PUSH 42           ; Push integer 42 onto stack
001: STORE x           ; Store 42 in variable 'x'
002: LOAD x            ; Load variable 'x' onto stack
003: PRINT             ; Pop and print value
004: HALT              ; Stop execution

Conditional: (if (> x 0) (print "pos") (print "neg"))

000: LOAD x            ; Load variable x onto stack
001: PUSH 0            ; Push 0 onto stack
002: GT                ; Pop 0,x; push (x > 0)
003: JZ _if_alternative_0  ; If false, jump to alternative
004: PUSH "pos"        ; Push "pos" string
005: PRINT             ; Print "pos"
006: GOTO _if_end_0    ; Jump to end
007: PUSH "neg"        ; Alternative: push "neg"
008: PRINT             ; Print "neg"
009: HALT              ; End

Function Definition: (func add (a b) (+ a b))

; Main program:
000: GOTO func_add_end_0   ; Jump over function definition
001: STORE b           ; Store parameter 'b' (popped from stack)
002: STORE a           ; Store parameter 'a' (popped from stack)
003: LOAD a            ; Load parameter a
004: LOAD b            ; Load parameter b
005: ADD               ; Add them
006: RET               ; Return result
007: HALT              ; End of program

; When calling (add 5 3):
; PUSH 5, PUSH 3, CALL func_add_start_0

Usage

Building and Running

# Build the project
go build ./cmd

# Run S-expressions on the VM
./butterstack program.btr

# Or run directly with go
go run ./cmd program.btr

Example Program

Create a file example.btr:

; Define some variables
(set pi 3.14159)
(set radius 5)

; Define a function to calculate area
(func circle-area (r)
    (* pi (* r r)))

; Calculate and print the area
(set area (circle-area radius))
(print "Circle area: ")
(print area)

; Conditional logic
(if (> area 50)
    (print "Large circle!")
    (print "Small circle"))

Run it:

./butterstack example.btr

Output:

Circle area: 78.539750Large circle!took 0ms

File Extensions

• .btr - S-expression source files (input for the VM)
• .butter - Bytecode files (compiled instructions)

Special Forms

The VM's compiler recognizes these special forms with custom compilation:

• (set var value) - Variable assignment
• (begin expr1 expr2 ...) - Sequential execution
• (print expr) - Print expression result
• (if condition consequent alternative) - Conditional
• (while condition body...) - Loops
• (func name (params...) body) - Function definition

All other forms are treated as function calls.

Current Limitations

• No module/import system
• Limited built-in functions
• Simple error reporting
• No interactive REPL
• Functions must be defined before use
• No closures or lexical scoping beyond function parameters