diff options
Diffstat (limited to 'js/scripting-lang/README.md')
| -rw-r--r-- | js/scripting-lang/README.md | 400 |
1 files changed, 149 insertions, 251 deletions
diff --git a/js/scripting-lang/README.md b/js/scripting-lang/README.md index b5d88d7..5890a06 100644 --- a/js/scripting-lang/README.md +++ b/js/scripting-lang/README.md @@ -1,296 +1,194 @@ -# Scripting Language: A Combinator-Based Functional Language +# Baba Yaga +## A Scripting Language -A functional programming language built on a **combinator foundation** that eliminates parsing ambiguity while preserving intuitive syntax. Every operation is a function call under the hood, creating a consistent and extensible language architecture. +Baba Yaga is a combinator-based scripting language that aims to be dangerously functional-brained, has minimal syntax, an intuitive approach to pattern matching, and hopefully enough of a standard library to be useful...but not too much of a standard library to be difficult to recall. -## Quick Start +This whole thing started as an aesthetic curiosity, and continued on from there. I wanted to be able to do pattern matching like this: -### Running Scripts -```bash -# Basic script execution -bun run lang.js script.txt - -# With debug output -DEBUG=1 bun run lang.js script.txt +```plaintext +factorial : n -> + when n is + 0 then 1 + _ then n * (factorial (n - 1)); ``` -### Example Script -```javascript -/* Basic arithmetic with combinator translation */ -x : 5; -y : 3; -result : x + y; // becomes add(x, y) internally - -/* Function definition and application */ +I've implemented a whole bunch of [forths](https://git.sr.ht/~eli_oat/chupacabra), and a couple schemes, but never have I ever implemented something like a "regular" programming language. And, while, an [ML-flavored](https://en.wikipedia.org/wiki/Standard_ML) programming language isn't exactly regular, this has grown from an aesthetic curiosity to a full-blown aesthetic indulgence. + +Baba Yaga supports... + +- **Function definitions** using arrow syntax with lexical scoping +- **Pattern matching** with a single `when ... is ... then` expression that handles wildcards and arbitrarily nested features +- **Tables** inspired by Lua's tables, with array-like and key-value entries, including boolean keys +- **Function references** using an `@` operator for higher-order programming +- **IO Operations** including input, output, and assertions, plus an `..emit` and `..listen` pattern for interfacing a functional core with the outside world. This contains side effects to a very limited surface area +- **Standard Library** with a complete set of arithmetic, comparison, logical, and higher-order combinators...I think (let me know if I'm missing anything) +- **APL-style operations** with element-wise and immutable table operations so that you can use broadcasting instead of looping +- **Function composition** with `compose`, `pipe`, and `via` operators, supporting a bunch of different ways to chain functions together +- **Currying by default** - all functions are automatically curried +- **Combinator-based architecture** everything is "just" a function call or reference under the hood...because this supposedly made parsing easier...but I'm not yet totally sold on that reasoning + +## Example Script +```plaintext +/* Basic arithmetic */ +result : 5 + 3 * 2; +..out result; + +/* Function definition */ +factorial : n -> + when n is + 0 then 1 + _ then n * (factorial (n - 1)); + +/* Function composition */ double : x -> x * 2; -result : double 5; // becomes apply(double, 5) internally - -/* Function composition with @ operator */ -add1 : x -> x + 1; -ref : @double; // function reference -result : ref 5; // call referenced function +increment : x -> x + 1; +composed : compose @double @increment 5; +..out composed; /* Pattern matching */ -message : when result is - 10 then "ten" - 12 then "twelve" - _ then "other"; - -/* Output */ -..out message; +classify : x y -> + when x y is + 0 0 then "both zero" + 0 _ then "x is zero" + _ 0 then "y is zero" + _ _ then "neither zero"; + +/* Tables */ +person : {name: "Baba Yaga", age: 99, active: true}; +..out person.name; +..out person["age"]; + +numbers : {1, 2, 3, 4, 5}; +doubled : map @double numbers; +..out doubled[1]; + +/* APL-style element-wise operations over tables */ +table1 : {a: 1, b: 2, c: 3}; +table2 : {a: 10, b: 20, c: 30}; +sum : each @add table1 table2; +..out sum.a; ``` -## Current Status - -### ✅ Recently Completed -- **@ Operator**: Function reference syntax working perfectly -- **Standard Library**: All higher-order functions working with @ syntax -- **Precedence Issues**: All operator precedence issues resolved -- **Partial Application**: Fixed `reduce`, `fold`, `curry` functions +Baba Yaga files should use either the `.txt` file extension, or the `.baba` extension. -### 🔧 Active Issues -- **Case Expression Parsing**: Fix "Unexpected token in parsePrimary: THEN" errors -- **Test Suite**: Get all tests passing (currently 8/18) +## Key Features -### 📊 Test Results -- **Passing**: 8/18 tests (all core features working) -- **Failing**: 10/18 tests (due to case expression parsing) -- **Architecture**: Working correctly -- **Function Composition**: ✅ Complete and working +### Function Application -## Why This Approach? +Functions are applied using juxtaposition (space-separated), and you can use parentheses to help disambiguate precedence: +```plaintext +f x /* Apply function f to argument x */ +f x y /* Apply f to x, then apply result to y */ +f (g x) /* Apply g to x, then apply f to result */ +``` -### The Problem We Solved -Traditional language parsers struggle with **operator precedence ambiguity**. Consider `f x + y` - should this be `(f x) + y` or `f (x + y)`? Most languages solve this with complex precedence tables, but we took a different approach. +### Pattern Matching -### The Combinator Solution -We translate **every operation into a function call**: -- `x + y` becomes `add(x, y)` -- `x - y` becomes `subtract(x, y)` -- `f x` becomes `apply(f, x)` -- `true and false` becomes `logicalAnd(true, false)` +Use `when` expressions for pattern matching: +```plaintext +result : when value is + 0 then "zero" + 1 then "one" + _ then "other"; +``` -This eliminates ambiguity entirely while keeping the syntax clean and intuitive. +### Tables -### Benefits -- **Zero Ambiguity**: Every expression has exactly one interpretation -- **Functional Foundation**: Everything is a function, enabling powerful abstractions -- **Extensible**: Add new operations by simply adding combinator functions -- **Consistent**: All operations follow the same pattern -- **Preserves Syntax**: Existing code continues to work unchanged +Create and access data structures: +```plaintext +/* Array-like */ +numbers : {1, 2, 3, 4, 5}; -## How It Works +/* Key-value pairs */ +person : {name: "Beatrice", age: 26}; -### Architecture Overview -``` -Source Code → Lexer → Parser → AST → Interpreter → Result - ↓ ↓ ↓ ↓ - Tokens → Combinator Translation → Function Calls +/* Boolean keys */ +flags : {true: "enabled", false: "disabled"}; ``` -### The Magic: Operator Translation -When you write `x + y * z`, the parser automatically translates it to: -```javascript -add(x, multiply(y, z)) +### Function References + +Use the `@` to make reference to functions as arguments for other functions: +```plaintext +numbers : {1, 2, 3, 4, 5}; +doubled : map @double numbers; ``` -This happens transparently - you write natural syntax, but get functional semantics. +## Combinators and Higher-Order Functions -### Function Application with Juxtaposition -Functions are applied by placing arguments next to them: -```javascript -f : x -> x * 2; -result : f 5; // apply(f, 5) → 10 -``` +Baba Yaga tries to provide a comprehensive set of combinators for functional programming: -### Function References with @ Operator -Reference functions without calling them: -```javascript -double_func : x -> x * 2; -ref : @double_func; // function reference -result : ref 5; // call referenced function -``` +### Core Combinators -## Language Features - -### Core Philosophy -- **Immutable by Default**: Variables cannot be reassigned -- **Functions First**: Everything is a function or function application -- **Pattern Matching**: Natural case expressions with wildcards -- **Lexical Scoping**: Functions create their own scope - -### Key Features -- **Combinator Foundation**: All operations are function calls -- **Function References**: `@` operator for function references -- **Pattern Matching**: `when` expressions with wildcard support -- **Tables**: Lua-style tables with array and key-value support -- **Standard Library**: Higher-order functions (`map`, `compose`, `pipe`, etc.) -- **IO Operations**: Built-in input/output (`..in`, `..out`, `..assert`) - -## Development Workflow - -### Testing Strategy -We use a **progressive testing approach** to ensure quality: - -#### 1. Scratch Tests (`scratch_tests/`) -**Purpose**: Rapid prototyping and debugging -- **Location**: `scratch_tests/*.txt` -- **Use Case**: Isolating specific issues, testing new features -- **Naming**: `test_<feature>_<purpose>.txt` (e.g., `test_precedence_simple.txt`) -- **Lifecycle**: Temporary, can be deleted after issue resolution - -#### 2. Unit Tests (`tests/`) -**Purpose**: Comprehensive feature coverage -- **Location**: `tests/*.txt` -- **Use Case**: Validating complete feature implementations -- **Naming**: `##_<feature_name>.txt` (e.g., `01_lexer_basic.txt`) -- **Lifecycle**: Permanent, part of regression testing - -#### 3. Integration Tests (`tests/`) -**Purpose**: Testing feature combinations -- **Location**: `tests/integration_*.txt` -- **Use Case**: Ensuring features work together -- **Naming**: `integration_##_<description>.txt` - -### Development Process - -#### When Adding New Features -1. **Create scratch test** to explore the feature -2. **Implement incrementally** with frequent testing -3. **Debug with `DEBUG=1`** for detailed output -4. **Promote to unit test** when feature is stable -5. **Add integration tests** for feature combinations - -#### When Fixing Bugs -1. **Create minimal scratch test** reproducing the issue -2. **Debug with `DEBUG=1`** to understand the problem -3. **Fix the issue** and verify with scratch test -4. **Update existing tests** if needed -5. **Clean up scratch tests** after resolution - -### Debugging Tools - -#### Enable Debug Mode -```bash -DEBUG=1 bun run lang.js script.txt -``` +- `map f x` - Transform elements in collections +- `filter p x` - Select elements based on predicates +- `reduce f init x` - Accumulate values into a single result +- `each f x` - Multi-argument element-wise operations -This shows: -- Token stream from lexer -- AST structure from parser -- Function call traces -- Scope information +### Function Composition -#### Call Stack Tracking -The interpreter tracks function calls to detect infinite recursion: -```bash -# Shows call statistics after execution -bun run lang.js script.txt -``` +- `compose f g` - Right-to-left composition (mathematical style) +- `pipe f g` - Left-to-right composition (pipeline style) +- `via` - Kinda like `.` composition syntax: `f via g via h` -### Running Tests -```bash -# Run all tests -./run_tests.sh +### Table Operations -# Run individual test -bun run lang.js tests/01_lexer_basic.txt +All table operations are immutable so they return new tables. -# Run scratch test -bun run lang.js scratch_tests/test_debug_issue.txt -``` +- `t.map`, `t.filter`, `t.set`, `t.delete`, `t.merge`, `t.get`, `t.has`, `t.length` -## Architecture Deep Dive +### When to Use Which Combinator -### Combinator Foundation -Every operation is implemented as a function call to standard library combinators: +- Use `map` for general collections, `t.map` to emphasize table operations +- Use `map` for single-table transformations, `each` for combining multiple collections. -```javascript -// Arithmetic -x + y → add(x, y) -x - y → subtract(x, y) -x * y → multiply(x, y) -// Comparison -x = y → equals(x, y) -x > y → greaterThan(x, y) +### Standard Library -// Logical -x and y → logicalAnd(x, y) -not x → logicalNot(x) +The language includes a comprehensive standard library: -// Function application -f x → apply(f, x) -``` +**Arithmetic**: `add`, `subtract`, `multiply`, `divide`, `modulo`, `power`, `negate` +**Comparison**: `equals`, `notEquals`, `lessThan`, `greaterThan`, `lessEqual`, `greaterEqual` +**Logical**: `logicalAnd`, `logicalOr`, `logicalXor`, `logicalNot` +**Higher-Order**: `map`, `compose`, `pipe`, `apply`, `filter`, `reduce`, `fold`, `curry`, `each` +**Enhanced**: `identity`, `constant`, `flip`, `on`, `both`, `either` +**Table Operations**: `t.map`, `t.filter`, `t.set`, `t.delete`, `t.merge`, `t.get`, `t.has`, `t.length` + +## Architecture + +Baba Yaga uses a combinator-based architecture where all operations are translated to function calls: + +1. **Lexer**: Converts source code into tokens +2. **Parser**: Translates tokens into AST, converting operators to combinator calls +3. **Interpreter**: Executes combinator functions from the standard library -### Standard Library Combinators -The language includes a comprehensive set of combinators: -- **Arithmetic**: `add`, `subtract`, `multiply`, `divide`, `negate` -- **Comparison**: `equals`, `greaterThan`, `lessThan`, etc. -- **Logical**: `logicalAnd`, `logicalOr`, `logicalNot` -- **Higher-Order**: `map`, `compose`, `pipe`, `apply`, `filter` - -### Parser Architecture -The parser uses a **precedence climbing** approach with combinator translation: -1. **Lexer**: Converts source to tokens -2. **Parser**: Builds AST with operator-to-function translation -3. **Interpreter**: Evaluates AST using combinator functions - -## Documentation - -### Design Documents -- **[design/README.md](design/README.md)** - Main design documentation entry point -- **[design/PROJECT_ROADMAP.md](design/PROJECT_ROADMAP.md)** - Current status and next steps -- **[design/COMBINATORS.md](design/COMBINATORS.md)** - Combinator foundation explanation -- **[design/ARCHITECTURE.md](design/ARCHITECTURE.md)** - Complete system architecture overview - -### Implementation Guides -- **[design/implementation/IMPLEMENTATION_GUIDE.md](design/implementation/IMPLEMENTATION_GUIDE.md)** - Current implementation guide -- **[design/implementation/COMPLETED_FEATURES.md](design/implementation/COMPLETED_FEATURES.md)** - Summary of completed features - -### Historical Documentation -- **[design/HISTORY/](design/HISTORY/)** - Resolved issues and completed work - -## Contributing - -### Development Guidelines -1. **Follow the combinator approach** for new operations -2. **Use scratch tests** for rapid prototyping -3. **Promote to unit tests** when features are stable -4. **Maintain backward compatibility** - existing code must work -5. **Document changes** in design documents - -### Code Style -- **Functional approach**: Prefer pure functions -- **Combinator translation**: All operations become function calls -- **Clear naming**: Descriptive function and variable names -- **Comprehensive testing**: Test edge cases and combinations - -### Testing Requirements -- **Unit tests** for all new features -- **Integration tests** for feature combinations -- **Backward compatibility** tests for existing code -- **Edge case coverage** for robust implementation - -## Quick Reference - -### Key Files -- **lang.js**: Main interpreter with standard library -- **parser.js**: Parser with combinator translation -- **lexer.js**: Tokenizer with all operators -- **tests/**: Comprehensive test suite - -### Development Commands +The idea behind this approach is that it should eliminate parsing ambiguity while preserving syntax and enabling functional programming patterns like currying and composition, but the implementation is likely a little bit janky. + +## Testing + +Run the complete test suite! ```bash -# Run all tests ./run_tests.sh +``` + +This assumes you are using bun, but I've also tested extensively with both node and the browser, too. I haven't validated it, yet, but I think Baba Yaga should work with quickjs, too. -# Run with debug -DEBUG=1 node lang.js script.txt +### Debug Mode -# Run individual test -node lang.js tests/01_lexer_basic.txt +Enable debug output for development using the flag `DEBUG=1` or `DEBUG=2`: +```bash +DEBUG=1 node lang.js your-script.txt ``` ---- +This'll output a lot of debug info, including the AST (as JSON). + +### Adding Features + +If you wanna add language features, the easiest way to do it is to see if you can implement them in Baba Yaga script, if you need to get into the guts of the thing, though, you wanna follow this pattern, -This language demonstrates how **functional programming principles** can solve real parsing problems while maintaining intuitive syntax. The combinator foundation provides a solid base for building powerful abstractions. \ No newline at end of file +1. Add tests in `tests/` +2. Add tokens in `lexer.js` +3. Add parsing logic in `parser.js` +4. Add evaluation logic in `lang.js` +5. Validate against the tests you added earlier +6. Update documentation \ No newline at end of file |