Re: subtyping and inheritance

From: Giuseppe Castagna (Giuseppe.Castagna@ens.fr)
Date: Tue Apr 20 1999 - 17:06:38 MET DST


Date: Tue, 20 Apr 1999 17:06:38 +0200
From: Giuseppe Castagna <Giuseppe.Castagna@ens.fr>
To: Didier.Remy@inria.fr
Subject: Re: subtyping and inheritance

Didier Remy wrote:
>
> The works [1] and [2] that you cite apply to the languages O2 and Java.
> However, both languages have a very weak type system. In particular, neither
> one supports polymorphic types (hence parametric classes) or self types.
> Thus, I don't think that your experiences with O2 and Java can immediately
> be transfered to Ocaml. In particular, adding dynamics types in the
> presence of polymorphism is much more complex than the simple sketch above.
> Also, regarding type checking, you probably need the higher-order version of
> lambda-&, which is much more difficult than the first-order version that you
> are using in [1] and [2]. Of course, type inference is likely to be another
> complication...
>
> So I do not think that applying [1] or [2] to Ocaml is an implementation
> exercise. It certainly remains an interesting, but serious and probably
> difficult, research project.
>

I completely agree, it is quite difficult (maybe impossible) to do it if you
want it fully general. But I was thinking of solving the particular problem
raised by Markus that, even though it does not reduce to an implementation
exercise, does not look so hard as the general case.
   Consider the example of binary method described in the reference manual and
let me modify it a little bit (even though the resulting code is a nonsense, it
is just for the sake of the example).

# class virtual comparable =
    object (_ : 'a)
      method virtual leq : 'a -> bool
    end;;

# class money (x : float) =
    object (self : 'mytype)
      inherit comparable
      val repr = x
      method value = repr
      method leq (p:'mytype) = repr <= p#value
    end;;

# class money2 x =
    object
      inherit money x
       method leq (p:'mytype) = repr <= (p#value -. p#square)
       method square = repr *. repr
    end;;

As it is said the reference manual money2 is not a subtype of money. The problem
Markus raised was (if I understood correctly) why cannot we use a money2
instance where a money instance is expected, and use the money method for leq if
the one of money2 does not work? What I was suggesting is to obtain the behavior
above by a little modification. Declare money2 as follows

# class money2 x =
    object
      inherit money x
       method dynamic leq (p:'mytype) = repr <= (p#value -. p#square)
       method square = repr *. repr
    end;;

What the "dynamic" modifier means? First of all, it means that money2 is a
subtype of money (that is it allows contravariant occurrences of 'mytype). It
also means that whenever this dynamic-declared method leq is selected, then the
systems checks whether its actual argument is an instance of money2. If it is
then it executes the method, otherwise it performs a method look-up (and selects
the leq method in money).

How can this be implemented? The compiler associates a counter to every
dynamic-declared binary method (hopefully there shouldn't be a lot), and
increments this counter at every overriding of the method. When an instance of a
class containing dynamic binary methods is created, all the counters of the
dynamic methods of the class are stored in the instance.
  When a dynamic method is selected its counter is compared with the
corresponding counter of the object argument; if they match, then the method is
executed, otherwise the method is looked-up in the hierarchy above.

Note that this does not mean to have complete type assignment or general dynamic
types. It just introduces some very specific marks for a very specific problem.
You can call it a "patch", if you want :-)
   I do not claim that all of this is straightforward (in particular if you want
to generalize it to methods that are not binary), but as long as I know it
should not be unfeasible (one should introduce some restrictions of course).
Finally, this solution works only if it is possible to "perform a method
look-up" in Ocaml; but to address this issue one must know Ocaml's
implementation, and I don't.

Whether it is worth doing it is different question I cannot answer. It is the
Ocaml users community that has to answer it.

Cheers

---Beppe---



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:22 MET