diff options
| author | elioat <elioat@tilde.institute> | 2025-07-20 20:47:51 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2025-07-20 20:47:51 -0400 |
| commit | 917cbb7c1cf1ad951ab5ee285787af560ed18be5 (patch) | |
| tree | e1e3da1c66787e339d29535a50f49238d5590a09 /awk | |
| parent | db479b4e241481d36431098242fa5098d14799dc (diff) | |
| download | tour-917cbb7c1cf1ad951ab5ee285787af560ed18be5.tar.gz | |
*
Diffstat (limited to 'awk')
| -rwxr-xr-x | awk/scheme/scheme/bin/vm.awk | 1 | ||||
| -rw-r--r-- | awk/scheme/scheme/scratch/OUTLINE.md | 264 |
2 files changed, 264 insertions, 1 deletions
diff --git a/awk/scheme/scheme/bin/vm.awk b/awk/scheme/scheme/bin/vm.awk index d1e8e00..550a0d2 100755 --- a/awk/scheme/scheme/bin/vm.awk +++ b/awk/scheme/scheme/bin/vm.awk @@ -483,7 +483,6 @@ function execute(instr) { if (stack_ptr < 2) error("SWAP requires two operands") val2 = pop() val1 = pop() - val1 = pop() push(val2) push(val1) } diff --git a/awk/scheme/scheme/scratch/OUTLINE.md b/awk/scheme/scheme/scratch/OUTLINE.md new file mode 100644 index 0000000..9969866 --- /dev/null +++ b/awk/scheme/scheme/scratch/OUTLINE.md @@ -0,0 +1,264 @@ +# Blog Post Outline: "I Built a Scheme VM in AWK and It's Surprisingly Not Terrible" + +## 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 + +## The Setup: Why AWK? (And Why Not?) +- The initial reaction: "AWK? Really?" +- What AWK actually is: a text processing language with some surprising features +- The appeal: simple, ubiquitous, built-in associative arrays +- The challenges: 1-indexed strings, weird syntax, limited data structures +- The realization: AWK is basically a functional language in disguise + +## Architecture Overview: The Three-Layer Cake +- **Layer 1: The Compiler** (`bin/compiler.awk`) + - 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 + +- **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 + +- **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 Weirdness: AWK Quirks That Made Me Question My Life Choices + +### 1-Indexed Everything +- Strings, arrays, everything starts at 1 +- The constant `substr(string, 1, index(string, ":") - 1)` dance +- Why `substr()` needs explicit length but `index()` returns 1-indexed positions +- The mental gymnastics of converting between 0-indexed and 1-indexed + +### Associative Arrays (The Good Part) +- AWK's killer feature: built-in hash maps +- How we use them for environments, function tables, closures +- The joy of `array[key] = value` without any setup +- The weirdness of `for (key in array)` syntax + +### String Manipulation: A Love-Hate Relationship +- `gsub()` for global substitution (like `replaceAll()`) +- `sub()` for single substitution +- The regex syntax that looks like it's from another planet +- Why string concatenation is just space-separation + +### File I/O: The AWK Way +- `getline` for reading files (returns 1/0/-1, not the data) +- `printf` with `>` for writing files +- The weirdness of `close()` being explicit +- State persistence using simple text files + +## The Compiler: From Scheme to Bytecode + +### Lexical Analysis: Tokenizing in AWK +- How we split Scheme expressions into tokens +- Handling parentheses, strings, numbers, symbols +- The challenge of nested expressions +- Why we need to track string literals to avoid paren confusion + +### Parsing: Recursive Descent in AWK +- Implementing a parser without parser generators +- 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 + +### Code Generation: From AST to Bytecode +- The instruction set: `PUSH_CONST`, `ADD`, `CALL`, `HALT` +- How we generate stack-based code +- The challenge of variable scoping +- Why function calls are just `CALL` instructions + +## The Virtual Machine: Stack-Based Execution + +### The Stack: Our Best Friend +- Simple stack operations: `push()`, `pop()`, `peek()` +- How everything becomes stack manipulation +- The beauty of stack-based execution +- Why we don't need registers (much) + +### Type System: Tagged Values +- Every value is `type:value` (e.g., `N:5`, `B:1`) +- Runtime type checking with `getType()` and `getValue()` +- The challenge of implementing lists with cons cells +- Why we need a heap for complex data structures + +### Environment Management: Lexical Scoping in AWK +- How we implement variable bindings +- Environment frames for function calls +- The complexity of closures +- Why capturing environments is harder than it looks + +### Function Calls: The Magic +- Built-in functions vs user-defined functions +- How we handle function lookup and execution +- 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 + +## The Forth Experiment: Proving Language Agnosticism + +### The Original Approach: Forth → Scheme → VM +- Translating Forth to Scheme expressions +- Using the existing compiler pipeline +- Why this felt like cheating + +### The Real Deal: Forth → VM Directly +- Building a Forth compiler that generates bytecode +- The joy of `PUSH_CONST N:5` and `ADD` +- Proving the VM is truly language-agnostic +- Why this is the real achievement + +### The Insight: Universal VM Target +- Any language can target this VM +- The same bytecode from different sources +- Why this matters for language design +- The power of a well-designed instruction set + +## Lessons Learned: What AWK Taught Me About Language Design + +### Simplicity is Powerful +- AWK's simple model enables complex things +- How constraints lead to creativity +- Why less is often more in language design + +### Stack-Based Execution is Beautiful +- The elegance of stack operations +- How it simplifies the VM +- Why many real VMs use this approach + +### Type Systems Matter +- Runtime type checking prevents bugs +- Tagged values enable safe operations +- Why type safety is worth the overhead + +### Environment Management is Hard +- Lexical scoping requires careful implementation +- Closures add significant complexity +- Why proper scoping is crucial for functional languages + +## The Weirdest Parts: AWK Quirks That Made Me Laugh/Cry + +### The 1-Indexed String Functions +- `substr(string, 1, length)` vs `string.slice(0, length)` +- The constant mental conversion +- Why this exists and how to cope + +### Associative Array Syntax +- `array[key] = value` without declaration +- The joy of `for (key in array)` +- Why this is AWK's best feature + +### File I/O Patterns +- `getline` returning status codes +- The explicit `close()` requirement +- Why AWK's I/O model is actually quite elegant + +### String Manipulation +- `gsub()` and `sub()` for regex replacement +- The regex syntax that looks alien +- Why AWK's string handling is powerful but weird + +## Performance and Limitations: The Reality Check + +### What Works Well +- Simple expressions compile and run quickly +- The REPL is responsive +- State persistence works reliably +- The type system prevents many bugs + +### What's Slow/Weird +- Complex expressions can be slow +- Memory usage with large programs +- The 1-indexed string operations +- Limited data structures beyond arrays + +### The AWK Tax +- Everything is string-based under the hood +- No native data structures beyond arrays +- Limited control flow constructs +- The constant string manipulation overhead + +## Conclusion: Was It Worth It? + +### The Unexpected Benefits +- Deep understanding of VM architecture +- Appreciation for language design decisions +- The joy of building something from scratch +- Why constraints breed creativity + +### The AWK Revelation +- AWK is more powerful than it looks +- Functional programming concepts work everywhere +- Simple tools can build complex systems +- Why the Unix philosophy matters + +### The Bigger Picture +- How this relates to real VMs (JVM, .NET, etc.) +- The universality of stack-based execution +- Why language-agnostic VMs are powerful +- The future of language design + +### Final Thoughts +- "I built a Scheme VM in AWK and it's surprisingly not terrible" +- The value of building things in unexpected languages +- Why understanding the fundamentals matters +- The joy of programming for its own sake + +## Technical Appendix: Key Code Snippets + +### The VM's Main Loop +```awk +while (pc < length(program)) { + execute(program[pc++]) +} +``` + +### Type System Implementation +```awk +function makeValue(type, val) { + return type ":" val +} +``` + +### Stack Operations +```awk +function push(val) { + stack[++stack_ptr] = val +} +``` + +### The Forth Compiler +```awk +if (token ~ /^-?[0-9]+$/) { + bytecode = bytecode "PUSH_CONST N:" token "\n" +} else if (token == "+") { + bytecode = bytecode "ADD\n" +} +``` + +## 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 |