Sample Solutions for Assignment 7
Spring 2002
Chris Stone


Problem 1:

  (a) type1 <= type2
        Q: What can one do with a type2 list?
        A: test for null,
           take the head (a type2) and the tail (a type2 list)
           prepend a value of type type2, obtaining a new longer
              type2 list (while the old list remains unchanged).

        Q: If every type1 is a type2, can we safely perform
           all these operations on a type1 list?
        A: Yes.

  (b) type1 <= type2

        If     type1 <= type2
        then   type1 list <= type2 list  (by part a)
        so     (type1 list) * (type1 list) <= (type2 list) * (type2 list)
        by the rule in class for pairs.

  (c) type1 = type2   (or  type1 <= type2 and type2 <= type1)

        By the rule in class for function types


  (d) type1 <= type2

       Applying the rule for function types twice, we have
       If       type1             <= type2
       then     type2->int        <= type1->int
       and so   (type1->int)->int <= (type2->int)->int

Problem 2:

  Any value of type type1 is (by subsumption) also a value of type
  type2, so it's ok to store in a cell of type   type2 ref.  The
  other way around doesn't work (e.g., putting an nat into an
  even ref)

Problem 3:

  (a)  The C++ behavior is fine.  When the new code
       returns an object with a more specific type, it
       is still (by subsumption) returning an object of
       the more general type, so even if we are treating
       a Cow object as if it were an Animal, we're still
       guaranteed to get at least an object of type Food
       back from the favoriteFood method.

  (b)  This is a well-known flaw in the original Eiffel
       design.   In the example shown, since every
       Cow is an Animal by subsumption, Animals ha e a method
       eat that can take any Food object, the type system
       cannot prevent us from passing any non-Vegetable Food
       we want to a Cow object, which at run-time leads to
       Cow's code for the eat method being called with a
       non-Vegetable argument.

  (c)  This would also be ok.  If the subclass replaces code
       the superclass's code with new code that which works on
       all the same arguments plus more, there is no safety problem
       with treating the subclass as a subtype.  So, if
       we treat an Omnivore object as an Animal and give it
       a Vegetable argument, at run-time it will be the
       Omnivore's version of eat that gets invoked, which
       is perfectly happy with not just Vegetables but
       any kind of food.