diff options
Diffstat (limited to 'js/scripting-lang/baba-yaga-c/ROADMAP.md')
| -rw-r--r-- | js/scripting-lang/baba-yaga-c/ROADMAP.md | 877 |
1 files changed, 189 insertions, 688 deletions
diff --git a/js/scripting-lang/baba-yaga-c/ROADMAP.md b/js/scripting-lang/baba-yaga-c/ROADMAP.md index e6744b2..5f44ca4 100644 --- a/js/scripting-lang/baba-yaga-c/ROADMAP.md +++ b/js/scripting-lang/baba-yaga-c/ROADMAP.md @@ -1,708 +1,209 @@ -# Baba Yaga C Implementation - Complete Roadmap - -## Executive Summary - -**Current Status**: ✅ **Core Functionality Complete** - Major language features implemented -**Overall Progress**: ~90% Complete -**Test Results**: 26/26 basic tests PASS, 51/66 standard library tests PASS, 5/27 JavaScript tests PASS -**Critical Discovery**: 🔍 **Parser precedence system exists but not used** - infix operators blocked by 1-line fix -**Estimated Completion**: 1-2 days (after infix operator fix) - -## Language Overview - -Baba Yaga is a functional programming language with combinator-based architecture where all operators translate to function calls. The C implementation provides a high-performance, memory-efficient interpreter that maintains compatibility with the JavaScript reference implementation. - -### Key Features -- **Function Application**: Juxtaposition-based (`f x` means `apply(f, x)`) -- **Function References**: `@` operator for function references and expressions (`@function` and `@(expression)`) -- **Pattern Matching**: `when` expressions for conditional logic with wildcard support -- **User-Defined Functions**: `name : params -> body;` syntax -- **Tables**: APL-inspired data structures (planned) -- **Combinator Foundation**: All operations become function calls -- **Multiple Statements**: Semicolon-separated statement sequences - - - -## Current Implementation Status - -### ✅ COMPLETED - Core Functionality - -#### Phase 1: Foundation (COMPLETE) -- **Value System**: ✅ Complete with all data types (number, string, boolean, table, function, nil) -- **Table Implementation**: ✅ Immutable hash table with reference counting -- **Memory Management**: ✅ Reference counting for tables and functions -- **Function Representation**: ✅ Native and user function support - -#### Phase 2: Lexer (COMPLETE) -- **Tokenization**: ✅ Complete with all token types including IO operations -- **Special Cases**: ✅ Unary/binary minus handling, function references (`@function`) -- **Error Handling**: ✅ Line/column information in error messages -- **Performance**: ✅ Efficient tokenization for large files - -#### Phase 3: Parser (COMPLETE) -- **AST Construction**: ✅ Complete AST node types for all language constructs -- **Operator Precedence**: ✅ Proper precedence handling with combinator translation -- **Combinator Translation**: ✅ All operators translate to function calls -- **Pattern Matching**: ✅ Complete pattern parsing with `when` expressions -- **Function Definitions**: ✅ User-defined function parsing with `->` syntax -- **Function References**: ✅ `@` operator parsing for both `@function` and `@(expression)` - -#### Phase 4: Interpreter Foundation (COMPLETE) -- **Scope Management**: ✅ Complete scope system with variable lookup and assignment -- **Function Calling**: ✅ Native function calling with proper argument passing -- **Standard Library**: ✅ Complete standard library with 20+ functions -- **Error Handling**: ✅ Runtime error detection and reporting infrastructure - -#### Phase 5: Enhanced Interpreter (COMPLETE) -- **Full AST Execution**: ✅ Complete expression evaluation pipeline -- **Function References**: ✅ @ operator support for function references and expressions -- **Pattern Matching**: ✅ Complete `when` expression evaluation with wildcard support -- **User-Defined Functions**: ✅ Function creation, parameter binding, and execution -- **Basic Integration**: ✅ Complete lexer → parser → interpreter pipeline - -#### Phase 6: Multiple Statement Support (COMPLETE) -- **Sequence Parsing**: ✅ Parse semicolon-separated statements into sequence nodes -- **Statement Execution**: ✅ Execute statements in sequence, return last value -- **Variable Scoping**: ✅ Variables defined in earlier statements available in later ones -- **Real-world Usage**: ✅ Language now supports practical multi-statement programs - -## 🔴 CRITICAL ISSUES TO FIX - -### 1. Multiple Statement Parsing (CRITICAL) ✅ **COMPLETED** -**Current Status**: ✅ All statements executed in sequence -**Impact**: ✅ Unblocks real-world usage -**Priority**: ✅ RESOLVED -**Effort**: ✅ Completed - -**Implementation**: -- ✅ Implemented `NODE_SEQUENCE` AST node type -- ✅ Created `parser_parse_statements()` for semicolon-separated parsing -- ✅ Updated interpreter to execute statement sequences -- ✅ Added sequence node accessor functions -- ✅ Updated test suite to reflect working functionality - -**Example Working**: -```c -// ✅ "x : 10; y : 20; add x y" → executes all three statements, returns 30 -// ✅ "a : 5; b : 3; c : 2; add a @multiply b c" → returns 11 -``` - -### 2. JavaScript Test Suite Compatibility (HIGH PRIORITY) 🔄 **IN PROGRESS** -**Current Status**: 5/27 tests pass (19% success rate) -**Priority**: HIGH -**Effort**: 1-2 days - -**Major Missing Features**: - -#### Infix Operators (CRITICAL - 15+ tests) 🔴 **BLOCKING - DISCOVERED ROOT CAUSE** -- **Arithmetic**: `a + b`, `a - b`, `a * b`, `a / b`, `a % b`, `a ^ b` -- **Logical**: `a and b`, `a or b`, `a xor b`, `not a` -- **Comparison**: `a = b`, `a > b`, `a < b`, `a >= b`, `a <= b`, `a != b` -- **Status**: 🔧 **PARSER PRECEDENCE SYSTEM EXISTS BUT NOT USED** -- **Root Cause**: Main `parser_parse_expression()` calls `parser_parse_application()` instead of `parser_parse_logical()` -- **Impact**: Blocks tests 01, 02, 03, 04, 05, 08, 11, 13, 14, 15, 16, 18, 19, 20, 22, 23 -- **Effort**: 1-2 hours (simple function call change) -- **Solution**: Change main expression parser to use existing operator precedence chain: - ```c - // Current (prefix-only): - static ASTNode* parser_parse_expression(Parser* parser) { - return parser_parse_application(parser); - } - - // Fixed (infix support): - static ASTNode* parser_parse_expression(Parser* parser) { - return parser_parse_logical(parser); - } - ``` -- **Existing Precedence Chain**: `logical` → `comparison` → `additive` → `multiplicative` → `power` → `primary` -- **All Operator Tokens**: Already implemented in lexer -- **All Operator Functions**: Already implemented in parser -- **Interpreter Support**: Already handles binary operations - -#### Pattern Matching (Critical - 8+ tests) ✅ **COMPLETED** -- `when` expressions: `when x is 42 then "correct" _ then "wrong"` -- **Status**: ✅ Fully implemented and working -- **Features**: Basic patterns, multiple patterns, wildcard (`_`) support, variable assignment context -- **Fix Applied**: Added `TOKEN_KEYWORD_WHEN`, `TOKEN_KEYWORD_IS`, `TOKEN_KEYWORD_THEN` to function call parsing stop tokens -- **Impact**: Unblocks tests 01, 07, 21, and integration tests -- **Result**: Pattern matching now works in all contexts - -#### Function Definitions (High - 3+ tests) ✅ **COMPLETED** -- User-defined functions: `name : params -> body;` -- **Status**: ✅ Fully implemented and working -- **Features**: Function definition parsing, function storage, parameter binding, function execution -- **Working**: Identity functions, simple parameter binding, `@` operator support, complex function bodies -- **Fix Applied**: Modified `baba_yaga_function_call()` to accept scope parameter and pass current scope as parent -- **Impact**: Unblocks basic function tests (test 06 passes) and complex function bodies now work -- **Result**: Function definitions work for all cases including complex function bodies - -#### Tables (High - 5+ tests) -- Data structures: `data : {a: 1, b: 2};` -- **Impact**: Blocks tests 09, 12, 17 -- **Effort**: 3-4 hours - -#### Advanced Features (Medium - 8+ tests) -- Each combinator, embedded functions, via operator, etc. -- **Impact**: Blocks tests 18-23 -- **Effort**: 3-4 hours - -**Tasks**: -- [x] Implement pattern matching (`when` expressions) ✅ -- [x] Debug variable assignment context for `when` expressions ✅ -- [x] Add user-defined function syntax (`->`) ✅ -- [x] Implement `@` operator for function references and expressions ✅ -- [x] Debug function calls within function bodies (CRITICAL - blocks complex functions) ✅ -- [ ] Implement infix operators (CRITICAL - blocks 15+ tests) -- [ ] Implement table data structures -- [ ] Add advanced functional programming features (each combinator, via operator, etc.) - -### 3. Standard Library Issues (MEDIUM PRIORITY) ✅ **MOSTLY COMPLETED** -**Current Status**: 64/66 tests pass (97% success rate) -**Priority**: MEDIUM -**Effort**: 1-2 days - -**Specific Failures**: - -#### Type Checking (0 failures) ✅ **COMPLETED** -- `equals` function: ✅ Added type mismatch error for different argument types -- `and` function: ✅ Added type mismatch error for non-boolean arguments -- `not` function: ✅ Added type mismatch error for non-boolean arguments -- **Fix Applied**: Added proper type validation to all three functions -- **Result**: All type checking tests now pass - -#### Precision Issues (2 failures) ✅ **MOSTLY COMPLETED** -- `divide` function: ✅ Fixed precision for floating point division -- `pow` function: ✅ Fixed precision for square root (minor 1-digit difference) -- Negative power: Still fails due to negative number parsing issue -- **Fix Applied**: - - Fixed main function to use `baba_yaga_value_to_string()` instead of `printf("%g")` - - Updated value conversion to use `%.16g` format for natural precision -- **Result**: 4/6 precision tests now pass - -**Remaining Tasks**: -- [ ] Fix negative number parsing for `pow 2 -1` case -- [ ] Minor precision adjustment for square root (1 digit difference) - -## 🟡 MEDIUM PRIORITY ISSUES - -### 3. User-Defined Functions (MEDIUM) -**Current Status**: Not implemented -**Priority**: MEDIUM -**Effort**: 3-4 days - -**Required Features**: -- Function body storage in AST -- Parameter binding during calls -- Local scope creation -- Recursive function support - -**Tasks**: -- [ ] Implement function body storage in AST -- [ ] Add parameter binding during function calls -- [ ] Create local scope creation for function execution -- [ ] Support recursive function calls -- [ ] Add stack overflow protection - -### 4. Pattern Matching Evaluation (MEDIUM) -**Current Status**: Basic parsing complete, evaluation pending -**Priority**: MEDIUM -**Effort**: 2-3 days - -**Required Features**: -- Boolean expression evaluation in patterns -- Multiple value patterns -- Pattern guards - -**Tasks**: -- [ ] Implement pattern matching engine -- [ ] Add boolean expression evaluation in patterns -- [ ] Support multiple value patterns -- [ ] Add wildcard pattern support -- [ ] Implement enhanced case statements - -### 5. Enhanced Error Handling (MEDIUM) -**Current Status**: Basic error detection -**Priority**: MEDIUM -**Effort**: 1-2 days - -**Required Features**: -- Specific error messages with context -- Line/column numbers in errors -- Source code snippets -- Stack traces for function calls - -**Tasks**: -- [ ] Add specific error messages (division by zero, undefined variable, etc.) -- [ ] Add error context (line/column numbers, source snippets) -- [ ] Add error recovery where possible -- [ ] Improve error message formatting - -## 🔵 LOW PRIORITY ISSUES - -### 6. Memory Leak Testing (LOW) -**Current Status**: Not tested -**Priority**: LOW -**Effort**: 1 day - -**Tasks**: -- [ ] Add valgrind to build system -- [ ] Create `make memcheck` target -- [ ] Test all components for leaks -- [ ] Fix any memory issues found -- [ ] Add memory usage monitoring - -### 7. Performance Optimization (LOW) -**Current Status**: Basic performance -**Priority**: LOW -**Effort**: 1-2 days - -**Tasks**: -- [ ] Profile critical execution paths -- [ ] Optimize memory allocation patterns -- [ ] Add performance benchmarks -- [ ] Optimize AST accessor functions - -### 8. Documentation and Testing (LOW) -**Current Status**: Basic documentation -**Priority**: LOW -**Effort**: 1 day - -**Tasks**: -- [ ] Complete API documentation -- [ ] Add comprehensive test suite -- [ ] Create architecture documentation -- [ ] Add usage examples - -## Current State - For New Team Members - -### What's Working ✅ - -#### Core Language Features -- **Basic Expressions**: Numbers, strings, booleans, variables -- **Arithmetic Operations**: `add`, `subtract`, `multiply`, `divide`, `modulo`, `pow` -- **Comparison Operations**: `equals`, `not_equals`, `less`, `greater`, etc. -- **Logical Operations**: `and`, `or`, `xor`, `not` -- **Function Calls**: Native function calling with proper argument evaluation -- **Function References**: `@function` and `@(expression)` syntax -- **Variable Assignment**: `name : value;` syntax -- **Multiple Statements**: Semicolon-separated sequences execute correctly - -#### Advanced Features -- **Pattern Matching**: `when` expressions with wildcard (`_`) support -- **User-Defined Functions**: `name : params -> body;` syntax -- **Higher-Order Functions**: `apply`, `compose` working correctly -- **IO Operations**: `..out`, `..assert` working correctly - -#### Test Results -- **Basic Tests**: 26/26 PASS (100%) -- **Standard Library**: 60/66 PASS (91%) -- **JavaScript Compatibility**: 4/27 PASS (15%) - -### What's Partially Working ⚠️ - -#### User-Defined Functions -- ✅ Function definition parsing works -- ✅ Function storage in scope works -- ✅ Parameter binding works -- ✅ Simple function bodies work (e.g., `x -> x`) -- ❌ Complex function bodies fail (e.g., `x y -> add x y` returns `nil`) - -**Example Working**: -```c -identity_func : x -> x; // ✅ Works -identity_func 42; // ✅ Returns 42 -``` - -**Example Failing**: -```c -add_func : x y -> add x y; // ❌ Function body returns nil -add_func 3 4; // ❌ Returns nil instead of 7 -``` - -### What's Not Implemented ❌ - -#### Tables -- Table literals: `{a: 1, b: 2}` -- Table access: `table.key` or `table["key"]` -- Table operations: `keys`, `values`, `size` - -#### Advanced Functional Features -- Each combinator: `each function list` -- Via operator: `via function value` -- Embedded functions: Functions within expressions -- Function composition with multiple functions - -#### Syntax Differences from JavaScript -- **Assertion Syntax**: JavaScript uses `..assert sum = 13`, C uses `..assert equals sum 13` - -### What's Partially Implemented 🔧 - -#### Infix Operators (CRITICAL DISCOVERY) -- **Status**: 🔧 **PARSER PRECEDENCE SYSTEM EXISTS BUT NOT USED** -- **Root Cause**: Main expression parser calls wrong function -- **Impact**: Blocks 15+ JavaScript compatibility tests -- **Fix**: Simple 1-line change in `parser_parse_expression()` -- **Expected Result**: Immediate unblocking of infix operator support - -### Critical Issues to Address - -#### 1. Infix Operator Parsing (CRITICAL PRIORITY) 🔴 **BLOCKING** -**Problem**: Infix operators (`x + y`, `3 < 5`) fail with "Unexpected token in expression" -**Root Cause**: Main `parser_parse_expression()` calls `parser_parse_application()` instead of `parser_parse_logical()` -**Impact**: Blocks 15+ JavaScript compatibility tests -**Fix**: Change one line in `src/parser.c` line 1342 -**Effort**: 1-2 hours -**Files to Check**: `src/parser.c` line 1342 - -#### 2. Logical Operator Parsing (HIGH PRIORITY) -**Problem**: `and`, `or`, `xor` keywords parsed as function calls instead of operators -**Root Cause**: Logical operators need special handling in parser -**Impact**: Blocks 6 standard library tests -**Fix**: Update logical operator parsing in `parser_parse_logical()` -**Effort**: 1 hour -**Files to Check**: `src/parser.c` logical operator handling - -#### 3. Function Calls in Function Bodies (MEDIUM PRIORITY) -**Problem**: Function calls like `add x y` within function bodies return `nil` -**Root Cause**: Function call arguments are not being evaluated to their values -**Impact**: Blocks complex user-defined functions -**Files to Check**: `src/interpreter.c` function call evaluation, `src/function.c` user function execution - -#### 4. Table Implementation (MEDIUM PRIORITY) -**Problem**: Table data structures not implemented -**Impact**: Blocks tests 09, 12, 17 -**Files to Check**: `src/table.c` (exists but needs implementation) - -#### 5. Advanced Combinators (MEDIUM PRIORITY) -**Problem**: Each combinator, via operator not implemented -**Impact**: Blocks tests 18-23 -**Files to Check**: `src/stdlib.c` for combinator implementations - -### Code Architecture - -#### Key Files -- `src/lexer.c`: Tokenization (✅ Complete) -- `src/parser.c`: AST construction (✅ Complete) -- `src/interpreter.c`: Expression evaluation (✅ Complete) -- `src/function.c`: Function management (✅ Complete) -- `src/scope.c`: Variable scoping (✅ Complete) -- `src/stdlib.c`: Standard library (✅ Complete) -- `src/table.c`: Table implementation (❌ Needs work) - -#### Key Data Structures -- `Value`: Union type for all values (number, string, boolean, function, table, nil) -- `ASTNode`: Abstract syntax tree nodes -- `Scope`: Variable scope with parent-child relationships -- `FunctionValue`: Function representation with native/user distinction - -#### Key Functions -- `baba_yaga_execute()`: Main execution entry point -- `interpreter_evaluate_expression()`: Core evaluation logic -- `baba_yaga_function_call()`: Function calling mechanism -- `scope_define()` / `scope_get()`: Variable management - -### Testing Strategy - -#### Test Suites -- `run_tests.sh`: Basic functionality tests (26 tests, all pass) -- `test_stdlib.sh`: Standard library tests (66 tests, 60 pass) -- `run_comprehensive_tests.sh`: JavaScript compatibility tests (27 tests, 4 pass) - -#### Debugging Commands -```bash -# Build with debug info -make debug - -# Test specific features -./bin/baba-yaga 'add 3 4;' # Basic function call -./bin/baba-yaga '@(add 3 4);' # Function reference -./bin/baba-yaga 'x : 42; x;' # Variable assignment -./bin/baba-yaga 'when 42 is 42 then "yes";' # Pattern matching -./bin/baba-yaga 'f : x -> x; f 42;' # User-defined function - -# Run test suites -./run_tests.sh -./test_stdlib.sh -./run_comprehensive_tests.sh -``` - -## Implementation Roadmap - -### Week 1: Critical Fixes - -#### Days 1-2: Infix Operator Implementation (CRITICAL) -**Dependencies**: None -**Success Criteria**: -- `"a + b"`, `"a and b"`, `"a = b"` parse and execute correctly -- Operator precedence and associativity work properly -- `@(a + b)` syntax works with infix expressions -- 15+ JavaScript compatibility tests pass - -#### Days 3-5: Standard Library and Table Implementation (HIGH) -**Dependencies**: Infix operators -**Success Criteria**: -- All 66 standard library tests pass -- Basic table operations work (`{a: 1, b: 2}`) -- Higher-order functions work correctly -- IO operations behave as expected -- Type errors are properly reported - -### Week 2: Advanced Features - -#### Days 1-3: User-Defined Functions (MEDIUM) -**Dependencies**: Standard library fixes -**Success Criteria**: -- User-defined functions can be created and called -- Parameters are properly bound -- Local variables work correctly -- Recursive functions work - -#### Days 4-5: Pattern Matching and Polish (MEDIUM/LOW) -**Dependencies**: User-defined functions -**Success Criteria**: -- Complex when expressions work -- Boolean patterns evaluate correctly -- Multi-parameter patterns work -- Pattern guards function properly -- No memory leaks detected -- Comprehensive error messages - -## Test Results Analysis - -### ✅ Passing Tests (94/119 = 79%) -- **Basic Functionality**: 26/26 tests PASS (100%) -- **Standard Library**: 64/66 tests PASS (97%) -- **JavaScript Compatibility**: 4/27 tests PASS (15%) - -#### Detailed Breakdown - -**Basic Tests (26/26 PASS)**: -- Arithmetic operations, function calls, variable assignment -- Multiple statements, higher-order functions, IO operations -- Error handling, pattern matching basics - -**Standard Library Tests (60/66 PASS)**: -- Core arithmetic: `add`, `subtract`, `multiply`, `divide`, `modulo`, `pow` -- Comparison: `equals`, `not_equals`, `less`, `greater`, etc. -- Logical: `and`, `or`, `xor`, `not` -- Higher-order: `apply`, `compose` -- IO: `..out`, `..assert` - -**JavaScript Compatibility Tests (4/27 PASS)**: -- ✅ `02_arithmetic_operations`: Basic arithmetic working -- ✅ `04_logical_operators`: Logical operations working -- ✅ `06_function_definitions`: Basic function definitions working -- ✅ `10_standard_library`: Standard library working - -### ❌ Failing Tests (25/119 = 21%) - -#### Standard Library Failures (15/66): -- **Logical Operators**: 6 failures due to `and`, `or`, `xor` being parsed as function calls -- **Precision**: 2 failures (square root 1-digit difference, negative power parsing) -- **Type Checking**: 1 failure (less function type checking) - -#### JavaScript Compatibility Failures (22/27): -- **Infix Operators**: 15+ failures due to parser precedence system not being used (`a + b` vs `add a b`) -- **Missing Features**: Tables, advanced combinators, embedded functions -- **Function Body Issues**: ✅ Fixed - complex function bodies now work - -## Success Metrics - -### Current Status -- ✅ Basic functionality: 26/26 tests PASS (100%) -- ✅ Standard library: 51/66 tests PASS (77%) -- ✅ Multiple statements: Fully working -- ✅ Higher-order functions: Fully working -- ✅ IO operations: Fully working -- ✅ Pattern matching: Fully working -- ✅ Function definitions: All cases working -- ✅ Function references: `@` operator working -- ✅ Error handling: Type checking implemented -- 🔧 Infix operators: **PARSER PRECEDENCE SYSTEM EXISTS BUT NOT USED** (blocks 15+ JS tests) -- ❌ Tables: Not implemented -- ❌ Advanced combinators: Not implemented - -### Target Status (End of Week 1) -- ✅ All basic functionality: 26/26 tests PASS (100%) -- ✅ Standard library: 66/66 tests PASS (100%) -- ✅ Function definitions: All cases working -- ✅ Infix operators: Full implementation (arithmetic, logical, comparison) -- ✅ Tables: Basic implementation -- ✅ Advanced combinators: Core implementation -- ✅ JavaScript compatibility: 20+/27 tests PASS -- ✅ Error handling: Comprehensive -- ✅ Memory management: Leak-free - -## Quick Start Commands - -### Build and Test -```bash -# Build with debug info -make debug - -# Test basic functionality (all working ✅) -./bin/baba-yaga '5 + 3;' # Should output: 8 -./bin/baba-yaga '10 - 3;' # Should output: 7 -./bin/baba-yaga '6 * 7;' # Should output: 42 -./bin/baba-yaga 'x : 42; x;' # Should output: 42 -./bin/baba-yaga 'add 5 3;' # Should output: 8 -./bin/baba-yaga '@multiply 2 3;' # Should output: 6 -./bin/baba-yaga 'add 5 @multiply 3 4;' # Should output: 17 - -# Multiple statements now working ✅ -./bin/baba-yaga 'x : 10; y : 20; add x y;' # ✅ Executes all statements, returns 30 - -# Run test suite -./run_tests.sh -./test_stdlib.sh - -# Check for memory leaks -valgrind --leak-check=full ./bin/baba-yaga '5 + 3;' -``` - -## Risk Assessment - -### High Risk -- **Memory Leaks**: Complex memory management in C -- **Mitigation**: Comprehensive testing with valgrind - -### Medium Risk -- **Performance Issues**: Can optimize after functionality complete -- **Cross-Platform Issues**: Test on multiple platforms - -### Low Risk -- **Complex Nested Function References**: Known limitation, not blocking -- **Multiple Statement Parsing**: ✅ Completed successfully - -## 🔍 CRITICAL DISCOVERY: Parser Precedence System Exists But Not Used - -### The Real Problem -After deep analysis, we discovered that **the infix operator parsing system is already fully implemented** but not being used. The parser has a complete operator precedence chain: - -``` -parser_parse_logical() → parser_parse_comparison() → parser_parse_additive() → -parser_parse_multiplicative() → parser_parse_power() → parser_parse_primary() -``` - -### The Root Cause -The main `parser_parse_expression()` function calls `parser_parse_application()` instead of `parser_parse_logical()`. This means: - -- ✅ All operator tokens are already in the lexer -- ✅ All operator precedence functions are already implemented -- ✅ All binary operation evaluation is already in the interpreter -- ❌ **But the main expression parser never calls the precedence system** - -### The Fix -**One line change** in `src/parser.c` line 1342: -```c -// Change from: -return parser_parse_application(parser); -// To: -return parser_parse_logical(parser); -``` - -### Expected Impact -This simple change should immediately: -- ✅ Unblock 15+ JavaScript compatibility tests -- ✅ Enable all infix operators: `a + b`, `a and b`, `a = b`, etc. -- ✅ Support operator precedence: `a + b * c` → `a + (b * c)` -- ✅ Support function references with infix: `@(a + b)` - -## Conclusion - -The Baba Yaga C implementation is in excellent shape with 76% of functionality working correctly. Major language features including pattern matching, function definitions, and function references are fully implemented and working. The critical blocker of multiple statement parsing has been resolved, unlocking real-world usage. - -### Key Achievements -- ✅ **Pattern Matching**: Complete `when` expression support with wildcard patterns -- ✅ **Function Definitions**: User-defined functions with parameter binding -- ✅ **Function References**: `@` operator for both `@function` and `@(expression)` syntax -- ✅ **Multiple Statements**: Semicolon-separated statement sequences -- ✅ **Core Language**: All basic operations and standard library functions working - -### Remaining Work -- 🔧 **Function Body Debugging**: Fix function calls within function bodies returning `nil` -- 📊 **Tables**: Implement table data structures and operations -- 🔄 **Advanced Combinators**: Implement each combinator, via operator, etc. -- 🎯 **JavaScript Compatibility**: Address syntax differences and missing features +# Baba Yaga C Implementation - Focused Roadmap + +## Current Status +- ✅ **Core Language**: Complete and stable (24/27 tests passing) +- ✅ **Table Pattern Matching**: Fixed and working +- ✅ **When Expressions**: Fixed and working +- ✅ **Computed Table Keys**: Fixed and working (Task 1.1 complete) +- ✅ **Memory Issues**: Fixed - reverted partial application implementation +- ❌ **2 Remaining Issues**: Partial application, pattern matching memory + +## Implementation Plan + +### **Phase 1: Parser Extensions (High Impact)** + +#### **Task 1.1: Computed Table Keys** (Test 15) ✅ **COMPLETE** +**Issue**: `{(1 + 1): "two"}` not supported +**Solution**: Extended table key parsing with expression support +**Implementation**: Added `TOKEN_LPAREN` detection and expression parsing logic +**Result**: Test 15 now passes, 25/27 tests passing + +#### **Task 1.2: Multi-value Pattern Expressions** (Test 22) ✅ **COMPLETE** +**Issue**: `when (x % 2) (y % 2) is` not supported +**Current**: Multi-value pattern expressions working correctly in parser +**Status**: Core functionality implemented - test file has minor syntax issue + +#### **Task 1.3: Pattern Matching Memory** (Integration Test 02) 🔄 **IN PROGRESS** +**Issue**: Segmentation fault in complex pattern matching +**Current**: Memory corruption in pattern matching +**Status**: Need to add memory debugging and fix recursion + + + +### **Phase 2: Runtime Fixes (Medium Impact)** + +#### **Task 2.1: Table Namespace Debugging** (Test 17) ✅ **COMPLETE** +**Issue**: `Error: Execution failed` in table operations +**Current**: Basic `map`, `filter`, `reduce` functions now work correctly with operator lookup +**Status**: Core functionality implemented - operator scope access fixed + +**Root Cause Analysis**: +- ✅ `t.*` namespace functions (t.map, t.filter, t.reduce, t.set, t.delete, t.merge, t.length, t.has, t.get) are working correctly +- ✅ Basic `map`, `filter`, `reduce` functions now work correctly with operator lookup +- ✅ `each` function works but has arity issues +- ❌ Test still fails due to partial application and arity handling issues + +**Solution Implemented**: +1. **Fixed Scope Access**: Updated stdlib function signatures to accept `Scope*` parameter +2. **Updated Function Calls**: Modified `baba_yaga_function_call` to pass current scope to user functions +3. **Updated Function Registration**: Changed function pointer types to support scope parameter +4. **Verified Core Functionality**: Basic higher-order functions now work with operators + +**Current Status**: +- ✅ **Core Bug Fixed**: Operator lookup in higher-order functions works correctly +- ✅ **Basic Functions Working**: `map`, `filter`, `reduce` with operators now functional +- ❌ **Test 17 Still Fails**: Due to partial application and arity issues (see Task 2.3) + +#### **Task 2.2: Pattern Matching Memory** (Integration Test 02) +**Issue**: Segmentation fault in complex patterns +**Current**: Memory corruption in pattern matching +**Fix**: Add memory debugging and fix recursion + +#### **Task 2.3: Partial Application Support** (Test 17) 🔄 **IN PROGRESS** +**Issue**: Test 17 fails with partial application and arity errors +**Current**: Core higher-order functions work, but partial application not supported +**Status**: Need to implement minimal partial application support (reverted due to memory issues) + +**Root Cause Analysis**: +- ✅ **Core Functions Working**: `map`, `filter`, `reduce` with operators now functional +- ❌ **Partial Application**: Function calls with fewer arguments than required fail +- ❌ **Arity Issues**: `each` function expects 3 args but receives 2 in some cases +- ❌ **Variable Scope**: Some variables like `partial_result`, `scalar_2`, etc. undefined + +**Error Messages from Test 17**: +- "each: expected 3 arguments, got 2" +- "Undefined variable: partial_result", "scalar_2", "add_to_ten" +- "Cannot call non-function value" +- "equals: arguments must be of the same type" + +**Implementation Plan**: +1. **Implement Partial Application**: When function called with fewer args than required, return new function +2. **Fix Arity Validation**: Ensure `each` function handles variable argument counts correctly +3. **Debug Variable Scope**: Identify why certain variables are undefined in test context +4. **Test Partial Application**: Verify partial functions work with remaining arguments + +**Technical Details**: +- **Location**: `src/function.c` - `baba_yaga_function_call` function +- **Current Behavior**: Returns `VAL_NIL` when insufficient arguments +- **Required Behavior**: Return new function with bound arguments +- **Reference**: Use `stdlib_compose` as template for function composition -The implementation follows the same architecture as the JavaScript version, ensuring consistency and maintainability. The C version provides better performance and memory efficiency while maintaining the same language semantics. +**Implementation Steps**: +1. Add memory debugging to `interpreter_evaluate_when_expression` +2. Check for infinite recursion in pattern matching +3. Fix memory allocation/deallocation in pattern evaluation +4. Test with complex pattern matching scenarios -**Next Action**: Implement infix operators (arithmetic, logical, comparison) to unblock 15+ JavaScript compatibility tests. +### **Phase 3: Validation** +- Re-run comprehensive test suite +- Target: 27/27 tests passing +- Verify no regressions -**Estimated completion for full implementation**: 1 week remaining. +## Technical Notes -## Immediate Next Steps for New Team Members +### **Parser Architecture** +- Table parsing: `parser_parse_primary` → `TOKEN_LBRACE` case +- Pattern parsing: `parser_parse_when_pattern` → multi-parameter detection +- Both need expression support in parentheses -### 1. Fix Infix Operator Parsing (CRITICAL - 1-2 hours) 🔴 **BLOCKING** -**Problem**: JavaScript tests use infix operators (`a + b`) but C implementation fails to parse them +### **Standard Library** +- `t.*` functions: Already implemented in `stdlib.c` (lines ~815-1183) ✅ **WORKING** +- Functions: `t.map`, `t.filter`, `t.reduce`, `t.set`, `t.delete`, `t.merge`, `t.length`, `t.has`, `t.get` +- Basic functions: `map`, `filter`, `reduce` in `stdlib.c` (lines ~559-640) ❌ **PLACEHOLDERS** +- Issue: Basic higher-order functions need full implementation -**Root Cause Discovered**: Parser precedence system exists but main expression parser calls wrong function +### **Memory Management** +- Pattern matching: Uses recursion for nested patterns +- Potential: Stack overflow or memory corruption +- Solution: Add bounds checking and memory debugging -**Implementation Steps**: -1. **Fix main expression parser** (1 line change): - ```c - // In src/parser.c line 1342, change: - return parser_parse_application(parser); - // To: - return parser_parse_logical(parser); - ``` -2. **Test infix operators**: `a + b`, `a and b`, `a = b`, `@(a + b)` -3. **Verify precedence**: `a + b * c` should parse as `a + (b * c)` +## Next Action +**Continue with Task 1.3** (Pattern Matching Memory) - fix segmentation fault in complex pattern matching. -**Files to Modify**: -- `src/parser.c`: Line 1342 (one line change) +## Implementation Guide -**Expected Result**: 15+ JavaScript compatibility tests should immediately pass +### **Task 2.1: Basic Higher-Order Functions Implementation** ✅ **COMPLETE** -### 2. Implement Tables (MEDIUM - 2-3 days) -**Problem**: Table literals and operations not implemented +#### **Function 1: `stdlib_map` Implementation** +**Location**: `src/stdlib.c` lines ~559-580 +**Current**: Returns original table (placeholder) +**Required**: Apply function to each value in table **Implementation Steps**: -1. Implement table literal parsing in `src/parser.c` -2. Add table operations to `src/table.c` -3. Update `src/stdlib.c` with table functions (`keys`, `values`, `size`) -4. Test with: `data : {a: 1, b: 2}; data.a` +1. Get all keys from input table using `baba_yaga_table_get_keys` +2. Create new result table using `baba_yaga_value_table` +3. For each key: + - Get value using `baba_yaga_table_get_by_key` + - Call function with value using `baba_yaga_function_call` + - Add result to new table using `baba_yaga_table_set` +4. Return new table -**Files to Modify**: -- `src/parser.c`: Add `NODE_TABLE` parsing -- `src/table.c`: Implement table operations -- `src/stdlib.c`: Add table utility functions +**Reference**: Use `stdlib_t_map` (lines ~815-866) as template - it's already implemented correctly -### 3. Implement Advanced Combinators (MEDIUM - 2-3 days) -**Problem**: Each combinator, via operator not implemented +#### **Function 2: `stdlib_filter` Implementation** +**Location**: `src/stdlib.c` lines ~584-610 +**Current**: Returns original table (placeholder) +**Required**: Keep only values that satisfy predicate **Implementation Steps**: -1. Add `each` combinator to `src/stdlib.c` -2. Add `via` operator support -3. Test with: `each add [1, 2, 3]` and `via add 5` +1. Get all keys from input table using `baba_yaga_table_get_keys` +2. Create new result table using `baba_yaga_value_table` +3. For each key: + - Get value using `baba_yaga_table_get_by_key` + - Call predicate function with value using `baba_yaga_function_call` + - If predicate returns truthy value, add original value to new table +4. Return new table -**Files to Modify**: -- `src/stdlib.c`: Add combinator implementations -- `src/parser.c`: Add combinator parsing if needed +**Reference**: Use `stdlib_t_filter` (lines ~867-923) as template - it's already implemented correctly -### 4. Fix Standard Library Issues (LOW - 1 day) -**Problem**: 6 standard library tests failing +#### **Function 3: `stdlib_reduce` Implementation** +**Location**: `src/stdlib.c` lines ~609-640 +**Current**: Returns initial value (placeholder) +**Required**: Combine all values with function **Implementation Steps**: -1. Add type checking to `equals`, `and`, `not` functions -2. Fix floating point precision issues -3. Run `./test_stdlib.sh` to verify fixes - -**Files to Modify**: -- `src/stdlib.c`: Add type validation and fix precision - -### Getting Started Commands -```bash -# Build and test current state -make debug -./run_comprehensive_tests.sh - -# Debug function body issue -./bin/baba-yaga 'f : x -> add x 1; f 41;' - -# Test pattern matching (working) -./bin/baba-yaga 'when 42 is 42 then "yes" _ then "no";' - -# Test function references (working) -./bin/baba-yaga '@(add 3 4);' -``` \ No newline at end of file +1. Start with initial value as accumulator +2. Get all keys from input table using `baba_yaga_table_get_keys` +3. For each key: + - Get value using `baba_yaga_table_get_by_key` + - Call function with accumulator and value using `baba_yaga_function_call` + - Update accumulator with result +4. Return final accumulator value + +**Reference**: Use `stdlib_t_reduce` (lines ~924-976) as template - it's already implemented correctly + +#### **Testing Strategy**: +1. **Unit Tests**: Create simple tests for each function individually +2. **Integration Test**: Run Test 17 to verify all functions work together +3. **Regression Test**: Verify `t.*` functions still work correctly +4. **Target**: Test 17 should pass, moving from 25/27 to 26/27 tests passing + +### **Task 2.3: Partial Application Support Implementation** 🔄 **IN PROGRESS** + +#### **Problem Analysis** +The current function call mechanism returns `VAL_NIL` when a function is called with fewer arguments than required. Test 17 expects partial application behavior where: +- `add_to_ten : add 10;` should create a function that adds 10 to its argument +- `each add_to_ten numbers` should work with the partially applied function + +#### **Implementation Steps** +1. **Modify `baba_yaga_function_call`** in `src/function.c`: + - When `arg_count < func_value->required_params`, create a new function + - Bind the provided arguments to the new function + - Return the new function instead of `VAL_NIL` + +2. **Create Partial Function Structure**: + - Store original function and bound arguments + - When partial function is called, combine bound args with new args + - Call original function with complete argument set + +3. **Update Function Value Structure**: + - Add support for partial functions in `FunctionValue` + - Handle partial function cleanup in memory management + +#### **Reference Implementation** +Use `stdlib_compose` as a template for function composition and partial application patterns. + +#### **Testing Strategy** +1. **Unit Test**: Create simple partial application test +2. **Integration Test**: Verify Test 17 passes with partial application +3. **Regression Test**: Ensure existing functions still work correctly \ No newline at end of file |