How to share lexical environment with recursive functions in a custom interpreter?

68 views Asked by At

I am implementing an interpreter with Rust. It works with constructs like:

let new_adder = fn (x) { return fn (y) { y + x }; };

let add_ten = new_adder(10);

add_ten(10) // this will be 20,

let apply_function = fn (x,y, func) { func(x,y) };
fn add(x,y) { x + y }

apply_function(3,4,add) // this will be 7

But recursive functions don't work because in my implementation there is no reference to self in the function's environment. For example:

fn recursive (x) {
    if (x>1000*1000*1000) {
        return true;
    } else {
        recursive(x+1)
    }
}

This is the implemetation of environments and functions.

// lexical environment
pub struct Environment<T: Hash + Eq + PartialEq> {
    binding: HashMap<T, Object>,
    outer: Option<Box<Self>>,
    // 0 for global, the bigger is the outter
    level: usize,
}

// function
pub struct Function {
    pub args: Vec<Identifier>,
    pub block: BlockStatement,
    pub env: Environment<String>,
}


// function evaluation (enlist)
//....
let fun = Function {
    args: func.parameters,
    block: func.body,
    // have to clone to catch the current lexical environment
    env: env.clone(),
};
// if this function have identifier, bind to environment
if func.ident.is_some() {
    env.set(func.ident.unwrap().to_str(), Object::Function(fun.clone()));
}
//....



//on calling function
fn eval_call_exp(
    exp: CallExpression,
    env: &mut Environment<String>,
) -> Result<Option<Object>, EvalError> {
    let func = eval_exp(*exp.function, env);

    if func.is_err() {
        return Err(func.err().unwrap());
    }
    if func.clone().unwrap().is_none() {
        return Err(EvalError::FunctionIsNone);
    }
    let func = func.unwrap().unwrap();
    match func {
        Object::Function(func) => {
            let args = eval_function_parameters(exp.arguments, env);
            if args.is_err() {
                return Err(args.err().unwrap());
            }
            let args = args.unwrap();
            apply_function(func, args)
        }
        // func is not a function
        obj => Err(EvalError::NotAFunction(obj)),
    }
}

fn eval_function_parameters(
    args: Vec<Expression>,
    env: &mut Environment<String>,
) -> Result<Vec<Object>, EvalError> {
    let mut result: Vec<Object> = Vec::new();

    for (_, arg) in args.iter().enumerate() {
        let evaluated = eval_exp(arg.clone(), env);

        if evaluated.is_err() {
            return Err(evaluated.err().unwrap());
        }
        if evaluated.clone().unwrap().is_none() {
            return Err(EvalError::EvaluationOfExpressionIsNone(arg.clone()));
        }

        result.push(evaluated.unwrap().unwrap())
    }

    Ok(result)
}

fn apply_function(fun: Function, args: Vec<Object>) -> Result<Option<Object>, EvalError> {
    if args.len() != fun.args.len() {
        return Err(EvalError::FunctionArgLengthNotMatched(ArgumentsLength {
            function_args: fun.args.len(),
            called_with: args.len(),
        }));
    }

    let mut extended_env = extend_function_env(fun.clone(), args);
    let evaluated = eval_stm(Statement::BlockStatement(fun.block), &mut extended_env);

    if evaluated.is_err() {
        return evaluated;
    }
    let evaluated = evaluated.unwrap();

    Ok(unwrap_return_value(evaluated))
}

fn extend_function_env(fun: Function, args: Vec<Object>) -> Environment<String> {
    let mut env = Environment::new_inner(fun.env);

    // bind given args(object) to fun's parameters(ident)
    for (idx, arg) in fun.args.iter().enumerate() {
        env.set(arg.value.clone(), args[idx].clone());
    }

    env
}

How can I give references to functions? I to tried share references with mutable references but the lifetimes are a hassle. Should I use RC, or are mutable references good enough?

Project link: dlang

0

There are 0 answers