1 Starter Code

The starter code for this week's lab is the same as the solution for the previous lab, with the only addition being the builtins.hpp header file, which is what you will largely fill in for today's lab. You can start with your working solution from the previous lab, or download these files to start fresh with the sample solutions.

You should already have a shared git repository spl. To get the starter code for today's lab, cd to your si413/spl directory and run these commands:

git pull starter main
git pull

You should now have a folder like si413/spl/lab09 with the starter code for this lab and a handy script to submit your code.

You can also browse the starter code from the Gitlab page (USNA intranet only).

2 Introduction

The previous lab was a big one - getting lexical scope with frames and closures working correctly in SPL. This week we will build on that work without radically changing the functionality of the interpreter.

We will first add run-time type checking to the SPL interpreter to (hopefully) avoid some nasty segfaults and other strange behavior that's possible in our untyped language.

The second part of the lab will add some built-in functions to do new and useful things that wouldn't be possible within the SPL language itself.

Next, we'll see how to make more use of SPL functionality (specifically the frames and closures you worked so hard on last lab) to simulate multi-argument functions using single-argument functions.

3 Dynamic Type Checking

Right now your SPL interpreter is most definitely not type-safe. This means we can do all kinds of nasty and meaningless things and the interpreter 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

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

   
   
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 now and check the autotesting so far! Just run ./submitme.sh from your lab directory.

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

Your first task will be to add a sqrt function which takes any non-negative integer and returns the floor of its square root. In C++, the efficient way to do this is by using the sqrt function from the <cmath> library, but there's no way to directly call this from SPL code. That's were your built-in comes in!

spl> write sqrt@25;
5
spl> write sqrt@10;
3
spl> write sqrt@(5*5 + 12*12);
13
spl> write sqrt@8 * sqrt@8;
4

Notice that sqrt looks and behaves like any other user-defined function, but in fact it's calling special C++ code internally, rather than calling user-defined SPL code.

Built-ins should really look and act like any other function in SPL, meaning they should be stored as Closure values in the global symbol table, and they can be re-assigned and passed around like any other name:

spl> write sqrt;
closure
spl> new f := lambda x { ret := x*x; };
spl> if read < 0 { f := sqrt; }
read> -1
spl> write f@100;
10

How exactly this works is up to you. But I will offer a few guidelines:

• You will need to make some new classes. Put them in the file builtins.hpp, a skeleton for which is provided as part of this lab's starter code.
• You shouldn't really need to make any changes in Lambda or Funcall themselves - those should keep working as before.
• You will probably want to make a new kind of Stmt node for evry new builtin, with an exec(Frame*) method that actually does whatever the builtin is supposed to do.
• Your built-in function will still have to use the Frame* passed to its exec method, both to get the argument value and to set the return value.
• If you want to do this without changing Funcall::eval(Frame*), then you'll need to pick a name for the parameter to your builtin function, even though the user will never ever see this name! Think about where this name needs to be so that Funcall your builtin both agree on using the same name for the argument value.

Exercises

3. Add a sqrt builtin function as described above.
   Hint: you will need to do a #include "builtin.hpp" in your spl.ypp file, to access the new class(es) you write in builtin.hpp.
   Hint: you should not need to change the parser or scanner (i.e., the regexes, tokens, or grammar) to make this happen.
4. Add a built-in function called rand that takes an integer n and returns a random number from 1 up to n (inclusive). You can use either C-style random number generation or the newer C++ random number generators. Be sure to seed your random number generator when your program starts so that the results are not the same every time the interpreter runs.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.

5 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

spl> # 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); }; }
    }
};
spl> write doubler @ false;
true
spl> write doubler @ 10;
20
spl> write doubler @ sqrt @ 81;
3

Exercises

5. Add the built-in functions isnum, isbool, and isfunc to your interpreter. Try to do this without repeating too much code!
6. Add another built-in function to do something interesting. Submit a README.txt that documents what the function is called and what it does.

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.

7. (OPTIONAL) The optional problem 7 from the previous lab asked you to write cons, car, and cdr. You can see my solution to this in the file cons.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 list.spl with your solution.

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.

6 Currying

Remember your Fibonacci function from last lab? It probably wasn't very efficient. Ages ago, we saw something like the following to compute Fibonacci numbers very efficiently in Scheme:

(define (fib n)
  (define (fib-helper i fib-of-i fib-of-i-plus-one)
    (if (= i n)
        fib-of-i
        (fib-helper (+ i 1)
                    fib-of-i-plus-one
                    (+ fib-of-i fib-of-i-plus-one))))
  (fib-helper 0 0 1))

So what's stopping us from doing this in SPL? Our functions only take one argument! We can get around this with a technique known as currying after its (perhaps) discoverer, the logician Haskell Curry.

The basic idea is that we can simulate a multi-argument function by a series of function calls to one-argument functions. This is easiest to illustrate with a simple example. Say we want a function f that just takes two numbers and adds them up. Since we can't write a two-argument function, we can write a one-argument function that returns another function, one that takes the second argument! Specifically, we can write:

new f := lambda a {
  ret := lambda b { ret := a + b; };
};

write f@3@4; # Should print 7

See what's happening? If you don't, try drawing out a trace with closures and frames. So we really don't lose anything by restricting to one-argument functions, at least when functions are first class!

Exercises

8. (OPTIONAL) Write a fib function for SPL that uses currying to make the operation run in linear-time like the Scheme example above.
   As before, we define fib@0 = 0 and fib@1 = 1. And similarly to before, write a line or two of SPL code after your function definition to read in an integer from the user, then write out the result of calling your fib function on that integer.
   Submit your function in a file called fastfib.spl.
   Note: This should already work in your interpreter from last week!

   roche@ubuntu$ ./spl fastfib.spl
   read> 10
   55
   
   roche@ubuntu$ ./spl fastfib.spl
   read> 42
   267914296

Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.