This lab contains only electronic parts, to be
submitted using the submit program.
For every exercise you work on,
add an entry to a features.txt file specifying
what you have working, and anything else the tester needs to know.
You can (and should) work with a partner for this lab, and if so, only one of you should submit.
Your electronic submission should come from a folder called
lab09. The following files must be included:
features.txt: Specification for testing.Makefile: If I type make spl, this program
should be compiled from source.
ex3.spl, if you complete Exercise 3..lpp Flex specification,
a .ypp Bison specification, and any number of .hpp
and .cpp files. (But probably, it will just be the same files
from the last lab, with st.* replaced with
frame.*.)
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).
Here's the program for a simple checking account object that we saw in the Class 17 Homework:
new mkcd := lambda a {
ret := lambda x {
if (a < x) { ret := true; }
else{ a := a - x; ret := false; }
};
};
new A := mkcd(10);
new B := mkcd(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 mkcd 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. Follow the instructions.
lab09 directory:
These are, respectively, the header file, implementation file, and a
small tester program for the Frame class.
st.hpp and st.cpp.
st.cpp on the
second line to frame.cpp. Then, add a new rule to
make the tester program as follows (make sure the tab really gets
copied as a tab and not as spaces!!!)
frame-test: frame-test.cpp ast.cpp frame.cpp ast.hpp frame.hpp value.hpp $(CXX) $(CPPFLAGS) $(CXXFLAGS) -o $@ frame-test.cpp ast.cpp frame.cpp
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. Feel free to modify it as you wish.
lookup, bind,
and rebind, in the Frame class. When you are done, the
frame-test program should make without errors and run
successfully.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.
Unfortunately, this requires changing the Value
class, since we no longer
want to store a function as a Lambda* but as a
Closure.
Fortunately, I've done this for you already. Download the new value.hpp and replace your existing one in your lab09 directory. (In the unlikely case that you've made modifications to this file from the original starter code, you might have to do some sort of creative merge.)
Now actually look at the thing you just downloaded and make
sure you see how to use the Closure type and how Closures are
stored inside Value objects.
(Nothing to submit or test for this part.)
Okay, now for the scary part: refactoring your existing SPL interpreter
to use lexical frames and closures. 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:
#include "frame.hpp" in ast.hpp instead of the old
symbol table file. Then 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.Frames. First, add a
Frame* argument to the base class methods for exec
and eval in Stmt and Exp, respectively.
In the main method in your spl.ypp file, create a global Frame
object, and pass in a pointer to that
Frame when you call tree->exec.
Running this should give nice "exec/eval not implemented" errors. Great!
exec, eval,
and evalAll
methods so that they take a Frame* argument, one by one.
(Of course, you will also need to modify every call to one of these
methods as well.) This seems daunting, I know, but making good use of your
text editor will help.Lambda and
Funcall. Lambda won't be too bad; it just has to return a
Closure now. Funcall will take a little bit of thought, but
the basic structure of will be the same as before.
Note: This section should be considered almost-optional. By that, I mean that it won't be worth very much in the grading compared to the previous sections.
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 ex3.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.