 |
CSE583 Assignment 2 Solution (Winter 2000) |
|
CSE Home |
About Us |
Search |
Contact Info |
See the basic page on assignments for program weights, rules for working in pairs, etc.
This assignment is due on Friday, February 11, 2000 at 5PM PST. We will make an announcement later about the specific electronic form for turning in the assignment.
There is no programming for this assignment!
Recall the rules for contravariance and covariance: I'll
use the convention that a ' after a type variable denotes subtyping,
so S' <= S and T' <= T. With this convention,
contravariance means S->T' <= S'->T and covariance means S'->T'
<= S->T. Recall also that to determine whether a (complex)
type U is a subtype of another (complex) type V, we first determine
whether U has at least as much information as V (i.e. all fields and
methods of V appear in U) and then whether all the elements of U
which also appear in V are subtypes of their corresponding V
element. (In other words, if field or function f appears in V,
it must appear in U and the version of f in V must be a subtype of
the version of f in V.) In the end, we'll need to determine
which versions of eat and make (whether instantiated with integers
or numbers) are subtypes of one another. In the following
table, eat[I] is the version of eat instantiated with Integer,
make[N] is the version of make instantiated with Number, etc.
The column labeled Type signature is the type signature of the
proposed subtype relationship. The column labeled Generic Type
signature is the type signature with Integer converted to S' (or T')
and Number converted to S (or T) as appropriate, to indicate that
Integer is a subtype of Number. Once the subtyping relation is
expressed in these terms, we can simply check it against the
contravariance and covariance patterns above. (Note that every
type is a subtype of itself, so void<=void is always true.)
| Functions | Type signature | Generic Type signature | Contravariance?
S->T' <= S'->T |
Covariance?
S'->T' <= S->T |
| eat[I] <?= eat[N] | Int->void <?= Num->void | S'->T <?= S->T | No | Yes |
| eat[N] <?= eat[I] | Num->void <?= Int->void | S->T <?= S'->T | Yes | No |
| make[I] <?= make[N] | void->Int <?= void->Num | S->T' <= S->T | Yes | Yes |
| make[N] <?= make[I] | void->Num<?= void->Int | S->T <= S->T' | No | No |
Each of the following answers uses the contravariance column of the above table to compare function subtyping relationships. For brevity, I will abbreviate Producer as P, Consumer as C and ProducerConsumer as PC and Integer and Number as I and N respectively.
There are two steps to determine whether A <= B. 1) Determine whether all variables and functions defined in B are also defined in A; and 2) Determine whether the versions of those variables or functions, as defined in A are subtypes of the versions defined in B.
Each part is worth 3 points
Again, the basic procedure is: 1) are all the fields and methods provided by the potential supertype also provided by the potential subtype and 2) are all those fields and methods appropriately subtyped, this time according to the covariance rule.
Each part is worth 3 points. Those parts for which example code is required to show why covariance breaks, the correct answer is worth 2 points and the example is worth 1 point. If you gave a correct example for at least one of the cases to which it applied, I gave credit for each case to which it applied. (In particular, parts A, B and F all have basically the same example, because they all fail when you try to call eat[I](1.1), but part G has a different one, so you could get full credit with all correct answers and 2 examples.)
People gave many scenarios, and most were acceptable. One common example was heterogeneous collections, for example, a list of items. Either you're forced to specify what kind of items will be in the list, which is undesirable because you may not know at compile time, or to use some sort of rooted hierarchy (like having a list of Objects in Java). This is undesirable because it forces everything in the list to be of that type. This means you can't put things into the list unless they were designed to go in. It also means you loose information about the type of the objects.
Another less common example was dynamic creation of classes at runtime. Since, by definition all classes must be known at compile time in a statically typed system, this is not possible.
Since the question said to argue either way, I allowed either a yes or no answer and judged based on the degree to which the argument supported the answer. Most people did fairly well on this question. Those who said multi-methods make programs easier to understand and change typically argued from reduced code size, reduced complexity of functions and the ability to determine, by inspection, which classes have a version of the method implemented. Some people also discussed the savings with respect to hand-coded double dispatching.
Those who said multi-methods do not make programs easier to understand typically discussed the additional complexity introduced in figuring out which multi-method would be invoked at runtime, the loss of encapsulation and the loss of locality of code (methods are no longer defined in the same file with the class to which they belong.)
While both of these arguments are fine, it seemed that many people quoted straight out of the Cecil paper (or other papers.) There were a number of phrases that appeared many times almost verbatim, such as "... reduces complexity by avoiding coding logic (switch statements) and because small methods further reduce complexity, as code complexity doesn't grow linearly with lines of code per method, but perhaps exponentially." This was really disappointing. The idea of these assignments is to get you to think about the issues in programming language design, not parrot back information from the readings and lectures.
Yes, since function call dynamic dispatch is implemented by calling the metaclass, it would be pretty trivial to augment the code that implements that dispatch to also increment a function-specific counter.
No, the metaclass is not invoked for variable assignments, variables going out of scope or formal parameter binding so it has no way to keep track of what variables refer to an object. Unless this is a pure OO language in which all variables are instance variables of some object and assignment is treated as a message. In that case, reference counting could be done, but there would still be no way to invoke the garbage collector. You could put it in the metaclass constructor, but that would still cause problems for generational garbage collection. Some people seemed confused about what reference counting is. They argued that you could increment a counter whenever an object was allocated and decrement it when the object was deallocated. This tells you how many instances of the classes exist, but not how many references there are to those instances.
Some people argued that you could do this, and I gave partial credit based on the completeness of the argument.
Yes, simply agument the normal dynamic dispatch mechanism, which is implemented in the metaclass, to look at other arguments. Many people argued that this wasn't possible because, according to the Cecil paper, multi-methods belong to all the arguments' classes. However, one should not confuse this theoretical notion with implementation detail. We can think of the multi-method as belonging to several classes, and still implement it using MOP. For all the remaining nay-sayers, not only are multi-methods in CLOS implemented using the MOP, but the book "The Art of the Meta-Object Protocol" by Kiczales (affectionately known as "AMOP") uses this exact problem as its working example.
Yes, simply create a metaclass which, instead of linearizing the variables in the multiple inheritance hierarchy, checks for conflicts and reports an error. However, since lisp is dynamically typed, and the metaclass methods that do this are invoked at runtime, it would be hard to have the disallowed name conflicts be detected statically.
|
|
|
 |
Department of Computer Science & Engineering
University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to notkin] |