Assignment 5, CSC430, Spring 2015

1 Goal

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

2 Guidelines

2.1 Contracts & Test Cases

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. The header lines must include input and output types.

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

2.2 Handling errors

Your parser and interpreter must detect errors and explicitly signal them by calling (error ...). We will consider an error raised internally by Racket to be a bug in your code.

For example, Racket signals a "divide by zero" error if you attempt to evaluate (/ 1 0). Since we use Racket’s division function to implement division in CFWAE, you may be tempted to leave it to Racket to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Racket’s division procedure.

2.3 Language Level & File Format

Your solution should take the form of a single file. Solve each problem separately, and 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.

3 The Assignment

This assignment will build on Program 3.

There are three parts to this assignment. The first two are easy, the third is harder.

3.1 Strings

Add strings to the language. This will require a new form of AST for string literals, a new form of string value, and a rule that evaluates string literals into string values.

In addition, you will need to extend the eq? function to work correctly on strings. Specifically, eq? must return true for two strings containing the same sequence of characters.

NOTE! You should not use the plai-typed function eq? to compare strings; it performs a pointer comparison, like java’s "==", which can bite you on this assignment. Instead, use the equal? function to compare strings.

3.2 Recursion

Following the template of the book, add a rec form that allows the definition of recursive functions. This form should simply expand into a self-mutating binding, as shown in the book.

3.3 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.3.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.3.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 EXCR5

A EXCR5 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 EXCR5 expressions with these additional features can be captured with the following EBNFs.

... where an id is not true, false, with, if, fn, =, rec, new, send, class, extends, or one of the operator names.

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 {}

{with {y = {send this get-y}}

{with {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.

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 rec

Our rec form is just like the book’s; it contains a bound identifier, a value to be bound, and a body in which the binding may be used.

In order to implement this, we need a new form of expression. You can add this to your expression definition:

[rec (name : symbol) (rhs : ExcrC) (body : ExcrC)]

Add a rule to your parser and the appropriate code (given in class) to your interpreter.

6.2 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:

{fn {x y z}

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

{fn {mesg}

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

{fn {this} z}

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

{fn {this}

{with {y = {send this get-y}}

{with {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:

{fn {}

{fn {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 with 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.3 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

'{with {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

(local [(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 strings. This should be pretty straightforward. For heaven’s sake, include test cases.

Next, 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:

Use the following interface for interp:

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

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

Your body can be different if you really want, but the types must match these.