Lab 10: Type Checking

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 lab10. The following files must be included:

Most of your work for this lab will be in value.hpp value.cpp, builtin.hpp, builtin.cpp, and spl.ypp.

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

Introduction

We saw in class last week that our SPL interpreter is most definitely not type-safe. This means we can do all kinds of nasty and meaningless things and the compiler won't even notice:

new f := lambda n { write 5; }; # Look ma, no return value!
write f(12) * 17;
5
0
write f - 20;
164221140
write f and 16;
false
new x := true;
write x < false;
true
write (x < false) + 20;
21
write x(5);
Segmentation fault

In today's lab we will implement type safety in our SPL interpreter. This will explicitly dis-allow all the terrible things in the example above, with nice informative error messages for the poor SPL programmer.

Actually, most of the machinery for the dynamic type-checking that we're going to do is already in the interpreter. Do you know where?

Then we'll look at the concept of built-in functions and make a few useful ones.

Dynamic Type Checking

Recall that dynamic type checking requires that type information is stored alongside values in the running program. Every time we execute a statement or evaluate an expression, the types of all values are checked for compatibility, depending on what the statement is.

If you look at the Value class, you will see that we have been storing this information all along! Each Value object has a field type of type VType, which is also defined in the value.hpp file.

To make your life easier, I wrote a function to print out VTypes in a nice way. To use it, do the following:

Exercises

  1. Add basic type checking to the "getter" methods num(), tf(), and func() in the Value class. So for instance, before returning the integer value, num() should confirm that the type of the object is actually NUM_T. If not, it should display a nice error message, like 
    Type mismatch: expected NUM, got BOOL
  2. Make sure that type checking works throughout your SPL interpreter. This might require more or less work from you, depending on how far your code has diverged from my solutions. Basically, every one of the nasty things that you see in the examples from the Introduction above should give nice error messages, and never seg faults. (You don't need a separate line in features.txt for this exercise.)

Built-In Functions

A built-in function in a programming language is one that looks like a regular function, but is not written in the language itself but rather hard-coded into the compiler or interpreter.

So how will this work? How can we trigger the execution of arbitrary C++ code within an SPL program? Let's look at an example step by step. We'll write a built-in function sqr to compute the square of a number. Of course this is a really stupid example because we could just write the function in SPL like this:

new sqr := lambda n { ret := n * n; };

Hopefully the stupidity of this example will make the concepts more clear for when you have to do more interesting functions. Now the first thing we will need is a new kind of Stmt node whose exec method will do whatever it is our built-in function is supposed to do. This new node type will correspond to the abstract class Builtin.

I've actually written this for you already: download the files builtin.hpp and builtin.cpp, copy them to your lab10 directory, and have a look. You will see the Builtin abstract class, as well as the Sqr subclass containing the functionality for squaring numbers. Important to notice is the getParam() function in the Builtin class. This gets the name of the argument to this built-in function (which is just "x" by default). The actual code for squaring is in the exec method in Sqr, of course.

Now how do we get this into our interpreter so we can call sqr from a SPL program and have it execute this node? The first thing to do is to make a Lambda whose body contains this new kind of statement. Specifically, we will make a little AST that looks like this:

The odd thing is that, rather than the scanner and parser generating this AST, we will create it manually, perhaps in the main function in spl.ypp. The following lines will create the little AST above:

Id* param = new Id("x");
Sqr* sqr = new Sqr;
Block* sqbody = new Block(sqr);
Lambda* sqlam = new Lambda(param, sqbody);

So now we have a Lambda node for our built-in function. All that remains is to give our baby a name and put it into the global Frame so it can be accessed anywhere. The following code will do that:

Closure sqc;
sqc.function = sqlam;
sqc.environment = NULL;
global.bind("sqr", sqc); // Note: global is the name of the global frame.

Exercises

  1. Download the files above and add the lines to your main so that the "sqr" built-in function works in your SPL interpreter just like any other function. Important: you probably will want to add "builtin.cpp" to the "IMPLS" variable in the Makefile.
  2. All that code in main is pretty ugly, and it's going to get way worse when we start adding more built-in functions. So write a C++ function getBuiltinClosure that takes any Builtin* pointer and returns a Closure for that function. This prototype for this function should go in builtin.hpp, and its implementation in builtin.cpp. Then you should be able to replace the code you added to main with one or two lines, using your new function. (Note: you don't need a line in features.txt for this exercise.)

User-Driven Type Checks

So from the first part, we have type safety implemented in the interpreter. But there is still no way for the SPL programmer to do their own type checks, because the type information is hidden from the programmer.

We'll change this by writing three built-in functions isnum, isbool, and isfunc, that take any value and return true or false to indicate if that value has the stated type. After this, we should be able to write crazy functions like 

# Arbirary doubler. Why? Because we can!
new doubler := lambda any {
  if (isbool(any)) { ret := true; }
  else {
    if (isnum(any)) { ret := any + any; }
    else { ret := lambda x { any(any(x)); }; }
  }
};
  1. Add the built-in functions isnum, isbool, and isfunc to your interpreter.
  2. Add another built-in function to do something interesting. Be sure to document what the function is called and what it does in your features.txt file.
  3. (OPTIONAL - 0.5 bonus points if your name is Yates) The optional problem 4 from last week's lab asked you to write cons, car, and cdr. You can see my solution to this in the file ex4.spl, where I also define a few more goodies like nil for the empty list. Now that we have user-driven type checking and built-in functions, much more is possible here! Try writing a curried function called list that builds up a list, terminated with nil, like 
    list(1)(2)(3)(4)(nil);
    You should be able to write this function in SPL. Next, try adding a built-in called display that prints out a list all nice, on one line, like 
    [1 2 3 4]