Sloth Functions

Due: May 2

Introduction

For this stage of the Sloth interpreter, we will be adding functions into the language. This will involve changes to the lexer, parser, and tree-walking interpreter.

Functions in Sloth are created with the function keyword. Next comes the name of the function, and the parameter list. Then the body of the function is enclosed in begin/end blocks. The begin/end keywords are required for functions, but not for control structures, which follows the way curly braces work in C-based languages.

Below is an example of a simple function with one parameter:


function printNum(number) begin
    println("Your number is " + number);
    println("Bye!");
end

Functions can also have returns which work similarly to other languages:


function square(number) begin
    return number * number;
end

We can call functions using the familiar syntax:


printNum(10);

x := square(5);

printNum(square(7));

Because Sloth is statically typed, we don't declare the return types of function parameters or return values.

We will use the following new test programs for this stage of the assignment:

Program	Description
simple-function.sl	Function with no parameters or return
greet.sl	Function with a parameter, but no return
fact-function.sl	Compute factorials with a function which returns value
fact-recursive.sl	Compute factorials with a recursive function
mergesort.sl	Multiple functions giving the recursive mergesort algorithm

Lexer Changes

The lexer has very few changes required. Your lexer will just need to capture the following new reserved words:

function
return

Parser Changes

We will need to make a few changes to the parser to be able to parse function definitions and calls. First there are three new types of statements:

Function definitions. These begin with the keyword function, an identifier for the name. Next comes the parameter list enclosed inside parentheses. There are zero or more parameters, but even with zero parameters the parentheses are required. Next comes the begin keyword, zero or more statements, and the end keyword.
Return statements. These contain the return keyword followed by an optional expression, then a semi-colon.
Function calls. Function calls can exist on a line by themselves, so they are a valid form of Sloth statement. A function call consists of an identifier, then zero or more arguments inside of parentheses. Again the parentheses are required even if there are zero arguments. Each of these arguments is any expression. Finally there is a semi-colon when a function call is a statement by itself.

There is also one new type of expression, which is a function call. Having function calls be a type of statement allows them to be called just by themselves. Having them be a type of expression allows them to be called as part of another expression in code like this:


num := num + square(x);

println(getName());

return fib(num - 1) + fib(num - 2);

You can make one grammar rule for function calls and make it an option for both statements and expressions.

Symbol Table Changes

In previous versions of Sloth, we had only one symbol table. Now however, we can have variables in different scopes. Creating a variable in a function only makes it for that function alone. To facilitate this, we're going to have two places to store variables within the interpreter:

We will still have one HashMap<String, SlothValue>, which will store global variables.
We will also have a Stack<HashMap<String, SlothValue>>, for our call stack. Each function that is called will have its own symbol table added to the stack. The variables we reference in the function will go here.

Each time we try to read a variable, we will first check if there is a symbol table on top of the stack. If there is, then we check if it contains a variable with the same name. If so, we fetch that value. If the variable is not in the function's scope (or we're not in a function), we check the global variables symbol table for it instead.

Likewise, every time we write to a variable, we check if there is symbol table on our stack (i.e. whether we are in a function). If so, we put the variable into that symbol table. If there is nothing on the stack, we add it to the global table.

Function Definitions

When we see a function definition, we don't actually run the code in it. We just need to remember it for later so that we can run the code if and when it is actually called. To that end, we will make another symbol table of sorts for storing our functions. The key will be the function name and the value will be the parse tree node of the function.

You can declare this as something like HashMap<String, SlothParser.FunctionDefContext>, of course depending on what your grammar rule for function definitions is called.

When we see a function definition in our walk of the tree, all we do is add a new entry for it into the function table. The name is the identifier of the function and the node is the ctx variable passed into the visit method.

Return Statements

When a function returns, it needs to stop executing and go back to where it was called. The simplest way to implement this behavior in our interpreter is with exception handling. We will create a new type of "exception" called FunctionReturn, as a subclass of RuntimeException. This new class should store a SlothValue, and allow it to be set in the constructor.

When your interpreter encounters a return statement, it should check to see if there is an expression attached. If so, evaluate the expression as the return value. If not, the return value is null. Then throw a new FunctionReturn, passing the return value into it.

Function Calls

Finally we come to actually calling a function. This will involve the following steps:

We must find the name of the function we are calling, and then look its tree node up from our function table. If the function does not exist, that is an error and we should quit.
Create a new symbol table for this function (do not add it to the stack yet).
We need to loop through the arguments and assign them to the formal parameters. For this, you can assume the number of parameters given match what is expected. If there are arguments given, loop through them and do the following:
1. Evaluate the argument by calling visit on it.
2. Make an entry in the function's symbol table with the name being that of the formal parameter, and the value being what we get back from visit.
Push the scope containing the parameters onto the stack of function scopes.
Run all of the statements for this function inside of a try block, where we catch the FunctionReturn exception. Make sure the loop is inside of the try so that the exception ends the whole function.
If we catch the exception, save the value stored inside it as our return value. If we finish the statements in the function without ever having explicitly returned, the return value is null.
Pop the scope for this function off the stack.
Return the return value for this function.

Submitting

Submit the files for your interpreter to Canvas for this assignment.