Lab 9: Lexical scoping with frames

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:

Besides these, you can also submit an .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.

  1. Download the following three files into your lab09 directory: These are, respectively, the header file, implementation file, and a small tester program for the Frame class.
  2. Delete the SymbolTable files st.hpp and st.cpp.
  3. Edit the Makefile. First, change the 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.


  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.
    Note: for full credit, you should give meaningful error messages when these methods are used inappropriately.


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.)

Putting it together

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:


  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.


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-helper (+ m 1)
                    (+ fib-of-m fib-of-m-1)
  (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!


  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 ex3.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.