Homework #13 Solution

Submit your work by scheduling a meeting with the instructor, preferably at a time well before the due date. You’ll show your code and answer questions in the meeting. You don’t need to handin your code at all, other than showing it at the meeting.

Start with the typed-class interpreter and typechecker: typed-parse.rkt. typed-class.rkt, inherit.rkt. inherit-parse.rkt. and class.rkt. Since you won’t use the “Handin” button to submit your work, there’s no need to collapse the modules into a single file.

Implement some of the follow additions, which are of varying difficulty. Each addition is annotated by a star rating; implement enough additions so that the sum of the star ratings is:

CS 3520 students: at least 8 ★s
CS 6520 students: at least 10 ★s
Extra credit will be awarded for rating sums beyond the required level, where the extra-point value of an extra star wll be 50% of the point value of a required star (e.g., 16 ★s would be 150% for a CS 3520 student).

     ★ 1.
Fix the type checker so that this and arg are prohibited in the main expression of a program (but allowed in a method body). This option Cannot be combined with 9, since 9 easily subsumes this problem.
★ 2.
Add a {cast <Symbol> <ExpI>} form to the language. At run-time, the cast expression reports an error if <ExpI> does not produce an instance of <Symbol> or one of its subclasses. Otherwise, the result is just the result of <ExpI>. Of course, <Symbol> should generally be a subtype of the type for <ExpI>, and the type checker can assume that the {cast <Symbol> <ExpI>} has type <Symbol>. The type-checker must reject the expression if the type of <ExpI> is neither a subtype nor supertype of <Symbol>, since the cast cannot succeed in that case.
★★ 3.
Add an {if0 <ExpI> <ExpI> <ExpI>} form to the language, where if0 requires a number for the test expression. The “then” and “else” branches should both have a type that is a subtype of some most-specific third type: one that is a subtype of any supertype of both the “then” and “else” types, which you might call the “least upper bound” of the “then” and “else” types.
★★ 4.
Add a Java-style null expression and value to the language. A null value can be used like an object, except that attempting to call a method or get (or set) a field of null produces a run-time error. The typechecker should ensure that null is never used like a number. The typechecker can reject expressions when null is used directly as a method or field source, as in {get null x} or {send null m 0}, but null should always be allowed as a non-number method argument or non-number field value. For example, if a method expects an object of some type, then the typechecker should allow null as an argument to the methods; if the method doesn’t try to access any fields or call any methods on the object, it should run without error.
★★★ 5.
Add imperative field assignment to the language. That is, in addition to the {get <ExpI> <Symbol>} form, add a {set <ExpI> <Symbol> <ExpI>} form that sets the value of the indicated field. (Hint: the value for each field in an object must be placed in a box.) Update the typechecker to ensure that the field is always available for the assignment, and to ensure that the type of the second <ExpI> in a set form is a subtype of the field’s type. Your test suite must include a test that would fail with a functional implementation of field assignment (i.e., one where assigning to a field produces a new object) and pass with an imperative implementation of update. Constructing the test is the hard part.
★ 6.
[Pre-reqsuites: 4 and 5] Change new so that it does not accept values for the object’s fields. Instead, new creates an object with null or 0 (as appropriate) for each field’s value, and then the fields can later be changed through set.
★★★ 7.
Add Java-style object arrays to the language with the forms {newarray <Type> <ExpI> <ExpI>}, {arrayref <ExpI> <ExpI>}, and {arrayset <ExpI> <ExpI> <ExpI>}.

In {newarray <Type> <ExpI> <ExpI>}, the first <ExpI> determines the size of the array, and the second <ExpI> is the initial value for every slot in the array (all the same); the whole expression is of type array-of-<Type>, and the type of the second <ExpI> must be a subtype of <Type>.
In {arrayref <ExpI> <ExpI>}, the first <ExpI> must produce an array-of-<Type>(for some <Type>), and the second <ExpI> must produce an index into the array; the expression is of type <Type>.
In {arrayset <ExpI> <ExpI> <ExpI>}, the first <ExpI> must have type array-of-<Type> (for some <Type>), the second <ExpI> must produce an index into the array, and the the third <ExpI> must have a type that is a subtype of <Type> to produce a value to put into the array. The arrayset operation is imperative, and to help make that clear, the result (unlike Java) must always be 0.
Your implementation should allow any kind of value in an array, including arrays of arrays or array of numbers. Your test suite must include a test that demonstrates arrayset as imperative. If you didn’t implement imperative field assignment, then constructing the test is one difficult part.
★★ 8.
[Pre-requisite: 7] As in Java, allow array-of-<Type>1 to be a subtype of array-of-<Type>2 when <Type>1 is a subtype of <Type>2. A run-time check must be added to arrayset to ensure that an instance of a class is not installed into an array that requires subclass instances.
★★★★ 9.
Add multi-argument methods, so that method arguments must be explicitly named in a method definition (along with the type for each argument), and identifiers are expressions. Also, allow fields to referenced directly, like method arguments (i.e., using the field name as an expression instead of using a get form).
★★★★ 10.
Add Java-style interfaces to the language. An interface is a set of method names, and it is a subinterface of an arbitrary number of other interfaces (in which case the interface includes all of the methods of its superinterfaces). A class implements any number of interfaces, and it is obliged to implement every method that is named in its implemented interfaces; the class is then a subtype of the interface. The type language is extended to include interface names in addition to class names and num.
★★★★★ 11.
Add Java-style overloading, where multiple methods can have the same name as long as they have different argument types. Usually, this is implemented by having the type-checker convert the input program to replace the original method names with names that describe the argument types.
★★★★★ 12.
Add Java-style generics, which are a form of parametric polymorphism. A generic class is parameterized with respect to a type variable, and whenever the generic class name is used, a specific type for the parameterization must be supplied. Consult a Java reference for more information; ignore Java’s support for generic methods and for using a generic type directly as a type (which is for backward compatibility only).