diff options
-rw-r--r-- | awk/scheme/scheme/docs/awk-scheme-prompt.md | 189 | ||||
-rw-r--r-- | awk/scheme/scheme/docs/awk-vm-implementation-prompt.md | 226 | ||||
-rw-r--r-- | awk/scheme/scheme/docs/scheme-compilation-examples.md | 222 | ||||
-rw-r--r-- | awk/scheme/scheme/docs/scheme-compiler-impl.md | 307 | ||||
-rw-r--r-- | awk/scheme/scheme/docs/scheme-vm-prompt.md | 112 | ||||
-rw-r--r-- | awk/scheme/scheme/docs/scheme-vm-spec.md | 130 | ||||
-rw-r--r-- | awk/scheme/scheme/docs/test-program.md | 48 |
7 files changed, 0 insertions, 1234 deletions
diff --git a/awk/scheme/scheme/docs/awk-scheme-prompt.md b/awk/scheme/scheme/docs/awk-scheme-prompt.md deleted file mode 100644 index f7e0414..0000000 --- a/awk/scheme/scheme/docs/awk-scheme-prompt.md +++ /dev/null @@ -1,189 +0,0 @@ -# Implementation Request for AWK-based Scheme Virtual Machine - -I need help implementing a stack-based virtual machine for a minimal Scheme implementation in AWK. The implementation should work with standard AWK (gawk features optional). - -## Core Data Structures - -### Value Representation -Values in AWK will be represented as strings with type tags. Each value should be a string with format "TYPE:VALUE" where: -- Numbers: "N:123.45" -- Booleans: "B:1" or "B:0" -- Symbols: "S:symbol-name" -- Pairs: "P:car_idx,cdr_idx" (indices into heap array) -- Functions: "F:addr,env_idx" (instruction address and environment index) -- Nil: "NIL:" - -### Memory Model -Using AWK's associative arrays: -```awk -# Stack - numeric indexed array -stack[stack_ptr] - -# Heap - numeric indexed array for allocated objects -heap[heap_ptr] - -# Environments - numeric indexed array of frames -env[env_ptr] - -# Each environment frame is stored as concatenated strings: -# "name1:val1,name2:val2,..." -``` - -### Instruction Format -Instructions stored in array with format: -```awk -instr[addr] = "OPCODE OPERAND1 OPERAND2..." -``` - -## Core Components Needed - -1. Value Handling -```awk -# Type checking -function isNumber(val) { return substr(val, 1, 2) == "N:" } -function isSymbol(val) { return substr(val, 1, 2) == "S:" } -# etc. - -# Value extraction -function getValue(val) { return substr(val, 3) } -``` - -2. Memory Management -- Simple reference counting using an additional array -- Object allocation through heap_ptr increment -- Basic sweep of unreferenced heap cells - -3. Stack Operations -```awk -# Push and pop -function push(val) { stack[++stack_ptr] = val } -function pop() { return stack[stack_ptr--] } -``` - -4. Environment Management -- Environment represented as chain of frames in env[] array -- Each frame is a string of name:value pairs -- Lookup walks the chain for variable resolution - -## Implementation Steps - -1. Parser/Tokenizer: - - Read instruction format from input file - - Parse into instruction array - - Handle basic syntax for immediate values - -2. Value System: - - Type tag handling - - Value construction - - Type checking - - Value extraction - -3. Core VM: - - Instruction dispatch - - Stack manipulation - - Basic arithmetic - - Flow control - -4. Memory Management: - - Heap allocation - - Reference counting - - Basic garbage collection - -5. Function Handling: - - Call frames - - Return handling - - Tail call optimization - -## Initial Implementation Structure - -```awk -BEGIN { - # Initialize VM state - stack_ptr = 0 - heap_ptr = 0 - env_ptr = 0 - pc = 0 # Program counter -} - -# Main instruction dispatch -function execute(instr) { - split(instr, parts, " ") - op = parts[1] - - if (op == "PUSH_CONST") - push(parts[2]) - else if (op == "ADD") { - b = pop() - a = pop() - push(add(a, b)) - } - # etc. -} - -# Main execution loop -{ - # Load instruction into array - instr[$1] = $0 -} - -END { - # Execute loaded program - while (pc < length(instr)) { - execute(instr[pc++]) - } -} -``` - -## Testing Strategy - -1. Input File Format: -``` -0 PUSH_CONST N:5 -1 PUSH_CONST N:3 -2 ADD -3 HALT -``` - -2. Test Cases: -- Basic arithmetic -- Stack operations -- Function calls -- Error handling -- Memory management - -## AWK-Specific Considerations - -1. String Operations: -- Use split() for parsing -- substr() for type tags -- string concatenation for compound values - -2. Limitations: -- No native types besides numbers and strings -- No recursive function calls in AWK -- Limited stack size -- Memory management needs care - -3. Advantages: -- Associative arrays simplify environment handling -- Built-in string operations help with parsing -- Line-oriented processing suits instruction loading - -## Style Guidelines - -1. Use clear function names: - - makeNumber(n) - - makeSymbol(s) - - etc. - -2. Consistent error handling: - - Set ERRNO - - Print to STDERR - - Exit codes - -3. Document array usage: - - Purpose of each array - - Format of entries - - Lifetime management - -Please start with implementing the value type system and basic stack operations, showing how to represent and manipulate Scheme values in AWK's string-based environment. diff --git a/awk/scheme/scheme/docs/awk-vm-implementation-prompt.md b/awk/scheme/scheme/docs/awk-vm-implementation-prompt.md deleted file mode 100644 index 6596589..0000000 --- a/awk/scheme/scheme/docs/awk-vm-implementation-prompt.md +++ /dev/null @@ -1,226 +0,0 @@ -# AWK-based Scheme VM Implementation Guide - -I need help implementing a stack-based virtual machine in AWK that will support a minimal Scheme implementation. Please focus on AWK-specific approaches and limitations. - -## VM Architecture Overview - -The VM should be stack-based with these key components: -1. An instruction array storing the program -2. A value stack using numeric-indexed arrays -3. A heap for pairs and closures using associative arrays -4. An environment chain for variable lookup - -## Core Data Types - -Each value should be represented as a string with format "TYPE:VALUE": - -```awk -# Examples -"N:42" # Number -"B:1" # Boolean true -"B:0" # Boolean false -"S:x" # Symbol 'x' -"P:1,2" # Pair (cons cell) with heap indices -"F:100,1" # Function (instruction addr, env index) -"NIL:" # Empty list -``` - -## Instruction Set - -### Stack Operations -``` -PUSH_CONST val # Push constant onto stack - # Example: "PUSH_CONST N:42" - -POP # Remove top value from stack - -DUP # Duplicate top stack value - # Before: [a] - # After: [a a] - -SWAP # Swap top two stack values - # Before: [a b] - # After: [b a] -``` - -### Memory Operations -``` -LOAD_LOCAL idx # Load local variable at index - # Example: "LOAD_LOCAL 0" - -STORE_LOCAL idx # Store into local variable - # Example: "STORE_LOCAL 1" - -MAKE_ENV n # Create new environment frame with n slots - # Example: "MAKE_ENV 2" - -LOAD_FREE idx # Load from closure's environment - # Example: "LOAD_FREE 0" - -STORE_FREE idx # Store into closure's environment - # Example: "STORE_FREE 1" -``` - -### Function Operations -``` -CALL n # Call function with n arguments - # Example: "CALL 2" - -TAIL_CALL n # Tail-call with n arguments - # Example: "TAIL_CALL 1" - -RETURN # Return from function - -MAKE_FUNCTION addr # Create function object - # Example: "MAKE_FUNCTION 100" -``` - -### List Operations -``` -CONS # Create pair from two stack values - # Before: [a b] - # After: [(a . b)] - -CAR # Get first element of pair - # Before: [(a . b)] - # After: [a] - -CDR # Get second element of pair - # Before: [(a . b)] - # After: [b] -``` - -### Arithmetic Operations -``` -ADD # Add top two numbers - # Before: [N:3 N:4] - # After: [N:7] - -SUB # Subtract -MUL # Multiply -DIV # Divide -``` - -### Comparison Operations -``` -EQ # Generic equality test -NUM_LT # Numeric less than -NUM_GT # Numeric greater than -``` - -### Control Flow -``` -JUMP offset # Unconditional jump - # Example: "JUMP 100" - -JUMP_IF_FALSE offset # Jump if top of stack is false - # Example: "JUMP_IF_FALSE 200" -``` - -## Implementation Requirements - -1. Instruction Format: -```awk -# Each instruction stored as string in instr[] array -instr[addr] = "OPCODE [operand1] [operand2]..." -``` - -2. Value Handling: -```awk -# Type checking functions -function isNumber(val) { return substr(val, 1, 2) == "N:" } -function isPair(val) { return substr(val, 1, 2) == "P:" } -# etc. - -# Value constructors -function makeNumber(n) { return "N:" n } -function makePair(car_idx, cdr_idx) { return "P:" car_idx "," cdr_idx } -# etc. -``` - -3. Stack Operations: -```awk -# Basic stack manipulation -function push(val) { stack[++stack_ptr] = val } -function pop() { if (stack_ptr < 1) error("stack underflow"); return stack[stack_ptr--] } -``` - -4. Memory Management: -```awk -# Heap allocation -function allocate(val) { - heap[++heap_ptr] = val - refs[heap_ptr] = 1 - return heap_ptr -} - -# Reference counting -function incref(idx) { if (idx > 0) refs[idx]++ } -function decref(idx) { if (idx > 0 && --refs[idx] == 0) free_cell(idx) } -``` - -## Starting Implementation - -Please help implement this VM following these steps: - -1. Core VM loop: -```awk -BEGIN { - # Initialize VM state - stack_ptr = 0 - heap_ptr = 0 - pc = 0 -} - -# Load program -{ - instr[NR-1] = $0 -} - -END { - # Main execution loop - while (pc < length(instr)) { - execute(instr[pc++]) - } -} -``` - -2. Instruction execution: -```awk -function execute(instr) { - split(instr, parts, " ") - op = parts[1] - - if (op == "PUSH_CONST") - push(parts[2]) - else if (op == "ADD") { - b = pop() - a = pop() - push(add(a, b)) - } - # etc. -} -``` - -Please start by implementing: -1. The basic VM loop -2. Stack operations -3. Arithmetic operations -4. Simple control flow - -Then we can move on to: -1. Function calls and returns -2. Environment handling -3. Cons cells and list operations -4. Garbage collection - -Focus on AWK's strengths: -- Associative arrays for memory management -- String operations for value handling -- Line-oriented processing for instruction loading - -And handle AWK's limitations: -- No native complex types -- Limited recursion -- String-based value representation -- Memory management constraints diff --git a/awk/scheme/scheme/docs/scheme-compilation-examples.md b/awk/scheme/scheme/docs/scheme-compilation-examples.md deleted file mode 100644 index 43bae3a..0000000 --- a/awk/scheme/scheme/docs/scheme-compilation-examples.md +++ /dev/null @@ -1,222 +0,0 @@ -# Scheme to VM Instruction Examples - -## Basic Arithmetic - -### Simple Addition -```scheme -(+ 1 2) -``` -```awk -# VM Instructions -0 PUSH_CONST N:1 -1 PUSH_CONST N:2 -2 ADD -``` - -### Nested Arithmetic -```scheme -(+ (* 3 4) (- 10 5)) -``` -```awk -# VM Instructions -0 PUSH_CONST N:3 -1 PUSH_CONST N:4 -2 MUL # Stack now has 12 -3 PUSH_CONST N:10 -4 PUSH_CONST N:5 -5 SUB # Stack now has 5 -6 ADD # Final result 17 -``` - -## Variable Binding and Use - -### Let Expression -```scheme -(let ((x 5)) - (+ x 1)) -``` -```awk -# VM Instructions -0 MAKE_ENV 1 # Create environment with 1 slot -1 PUSH_CONST N:5 # Push initial value -2 STORE_LOCAL 0 # Store into x's slot -3 LOAD_LOCAL 0 # Load x -4 PUSH_CONST N:1 -5 ADD -``` - -### Nested Let -```scheme -(let ((x 5)) - (let ((y (+ x 1))) - (* x y))) -``` -```awk -# VM Instructions -0 MAKE_ENV 1 # Environment for x -1 PUSH_CONST N:5 -2 STORE_LOCAL 0 # Store x -3 MAKE_ENV 1 # Environment for y -4 LOAD_LOCAL 0 # Load x -5 PUSH_CONST N:1 -6 ADD -7 STORE_LOCAL 0 # Store y -8 LOAD_LOCAL 1 # Load x (from outer env) -9 LOAD_LOCAL 0 # Load y -10 MUL -``` - -## Function Definition and Call - -### Simple Function -```scheme -(define (add1 x) - (+ x 1)) -``` -```awk -# VM Instructions -0 MAKE_FUNCTION 2 # Create function pointing to instruction 2 -1 STORE_GLOBAL 0 # Store in global env slot for add1 -2 MAKE_ENV 1 # Function body starts here -3 LOAD_LOCAL 0 # Load parameter x -4 PUSH_CONST N:1 -5 ADD -6 RETURN -``` - -### Function Call -```scheme -(add1 5) -``` -```awk -# VM Instructions -0 PUSH_CONST N:5 # Push argument -1 LOAD_GLOBAL 0 # Load add1 function -2 CALL 1 # Call with 1 argument -``` - -## List Operations - -### List Construction -```scheme -(cons 1 (cons 2 '())) -``` -```awk -# VM Instructions -0 PUSH_CONST N:1 -1 PUSH_CONST N:2 -2 PUSH_CONST NIL: -3 CONS # Creates (2 . nil) -4 CONS # Creates (1 . (2 . nil)) -``` - -### List Operations -```scheme -(car (cons 1 2)) -``` -```awk -# VM Instructions -0 PUSH_CONST N:1 -1 PUSH_CONST N:2 -2 CONS -3 CAR -``` - -## Conditionals - -### If Expression -```scheme -(if (< x 0) - (- 0 x) - x) -``` -```awk -# VM Instructions -0 LOAD_LOCAL 0 # Load x -1 PUSH_CONST N:0 -2 NUM_LT # Compare x < 0 -3 JUMP_IF_FALSE 7 # Skip to else branch if false -4 PUSH_CONST N:0 -5 LOAD_LOCAL 0 # Load x again -6 SUB # Compute 0 - x -7 JUMP 9 # Skip else branch -8 LOAD_LOCAL 0 # Else branch: just load x -9 NOP # Continue here -``` - -## Closures - -### Create Closure -```scheme -(let ((x 1)) - (lambda (y) (+ x y))) -``` -```awk -# VM Instructions -0 MAKE_ENV 1 # Environment for x -1 PUSH_CONST N:1 -2 STORE_LOCAL 0 # Store x -3 MAKE_FUNCTION 5 # Create function -4 MAKE_CLOSURE 1 # Capture current env -5 MAKE_ENV 1 # Function body starts here -6 LOAD_FREE 0 # Load captured x -7 LOAD_LOCAL 0 # Load parameter y -8 ADD -9 RETURN -``` - -## Recursive Function - -### Factorial -```scheme -(define (factorial n) - (if (= n 0) - 1 - (* n (factorial (- n 1))))) -``` -```awk -# VM Instructions -0 MAKE_FUNCTION 2 # Create factorial function -1 STORE_GLOBAL 0 # Store in global env -2 MAKE_ENV 1 # Function body starts -3 LOAD_LOCAL 0 # Load n -4 PUSH_CONST N:0 -5 NUM_EQ # Compare n = 0 -6 JUMP_IF_FALSE 9 # Skip to else branch -7 PUSH_CONST N:1 # Return 1 for base case -8 RETURN -9 LOAD_LOCAL 0 # Load n -10 LOAD_LOCAL 0 # Load n again -11 PUSH_CONST N:1 -12 SUB # Compute n - 1 -13 LOAD_GLOBAL 0 # Load factorial function -14 TAIL_CALL 1 # Tail call factorial(n-1) -15 MUL # Multiply n * factorial(n-1) -16 RETURN -``` - -## Implementation Notes - -1. Environment Chain -- Each MAKE_ENV creates a new frame -- LOAD_LOCAL counts down the chain for outer references -- STORE_LOCAL works similarly - -2. Closure Creation -- MAKE_CLOSURE captures current environment -- LOAD_FREE accesses captured variables - -3. Tail Calls -- TAIL_CALL reuses current stack frame -- Essential for recursive functions - -4. Memory Management -- CONS allocates in heap -- Reference counting needed for heap objects -- Environment frames need reference counting too - -These examples show typical compilation patterns. The actual compiler would need to: -1. Track variable locations -2. Manage label generation -3. Detect tail call positions -4. Handle lexical scoping properly diff --git a/awk/scheme/scheme/docs/scheme-compiler-impl.md b/awk/scheme/scheme/docs/scheme-compiler-impl.md deleted file mode 100644 index db8a204..0000000 --- a/awk/scheme/scheme/docs/scheme-compiler-impl.md +++ /dev/null @@ -1,307 +0,0 @@ -# Scheme Compiler Implementation in AWK - -## Basic Compiler Structure - -We'll implement the compiler as a recursive descent processor that converts Scheme expressions into VM instructions. Here's the core structure: - -```awk -# Global state -BEGIN { - next_label = 0 # For generating unique labels - next_address = 0 # Current instruction address - depth = 0 # Current environment depth -} - -# Main compile function -function compile(expr, parts, len) { - if (isAtom(expr)) - return compileAtom(expr) - - split(expr, parts, " ") - len = length(parts) - - # Strip parentheses - parts[1] = substr(parts[1], 2) # Remove leading ( - parts[len] = substr(parts[len], 1, length(parts[len])-1) # Remove trailing ) - - # Dispatch based on first element - if (parts[1] == "+") - return compileAdd(parts, len) - else if (parts[1] == "let") - return compileLet(parts, len) - else if (parts[1] == "lambda") - return compileLambda(parts, len) - else if (parts[1] == "if") - return compileIf(parts, len) - else - return compileCall(parts, len) -} - -# Utility functions -function isAtom(expr) { - return substr(expr, 1, 1) != "(" -} - -function newLabel() { - return "L" next_label++ -} - -function emit(instr) { - program[next_address++] = instr -} -``` - -## Compilation Patterns - -### 1. Basic Arithmetic - -```awk -function compileAdd(parts, len, i) { - # Compile each argument - for (i = 2; i <= len; i++) - compile(parts[i]) - - # Emit adds between each value - for (i = 3; i <= len; i++) - emit("ADD") - - return next_address - 1 -} - -# Example usage: -# Input: (+ 1 2 3) -# Output: -# PUSH_CONST N:1 -# PUSH_CONST N:2 -# ADD -# PUSH_CONST N:3 -# ADD -``` - -### 2. Let Expressions - -```awk -function compileLet(parts, len, bindings, body, i, num_bindings) { - # Parse let structure - bindings = parts[2] - body = parts[3] - - # Count bindings - split(bindings, binding_parts, " ") - num_bindings = (length(binding_parts) - 2) / 2 # Account for parentheses - - # Create new environment frame - emit("MAKE_ENV " num_bindings) - - # Compile each binding value and store - for (i = 1; i <= num_bindings; i++) { - compile(binding_parts[i * 2]) - emit("STORE_LOCAL " (i - 1)) - } - - # Compile body in new environment - depth++ - compile(body) - depth-- - - return next_address - 1 -} - -# Example usage: -# Input: (let ((x 5)) (+ x 1)) -# Output: -# MAKE_ENV 1 -# PUSH_CONST N:5 -# STORE_LOCAL 0 -# LOAD_LOCAL 0 -# PUSH_CONST N:1 -# ADD -``` - -### 3. Lambda Expressions - -```awk -function compileLambda(parts, len, param_list, body, label_start, label_end) { - label_start = newLabel() - label_end = newLabel() - - # Emit jump around function body - emit("JUMP " label_end) - - # Mark function start - emit(label_start ":") - - # Parse parameters - param_list = parts[2] - body = parts[3] - - # Compile function body - depth++ - compile(body) - emit("RETURN") - depth-- - - # Mark function end - emit(label_end ":") - - # Create function object - emit("MAKE_FUNCTION " label_start) - - return next_address - 1 -} - -# Example usage: -# Input: (lambda (x) (+ x 1)) -# Output: -# JUMP L1 -# L0: -# LOAD_LOCAL 0 -# PUSH_CONST N:1 -# ADD -# RETURN -# L1: -# MAKE_FUNCTION L0 -``` - -### 4. If Expressions - -```awk -function compileIf(parts, len, condition, true_branch, false_branch, label_else, label_end) { - label_else = newLabel() - label_end = newLabel() - - # Compile condition - compile(parts[2]) - - # Jump to else if false - emit("JUMP_IF_FALSE " label_else) - - # Compile true branch - compile(parts[3]) - emit("JUMP " label_end) - - # Compile false branch - emit(label_else ":") - if (len > 4) # If there is an else branch - compile(parts[4]) - - emit(label_end ":") - - return next_address - 1 -} - -# Example usage: -# Input: (if (< x 0) (- 0 x) x) -# Output: -# LOAD_LOCAL 0 -# PUSH_CONST N:0 -# NUM_LT -# JUMP_IF_FALSE L0 -# PUSH_CONST N:0 -# LOAD_LOCAL 0 -# SUB -# JUMP L1 -# L0: -# LOAD_LOCAL 0 -# L1: -``` - -### 5. Function Calls - -```awk -function compileCall(parts, len, i, num_args) { - num_args = len - 1 - - # Compile each argument - for (i = 2; i <= len; i++) - compile(parts[i]) - - # Compile function reference - compile(parts[1]) - - # Emit call instruction - emit("CALL " num_args) - - return next_address - 1 -} - -# Example usage: -# Input: (add1 5) -# Output: -# PUSH_CONST N:5 -# LOAD_GLOBAL 0 -# CALL 1 -``` - -## Symbol Table Management - -```awk -# Track variables and their locations -function enterScope() { - scope_depth++ - next_local = 0 -} - -function leaveScope() { - scope_depth-- -} - -function addLocal(name) { - symbols[scope_depth "," name] = next_local++ -} - -function findVariable(name, i) { - for (i = scope_depth; i >= 0; i--) - if ((i "," name) in symbols) - return "LOCAL " i "," symbols[i "," name] - return "GLOBAL " name -} -``` - -## Example Usage - -Here's how to use the compiler: - -```awk -BEGIN { - # Initialize compiler - next_label = 0 - next_address = 0 - depth = 0 - - # Compile some example code - expr = "(let ((x 5)) (+ x 1))" - compile(expr) - - # Print generated code - for (i = 0; i < next_address; i++) - print i ": " program[i] -} -``` - -## Implementation Notes - -1. Variable Resolution - - Track scope depth for proper variable lookup - - Generate appropriate LOAD/STORE instructions - - Handle closure captures - -2. Label Generation - - Use unique labels for control flow - - Track label addresses for jumps - -3. Environment Management - - Track environment depth - - Generate correct frame sizes - - Handle nested scopes - -4. Error Handling - - Check for syntax errors - - Validate number of arguments - - Report meaningful errors - -5. Optimization Opportunities - - Tail call detection - - Constant folding - - Peephole optimization - - Dead code elimination diff --git a/awk/scheme/scheme/docs/scheme-vm-prompt.md b/awk/scheme/scheme/docs/scheme-vm-prompt.md deleted file mode 100644 index 7463494..0000000 --- a/awk/scheme/scheme/docs/scheme-vm-prompt.md +++ /dev/null @@ -1,112 +0,0 @@ -# Implementation Request for Scheme Virtual Machine - -I need help implementing a stack-based virtual machine for a minimal Scheme implementation in JavaScript. The implementation should follow these requirements: - -## Core Data Structures - -### Value Representation -Please help me implement a tagged union type for Scheme values with these cases: -- Numbers (using JavaScript numbers) -- Booleans (using JavaScript booleans) -- Symbols (as strings) -- Pairs (cons cells) -- Functions (closures) -- Nil - -Each value should include a type tag and the actual value data. The implementation should be memory efficient while still being easy to debug. - -### Stack Frame -Design a stack frame structure that includes: -- An array for local variables -- An operand stack (array) -- Return address (number) -- Previous frame pointer -- Captured environment reference (for closures) - -### Instruction Format -Each instruction should be represented as an object with: -- opcode (string or number) -- operands (if any) -- source position (for debugging) - -## Core Components Needed - -1. Value Constructor/Accessors -- Functions to create each type of value -- Type predicates (isNumber, isPair, etc.) -- Safe accessors that check types - -2. Memory Management -- A simple mark-and-sweep garbage collector -- Root set scanning of VM stack and global environment -- Object allocation interface - -3. Environment Management -- Environment chain implementation -- Closure creation and variable capture -- Variable lookup and storage - -4. Instruction Interpreter -- Main instruction dispatch loop -- Stack manipulation helpers -- Error handling with meaningful messages -- Debugging support (stack traces) - -## Initial Implementation Steps - -Please help me implement these components in this order: - -1. Value type system and basic operations -2. Stack frame and basic stack operations -3. Main instruction interpreter loop -4. Simple arithmetic and comparison operations -5. Function calls and returns -6. Closure creation and environment handling -7. Cons cells and list operations -8. Basic garbage collection - -## Starting Point - -Please start by showing me how to implement: - -1. The tagged value type system -2. Basic stack operations (push, pop) -3. A simple instruction interpreter that can handle: - - PUSH_CONST - - POP - - ADD - - RETURN - -The code should be in a functional style, avoiding mutation where practical, and should use modern JavaScript features. Please include basic error checking and type safety. - -## Testing Approach - -For each component, I'd like to see: -1. Basic unit tests -2. Example instruction sequences -3. Error cases to handle -4. Edge cases to consider - -The implementation should prioritize correctness and clarity over performance initially. - -## Additional Considerations - -Please also consider: -1. How to handle tail calls efficiently -2. Debug information tracking -3. Error recovery strategies -4. Performance bottlenecks to watch for -5. Future extensibility - -## Style Preferences - -The implementation should: -- Use functional programming patterns where appropriate -- Minimize state mutation -- Use clear naming conventions -- Include detailed comments explaining non-obvious code -- Use TypeScript-style JSDoc comments for better tooling support -- Target modern browsers without external dependencies -- Use ES modules for code organization - -Please start with the value type system implementation, showing how to create and manipulate Scheme values in a type-safe way. diff --git a/awk/scheme/scheme/docs/scheme-vm-spec.md b/awk/scheme/scheme/docs/scheme-vm-spec.md deleted file mode 100644 index 424602e..0000000 --- a/awk/scheme/scheme/docs/scheme-vm-spec.md +++ /dev/null @@ -1,130 +0,0 @@ -# Scheme Virtual Machine Specification - -## Stack and Memory Model -The VM uses a stack-based architecture with a separate heap for storing longer-lived objects. Each stack frame contains: -- Local variable space -- Operand stack -- Return address - -## Data Types -- Numbers (implemented as JavaScript numbers) -- Booleans -- Symbols (interned strings) -- Pairs (cons cells) -- Functions (closures) -- Nil - -## Instructions - -### Stack Operations -- PUSH_CONST value ; Push constant onto stack -- POP ; Remove top value from stack -- DUP ; Duplicate top stack value -- SWAP ; Swap top two stack values - -### Environment Operations -- LOAD_LOCAL idx ; Load local variable at index -- STORE_LOCAL idx ; Store into local variable -- MAKE_CLOSURE n ; Create closure with n free variables -- LOAD_FREE idx ; Load from closure's environment -- STORE_FREE idx ; Store into closure's environment - -### Function Operations -- CALL n ; Call function with n arguments -- TAIL_CALL n ; Tail-call with n arguments -- RETURN ; Return from function -- MAKE_FUNCTION addr ; Create function object - -### Pair Operations -- CONS ; Create pair from two stack values -- CAR ; Get first element of pair -- CDR ; Get second element of pair -- SET_CAR ; Set first element of pair -- SET_CDR ; Set second element of pair - -### Arithmetic Operations -- ADD ; Add top two numbers -- SUB ; Subtract -- MUL ; Multiply -- DIV ; Divide -- REMAINDER ; Modulo operation - -### Comparison Operations -- EQ ; Generic equality test -- NUM_EQ ; Numeric equality -- NUM_LT ; Less than -- NUM_GT ; Greater than - -### Control Flow -- JUMP offset ; Unconditional jump -- JUMP_IF_FALSE offset ; Conditional jump -- JUMP_IF_TRUE offset ; Conditional jump - -### Type Operations -- TYPE_OF ; Get type of value -- IS_PAIR ; Test if value is pair -- IS_NUMBER ; Test if value is number -- IS_SYMBOL ; Test if value is symbol - -## Example Instruction Sequences - -### Function Definition -```scheme -(define (add1 x) (+ x 1)) -``` -Compiles to: -``` -MAKE_FUNCTION L1 -STORE_LOCAL 0 -JUMP L2 -L1: - LOAD_LOCAL 0 ; Load x - PUSH_CONST 1 - ADD - RETURN -L2: -``` - -### List Creation -```scheme -(cons 1 (cons 2 '())) -``` -Compiles to: -``` -PUSH_CONST 1 -PUSH_CONST 2 -PUSH_CONST nil -CONS -CONS -``` - -### Closure Creation -```scheme -(let ((x 1)) - (lambda (y) (+ x y))) -``` -Compiles to: -``` -PUSH_CONST 1 ; Push initial value of x -MAKE_FUNCTION L1 ; Create function body -MAKE_CLOSURE 1 ; Create closure capturing x -JUMP L2 -L1: - LOAD_FREE 0 ; Load captured x - LOAD_LOCAL 0 ; Load parameter y - ADD - RETURN -L2: -``` - -## Implementation Notes - -1. The VM should implement proper tail-call optimization using the TAIL_CALL instruction. - -2. Garbage collection can be implemented using a simple mark-and-sweep collector, scanning the stack and heap for reachable objects. - -3. For efficiency, common constants (small integers, nil, etc.) can be preallocated and shared. - -4. The environment model uses static scope, with closures capturing their creation environment. - -5. Function calls maintain their own stack frame with local variables and operand stack. diff --git a/awk/scheme/scheme/docs/test-program.md b/awk/scheme/scheme/docs/test-program.md deleted file mode 100644 index ee20e32..0000000 --- a/awk/scheme/scheme/docs/test-program.md +++ /dev/null @@ -1,48 +0,0 @@ -# Test Program - -Save this as `test.scm.asm`: -``` -PUSH_CONST N:5 -PUSH_CONST N:3 -ADD -PUSH_CONST N:2 -SUB -HALT -``` - -Run with: -```bash -awk -f vm.awk test.scm.asm -``` - -Expected output: -``` -Result: N:6 -``` - -# Additional Test Cases - -## List Operations -``` -PUSH_CONST N:1 -PUSH_CONST N:2 -CONS -PUSH_CONST N:3 -CONS -CAR -HALT -``` - -## Error Cases -``` -# Stack underflow -POP -POP -HALT - -# Type error -PUSH_CONST S:hello -PUSH_CONST N:1 -ADD -HALT -``` |