1 Starter Code

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

git pull starter main
git pull

You should now have a folder like si413/parsing/lab06 with the starter code for this lab, the lab06.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 Overview and Goals

Starting today, and for the rest of the semester, our labs will be focused on a new programming language called SPL, or SI413 Programming Language.

This week, we will provide you access to a working SPL interpreter, and ask you to write some small SPL programs so that you get an idea of how the language works. In subsequent labs, you will little-by-little write a complete interpreter and then compiler for SPL yourselves.

So, please keep in mind that the purpose of today's lab is partially to give you practice in writing code (like every other lab has been as well), but also to get you acquainted with this language that you need to understand deeply in order to do well for the rest of the semester.

So enjoy it, take advantage of the time, and be creative in trying things out to understand the "corners" and "quirks" of the language. The better and more deeply familiar you are with SPL after today's lab, the easier all of the following ones will be.

3 Accessing the SPL interpreter

You can run a working SPL interpreter on the lab machines or sshing into the CS department server, by running the command spli.

• You can run spli by itself to get a "live" interpreter, or, if you have written some SPL code in a file like myprog.spl, then you can run that by typing spli myprog.spl.
• If you get an error like "command not found", then it means that the directory /courses/roche/413/bin is not in your PATH. You can run it directly by typing out the full path every time, like /courses/roche/413/bin/spli, or you can edit your ~/.bashrc file to add a line like this:

  export PATH="/courses/roche/413/bin:$PATH"

Try running these example commands to get your feet wet. See if you can guess what is going on in the language.

roche@ubuntu$ spli

spl> write 1 + 2 * 7;
15

spl> new cookies := 5;

spl> while cookies > 0 { cookies := cookies - 1; "YUM!" }
YUM!
YUM!
YUM!
YUM!
YUM!

spl> ifelse 20 / 3 = 6 { "division rounds down" } { "division is exact" }
division rounds down

spl> new fun := lambda x { x := x * 2; write x; };

spl> fun@30;
60

spl> x; # will be undefined
ERROR: No binding for variable 'x'

spl> new double := lambda x { ret := x + x; };

spl> write double;
si413.spl.Closure@433d61fb

spl> write double@14;
28

spl> write double@double@3;
ERROR: Cannot cast to num: si413.spl.Closure@433d61fb

spl> write double@(double@3);
12

spl> new larger := lambda a {
...>   ret := lambda b {
...>     ifelse a >= b
...>       { ret := a; }
...>       { ret := b; }
...>   };
...> };

spl> write larger @ 20 @ 30;
30

spl> write larger @ 20 @ 5;
20

spl> new cool := read;
read> 15

spl> write read * cool;
read> 10
150

4 The SPL language

4.1 Quick summary

SPL is an extension of the calculator language we have seen in class to include a few control structures and functions. The syntax is similar in some ways to C++ and Java but much more limited, and there are some very important differences (as we will see). Specifically, SPL supports:

• Integers like 1234 and booleans true and false
• Basic arithmetic (+, -, *, /)
• Numeric comparisons (=,!=, >, >=, <, <=)
• Boolean operations (and, or, not)
• Output with the write statement
• Numeric input with the read expression
• Basic control structures (if, ifelse, and while)
• Variables, declared with the new keyword and assigned using the := operator.
• User-defined functions. These must be unary (single-argument), and are defined with lambda statements.
  NOTE: We will deal with functions in all their glory in later labs, but for this lab you don't have to worry about lambdas or function calls.
• Special "Debug" statements that just print a line of text when they are executed, indicated by surrounding "with double quotes"

4.2 SPL lexicon

The tokens of SPL fall in five categories.

First, we have the following keywords:

if ifelse while read write lambda new true false and or not

Second, an SPL atoms can be one of three kinds of token:

NUM     : [0-9]+ ;
BOOL    : 'true'|'false' ;
ID      : [a-zA-Z_][a-zA-Z_0-9]* ;

Third, we have a bunch of operators (in order from high to low precedence):

* / + - < <= = >= > != and or not @ :=

Fourth, we have a few purely syntactic/grouping tokens:

( ) { } ;

And finally, we have the unusual token for DEBUG statements, which is any double-quoted string.

4.3 SPL Grammar

Here is the complete grammar for SPL, which consists mostly of statements ("do this command") and expressions ("compute and return this value").

(Note that in the listing below, STOP is a semicolon, BOP is a boolean operator, etc. And the empty expansion of stlist means that nonterminal can match to an empty sequence of tokens, a.k.a. ε.)

prog: stlist EOF

stlist
  : stlist stmt
  |

stmt
  : exp STOP
  | NEW ID ASN exp STOP
  | ID ASN exp STOP
  | WRITE exp STOP
  | IF exp block
  | IFELSE exp block block
  | WHILE exp block
  | block
  | DEBUG

block : LC stlist RC

exp
  : NUM
  | BOOL
  | ID
  | LP exp RP
  | READ
  | LAMBDA ID block
  | exp FUNARG exp
  | exp OPM exp
  | OPA exp
  | exp OPA exp
  | exp COMP exp
  | NOT exp
  | exp BOP exp

4.4 SPL quirks

Here are a few interesting aspects of SPL that you should be aware of:

• There are no declared types. Variables are declared and given an initial value with a statement like

  new x := 10;

  and afterwards, they can be reassigned using just the := operator without the new keyword.
• The conditions in if and while statements do not need to be enclosed in parentheses. For example, here is a program to find (and then print) the sum of 1 up to 100:

  new i := 1;
  new sum := 0;
  while i <= 100 {
    sum := sum + i;
    i := i + 1;
  }
  write sum;

• A regular if statement (with no else) looks like you might expect:

  if 1 < 10 { write true; }

  But if we have an if-else, you use the keyword ifelse instead of if, followed by the condition and the two code blocks - no separate else keyword is used:

  ifelse false { write 100; } { write -100; }

• The read keyword is an expression, not a statement! So syntactically you can use read like a variable, but any time its value is needed, the user will be asked to type in a number.
• Function calls are a bit different than the norm. Every function is a unary function (takes one argument), and return values are specified by assigning to the special variable ret. So here is a function to compute the factorial of its argument:

  # This is a one-argument function to compute factorials.
  new fact := lambda n {
    new prod := 1;
    new i := 1;
    while i <= n {
      prod := prod * i;
      i := i + 1;
    }
    ret := prod;
  };

  (Did I mention? Pound signs # start single-line comments.)
  Once we have a function defined, you call it with the @ operator, like function @ operand. Using the function just defined, we could print out 8 factorial with:

  write fact@8;

5 Your task

For this lab, you will need to write a number SPL programs, of increasing complexity. Use the spli interpreter to gradually develop and test your code.

Note, this will be more challenging than other kinds of programming because this is really a made-up language just for this course. So there are no debuggers, no online tutorials, no fancy syntax highlighting, nothing to help you out other than this web page, the spli interpreter, and your massive brains. So be patient with yourselves, take it slowly, and continually check your work.

Exercises

1. Write an SPL program that reads in integers until 0 is entered, at which time the sum of all the integers read in is printed to the screen.

   Submit your program in a file called sum.spl

   Here is an example run:

   roche@ubuntu$ spli sum.spl
   read> 1
   read> 2
   read> 3
   read> 4
   read> 10
   read> 10
   read> 0
   30

2. Write the FizzBuzz program in SPL. (This is a famous/infamous example of an extremely simple programming task that supposedly, sadly, many CS grads can't do when they look for jobs.)

   Here is the specific task:

   Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".

   Submit your program in a file fizzbuzz.spl

3. Write a guessing-game program guessing.spl. Your program should repeatedly read a guess from the user, and then report whether it was "too low", "too high", or "CORRECT".

   Hard-code 42 as the secret number. Keep taking more guesses until the guess is CORRECT at 42.

   Example run:

   roche@ubuntu$ spli guessing.spl
   read> 10
   too low
   read> 20
   too low
   read> 30
   too low
   read> 40
   too low
   read> 50
   too high
   read> 45
   too high
   read> 43
   too high
   read> 41
   too low
   read> 42
   CORRECT

4. Write an SPL program stats.spl that reads in positive numbers until the user types in 0 or a negative number, and then displays three statistics (in this order): the minimum (positive) number entered, the maximum number entered, and the average (rounded down to the nearest integer).

   For example:

   roche@ubuntu$ spli stats.spl
   read> 56
   read> 71
   read> 2
   read> 33
   read> 19
   read> 101
   read> 50
   read> 0
   2
   101
   47

5. SPL is primarily integers-based, so let's do some number crunching.

   An abundant number is a number n where all of n's factors from 1 up to (n - 1) add up to strictly more than n.

   For example, 24 is abundant because its factors sum to 1+2+3+4+6+8+12=36, which is more than 24. 6 is not abundant because its factors sum to 1+2+3=6, which is not more than 6.

   Write an SPL program abundant.spl that reads from the use two numbers a and b, and then prints out all abundant numbers that exist from a up to b (inclusive). For example:

   roche@ubuntu$ spli abundant.spl
   read> 20
   read> 55
   20
   24
   30
   36
   40
   42
   48
   54

   Hints:

   • There is no "mod" operator in SPL. Instead, to check if one number divides another one, you have to use normal integer division and multiplication. For exanple, I could check whether 100 is divisible by 13 by first dividing 100/13 (using integer division) to get 7, then multiplying 7*13 to get 91. Since 91 is not 100, that means 13 is not a factor of 100.
   • Make some helper functions! I suggest one for testing divisibility, and another one for computing the sum of the divisors of a number.
   • Start small, work carefully, test, debug, repeat.
6. (OPTIONAL)

   SPL uses closures just like Scheme. Neat! So we can for example write a lambda to store a running sum, like this:

   roche@ubuntu$ spli
   spl> new runsum := lambda current {
   ...>   ret := lambda additional {
   ...>     current := current + additional;
   ...>     ret := current;
   ...>   };
   ...> };
   spl> new A := runsum@0;
   spl> new B := runsum@0;
   spl> write A@10;
   10
   spl> write A@15;
   25
   spl> write A@3;
   28
   spl> write B@3;
   3
   spl> write B@3;
   6
   spl> write A@100;
   128

   Unlike Scheme, SPL does not have any built-in data structures such as lists. But because we have closures, we can make the same functionality of basic linked lists (basically, null?, cons, car, and cdr) using functions and closures, similarly to when we did "object-oriented" Scheme with lambdas and message passing.

   Your task is deceptively simple: write a program reverse.spl that reads in numbers until 0 is entered, and then prints out those same numbers in reverse order. Example run below. Good luck!

   roche@ubuntu$ spli reverse.spl
   read> 5
   read> 6
   read> 20
   read> 30
   read> 4
   read> 0
   4
   30
   20
   6
   5