diff options
| author | elioat <elioat@tilde.institute> | 2025-07-20 23:23:17 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2025-07-20 23:23:17 -0400 |
| commit | d242546a4a618a97307e74c066080395d1333e7b (patch) | |
| tree | 96e5bc875ed663b90e810ee48c813a235f7cd9b5 /awk | |
| parent | 375f5ba917d733662ea161c2e17c2416418343b9 (diff) | |
| download | tour-d242546a4a618a97307e74c066080395d1333e7b.tar.gz | |
*
Diffstat (limited to 'awk')
| -rw-r--r-- | awk/scheme/scheme/README.md | 28 | ||||
| -rw-r--r-- | awk/scheme/scheme/scratch/OUTLINE.md | 138 | ||||
| -rw-r--r-- | awk/scheme/scheme/scratch/arch-notes.md | 133 |
3 files changed, 255 insertions, 44 deletions
diff --git a/awk/scheme/scheme/README.md b/awk/scheme/scheme/README.md index 632e421..cf346c7 100644 --- a/awk/scheme/scheme/README.md +++ b/awk/scheme/scheme/README.md @@ -116,6 +116,33 @@ echo "(+ 1 2)" | DEBUG=1 ./scheme # Single expression - Environment changes and variable lookups - Function calls and closure operations +### Command-Line Debugging Hints + +**View bytecode generation**: +```bash +echo "(+ 1 2)" | ./bin/compiler.awk +``` + +**Step-by-step VM execution**: +```bash +echo "(+ 1 2)" | ./bin/compiler.awk | DEBUG=1 ./bin/vm.awk +``` + +**Trace specific functions**: +```bash +grep -n "function_name" bin/vm.awk +``` + +**Check syntax errors**: +```bash +echo "(+ 1" | ./bin/compiler.awk # Should show error +``` + +**Compare outputs**: +```bash +diff <(echo "(+ 1 2)" | ./bin/compiler.awk) <(echo "(+ 2 1)" | ./bin/compiler.awk) +``` + ### Common Issues **"Unknown expression type"**: Usually a parsing issue. Check for unsupported syntax. @@ -130,7 +157,6 @@ echo "(+ 1 2)" | DEBUG=1 ./scheme # Single expression **Not Supported**: - Floating point numbers (integers only) -- Nested lambda definitions - Proper tail recursion - Garbage collection - Macros diff --git a/awk/scheme/scheme/scratch/OUTLINE.md b/awk/scheme/scheme/scratch/OUTLINE.md index 9969866..073afef 100644 --- a/awk/scheme/scheme/scratch/OUTLINE.md +++ b/awk/scheme/scheme/scratch/OUTLINE.md @@ -3,7 +3,7 @@ ## Introduction - Hook: "What do you get when you cross a functional programming language with a text processing tool from the 1970s?" - Brief context: My journey from JS/functional programming to AWK/compilers/VMs -- Thesis: Building a Scheme VM in AWK taught me more about language design than I expected +- Thesis: Building a Scheme VM in AWK taught me more about language design than I expected, and it evolved into a surprisingly capable system ## The Setup: Why AWK? (And Why Not?) - The initial reaction: "AWK? Really?" @@ -17,18 +17,40 @@ - Takes Scheme expressions, outputs VM bytecode - Recursive descent parsing (because AWK doesn't have fancy parser generators) - The joy of implementing `car` and `cdr` in a language that doesn't have lists + - Error detection for incomplete expressions (because debugging is hard enough) - **Layer 2: The Virtual Machine** (`bin/vm.awk`) - Stack-based execution (because registers are hard) - Type system with tagged values (`N:5`, `B:1`, `P:42`) - Environment management for lexical scoping - The weirdness of implementing closures in AWK + - Higher-order functions with nested call support (because functional programming is fun) - **Layer 3: The REPL** (`bin/repl`) - Interactive development (because who doesn't love a good REPL?) - State persistence between sessions - The challenge of making AWK feel interactive +## The Evolution: From Simple Interpreter to Language-Agnostic VM + +### The Early Days: Basic Scheme +- Started with simple arithmetic and basic functions +- The joy of getting `(+ 1 2)` to work +- Why stack-based execution made sense in AWK +- The challenge of implementing lists with cons cells + +### The Middle Phase: Functions and Closures +- Adding user-defined functions (because Scheme needs functions) +- Implementing closures (because lexical scoping is important) +- The complexity of environment management in AWK +- Why capturing environments was harder than expected + +### The Current State: Higher-Order Functions and Multi-Language Support +- Adding `map` and `filter` with full function support +- The nested function call system (because higher-order functions need to call other functions) +- The Forth compiler experiment (because why not?) +- Proving the VM is truly language-agnostic + ## The Weirdness: AWK Quirks That Made Me Question My Life Choices ### 1-Indexed Everything @@ -68,6 +90,7 @@ - The beauty of recursive functions in AWK - How we handle function calls, special forms, literals - The joy of implementing `if` and `cond` without proper control flow +- Error detection for incomplete expressions (because users make mistakes) ### Code Generation: From AST to Bytecode - The instruction set: `PUSH_CONST`, `ADD`, `CALL`, `HALT` @@ -101,19 +124,11 @@ - The challenge of parameter passing - Why `CALL` is more complex than it seems -## The REPL: Making AWK Interactive - -### State Persistence: Between Sessions -- Saving function definitions to files -- Loading state on startup -- The simplicity of text-based persistence -- Why we don't need a database - -### Interactive Development: The AWK Way -- Reading input line by line -- Compiling and executing each expression -- The challenge of maintaining state -- Why the REPL feels surprisingly natural +### Higher-Order Functions: The Real Magic +- How `map` and `filter` work with any function type +- The nested function call system +- Why calling functions from within functions is tricky +- The joy of data transformation pipelines ## The Forth Experiment: Proving Language Agnosticism @@ -134,6 +149,39 @@ - Why this matters for language design - The power of a well-designed instruction set +## The Testing Journey: From Chaos to Order + +### The Early Days: Manual Testing +- Running expressions by hand +- The pain of debugging without proper tests +- Why testing is crucial even for small projects + +### The Evolution: Comprehensive Test Suite +- 48 unit tests covering all features +- Integration tests for complex scenarios +- Regression tests to prevent bugs +- Examples that demonstrate usage + +### The Test Runner: Making Testing Easy +- Automated test execution +- Clear pass/fail reporting +- Error detection and reporting +- Why good tooling matters + +## The REPL: Making AWK Interactive + +### State Persistence: Between Sessions +- Saving function definitions to files +- Loading state on startup +- The simplicity of text-based persistence +- Why we don't need a database + +### Interactive Development: The AWK Way +- Reading input line by line +- Compiling and executing each expression +- The challenge of maintaining state +- Why the REPL feels surprisingly natural + ## Lessons Learned: What AWK Taught Me About Language Design ### Simplicity is Powerful @@ -156,6 +204,16 @@ - Closures add significant complexity - Why proper scoping is crucial for functional languages +### Higher-Order Functions are Worth It +- The power of function composition +- How data transformation becomes elegant +- Why functional programming patterns matter + +### Language Agnosticism is Achievable +- A well-designed VM can support multiple languages +- The benefits of shared runtime and standard library +- Why this approach reduces implementation complexity + ## The Weirdest Parts: AWK Quirks That Made Me Laugh/Cry ### The 1-Indexed String Functions @@ -185,12 +243,15 @@ - The REPL is responsive - State persistence works reliably - The type system prevents many bugs +- Higher-order functions work smoothly +- The test suite catches regressions ### What's Slow/Weird - Complex expressions can be slow - Memory usage with large programs - The 1-indexed string operations - Limited data structures beyond arrays +- No tail call optimization ### The AWK Tax - Everything is string-based under the hood @@ -198,6 +259,30 @@ - Limited control flow constructs - The constant string manipulation overhead +## The Current State: A Surprisingly Capable System + +### What We Have +- Full Scheme interpreter with higher-order functions +- Language-agnostic VM with Forth support +- Comprehensive test suite (48 tests) +- Interactive REPL with state persistence +- Error detection and reporting +- Standard library with 50+ functions + +### What Makes It Special +- Built entirely in AWK (no external dependencies) +- Supports complex functional programming patterns +- Language-agnostic VM design +- Comprehensive testing and documentation +- Clean, maintainable architecture + +### The Numbers +- ~3,900 lines of AWK code +- 48 unit tests + integration/regression tests +- 50+ standard library functions +- 2 target languages (Scheme, Forth) +- 0 external dependencies + ## Conclusion: Was It Worth It? ### The Unexpected Benefits @@ -205,6 +290,7 @@ - Appreciation for language design decisions - The joy of building something from scratch - Why constraints breed creativity +- The power of comprehensive testing ### The AWK Revelation - AWK is more powerful than it looks @@ -223,6 +309,7 @@ - The value of building things in unexpected languages - Why understanding the fundamentals matters - The joy of programming for its own sake +- How constraints can lead to better design ## Technical Appendix: Key Code Snippets @@ -247,6 +334,17 @@ function push(val) { } ``` +### Higher-Order Functions +```awk +function stdlib_map() { + # Get function and list from stack + func = pop() + list = pop() + # Call function for each element + result = execute_nested_function_call(func, element) +} +``` + ### The Forth Compiler ```awk if (token ~ /^-?[0-9]+$/) { @@ -256,9 +354,19 @@ if (token ~ /^-?[0-9]+$/) { } ``` +### Error Detection +```awk +if (paren_count > 0) { + error("Unmatched opening parentheses - incomplete expression") +} +``` + ## Resources and Further Reading - AWK documentation and tutorials - Scheme language specification - Virtual machine design principles - Stack-based execution models -- Language implementation techniques
\ No newline at end of file +- Language implementation techniques +- Functional programming concepts +- Higher-order functions and closures +- Language-agnostic VM design
\ No newline at end of file diff --git a/awk/scheme/scheme/scratch/arch-notes.md b/awk/scheme/scheme/scratch/arch-notes.md index 8644da8..bb2e240 100644 --- a/awk/scheme/scheme/scratch/arch-notes.md +++ b/awk/scheme/scheme/scratch/arch-notes.md @@ -1,7 +1,7 @@ # Awk-Scheme: Architectural Notes ## Overview -A little Scheme interpreter implemented in AWK, composed of a compiler and a stack-based virtual machine. The architecture seeks to be modular, with clear separation of concerns between parsing/compilation and execution. +A little Scheme interpreter implemented in AWK, composed of a compiler and a stack-based virtual machine. The architecture seeks to be modular, with clear separation of concerns between parsing/compilation and execution. The system has evolved to support higher-order functions, nested function calls, and language-agnostic VM design with Forth as a second target language. --- @@ -24,7 +24,7 @@ A little Scheme interpreter implemented in AWK, composed of a compiler and a sta ### 2.2. Parsing (Recursive Descent) - **Pattern**: *Recursive Descent Parser* - **Why**: Simple, direct mapping from grammar to code; easy to debug and extend for a small language. -- **How**: The parser builds an expression tree from tokens, handling nested expressions, string literals, and validating syntax with proper parenthesis matching. +- **How**: The parser builds an expression tree from tokens, handling nested expressions, string literals, and validating syntax with proper parenthesis matching and error detection for incomplete expressions. ### 2.3. Code Generation - **Pattern**: *Visitor/Dispatcher* (for expression types) @@ -41,6 +41,11 @@ A little Scheme interpreter implemented in AWK, composed of a compiler and a sta - **Why**: Enables lexical scoping and first-class functions by capturing the environment at lambda creation. - **How**: The compiler emits `CAPTURE_ENV` instructions to capture the current environment and create closure objects with unique environment IDs. +### 2.6. Error Detection +- **Pattern**: *Fail-Fast Error Detection* +- **Why**: Early detection of syntax errors prevents runtime issues and improves debugging. +- **How**: The compiler validates parenthesis matching and detects incomplete expressions during parsing, providing clear error messages. + --- ## 3. Virtual Machine (`bin/vm.awk`) @@ -75,17 +80,27 @@ A little Scheme interpreter implemented in AWK, composed of a compiler and a sta - **Why**: Enables functions like `string-append` to accept any number of arguments, improving usability. - **How**: Functions like `string_append()` process all arguments on the stack using a loop, maintaining proper argument order and type checking. -### 3.7. Output System +### 3.7. Higher-Order Functions +- **Pattern**: *Function as Data* (first-class functions) +- **Why**: Enables functional programming patterns like `map` and `filter` with user-defined functions, lambdas, and closures. +- **How**: The VM implements `map` and `filter` functions that can accept any function type (built-in, user-defined, lambda, closure) through a nested function call mechanism. + +### 3.8. Nested Function Call System +- **Pattern**: *Context Preservation* (for nested execution) +- **Why**: Enables higher-order functions to call other functions while preserving the calling context. +- **How**: The VM maintains a call stack that saves and restores execution context, allowing functions to be called from within other functions without losing state. + +### 3.9. Output System - **Pattern**: *Visitor Pattern* (for value display) - **Why**: Different value types require different display formats, and the display logic should be extensible. - **How**: The `display_value()` function recursively visits different value types, converting them to readable string representations with proper list formatting. -### 3.8. Heap and Memory Management +### 3.10. Heap and Memory Management - **Pattern**: *Manual Heap with Reference Counting (partial)* - **Why**: Enables cons cell allocation and basic memory management for list operations. - **How**: The VM allocates cons cells on a heap array, with a placeholder for reference counting (not fully implemented). -### 3.9. State Persistence +### 3.11. State Persistence - **Pattern**: *State Serialization* - **Why**: Allows global state and functions to persist across REPL sessions for continuity. - **How**: The VM serializes global variables and function definitions to files, loading them on startup with proper state restoration. @@ -109,45 +124,94 @@ A little Scheme interpreter implemented in AWK, composed of a compiler and a sta - **Why**: String operations like concatenation need to handle variable numbers of arguments efficiently. - **How**: Functions like `string_append()` build the result incrementally by processing all arguments on the stack in order. +### 4.4. Higher-Order Functions +- **Pattern**: *Functional Programming Patterns* +- **Why**: Enables data transformation and filtering with user-defined functions. +- **How**: `map` and `filter` functions accept any function type and execute them in a nested context, supporting complex data processing pipelines. + +--- + +## 5. Language-Agnostic VM Design + +### 5.1. Forth Compiler +- **Pattern**: *Multi-Language Frontend* +- **Why**: Demonstrates the VM's language-agnostic nature and validates the instruction set design. +- **How**: A separate Forth compiler (`scratch/forth/forth.awk`) generates the same VM bytecode, proving that the VM can execute code from different source languages. + +### 5.2. Shared Instruction Set +- **Pattern**: *Universal Bytecode* +- **Why**: Enables multiple languages to target the same VM, reducing implementation complexity. +- **How**: Both Scheme and Forth compilers generate identical VM instructions, allowing seamless execution of mixed-language programs. + +### 5.3. Standard Library Integration +- **Pattern**: *Shared Runtime* +- **Why**: Provides consistent functionality across different source languages. +- **How**: The VM's standard library functions are available to all languages targeting the VM, ensuring consistent behavior. + --- -## 5. Extensibility and Maintainability +## 6. Testing Architecture -### 5.1. Separation of Concerns +### 6.1. Comprehensive Test Suite +- **Pattern**: *Layered Testing Strategy* +- **Why**: Ensures correctness across different levels of complexity and use cases. +- **How**: Tests are organized into unit tests (48 tests), integration tests, regression tests, and examples, covering basic operations to complex higher-order function scenarios. + +### 6.2. Test Organization +- **Pattern**: *Test Categories* +- **Why**: Different types of tests serve different purposes in validation. +- **How**: Unit tests focus on individual features, integration tests validate complex interactions, regression tests prevent regressions, and examples demonstrate usage patterns. + +### 6.3. Error Detection Testing +- **Pattern**: *Negative Testing* +- **Why**: Ensures the system properly handles and reports errors. +- **How**: Tests include syntax error detection, type checking, and edge cases to validate error handling behavior. + +--- + +## 7. Extensibility and Maintainability + +### 7.1. Separation of Concerns - **Pattern**: *Layered Architecture* - **Why**: Compiler and VM are independent, making it easy to extend the language or change the execution model. - **How**: Clear interfaces between compilation and execution phases, with well-defined instruction formats. -### 5.2. Function Extension +### 7.2. Function Extension - **Pattern**: *Open/Closed Principle* (open for extension, closed for modification) - **Why**: Adding new functions should not require changes to existing code. - **How**: New functions are added by registering them in the `FUNCTIONS` table and implementing the corresponding VM function. -### 5.3. Error Handling +### 7.3. Error Handling - **Pattern**: *Fail-Fast* (for debugging) - **Why**: Early error detection helps identify issues quickly during development. - **How**: Functions validate arguments and types at runtime, throwing descriptive error messages. +### 7.4. Language Extension +- **Pattern**: *Plugin Architecture* (for new languages) +- **Why**: Enables new languages to target the VM without modifying existing code. +- **How**: New language compilers can be added as separate modules that generate the same VM bytecode. + --- -## 6. Notable Limitations and Future Enhancements +## 8. Notable Limitations and Future Enhancements -### 6.1. Current Limitations -- **Nested Lambda Support**: Limited support for lambdas defined inside other lambdas +### 8.1. Current Limitations - **Tail Recursion**: No proper tail call optimization - **Garbage Collection**: Reference counting is stubbed but not enforced - **Error Recovery**: Minimal error recovery in REPL - **Type System**: Basic runtime type checking only +- **Performance**: Limited optimization for complex expressions -### 6.2. Architectural Patterns for Future Enhancements +### 8.2. Architectural Patterns for Future Enhancements - **Continuation-Passing Style**: For proper tail recursion - **Generational Garbage Collection**: For memory management - **Exception Handling**: For better error recovery - **Type Inference**: For compile-time type checking +- **JIT Compilation**: For performance optimization --- -## 7. Summary Table: Patterns Used +## 9. Summary Table: Patterns Used | Area | Pattern(s) Used | Why? | |---------------------|----------------------------------|--------------------------------------| @@ -161,44 +225,57 @@ A little Scheme interpreter implemented in AWK, composed of a compiler and a sta | State Persistence | State Serialization | REPL continuity | | Memory Management | Manual Heap, Ref Counting (stub) | List support, future GC | | Error Handling | Fail-Fast | Debugging, development | +| Higher-Order Funcs | Function as Data, Context Pres. | Functional programming support | +| Multi-Language | Universal Bytecode, Shared Runtime| Language agnosticism | +| Testing | Layered Testing, Test Categories | Comprehensive validation | --- -## 8. Architectural Choices: Rationale +## 10. Architectural Choices: Rationale -### 8.1. Language Choice +### 10.1. Language Choice - **AWK as Implementation Language**: Chosen for portability and as a challenge; influences the use of arrays and string-based data structures. - **Why**: AWK's built-in associative arrays and string manipulation capabilities map well to the VM's needs. -### 8.2. VM Design +### 10.2. VM Design - **Stack Machine**: Maps well to AWK's capabilities and keeps the VM simple. - **Why**: Stack operations are straightforward to implement in AWK and provide clear semantics. -### 8.3. Modularity +### 10.3. Modularity - **Separation of Compiler/VM**: Enables clear boundaries and easier debugging. - **Why**: Independent development and testing of compilation and execution phases. -### 8.4. Type System +### 10.4. Type System - **Explicit Typing**: Reduces runtime errors and clarifies value handling. - **Why**: Tagged values provide runtime safety and clear debugging information. +### 10.5. Language Agnosticism +- **Universal VM Target**: Enables multiple languages to share the same runtime. +- **Why**: Reduces implementation complexity and enables language experimentation. + --- -## 9. Flow Diagram (Textual) +## 11. Flow Diagram (Textual) ``` -User Input (Scheme) → [Compiler] → VM Instructions → [VM] → Result/State - ↓ - [Display/Output] +User Input (Scheme/Forth) → [Compiler] → VM Instructions → [VM] → Result/State + ↓ + [Display/Output] ``` -## 10. Key Architectural Insights +## 12. Key Architectural Insights -### 10.1. Pattern Composition +### 12.1. Pattern Composition The system demonstrates how classic architectural patterns can be composed to create a functional interpreter. The combination of Registry, Visitor, and Strategy patterns enables extensibility while maintaining simplicity. -### 10.2. AWK-Specific Adaptations +### 12.2. AWK-Specific Adaptations The patterns are adapted to AWK's strengths: associative arrays for registries, string manipulation for value representation, and procedural programming for the VM loop. -### 10.3. Extensibility Through Registration -The function registration system demonstrates how a simple registry pattern can enable significant extensibility without complex inheritance hierarchies or plugin systems.
\ No newline at end of file +### 12.3. Extensibility Through Registration +The function registration system demonstrates how a simple registry pattern can enable significant extensibility without complex inheritance hierarchies or plugin systems. + +### 12.4. Language Agnosticism +The VM's language-agnostic design demonstrates how a well-designed instruction set can support multiple source languages, enabling experimentation and reducing implementation complexity. + +### 12.5. Higher-Order Function Support +The nested function call system shows how complex functional programming features can be implemented in a simple stack-based VM, enabling powerful data transformation capabilities.
\ No newline at end of file |