Lab 3.1: Spec and Interpreter for an Iffy Language

Grades and deadlines

Getting started: files

Start by downloading the starter code. Running this command will create a new directory lab3.1:

git clone https://github.com/si413usna/startlab.git -b lab3.1 lab3.1

In there you will find:

Background: Java record syntax

In the AST node classes Stmt.java and Expr.java we use a syntax in Java that might be unfamiliar to you: Java records.

There official documentation on this is pretty straightforward and I encourage you to check that out.

A record is simply a shorthand to make our code have less boilerplate. It’s really common to make a Java class where:

Rather than having to repeat yourself three times, the record syntax was introduced to save typing and make your code more readable to handle this common use case.

Concretely, take this example, which is one of the AST node types from Stmt.java:

record AssignString(String name, Expr<String> child) implements Stmt {
    @Override
    public void exec(Interpreter interp) {
        String val = child.eval(interp);
        interp.getStringVars().put(name, val);
    }
}

This short record declaration is equivalent to the following class definition:

public class AssignString implements Stmt {
    // private fields auto-filled in from record arguments
    private String name;
    private Expr<String> child;

    // public constructor auto-created, matching record arguments
    public AssignString(String name, Expr<String> child) {
        this.name = name;
        this.child = child;
    }

    // public getter methods auto-created from record arguments
    public String name() { return name; }
    public Expr<String> child() { return child; }

    // a few more common methods auto-filled in for you,
    // like toString() and equals()

    // and finally whatever methods are specified in the record definition
    @Override
    public void exec(Interpreter interp) {
        String val = child.eval(interp);
        interp.getStringVars().put(name, val);
    }
}

Because there are around a dozen different type of AST nodes, it would be a real pain to have to write out all the fields, constructors, getters, equalitiy check, etc. for every single one. The record syntax in Java just saves us the hassle and makes the code more readable for these straightforward kinds of classes.

Task 1: Design your language

You need a language that supports all of the string and boolean operations from Lab2.1, but now must additionally support if statements and while loops.

Your language can be derived from some language in prior weeks, but it still needs to be original, and have an original name.

Even though there is not too much to add with if statements and while loops, you still have some interesting choices:

Fill in the langauge_name and language_description fields in the YAML file.

(Note: Unlike in previous units, you do not need to write out the syntax of your language. That is because you will also be turning in a working interpreter that will have to include the token spec and grammar files anyway.)

Task 2: Write an example program.

Write a complete example program that demonstrates all the features of your language. Make good use of variable names, spacing, and comments so that your code is easily readable and understandable.

Be sure to especially demonstrate how your if statements and while loops work! Your example program must include at least one nested if statement and at least one nested while loop.

Fill in the example_program field, as well as example_input1, example_output1, example_input2, and example_output2, in the YAML file.

We will use your own code example and input/output to test your interpreter, so make sure it’s precise. Come back and check it after you get your interpreter working!

Task 3: Write the dance program in your language

Here is a simple Python program that demonstrates the various boolean, string, and control flow features your language should support:

print("enter two dance moves")
x = input() + "m" + input()
print("Let's do the " + x)
y = ("mb" in x)
if x < "mambo":
    print(x[::-1])
    y = False
print(y)
print("a" in x and not y)
timer = ""
while not ("..." in timer):
    print("cha")
    timer = timer + "."

You need to write a program in your language which is exactly equivalent to this one in terms of its run-time behavior. That is, running your program in your (eventually) working interpreter, should be the same as running the code above using the python3 interpreter.

Fill in the dance_program field in the YAML file. You don’t need to provide sample input/output pairs for this one.

Task 4: Write your interpreter

The starter code you downloaded has a working implementation of an interpreter for a very small subset of Python. For example, it would work on a two-line program like this:

print("one" + "two" + "three")
print(not not not True)

This is way less powerful than the interpreters you already wrote in the previous unit. But what’s different now is how this interpreter works!

Rather than directly executing the code while walking the parse tree in the various visitX() methods, this interpreter first creates an AST, and then calls the exec() method on the root node of the AST to run the program.

Here’s how it works specifically:

So what you will need to do is:

As usual, starting small and testing along the way will be key to your success. I recommend starting with something super simple, like printing a single boolean literal. Write a tiny example program file that just does that, then try to fill in enough in your Java code and token/grammar specs to make that work. Then add a little more, and a little more, testing along the way so you don’t get stuck.

Task 5: Test and submit

Once you think your interpreter is complete, you need to thoroughly test it and make sure it works perfectly. Of course, you were already testing your code as you went along, so this shouldn’t be a huge step.

Be sure to test your code on the two example programs you wrote earlier. That is also what we will use to test your code when you submit!

Follow the submit commands at the top of this page to turn everything in.

Optional fun challenge: Numbers!

Your programming language now supports strings, booleans, variables, conditionals (if statements), and looping. But still it doesn’t have any kind of integer type or arithmetic.

We could easily add numbers to the tokens, grammar, and interpreter that you wrote. And in fact we will add numerical support to your languages in a later unit this semester.

But this challenge isn’t about modifying the language further, it’s about using the language as-is to emulate numerical computation using strings. Thanks to the features you have now added (variables, if statements, and loops), your existing language and interpreter are able to do math with strings. Yes, it’s really possible!

I hope this is a fun challenge, but it’s also a valuable exercise that’s important when dealing with new programming languages or restricted environments: Given the limited (computing) tools you have, what’s the most you can do? This is actually the spirit of a “minimalistic” language like Scheme. So let’s practice on the languages you all have created!

Challenge part 1: Unary math

For starters, we will represent numbers in unary, as just a series of x’s. So like the number 5 would be represented by this string:

xxxxx

See if you can write a program in your language that reads in two unary numbers like this, then performs some basic arithmetic on those “numbers” and prints out the results in unary.

Specifically, your program should:

Here is a complete sample run of how your program should work. In this example, the input numbers are 17 and 5; their sum is 22, difference is 12, product is 85, quotient is 3, and remainder is 2.

enter two numbers with x's:
xxxxxxxxxxxxxxxxx
xxxxx
sum:
xxxxxxxxxxxxxxxxxxxxxx
difference:
xxxxxxxxxxxx
product:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
quotient:
xxx
remainder:
xx

Challenge part 10: Binary

Now do the same, but make it more efficient with a binary representation of numbers.

Because these are just strings you could use any two characters you like for 0 and 1. I used o and x.

Try to get the same four operations working as before. It will be tough! But it’s definitely possible, and even trying to work through this will stretch your thinking muscles.