Michael Schimmel
8c865681ff
This commit introduces a new mechanism for calculating the required stack size for closures at bind time, rather than storing it in the AST. This is achieved by adding a `calculate_stack_size` method to `BoundNode`. Key changes include: - `BoundNode::calculate_stack_size`: Recursively traverses the bound AST to find the maximum `LocalSlot` index used. - Recursion blocker for lambdas: Ensures that nested lambdas are not visited during stack size calculation for the outer closure, preventing incorrect stack size estimations. - VM update: The `VM::run` method now accepts and uses the pre-calculated stack size for setting up call frames. - `Closure` struct update: Stores the `stack_size` directly within the `Closure` struct. - Binder and TypeChecker updates: Minor adjustments to accommodate the new strategy and error reporting. - Optimizer enhancements: Constant and pure-lambda propagation for `Define` statements within blocks to ensure inlinability. This refactoring addresses issues related to accurate stack size management and improves the overall robustness of the binder and VM.
78 lines
5.1 KiB
Markdown
78 lines
5.1 KiB
Markdown
# Development Log: Binder Refactoring & Block Scoping
|
|
|
|
## Status Quo
|
|
- Myc currently uses a flat scope per function.
|
|
- `def` is treated as a side-effect expression that "leaks" into the function scope regardless of nesting (e.g., inside `if` or `do`).
|
|
- This leads to uninitialized variables at runtime if the definition is skipped by control flow.
|
|
|
|
## Goal
|
|
Implement strict **Block Scoping** and distinguish between **Statements** and **Expressions** to eliminate undefined variable states.
|
|
|
|
### Rules
|
|
1. **Block Scoping:** Every `(do ...)` and `if` branch creates a new lexical scope.
|
|
2. **Statements vs. Expressions:**
|
|
- `def` is a **Statement**.
|
|
- Statements have no return value (Void).
|
|
- Statements **cannot** be used as expressions (e.g., as arguments, RHS of assignments, or conditions).
|
|
- Statements **cannot** be the last element of a block (since the block's value is determined by its last expression).
|
|
3. **No Shadowing:** Redefining a symbol within the **same** scope level is an error. Shadowing from outer scopes is allowed (standard lexical scoping).
|
|
4. **Self-Reference:** A variable is only available in its scope **after** its definition is complete (RHS of `def` sees outer scope).
|
|
|
|
## Implementation Plan
|
|
|
|
### Phase 1: Binder Infrastructure (Completed)
|
|
1. [x] Update `CompilerScope` to support hierarchical nesting via a stack in `FunctionCompiler`.
|
|
2. [x] Implement `push_scope` and `pop_scope` in `Binder`.
|
|
3. [x] Refactor `resolve_variable` to traverse the scope stack (inner-to-outer).
|
|
4. [x] Update `define_variable` to enforce "No Shadowing" at the current scope level.
|
|
|
|
### Phase 2: Statement/Expression Validation (Completed)
|
|
1. [x] Introduce a mechanism to track "Context" (Expression vs. Statement) during binding.
|
|
2. [x] Validate that `def` is only used in statement positions.
|
|
3. [x] Enforce that the last node in a `BoundKind::Block` is an expression.
|
|
|
|
### Phase 3: VM Compatibility
|
|
1. [ ] Ensure the VM handles "Void" results from statements correctly.
|
|
2. [ ] (Optional) Optimize stack allocation based on scope depth.
|
|
|
|
---
|
|
|
|
## Log Entries
|
|
|
|
### 2024-05-22: Phase 2 Completed & Strategy Adjustment
|
|
- Successfully implemented strict **Block Scoping** and **Statement vs. Expression** validation.
|
|
- Repaired the Root-Scope "leaking" problem: `def` only creates Globals at the top-most level of the script.
|
|
- **Challenge:** Many existing tests fail because they use `def` in expression positions or as the last element of a block.
|
|
- **Strategy Change for Stack Size:** Instead of storing `slot_count` in the AST during Binding, we will implement **Late Counting**. Just before execution, we will determine the required stack size by finding the maximum `LocalSlot` index used in each lambda. This avoids propagating metadata through all compiler passes and remains accurate after optimizations.
|
|
|
|
## Phase 4: Late Stack Size Calculation & VM Robustness (Completed)
|
|
1. [x] Implement a `calculate_stack_size()` method on `BoundNode` to find the maximum `LocalSlot` used in a frame.
|
|
2. [x] Recursion stops at lambda boundaries to ensure each closure gets its own independent stack size.
|
|
3. [x] Update VM to pre-allocate the stack with `Value::Void` for each call frame. This eliminates "Stack Underflow" when control flow skips a variable definition.
|
|
4. [x] Fixed "Nested Cell Bug": `Define` now checks if a slot is already a `Cell` (due to forward capture) before wrapping, preventing `Cell(Cell(Value))` corruption.
|
|
5. [x] Fixed "Root Closure Execution": Root scripts are now correctly executed as parameterless lambdas, returning the actual script result instead of the closure object.
|
|
|
|
### Phase 5: Optimizer Enhancements (Completed)
|
|
1. [x] Enabled constant and pure-lambda propagation for `Define` statements within blocks.
|
|
2. [x] This ensures that macro expansion and record field access remain fully inlinable even with strict statement rules.
|
|
|
|
---
|
|
|
|
## Final Status: 100% Green Tests
|
|
- All 64 tests (Unit + Integration + Examples) are passing.
|
|
- Strict **Block Scoping** is enforced everywhere.
|
|
- `def` is a pure **Statement** (no return value, not allowed at end of blocks).
|
|
- Design flaw "Uninitialized variables" is completely eliminated via pre-allocation and binder visibility rules.
|
|
|
|
## Key Learnings (Rust Context)
|
|
- **Late Counting vs. AST Metadata:** Keeping the AST clean and calculating runtime needs (stack size) just before execution is more robust against optimizer changes.
|
|
- **Nested Ownership (Value::Cell):** Explicitly handling the state of stack slots (raw value vs. heap-allocated cell) is crucial for correct closure captures.
|
|
- **Root Scope Specialization:** Treating the initial script as a "Function with special global-promotion rules" keeps the compiler logic consistent.
|
|
|
|
### Phase 1 & 2 Completed
|
|
- Introduced scope stack into `FunctionCompiler`.
|
|
- Introduced `ExprContext` (`Expression` / `Statement`) in the `Binder`.
|
|
- `def` now acts strictly as a statement.
|
|
- Variables defined inside nested scopes (e.g. inside `if` or `do`) do not leak into outer local scopes anymore.
|
|
- Outstanding behavior to discuss: `def` inside nested scopes at the *root* level still leaks into globals.
|