1 Starter Code

You should already have a shared git repository spl. To get the starter code for today's lab, cd to your si413/spl directory and run these commands:

git pull starter main
git pull

You should now have a folder like si413/spl/lab08 with the starter code for this lab, the lab08.md file you will need to fill out, and a handy script to submit your code.

You can also browse the starter code from the Gitlab page (USNA intranet only).

2 Introduction

Today we're going to implement proper lexical scoping with frames and closures in SPL. By the end of this lab, you will have working function calls with lexical scope, and will be able to run complete and powerful SPL programs.

Specifically, you will:

• Implement lexical scoping with blocks, by adding a parent frame pointer to the Frame class, and replacing the global symbol table from last week's lab with a Frame object which is passed to every evaluate() and execute() method.
• Implement closures to support evaluating lambda expressions. This will first require a new Closure class to associate a Lambda with the Frame where it was evaluated. Then you have to complete the evaluate() method in the Lambda class itself to return (a numeric representation of) a new Closure.
• Implement function calls which (for now) ignore arguments and return values. This means implementing the execute() method in the FunCall class.
• Complete the implementation of function calls with arguments and return values properly handled in their respective scopes.
• Add a new kind of "expression statement" to the SPL interpreter language, so that it's possible for example to simply call a function as a complete statement, rather than having to incorporate the function call as part of a write or assignment.

This will be another challenging lab, but in a different way from last week. Last week, you had to write a lot of code, but much of it was fairly straightforward. This weeks lab actually requires a lot less new code to be written, but most of it is very precise, and getting it right requires you to really understand how scoping and function calls work. Plan to spend much more time thinking, diagramming, testing, and debugging, than you do actually writing code.

3 Looking at the starter code

The starter code that you pulled from gitlab is actually a solution to last week's lab, with the following updates:

• Every evaluate() and execute() method has been changed to take a single argument Frame env, representing the current environment. But in the starter code this Frame is never updated anywhere, so there is still just a single global scope (until you fix it!).
• New classes Lambda and FunCall have been added to the ast sub-package and to ExpressionBuilder. But the all-important evaluate() methods have not been implemented; that's your job.
• All of the public and hidden unit tests have been consolidated into a single (massive) class Lab07Test.
• There are new unit test files for the (public) tests for this lab, named Ex1Test, Ex2Test, etc.

You should be able to fully understand all of this. I could have asked you to make these changes yourself, and you could definitely do it, but it would be a bit tedious. I would rather you spend your time doing other things!

If you want, you can use your own solution to last week's lab instead of this starter code, but probably chat with your instructor about it first. You would want to make sure that your solution was 100% correct, and that it incorporates the changes mentioned above.

4 Frames and Lexical Scope with Blocks

Last week's lab had a single global Frame object for the single global scope. Now we will implement lexical scoping with (nested) blocks in SPL.

Specifically, you need to do three things:

• Modify the Frame class so that it has a new field (of type Frame to represent the parent Frame. Add a constructor that accordingly takes an argument for the parent Frame, and update the makeGlobal() method so that the global frame has a parent that is null.
• Fix the execute() method in the Block class so that it executes the statements in a new Frame.
• Fix the bind, rebind, and lookup methods in the Frame class so that they recursively look into the parent frame as necessary.
  (Note, not all three methods necessarily need to be changed. Think about it, test, and experiment!)

After this, your SPL interpreter should correctly handle local variables in nested scopes, exactly like this:

roche@ubuntu$ ./spli.sh
spl> new a := 100;
spl> { new x := a; write a + x; }
200
spl> write a + x;
ERROR: No binding for variable 'x'
spl> { new y := 3; a := a + y; }
spl> write a;
103
spl> { new a := 50; while a < 100 { a := a + 30; } write a; }
110
spl> write a;
103

Exercises

1. Update the Frame and Block classes so that nested blocks (and any other kinds of statements except function calls) work correctly with lexical scoping.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
To run the public tests yourself, run: ./runtest.sh Ex1Test

5 Closures and Lambda evaluation

The next step is to write the int evaluate(Frame env) method working in the Lambda class. But first we have to ask, what should a lambda actually evaluate to in the SPL language?

We know that lambda represents an (unnamed) function definition, and we also know that the SPL language should support lexical scoping with first-class functions. That means there is only one choice: evaluating a lambda should produce a closure.

OK, so you will have to add a new Closure class to your SPL interpreter, which contains two things: a reference to the Lambda AST node instance for this function, and a reference to the Frame where the lambda was evaluated.

So far this sounds good: the evaluate method in the Lambda class can create a new Closure instance (which includes this Lambda class itself along with the current Frame environment), and then return that Closure object you just created.

Except, there is a small technical issue: the int evaluate(Frame env) method in your Lambda class can't return any old object, it has to return an int. We can accommodate this by adding some static fields and methods to the Closure class that gives each Closure an instance a numeric id number at construction time, and then allows you to effectively look up any Closure instance by its id number later on.

This might sound a little complicated, but it's actually not too bad if you remember how static fields and methods work from your Object-Oriented Programming class. Take some inspiration (and feel free to steal some code) from this small Widget class example of the same concept:

import java.util.*;

/** A simple class to demonstrate the ability to save all instances of an object. */
public class Widget {
    /** A STATIC list of instances of this class. */
    private static List<Widget> saved = new ArrayList<>();

    /** STATIC method to get the instance from its id number. */
    public static Widget fromId(int id) {
        return saved.get(id);
    }

    /** Each instance has a name and an id. (NOT static) */
    private String name;
    private int id;

    /** Constructor from a name.
     * Inside the constructor is the logic to get an unused id
     * and add it to the list.
     */
    public Widget(String name) {
        this.name = name;
        id = saved.size();
        saved.add(this);
    }

    /** Get the numeric id for this instance.
     * For any instance x, it should be true that Widget.fromId(x.getId()) == x.
     */
    public int getId() {
        return id;
    }

    @Override
    public String toString() {
        return "Widget '%s' with id %d".formatted(name, id);
    }

    /** Example program to show how the ids can be used. */
    public static void main(String[] args) {
        Widget first = new Widget("first");
        System.out.println(first); // Widget 'first' with id 0
        Widget second = new Widget("second");
        System.out.println(second); // Widget 'second' with id 1
        System.out.format("%s %s%n",
            new Widget("throwaway"),
            new Widget("another throwaway"));
        int remember;
        {
            Widget temp = new Widget("nested");
            remember = temp.getId();
        }
        // note, can't refer to variable "temp" here, out of scope
        // but we can get that Widget back, using its id!
        Widget gotback = Widget.fromId(remember);
        System.out.println(gotback); // Widget 'nested' with id 4
    }
}

Exercises

2. Add an implementation of the int evaluate(Frame env) method to the Lambda class which creates a new closure and returns a numeric id representing the closure.
   Specifically, you will need to:
   • Write a new Closure.java class in the src/main/java/si413/spl directory. (Be sure to indicate that this class is part of the si413.spl package on the first line.)
   • Add a constructor to your Closure class that takes a Lambda and and Frame, and stores those as class instance fields.
   • Add static functionality to your Closure class to support numeric id's along the lines of the Widget example above. (You will want a static fromId method and a non-static getId method.)
   • Write the evaluate method in your Lambda class, which should create a new Closure instance and then return that closure's numeric id.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
To run the public tests yourself, run: ./runtest.sh Ex2Test

6 Basic function calls

The next step is implementing the int evaluate(Frame env) method in your FunCall class so that functions actually work. Exciting!

For this part, you can ignore arguments and return values; your goal is just to be able to jump in program execution from the call site to the actual function definition in the AST.

Note that the FunCall class has two sub-expressions, for the left-hand side and right-hand side of the @ sign. We usually have a variable name on the left-hand side but it doesn't necessarily have to be that!

Tips:

• The first thing your FunCall's evaluate will have to do is to recursively evaluate the funExp on the left-hand side of the @ sign.
• That evaluation - like all SPL evaluations for now - returns an int. This number should be the id of a Closure instance. From the previous part, you should have a static method in your Closure class which allows you to turn that id into an actual Closure object.
• You want to somehow call execute on the body of the lambda itself. To get at this information, you will probably need to add a few getter functions to the Closure and/or Lambda classes.
• It's possible that the SPL programmer puts something on the left of the @ operator which is not actually a function. Gasp! Rather than crashing unceremoniously with something like a IndexOutOfBoundsException, your code should call the error() method from the Interpreter class to properly report the error in SPL.
• We are ignoring the function return values, but your int evaluate(Frame env) method in the FunCall class has to return some integer or else the compiler will be angry. Just return your favorite number; we will replace it in the next part.
• Make sure you don't break anything that used to work before! You can always run ./runtest.sh Lab07Test to check that everything from the starter code still works.

After this, you should be able to do:

./spli.sh
Fancy SPL Interpreter
Enter SPL statements. Ctrl-D to exit gracefully.
spl> new f := lambda x {
...> write 1 + 2;
...> "We did it!"
...> };
spl> new trash := f@100;
3
We did it!
spl> trash := lambda y { new c := 0; while c < 3 { "tick" c := c + 1; } } @ 99;
tick
tick
tick
spl> write 5 @ 6;
ERROR: Closure with id 5 does not exist

Exercises

3. Get function calls to work, without arguments or return values.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
To run the public tests yourself, run: ./runtest.sh Ex3Test

7 Function arguments and return values

Now it's time to get function calls fully working. If you've done everything else correclty so far, all this will require is some careful footwork in the int evaluate(Frame env) method of the FunCall class.

You will need to think carefully about when and in which environment each of the following happens:

• Creating a new Frame
• Evaluating the argument
• Binding the argument to the parameter name
• Executing the function body
• Retrieving the return value

After this, all kinds of fancy functions should work in SPL. Here are a few you can try to test your code.

roche@ubuntu$ ./spli.sh
Fancy SPL Interpreter
Enter SPL statements. Ctrl-D to exit gracefully.
spl> new ignored := lambda x { write x * 2; } @ -5;
-10
spl> write lambda unused { ret := 1+2+3+4+5; } @ false;
15
spl> new fun := lambda a { ret := lambda b { ret := 100*a + b; }; };
spl> write fun@5@6;
506
spl> write fun@33@4;
3304
spl> write fun@200@(fun@5@6);
20506
spl> new pow := lambda a { ret := lambda b {
...> ifelse b = 0 { ret := 1; } { ret := a * pow@a@(b-1); }
...> }; };
spl> write pow@10@7;
10000000
spl> write pow@2@20;
1048576
spl> write pow@(-1)@101;
-1
spl> write pow@(pow@2@3)@(pow@4@1);
4096

Exercises

4. Get function definitions and function calls to work with proper lexical scope and correct arguments and return values.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
To run the public tests yourself, run: ./runtest.sh Ex4Test

8 Expression Statements

Right now, the following program should give an error:

new f := lambda x { write x + 5; };
f@3;

What's going on? Well, the problem is that a function call like f@3 is an expression but not a statement. Now that we have function calls, we might want to have an expression as a statement all by itself, without having to write its result.

Your job in this part is to make this possible. This shouldn't involve any intricate or tricky code, but will require you to change things at all levels in the interpreter: adding a rule to the ANTLR parser grammar; adding a function to one of the builder classes; and creating a new class in the AST hierarchy.

(Once again, you only have to add one or a few lines in each of those places. If you find yourself making changes in lots and lots of files, or adding many lines of intricate code, step back and ask yourself if there is a better/simpler way!)

After this, examples like these should work in your interpreter:

roche@ubuntu$ ./spli.sh
spl> new f := lambda x { write x + 5; };
spl> f@3;
8
spl> 100;
spl> x * 7;
ERROR: No binding for variable 'x'
spl> new countDown := lambda start { if start > 0 { write start; countDown@(start-1); } };
spl> countDown@5;
5
4
3
2
1
spl> countDown@2;
2
1
s

Exercises

5. Allow semicolon-terminated expressions as single statements.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
To run the public tests yourself, run: ./runtest.sh Ex5Test