CS 5510 Homework 12

Due: Thursday, December 8th, 2016 11:59pm

Submit your work by scheduling a meeting with the instructor.

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 at least 8. Extra credit will be awarded for rating sums beyond 8.

 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).
 2.Add an {instanceof <ExprI> <Sym>} form to the language. The result of {instanceof <ExprI> <Sym>} is 0 if <ExprI> produces an object that is an instance of the class <Sym> or one of its subclasses, otherwise it produces 1. The typechecker should ensure that <ExprI> does not produce a number, since the instanceof test could never succeed in that case.
 3.Add an {if0 <ExprI> <ExprI> <ExprI>} form to the language, where if0 requires a number for the test expression. The “then” and “else” branches should be constrained in the same way as in Java: the type of one must be a subtype of the other, and whichever is the supertype determines the type of the if0 form.
★★ 4.Generalize checking of if0 to allow the case where the “then” branch is not a subtype of the “else” branch or vice versa, but the type of each is a subtype of some third type. The type of the if0 expression should be the most specific third type (i.e., 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).
★★ 5.Add a {cast <Sym> <ExprI>} form to the language. At run-time, the cast expression reports an error if <ExprI> does not produce an instance of <Sym> or one of its subclasses. Otherwise, the result is just the resuilt of <ExprI>. Of course, <Sym> should generally be a subtype of the type for <ExprI>, and the type checker can assume that the {cast <Sym> <ExprI>} has type <Sym>. The type-checker must reject the expression if the type of <ExprI> is neither a subtype nor super-type of <Sym>, since the cast cannot succeed in that case.
★★★ 6.Add imperative field assignment to the language. That is, in addition to the {get <ExprI> <Sym>} form, add a {set <ExprI> <Sym> <ExprI>} 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 <ExprI> in a set form is a subtype of the field’s type.
 7.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 typecheck 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.
 8.[Pre-reqsuites: 6 and 7] 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.
★★★ 9.Add Java-style object arrays to the language with the forms {newarray <Type> <ExprI> <ExprI>}, {arrayref <ExprI> <ExprI>}, and {arrayset <ExprI> <ExprI> <ExprI>}.
  • In {newarray <Type> <ExprI> <ExprI>}, the first <ExprI> determines the size of the array, and the second <ExprI> 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 <ExprI> must be a subtype of <Type>.
  • In {arrayref <ExprI> <ExprI>}, the first <ExprI> must produce an array-of-<Type> (for some <Type>), and the second <ExprI> must produce an index into the array; the expression is of type <Type>.
  • In {arrayset <ExprI> <ExprI> <ExprI>}, the first <ExprI> must have type array-of-<Type> (for some <Type>), the second <ExprI> must produce an index into the array, and the the third <ExprI> must have a type that is a subtype of <Type> to produce a value to put into the array; the result is always 0.
★★ 10.[Pre-requisite: 9] 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.
★★ 11.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. Allow fields to referenced directly, like method arguments (i.e., using the field name as an expression instead of using a get form).
★★★ 12.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.
★★★★ 13.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 super-interfaces). 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.
★★★★ 14.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).

Last update: Tuesday, November 15th, 2016
mflatt@cs.utah.edu