Building an Interpreter: Functions

A Function in Sox is just another type, like an integer or a string, with its idiosyncrasies such as the ability to execute some predefined code when called using the double parenthesis ( () ) call expression syntax. To integrate functions into our interpreter, we do the following :

1. Define our function type and its implementation(s),

2. Expand our SoxObject enum to include the function type, and

3. Implement visitors for the function and other associated statements in our interpreter.

Let's dive into these in more detail.

The Function type

A function is just a type composed of a block of code that executes when called and a captured environment. SoxFunctions support the following:

1. Calling using the () call syntax.

2. Returning values from their call.

3. Nested function definitions.

So let's get straight to hammering out an implementation that provides the above-listed functionalities. First, we define our function type as the struct shown below.

#[derive(Clone, Debug, PartialEq)]
pub struct SoxFunction {
    pub declaration: Box<Stmt>,
    pub environment_ref: DefaultKey,
}

1. The declaration field is a block statement* - recall block statements are just collections of statements within braces. This block statement is the body of our function that is executed when the function is called and maps to the body of our function definition.

2. The environment_ref is a reference to the interpreter's environment at the point the function was declared. This environment is a snapshot that is immutable from outside of our function. This is useful when dealing with closure.

When the interpreter encounters a function definition, the interpreter invokes the visit_function_stmt below.

    fn visit_function_stmt(&mut self, stmt: &Stmt) -> Self::T {
        if let Stmt::Function {
            name,
            params: _params,
            body: _body,
        } = stmt
        {
            let func_env = Env::default();
            let env_id = self.envs.insert(func_env);

            let stmt_clone = stmt.clone();
            let fo = SoxFunction::new(stmt_clone, env_id);
            let ns = {
                let active_env = self.active_env_mut();
                active_env.define(name.lexeme.clone(), fo.into_ref());
                active_env.namespaces.clone()
            };
            let func_env = self.envs.get_mut(env_id).unwrap();
            func_env.namespaces = ns;

            Ok(())
        } else {
            return Err(Interpreter::runtime_error(
                "Evaluation failed -  Calling a visit_function_stmt on non function node."
                    .to_string(),
            ));
        }
    }

This function creates a new instance of SoxFunction and defines it in the active environment. This idea of capturing a snapshot of the active environment within the function object enables nested functions because a function will always refer to the environment in which it is declared. The implementation of vist_function_stmt is below.

To support the call functionality, we define a call method for SoxFunctions as shown below. The call method has the GenericMethod function signature - fn(fo: SoxObject, args: FuncArgs, interpreter: &mut Interpreter) and we add it to the slot field of the Function type.

Calling a function carries out the following steps:

1. Obtains the environment when captured by the function object.

2. Binds parameters in the environment from #1.

3. Executes the function’s code block within the environment from #1.

4. Returns any value from executing the code block using the exception mechanism.

The interpreter invokes the visit_call_expr function, shown below when it interprets a call expression.

 fn visit_call_expr(&mut self, expr: &Expr) -> Self::T {
        if let Expr::Call {
            callee,
            paren: _,
            arguments,
        } = expr
        {
            let callee_ = self.evaluate(callee)?;
            let mut args = vec![];
            for argument in arguments {
                let arg_val = self.evaluate(argument)?;
                args.push(arg_val);
            }
            let call_args = FuncArgs::new(args);
            let callee_type = callee_.sox_type(self);
            let ret_val = match callee_type.slots.call {
                Some(fo) => {
                    let val = (fo)(callee_, call_args, self);
                    val
                }
                _ => Err(Interpreter::runtime_error(
                    "Callee evaluated to an object that is not callable.".into(),
                )),
            };
            ret_val
        } else {
            Err(Interpreter::runtime_error(
                "Can only call functions and classes".into(),
            ))
        }
    }

This function works by

1. Evaluating the callee to get a SoxObject

2. Evaluating callee arguments, bundling them into a vector and creating a FuncArg object from the arguments.

3. Checking for a call slot implementation on the callee’s type and calling it if there is one with arguments from #2.

We also have to deal with returning values from a callee to the caller. The interpreter uses the visit_return_stmt to handle return statements. A return statement causes an exception to the normal execution flow just like an error would, so we model a return statement as an Exception. Our Exception is expanded into the following shape.

#[derive(Clone, Debug)]
pub enum Exception {
    Err(RuntimeError),
    Return(SoxObject),
}

The Return statement enum option has a Soxobject payload, the data returned from the callee. The snippet below from the call method of the SoxFunction handles disambiguating the exception returned from executing the function body.

if ret.is_err() {
    let exc = ret.err().unwrap().as_exception();
    if let Some(obj) = exc {
        match obj.deref() {
            Exception::Return(v) => {
                return_value = Ok(v.clone());
            }
            Exception::Err(v) => {
                let rv = Exception::Err(v.clone());
                return_value = Err(rv.into_ref());
             }
         }
     }
 }

We end this post with a simple definition of a function to compute the Fibonacci sequence below.

def fib(n) {
    if (n == 0 or n == 1) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

We call the function with an argument of 8 and it outputs 13 as expected below.

fib(8)
>> 13 

That is all there is to our implementation of functions in our language. As usual you can access the code on github. Next, we will extend our interpreter with classes and class instances thus completing a first pass implementation of the Sox grammar as specified in our opening post.