This is the archived website of SI 413 from the Fall 2012 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
This lab is due at 0900 next Tuesday, October 30.
It should contain all the files in the starter code listed below,
as well as a subfolder called tests with your tests.
See the submit page for more info.
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.
Here's the program for a simple checking account object that we saw in Homework 7, translated of course into SPL:
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.
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.
lookup, bind,
and rebind, in the Frame class. When you are done, the
frame-test program should make without errors and run
successfully.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.
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:
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.)
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.exec() functions
(and function calls!) in all statements to take a single argument, which
is a pointer to a Frame. Sub-steps:
virtual void exec()
method in the Stmt class to be
virtual void exec(Frame* env)(or whatever you want to call the frame).
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.
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!
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.
eval() in
the Exp class, and everywhere that calls it. (You should still
leave Funcall alone, though.)
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.
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.
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 a new forward declaration for the Frame
class above this struct, which just looks like:
class Frame;
Now there are three places where you will need to incorporate closures,
replacing situations where we previously just used a Lambda*:
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.
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.
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.
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!
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.
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.is_cons.