Lab 8: Functions and Dynamic Scope

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 23. 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 to keep things running smoothly.

# Warm-up: Some more SPL coding!

Like last week, we are going to start by writing a small SPL program that, by the end of the lab, we should be able to correctly execute using our interpreter.

As an example of the kind of thing you need to do for this part, here is an SPL function that uses recursion to compute the value of n! - that is, n*(n-1)*(n-2)*...*1.

```# Computes n!
new fact := lambda n {
ifelse n <= 1
{ ret := 1; }
{ ret := n * fact@(n-1); }
};

# This should print 5! = 120
write fact @ 5;```

Notice the structure of the `lambda` in SPL: we have the keyword `lambda`, followed by the name of the SINGLE argument (all functions are unary in SPL), followed by a block of code in curly braces for the body of the function. Remember also that `ret` is a special name that must be assigned to the return value.

The way functions are called is a little unusual: we use the FUNARG operator `@`, which you should know has highest precedence and is left associative. I assume you know what that means by now!

## Exercises

1. Write SPL code for a recursive function called `fib` that takes a single argument `n` and computes the n'th Fibonacci number. So for example, after reading your code, typing `write fib@10;` should produce 55.
Save this code in a file called `ex1.spl`, to be included with your submission.
(No tests to submit for this exercise.)

# Dynamic Scope with Central Reference Tables

In this part of the lab, we are going to extend the `SymbolTable` class to implement proper dynamic scoping rules. Recall from class that a CRT contains two parts: a mapping from strings to stacks of values (the bindings), and a stack of sets of strings (the variables in scope).

For this part of the lab, you just need to get dynamic scoping to work correctly with blocks and if/else/while statements in your SPL interpreter. You should do this by augmenting the `SymbolTable` class with some additional data structures, as well as two new methods, `startScope()` and `endScope()`, which do the obvious things. In what follows I will briefly outline one way of getting this working. But feel free to solve this in any reasonable way that makes sense to you.

It may be useful to reference the following C++ Standard Template Library APIs: stack, map, set.

## Suggested Steps

Even if you don't follow all the steps like I suggest, I strongly recommend that you test your code often as you go along. The key to making a big change like this one successful is to do it in small, manageable steps, making sure everything works before you go on.

• Add two new methods `startScope()` and `endScope()` to the `SymbolTable` class. For now, these methods do not need to do anything except print out a debugging statement like "entering/leaving a scope". These should both be `public` methods in the `SymbolTable` class, and they should both return `void` and take 0 arguments.
You will need to call each of these two methods once in your `main` method, to start and end the global scope. They also need to be called when we enter and leave a block (with curly braces). Eventually, there is a third place to create and leave scopes - when function calls are made - but that's the next part.
• Now turn the `bindings` field in `SymbolTable` from a plain old map into a map of stacks. So you will have to `#include <stack>` at the top of the file, and the new type of `bindings` will be
`map<string, stack<Value> >`
CAREFUL! The space between the last two `>`'s is absolutely necessary so that the two aren't read as a single `>>` operator. DAMN YOU MAXIMAL MUNCH!
You will now have to change the three access functions - `lookup`, `bind`, and `rebind` - to work a bit differently. `lookup` and `rebind` should be accessing the top of the stack for the given identifier, and `bind` should be pushing a new value to the top of the relevant stack.
Oh and by the way, your error conditions will definitely have to change. For example, it's no longer necessarily an error to bind a variable that's already bound - only if it's already bound in the current scope. Actually, your CRT doesn't have enough information to do this kind of error checking yet, so maybe cut out some of the error checking, just for now.
• OK, now everything is good, but we're not really implementing scope because nothing ever gets popped off the stacks of bindings! As a first step, let's start saving the names of things that are pushed on. Create a new field in `SymbolTable` called `scopeVars` that is a stack of sets of strings - i.e., has type `stack< set<string> >`. Every time you start a new scope, you should push a new empty set of strings onto `scopeVars`. And every time a new binding gets created, you should insert the name of that identifier onto the top set in `scopeVars`.
Finally, you will have to add code to `endScope()` that goes through all the identifiers in the top stack, and for each one pops off and removes the top element of the relevant stack in `bindings`. Unfortunately, the only way to do this requires you to use a C++ iterator type. Here's a summary of how it works:
• An iterator is an abstraction of an array pointer. Let's say we had an array of strings `A` and we wanted to print out each one. You could do this with the following C++ code:
```// Here we define the array
const int len = 3;
string A[len] = {"one", "two", "three"};

// The type of the iterator is "pointer to a string",
// and it starts by pointing to the first thing in A.
string* iter = &A[0];

// When the iterator is "len" spots past the beginning, it's no
// longer pointing into the array, so we're done.
while (iter != A + len) {
// We must dereference the iter with a "*" to get back a string
cout << *iter << endl;
// Now increment the iterator to point to the next thing.
++iter;
}```
• Now here is how we would do exactly the same thing over a set of strings `S` rather than an array. Make sure you read and understand each line, and how it compares to the example above:
```// Here we define the set
set<string> S;
S.insert("one"); S.insert("two"); S.insert("three");

// This type is taken from the set class, but it acts just like
// a pointer to a string - trust me!
// S.begin() gives a pointer to the first thing in the set.
set<string>::iterator iter = S.begin();

// We compare against S.end() to determine when we're no longer
// pointing into the set, i.e., we're done.
while (iter != S.end()) {
// We must dereference the iter with a "*" to get back a string
cout << *iter << endl;
// Now increment the iterator to point to the next thing.
++iter;
}```
• Now you need to do this, where for you the set `S` will be the top set in `scopeVars`, and of course you won't just be printing out each name but popping the top Value from the corresponding stack in `bindings`. Do it!
Hints: Do this piece by piece, with plenty of debugging statements to make sure the right things are happening. Implement the `endScope` part last.
• Finally, implement proper error checking in `lookup`, `bind`, and `rebind`.
• Test, test, test! Remember that my sanity checks are not exhaustive - it's up to you to make sure that your own code is correct!

## Exercises

1. Get dynamic scoping with basic control structures working. After this, a program such as
```{ new x := 1;
if x = 1 {
new x := 2;
write x;
}
write x;
}```
should work and print 2 followed by 1.
You are required to submit at least four tests for this exercise.

# Lambdas and Function Calls

Now it's time to actually get function calls to work. This will require you to implement the `eval()` methods in the `Lambda` and `Funcall` classes. My suggestions are below, but remember that you are free to go your own way!

## Tips

• Evaluating a lambda is the really easy part - it just has to return a pointer to itself! Hint: look at this page.
• The real fun is in `Funcall`. Here are all the ingredients you need to evaluate a unary function:
• The name of the variable ("formal parameter")
• The value of the argument ("actual argument")
• The body of the function
• The return value
Think about where all these pieces are going to be. Some of them are in the `Funcall` class, some are in the `Lambda` class, and some come from the CRT from the previous part. You might want to look at an AST for a simple function definition and call, and trace out what should happen in the function call, step by step.
• Once you think you know what should happen, go ahead and try implementing the `eval()` method in `Funcall`. Start by ignoring arguments and return values, and just get simple functions like
`lambda x { write 5; }`
to work. Then get the arguments working, then get the return values, and last of all get the scope started and ended properly.
• Code like
`write 1@2;`
will probably cause your interpreter to crash in a very bad way. Unfortunately, there's not a lot we can do about this at the moment (since we're not doing any type checking yet). So you just have to live with this kind of crash (don't test for it!).
• Hint: Take a good look at the `Value` class in value.hpp. You'll see that a Value object can store three things: a number, a boolean, or a pointer to a `Lambda` object. You've already used the first two; now you're going to use the other one. You'll also notice that creating a `Value` object with no arguments causes it to be "unset".
• Big hint: When everything works, you should have two recursive calls to `eval` and two calls to the `bind` method in `SymbolTable`.

## Exercises

1. Get function definitions and function calls to work. After this, you should be able to execute your `ex1.spl` program and compute Fibonacci numbers.
You are required to submit at least six tests for this exercise.

# Expression Statements

Right now, the following program should give an error:

```new f := lambda x { write x + 5; };
f@3;```

What's going on? Well, the problem is that a function call like `f(3)` is an expression but not a statement. Now that we have function calls, we might want to have an expression as a statement all by itself, without having to `write` its result.

Your job in this part is to make this possible. This will involve adding a new subclass to the `AST` hierarchy - you might want to call it `ExpStmt`. It should be a subclass of `Stmt` that only has one part - an expression! Executing the statement will just mean evaluating the expression and throwing away the result.

## Exercises

1. Allow semicolon-terminated expressions as single statements. This will require adding a new grammar rule to the `spl.ypp` Bison file as well as a new class to the `ast.hpp` file.
You are required to submit at least two tests for this exercise.

# OPTIONAL: More arguments, more returns

Important: Please save/submit your work before starting on this part. It is highly likely to break your code. I will be mightily impressed if you get everything here working, though. Keep in mind that you should be able to implement these changes with complete backward compatibility - that is, previously existing SPL programs should still work.

## Exercises

1. (OPTIONAL) Allow multi-argument function definitions and function calls. You decide the exact syntax you would like for it, but you will probably need a new token to separate arguments, some new grammar rules, and significant changes to `Lambda` and `Funcall`. You might want to start with just two arguments instead of one.
2. (OPTIONAL) Okay, I'm sure no one is going to do this. But just in case... Add the ability for functions to return multiple values. You can decide the exact syntax for this, but you might allow programs like:
```{ new a := 0;
new b := 0;
new squareAndCube := lambda x {
new sqr := x * x;
ret := sqr, x*sqr;
};
a, b := squareAndCube(3);
write a; # Should print 9
write b; # Should print 27
}```