Lab 10: Type Checking

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, 14 November. It should be submitted as "413 lab 10", 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 and the new file builtin.hpp to keep things running smoothly.

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:

spl> new f := lambda n { write 5; }; # Look ma, no return value!

spl> write f@12 * 17;
5
0

spl> write f - 20;
164221140

spl> write f and 16;
false

spl> new x := true;

spl> write x < false;
true

spl> write (x < false) + 20;
21

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

If you want to do error checking in a consistent way with the rest of SPL, you will have to add the following declarations after the other #include's near the top of the value.hpp file:

#include "colorout.hpp"
extern bool error;
extern colorout errout;

Recall, the global variable error should be set to true whenever an error is detected, to communitcate to the rest of the interpreter that an error has occurred. errout is the name of a special output stream that will print in red, so you know that it's an error.

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 UNSET
    

    (No submitted tests for this exercise.)
  2. Make sure that type checking works throughout your SPL interpreter. Basically, you should never get the nasty behavior like in the examples above; instead there should be informative error messages.
    Submit at least four error tests for this exercise. Remember that error tests end in .err and don't have any semicolon line or output. All they test is whether the given input produces a nice error condition.

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, in the builtin.hpp file in today's starter code. Take a look at it. 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. This is set to "x" by Sqr's constructor. 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. I have already written the Sqr class for you in the starter code, so you could create that object with a line like

Sqr* sqr = new Sqr;
This will also create the null statement node below the sqr node in the AST. You will also have to construct a new Id node, a new Block node, and finally a new Lambda node, to complete that AST. Each of the constructors for these classes takes arguments according to what its children are; you can look at the constructor definition in the ast.hpp header file to confirm.

So now we have a Lambda node for our built-in function. The next step is to create a new Closure object that will hold this function and allow it to be executed. The func of the Closure will be the new Lambda object from above, and the env of this Closure can actually be NULL, since the built-in doesn't need to access any global variables.

All that remains is to give our baby a name so it can be accessed, something like:

Closure sqc;
// Your code to set the func and env of the Closure...
global.bind("sqr", sqc); // Note: global is the name of the global frame.

Exercises

  1. Follow the directions above to add code in your main function so that the "sqr" built-in works in your SPL interpreter just like any other function. Include at least 2 tests for this exercise.
    Hint: you will need to do a #include "builtin.hpp" in your spl.ypp file.
  2. Built-in functions are useful when they do something which otherwise would not be possible in the language. Add a built-in function called pause that takes an integer argument and makes the execution pause for that number of seconds. So for example, doing
    pause@3;
    Should just make the interpreter "hang" for 3 seconds and then display the prompt again.
    In C++, you can make this happen by using the sleep command from the unistd.h header file; see this page out of the GNU libc manual for the full details.
    (No tests required 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 {
  ifelse isbool@any 
    { ret := true; }
    { ifelse isnum@any 
        { ret := any + any; }
        { ret := lambda x { ret := any@(any@x); }; }
    }
};
write doubler @ false;   # true
write doubler @ 10;      # 20
write doubler @ sqr @ 3; # (3^2)^2 = 81

Exercises

  1. Add the built-in functions isnum, isbool, and isfunc to your interpreter. You might notice yourself repeating a lot of code. Submit at least 3 tests for this exercise.
    Hint: Maybe you should write a helper function to help you create new built-ins?
  2. Add another built-in function to do something interesting. Submit a file ex6.txt that documents what the function is called and what it does. (No tests required for this exercise.)
  3. (OPTIONAL) The optional problem 5 from last week's lab asked you to write cons, car, and cdr. You can see my solution to this in the file ex5.spl, where I also define a few more goodies like null 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 @ null;
    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]

    If you choose to accept this challenge, submit a file called ex7.spl with your solution. I suggest you refer to my ex5.spl from last week's lab solutions.