## Coverage Report

#### Created: 2025-09-08 21:26

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /home/noah/src/ruchy/src/transpiler/reference_interpreter.rs

    Line
    Count
    Source
    1
    //! Reference Interpreter - Ground Truth for Semantic Verification
    2
    //!
    3
    //! A minimal, unoptimized, obviously correct interpreter for the core language.
    4
    //! This serves as the oracle for differential testing against the transpiler.
    5
    //!
    6
    //! Design principles:
    7
    //! - Clarity over performance
    8
    //! - No optimizations whatsoever
    9
    //! - Under 1000 LOC
    10
    //! - Direct operational semantics
    11
    12
    #![allow(clippy::cast_possible_truncation)] // Reference interpreter prioritizes simplicity
    13
    #![allow(clippy::cast_sign_loss)] // Reference interpreter uses simple casts
    14
    #![allow(clippy::cast_possible_wrap)] // Reference interpreter uses simple casts
    15
    16
    use crate::transpiler::canonical_ast::{CoreExpr, CoreLiteral, DeBruijnIndex, PrimOp};
    17
    use std::rc::Rc;
    18
    19
    /// Runtime values
    20
    #[derive(Debug, Clone, PartialEq)]
    21
    pub enum Value {
    22
        Integer(i64),
    23
        Float(f64),
    24
        String(String),
    25
        Bool(bool),
    26
        Char(char),
    27
        Unit,
    28
        Nil,
    29
        /// Closure captures the body and environment at creation time
    30
        Closure {
    31
            body: Rc<CoreExpr>,
    32
            env: Environment,
    33
        },
    34
        /// Arrays are just vectors
    35
        Array(Vec<Value>),
    36
    }
    37
    38
    /// Environment for variable bindings
    39
    #[derive(Debug, Clone, PartialEq)]
    40
    pub struct Environment {
    41
        bindings: Vec<Value>,
    42
    }
    43
    44
    impl Default for Environment {
    45
    0
        fn default() -> Self {
    46
    0
            Self::new()
    47
    0
        }
    48
    }
    49
    50
    impl Environment {
    51
        #[must_use]
    52
    0
        pub fn new() -> Self {
    53
    0
            Self {
    54
    0
                bindings: Vec::new(),
    55
    0
            }
    56
    0
        }
    57
    58
    0
        pub fn push(&mut self, value: Value) {
    59
    0
            self.bindings.push(value);
    60
    0
        }
    61
    62
    0
        pub fn pop(&mut self) {
    63
    0
            self.bindings.pop();
    64
    0
        }
    65
    66
        #[must_use]
    67
    0
        pub fn lookup(&self, index: &DeBruijnIndex) -> Option<&Value> {
    68
            // De Bruijn indices count from the end
    69
    0
            let pos = self.bindings.len().checked_sub(index.0 + 1)?;
    70
    0
            self.bindings.get(pos)
    71
    0
        }
    72
    }
    73
    74
    /// Reference interpreter - deliberately simple and unoptimized
    75
    pub struct ReferenceInterpreter {
    76
        env: Environment,
    77
        trace: Vec<String>, // For debugging
    78
    }
    79
    80
    impl Default for ReferenceInterpreter {
    81
    0
        fn default() -> Self {
    82
    0
            Self::new()
    83
    0
        }
    84
    }
    85
    86
    impl ReferenceInterpreter {
    87
        #[must_use]
    88
    0
        pub fn new() -> Self {
    89
    0
            Self {
    90
    0
                env: Environment::new(),
    91
    0
                trace: Vec::new(),
    92
    0
            }
    93
    0
        }
    94
    95
        /// Evaluate an expression to a value
    96
        /// This is the core of the interpreter - direct operational semantics
    97
        /// # Errors
    98
        ///
    99
        /// Returns an error if the operation fails
    100
        /// # Errors
    101
        ///
    102
        /// Returns an error if the operation fails
    103
    0
        pub fn eval(&mut self, expr: &CoreExpr) -> Result<Value, String> {
    104
    0
            self.trace.push(format!("Evaluating: {expr:?}"));
    105
    106
    0
            match expr {
    107
    0
                CoreExpr::Var(idx) => self
    108
    0
                    .env
    109
    0
                    .lookup(idx)
    110
    0
                    .cloned()
    111
    0
                    .ok_or_else(|| format!("Unbound variable: {idx:?}")),
    112
    113
    0
                CoreExpr::Lambda { body, .. } => {
    114
                    // Create closure capturing current environment
    115
    0
                    Ok(Value::Closure {
    116
    0
                        body: Rc::new(body.as_ref().clone()),
    117
    0
                        env: self.env.clone(),
    118
    0
                    })
    119
                }
    120
    121
    0
                CoreExpr::App(func, arg) => {
    122
                    // Evaluate function
    123
    0
                    let func_val = self.eval(func)?;
    124
    125
                    // Evaluate argument (call-by-value)
    126
    0
                    let arg_val = self.eval(arg)?;
    127
    128
                    // Apply function to argument
    129
    0
                    match func_val {
    130
    0
                        Value::Closure { body, mut env } => {
    131
                            // Save current environment
    132
    0
                            let saved_env = self.env.clone();
    133
    134
                            // Set up closure environment with argument
    135
    0
                            env.push(arg_val);
    136
    0
                            self.env = env;
    137
    138
                            // Evaluate body
    139
    0
                            let result = self.eval(&body)?;
    140
    141
                            // Restore environment
    142
    0
                            self.env = saved_env;
    143
    144
    0
                            Ok(result)
    145
                        }
    146
    0
                        _ => Err(format!("Cannot apply non-function: {func_val:?}")),
    147
                    }
    148
                }
    149
    150
    0
                CoreExpr::Let { value, body, name } => {
    151
    0
                    self.trace.push(format!("Let binding: {name:?}"));
    152
    153
                    // Evaluate the value
    154
    0
                    let val = self.eval(value)?;
    155
    156
                    // Bind it in the environment
    157
    0
                    self.env.push(val);
    158
    159
                    // Evaluate the body
    160
    0
                    let result = self.eval(body)?;
    161
    162
                    // Pop the binding
    163
    0
                    self.env.pop();
    164
    165
    0
                    Ok(result)
    166
                }
    167
    168
    0
                CoreExpr::Literal(lit) => Ok(match lit {
    169
    0
                    CoreLiteral::Integer(i) => Value::Integer(*i),
    170
    0
                    CoreLiteral::Float(f) => Value::Float(*f),
    171
    0
                    CoreLiteral::String(s) => Value::String(s.clone()),
    172
    0
                    CoreLiteral::Bool(b) => Value::Bool(*b),
    173
    0
                    CoreLiteral::Char(c) => Value::Char(*c),
    174
    0
                    CoreLiteral::Unit => Value::Unit,
    175
                }),
    176
    177
    0
                CoreExpr::Prim(op, args) => self.eval_prim(op, args),
    178
            }
    179
    0
        }
    180
    181
        /// Evaluate primitive operations
    182
        #[allow(clippy::too_many_lines)] // Comprehensive primitive operations
    183
    0
        fn eval_prim(&mut self, op: &PrimOp, args: &[CoreExpr]) -> Result<Value, String> {
    184
            // Evaluate all arguments first (strict evaluation)
    185
    0
            let mut values = Vec::new();
    186
    0
            for arg in args {
    187
    0
                values.push(self.eval(arg)?);
    188
            }
    189
    190
    0
            match op {
    191
                // Arithmetic operations
    192
                PrimOp::Add => {
    193
    0
                    if values.len() != 2 {
    194
    0
                        return Err(format!("Add expects 2 arguments, got {}", values.len()));
    195
    0
                    }
    196
    0
                    match (&values[0], &values[1]) {
    197
    0
                        (Value::Integer(a), Value::Integer(b)) => Ok(Value::Integer(a + b)),
    198
    0
                        (Value::Float(a), Value::Float(b)) => Ok(Value::Float(a + b)),
    199
    0
                        (Value::String(a), Value::String(b)) => Ok(Value::String(format!("{a}{b}"))),
    200
    0
                        _ => Err(format!(
    201
    0
                            "Type error in addition: {:?} + {:?}",
    202
    0
                            values[0], values[1]
    203
    0
                        )),
    204
                    }
    205
                }
    206
    207
    0
                PrimOp::Sub => match (&values[0], &values[1]) {
    208
    0
                    (Value::Integer(a), Value::Integer(b)) => Ok(Value::Integer(a - b)),
    209
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Float(a - b)),
    210
    0
                    _ => Err("Type error in subtraction".to_string()),
    211
                },
    212
    213
    0
                PrimOp::Mul => match (&values[0], &values[1]) {
    214
    0
                    (Value::Integer(a), Value::Integer(b)) => Ok(Value::Integer(a * b)),
    215
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Float(a * b)),
    216
    0
                    _ => Err("Type error in multiplication".to_string()),
    217
                },
    218
    219
    0
                PrimOp::Div => match (&values[0], &values[1]) {
    220
    0
                    (Value::Integer(a), Value::Integer(b)) => {
    221
    0
                        if *b == 0 {
    222
    0
                            Err("Division by zero".to_string())
    223
                        } else {
    224
    0
                            Ok(Value::Integer(a / b))
    225
                        }
    226
                    }
    227
    0
                    (Value::Float(a), Value::Float(b)) => {
    228
    0
                        if *b == 0.0 {
    229
    0
                            Err("Division by zero".to_string())
    230
                        } else {
    231
    0
                            Ok(Value::Float(a / b))
    232
                        }
    233
                    }
    234
    0
                    _ => Err("Type error in division".to_string()),
    235
                },
    236
    237
    0
                PrimOp::Mod => match (&values[0], &values[1]) {
    238
    0
                    (Value::Integer(a), Value::Integer(b)) => {
    239
    0
                        if *b == 0 {
    240
    0
                            Err("Modulo by zero".to_string())
    241
                        } else {
    242
    0
                            Ok(Value::Integer(a % b))
    243
                        }
    244
                    }
    245
    0
                    _ => Err("Type error in modulo".to_string()),
    246
                },
    247
    248
    0
                PrimOp::Pow => match (&values[0], &values[1]) {
    249
    0
                    (Value::Integer(a), Value::Integer(b)) => {
    250
    0
                        if *b < 0 {
    251
    0
                            Err("Negative exponent for integer".to_string())
    252
                        } else {
    253
    0
                            Ok(Value::Integer(a.pow(*b as u32)))
    254
                        }
    255
                    }
    256
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Float(a.powf(*b))),
    257
    0
                    _ => Err("Type error in power".to_string()),
    258
                },
    259
    260
                // Comparison operations
    261
    0
                PrimOp::Eq => Ok(Value::Bool(values[0] == values[1])),
    262
    263
    0
                PrimOp::Ne => Ok(Value::Bool(values[0] != values[1])),
    264
    265
    0
                PrimOp::Lt => match (&values[0], &values[1]) {
    266
    0
                    (Value::Integer(a), Value::Integer(b)) => Ok(Value::Bool(a < b)),
    267
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Bool(a < b)),
    268
    0
                    _ => Err("Type error in less-than".to_string()),
    269
                },
    270
    271
    0
                PrimOp::Le => match (&values[0], &values[1]) {
    272
    0
                    (Value::Integer(a), Value::Integer(b)) => Ok(Value::Bool(a <= b)),
    273
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Bool(a <= b)),
    274
    0
                    _ => Err("Type error in less-equal".to_string()),
    275
                },
    276
    277
    0
                PrimOp::Gt => match (&values[0], &values[1]) {
    278
    0
                    (Value::Integer(a), Value::Integer(b)) => Ok(Value::Bool(a > b)),
    279
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Bool(a > b)),
    280
    0
                    _ => Err("Type error in greater-than".to_string()),
    281
                },
    282
    283
    0
                PrimOp::Ge => match (&values[0], &values[1]) {
    284
    0
                    (Value::Integer(a), Value::Integer(b)) => Ok(Value::Bool(a >= b)),
    285
    0
                    (Value::Float(a), Value::Float(b)) => Ok(Value::Bool(a >= b)),
    286
    0
                    _ => Err("Type error in greater-equal".to_string()),
    287
                },
    288
    289
                // Logical operations
    290
    0
                PrimOp::And => match (&values[0], &values[1]) {
    291
    0
                    (Value::Bool(a), Value::Bool(b)) => Ok(Value::Bool(*a && *b)),
    292
    0
                    _ => Err("Type error in AND".to_string()),
    293
                },
    294
    295
    0
                PrimOp::Or => match (&values[0], &values[1]) {
    296
    0
                    (Value::Bool(a), Value::Bool(b)) => Ok(Value::Bool(*a || *b)),
    297
    0
                    _ => Err("Type error in OR".to_string()),
    298
                },
    299
    300
                PrimOp::NullCoalesce => {
    301
    0
                    if values.len() != 2 {
    302
    0
                        return Err(format!("NullCoalesce expects 2 arguments, got {}", values.len()));
    303
    0
                    }
    304
                    // Return left if not nil, otherwise right
    305
    0
                    match &values[0] {
    306
    0
                        Value::Nil => Ok(values[1].clone()),
    307
    0
                        _ => Ok(values[0].clone()),
    308
                    }
    309
                },
    310
    311
                PrimOp::Not => {
    312
    0
                    if values.len() != 1 {
    313
    0
                        return Err(format!("NOT expects 1 argument, got {}", values.len()));
    314
    0
                    }
    315
    0
                    match &values[0] {
    316
    0
                        Value::Bool(b) => Ok(Value::Bool(!b)),
    317
    0
                        _ => Err("Type error in NOT".to_string()),
    318
                    }
    319
                }
    320
    321
                // Control flow
    322
                PrimOp::If => {
    323
    0
                    if values.len() != 3 {
    324
    0
                        return Err(format!("IF expects 3 arguments, got {}", values.len()));
    325
    0
                    }
    326
    327
                    // Note: We already evaluated all branches (strict evaluation)
    328
                    // A lazy interpreter would evaluate condition first, then the appropriate branch
    329
    0
                    match &values[0] {
    330
    0
                        Value::Bool(true) => Ok(values[1].clone()),
    331
    0
                        Value::Bool(false) => Ok(values[2].clone()),
    332
    0
                        _ => Err("Type error: IF condition must be boolean".to_string()),
    333
                    }
    334
                }
    335
    336
                // Array operations
    337
                PrimOp::ArrayNew => {
    338
                    // Create array from all arguments
    339
    0
                    Ok(Value::Array(values))
    340
                }
    341
    342
                PrimOp::ArrayIndex => {
    343
    0
                    if values.len() != 2 {
    344
    0
                        return Err("Array index expects 2 arguments".to_string());
    345
    0
                    }
    346
    0
                    match (&values[0], &values[1]) {
    347
    0
                        (Value::Array(arr), Value::Integer(idx)) => {
    348
    0
                            if *idx < 0 || *idx as usize >= arr.len() {
    349
    0
                                Err(format!("Array index out of bounds: {idx}"))
    350
                            } else {
    351
    0
                                Ok(arr[*idx as usize].clone())
    352
                            }
    353
                        }
    354
    0
                        _ => Err("Type error in array indexing".to_string()),
    355
                    }
    356
                }
    357
    358
                PrimOp::ArrayLen => {
    359
    0
                    if values.len() != 1 {
    360
    0
                        return Err("Array length expects 1 argument".to_string());
    361
    0
                    }
    362
    0
                    match &values[0] {
    363
    0
                        Value::Array(arr) => Ok(Value::Integer(arr.len() as i64)),
    364
    0
                        _ => Err("Type error: expected array".to_string()),
    365
                    }
    366
                }
    367
    368
    0
                PrimOp::Concat => Err(format!("Unsupported primitive: {op:?}")),
    369
            }
    370
    0
        }
    371
    372
        /// Get execution trace for debugging
    373
        #[must_use]
    374
    0
        pub fn get_trace(&self) -> &[String] {
    375
    0
            &self.trace
    376
    0
        }
    377
    378
        /// Clear the trace
    379
    0
        pub fn clear_trace(&mut self) {
    380
    0
            self.trace.clear();
    381
    0
        }
    382
    }
    383
    384
    #[cfg(test)]
    385
    #[allow(clippy::unwrap_used)]
    386
    mod tests {
    387
        use super::*;
    388
        use crate::transpiler::canonical_ast::AstNormalizer;
    389
        use crate::Parser;
    390
    391
        #[test]
    392
        fn test_eval_arithmetic() {
    393
            let input = "1 + 2 * 3";
    394
            let mut parser = Parser::new(input);
    395
            let ast = parser.parse().unwrap();
    396
    397
            let mut normalizer = AstNormalizer::new();
    398
            let core = normalizer.normalize(&ast);
    399
    400
            let mut interp = ReferenceInterpreter::new();
    401
            let result = interp.eval(&core).unwrap();
    402
    403
            assert_eq!(result, Value::Integer(7)); // 1 + (2 * 3)
    404
        }
    405
    406
        #[test]
    407
        fn test_eval_let_binding() {
    408
            let input = "let x = 10 in ()";
    409
            let mut parser = Parser::new(input);
    410
            let ast = parser.parse().unwrap();
    411
    412
            let mut normalizer = AstNormalizer::new();
    413
            let core = normalizer.normalize(&ast);
    414
    415
            let mut interp = ReferenceInterpreter::new();
    416
            let result = interp.eval(&core).unwrap();
    417
    418
            // Let with unit body evaluates to unit
    419
            assert_eq!(result, Value::Unit);
    420
        }
    421
    422
        #[test]
    423
        fn test_eval_function() {
    424
            // This would need more setup to test properly
    425
            // as we need to handle function definitions and calls
    426
        }
    427
    }