# Ruchy Interpreter Architecture
**Version**: v0.10.0 - Revolutionary Development Tools Release
**Status**: Production-ready with formal verification support
## Overview
The Ruchy interpreter is a production-grade, resource-bounded evaluation engine optimized for low complexity and high performance. As of v0.10.0, the interpreter integrates with revolutionary development tools including formal verification and automatic BigO complexity analysis - features that don't exist in any other programming language.
## Architecture Components
### 1. Core Interpreter (`src/runtime/repl.rs`)
The heart of the interpreter is the `evaluate_expr` function, which recursively evaluates AST nodes with resource bounds:
```rust
fn evaluate_expr(&mut self, expr: &Expr, deadline: Instant, depth: usize) -> Result<Value>
```
**Key features:**
- **Timeout protection**: Every evaluation checks against a deadline
- **Stack depth limiting**: Prevents stack overflow from deep recursion
- **Memory tracking**: Monitors allocation and prevents OOM conditions
**Complexity Evolution:**
- v0.7.x: 209 cyclomatic complexity
- v0.8.0: 50 cyclomatic complexity (76% reduction)
### 2. Value System (`src/runtime/repl.rs`)
The `Value` enum represents all runtime values:
```rust
pub enum Value {
Int(i64),
Float(f64),
String(String),
Bool(bool),
Char(char),
List(Vec<Value>),
Tuple(Vec<Value>),
Function { name: String, params: Vec<String>, body: Box<Expr> },
Lambda { params: Vec<String>, body: Box<Expr> },
DataFrame { columns: Vec<DataFrameColumn> },
Object(HashMap<String, Value>),
Range { start: i64, end: i64, inclusive: bool },
EnumVariant { enum_name: String, variant_name: String, data: Option<Vec<Value>> },
Unit,
}
```
### 3. Display Formatting (`src/runtime/repl/display.rs`)
Display formatting has been extracted to a separate module for maintainability:
- **Before**: Single `fmt` function with 66 complexity
- **After**: Modular helpers, each under 30 complexity
- **Benefits**: Easier testing, better code organization, reduced cognitive load
### 4. Memory Management
The interpreter uses a `MemoryTracker` to enforce memory limits:
```rust
pub struct MemoryTracker {
allocated: AtomicUsize,
max_memory: usize,
}
```
**Features:**
- Per-evaluation reset
- Atomic operations for thread safety
- Immediate failure on limit exceeded
## Evaluation Flow
### 1. Expression Parsing
```
Input String → Parser → AST
```
### 2. Resource Initialization
```
Create deadline (timeout)
Reset memory tracker
Initialize depth counter
```
### 3. Recursive Evaluation
```
evaluate_expr(ast, deadline, depth)
├─ Check resource bounds
├─ Match expression type
├─ Evaluate subexpressions
└─ Return Value
```
### 4. Result Formatting
```
Value → Display trait → Formatted output
```
## Optimization Techniques
### 1. Complexity Reduction
**Method Extraction:**
- Split large functions into focused helpers
- Each helper has single responsibility
- Complexity distributed across modules
**Example:**
```rust
// Before (complexity: 66)
fn fmt(&self, f: &mut Formatter) -> Result {
// 66 branches of logic
}
// After (complexity: 15)
fn fmt(&self, f: &mut Formatter) -> Result {
match self {
Value::List(items) => Self::fmt_list(f, items),
Value::DataFrame(df) => Self::format_dataframe(f, df),
// ... simple delegations
}
}
```
### 2. O(n²) Algorithm Elimination
**Before:**
```rust
// O(n²) - checking contains for each item
for method in &self.string_methods {
if !completions.contains(method) {
completions.push(method.clone());
}
}
```
**After:**
```rust
// O(n) - using HashSet for deduplication
let mut seen = HashSet::new();
for method in &self.string_methods {
if seen.insert(method.clone()) {
completions.push(method.clone());
}
}
```
### 3. HashSet Lookups
**Before:**
```rust
// O(n) lookup in Vec
if self.keywords.contains(&identifier) { ... }
```
**After:**
```rust
// O(1) lookup in HashSet
if self.keywords_set.contains(&identifier) { ... }
```
## Supported Operations
### Arithmetic
- Binary: `+`, `-`, `*`, `/`, `%`
- Comparison: `==`, `!=`, `<`, `>`, `<=`, `>=`
- Logical: `&&`, `||`, `!`
- Bitwise: `&`, `|`, `^`, `<<`, `>>`
### Control Flow
- If/else expressions
- Match expressions with pattern matching
- For loops (return last value)
- While loops (return Unit)
- Loop with break/continue
### Data Structures
- Lists with methods: `map`, `filter`, `reduce`, `len`, `head`, `tail`
- Tuples (immutable, heterogeneous)
- Objects/Maps (HashMap<String, Value>)
- Ranges (inclusive and exclusive)
### Functions
- Named functions with type annotations
- Lambda expressions
- Closures with captured environment
- Higher-order functions
### Special Types
- Unit: () for side effects
## Error Handling
### Parse Errors
```rust
Failed to parse input
at line 2, column 5
expected '}', found 'EOF'
```
### Runtime Errors
```rust
Error: Division by zero
at line 3
in function 'calculate'
```
### Resource Errors
```rust
Error: Evaluation timeout exceeded (100ms)
Error: Maximum recursion depth 256 exceeded
Error: Memory limit exceeded (10MB)
```
## Performance Characteristics
### Time Complexity
- Expression evaluation: O(n) where n = AST nodes
- Variable lookup: O(1) HashMap access
- Function calls: O(m) where m = function body size
- Pattern matching: O(p) where p = number of patterns
### Space Complexity
- Stack depth: O(d) where d = max recursion depth
- Environment: O(v) where v = number of variables
- Value storage: O(s) where s = total value size
### Benchmarks (v0.8.0)
```
Parsing throughput: 50MB/s
Simple expressions: <1μs
Function calls: <10μs
Pattern matching: <5μs
List operations: O(n) as expected
```
## Testing Strategy
### Unit Tests
- Each evaluation method tested independently
- Edge cases for all value types
- Resource limit enforcement
### Property Tests
- Mathematical properties (commutativity, associativity)
- Type system invariants
- Memory safety guarantees
### Fuzz Tests
- Random input generation
- Crash resistance
- Memory leak detection
### Integration Tests
- Full REPL sessions
- Multi-line input handling
- Error recovery
## Future Optimizations
### Planned for v0.9.0
1. **Bytecode compilation**: Compile AST to bytecode for faster evaluation
2. **JIT compilation**: Hot path optimization using Cranelift
3. **Parallel evaluation**: Safe parallelism for independent expressions
4. **Incremental parsing**: Reuse AST fragments for REPL efficiency
### Research Areas
1. **Type specialization**: Monomorphize generic functions
2. **Escape analysis**: Stack allocate non-escaping values
3. **Constant folding**: Evaluate compile-time constants
4. **Dead code elimination**: Remove unreachable branches
## Code Quality Metrics
### Complexity Limits
- Maximum cyclomatic complexity: 50
- Maximum cognitive complexity: 15
- Maximum function length: 100 lines
- Maximum nesting depth: 4
### Coverage Requirements
- Line coverage: >80%
- Branch coverage: >75%
- Function coverage: 100%
### Performance Requirements
- No O(n²) algorithms
- Sub-millisecond response for simple expressions
- Memory usage proportional to input size
## v0.10.0 Revolutionary Tool Integration
The interpreter now supports groundbreaking development tools:
### Formal Verification Support
- AST nodes carry verification metadata
- Purity analysis during evaluation
- Termination proof generation for loops/recursion
- Contract checking at runtime
### Performance Analysis Integration
- Automatic complexity tracking during evaluation
- Loop iteration counting for BigO detection
- Recursive call depth monitoring
- Memory allocation tracking
### Tool Commands
```bash
# Verify interpreter behavior
ruchy provability src/runtime/repl.rs --verify
# Analyze interpreter performance
ruchy runtime src/runtime/repl.rs --bigo
# Check interpreter complexity
ruchy ast src/runtime/repl.rs --metrics
```
## Contributing
When modifying the interpreter:
1. **Maintain complexity budget**: Use `ruchy ast --metrics` to check complexity
2. **Verify correctness**: Run `ruchy provability --verify` on changes
3. **Check performance**: Use `ruchy runtime --bigo` to detect regressions
4. **Add tests**: Every new feature needs unit and integration tests
5. **Document changes**: Update this document for architectural changes
6. **Benchmark impact**: Run benchmarks before and after changes
7. **Follow Toyota Way**: Zero defects, stop the line for any regression
## Quality Gates (v0.10.0)
All interpreter changes must pass:
- Cyclomatic complexity < 50 per function
- Test coverage > 80%
- Zero clippy warnings (`make lint`)
- Formal verification pass (`ruchy provability`)
- No performance regression (`ruchy runtime --compare`)
## References
- [SPECIFICATION.md](./SPECIFICATION.md) - Language specification
- [CLAUDE.md](../CLAUDE.md) - Development protocol
- [Revolutionary Tools](./tools/README.md) - v0.10.0 tool documentation
- [repl/mod.rs](../src/runtime/repl/mod.rs) - REPL main module
- [repl/formatting.rs](../src/runtime/repl/formatting.rs) - Display formatting
