diff options
Diffstat (limited to 'awk/vm')
| -rw-r--r-- | awk/vm/README.md | 91 | ||||
| -rwxr-xr-x | awk/vm/compiler.py | 172 | ||||
| -rw-r--r-- | awk/vm/debug.coffee | 6 | ||||
| -rw-r--r-- | awk/vm/simple.coffee | 4 | ||||
| -rw-r--r-- | awk/vm/simple_test.coffee | 8 | ||||
| -rw-r--r-- | awk/vm/stack_test.coffee | 15 | ||||
| -rw-r--r-- | awk/vm/test.coffee | 7 | ||||
| -rw-r--r-- | awk/vm/test_steps.coffee | 15 | ||||
| -rwxr-xr-x | awk/vm/vm.awk | 254 | ||||
| -rwxr-xr-x | awk/vm/vm_tests.sh | 42 |
10 files changed, 614 insertions, 0 deletions
diff --git a/awk/vm/README.md b/awk/vm/README.md new file mode 100644 index 0000000..83a35fd --- /dev/null +++ b/awk/vm/README.md @@ -0,0 +1,91 @@ +# Stack-Based Virtual Machine in AWK + +A simple stack-based virtual machine implementation in AWK, inspired by Forth. The VM provides basic stack manipulation, arithmetic operations, register access, and memory operations. + +## Architecture + +The VM consists of: +- A data stack (100 elements) +- Main memory (1000 cells) +- Three registers: + - A: General purpose register + - B: Often used as memory pointer + - P: Program pointer, used for sequential memory operations + +## Instruction Set + +### Stack Operations +- `DROP` - Remove top item from stack +- `DUP` - Duplicate top stack item +- `OVER` - Copy second item to top of stack +- `SWAP` - Exchange top two stack items +- Numbers are automatically pushed onto the stack + +### Arithmetic Operations +- `+` - Add top two stack items (a b -- a+b) +- `*` - Multiply top two stack items (a b -- a*b) +- `AND` - Bitwise AND of top two items +- `XOR` - Bitwise XOR of top two items +- `NOT` - Bitwise NOT of top item +- `2*` - Multiply top item by 2 (shift left) +- `2/` - Divide top item by 2 (shift right) + +### Register Operations +- `A` - Push value of A register onto stack +- `A!` - Store top stack value into A register +- `B!` - Store top stack value into B register + +### Memory Operations +- `@` - Fetch from memory address on stack (addr -- value) +- `!` - Store to memory address on stack (value addr --) +- `@+` - Fetch from memory at P, then increment P +- `!+` - Store to memory at P, then increment P +- `@B` - Fetch from memory address in B register +- `!B` - Store to memory address in B register +- `@P` - Fetch from memory address in P register +- `!P` - Store to memory address in P register + +### Debug & Control +- `.` - NO-OP (does nothing) +- `BYE` - Exit program +- `SHOW` - Display current machine state (stack, registers, memory) + +## Memory Model + +- Memory is zero-based +- Each cell can hold a numeric value +- Memory is accessed either directly (using @ and !) or through registers +- P register is typically used for sequential memory operations +- B register is typically used as a memory pointer + +## Example Programs + +### Store and retrieve a value +``` +5 DUP 0 ! # Store 5 at address 0 +3 DUP 1 ! # Store 3 at address 1 +0 @ 1 @ + # Load both values and add them +2 ! # Store result at address 2 +``` + +### Using registers +``` +42 A! # Store 42 in A register +A # Push A's value onto stack +100 B! # Set B to address 100 +42 !B # Store 42 at address 100 +@B # Read from address 100 +``` + +## Usage + +```bash +# Run a program directly +echo "5 3 + SHOW" | awk -f vm.awk + +# Compile and run a program +./compiler.py program.coffee | awk -f vm.awk + +# Run test suite +./vm_tests.sh +``` \ No newline at end of file diff --git a/awk/vm/compiler.py b/awk/vm/compiler.py new file mode 100755 index 0000000..a406779 --- /dev/null +++ b/awk/vm/compiler.py @@ -0,0 +1,172 @@ +#!/usr/bin/env python3 + +""" +A simple compiler that translates CoffeeScript-like syntax to VM instructions. +Example input: + + # Simple arithmetic + x = 5 + y = 3 + z = x + y + + # Using memory + array = [] + array[0] = 42 + array[1] = array[0] * 2 + +Will compile to VM instructions like: + + 5 A! # store 5 in A register + 3 B! # store 3 in B register + A @B + # add them +""" + +import sys +import re + +class Compiler: + def __init__(self): + self.variables = {} # Maps variable names to memory locations + self.next_memory = 0 # Next available memory location + + def allocate_variable(self, name): + """Allocate memory location for a variable""" + if name not in self.variables: + self.variables[name] = self.next_memory + self.next_memory += 1 + return self.variables[name] + + def compile_assignment(self, line): + """Compile assignment statements like 'x = 5' or 'x = y + z'""" + # Remove any comments from the line + line = line.split('#')[0].strip() + + match = re.match(r'(\w+)\s*=\s*(.+)', line) + if not match: + return None + + var_name = match.group(1) + expression = match.group(2) + + print(f"# Compiling assignment: {var_name} = {expression}", file=sys.stderr) + + # First get the memory location + mem_loc = self.allocate_variable(var_name) + + # Then compile the expression + expr_code = self.compile_expression(expression) + if not expr_code: + print(f"# Error: Failed to compile expression: {expression}", file=sys.stderr) + return None + + # Generate code that: + # 1. Evaluates the expression + # 2. Duplicates the result (for storing and leaving on stack) + # 3. Stores at memory location + vm_code = [] + vm_code.extend(expr_code) # Evaluate expression + vm_code.append("DUP") # Make a copy + vm_code.append(str(mem_loc)) # Push memory location + vm_code.append("@") # Read current value (for debugging) + vm_code.append("DROP") # Drop the old value + vm_code.append("!") # Store new value + + return vm_code + + def compile_expression(self, expr): + """Compile expressions like '5', 'x + y', etc.""" + vm_code = [] + + # Remove any comments from the expression + expr = expr.split('#')[0].strip() + + # Handle simple number + if expr.isdigit(): + vm_code.append(expr) + return vm_code + + # Handle variable reference + if expr in self.variables: + vm_code.append(str(self.variables[expr])) + vm_code.append("@") + return vm_code + + # Handle binary operations + ops = { + '+': '+', + '*': '*', + '-': 'NOT +', + } + + # Try each operator + for op in ops: + if op in expr: + parts = expr.split(op, 1) + if len(parts) == 2: + left = parts[0].strip() + right = parts[1].strip() + + print(f"# Debug: left={left}, right={right}", file=sys.stderr) + + # Generate code for left operand + left_code = self.compile_expression(left) + if not left_code: + continue + vm_code.extend(left_code) + + # Generate code for right operand + right_code = self.compile_expression(right) + if not right_code: + continue + vm_code.extend(right_code) + + # Add the operation + vm_code.append(ops[op]) + return vm_code + + return vm_code + + def compile(self, source): + """Compile source code to VM instructions""" + output = [] + debug_output = [] + + for line in source.split('\n'): + line = line.strip() + if not line or line.startswith('#'): + continue + + if line == "SHOW": + output.append("SHOW") + continue + + if '=' in line: + vm_code = self.compile_assignment(line) + if vm_code: + output.extend(vm_code) + debug_output.append(f"{' '.join(vm_code)} # {line}") + if not line.startswith('result ='): # If not final result + output.append("DROP") # Drop the duplicate we left on stack + continue + + print("# Generated VM code:", file=sys.stderr) + for line in debug_output: + print(f"# {line}", file=sys.stderr) + + # Add final SHOW to see the result + output.append("SHOW") + return ' '.join(output) + +def main(): + if len(sys.argv) > 1: + with open(sys.argv[1]) as f: + source = f.read() + else: + source = sys.stdin.read() + + compiler = Compiler() + vm_code = compiler.compile(source) + print(vm_code) + +if __name__ == '__main__': + main() \ No newline at end of file diff --git a/awk/vm/debug.coffee b/awk/vm/debug.coffee new file mode 100644 index 0000000..0663cec --- /dev/null +++ b/awk/vm/debug.coffee @@ -0,0 +1,6 @@ +x = 5 +SHOW +y = 3 +SHOW +z = x + y +SHOW \ No newline at end of file diff --git a/awk/vm/simple.coffee b/awk/vm/simple.coffee new file mode 100644 index 0000000..0a596a7 --- /dev/null +++ b/awk/vm/simple.coffee @@ -0,0 +1,4 @@ +x = 5 +y = 3 +z = x + y +result = z * 2 \ No newline at end of file diff --git a/awk/vm/simple_test.coffee b/awk/vm/simple_test.coffee new file mode 100644 index 0000000..8fec5ba --- /dev/null +++ b/awk/vm/simple_test.coffee @@ -0,0 +1,8 @@ +x = 5 +SHOW +y = 3 +SHOW +z = x + y # Should be 8 +SHOW +result = z * 2 # Should be 16 +SHOW \ No newline at end of file diff --git a/awk/vm/stack_test.coffee b/awk/vm/stack_test.coffee new file mode 100644 index 0000000..ab29e63 --- /dev/null +++ b/awk/vm/stack_test.coffee @@ -0,0 +1,15 @@ +# First store 5 in memory location 0 +x = 5 +SHOW + +# Then store 3 in memory location 1 +y = 3 +SHOW + +# Add them: load 5, load 3, add them +z = x + y +SHOW + +# Double z: load 8, multiply by 2 +result = z * 2 +SHOW \ No newline at end of file diff --git a/awk/vm/test.coffee b/awk/vm/test.coffee new file mode 100644 index 0000000..aecda14 --- /dev/null +++ b/awk/vm/test.coffee @@ -0,0 +1,7 @@ +# Calculate sum +x = 5 +y = 3 +z = x + y + +# Double it +result = z * 2 diff --git a/awk/vm/test_steps.coffee b/awk/vm/test_steps.coffee new file mode 100644 index 0000000..f1d0415 --- /dev/null +++ b/awk/vm/test_steps.coffee @@ -0,0 +1,15 @@ +# Step 1: Initialize x +x = 5 +SHOW + +# Step 2: Initialize y +y = 3 +SHOW + +# Step 3: Add x and y +z = x + y +SHOW + +# Step 4: Double z +result = z * 2 +SHOW \ No newline at end of file diff --git a/awk/vm/vm.awk b/awk/vm/vm.awk new file mode 100755 index 0000000..67da3e7 --- /dev/null +++ b/awk/vm/vm.awk @@ -0,0 +1,254 @@ +#!/usr/bin/awk -f + + +# Stack: DROP, DUP, OVER, PUSH, POP +# Math: + AND XOR NOT 2* 2/ multiply-step +# Call: JUMP CALL RETURN IF -IF +# Loop: NEXT UNEXT +# Register: A A! B! +# Memory: @ ! @+ !+ @B !B @P !P +# NO-OP: . + + +BEGIN { + # Initialize VM state + stack_pointer = 0 # Points to next free position + pc = 0 # Program counter + MAX_STACK = 100 # Maximum stack size + MAX_MEM = 1000 # Memory size + + # Initialize registers + A = 0 # A register + B = 0 # B register + P = 0 # P register (auxiliary pointer) + + # Stack operations + split("", stack) # Initialize stack array + split("", memory) # Initialize memory array +} + +# Stack operations +function push(value) { + if (stack_pointer >= MAX_STACK) { + print "Stack overflow!" > "/dev/stderr" + exit 1 + } + printf "# DEBUG: Pushing %d onto stack\n", value > "/dev/stderr" + stack[stack_pointer++] = value +} + +function pop() { + if (stack_pointer <= 0) { + print "Stack underflow!" > "/dev/stderr" + exit 1 + } + value = stack[--stack_pointer] + printf "# DEBUG: Popping %d from stack\n", value > "/dev/stderr" + return value +} + +# Basic stack manipulation +function op_drop() { + pop() +} + +function op_dup() { + if (stack_pointer <= 0) { + print "Stack underflow on DUP!" > "/dev/stderr" + exit 1 + } + push(stack[stack_pointer - 1]) +} + +function op_over() { + if (stack_pointer <= 1) { + print "Stack underflow on OVER!" > "/dev/stderr" + exit 1 + } + push(stack[stack_pointer - 2]) +} + +# Basic arithmetic operations +function op_add() { + b = pop() + a = pop() + result = a + b + printf "# DEBUG: Adding %d + %d = %d\n", a, b, result > "/dev/stderr" + push(result) +} + +function op_and() { + b = pop() + a = pop() + # For now, we'll just multiply as a placeholder + # In a real implementation, we'd need to implement proper bitwise AND + push(a * b) +} + +function op_xor() { + b = pop() + a = pop() + # For now, we'll just add as a placeholder + # In a real implementation, we'd need to implement proper bitwise XOR + push(a + b) +} + +function op_not() { + a = pop() + # For now, we'll just negate as a placeholder + # In a real implementation, we'd need to implement proper bitwise NOT + push(-a - 1) +} + +function op_2times() { + a = pop() + push(a * 2) +} + +function op_2div() { + a = pop() + push(int(a / 2)) +} + +function op_multiply() { + b = pop() + a = pop() + result = a * b + printf "# DEBUG: Multiplying %d * %d = %d\n", a, b, result > "/dev/stderr" + push(result) +} + +# Register operations +function op_a() { + push(A) +} + +function op_astore() { + A = pop() +} + +function op_bstore() { + B = pop() +} + +# Memory operations +function op_fetch() { + addr = pop() + value = memory[addr] + printf "# DEBUG: Fetching %d from memory[%d]\n", value, addr > "/dev/stderr" + push(value) +} + +function op_store() { + addr = pop() # First pop the address + value = pop() # Then pop the value + printf "# DEBUG: Storing %d at memory[%d]\n", value, addr > "/dev/stderr" + memory[addr] = value +} + +function op_fetchplus() { + push(memory[P++]) +} + +function op_storeplus() { + memory[P++] = pop() +} + +function op_fetchb() { + push(memory[B]) +} + +function op_storeb() { + memory[B] = pop() +} + +function op_fetchp() { + push(memory[P]) +} + +function op_storep() { + memory[P] = pop() +} + +function print_stack() { + printf "Stack: " + for (i = 0; i < stack_pointer; i++) { + printf "%d ", stack[i] + } + printf "\n" +} + +function print_state() { + print_stack() + printf "Registers: A=%d B=%d P=%d\n", A, B, P + printf "Memory[P]=%d Memory[B]=%d\n", memory[P], memory[B] + printf "Memory: " + for (i = 0; i < 4; i++) { # Show first 4 memory locations + printf "[%d]=%d ", i, memory[i] + } + printf "\n-------------------\n" +} + +function op_swap() { + if (stack_pointer < 2) { + print "Stack underflow on SWAP!" > "/dev/stderr" + exit 1 + } + # Swap the top two elements on the stack + temp = stack[stack_pointer - 1] + stack[stack_pointer - 1] = stack[stack_pointer - 2] + stack[stack_pointer - 2] = temp + printf "# DEBUG: Swapping top two stack elements\n" > "/dev/stderr" +} + +function execute_instruction(inst) { + if (inst ~ /^[0-9]+$/) { + # Numbers are pushed onto the stack + push(int(inst)) + return + } + + if (inst == "BYE") { exit 0 } # not really in the minimal spec as set out by Chuck Moore, but useful for a graceful exit. + if (inst == "DROP") { op_drop(); return } + if (inst == "DUP") { op_dup(); return } + if (inst == "OVER") { op_over(); return } # copy second item to top of stack + if (inst == "SWAP") { op_swap(); return } # swap top two stack items + if (inst == "+") { op_add(); return } + if (inst == "AND") { op_and(); return } + if (inst == "XOR") { op_xor(); return } + if (inst == "NOT") { op_not(); return } + if (inst == "2*") { op_2times(); return } # multiply-step + if (inst == "2/") { op_2div(); return } # divide-step + if (inst == "*") { op_multiply(); return } + if (inst == "A") { op_a(); return } # push A register + if (inst == "A!") { op_astore(); return } # store A register + if (inst == "B!") { op_bstore(); return } # store B register + if (inst == "@") { op_fetch(); return } # fetch from memory + if (inst == "!") { op_store(); return } # store to memory + if (inst == "@+") { op_fetchplus(); return } # fetch from memory at P+ + if (inst == "!+") { op_storeplus(); return } # store to memory at P+ + if (inst == "@B") { op_fetchb(); return } # fetch from memory at B + if (inst == "!B") { op_storeb(); return } # store to memory at B + if (inst == "@P") { op_fetchp(); return } # fetch from memory at P + if (inst == "!P") { op_storep(); return } # store to memory at P + if (inst == ".") { return } # NO-OP + if (inst == "SHOW") { print_state(); return } # show state info + + print "Unknown instruction: " inst > "/dev/stderr" + exit 1 +} + +# Main execution loop +{ + # Remove comments (everything after #) + sub(/#.*$/, "") + + # Skip empty lines after comment removal + if (NF == 0) next + + # Split the input line into words + n = split($0, words) + for (i = 1; i <= n; i++) { + execute_instruction(words[i]) + } +} diff --git a/awk/vm/vm_tests.sh b/awk/vm/vm_tests.sh new file mode 100755 index 0000000..6244c51 --- /dev/null +++ b/awk/vm/vm_tests.sh @@ -0,0 +1,42 @@ +#!/bin/bash + +echo "Running VM tests..." +echo + +echo "Test 1: Basic register A operations" +echo "42 A! A A # Store 42 in A, then read A twice" | awk -f vm.awk +echo + +echo "Test 2: Register A and B with memory operations" +echo "100 A! 200 B! 42 @B # Store 100 in A, 200 in B, read from B's address" | awk -f vm.awk +echo + +echo "Test 3: Sequential memory operations using P register" +echo "0 !P 1 !+ 2 !+ 3 !+ 4 !+ 5 !+ # Store 1-5 sequentially using P" | awk -f vm.awk +echo "0 !P @+ @+ @+ @+ @+ # Read back values using P" | awk -f vm.awk +echo + +echo "Test 4: Complex register manipulation" +echo "42 A! A DUP B! @B # Store 42 in A, copy to B, read via B" | awk -f vm.awk +echo + +echo "Test 5: Register arithmetic" +echo "5 A! 3 B! A @B + # Store 5 in A, 3 in B, add A + mem[B]" | awk -f vm.awk +echo + +echo "Test 6: Memory pointer operations" +echo "42 0 ! 1 !P @P # Store 42 at addr 0, point P to 1, read P" | awk -f vm.awk +echo + +echo "Test 7: Register and memory interaction" +echo "10 A! 20 B! A @B ! # Store A's value at B's address" | awk -f vm.awk +echo "@B # Read from memory at B's address" | awk -f vm.awk +echo + +echo "Test 8: Demonstrating B! vs !B" +echo "100 B! # Set B register to 100" | awk -f vm.awk +echo "42 !B # Store 42 at memory location 100" | awk -f vm.awk +echo "@B # Read from memory location 100" | awk -f vm.awk +echo + +echo "Tests completed." \ No newline at end of file |