1 Starter Code

The starter code for this lab is basically a working solution to Lab 9, which was our last SPL Interpreter lab.

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

git pull starter main
git pull

You should now have a folder like si413/compiler/lab12 with the starter code for this lab, the lab12.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 SPL++

2.1 Overview and goals

This lab is about extending the SPL Interpreter (not compiler!) to add support for basic object oriented programming with classes.

Besides being a way to really experience how OOP can be implemented in a language, this will also require making (small) changes at every level of the interpreter from scanning to execution, and so will serve as a good overview/review of the stages of compilation that we have learned over the semester.

In the first (main) part, you will add support for class declarations, object construction, and field/method referencing within an object. As we will see, these are very similar to lambda declarations, function calls, and scoped variable lookup (respectively), all of which we have implemented already in the SPL interpreter.

In the second part of the lab, you will add support for base/derived classes and inheritance. Then we will really have OOP in SPL - awesome!

2.2 Bad-looking 'objects' using lambdas

Because SPL is a functional language, we could already kind of support objects by using closures, similar to how we did in Scheme. For example, here is an SPL program, using only lambdas, which gives (something like) the functionality of a bank account class with three methods to deposit, withdraw, and get the balance:

new BankAccount := lambda ignored {
  new balance := 0;
  ret := lambda which_function {
    ifelse which_function = 1 {
      ret := lambda deposit_amt
        { balance := balance + deposit_amt; };
    } {
      ifelse which_function = 2 {
        ret := lambda withdraw_amt
          { balance := balance - withdraw_amt; };
      } {
        ifelse which_function = 3 {
          ret := balance;
        } {
          "ERROR: INVALID which_function ARGUMENT"
        }
      }
    }
  };
};

# rich bank account with a million dollars
new rich := BankAccount@0;
rich @ 1 @ 1000000;

# poor bank account with 10 dollars
new poor := BankAccount@0;
poor @ 1 @ 10;

# withdraw 5 bucks from each, then print balance
rich @ 2 @ 5;
poor @ 2 @ 5;
write rich @ 3;
write poor @ 3;

See how this works? There are three levels of nested lambdas that form a bank account "class". The outer level is essentially the constructor - it initializes a local variable balance, then returns the second-level lambda.

Significantly, since SPL is lexically scoped with first-class objects, this creates a closure which ties the current Frame (with the balance) to the second-level lambda. That's crucial because it's what allows each bank account "object" to have its own balance.

The second-level lambda is just there to decide which function or method to access. Based on whether the number passed to the second level is 1, 2, or 3, that means either to do a deposit, do a withdraw, or get the current balance. This is essentially taking the place of the dot operator in Java or C++.

The third-level lambdas are like the class methods - they are doing the logic to actually deposit and withdraw from the balance.

BUT the code above is pretty messy to look at and hard to write/maintain. Most glaringly, we have to specify fields/methods by some numeric code 1,2,3 and then have a bunch of if/else statements to check for this. Gross!

2.3 What you will implement: classes

Here's how we will write the same logical code in SPL once your interpreter is complete for the first part of the lab:

new BankAccount := class {
  new balance := 0;

  new deposit := lambda amt
    { balance := balance + amt; };

  new withdraw := lambda amt
    { balance := balance - amt; };
};

# rich bank account with a million dollars
new rich := BankAccount ! ;
rich ! deposit @ 1000000 ;

# poor bank account with 10 dollars
new poor := BankAccount ! ;
poor ! deposit @ 10 ;

# withdraw 5 bucks from each, then print balance
rich ! withdraw @ 5;
poor ! withdraw @ 5;
write rich ! balance;
write poor ! balance;

Better, right? There are three new syntaxes that your interpreter will need to support:

• Class declaration:

  class {
    # any statements here, most commonly new field/method declarations
  }

  The class declaration is just the (new) keyword class followed by a block of code that will serve as the constructor for new instances of that class.

  The class itself will need to be a new kind of value in your SPL interpreter. Similarly to the closure returned by a lambda declaration, a class declaration will combine the referencing environment (Frame) with a block of code (list of Statements).

• Object creation/construction: BankAccount !

  This syntax uses the (new) operator ! to create a new instance of a class. In the interpreter, this should run the block of code from that class's declaration, and then return a new class instance - which will be represented simply by the Frame that results after running the constructor.

• Object field/method reference: rich ! deposit

  This syntax again uses the ! operator, but now with both a left-hand side and right-hand side. The left-hand side can be any expression that evaluates to a class instance, but the right-hand side has to be an identifier.

  Remember that class instances in the interpreter will be represented essentially by a Frame containing bindings for the fields and methods of that class. So to do a field or method reference, in the interpreter it just means performing a lookup operation in the Frame corresponding to the left-hand side.

3 Class declarations

Start by getting class declarations working. After this, an SPL program like the following should run (but won't actually do anything!):

new A := class {
  new some_field := 100;
  new some_method := lambda x { some_field := x; };
};
new B := class { };
write A; # should print as something like Class#0
write B; # should print as something like Class#1

(First a word of caution for Java: you can't call anything 'class' in your Java code because that is a Java keyword. Usually people end up using replacements like cls or clazz - just know that if you use class for something like a variable name, it will result in a strange-looking syntax error when you try to compile your interpreter.)

Implementing class declarations like this requires small additions at nearly every level of the interpreter. Here's what you will need (and I do recommend to work in this order too):

• Scanner:

  In the ANTLR scanner specification src/main/antlr4/si413/spl/SPLLexer.g4 add a new token for the class keyword.

• Parser:

  In the ANTLR parser grammar src/main/antlr4/si413/spl/SPLParser.g4 add a new expansion for the exp nonterminal, which is the class keyword token you just added to the scanner, followed by a block.

  (Be sure to add a name for your new grammar rule like # ClassDecl)

• Semantic analysis:

  Once your ANTLR scanner and parser changes are made, something like the above will no longer give syntax errors in your interpreter, but instead (worse!) a NullPointerException because you haven't made the corresponding AST node yet.

  First, create a new AST node for class declarations. This means creating a new Java class file within si413.spl.ast. A class declaration is similar to a lambda in SPL, except that there is no parameter. So maybe use the existing Lambda.java as a guide for what's needed here.

  (In your new AST node, all you really need at this point is a field for the Block and a constructor - don't worry about the evaluate() method just yet.)

  Then, add a new method to the ExpressionBuilder.java class to create a new instance of the AST node when walking the parse tree. Your new method might look something like this, depending on what names you chose:

  @Override
  public Expression visitClassDecl(SPLParser.ClassDeclContext ctx) {
      Block body = stmtBuilder.visitBlock(ctx.block());
      return new ClassDecl(body);
  }

• Types:

  At this point, when you try to do a class declaration in your interpreter, it should no longer give a syntax error or NullPointerException, but an UnsupportedOperationException because you haven't yet written the evaluate() method.

  But before we can write that evaluate() method, we need a new type of SPL value to return. So far SPL supports numbers, booleans, and functions as types within a running SPL program; you have to add another type for an SPL class declaration.

  Recall from the discussion above that a class declaration in the SPL interpreter really needs to remember two things: the environment (Frame) where the class was declared, and the block of code for the constructor.

  First, make a new Java class to hold these two pieces of information; you might call it ClassClosure since it's going to be very similar to a closure. In fact, I recommend copying from Closure.java, but changing it so that instead of a referencing environment and a Lambda AST node, it instead stores a referencing environemnt and a ClassDecl AST node (or whatever you called your new AST node from the previous step.)

  Next, make modifications to the Value.java class to support your new type. Specifically, you will need to add a new entry to the Type enum; a new pair of methods to convert between a Value and a ClassClosure; and a new case in the toString() method to display a class object.

  The method signatures for the two new methods in the Value class might be something like this:

  public static Value fromCC(ClassClosure c) { /* ... */ }
  public ClassClosure getCC() { /* ... */ }

• Execution:

  Now you just need to add an override for the evaluate() method to the AST node class you created for class declarations. This should be a very short function, that just creates a new ClassClosure instance, converts it to a Value, and returns it. (Hint: it will be similar to the evaluate() in the Lambda class.)

Exercises

1. Get class declarations working in your interpreter.
   At this point, code like the one above that just declares classes but never tries to construct or use them, should work (but do nothing).

   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

4 Class construction

The next goal is to create an object by calling the constructor of a declared class. After this, code like the following which declares and constructs class objects, but never actually tries to look up any fields or methods, should work:

new ConstructMe := class {
  write 42;
  "hooray"
};
new instance := ConstructMe!;   # prints 42 and then hooray
ConstructMe!;                    # prints both lines a second time
write instance;                 # should print something like Instance#0

Note that class declarations should obey lexical scoping, so more exotic-looking SPL programs like this should also work, where a function returns a class declaration:

new builder := lambda val {
  new other := 100;
  ret := class {
    write val * other;
  };
};
(builder@7)!;   # should print 700

To get this working, you will follow many of the similar steps as with the previous part. Here I will remind you what the steps are, but they are less detailed than above - think carefully, remember what you did before, and see if you can figure it out!

• Scanner (src/main/antlr4/si413/spl/SPLexer.g4):

  Add a new token for the ! operator

• Parser (src/main/antlr4/si413/spl/SPParser.g4):

  Add a new expansion for the exp nonterminal for an expression followed by the ! token. (And be sure to label your new rule with a name like # YourNewRule)

• Semantic analysis (ast/YourNewNode.java and ExpressionBuilder.java):

  Create a new AST node class for a constructor call. At this point, you just need the class itself, one field for the left-hand side expression, and the constructor.

  Then tell your interpreter how to create this AST node from the parse tree by adding an override for something like visitYourNewRule() to ExpressionBuilder.java

• Types (Instance.java and Value.java):

  You will need a new class for an object instance value, maybe call it Instance.java. This will be similar to Closure and ClassClosure but even simpler because an object instance just needs to hold a Frame.

• Execution (ast/YourNodeNode.java):

  OK, now you are ready to implement the evaluate() method in your new AST node for class construction. This part is more involved than above! Rather than just returning a new instance, you need to actually evaluate the block of code from the left-hand side expression (which should be a ClassClosure).

  For starters, you might want to remind yourself how evaluate() works in the FunCall class for function calls. Here it should be much simpler than function calls, because there are no arguments or return values.

  More specifically, you will need to (1) evaluate the left-hand expression to get a ClassClosure; (2) create a new frame whose parent frame comes from the environment where the class was declared; (3) execute the body of the class declaration with that new Frame; and (4) convert that Frame into an Instance and then a Value to return.

Exercises

2. Get class declarations and constructors working in your interpreter with lexical scope.

   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

5 Class fields and methods reference

Great work so far! Now it's time to make classes really work by being able to reference fields and methods from an instance.

For this, you need to support a new syntax in your SPL interpreter like some_instance ! some_name, which should evaluate the left-hand side to get a class Instance value (which holds a Frame), then lookup the right-hand side identifier in that Frame to get the field or method requested.

Here is what you will need to add to make this happen. Again, we are intentionally giving a little less guidance than the previous part; re-read what you did before, think carefully, and you will be able to figure it out!

• Scanner: No changes needed (the ! token should already exist)
• Parser: One new rule needed for exp, which will be an expression, a ! token, and then an identifier token ID.
• Semantic analysis: New AST node and ExpressionBuilder method needed
• Types: No changes needed this time! The fields and methods are not anything special type-wise; they can just be numbers etc.
• Execution: The evaluate() override in your new AST node class needs to evaluate the left-hand side, convert it to an Instance, then use the Frame stored in that instance to lookup the requested identifier value and return whatever it is.

Exercises

3. Get class field and methods references working.
   At this point, the full BankAccount example from the beginning of the lab should work perfectly!

   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 Ex3Test

6 OPTIONAL: Inheritance

Hooray, we have objects! But this isn't really OOP without class inheritance, like base classes and derived classes. Here's how this should work in SPL:

new Employee := class {
  # These is a placeholder for what derived classes should override.
  # Think of it as an abstract method.
  new paycheck := -1;

  new yearly := lambda hoursPerWeek {
    ret := paycheck@hoursPerWeek * 52;
  };
};

new Salaried := class Employee {
  new salary := 0;

  new set_salary := lambda s { salary := s; };

  paycheck := lambda hours {
    ret := salary / 52;
  };
};

new Hourly := class Employee {
  new wage := 0;

  new set_wage := lambda w { wage := w; };

  paycheck := lambda hours {
    ret := hours * wage;
  };
};


new manager := Salaried! ;
manager!set_salary @ 100000;
write manager!yearly @ 40;

new consultant := Hourly! ;
consultant!set_wage @ 100;
write consultant!yearly @ 15;

As you can see in this example, the syntax for a derived class is to put the base class between the keyword class and the constructor block.

In order to support that syntax without your compiler crashing, you will need a new grammar rule, a new AST class or a modification to the existing ClassDecl class, and a new method in the ExpressionBuilder class to actually construct that AST node from the parse tree.

But the syntax is the easy part here! What about semantics - how is a derived class actually supposed to work?

For the way we have it set up in the SPL language, there are three things you need to change on the semantics side of things: the ClassClosure (a little bit, so that it remembers the parent class), the Frame class, and the class constructor AST node.

For the Frame, what's odd is that a scope can now kind of have two scopes it inherits from - the surrounding lexical scope where the class definition is, AND the scope of the superclass's constructor block (if any). Here's an example to demonstrate the issue:

new A := class {
  new x := 10;
};
new funky := lambda y {
  new B := class A {
    # NOTE: x should be the x from the parent class A
    # and y should be referring to the function argument (outer scope)
    x := y * 100;
  };
  ret := B!;
};
write (funky@4)!x; # should be 400

To solve this, it's not that bad - you just need to add an extra Frame field inside the Frame class for the "superclass frame" - which in most cases will be null. Then adjust the logic of lookup() and rebind() to first look in the current frame's binding, then try the superclass frame if it's not null, and finally try the parent frame.

Now to the last part: when a constructor call is evaluated for a derived class, it needs to do all the same things as before, but there is one additional step: Before executing the body of the class's constructor, you first need to execute the parent class's constructor, and then connect that superclass frame to the frame for this new class instance. To make this possible, you might need to make some small changes or add a a method to a few other places in your interpreter code besides just the constructor call AST node's evaluate() method.

To summarize and help you plan your work, here is all that you need to do for this part:

• Add a new grammar rule, AST node (or modify the existing ClassDecl one), and ExpressionBuilder method to support the syntax `class SuperName { ... }`
• Modify ClassClosure so that it saves a pointer to the superclass (which might be null), in addition to the environment Frame and the constructor body which should already be there.
• Modify the AST node for subclass declarations so that its evaluate() method returns this new kind of ClassClosure with the superclass.
• Change the Frame class so that it has a pointer to the superclass constructor Frame (in addition to the parent Frame). By default, the superclass constructor Frame will be null. Fix the logic for lookup() and rebind() to look in the superclass frame (if it isn't null) before checking the parent frame.
• Modify the evaluate() method in your class constructor AST node so that it calls the superclass constructor (if any) before executing the body of the current class. This is where you will need to be careful to make the correct Frames with the correct parent Frame and superclass Frame to respect both lexical scope and inheritance.

Want a longer example? Check out this object-based implementation of a binary search tree in SPL. It should work in your interpreter if you finish this part!

Exercises

4. (OPTIONAL) Get derived classes working in your interpreter. Function overriding and polymorphism should both work as in the example above (or any other example!).

   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