1 Starter Code

The starter code for this week's lab is a complete solution to the previous lab, plus some new testing files and two new files Value.java and Sound.java in the src/main/java/si413/spl/ directory.

If you want to start from your own working solution from the previous lab instead of my solution that's fune, but then be sure to copy over the test directory and the two new class files mentioned above before you get started.

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, the lab09.md file you will need to fill out, 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 (uncaught) errors 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.

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> write 1 and 2 and 3;
1
spl> new f := lambda n { write 5; }; # Look ma, no return value!
spl> write f@12 * 17;
5
0
spl> write f - 20;
-20
spl> write f and 16;
0
spl> new x := true;
spl> write x < false;
0
spl> write true * 3
3
spl> lambda arg { "should never be executed" ret := 17; };
spl> write x@true;
should never be executed
17

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.

We want to support four types in SPL:

• NUM: An integer, backed by a 32-bit signed int in Java
• BOOL: A boolean value, backed by a true/false boolean
• FUN: A function waiting to be called, which is represented by a (non-null!) instance of the Closure class that you used in the previous lab.
• UNSET: A special SPL value that... has no value. This will be the type which is initially bound to "ret" before a function call, and therefore the type that a function which has no return assignment, returns.

Once you finish this part of the lab, we should have support for all of these types, so the above examples will give proper error messages instead of garbage answers:

spl> write 1 and 2 and 3;
ERROR: Cannot convert NUM to BOOL
spl> new f := lambda n { write 5; };
spl> write f@12 * 17;
5
ERROR: Cannot convert UNSET to NUM
spl> write f - 20;
ERROR: Cannot convert FUN to NUM
spl> write f and 16;
ERROR: Cannot convert FUN to BOOL
spl> new x := true;
spl> write x < false;
ERROR: Cannot convert BOOL to NUM
spl> write true * 3;
ERROR: Cannot convert BOOL to NUM
spl> lambda arg { "should never be executed" ret := 17; };
spl> write x@true;
ERROR: Cannot convert BOOL to FUN

As a nice side-effect, we will also get more sensible displays when writing values that aren't integers, like this:

spl> write 1 < 2;
true
spl> new f := lambda x { "no return" };
spl> write f;
Closure#0
spl> new r := f@10;
no return
spl> write r;
UNSET

Today's starter code has a (mostly empty) class Value in the si413.spl package which is what you need to fill in to represent an SPL run-time value and its run-time type. After completing that class, you will need to make small tweaks to the code of almost every execute() and evaluate() method in the AST so that expression evaluations return Value objects instead of ints.

Exercises

1. Complete the Value.java class. Specifially, you will need to:
   • Add run-time fields to represent a value's actual value as well as one of the four types NUM, BOOL, FUN, or UNSET.
   • Complete the static fromX() and unset() methods to construct and return a new Value object with the given actual value and corresponding type.
   • Complete the getX() methods to check the type of the current object, and either return its underlying value, or call Interpreter.current().error(...) with an appropriate error message.
   • Complete the toString() method to pretty-print any value depending on its type.

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
   To run the public tests yourself, run: ./runtest.sh Ex1Test

2. Change the AST evaluate and execute methods so that every expression evaluation returns a Value instead of an int. Start by just fixing the AST nodes that don't have to touch the environment Frame.
   This is a big refactoring task, which involves making many small, straightforward changes in a lot of different files. There are multiple ways to approach it. What I did to be able to incrementally compile and test my work was this:
   • First change rename all of the evaluate methods to evaluateOLD with a single command-line call:

     sed -i 's/evaluate/evaluateOLD/g' ast/*.java

   • Then add a new method Value evaluate(Frame env) in the Expression base class, which is just like the evaluateOLD method in the base class except that it now returns a Value instead of an int.
     At this point, your code should once again compile and work, but obviously with no type checking.
   • Go through all of the AST nodes and replace the evaluateOLD calls and methods with evaluate, updating as needed to handle Value objects instead of ints.
     For this part, just work on the AST nodes that don't interact with the Frame; I recommend tackling things in this order:

     Num Write NegOp ArithOp Bool NotOp CompOp BoolOp
     Read IfElse WhileStmt Lambda ExpressionStatement

   At this point, you should be able to run SPL programs with type checking as long as they don't involve any variables or function calls, like:

   spl> write 1 < 2;
   true
   spl> write 1 < true;
   ERROR: Expected NUM, got BOOL
   spl> write 3 and false;
   ERROR: Expected BOOL, got NUM
   spl> 1 < true;
   ERROR: Expected NUM, got BOOL
   spl> if 10 { write 200; }
   ERROR: Expected BOOL, got NUM
   spl> while not 11 { write 300; }
   ERROR: Expected BOOL, got NUM

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
   To run the public tests yourself, run: ./runtest.sh Ex2Test

3. Finish up your type checking integration by first modifying the Frame class so that it stores Values instead of Integers for each binding, and then fixing up the remaining AST nodes which use Frames:

   Id NewStmt Asn FunCall

   Now you should be able to use the full SPL interpreter, with wonderful type checking everywhere.

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
   To run the public tests yourself, run: ./runtest.sh Lab07Test Lab08Test Ex2Test Ex3Test

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.

Often a built-in function will do something "special" that is not possible directly in the language itself, via direct interaction with the OS or hardware.

You will first create a rand built-in that returns a random number between 1 and the given argument. For example:

spl> write rand@2;
2
spl> write rand@2;
1
spl> write rand@2;
1
spl> write rand@100;
14
spl> write rand@100;
47

Next, you will create two more built-ins that make music! I have included a new class Sound.java in the starter code which deals with the underlying Java calls and waveform generation; you have to figure out to allow the SPL interpreter to access it.

To make sure sound is working for you, turn the volume to a reasonable level and run ./runmain.sh Sound - you should hear a short familiar tune!

Your first music built-in will be a 1-argument function beep which takes a desired frequency and plays a tone at that frequency for 1/4 second, like beep@440.

Your second music built-in will be a 2-argument function note which takes a desired frequency as the first argument and desired duration (in milliseconds) as the second argument, like note@440@750 to play a 440hz pitch for .75 seconds.

4.1 How to make builtins

Notice in the example above that rand looks and behaves like any other user-defined function, but in fact it's calling special Java code internally (using the Java.Random class), 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 rand;
Closure#0
spl> write beep;
Closure#2
spl> new something := rand;
spl> write something@100;
25
spl> something := beep;
spl> write something@100; # (makes a sound)
UNSET
spl> write something@150; # (makes a higher sound)
UNSET

How exactly this works is up to you. Here's how I did it:

• Create a new class in the AST for each new type of built-in. Your new class should be a sub-class of Statement and the special thing each built-in does will go in an overridden void execute(Frame env) method.
• Now you have to somehow tie your new AST node into the actual run-time interpreter. Normally the way AST nodes are created are from the parse tree builder methods, but not with built-ins, since they are supposed to be built in and not based on the SPL programmer entering them.
  To do that, I made a "mini-AST" for each built-in, consisting of:
  • An instance of the new builtin AST node class (which remember should be a sub-type of Statement)
  • A Lambda node with that new kind of built-in Statement as the body of the Lambda
  • A NewStmt node tying the desired built-in's name to the Lambda node as its value
• Now you just need to execute your mini-AST inside the global frame, once at the beginning of the program. A sensible place to do all this is inside the makeGlobal method in the Frame class.

Exercises

4. Add a built-in function called rand that takes an integer n and returns a random number from 1 up to n (inclusive).

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
   To run the public tests yourself, run: ./runtest.sh Ex4Test

5. Add a built-in function beep that takes an integer freq and plays a tone for 1/4 second at that frequency (in Hz).

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
   To run the public tests yourself, run: ./runtest.sh Ex5Test

6. Add a built-in function note that takes two arguments in succession, freq and duration, for the frequency (in Hz) and the duration (in milliseconds) of a tone to be played.

   Submit now and check the autotesting so far! Just run ./submitme.sh from your lab directory.
   To run the public tests yourself, run: ./runtest.sh Ex6Test

After you have this working, the following program should work to play Anchors Aweigh in a random key and tempo. Enjoy annoying your roomates!

new aweigh := lambda fund { ret := lambda tempo {
  new beat := 60 * 1000 / tempo;
  new do := fund;
  new re := fund * 9/8;
  new mi := fund * 5/4;
  new sol := fund * 3/2;
  new la := fund * 5/3;
  note@do@(beat*2);
  note@mi@beat;
  note@sol@beat;
  note@la@(beat*3/2);
  note@mi@(beat/2);
  note@la@(beat*2);
  note@(2*do)@(beat*2);
  note@(2*re)@beat;
  note@sol@beat;
  note@(2*do)@(beat*3);
  note@1@beat;
}; };
aweigh@(150 + rand@200)@(100 + rand@100);