• SI 413
• Calendar
• Classes
• Labs
• Project
• Resources
• Grades
• Submit

This lab contains only electronic parts, to be submitted using the submit program. For every exercise except Exercise 1, 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 lab08. The following files must be included:

• ex1.spl: Solution to exercise 1
• features.txt: Specification for testing exercises 2-7.
• Makefile: If I type make spl, this program should be compiled from source.

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

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 {
  if (n <= 1) { ret := 1; }
  else { 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.

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 89.
   Save this code in a file called ex1.spl, to be included with your submission.

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". You will need to call these each 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, 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.
• 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 stacks of strings - i.e., has type stack< stack<string> >. Every time you start a new scope, you should push a new empty stack of strings onto scopeVars. And every time a new binding gets created, you should push the name of that identifier onto the top stack in scopeVars. Finally, add code to endScope() that pops off all the identifiers in the top stack, one-by-one, and for each one it pops off and removes the top element of the relevant stack in bindings.
  Hints: Do this piece by piece, with plenty of debugging statements to make sure the right things are happening. Implement the endScope part last. And for now, assume the input SPL programs are perfect. Don't worry about trying to give proper error messages until everything is working correctly.
  Note: A stack of sets would probably be more appropriate here than a stack of stacks. The reason I'm not recommending it is that going through all the strings in a set requires the use of iterators, and I don't feel like explaining that. But feel free to figure this out and do it yourself!
• Now test, test, test!

Exercises

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

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 is 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.
• Big hint: When everything works, you should have two recursive calls to eval and two calls to the bind method in SymbolTable.

Exercises:

3. Get function definitions and function calls to work. After this, you should be able to execute your ex1.spl program and compute Fibonacci numbers.

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

4. 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.
5. Now you should be able to run your program from Exercise 1. So do it, and make sure everything is working correctly. (Nothing extra to turn in for this part.)

OPTIONAL: More on arguments

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

6. (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.
7. (OPTIONAL) Implement parameter passing by reference as well as by value. There are a few ways you could do this, but they will both probably require changes to the way Values and the Central Reference Table work. (For instance, you could add a new kind of value for an alias that just holds a pointer to another value.) Then of course you will also need a way to specify this in the syntax.
8. (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
   }