Assignment 5, CSC430, Winter 2017

1 Goal

Extend the interpreter to handle recursive functions and a simple class system

2 Guidelines

For this and all remaining assignments, every function you develop must come with the following things:

• A commented header line that expresses the result of the function in terms of its inputs, written in English. Be as precise as you can within the space of a line or two.

• A type declaration, specifying the input and output types.

• Test cases. A function without test cases is incomplete. Write the test cases first, please.

For this assignment, you must develop your solutions using the typed/racket language. If you still haven’t seen them, you might be interested in these Hints on Using Typed Racket in CPE 430.

Your test cases must use the check-equal?, check-=, or check-exn forms.

Your solution should take the form of a single file. Solve each problem separately, ands make sure that each solution appears in a separate part of the file, with comments separating each problem’s solution.

Hand in your solution using the handin server. For help with the handin server, please see the course web page.

2.1 Handling Errors

All of your error messages must start with the string "PHYM: ". Essentially, this allows my test cases to distinguish errors correctly signaled by your implementation from errors in your implementation. To be more specific: any error message that doesn’t contain the string "PHYM" will be considered to be an error in your implementation.

2.2 Progress Toward Goal comment

Graders are happier when they know what to expect. Your final submission should start with a short one- or two-line comment indicating how far you got through the project. Ideally, this would just be: “Full project implemented.” But if you only implemented, say, squazz and blotz, and didn’t get to frob or dringo, please indicate this in the comment, so that we don’t spend all our time searching for bits that aren’t there.

3 The Assignment

This assignment will build on Assignment 3, with the addition of top-level environments and strings (that is, the suggested checkpoint in Assignment 4).

There are two parts to this assignment. The first is easier, the second is harder.

3.1 Recursion

Following the template of the book, add a rec form that allows the definition of recursive functions. You can build the rec form using the mutation available in Typed Racket.

Specifically, change the type of environments to map names to boxed values, update the appC and idC rules to perform box creation and box deref, and then add a recC rule to the interpreter that creates a box, adds it to the environment, uses it to evaluate the rhs, then uses box mutation to put the resulting value in the box.

3.2 Classes and Objects

Here’s the tricky one. However, one thing makes it simpler: we will not be changing the interp function in any way in order to support objects. Instead, we will be representing objects as closures, following the lead of the book.

For this assignment, we will add two new expression forms, and one new top-level form.

3.2.1 Expression Forms

• {new <classname> <arg> ...} : create a new object of the given class, with the given fields.

• {send <object> <message> <arg> ...} : call the named method of the given object, passing it the given arguments.

3.2.2 Top-level form

• {class <classname> extends <classname> {<field> ...} <method> ...} : specifies a class with the given name, that extends the given superclass. It has the named fields, and the given methods.

4 Syntax of PHYM5

A PHYM5 program consists of a sequence of class definitions, and a single expression (all wrapped in a single pair of brackets).

The concrete syntax of the ClassDef and PHYM5 expressions with these additional features can be captured with the following EBNFs.

... where an id is not var, if, lam, new, send, = or rec.

5 Classes, Objects, and Inheritance

In our system, all classes are declared first. They must declare a superclass, but they may declare the base "Object" superclass, a special superclass that does not need to be declared, and has no fields or methods.

Further, they must be declared in top-down order, superclasses first.

Each class contains a set of fields, and a set of methods. The methods may refer to the fields. Within the method declarations, the name this will refer to the object on which the method was called.

When an object has a superclass, it will create an object of that superclass when the object of the given class is created. The translation example below may make this more clear.

In order to create an object, you must supply values for all of the fields of the class. If the class has a superclass (that may have a superclass), you must supply the fields of the topmost class first. Here’s an example:

{{class Top extends Object {a}}

{class Middle extends Top {b}}

{class Bottom extends Middle {c}}

{new Bottom 10 11 12}}

In this example, the value 10 would be the a field of the Top object, the value 11 would be the b field of the Middle object, and the value 12 would be the c field of the Bottom object.

In order to keep things simple, our class system has lots of restrictions.

First off, fields are all ‘private’. They may be accessed only through provided methods.

Here’s an example of a Point class that provides a getter for y and x:

{class Point extends Object

{x y}

{get-x {} x}

{get-y {} y}}

Next, the fields of superclasses are visible only to those superclasses. If subclasses want to use those methods, they’ll need to use the getters. Here’s an example of a 3d point as a subclass:

{class 3DPoint extends Point

{z}

{get-z {} z}

{dist-from-zero {}

{var {y = {send this "get-y"}}

{var {x = {send this "get-x"}}

{expt {+ {* z z} {+ {* y y} {* x x}}} 1/2}}}}}

Note that calls to getters are required in order to get the values of x and y.

Another simplification is that we disallow shared field names between classes and their superclasses.

Also, you cannot declare the same class name twice.

On the other hand, we will be doing dynamic dispatch ‘correctly’. Here’s a contrived example:

{class Rider extends Object {}

{one-if-by-land {}

{if {eq? {send this "travel-mode"} "by land"}

1

2}}}

{class LandRider extends Rider {}

{travel-mode {} "by land"}}

{class SeaRider extends Rider {}

{travel-mode {} "by sea"}}

If we call {send my-rider one-if-by-land}, it should work for both LandRiders and SeaRiders.

6 Desugaring

We will be implementing the class system using desugaring. That is, the parser will translate the new forms into existing forms.

6.1 Desugaring ClassDefs

The most complex translation is for the class form. In order to illustrate the process, here’s the translation of the 3DPoint class shown above into the existing concrete syntax:

{lam {x y z}

{var {parent = {new Point x y}}

{lam {mesg}

{if {eq? mesg "get-z"}

{lam {this} z}

{if {eq? mesg "dist-from-zero"}

{lam {this}

{var {y = {send this "get-y"}}

{var {x = {send this "get-x"}}

{expt {+ {* z z} {+ {* y y} {* x x}}} 1/2}}}}

{parent mesg}}}}}}

Note that large chunks of this (especially the body of dist-from-zero) are taken directly from the class declaration. Also note the delegation to the parent in the case that we don’t find a definition for the given method name.

Also, note that this uses the name parent in a way that could cause shadowing, if the programmer used the name parent in a different way. The right way to solve this problem is with macro hygiene. Lacking it, we will simply cross our fingers and hope that the programmer doesn’t use these as identifiers.

Also, note that this concrete syntax still needs to be parsed. I recommend using the parser to rewrite the syntax into another s-expression, and then calling parse on the result.

Another important point concerns the correct computation of the class arguments, and how to pass them on to the superclass correctly. In the example above, the translation must have enough information about the superclass to know that it requires two arguments named x and y. You’ll probably want to make two passes through the ClassDefs; the first to build this table, the second to perform the actual desugaring.

In order to be able to "bottom out", you’ll need a built-in declaration for Object. Here’s the one I suggest:

{lam {}

{lam {mesg}

"NO METHODS"}}

Calling any methods on something created using this function will simply signal an error.

When you’re done, you’ll have a set of functions, one for each class. Add these to the outside of the program, as var bindings. So, for instance, if we declare the Point and 3DPoint classes, our final program would look like:

{rec {Object = ...}

{rec {Point = ...}

{rec {3DPoint = ...}

...}}}

... where the ...’s are replaced with the class definition functions and the body of the program.

6.2 Desugaring expression forms

Next, we need to desugar the new and send expressions. These are much simpler.

We could come up with a more elaborate way of separating constructors from applications, but it would just add complexity.

The temporary variable obj is necessary in case the target of the send is an expression that performs mutation. so, for instance, if we wrote {send {get-new-socket} bind-to 4421}, we certainly wouldn’t want to create two new sockets.

Also, as with parent, we’re simply crossing our fingers and hoping that the programmer doesn’t use these identifiers. This is a macro hygiene problem.

7 Quasiquote!

There are a number of ways of implementing desugaring for this assignment. You could expand your class forms directly into ExprC’s, for instance. This works fine, but it’s very verbose and painful.

Instead, I advise you to write a desugarer for classes that expand into one big s-expression that is then fed into the interpreter.

But wait! There’s a problem!

Suppose I want to construct the s-expression

'{var {parent = {new parent-class-name x y}} ...}

.. except that where it says parent-class-name, we want to plug in the actual name of the parent class. Put differently, we want an s-expression template. Quasiquote provides that template.

The basic idea is this. When you begin a quoted expression with a ‘ (back-tick), rather than a ’ (forward tick), you can use a comma in order to escape again into the language outside of the quote.

So, for instance, if you wrote

(define test `{+ 3 4})

(define then `{+ p 15})

(define els `{f x})

`{if ,test ,then ,els}

It would evaluate to

`{if {+ 3 4} {+ p 15} {f x}}

You can use unquoting (the comma) to insert pieces of data from the enclosing language.

There’s one more form that may be useful to you, "unquote splice". It’s written using ,@ (comma at-sign), and it "splices" its argument into the context. So, if you had written

(local [(define test `{+ 3 4})

(define then {list `+ `p `15})

(define els `{f x})]

`{if ,test ,@then ,els})

It would produce

`{if {+ 3 4} + p 15 {f x}}

Notice that the elements of the second list are now "spliced" into the surrounding quoted list.

8 Suggested Implementation Strategy

As always, you may feel free to ignore my suggested implementation strategy. What follows is just the implementation strategy that makes the most sense to me.

First, I would add recursion. Use the code given in class. Make sure to write tests.

Next, we need to deal with classes.

Let me reiterate here, that this requires no changes at all to the interp function, or the set of values. Our entire object system will be implemented using desugaring into existing forms.

I think I would start simple, by “faking” the classdefs while getting new and send working. In particular, I would take a simple hand-translated class function like the one above or one of the ones you created in lab 8, and add it to the program with an explicit "rec" so that you can test your other forms. I would start with new, and then move on to send. You should be able to test these two forms pretty completely before tackling the translation of the classes.

Translating the classes will be the big part. I think I might start by translating classes that have no fields, only methods. These are less work because you don’t need to figure out what fields are associated with the superclass. Get these working, and make sure that you can delegate to the superclass when no method with the given name is found.

Next, try classes with fields that have superclasses with no fields.

Finally, add support for superclasses with fields. In order to do this, you’ll need to keep track of the field names associated with each superclass.

Now you’re done!

9 Interface

Make sure that you include the following functions, and that they match this interface:

(define (top-interp [program : s-expression]) : string

(serialize (interp (parse-prog program) top-env)))