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:

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*:

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.