Try Firefox!

SI413 Lab 11: Adding lexical scoping with Frames

This lab is a continuation of Lab 8, Lab 9, and Lab 10. You'll want to start off with a Lab 9 solution, with the "expression-statements" from Lab 10 added on. In other words, we don't want to carry the WormWorld scripting forward. Probably your best bet is to copy your Lab11 solution, and simple delete the lines that deal with Worm World.

Our SPL interpreter up to this point has used dynamic scope, which most modern languages have avoided, because it's too easy to inadvertantly change the behavior of functions. Moreover, our interpreter doesn't realize complete and consistent semantics for SPL. In particular, there are problems with scope and functions returing functions:

{
new mkm := lambda a { res := lambda x { res := a*x; }; };
new f := mkm(10);
# The following should write out 30.
write f(3);
}
Undefined variable a
Our simple model for dynamic scope doesn't actually allow for this kind of thing. Therefore ... we're going to change our language (and implementation) to lexical scope. Fortunately we already know how to do this!

Step 1: Get rid of Worm World
Copy your Lab 10 solution into a new directory, and comment out or delete the code in the interpreter that involves WormWorld. For this lab we want the expression statements and immediate evaluation we added in Lab 10, but not WormWorld.

Step 2: Change Everything
Ha, ha just kidding .. kind of. As we discussed in class, in our model for implementing lexical scope, there is no single global data structure representing the referencing environment. Therefore, eval is going to have take two arguments, a pointer to the root node of the subtree we want to evaluate, and the referencing environment in which that evaluation will take place. So every call to eval will have to be changed to pass along referencing environments, and some of the cases will have to be modified to manipulate these referencing environments properly. First, however, we need to add a new structure, the Frame in order to represent referencing environments.

Frames
A frame is like its own little single-scope symbol table, augmented by a pointer to a parent frame. We went over this in great detail in class. So from an implementation perspective, a Frame object should be a map<string,int> plus a Frame*. When we want to add data and/or functionality to an existing object type, what do we use? If you didn't scream out (mentally, I mean) "inheritance" you should be ashamed. Yes, I want to derive a new class "Frame" from the class map<string,int> and add a data member "parent" of type Frame*.

Now, you haven't done object oriented programming in C++, just procedural programming, so I'm going to have to show you the syntax for this:

class Frame : public map<string,int>
{
public:
  Frame* parent;
};
This derives the new class Frame from map<string,int> and adds the field parent of type Frame*. In case you haven't been paying attention these last few years, this means that an object of type Frame is a map<string,int>. Anything you can do with a map<string,int> you can do with a Frame.So,

  1. Delete the definition of symTable from your interpreter. We don't want it anymore.
  2. Stick the defintion of class Frame in the appropriate place in your .ypp file.
  3. Change eval's prototype so that it takes a second argument of type Frame*, and if you don't call it env or something similar I'll have to kick you out of this major.
  4. Add the necessary statements in main to create the global frame (initializing parent to NULL) and pass that along to your call(s) to eval inside of main.
  5. The only way (for the moment) a new frame is ever created is when a function gets called, so comment out the _lambda and _funcall cases in your interpreter, and change the rest of the cases so that they function properly with this new Frame* parameter in eval. Since you commented out _lambda, you can assume for now that you only need to do a simple lookup in the given frame (no need to look in the parent frame). Start off making sure the _new, _id and write cases work properly ... you could even comment out the rest. So something like this:
    new a := 5;
    write a;
    
    ought to work. (Note: If you have Frame *p, and you want to look up name "foo", you have to write (*p)["foo"]: the (*p) gives the map object, rather than a pointer, which you can then subscript. The parens are needed to override precedence/associativity.) Then gradually add the rest (except _lambda and _funcall, of course). (NOTE #2: No curly braces should be needed around this code now!)

Important: Delete the call to addCloseScopeStmts and remove the _endscope case in eval. That mechanism was part of our dynamic scope implementation and doesn't make sense in this new context.

Lambda
Calling a function creates a new frame. However, before we can call a function we need to be able to evaluate lambda-expressions, and evaluating a lambda expression creates a closure. A closure consists of a pointer to a _lambda node and a pointer to the referencing environment in which that lambda node was evaluated. So you need to define a new class to represent a closure. Our hack will still be in force, so evaluating the lambda results in a new closure being created, and the pointer to that closure gets cast to an int, which is then returned as the result of the call to eval. Implement this carefully, you won't really be able to test it, since you'll need to deal with _funcall nodes for that.

Function calls
It's not called _funcall for nothing, all the fun is in the function call. This is where new referencing environments, i.e. new Frames are created. I'll repeat the steps and you implement them. At the function call
foo(expr)
here's what needs to happen:

  1. expr needs to be evaluated in the current environment to get the value of the argument
  2. foo needs to be looked up in the current environment to get the closure object we're going to apply to the afore-mentioned argument
  3. the closure references an environment (a Frame*): we need to create a new frame with that environment as its parent
  4. the closure references a _lambda node, we need to get the name of the parameter from that and add an entry in the new frame that binds that name to the argument value we computed in step 1.
  5. in the new frame we need to add an entry for res, which you can initialize to whatever you want.
  6. call eval with the a pointer to the body of the function defined by the _lambda node, and the new frame we created in step 3.
  7. return the value of res in the new frame.

Make sure the following works:

new sqr := lambda x { res := x*x; };
new x := 2;
write sqr(5*x);
100

Fix it
Now go back and fix your _id case so that this example
new k := 5;
new f := lambda x { res := k*x; };
write f(3);
15
... works, as well as the example at the beginning of the lab. In fact, you're going to have to fix _funcall and _asn for the same reason. My suggestion is that you define a function with this prototytpe:
// Returns pointer to first Frame containing reference to "name", NULL if none found
Frame* findFrame(const string &name, Frame* env);

This you can then use to fix _id, _funcall and _asn.

Other ways to create frames
Finally ... the bodys of while loops and if-statment then's/else's are a new scope, so therefore you need to create a new empty frome (with the parent set properly) to evaluate these while/if bodies in. Otherwise, variables declared within the loop/if body won't be local to that body. Here are some tests:
# Should print out 7 followed by 5.
{
new t:=5;
if (t = 5)
{
 new t := 7;
 write t;
}
write t;
} 

# Should print out 333 followed by 2
{
new t := 1;
if (1)
{
  write 333;
  t := t + 1;
}
write t;
}

# Should print out 8 followed by 5
{
new t := 5;
new fn := 1;
new fnm1 := 1;
new i := 2;
while(i <= 5)
{
  new t:= fn;
  fn := fn + fnm1;
  fnm1 := t;
  i := i + 1;
}
write fn;
write t;
}

Christopher W Brown
Last modified: Wed Dec 9 16:54:28 EST 2009