aboutsummaryrefslogtreecommitdiffstats
path: root/awk
diff options
context:
space:
mode:
authorelioat <elioat@tilde.institute>2025-07-20 23:23:17 -0400
committerelioat <elioat@tilde.institute>2025-07-20 23:23:17 -0400
commitd242546a4a618a97307e74c066080395d1333e7b (patch)
tree96e5bc875ed663b90e810ee48c813a235f7cd9b5 /awk
parent375f5ba917d733662ea161c2e17c2416418343b9 (diff)
downloadtour-d242546a4a618a97307e74c066080395d1333e7b.tar.gz
*
Diffstat (limited to 'awk')
-rw-r--r--awk/scheme/scheme/README.md28
-rw-r--r--awk/scheme/scheme/scratch/OUTLINE.md138
-rw-r--r--awk/scheme/scheme/scratch/arch-notes.md133
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