Example lambda interpreter written in F-natural

lambda.fn

{
    // very simple environment, one binding per frame
    typedef environment { frame(string, expression, environment) | root }
    
    // lookup access to the environment
    fn lookup {
        (str, frame(str, value, _)) { value }
        (str, frame(_, _, parent))  { lookup(str, parent) }
        (str, root)                 { error("mce symbol not defined " @@ str) }
    }

    // very simple AST
    typedef expression {
        addition(expression, expression) |
        subtraction(expression, expression) |
        multiplication(expression, expression) |
        division(expression, expression) |
        number(int) |
        symbol(string) |
        conditional(expression, expression, expression) |
        lambda(expression, expression) |
        closure(expression, environment) |
        application(expression, expression)
    }

    // an interpreter
    fn eval {
        (addition(l, r), env)              { add(eval(l, env), eval(r, env)) }
        (subtraction(l, r), env)           { sub(eval(l, env), eval(r, env)) }
        (multiplication(l, r), env)        { mul(eval(l, env), eval(r, env)) }
        (division(l, r), env)              { div(eval(l, env), eval(r, env)) }
        (i = number(_), env)               { i }
        (symbol(str), env)                 { lookup(str, env) }
        (conditional(test, pro, con), env) { cond(test, pro, con, env) }
        (l = lambda(symbol(_), _), env)    { closure(l, env) }
        (application(function, arg), env)  { apply(eval(function, env), eval(arg, env)) }
    }
    
    // function application
    fn apply (closure(lambda(symbol(str), body), env), arg) {
        eval(body, frame(str, arg, env))
    }
    
    // built-ins
    fn add (number(a), number(b)) { number(a + b) }
    fn sub (number(a), number(b)) { number(a - b) }
    fn mul (number(a), number(b)) { number(a * b) }
    fn div (number(a), number(b)) { number(a / b) }
    
    fn cond(test, pro, con, env) {
        switch (eval(test, env)) {
            (number(0)) { eval(con, env) } // 0 is false
            (number(_)) { eval(pro, env) }
        }
    }

    // try it out: [((lambda (x) (if x (+ x 2) x)) a) |- a: 3] = 5
    eval(
        application(
            lambda(
                symbol("x"),
                conditional(
                    symbol("x"),
                    addition(symbol("x"), number(2)),
                    symbol("x")
                )
            ),
            symbol("a")
        ),
        frame("a", number(3), root)
    );
}