panproto_expr/

eval.rs

//! Call-by-value expression evaluator with step and depth limits.
//!
//! The evaluator is pure, deterministic, and WASM-safe. It tracks a step
//! counter (decremented on each reduction) and a depth counter (incremented
//! on each recursive call) to bound computation.

use std::sync::Arc;

use crate::builtin::apply_builtin;
use crate::env::Env;
use crate::error::ExprError;
use crate::expr::{BuiltinOp, Expr, Pattern};
use crate::literal::Literal;

/// Configuration for the expression evaluator.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct EvalConfig {
    /// Maximum number of reduction steps before aborting.
    pub max_steps: u64,
    /// Maximum recursion depth before aborting.
    pub max_depth: u32,
    /// Maximum list length for operations that produce lists.
    pub max_list_len: usize,
}

impl Default for EvalConfig {
    fn default() -> Self {
        Self {
            max_steps: 100_000,
            max_depth: 256,
            max_list_len: 10_000,
        }
    }
}

/// A source of answers for builtins this evaluator cannot compute on its own.
///
/// The graph traversal builtins read an instance, which the pure evaluator
/// does not hold. A resolver plugs that context in at every point a builtin is
/// applied — not only at the root of the expression — so a graph builtin
/// nested under a comparison, a binding, a lambda, or a comprehension answers
/// exactly as it would at the top.
pub trait BuiltinResolver {
    /// Whether this resolver answers for `op`. Operations it declines are
    /// computed by [`apply_builtin`](crate::builtin::apply_builtin).
    fn handles(&self, op: BuiltinOp) -> bool;

    /// Answer `op` on already-evaluated arguments.
    ///
    /// # Errors
    ///
    /// Returns [`ExprError`] when the arguments are of the wrong number or
    /// type, or when the operation fails against the context.
    fn apply(&self, op: BuiltinOp, args: &[Literal]) -> Result<Literal, ExprError>;
}

/// The resolver in force when none is supplied: it answers for nothing, so
/// every builtin is computed purely.
struct NoResolver;

impl BuiltinResolver for NoResolver {
    fn handles(&self, _op: BuiltinOp) -> bool {
        false
    }

    fn apply(&self, op: BuiltinOp, _args: &[Literal]) -> Result<Literal, ExprError> {
        Err(ExprError::NoInstanceContext {
            op: format!("{op:?}"),
        })
    }
}

/// Mutable evaluation state tracking resource consumption.
struct EvalState<'a> {
    steps_remaining: u64,
    max_steps: u64,
    max_depth: u32,
    max_list_len: usize,
    resolver: &'a dyn BuiltinResolver,
}

impl<'a> EvalState<'a> {
    const fn new(config: &EvalConfig, resolver: &'a dyn BuiltinResolver) -> Self {
        Self {
            steps_remaining: config.max_steps,
            max_steps: config.max_steps,
            max_depth: config.max_depth,
            max_list_len: config.max_list_len,
            resolver,
        }
    }

    const fn tick(&mut self) -> Result<(), ExprError> {
        if self.steps_remaining == 0 {
            return Err(ExprError::StepLimitExceeded(self.max_steps));
        }
        self.steps_remaining -= 1;
        Ok(())
    }
}

/// Evaluate an expression in the given environment.
///
/// # Errors
///
/// Returns [`ExprError`] on type mismatches, unbound variables,
/// step/depth limit exceeded, or runtime errors.
pub fn eval(expr: &Expr, env: &Env, config: &EvalConfig) -> Result<Literal, ExprError> {
    eval_with_resolver(expr, env, config, &NoResolver)
}

/// Evaluate an expression, routing the builtins `resolver` claims through it.
///
/// The resolver is consulted wherever a builtin is applied, at any depth, so a
/// context-dependent builtin behaves the same nested as it does at the root.
///
/// # Errors
///
/// Returns [`ExprError`] on type mismatches, unbound variables,
/// step/depth limit exceeded, or runtime errors, including any the resolver
/// itself reports.
pub fn eval_with_resolver(
    expr: &Expr,
    env: &Env,
    config: &EvalConfig,
    resolver: &dyn BuiltinResolver,
) -> Result<Literal, ExprError> {
    let mut state = EvalState::new(config, resolver);
    eval_inner(expr, env, 0, &mut state)
}

fn eval_inner(
    expr: &Expr,
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    if depth > state.max_depth {
        return Err(ExprError::DepthExceeded(state.max_depth));
    }
    state.tick()?;

    match expr {
        // The builtins form a scope beneath the environment: a lexical
        // binding of the same name shadows one, and a free variable naming a
        // builtin denotes that builtin as a value, curried over its arity.
        Expr::Var(name) => env.get(name).cloned().map_or_else(
            || {
                BuiltinOp::from_name(name)
                    .map(builtin_as_value)
                    .ok_or_else(|| ExprError::UnboundVariable(name.to_string()))
            },
            Ok,
        ),

        Expr::Lit(lit) => Ok(lit.clone()),

        Expr::Lam(param, body) => {
            // Lambdas evaluate to closures over the scope they were written
            // in, which gives lexical scoping and first-class functions. The
            // scope is shared, not copied.
            Ok(Literal::Closure {
                param: Arc::clone(param),
                body: body.clone(),
                env: env.clone(),
            })
        }

        Expr::App(func, arg) => eval_app(func, arg, env, depth, state),

        Expr::Record(fields) => {
            let mut result = Vec::with_capacity(fields.len());
            for (name, expr) in fields {
                let val = eval_inner(expr, env, depth + 1, state)?;
                result.push((Arc::clone(name), val));
            }
            Ok(Literal::Record(result))
        }

        Expr::List(items) => {
            let mut result = Vec::with_capacity(items.len());
            for item in items {
                let val = eval_inner(item, env, depth + 1, state)?;
                result.push(val);
            }
            if result.len() > state.max_list_len {
                return Err(ExprError::ListLengthExceeded(result.len()));
            }
            Ok(Literal::List(result))
        }

        Expr::Field(expr, field) => {
            let val = eval_inner(expr, env, depth + 1, state)?;
            match &val {
                Literal::Record(fields) => fields
                    .iter()
                    .find(|(k, _)| k == field)
                    .map(|(_, v)| v.clone())
                    .ok_or_else(|| ExprError::FieldNotFound(field.to_string())),
                _ => Err(ExprError::TypeError {
                    expected: "record".into(),
                    got: val.type_name().into(),
                }),
            }
        }

        Expr::Index(expr, idx_expr) => eval_index(expr, idx_expr, env, depth, state),

        Expr::Match { scrutinee, arms } => eval_match(scrutinee, arms, env, depth, state),

        Expr::Let { name, value, body } => {
            let val = eval_inner(value, env, depth + 1, state)?;
            let new_env = env.extend(Arc::clone(name), val);
            eval_inner(body, &new_env, depth + 1, state)
        }

        Expr::Builtin(op, args) if args.len() < op.arity() => {
            // A builtin given fewer arguments than it takes is a function of
            // the rest, exactly as a partially applied lambda is.
            eval_partial_builtin(*op, args, env, depth, state)
        }

        Expr::Builtin(op, args) => {
            // Special handling for higher-order builtins (Map, Filter, Fold,
            // FlatMap) and for Range, which needs the list-length budget:
            // it is the one builtin that can allocate an arbitrarily long
            // list from a constant-size expression.
            match op {
                BuiltinOp::Map => eval_map(args, env, depth, state),
                BuiltinOp::Filter => eval_filter(args, env, depth, state),
                BuiltinOp::Fold => eval_fold(args, env, depth, state),
                BuiltinOp::FlatMap => eval_flat_map(args, env, depth, state),
                BuiltinOp::Range => eval_range(args, env, depth, state),
                _ => {
                    let evaluated: Result<Vec<_>, _> = args
                        .iter()
                        .map(|a| eval_inner(a, env, depth + 1, state))
                        .collect();
                    let evaluated = evaluated?;
                    if state.resolver.handles(*op) {
                        state.resolver.apply(*op, &evaluated)
                    } else {
                        apply_builtin(*op, &evaluated)
                    }
                }
            }
        }
    }
}

/// The name a builtin's `n`-th curried parameter binds.
///
/// The double underscore keeps these out of the way of surface identifiers,
/// which the lexer does not admit with that prefix.
fn builtin_param(index: usize) -> Arc<str> {
    Arc::from(format!("__builtin_arg{index}"))
}

/// The function a builtin denotes once `supplied` arguments are in hand: a
/// closure taking the rest one at a time, in surface order.
///
/// Arguments sit in surface order until the call is saturated, so the
/// permutation into [`Expr::Builtin`] order is applied once, on the complete
/// list inside the closure's body.
fn curried_builtin(op: BuiltinOp, mut surface: Vec<Expr>) -> Literal {
    let arity = op.arity();
    let first_missing = surface.len();
    for index in first_missing..arity {
        surface.push(Expr::Var(builtin_param(index)));
    }

    let mut body = Expr::Builtin(op, op.surface_args_to_expr_args(surface));
    // Wrap innermost-last: `\a_k -> ... -> \a_{n-1} -> op a_0 ... a_{n-1}`.
    for index in (first_missing + 1..arity).rev() {
        body = Expr::Lam(builtin_param(index), Box::new(body));
    }
    Literal::Closure {
        param: builtin_param(first_missing),
        body: Box::new(body),
        env: Env::new(),
    }
}

/// The value a builtin's bare name denotes: the builtin curried over its whole
/// argument list.
fn builtin_as_value(op: BuiltinOp) -> Literal {
    curried_builtin(op, Vec::new())
}

/// Evaluate an under-saturated builtin to the function of its missing
/// arguments.
///
/// The arguments already supplied are evaluated here, at the point the partial
/// application is written, and carried into the closure as literals; the rest
/// are abstracted over. Arguments sit in surface order until the call is
/// saturated, so the permutation into `Expr::Builtin` order is applied once,
/// on the complete list inside the closure's body.
fn eval_partial_builtin(
    op: BuiltinOp,
    args: &[Expr],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    let mut surface = Vec::with_capacity(op.arity());
    for arg in args {
        surface.push(Expr::Lit(eval_inner(arg, env, depth + 1, state)?));
    }
    Ok(curried_builtin(op, surface))
}

/// Evaluate a range: `range(start, stop)` -> `[start, ..., stop]`.
///
/// Both bounds are inclusive, following the surface syntax `[a..b]` this
/// lowers from. A `stop` below `start` yields the empty list rather than
/// an error, matching the descending-range convention of the Haskell-style
/// syntax the parser accepts.
///
/// The length is checked *before* allocating. Range is the only builtin
/// that can turn a constant-size expression into an arbitrarily long list,
/// so computing the length first and rejecting it against `max_list_len`
/// keeps `[0..9999999999]` from exhausting memory before the budget is
/// consulted.
fn eval_range(
    args: &[Expr],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    if args.len() != 2 {
        return Err(ExprError::ArityMismatch {
            op: "Range".into(),
            expected: 2,
            got: args.len(),
        });
    }
    let start = match eval_inner(&args[0], env, depth + 1, state)? {
        Literal::Int(n) => n,
        other => {
            return Err(ExprError::TypeError {
                expected: "int".into(),
                got: other.type_name().into(),
            });
        }
    };
    let stop = match eval_inner(&args[1], env, depth + 1, state)? {
        Literal::Int(n) => n,
        other => {
            return Err(ExprError::TypeError {
                expected: "int".into(),
                got: other.type_name().into(),
            });
        }
    };

    if stop < start {
        return Ok(Literal::List(Vec::new()));
    }
    // `stop >= start` here, so the difference is non-negative; widen to
    // i128 so that a range spanning the full i64 domain cannot overflow
    // while computing its own length.
    let len = (i128::from(stop) - i128::from(start)) + 1;
    let max = i128::try_from(state.max_list_len).unwrap_or(i128::MAX);
    if len > max {
        return Err(ExprError::ListLengthExceeded(
            usize::try_from(len).unwrap_or(usize::MAX),
        ));
    }
    let len_usize = usize::try_from(len).unwrap_or(usize::MAX);
    let mut result = Vec::with_capacity(len_usize);
    for n in start..=stop {
        result.push(Literal::Int(n));
    }
    Ok(Literal::List(result))
}

/// Evaluate a function application.
///
/// Evaluates both the function and argument, then applies. The function
/// may be a structural `Lam` node (direct beta reduction) or may evaluate
/// to a `Literal::Closure` (proper closure application with captured env).
fn eval_app(
    func: &Expr,
    arg: &Expr,
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    // Evaluate the function expression to a value.
    let func_val = eval_inner(func, env, depth + 1, state)?;
    // Evaluate the argument.
    let arg_val = eval_inner(arg, env, depth + 1, state)?;
    // Apply the closure to the argument.
    apply_closure(&func_val, &arg_val, depth, state)
}

/// Apply a closure value to an argument value.
///
/// Reconstructs the captured environment, binds the parameter, and
/// evaluates the body. This is the formal beta-reduction step for
/// the call-by-value evaluation strategy.
fn apply_closure(
    func: &Literal,
    arg: &Literal,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    match func {
        Literal::Closure { param, body, env } => {
            // Bind the parameter in the captured scope and evaluate the body
            // there. This is the beta-reduction step of call-by-value.
            let closure_env = env.extend(Arc::clone(param), arg.clone());
            eval_inner(body, &closure_env, depth + 1, state)
        }
        _ => Err(ExprError::NotAFunction),
    }
}

/// Evaluate an index expression: `expr[idx]`.
#[allow(
    clippy::cast_possible_wrap,
    clippy::cast_possible_truncation,
    clippy::cast_sign_loss
)]
fn eval_index(
    expr: &Expr,
    idx_expr: &Expr,
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    let val = eval_inner(expr, env, depth + 1, state)?;
    let idx = eval_inner(idx_expr, env, depth + 1, state)?;
    match (&val, &idx) {
        (Literal::List(items), Literal::Int(i)) => {
            let index = if *i < 0 {
                (items.len() as i64 + i) as usize
            } else {
                *i as usize
            };
            items
                .get(index)
                .cloned()
                .ok_or(ExprError::IndexOutOfBounds {
                    index: *i,
                    len: items.len(),
                })
        }
        _ => Err(ExprError::TypeError {
            expected: "(list, int)".into(),
            got: format!("({}, {})", val.type_name(), idx.type_name()),
        }),
    }
}

/// Evaluate a match expression.
fn eval_match(
    scrutinee: &Expr,
    arms: &[(Pattern, Expr)],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    let val = eval_inner(scrutinee, env, depth + 1, state)?;
    for (pattern, body) in arms {
        if let Some(bindings) = match_pattern(pattern, &val) {
            let mut new_env = env.clone();
            for (name, bound_val) in bindings {
                new_env = new_env.extend(name, bound_val);
            }
            return eval_inner(body, &new_env, depth + 1, state);
        }
    }
    Err(ExprError::NonExhaustiveMatch)
}

/// Evaluate `map(list_expr, lambda_expr)`.
fn eval_map(
    args: &[Expr],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    if args.len() != 2 {
        return Err(ExprError::ArityMismatch {
            op: "Map".into(),
            expected: 2,
            got: args.len(),
        });
    }
    let list_val = eval_inner(&args[0], env, depth + 1, state)?;
    let items = match list_val {
        Literal::List(items) => items,
        other => {
            return Err(ExprError::TypeError {
                expected: "list".into(),
                got: other.type_name().into(),
            });
        }
    };

    let func = &args[1];
    let mut result = Vec::with_capacity(items.len());
    for item in &items {
        let val = apply_lambda(func, item, env, depth + 1, state)?;
        result.push(val);
    }
    if result.len() > state.max_list_len {
        return Err(ExprError::ListLengthExceeded(result.len()));
    }
    Ok(Literal::List(result))
}

/// Evaluate `filter(list_expr, predicate_expr)`.
fn eval_filter(
    args: &[Expr],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    if args.len() != 2 {
        return Err(ExprError::ArityMismatch {
            op: "Filter".into(),
            expected: 2,
            got: args.len(),
        });
    }
    let list_val = eval_inner(&args[0], env, depth + 1, state)?;
    let items = match list_val {
        Literal::List(items) => items,
        other => {
            return Err(ExprError::TypeError {
                expected: "list".into(),
                got: other.type_name().into(),
            });
        }
    };

    let pred = &args[1];
    let mut result = Vec::new();
    for item in &items {
        let keep = apply_lambda(pred, item, env, depth + 1, state)?;
        match keep {
            Literal::Bool(true) => result.push(item.clone()),
            Literal::Bool(false) => {}
            other => {
                return Err(ExprError::TypeError {
                    expected: "bool".into(),
                    got: other.type_name().into(),
                });
            }
        }
    }
    Ok(Literal::List(result))
}

/// Evaluate `fold(list_expr, init_expr, accumulator_expr)`.
fn eval_fold(
    args: &[Expr],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    if args.len() != 3 {
        return Err(ExprError::ArityMismatch {
            op: "Fold".into(),
            expected: 3,
            got: args.len(),
        });
    }
    let list_val = eval_inner(&args[0], env, depth + 1, state)?;
    let items = match list_val {
        Literal::List(items) => items,
        other => {
            return Err(ExprError::TypeError {
                expected: "list".into(),
                got: other.type_name().into(),
            });
        }
    };

    let mut acc = eval_inner(&args[1], env, depth + 1, state)?;
    let func = &args[2];

    for item in &items {
        // func is a curried binary function: λacc. λitem. body
        // Apply it to acc, then to item.
        acc = apply_lambda_2(func, &acc, item, env, depth + 1, state)?;
    }
    Ok(acc)
}

/// Evaluate `flat_map(list_expr, lambda_expr)`.
fn eval_flat_map(
    args: &[Expr],
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    if args.len() != 2 {
        return Err(ExprError::ArityMismatch {
            op: "FlatMap".into(),
            expected: 2,
            got: args.len(),
        });
    }
    let list_val = eval_inner(&args[0], env, depth + 1, state)?;
    let items = match list_val {
        Literal::List(items) => items,
        other => {
            return Err(ExprError::TypeError {
                expected: "list".into(),
                got: other.type_name().into(),
            });
        }
    };

    let func = &args[1];
    let mut result = Vec::new();
    for item in &items {
        let sub_list = apply_lambda(func, item, env, depth + 1, state)?;
        match sub_list {
            Literal::List(sub_items) => result.extend(sub_items),
            other => {
                return Err(ExprError::TypeError {
                    expected: "list".into(),
                    got: other.type_name().into(),
                });
            }
        }
        if result.len() > state.max_list_len {
            return Err(ExprError::ListLengthExceeded(result.len()));
        }
    }
    Ok(Literal::List(result))
}

/// Evaluate a function expression and apply it to a single argument value.
///
/// The function expression is evaluated to produce a closure, then the
/// closure is applied to the argument via [`apply_closure`].
fn apply_lambda(
    func_expr: &Expr,
    arg: &Literal,
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    let func_val = eval_inner(func_expr, env, depth + 1, state)?;
    apply_closure(&func_val, arg, depth, state)
}

/// Evaluate a curried binary function and apply it to two arguments.
///
/// Evaluates `func_expr` to get a closure, applies to `arg1` to get
/// a second closure, then applies to `arg2`.
fn apply_lambda_2(
    func_expr: &Expr,
    arg1: &Literal,
    arg2: &Literal,
    env: &Env,
    depth: u32,
    state: &mut EvalState<'_>,
) -> Result<Literal, ExprError> {
    let func_val = eval_inner(func_expr, env, depth + 1, state)?;
    let partial = apply_closure(&func_val, arg1, depth, state)?;
    apply_closure(&partial, arg2, depth, state)
}

/// Try to match a value against a pattern, returning bindings on success.
fn match_pattern(pattern: &Pattern, value: &Literal) -> Option<Vec<(Arc<str>, Literal)>> {
    let mut bindings = Vec::new();
    if match_inner(pattern, value, &mut bindings) {
        Some(bindings)
    } else {
        None
    }
}

fn match_inner(
    pattern: &Pattern,
    value: &Literal,
    bindings: &mut Vec<(Arc<str>, Literal)>,
) -> bool {
    match pattern {
        Pattern::Wildcard => true,
        Pattern::Var(name) => {
            bindings.push((Arc::clone(name), value.clone()));
            true
        }
        Pattern::Lit(lit) => lit == value,
        Pattern::Record(field_pats) => {
            if let Literal::Record(fields) = value {
                for (pat_name, pat) in field_pats {
                    let field_val = fields.iter().find(|(k, _)| k == pat_name);
                    match field_val {
                        Some((_, v)) => {
                            if !match_inner(pat, v, bindings) {
                                return false;
                            }
                        }
                        None => return false,
                    }
                }
                true
            } else {
                false
            }
        }
        Pattern::List(item_pats) => {
            if let Literal::List(items) = value {
                if items.len() != item_pats.len() {
                    return false;
                }
                for (pat, val) in item_pats.iter().zip(items.iter()) {
                    if !match_inner(pat, val, bindings) {
                        return false;
                    }
                }
                true
            } else {
                false
            }
        }
        Pattern::Constructor(tag, arg_pats) => {
            // Constructors match against records with a "$tag" field
            if let Literal::Record(fields) = value {
                let tag_field = fields.iter().find(|(k, _)| &**k == "$tag");
                if let Some((_, Literal::Str(t))) = tag_field {
                    if t.as_str() != &**tag {
                        return false;
                    }
                    // Match remaining args against "$0", "$1", etc. fields
                    for (i, pat) in arg_pats.iter().enumerate() {
                        let key = format!("${i}");
                        let field_val = fields.iter().find(|(k, _)| k.as_ref() == key.as_str());
                        match field_val {
                            Some((_, v)) => {
                                if !match_inner(pat, v, bindings) {
                                    return false;
                                }
                            }
                            None => return false,
                        }
                    }
                    true
                } else {
                    false
                }
            } else {
                false
            }
        }
    }
}

#[cfg(test)]
#[allow(clippy::unwrap_used)]
mod tests {
    use super::*;

    fn default_config() -> EvalConfig {
        EvalConfig::default()
    }

    #[test]
    fn eval_literal() {
        let result = eval(&Expr::Lit(Literal::Int(42)), &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(42));
    }

    #[test]
    fn eval_variable() {
        let env = Env::new().extend(Arc::from("x"), Literal::Int(10));
        let result = eval(&Expr::var("x"), &env, &default_config());
        assert_eq!(result.unwrap(), Literal::Int(10));
    }

    #[test]
    fn eval_unbound_variable() {
        let result = eval(&Expr::var("x"), &Env::new(), &default_config());
        assert!(matches!(result, Err(ExprError::UnboundVariable(_))));
    }

    #[test]
    fn eval_lambda_application() {
        // (λx. add(x, 1))(41) = 42
        let expr = Expr::App(
            Box::new(Expr::lam(
                "x",
                Expr::builtin(
                    BuiltinOp::Add,
                    vec![Expr::var("x"), Expr::Lit(Literal::Int(1))],
                ),
            )),
            Box::new(Expr::Lit(Literal::Int(41))),
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(42));
    }

    #[test]
    fn eval_let_binding() {
        // let x = 10 in add(x, 5)
        let expr = Expr::let_in(
            "x",
            Expr::Lit(Literal::Int(10)),
            Expr::builtin(
                BuiltinOp::Add,
                vec![Expr::var("x"), Expr::Lit(Literal::Int(5))],
            ),
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(15));
    }

    #[test]
    fn eval_record_and_field() {
        let expr = Expr::field(
            Expr::Record(vec![
                (Arc::from("name"), Expr::Lit(Literal::Str("alice".into()))),
                (Arc::from("age"), Expr::Lit(Literal::Int(30))),
            ]),
            "age",
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(30));
    }

    #[test]
    fn eval_list_index() {
        let expr = Expr::Index(
            Box::new(Expr::List(vec![
                Expr::Lit(Literal::Int(10)),
                Expr::Lit(Literal::Int(20)),
                Expr::Lit(Literal::Int(30)),
            ])),
            Box::new(Expr::Lit(Literal::Int(1))),
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(20));
    }

    #[test]
    fn eval_pattern_match() {
        // match 42 { 0 => "zero", x => concat("num:", int_to_str(x)) }
        let expr = Expr::Match {
            scrutinee: Box::new(Expr::Lit(Literal::Int(42))),
            arms: vec![
                (
                    Pattern::Lit(Literal::Int(0)),
                    Expr::Lit(Literal::Str("zero".into())),
                ),
                (
                    Pattern::Var(Arc::from("x")),
                    Expr::builtin(
                        BuiltinOp::Concat,
                        vec![
                            Expr::Lit(Literal::Str("num:".into())),
                            Expr::builtin(BuiltinOp::IntToStr, vec![Expr::var("x")]),
                        ],
                    ),
                ),
            ],
        };
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Str("num:42".into()));
    }

    #[test]
    fn eval_map() {
        // map([1, 2, 3], λx. mul(x, 2))
        let expr = Expr::builtin(
            BuiltinOp::Map,
            vec![
                Expr::List(vec![
                    Expr::Lit(Literal::Int(1)),
                    Expr::Lit(Literal::Int(2)),
                    Expr::Lit(Literal::Int(3)),
                ]),
                Expr::lam(
                    "x",
                    Expr::builtin(
                        BuiltinOp::Mul,
                        vec![Expr::var("x"), Expr::Lit(Literal::Int(2))],
                    ),
                ),
            ],
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(
            result.unwrap(),
            Literal::List(vec![Literal::Int(2), Literal::Int(4), Literal::Int(6)])
        );
    }

    #[test]
    fn eval_filter() {
        // filter([1, 2, 3, 4], λx. gt(x, 2))
        let expr = Expr::builtin(
            BuiltinOp::Filter,
            vec![
                Expr::List(vec![
                    Expr::Lit(Literal::Int(1)),
                    Expr::Lit(Literal::Int(2)),
                    Expr::Lit(Literal::Int(3)),
                    Expr::Lit(Literal::Int(4)),
                ]),
                Expr::lam(
                    "x",
                    Expr::builtin(
                        BuiltinOp::Gt,
                        vec![Expr::var("x"), Expr::Lit(Literal::Int(2))],
                    ),
                ),
            ],
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(
            result.unwrap(),
            Literal::List(vec![Literal::Int(3), Literal::Int(4)])
        );
    }

    #[test]
    fn eval_fold() {
        // fold([1, 2, 3], 0, λacc. λx. add(acc, x)) = 6
        let expr = Expr::builtin(
            BuiltinOp::Fold,
            vec![
                Expr::List(vec![
                    Expr::Lit(Literal::Int(1)),
                    Expr::Lit(Literal::Int(2)),
                    Expr::Lit(Literal::Int(3)),
                ]),
                Expr::Lit(Literal::Int(0)),
                Expr::lam(
                    "acc",
                    Expr::lam(
                        "x",
                        Expr::builtin(BuiltinOp::Add, vec![Expr::var("acc"), Expr::var("x")]),
                    ),
                ),
            ],
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(6));
    }

    #[test]
    fn eval_step_limit() {
        // A computation that exceeds the step limit
        let config = EvalConfig {
            max_steps: 5,
            ..EvalConfig::default()
        };
        // map([1,2,3,4,5,6,7,8,9,10], λx. add(x, 1)); should exceed 5 steps
        let items: Vec<_> = (1..=10).map(|i| Expr::Lit(Literal::Int(i))).collect();
        let expr = Expr::builtin(
            BuiltinOp::Map,
            vec![
                Expr::List(items),
                Expr::lam(
                    "x",
                    Expr::builtin(
                        BuiltinOp::Add,
                        vec![Expr::var("x"), Expr::Lit(Literal::Int(1))],
                    ),
                ),
            ],
        );
        let result = eval(&expr, &Env::new(), &config);
        assert!(matches!(result, Err(ExprError::StepLimitExceeded(_))));
    }

    #[test]
    fn eval_merge_example() {
        // The merge example from the design doc:
        // λfirst. λlast. concat(first, concat(" ", last))
        let merge_fn = Expr::lam(
            "first",
            Expr::lam(
                "last",
                Expr::builtin(
                    BuiltinOp::Concat,
                    vec![
                        Expr::var("first"),
                        Expr::builtin(
                            BuiltinOp::Concat,
                            vec![Expr::Lit(Literal::Str(" ".into())), Expr::var("last")],
                        ),
                    ],
                ),
            ),
        );
        // Apply: merge_fn("Alice")("Smith")
        let expr = Expr::App(
            Box::new(Expr::App(
                Box::new(merge_fn),
                Box::new(Expr::Lit(Literal::Str("Alice".into()))),
            )),
            Box::new(Expr::Lit(Literal::Str("Smith".into()))),
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Str("Alice Smith".into()));
    }

    #[test]
    fn eval_split_example() {
        // The split example from the design doc:
        // λfull. let parts = split(full, " ") in
        //   { firstName: head(parts), lastName: join(tail(parts), " ") }
        let split_fn = Expr::lam(
            "full",
            Expr::let_in(
                "parts",
                Expr::builtin(
                    BuiltinOp::Split,
                    vec![Expr::var("full"), Expr::Lit(Literal::Str(" ".into()))],
                ),
                Expr::Record(vec![
                    (
                        Arc::from("firstName"),
                        Expr::builtin(BuiltinOp::Head, vec![Expr::var("parts")]),
                    ),
                    (
                        Arc::from("lastName"),
                        Expr::builtin(
                            BuiltinOp::Join,
                            vec![
                                Expr::builtin(BuiltinOp::Tail, vec![Expr::var("parts")]),
                                Expr::Lit(Literal::Str(" ".into())),
                            ],
                        ),
                    ),
                ]),
            ),
        );
        let expr = Expr::App(
            Box::new(split_fn),
            Box::new(Expr::Lit(Literal::Str("Alice B Smith".into()))),
        );
        let result = eval(&expr, &Env::new(), &default_config());
        let expected = Literal::Record(vec![
            (Arc::from("firstName"), Literal::Str("Alice".into())),
            (Arc::from("lastName"), Literal::Str("B Smith".into())),
        ]);
        assert_eq!(result.unwrap(), expected);
    }

    #[test]
    fn eval_coercion_example() {
        // λv. str_to_int(v)
        let coerce = Expr::lam(
            "v",
            Expr::builtin(BuiltinOp::StrToInt, vec![Expr::var("v")]),
        );
        let expr = Expr::App(
            Box::new(coerce),
            Box::new(Expr::Lit(Literal::Str("42".into()))),
        );
        let result = eval(&expr, &Env::new(), &default_config());
        assert_eq!(result.unwrap(), Literal::Int(42));
    }
}