uni_core/
evaluator.rs

1// This module implements the AST-walking evaluator for Uni
2//
3// UNI EXECUTION MODEL (detailed):
4// 1. Numbers, strings, lists: Push themselves onto the stack (they are data)
5// 2. Atoms: Look up in dictionary and execute the definition
6// 3. Quoted atoms: Already parsed as (quote atom), quote builtin handles them
7// 4. Lists are data by default, use 'exec' builtin to execute them
8//
9// RUST LEARNING NOTES:
10// - This demonstrates recursive function calls and pattern matching
11// - We use Result<(), RuntimeError> to handle execution errors
12// - Mutable references (&mut) allow us to modify the interpreter state
13// - The ? operator propagates errors up the call stack automatically
14
15use crate::interpreter::Interpreter;
16use crate::value::{RuntimeError, Value};
17use crate::compat::{Rc, Vec, ToString};
18
19#[cfg(not(target_os = "none"))]
20use std::collections::HashMap;
21
22#[cfg(target_os = "none")]
23use alloc::collections::BTreeMap as HashMap;
24
25// RUST CONCEPT: Continuation-based evaluation for tail-call optimization
26// Instead of using recursion, we use an explicit continuation stack
27// This enables proper tail-call optimization and prevents stack overflow
28#[derive(Debug, Clone)]
29enum Continuation {
30    // Execute a single value (push data or execute atom)
31    Value(Value),
32
33    // Execute a list of values sequentially with index tracking
34    // When index == items.len()-1, we can do tail-call optimization
35    List {
36        items: Vec<Value>,
37        index: usize,
38    },
39
40    // Execute an if statement (condition already evaluated)
41    If {
42        condition_result: bool,
43        true_branch: Value,
44        false_branch: Value,
45    },
46
47    // Execute an exec'd expression
48    Exec(Value),
49
50    // Execute a defined word's body
51    Definition(Value),
52
53    // Pop a local frame when this continuation is reached
54    // Used to clean up local variables after quotation/definition execution
55    PopLocalFrame,
56}
57
58// RUST CONCEPT: Continuation-based execution loop
59// This replaces recursion with an explicit continuation stack for tail-call optimization
60pub fn execute_with_continuations(
61    initial_value: &Value,
62    interp: &mut Interpreter,
63) -> Result<(), RuntimeError> {
64    let mut continuation_stack: Vec<Continuation> = Vec::new();
65    continuation_stack.push(Continuation::Value(initial_value.clone()));
66
67    while let Some(continuation) = continuation_stack.pop() {
68        match continuation {
69            Continuation::Value(value) => {
70                execute_value_direct(&value, interp, &mut continuation_stack)?;
71            }
72
73            Continuation::List { items, index } => {
74                if index >= items.len() {
75                    continue; // Empty list or finished
76                }
77
78                let item = &items[index];
79                let is_tail_call = index == items.len() - 1;
80
81                if is_tail_call {
82                    // TAIL-CALL OPTIMIZATION: Don't push continuation for last item
83                    // This reuses the current "stack frame" enabling proper TCO
84                    continuation_stack.push(Continuation::Value(item.clone()));
85                } else {
86                    // Push continuation for next item, then execute current
87                    continuation_stack.push(Continuation::List {
88                        items: items.clone(),
89                        index: index + 1,
90                    });
91                    continuation_stack.push(Continuation::Value(item.clone()));
92                }
93            }
94
95            Continuation::If {
96                condition_result,
97                true_branch,
98                false_branch,
99            } => {
100                let branch = if condition_result {
101                    true_branch
102                } else {
103                    false_branch
104                };
105                // TAIL-CALL OPTIMIZATION: Execute branch directly without adding continuation
106                match &branch {
107                    Value::Pair(_, _) | Value::Nil => {
108                        let items = list_to_vec(&branch)?;
109                        continuation_stack.push(Continuation::List { items, index: 0 });
110                    }
111                    _ => {
112                        continuation_stack.push(Continuation::Value(branch));
113                    }
114                }
115            }
116
117            Continuation::Exec(value) => {
118                // Convert list to continuation or execute single value directly
119                match &value {
120                    Value::Pair(_, _) => {
121                        // Push local frame for quotation execution
122                        interp.local_frames.push(HashMap::new());
123                        // Schedule frame cleanup after execution
124                        continuation_stack.push(Continuation::PopLocalFrame);
125                        // Execute the list
126                        let items = list_to_vec(&value)?;
127                        continuation_stack.push(Continuation::List { items, index: 0 });
128                    }
129                    Value::Nil => {
130                        // Empty list - do nothing (no frame needed)
131                    }
132                    _ => {
133                        // Single value - execute directly (tail-call optimized, no frame needed)
134                        continuation_stack.push(Continuation::Value(value));
135                    }
136                }
137            }
138
139            Continuation::Definition(definition) => {
140                match &definition {
141                    Value::Pair(_, _) | Value::Nil => {
142                        // Push local frame for definition execution
143                        interp.local_frames.push(HashMap::new());
144                        // Schedule frame cleanup after execution
145                        continuation_stack.push(Continuation::PopLocalFrame);
146                        // Execute list as code (tail-call optimized)
147                        let items = list_to_vec(&definition)?;
148                        continuation_stack.push(Continuation::List { items, index: 0 });
149                    }
150                    _ => {
151                        // Execute single value directly (tail-call optimized, no frame needed for single values)
152                        continuation_stack.push(Continuation::Value(definition));
153                    }
154                }
155            }
156
157            Continuation::PopLocalFrame => {
158                // Pop the local frame to clean up local variables
159                if interp.local_frames.is_empty() {
160                    return Err(RuntimeError::TypeError(
161                        "PopLocalFrame: no local frame to pop (internal error)".to_string(),
162                    ));
163                }
164                interp.local_frames.pop();
165            }
166        }
167    }
168
169    Ok(())
170}
171
172// RUST CONCEPT: Helper function to execute a value directly and manage continuations
173// This is where atoms are looked up and special forms are handled
174fn execute_value_direct(
175    value: &Value,
176    interp: &mut Interpreter,
177    continuation_stack: &mut Vec<Continuation>,
178) -> Result<(), RuntimeError> {
179    match value {
180        // RUST CONCEPT: Simple values just push themselves onto the stack
181        Value::Number(n) => {
182            interp.push(Value::Number(*n));
183            Ok(())
184        }
185        // RUST CONCEPT: New number types also push themselves
186        Value::Int32(i) => {
187            interp.push(Value::Int32(*i));
188            Ok(())
189        }
190        Value::Integer(i) => {
191            interp.push(Value::Integer(i.clone()));
192            Ok(())
193        }
194        Value::Rational(r) => {
195            interp.push(Value::Rational(r.clone()));
196            Ok(())
197        }
198        #[cfg(feature = "complex_numbers")]
199        Value::Complex(c) => {
200            interp.push(Value::Complex(*c));
201            Ok(())
202        }
203        #[cfg(feature = "complex_numbers")]
204        Value::GaussianInt(re, im) => {
205            interp.push(Value::GaussianInt(re.clone(), im.clone()));
206            Ok(())
207        }
208        Value::String(s) => {
209            interp.push(Value::String(s.clone()));
210            Ok(())
211        }
212        Value::Boolean(b) => {
213            interp.push(Value::Boolean(*b));
214            Ok(())
215        }
216        Value::Null => {
217            interp.push(Value::Null);
218            Ok(())
219        }
220        Value::Array(array) => {
221            interp.push(Value::Array(array.clone()));
222            Ok(())
223        }
224        Value::Variable(var) => {
225            interp.push(Value::Variable(var.clone()));
226            Ok(())
227        }
228        Value::Pair(_, _) | Value::Nil => {
229            interp.push(value.clone());
230            Ok(())
231        }
232        Value::QuotedAtom(atom_name) => {
233            interp.push(Value::Atom(atom_name.clone()));
234            Ok(())
235        }
236        Value::Builtin(func) => func(interp),
237        Value::Atom(atom_name) => {
238            execute_atom_with_continuations(atom_name, interp, continuation_stack)
239        }
240        // RUST CONCEPT: Records and record types push themselves
241        Value::Record { .. } | Value::RecordType { .. } => {
242            interp.push(value.clone());
243            Ok(())
244        }
245        // RUST CONCEPT: I16 buffers push themselves (they are data)
246        Value::I16Buffer(_) => {
247            interp.push(value.clone());
248            Ok(())
249        }
250    }
251}
252
253// RUST CONCEPT: Convert list structure to vector for sequential processing
254fn list_to_vec(list: &Value) -> Result<Vec<Value>, RuntimeError> {
255    let mut current = list.clone();
256    let mut items = Vec::new();
257
258    loop {
259        match current {
260            Value::Pair(car, cdr) => {
261                items.push((*car).clone());
262                current = (*cdr).clone();
263            }
264            Value::Nil => break,
265            _ => {
266                // Single value (improper list) - just return it as single item
267                items.push(current);
268                break;
269            }
270        }
271    }
272
273    Ok(items)
274}
275
276// RUST CONCEPT: Atom execution with continuation support
277fn execute_atom_with_continuations(
278    atom_name: &Rc<str>,
279    interp: &mut Interpreter,
280    continuation_stack: &mut Vec<Continuation>,
281) -> Result<(), RuntimeError> {
282    // RUST CONCEPT: Special handling for exec, if, and quit
283    if &**atom_name == "exec" {
284        let value = interp.pop()?;
285        continuation_stack.push(Continuation::Exec(value));
286        return Ok(());
287    }
288
289    if &**atom_name == "if" {
290        let false_branch = interp.pop()?;
291        let true_branch = interp.pop()?;
292        let condition = interp.pop()?;
293
294        let condition_result = interp.is_truthy(&condition);
295        continuation_stack.push(Continuation::If {
296            condition_result,
297            true_branch,
298            false_branch,
299        });
300        return Ok(());
301    }
302
303    if &**atom_name == "quit" {
304        // Return special error to signal clean exit
305        return Err(RuntimeError::QuitRequested);
306    }
307
308    // RUST CONCEPT: Local frame lookup first, then dictionary lookup
309    // Check local frames from top (most recent) to bottom (oldest)
310    for frame in interp.local_frames.iter().rev() {
311        if let Some(value) = frame.get(atom_name) {
312            // Found in local frame - push the value directly (it's a constant)
313            interp.push(value.clone());
314            return Ok(());
315        }
316    }
317
318    // Not in local frames - try dictionary lookup
319    match interp.dictionary.get(atom_name) {
320        Some(entry) => {
321            let entry_copy = entry.clone();
322
323            if entry_copy.is_executable {
324                // Push definition execution continuation
325                continuation_stack.push(Continuation::Definition(entry_copy.value));
326            } else {
327                // Non-executable entry - just push as constant
328                interp.push(entry_copy.value);
329            }
330            Ok(())
331        }
332        None => Err(RuntimeError::UndefinedWord((**atom_name).to_string())),
333    }
334}
335
336// RUST CONCEPT: Public functions that other modules can use
337// This is the main entry point for executing Uni values
338// Now uses continuation-based execution for tail-call optimization
339pub fn execute(value: &Value, interp: &mut Interpreter) -> Result<(), RuntimeError> {
340    execute_with_continuations(value, interp)
341}
342
343// NOTE: Old execute_atom function removed - now using execute_atom_with_continuations
344
345// RUST CONCEPT: Top-level execution function
346// This parses and executes a string of Uni code
347pub fn execute_string(code: &str, interp: &mut Interpreter) -> Result<(), RuntimeError> {
348    // RUST CONCEPT: Module imports and error conversion
349    // We import parse from our parser module
350    use crate::parser::parse;
351
352    // RUST CONCEPT: Error propagation with ?
353    // parse() returns Result<Vec<Value>, ParseError>
354    // The ? converts ParseError to RuntimeError using our From implementation
355    let values = parse(code, interp)?;
356
357    // RUST CONCEPT: Iterators and error handling in loops
358    // We execute each top-level value in sequence
359    // If any execution fails, the ? will return that error immediately
360    for value in values {
361        execute(&value, interp)?;
362    }
363
364    Ok(())
365}
366
367// RUST CONCEPT: Conditional compilation for tests
368#[cfg(test)]
369mod tests {
370    use super::*;
371    // use crate::builtins::register_builtins;  // No longer needed
372
373    // RUST CONCEPT: Test helper function
374    // DRY principle - Don't Repeat Yourself
375    fn setup_interpreter() -> Interpreter {
376        // RUST CONCEPT: Automatic initialization
377        // Interpreter::new() now automatically loads builtins and prelude
378        Interpreter::new()
379    }
380
381    #[test]
382    fn test_execute_numbers() {
383        let mut interp = setup_interpreter();
384
385        // RUST CONCEPT: Testing basic functionality
386        let number = Value::Number(42.0);
387        execute(&number, &mut interp).unwrap();
388
389        // RUST CONCEPT: Verifying state changes
390        let result = interp.pop().unwrap();
391        assert!(matches!(result, Value::Number(n) if n == 42.0));
392    }
393
394    #[test]
395    fn test_execute_strings() {
396        let mut interp = setup_interpreter();
397
398        let string_val: Rc<str> = "hello world".into();
399        let string = Value::String(string_val);
400        execute(&string, &mut interp).unwrap();
401
402        let result = interp.pop().unwrap();
403        assert!(matches!(result, Value::String(s) if s.as_ref() == "hello world"));
404    }
405
406    #[test]
407    fn test_execute_lists_as_data() {
408        let mut interp = setup_interpreter();
409
410        // RUST CONCEPT: Testing that lists don't execute, just push themselves
411        let plus_atom = interp.intern_atom("+");
412        let list = interp.make_list(vec![
413            Value::Number(1.0),
414            Value::Number(2.0),
415            Value::Atom(plus_atom),
416        ]);
417
418        execute(&list, &mut interp).unwrap();
419
420        // Should have pushed the list as data, not executed it
421        let result = interp.pop().unwrap();
422        assert!(matches!(result, Value::Pair(_, _)));
423
424        // Stack should be empty (list didn't execute and push 3)
425        assert!(interp.pop().is_err());
426    }
427
428    #[test]
429    fn test_execute_builtin_functions() {
430        let mut interp = setup_interpreter();
431
432        // RUST CONCEPT: Testing builtin execution
433        // Set up stack for addition: 3 + 5
434        interp.push(Value::Number(3.0));
435        interp.push(Value::Number(5.0));
436
437        // Get the + builtin from dictionary and execute it
438        let plus_atom = interp.intern_atom("+");
439        execute(&Value::Atom(plus_atom), &mut interp).unwrap();
440
441        // Should have popped 3 and 5, pushed 8
442        let result = interp.pop().unwrap();
443        assert!(matches!(result, Value::Number(n) if n == 8.0));
444    }
445
446    #[test]
447    fn test_execute_undefined_atom() {
448        let mut interp = setup_interpreter();
449
450        // RUST CONCEPT: Testing error cases
451        let undefined_atom = interp.intern_atom("nonexistent");
452        let result = execute(&Value::Atom(undefined_atom), &mut interp);
453
454        assert!(result.is_err());
455        assert!(
456            matches!(result.unwrap_err(), RuntimeError::UndefinedWord(s) if s == "nonexistent")
457        );
458    }
459
460    #[test]
461    fn test_execute_string_simple() {
462        let mut interp = setup_interpreter();
463
464        // RUST CONCEPT: Testing integration between parser and evaluator
465        execute_string("42 3.14", &mut interp).unwrap();
466
467        // Should have two values on stack
468        let result1 = interp.pop().unwrap();
469        let result2 = interp.pop().unwrap();
470
471        assert!(matches!(result1, Value::Number(n) if n == 3.14));
472        assert!(matches!(result2, Value::Int32(42))); // Small integers use Int32
473    }
474
475    #[test]
476    fn test_execute_string_with_builtin() {
477        let mut interp = setup_interpreter();
478
479        // RUST CONCEPT: Testing complete execution flow
480        execute_string("5 3 +", &mut interp).unwrap();
481
482        // Should have executed: push 5, push 3, execute +
483        let result = interp.pop().unwrap();
484        assert!(matches!(result, Value::Int32(8))); // Small integers use Int32
485
486        // Stack should be empty
487        assert!(interp.pop().is_err());
488    }
489
490    // RUST CONCEPT: Tail-call optimization tests
491    // These tests demonstrate that the continuation-based evaluator
492    // provides proper tail-call optimization for recursive functions
493
494    #[test]
495    fn test_tail_recursive_factorial() {
496        let mut interp = setup_interpreter();
497
498        // Define simple tail-recursive countdown
499        execute_string(
500            "'count-down [dup 1 <= [drop 999] [1 - count-down] if] def",
501            &mut interp,
502        )
503        .unwrap();
504
505        // Test with small value
506        execute_string("5 count-down", &mut interp).unwrap();
507        let result = interp.pop().unwrap();
508        assert!(matches!(result, Value::Int32(999))); // Small integers use Int32
509    }
510
511    #[test]
512    fn test_deep_tail_recursion() {
513        let mut interp = setup_interpreter();
514
515        // Define a tail-recursive countdown that would overflow regular recursion
516        execute_string(
517            "'countdown [dup 0 <= [drop 42] [1 - countdown] if] def",
518            &mut interp,
519        )
520        .unwrap();
521
522        // Test with moderately deep recursion (this would cause stack overflow without TCO)
523        execute_string("1000 countdown", &mut interp).unwrap();
524        let result = interp.pop().unwrap();
525        assert!(matches!(result, Value::Int32(42))); // Small integers use Int32
526    }
527
528    #[test]
529    fn test_mutually_tail_recursive_functions() {
530        let mut interp = setup_interpreter();
531
532        // Define mutually recursive even/odd functions using available primitives
533        execute_string("'even [dup 0 = [drop true] [1 - odd] if] def", &mut interp).unwrap();
534        execute_string("'odd [dup 0 = [drop false] [1 - even] if] def", &mut interp).unwrap();
535
536        // Test even/odd with moderate numbers
537        execute_string("10 even", &mut interp).unwrap();
538        let result = interp.pop().unwrap();
539        assert!(matches!(result, Value::Boolean(true)));
540
541        execute_string("11 odd", &mut interp).unwrap();
542        let result = interp.pop().unwrap();
543        assert!(matches!(result, Value::Boolean(true)));
544    }
545
546    #[test]
547    fn test_tail_call_in_if_branches() {
548        let mut interp = setup_interpreter();
549
550        // Test that both branches of if are tail-call optimized
551        execute_string(
552            "'branch-test [dup 10 > [drop 99] [1 + branch-test] if] def",
553            &mut interp,
554        )
555        .unwrap();
556
557        execute_string("5 branch-test", &mut interp).unwrap();
558        let result = interp.pop().unwrap();
559        assert!(matches!(result, Value::Int32(99))); // Small integers use Int32
560    }
561
562    #[test]
563    fn test_execute_string_with_list() {
564        let mut interp = setup_interpreter();
565
566        // RUST CONCEPT: Testing that lists remain as data
567        execute_string("[1 2 +] 42", &mut interp).unwrap();
568
569        // Should have list and number on stack
570        let number = interp.pop().unwrap();
571        let list = interp.pop().unwrap();
572
573        assert!(matches!(number, Value::Int32(42))); // Small integers use Int32
574        assert!(matches!(list, Value::Pair(_, _)));
575    }
576
577    #[test]
578    fn test_execute_quoted_atoms() {
579        let mut interp = setup_interpreter();
580
581        // RUST CONCEPT: Testing quote behavior
582        // 'hello should parse as (quote hello) and quote should be a builtin that
583        // pushes the atom without executing it
584
585        // First we need to add a quote builtin for this test to work
586        // For now, let's test that quoted structure gets created correctly
587        let hello_atom = interp.intern_atom("hello");
588        let quote_atom = interp.intern_atom("quote");
589
590        let quoted_hello = Value::Pair(
591            Rc::new(Value::Atom(quote_atom)),
592            Rc::new(Value::Pair(
593                Rc::new(Value::Atom(hello_atom)),
594                Rc::new(Value::Nil),
595            )),
596        );
597
598        // This should push the quoted structure as data (since it's a list)
599        execute(&quoted_hello, &mut interp).unwrap();
600
601        let result = interp.pop().unwrap();
602        assert!(matches!(result, Value::Pair(_, _)));
603    }
604
605    #[test]
606    fn test_execute_string_parse_errors() {
607        let mut interp = setup_interpreter();
608
609        // RUST CONCEPT: Testing error propagation from parser
610        let result = execute_string("[1 2", &mut interp); // Unclosed bracket
611        assert!(result.is_err());
612
613        let result = execute_string("'[1 2]", &mut interp); // Invalid quote
614        assert!(result.is_err());
615    }
616}
uni_core/evaluator.rs

uni_core/
evaluator.rs
