Lab 9: Lexical scoping with frames

This is the archived website of SI 413 from the Fall 2013 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

This lab is due at 2359 on Thursday, 7 November. It should be submitted as "413 lab 09", with the files named properly according to the submit script. See the submit page for details. You are highly encouraged to submit whatever you have done by the end of this lab. Remember that duplicate submissions are fine; I will just grade the latest one when the time comes.

# Starter Code

The starter code for this week's lab is... the solution to last week's lab. You can stick with your own solution or use mine (or some combination thereof). But in either case you should download the updated Makefile, as well as frame.hpp and frame-test.cpp to keep things running smoothly.

# Introduction

Here's the program for a simple checking account object that's eerily similar to what you saw in the last homework:

new account := lambda a {
new withdraw := lambda x {
ifelse a < x
{ ret := false; }
{ a := a - x;
ret := true;
}
};
ret := withdraw;
};

new A := account@10;
new B := account@12;

write A@11;
write B@11;

If you try this in your current SPL interpreter, you will get an error (hopefully!) telling you that "a" is not in scope. This is because the argument to account is accessed after the function returns, inside the first-class function that gets returned.

Today we're going to implement proper lexical scoping with frames and closures in SPL. By the end of this lab, you should be able to run the program above just as we did on the board in class.

# Frames

Recall that a lexical frame consists of a simple symbol table (mapping of strings to values), plus a pointer to the parent frame. We are going to replace our old SymbolTable class with one called Frame that represents a lexical frame.

Because I'm so nice, I've provided starter code for the Frame class, in the file frame.hpp above.

The frame-test program is a means I've provided you with to test your Frame implementation without having to incorporate it into the whole SPL interpreter right away. Use it to guide your development, and feel free to modify it; it won't be submitted.

## Exercises

1. Implement the three methods lookup, bind, and rebind, in the Frame class. When you are done, the frame-test program should make without errors and run successfully.
For full credit, you should give meaningful error messages when these methods are used inappropriately.
(No tests to submit for this exercise)
Hint: lookup and rebind will be the compilcated ones, because they have to search for the variable in every frame all the way up to the root (global scope). I recommend you write these functions recursively, although of course you don't have to.

# Dynamic Scope with Frames

Okay, now for the scary part: refactoring your existing SPL interpreter to use Frames instead of the old SymbolTable. The basic idea is that you will have to add an argument of type Frame* to every eval and exec method, the argument representing the current referencing environment.

You can implement this change however you wish. Here's what I would do:

• First, go ahead and delete the st.hpp file, since you won't need it anymore. Then you will have to change any #include "st.hpp" to #include "frame.hpp". (In my starter code, this only shows up in ast.hpp.)
• Now just get something compiling. There will be a bunch of references to ST and so on that won't work anymore. Comment all of these out, so that you get an interpreter that doesn't work correctly but at least compiles.
• Next you want to change all the exec() functions (and function calls!) in all statements to take a single argument, which is a pointer to a Frame. Sub-steps:
1. Start by changing the virtual void exec() method in the Stmt class to be
virtual void exec(Frame* env)
(or whatever you want to call the frame).
2. Next fix up your main method in spl.ypp Where you used to call ST.startScope(), you want to instead declare a Frame object for the global frame. Then re-write the two places where tree->exec() shows up so that they get a pointer to this global Frame.
3. You'll still have a big 'ol pile of compiler errors, which you need to fix. Basically, you're searching for every place the string exec() appears in ast.hpp and ast.cpp. and fixing them to take a single argument. This seems daunting, I know, but making good use of your text editor will help greatly!
4. Just comment out everything in Funcall that gives errors, for now, and take care in the Block to make sure it's working correctly. Ultimately, the only three places where a new Frame will get created is in your main, in Block, and in Funcall.
• Next do the same thing as above, but for the eval() in the Exp class, and everywhere that calls it. (You should still leave Funcall alone, though.)
• Now go back all the places where ST.something was commented out and fix to use the Frame argument instead. (This should be pretty straightforward if your Frame class is correct!) At this point, everything should work except for function calls.
• Finally, go back and get Funcall to work. You shouldn't really have to shuffle anything around, just replace starting a scope with creating a new Frame, and adjust any other previous uses of ST to use the Frame instead.

## Exercises

1. Incorporate frames closures into your SPL interpreter to implement dynamic scope. After this is complete, you should be able to run everything just like last lab. (This should be highly unsatisfying after all your work! So keep going!)
(No tests to submit for this exercise)

# Closures and Lexical Scope

So far it seems like you've accomplished nothing; we had dynamic scoping done last week! But remember that Frames can be used to implement lexical scope as well, when we combine them with the use of closures. That's what's next

Remember that a closure is just a function definition plus its referencing environment. We will implement closures for the SPL interpreter as a new struct type. Go ahead and copy this definition to your value.hpp file, right below the forward declaration for the Lambdaclass near the top:

struct Closure {
Lambda* func;
Frame* env;

// This overloads the "==" operator so we can do comparison.
bool operator== (const Closure& other) {
return func == other.func && env == other.env;
}
};

You will also need to add new forward declarations for the Frame and Lambda classes above this struct, like:

class Frame;
class Lambda;

Now there are three places where you will need to incorporate closures, replacing situations where we previously just used a Lambda*:

• In the Value class. You will definitely want to replace the Lambda* in the union, the constructor that takes a Lambda*, and the function func() which returns a Lambda*. All of these will need to deal with a Closure object instead. You can also incorporate some additional "cosmetic" changes to the Value class if you like.
Hint: since closures are a basic struct with just 2 pointers inside, you don't have to worry about pointers to closures. That is, you can just store, return, and use things of type Closure, not Closure*.
• In the Lambda class. The eval(...) method won't be quite so simple any more, because now it should create (and then return) an actual Closure object.
• In the Funcall class. The func() method from the Value class no longer gives a Lambda* directly, but a Closure instead. So you will have to get the Lambda node out of this Closure before you can grab its variable name and function body. Oh, and you should probably do something with the environment part of the Closure object too! Think back to the examples from class and see if you can figure out where this should get used.

## Exercises

1. Incorporate lexical frames with closures into your SPL interpreter. After this is complete, you should be able to run SPL programs like the one in the introduction to this lab. Give yourself a big pat on the back.
All of the auto-tests are for this exercise. You must submit at least 5 test cases.

# Currying

Remember your Fibonacci function from last week? It probably wasn't very efficient. Ages ago, we saw something like the following to compute Fibonacci numbers very efficiently in Scheme:

(define (fib n)
(define (fib-helper m fib-of-m fib-of-m-1)
(if (= n m)
fib-of-m
(fib-helper (+ m 1)
(+ fib-of-m fib-of-m-1)
fib-of-m)))
(fib-helper 1 1 0))

So what's stopping us from doing this in SPL? Our functions only take one argument! We can get around this with a technique known as currying after its (perhaps) discoverer, the logician Haskell Curry.

The basic idea is that we can simulate a multi-argument function by a series of function calls to one-argument functions. This is easiest to illustrate with a simple example. Say we want a function f that just takes two numbers and adds them up. Since we can't write a two-argument function, we can write a one-argument function that returns another function, one that takes the second argument! Specifically, we can write:

new f := lambda a {
ret := lambda b { ret := a + b; };
};

write f@3@4; # Should print 7

See what's happening? If you don't, try drawing out a trace with closures and frames. So we really don't lose anything by restricting to one-argument functions, at least when functions are first class!

## Exercises

1. Write a fib function for SPL that uses currying to make the operation run in linear-time like the Scheme example above. Submit your function in a file called ex4.spl.
2. (OPTIONAL) Now write cons, car, and cdr functions for SPL. The cons should be a curried function of 2 arguments that returns a closure (i.e., returns a function). The function returned should examine its argument and either produce the first part of the cons pair or the second. The car and cdr functions will take in a consed pair (which is a closure, remember) and evaluate the passed in function passing it a special argument that indicates which part of the pair to return.
This should be mind-blowing.
If you want to go further, think about how to implement the empty list and a predicate function is_cons.
3. (OPTIONAL) A significant advantage of the Scheme program above is that it is tail-recursive. (Remember what that means?) Because Scheme optimizes for tail recursion, the function above will only use a constant amount of space. See if you can get any tail-recursion optimization in SPL. Talk to your instructor if you have questions about how to get started. Yes, this would be very difficult to do completely. No, I don't expect anyone to complete it.