CS 3520 Homework 13

Due: Friday, December 15th, 2023 11:59pm

Submit your work by scheduling a meeting with an instructor [link to appear; watch for announcement], 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.rhm. typed_class.rhm, inherit.rhm. inherit_parse.rhm. and class.rhm. 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:

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

The options are somewhat underspecified and open-ended, so you will need to make some reasonable choices and be ready to defend them, particularly with respect to whether your choices are sound (i.e., interpreter and type checker are consistent). The intent in most cases is to imitate Java, so you may find it useful to browse the Java Language Specification: https://docs.oracle.com/javase/specs/.

 1.Add a (<Symbol>)<ExpI> cast 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 (<Symbol>)<ExpI> expression 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. Note: “subtype” and “supertype” here are reflexive relations. Note also that the implementation will require a run-time check to make sure that a cast is ok; the cast form cannot be handled by just only the type checker.
Tip: In your parser, use the pattern '($(id :: Identifier))$exp' to avoid matching too many parenthesized forms.
★★ 2.Change type checking so that an overridden method’s result type can vary covariantly and its argument types can vary contravariantly. (Knowing what “covariantly” and “contravariantly” mean here is part of the exercise.) Your implementation must include examples/tests that demonstrate how your type checker soundly allows programs rejected by the initial type checker, and also examples where that your new type checker still correctly rejects.
★★ 3.Add an if <ExpI> == 0 | <ExpI> | <ExpI> form to the language, where if requires a number for the expression before ==. 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. (Note: “subtype” and “supertype” here are reflexive relations.)
★★ 4.

Add support for declaring private methods that can only be called via this. or super.. Other method calls that would invoke private methods should be rejected statically. A private method cannot be overriden by a public method or vice-versa.

★★ 5.Add a local-binding expression form like let <Symbol> :: <Type> = <ExpI>: <ExpI>, but you can pick whatever syntax you like. You’ll need to also allow identifiers as expressions, and your typechecker must ensure that there are no free identifiers. Also, allow the argument name for a method to be something other than arg. Disallow this as a local variable name or as a method argument name.
★★ 6.[Pre-requsite: 5] Allow fields to be referenced directly within a method using the field name as an expression instead of using a this. form. For example, in a class has a size field, then size as an expression within a method refers to that field. Methods in a subclass should be able to directly reference fields declared in superclasses; you can assume that all field names are distinct. Method and local-variable names should shadow field names; for example, if a method of a class has a size argument, then size as an expression refers to the argument of the method, and a size field would only be accessible within the method using this.size.
★★ 7.Add imperative field assignment to the language. That is, in addition to the <ExpI>.<Symbol> form, add a <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 := 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. That test must be just a Moe program; trying to use begin or let at the Shplait level will not work. If you don’t implement local binding, then constructing the test is challenging, but not impossible.
★★ 8.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 null.x or 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.
★★ 9.[Natural in combination with 7 and 8] Add support for constructors in class definitions, where a constructor when declared is used by new instead of the default constructor that expects one value for each field. A default constructor should still be supported, so that all old code works. If you implement field assignment and null, then you can have constructors work by creating an object with default values and have the constructor assign fields (and you probably also want to add begin). If you don’t implement field assignment and null, then your constructors will need to somehow functionally provide the values of fields for a new object. You get to pick how the constructor works for a subclass when the superclass has a constructor, and a subclass of such a superclass does not have to support a default constructor.
★★★ 10.[Pre-requisite: 8] Add Java-style object arrays to the language with the forms new <Type>[<ExpI>], <ExpI>[<ExpI>], and <ExpI>[<ExpI>] := <ExpI>.
  • In new <Type>[<ExpI>], the <ExpI> determines the size of the array, and the initial value for every slot in the array is 0 if <Type> is Int or null otherwise; the whole expression is of type array-of-<Type>.
  • In <ExpI>[<ExpI>], the first <ExpI> must produce an array-of-<Type> (for some <Type>), and the second <ExpI> must produce an integer index into the array; the expression is of type <Type>.
  • In <ExpI>[<ExpI>] := <ExpI>, the first <ExpI> must have type array-of-<Type> (for some <Type>), the second <ExpI> must produce an integer 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. This array assignment 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 assignment as imperative. If you didn’t implement local binding, then constructing the test is challenging, but not impossible.
★★ 11.[Pre-requisite: 10] 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.
★★★★ 12.

Add support for declaring final classes and optimize method calls that will definitely dispatch to a final method (i.e., before interp) to static method calls instead of dynamic method calls. A final class cannot be extended, but a final class can extend a non-final class.

★★★★★ 13.Add Java-style interfaces to the language. An interface is a set of method names and types, 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 Int.
★★★★★★ 14.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.
★★★★★★ 15.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: Wednesday, November 15th, 2023
mflatt@cs.utah.edu