An interpreter of Dunno.

dunno.rs

#[derive(Debug, Clone)]
enum Expr {
    Int(u32),
    Succ,
    Apply(Box<Expr>, Box<Expr>),
    Comp(Box<Expr>, Box<Expr>),
    Times(Box<Expr>, Box<Expr>),
}

enum ExprRes {
    Int(u32),
    Func(Box<dyn Fn(u32) -> u32>),
    RuntimeError,
}

impl std::fmt::Debug for ExprRes {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            ExprRes::Int(n) => write!(f, "Int({n:?})"),
            ExprRes::Func(_) => write!(f, "Func(..)"),
            ExprRes::RuntimeError => write!(f, "RuntimeError"),
        }
    }
}

impl Expr {
    fn eval(self) -> ExprRes {
        match self {
            Expr::Int(n) => ExprRes::Int(n),
            Expr::Succ => ExprRes::Func(Box::new(|n| n + 1)),
            Expr::Apply(f, i) => {
                let ExprRes::Func(f) = f.eval() else {
                    return ExprRes::RuntimeError;
                };
                let ExprRes::Int(i) = i.eval() else {
                    return ExprRes::RuntimeError;
                };
                ExprRes::Int((f)(i))
            }
            Expr::Comp(f, g) => {
                let ExprRes::Func(f) = f.eval() else {
                    return ExprRes::RuntimeError;
                };
                let ExprRes::Func(g) = g.eval() else {
                    return ExprRes::RuntimeError;
                };
                ExprRes::Func(Box::new(move |n| f(g(n))))
            }
            Expr::Times(i, f) => {
                let ExprRes::Int(i) = i.eval() else {
                    return ExprRes::RuntimeError;
                };
                let ExprRes::Func(f) = f.eval() else {
                    return ExprRes::RuntimeError;
                };
                ExprRes::Func(Box::new(move |n| {
                    let mut x = n;
                    for _ in 0..i {
                        x = f(x);
                    }
                    x
                }))
            }
        }
    }
}

fn main() {
    let x = Expr::Apply(
        Expr::Times(
            Expr::Int(3).into(),
            Expr::Times(
                Expr::Int(5).into(),
                Expr::Comp(Expr::Succ.into(), Expr::Succ.into()).into(),
            )
            .into(),
        )
        .into(),
        Expr::Int(2).into(),
    );
    println!("{:?}", x.eval());
}