subtyping and inheritance

subtyping and inheritance

[Markus Mottl]

Hello again,

this time a question about inheritance and subtyping...
Let's consider the following code snippet:

---------------------------------------------------------------------------
class foo =
object (self:'self)
  method x = "x"
  method eq (other:'self) = if self#x = other#x then true else false
end

class bar =
object
  inherit foo
  method y = "y"
end

let f = new foo
and b = new bar
;;

print_string (string_of_bool (f #eq f)); print_newline ();
print_string (string_of_bool (b #eq b)); print_newline ();
---------------------------------------------------------------------------

So far no problem. Class "bar" inherits from "foo" and adds a method.
The program will print out two times "true", because objects of type
"foo" can be tested for equivalence within their class and objects of type
"bar" as well.

But now, I would really like to compare objects of type "foo" with
objects of type "bar" as in:

---------------------------------------------------------------------------
print_string (string_of_bool (f #eq (b :> foo))); print_newline ();
---------------------------------------------------------------------------

This is, of course, not possible, because "bar" is not a subtype of
"foo" and thus, cannot be coerced to "foo".

But "bar" inherits everything from "foo" so I think it would be safe
to call methods ** as they are defined in "foo" **. I think the problem
occurs because of the following rule taken from the OCAML manual:

  Only the last definition of a method is kept: the redefinition in a
  subclass of a method that was visible in the parent class overrides
  the definition in the parent class.

This rule prohibits that definitions as they appear in the parent
class may be reused in case that an object of a subclass (in terms of
inheritance, not subtyping!) shall be seen from the parent's "point
of view". In the upper case, method "eq" is automatically redefined,
because it has the type "'self" in its signature.  Actually, *this*
is the problem, not the additional method "y" as is stated at the end
of the error message generated on the last "print_string...".

My specific problem is: I have a program with classes for "terminal"
and "nonterminal" symbols. Both inherit from a base class "symbol". The
symbol class inherits from a class "ord", which defines a virtual method
"compare". This allows me to compare terminals with terminals and
nonterminals with nonterminals, but it also allows comparison between
symbols (all three classes redefine "compare").

Look at this graph:

         ord                ->  defines virtual method "compare"
          |
        symbol              ->  redefines "compare"
       /      \
   terminal  nonterminal    ->  both redefine "compare"

But the problem is: I will never be able to compare terminals and
nonterminals with each other, because the appropriate comparison method
as defined in "symbol" has been "forgotten" - it is redefined in all
child classes. Thus, I am not able to coerce them to "symbol".

I have worked around this with the following inheritance scheme:

    ---- ord -----          ->  defines virtual method "compare"
    |            |
    |   symbol   |          ->  has a method "compare_symbol"
    |  /      \  |
   terminal  nonterminal    ->  both redefine "compare"

Although it is now possible to coerce terminals and nonterminals
to symbols and have them thus compared via "compare_symbol", I am not
content with this scheme: I would really like to have all methods from
"ord" in "symbol", which all make use of the virtual "compare" method.

I am neither sure whether I am overlooking some clever trick to get the
result I want, nor whether a change in the handling of coercions ("memory"
for methods of parent classes) is really safe. But at the moment I cannot
think of any way to circumvent type safety. Comments on this welcome!

Best regards,
Markus

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: subtyping and inheritance

[Jerome Vouillon]

Hello,

> My specific problem is: I have a program with classes for "terminal"
> and "nonterminal" symbols. Both inherit from a base class "symbol". The
> symbol class inherits from a class "ord", which defines a virtual method
> "compare". This allows me to compare terminals with terminals and
> nonterminals with nonterminals, but it also allows comparison between
> symbols (all three classes redefine "compare").
> 
> Look at this graph:
> 
>          ord                ->  defines virtual method "compare"
>           |
>         symbol              ->  redefines "compare"
>        /      \
>    terminal  nonterminal    ->  both redefine "compare"
> 
> But the problem is: I will never be able to compare terminals and
> nonterminals with each other, because the appropriate comparison method
> as defined in "symbol" has been "forgotten" - it is redefined in all
> child classes. Thus, I am not able to coerce them to "symbol".
> 
> I have worked around this with the following inheritance scheme:
> 
>     ---- ord -----          ->  defines virtual method "compare"
>     |            |
>     |   symbol   |          ->  has a method "compare_symbol"
>     |  /      \  |
>    terminal  nonterminal    ->  both redefine "compare"
> 
> Although it is now possible to coerce terminals and nonterminals
> to symbols and have them thus compared via "compare_symbol", I am not
> content with this scheme: I would really like to have all methods from
> "ord" in "symbol", which all make use of the virtual "compare" method.

I think the method "compare" in class "ord" need not be a binary method: its
argument type can probably instead be a type parameter of the class.
    class virtual ['a] ord = object
      method virtual compare : 'a -> bool
      (* ... *)
    end;;
Then, the method "compare" can be given the type "symbol -> bool" in
class "symbol" (and its subclasses) :
    class symbol = object (self)
      inherit [symbol] ord
      method x = "x"
      method compare other = self#x = other#x
    end;;
    class terminal = object
      inherit symbol
      method x = "a"
      method y = "y"
    end;;
This way, you can compare objects from the class "symbol" and any of
its subclasses.
    # new terminal#compare new symbol;; 
    - : bool = false
    # new terminal#compare (new terminal :> symbol);;
    - : bool = true

Regards,

-- Jerome

Re: subtyping and inheritance

[Markus Mottl]

Hello,

> I think the method "compare" in class "ord" need not be a binary method: its
> argument type can probably instead be a type parameter of the class.
>     class virtual ['a] ord = object
>       method virtual compare : 'a -> bool
>       (* ... *)
>     end;;
> Then, the method "compare" can be given the type "symbol -> bool" in
> class "symbol" (and its subclasses) :
>     class symbol = object (self)
>       inherit [symbol] ord
>       method x = "x"
>       method compare other = self#x = other#x
>     end;;
>     class terminal = object
>       inherit symbol
>       method x = "a"
>       method y = "y"
>     end;;
> This way, you can compare objects from the class "symbol" and any of
> its subclasses.
>     # new terminal#compare new symbol;; 
>     - : bool = false
>     # new terminal#compare (new terminal :> symbol);;
>     - : bool = true

I am really sorry - I have probably not explained the problem well enough:

What I want to do is:

Compare terminals to terminals:
  Via a method "compare", which is naturally defined in class "terminal"
  This method calls methods in "other", which are only found in terminals

Compare nonterminal to nonterminal:
  Via a method "compare", which is naturally defined in class "nonterminal"
  This method calls methods in "other", which are only found in
  nonterminals

Compare symbols to symbols:
  Via a method "compare", which is naturally defined in class "symbol"
  This method calls methods in "other", which are found in nonterminals
  and terminals the like

The base class "ord" has some useful functions like "leq", "gt", etc...
I would like to use them without having to redefine them in every class.

If I change your example into the direction I want, I would change class
"terminal" e.g. as follows:

  class terminal = object (self)
    inherit symbol
    method x = "a"
    method y = "y"
    method compare (other : terminal) = self#y = other#y (* line 15 *)
  end

Here, I compare terminals to each other with a totally different
comparison method than the one found in "symbol".  Unfortunately, your
example won't type check correctly anymore: the compiler generates the
(certainly not correct) message:

  File "bla.ml", line 15, characters 47-52:
  This expression has type terminal
  It has no method y

But "terminal" *has* a method "y"!!! The problem is that "compare" has
been instantiated in "symbol" with "symbol" as type parameter to "ord".
Thus, the method "compare" has type "symbol -> bool".  The compiler still
believes that "compare" should have this type, but wrongly takes the
type information provided in the declaration of "compare" in "terminal",
which declares "compare" to be of type "terminal -> bool". This results
in the incorrect error message that "terminal" has no method "y".

What the compiler actually should flag is the (here) incorrect
redefinition, or better *redeclaration* (due to other type) of "compare".

My proposition for the resolution of this conflict (I have no idea
whether this might result in inconsistencies - I am sure you can judge
this better):

  If an object that has inherited from another class is coerced to this
  class, then the definition *and* the type of all methods should be
  taken from this ancestor. Because the object *must* have all the data
  defined in its ancestor (it has inherited all of it), the use of the
  ancestor's methods should not lead to any inconsistencies.

  E.g.

    class virtual ord = object (self:'self)
      method virtual compare : 'self -> bool
    end
    
    class symbol = object (self)
      inherit ord
    
      val mutable symbol_order = 0
      method symbol_order = symbol_order
    
      method compare other = self#symbol_order = other#symbol_order
    end
    
    class terminal = object (self)
      inherit symbol
    
      val mutable terminal_order = 0
      method terminal_order = terminal_order
    
      method compare other = self#terminal_order = other#terminal_order
    
      initializer symbol_order <- 1
    end
    ;;
    
    (new terminal :> symbol)#compare new symbol


  The last line should be resolved as follows:

  "new terminal :> symbol" should be allowed to be coerced to "symbol"
  (although the type of "compare" is not the same). The method "compare"
  is taken from "symbol" - this is intuitive and should lead to no
  inconsistencies (I hope so ;-)

  With this definition we arrive at:
    self#symbol_order = other#symbol_order

  equals "false" (0 = 1), because "symbol_order" has been initialized
  (overwritten) in "terminal" with "1".

Actually, the error message of the compiler for this example code is
(in my eyes) also misleading. It says:

  File "bla.ml", line 26, characters 1-13:
  This expression cannot be coerced to type
    symbol = < compare : symbol -> bool; symbol_order : int >;
  it has type
    terminal =
      < compare : terminal -> bool; symbol_order : int; terminal_order : int >
  but is here used with type
    < compare : symbol -> bool; symbol_order : int; terminal_order : int >
  Type
    terminal =
      < compare : terminal -> bool; symbol_order : int; terminal_order : int >
  is not compatible with type
    symbol = < compare : symbol -> bool; symbol_order : int >
  Only the first object type has a method terminal_order

Although it is correct that types "terminal" and "symbol" are
incompatible, the reason is *not* that "only the first object type has a
method terminal_order". An additional method in the object to be coerced
does not harm coercion.  Coercion is only impossible if the object lacks
some methods or has methods of another type. The latter is the case
in this example: "compare" in "terminal" does not match "compare" in
"symbol". My proposition would change this mismatch, because the method
(including its type) is then taken from symbol.

It took me quite some time to figure out what this error message really
meant when I began to play around with the class system...

I hope that my explanations are not hopelessly incomprehensible or
unuseful and would like to know, whether my proposition would make any
sense in the object calculus of OCAML.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: subtyping and inheritance

[Jerome Vouillon]

> What I want to do is:
> 
> Compare terminals to terminals:
>   Via a method "compare", which is naturally defined in class "terminal"
>   This method calls methods in "other", which are only found in terminals
> 
> Compare nonterminal to nonterminal:
>   Via a method "compare", which is naturally defined in class "nonterminal"
>   This method calls methods in "other", which are only found in
>   nonterminals
> 
> Compare symbols to symbols:
>   Via a method "compare", which is naturally defined in class "symbol"
>   This method calls methods in "other", which are found in nonterminals
>   and terminals the like

So, you want to be able to select a method depending on two
objets. This is not directly possible, but you can encode it using two
successive method calls:

    class type symbol_t = object
      method x : int
    end and terminal_t = object
      inherit symbol_t
      method y : int
    end;;
    class symbol x = object (self : 'a)
      method x = x

      method compare (other : symbol) =
        other#compare_with_symbol (self :> symbol_t)
      method compare_with_symbol other = self#x = other#x
      method compare_with_terminal (other : terminal_t) = false
    end;;
    class terminal x y = object (self)
      inherit symbol x
      method y = y

      method compare (other : symbol) =
        other#compare_with_terminal (self :> terminal_t)
      method compare_with_symbol other = false
      method compare_with_terminal other =
        (self#x = other#x) && (self#y = other#y)
    end;;

> If I change your example into the direction I want, I would change class
> "terminal" e.g. as follows:
> 
>   class terminal = object (self)
>     inherit symbol
>     method x = "a"
>     method y = "y"
>     method compare (other : terminal) = self#y = other#y (* line 15 *)
>   end
> 
> Here, I compare terminals to each other with a totally different
> comparison method than the one found in "symbol".  Unfortunately, your
> example won't type check correctly anymore: the compiler generates the
> (certainly not correct) message:
> 
>   File "bla.ml", line 15, characters 47-52:
>   This expression has type terminal
>   It has no method y
> 
> But "terminal" *has* a method "y"!!! The problem is that "compare" has
> been instantiated in "symbol" with "symbol" as type parameter to "ord".
> Thus, the method "compare" has type "symbol -> bool".  The compiler still
> believes that "compare" should have this type, but wrongly takes the
> type information provided in the declaration of "compare" in "terminal",
> which declares "compare" to be of type "terminal -> bool". This results
> in the incorrect error message that "terminal" has no method "y".

Here is an explanation of this error message. Just before typing the
method "compare" in class "terminal", we know that its type must be
"symbol -> bool". However, we don't know anything about the type
"terminal" yet (this type will have to be a suitable instance of the
type of self, but this can only be checked once the whole class body
is typed). Then, the type constraint "(other : terminal)" tells the
compiler that the type "terminal" must be the same as the type of the
argument of the method, that is "symbol". This will not be possible,
but the compiler does not know it yet. Then, the type checking fails
because "other", of type "symbol" has no method "y".

I will try to provide a better error message.

>     class virtual ord = object (self:'self)
>       method virtual compare : 'self -> bool
>     end
>     
>     class symbol = object (self)
>       inherit ord
>     
>       val mutable symbol_order = 0
>       method symbol_order = symbol_order
>     
>       method compare other = self#symbol_order = other#symbol_order
>     end
>     
>     class terminal = object (self)
>       inherit symbol
>     
>       val mutable terminal_order = 0
>       method terminal_order = terminal_order
>     
>       method compare other = self#terminal_order = other#terminal_order
>     
>       initializer symbol_order <- 1
>     end
>     ;;
>     
>     (new terminal :> symbol)#compare new symbol
[...]
> Actually, the error message of the compiler for this example code is
> (in my eyes) also misleading. It says:
> 
>   File "bla.ml", line 26, characters 1-13:
>   This expression cannot be coerced to type
>     symbol = < compare : symbol -> bool; symbol_order : int >;
>   it has type
>     terminal =
>       < compare : terminal -> bool; symbol_order : int;
>         terminal_order : int >
>   but is here used with type
>     < compare : symbol -> bool; symbol_order : int; terminal_order : int >
>   Type
>     terminal =
>       < compare : terminal -> bool; symbol_order : int;
>         terminal_order : int >
>   is not compatible with type
>     symbol = < compare : symbol -> bool; symbol_order : int >
>   Only the first object type has a method terminal_order

Here is how you should understand this error message.  The method
"compare" in an object of class "terminal" has type "terminal ->
bool". Therefore, it can make use of the method "terminal_order" of
its argument. Thus, as the type "symbol" has no method
"terminal_order", the method "compare" cannot be given the type
"symbol -> bool". Hence, finally, the type "terminal" is not a subtype
of type "symbol", and the coercion is not possible.

-- Jérôme

Re: subtyping and inheritance

[Markus Mottl]

Hello,

> So, you want to be able to select a method depending on two
> objets. This is not directly possible, but you can encode it using two
> successive method calls:
> 
>     class type symbol_t = object
>       method x : int
>     end and terminal_t = object
>       inherit symbol_t
>       method y : int
>     end;;
>     class symbol x = object (self : 'a)
>       method x = x
> 
>       method compare (other : symbol) =
>         other#compare_with_symbol (self :> symbol_t)
>       method compare_with_symbol other = self#x = other#x
>       method compare_with_terminal (other : terminal_t) = false
>     end;;
>     class terminal x y = object (self)
>       inherit symbol x
>       method y = y
> 
>       method compare (other : symbol) =
>         other#compare_with_terminal (self :> terminal_t)
>       method compare_with_symbol other = false
>       method compare_with_terminal other =
>         (self#x = other#x) && (self#y = other#y)
>     end;;

To solve this problem I've done something similar (defined an extra
comparison method for symbols in class symbol) - I don't know of any
better means. But as is obvious: this workaround unfortunately does not
really exhibit the virtues of code reuse...

Even worse (taking your example): if I add another kind of symbol (say,
a nonterminal symbol), I would have to write a comparison method for
each kind of symbol already in the class hierarchie. But not enough: I
would have to change all of the older classes to recognize the new one!
This all, although many of the comparison functions are (syntactically)
the same and would only have to be instantiated with another type in
the new class.

> > But "terminal" *has* a method "y"!!! The problem is that "compare" has
> > been instantiated in "symbol" with "symbol" as type parameter to "ord".
> > Thus, the method "compare" has type "symbol -> bool".  The compiler still
> > believes that "compare" should have this type, but wrongly takes the
> > type information provided in the declaration of "compare" in "terminal",
> > which declares "compare" to be of type "terminal -> bool". This results
> > in the incorrect error message that "terminal" has no method "y".
> 
> Here is an explanation of this error message. Just before typing the
> method "compare" in class "terminal", we know that its type must be
> "symbol -> bool". However, we don't know anything about the type
> "terminal" yet (this type will have to be a suitable instance of the
> type of self, but this can only be checked once the whole class body
> is typed). Then, the type constraint "(other : terminal)" tells the
> compiler that the type "terminal" must be the same as the type of the
> argument of the method, that is "symbol". This will not be possible,
> but the compiler does not know it yet. Then, the type checking fails
> because "other", of type "symbol" has no method "y".
> 
> I will try to provide a better error message.

Seems that my explanation was not totally wrong (I have not seen the code
yet). I didn't know that the compiler would have to know the whole body
of the class before it can emit the correct message. I (wrongly) believed
that the compiler incrementally extends the interface while interpreting
the type information of the methods. Hm, probably a stupid idea...

I am not sure, but I can imagine it's a bit tricky to delay the
message. The compiler knows that something is wrong, but might need
exactly the (inconsistent) type information from the incorrect part to
interpret the rest of the methods in the class definition. It would
have to ignore the resulting incorrectness of those methods without
"forgetting" the true source of the error.

[snip second error message]

> Here is how you should understand this error message.  The method
> "compare" in an object of class "terminal" has type "terminal ->
> bool". Therefore, it can make use of the method "terminal_order" of
> its argument. Thus, as the type "symbol" has no method
> "terminal_order", the method "compare" cannot be given the type
> "symbol -> bool". Hence, finally, the type "terminal" is not a subtype
> of type "symbol", and the coercion is not possible.

Ah! That's the way the compiler concludes! When I first encountered this
message, I always wondered what was wrong about method "terminal_order"
- I didn't look to deeply into the rest of the output...

It should take me some time to see that it's method "compare" that
causes the trouble - by invoking methods that do not exist in "symbol"
but are required there - yet I didn't come to this last conclusion.

If the compiler emits a huge bunch of class interfaces in error messages
the human user can often be overcharged with interpreting this amount
of information... ;-)

Best regards,
Markus

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: subtyping and inheritance

[Hendrik Tews]

Hi,

Markus Mottl writes (in reply to Jerome Vouillon):
   From: Markus Mottl <mottl@miss.wu-wien.ac.at>
   Date: Mon, 18 Jan 1999 22:18:40 +0100 (MET)
   Subject: Re: subtyping and inheritance
   
   Hello,
   
   > So, you want to be able to select a method depending on two
   > objets. 

   [...]
   
   To solve this problem I've done something similar (defined an extra
   comparison method for symbols in class symbol) - I don't know of any
   better means. But as is obvious: this workaround unfortunately does not
   really exhibit the virtues of code reuse...
   
This is true. But what you really need to solve your problem is a
feature called sometimes "(covariant) specialization of code".
Ocaml does not have this feature. Therefore you can not hope for
a solution which is typesafe and supports code reuse. Ocaml does
provide the feature "contravariant subtyping", which gives you a
save subtype relation. There is nice paper of Guiseppe Castagna
"Covariance and Contravariance: Conflict without a Cause" [1]
which discusses those features and their relation. 

This paper and the references therein contain also proposals how
to integrate specialization of code into a record based object
oriented language. Is their any hope, that ocaml adopts this (or
any other) solution in the future, such that Markus can implement
comparison of terminals and symbols in a clean way?

There was already a proposal how to solve the problem by Jerome
Vouillon. Just for demonstration I append another solution, which
uses a self implemented type case. It supports code reuse better,
but loses type security by using the Obj module. Maybe one of the
people who "understand the whole source code for the O'Caml
compiler, runtime and libraries" and by that can use the Obj
module, can comment on its use here.
;-)

[1] G. Castagna. Covariance and contravariance: conflict without
a cause. ACM Transactions on Programming Languages and Systems
17(3):431-447, March 1995. Also available at
http://www.ens.fr/~castagna/pub.html.

Gruss,

Hendrik


exception No_subclass

(* always use unique numbers for this_dynamic_type for every class,
   such that 
     this_dynamic_type(class1) mod this_dynamic_type(class2) = 0
              if and only if
     class1 inherits from class2
*)

class top = let this_dynamic_type = 1 in
object (self : 'self)
  method dynamic_type = this_dynamic_type
  method subclass (super : int) (sub : top) =
		(* sub belongs to a subclass of super *)
    sub#dynamic_type mod super = 0

  method eq (x : top) = print_string "top = top ? "; true
end 

class left (l1 : int) = let this_dynamic_type = 2 in
  object (self : 'self)
  inherit top as super
  method dynamic_type = this_dynamic_type
  method private cast_left other =
    if self#subclass this_dynamic_type other 
    then (Obj.magic(other) : left)
    else raise No_subclass

  method eq (x : top) = 
    try let x' = self#cast_left(x) in 
    begin
      print_string "left = left ? "; 
      self#m_left = x'#m_left
    end
    with No_subclass -> super#eq(x)

  method m_left = l1
end

class right (r1 : int) = let this_dynamic_type = 3 in
  object (self : 'self)
  inherit top as super
  method dynamic_type = this_dynamic_type
  method private cast_right other =
    if self#subclass this_dynamic_type other 
    then (Obj.magic(other) : right)
    else raise No_subclass

  method eq (x : top) = 
    try let x' = self#cast_right(x) in 
    begin
      print_string "right = right ? "; 
      self#m_right = x'#m_right
    end
    with No_subclass -> super#eq(x)

  method m_right = r1
  end

let l1 = new left 1
let l2 = new left 2
let r1 = new right 1

let x = l1#eq(l2:>top)
let y = r1#eq(l1:>top)

Re: subtyping and inheritance

[Markus Mottl]

Hello,

> This is true. But what you really need to solve your problem is a
> feature called sometimes "(covariant) specialization of code".
> Ocaml does not have this feature. Therefore you can not hope for
> a solution which is typesafe and supports code reuse. Ocaml does
> provide the feature "contravariant subtyping", which gives you a
> save subtype relation. There is nice paper of Guiseppe Castagna
> "Covariance and Contravariance: Conflict without a Cause" [1]
> which discusses those features and their relation. 
> 
> This paper and the references therein contain also proposals how
> to integrate specialization of code into a record based object
> oriented language. Is their any hope, that ocaml adopts this (or
> any other) solution in the future, such that Markus can implement
> comparison of terminals and symbols in a clean way?

> [1] G. Castagna. Covariance and contravariance: conflict without
> a cause. ACM Transactions on Programming Languages and Systems
> 17(3):431-447, March 1995. Also available at
> http://www.ens.fr/~castagna/pub.html.

I have taken a close look on the paper now. As it seems, it exactly
addresses the problem I (and probably many others) have. Quotes with
[remarks]:

  ... Despite its unsoundness, covariant specialization has its tenacious
  defenders, and not without cause. [snip]  The contravariant rule,
  besides being less intuitive than the covariant one, is the source of
  many problems. The most surprising one appears with binary methods
  and can be exemplefied as follows. [snip details of the problem I
  actually have]. This is quite unintuitive [yes, I think so, too]
  [snip]. Furthermore, experience with O2 (which is the third most
  sold object-oriented database management system in the world) shows,
  that the unsoundness of the type-checker has not caused many problems
  in practice.

So far it seems that things would be unsafe with covariance. But now,
Castagna answers my (former) question, whether making "reappear" methods
from ancestors would be safe: it is...

The paper looked difficult at first, but turned out to be surprisingly
easy to read: Castagna makes the theorie very intuitively clear with his
examples of classes "2DPoint" and "3DPoint" and how methods are chosen
in the different models.

The record based method (as found in OCAML - the object (record)
determines, which method is selected, arguments are not considered)
can be obviously extended to support covariance.

Sylvain Boulmé pointed out that semantics could become difficult to
understand. I am not sure whether this would really turn out to be a
problem.  Implementing a large project employing a deep class hierarchie
in both approaches could probably demonstrate, where their strengths
and weaknesses are.  But at the moment, we don't have this choice...

> There was already a proposal how to solve the problem by Jerome
> Vouillon. Just for demonstration I append another solution, which
> uses a self implemented type case. It supports code reuse better,
> but loses type security by using the Obj module. Maybe one of the
> people who "understand the whole source code for the O'Caml
> compiler, runtime and libraries" and by that can use the Obj
> module, can comment on its use here.

[snip code]

Nice example code! I don't know what "Obj.magic" does internally,
but I believe it can do real black (= unintended) magic, too. Thus,
it is certainly not advisable to use it as a surrogate for the missing
feature of covariance.  But Hendrik's intention is surely to demonstrate,
how objects could behave in such an environment...

Best regards,
Markus

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Musings on Obj.magic (Was: subtyping and inheritance)

[David Monniaux]

Here are some slightly off-thread remarks on Obj.magic and why it can be
good:

On Mon, 25 Jan 1999, Markus Mottl wrote:

> Nice example code! I don't know what "Obj.magic" does internally,
> but I believe it can do real black (= unintended) magic, too.

Obj.magic is defined as the identity from any type to any type. Its
semantics are highly dependent on the memory layout of OCaml, and you can
do nasty things like:
# (((Obj.magic A),(Obj.magic B)) : int*int);;
- : int * int = 0, 1

This depends on the fact that in an enumerated datatype, 0-ary
constructors are encoded exactly as integers are encoded. Thus the first
constructor is seen as 0, the second as 1...

Now there are some legitimate (ie non implementation-dependent) uses of
Obj.magic. First, its semantics are well-defined when there exists a proof
of well-typedness in a stronger type system than OCaml's. For instance,
programs exported from Coq may need to be manually patched by inserting
Obj.magic at some places. This has to do with the fact that Coq's typing
is impredicative while OCaml's is not.

Second, it's needed for the toplevel, for printing out values. The type
safety of the procedure that prints the value of the expression the user
has just input relies on the overall safety of the OCaml type checker and
the subject reduction property of OCaml. This means that if the
typechecker says "hey, it's an int*int" you can trust it and cast the
return value into a int*int using Obj.magic. Of course, you can see that
as well-typedness in a proof system that is powerful enough to certify
OCaml's typechecker.

Regards, D. Monniaux

Re: subtyping and inheritance

[Jerome Vouillon]

On Mon, Jan 25, 1999 at 01:08:30AM +0100, Markus Mottl wrote:
[...]
> So far it seems that things would be unsafe with covariance. But now,
> Castagna answers my (former) question, whether making "reappear" methods
> from ancestors would be safe: it is...
> 
> The paper looked difficult at first, but turned out to be surprisingly
> easy to read: Castagna makes the theorie very intuitively clear with his
> examples of classes "2DPoint" and "3DPoint" and how methods are chosen
> in the different models.
> 
> The record based method (as found in OCAML - the object (record)
> determines, which method is selected, arguments are not considered)
> can be obviously extended to support covariance.

However, it is not possible to apply this extension to Ocaml.  Indeed,
it requires that methods are chosen depending on the dynamic type of
their arguments.  But this information is not available in Ocaml.
There are also difficulties for type inference.

-- Jérôme

Re: subtyping and inheritance

[Jerome Vouillon]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2380 bytes --]


On Wed, Jan 20, 1999 at 12:50:21PM +0100, Hendrik Tews wrote:
> There was already a proposal how to solve the problem by Jerome
> Vouillon. Just for demonstration I append another solution, which
> uses a self implemented type case. It supports code reuse better,
> but loses type security by using the Obj module. Maybe one of the
> people who "understand the whole source code for the O'Caml
> compiler, runtime and libraries" and by that can use the Obj
> module, can comment on its use here.

Your example indeed works, as coercions do not actually modify
objects.
When you need to make use of the Obj module, it is however advised to
limit this use to a small module with a type-safe interface. Your
example can be rewritten this way:

class top = object
  inherit Property.c
  method eq (x : top) = print_string "top = top ? "; true
end;;
let left_k = Property.create_key ();;
class left (l1 : int) = object (self)
  inherit top as super
  initializer Property.add left_k self l1
  method eq x =
    try
      let l1' = Property.find left_k x in
      print_string "left = left ? ";
      l1 = l1'
    with Not_found -> super#eq x
end;;
let right_k = Property.create_key ();;
class right (r1 : int) = object (self)
  inherit top as super
  initializer Property.add right_k self r1
  method eq x =
    try
      let r1' = Property.find right_k x in
      print_string "right = right ? ";
      r1 = r1'
    with Not_found -> super#eq x
end;;

-- Jérôme

type 'a t

type u and u'

class virtual s : object
  method virtual properties : u
  method virtual add_property : u' -> unit
end

class c : object
  method properties : u
  method add_property : u' -> unit
end

val create_key : unit -> 'a t
val add : 'a t -> #c -> 'a -> unit
val find : 'a t -> #c -> 'a

filename="property.ml"

type 'a t = int

module Properties = Map.Make (struct type t = int let compare = compare end)

type u' = int * Obj.t
type u = Obj.t Properties.t

class virtual s = object
  method virtual properties : u
  method virtual add_property : u' -> unit
end

class c = object
  val mutable properties = (Properties.empty : u)
  method properties = properties
  method add_property (k, p) = properties <- Properties.add k p properties
end

let i = ref (-1)
let create_key () = incr i; !i

let add p x v = x#add_property (p, Obj.repr v)

let find p x = Obj.obj (Properties.find p (x#properties))

Re: subtyping and inheritance

[Markus Mottl]

> On Mon, Jan 25, 1999 at 01:08:30AM +0100, Markus Mottl wrote:
> [...]
> > So far it seems that things would be unsafe with covariance. But now,
> > Castagna answers my (former) question, whether making "reappear" methods
> > from ancestors would be safe: it is...
> > 
> > The paper looked difficult at first, but turned out to be surprisingly
> > easy to read: Castagna makes the theorie very intuitively clear with his
> > examples of classes "2DPoint" and "3DPoint" and how methods are chosen
> > in the different models.
> > 
> > The record based method (as found in OCAML - the object (record)
> > determines, which method is selected, arguments are not considered)
> > can be obviously extended to support covariance.
> 
> However, it is not possible to apply this extension to Ocaml.  Indeed,
> it requires that methods are chosen depending on the dynamic type of
> their arguments.  But this information is not available in Ocaml.
> There are also difficulties for type inference.

What a pity...

At least we know now, that design questions have to be solved quite
differently in OCAML than in some other OO-languages.

Regards,
Markus

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: subtyping and inheritance

[Hendrik Tews]

Hi,

I don't know how method dispatch is implemented in ocaml. I was
also not able to find a reference about that (is their such?).
Therefore the following is based on some speculation.

   From: Jerome Vouillon <Jerome.Vouillon@inria.fr>
   Date: Wed, 27 Jan 1999 15:18:27 +0100
   Subject: Re: subtyping and inheritance
   
    [concerning covariant method specialization]
   
   However, it is not possible to apply this extension to Ocaml.  Indeed,
   it requires that methods are chosen depending on the dynamic type of
   their arguments.  But this information is not available in Ocaml.
   There are also difficulties for type inference.

But also in ocaml you choose the method depending on the dynamic
type of object to which it is applied (otherwise late binding
could never work). You only had to repeat this process for all
the arguments of the method which are declared for covariant
specialization. 

The absence of dynamic types applies only to arguments which are
not objects. But since other types (than object types) cannot be
related by the subtype relation, covariant specialization would
never apply for such arguments.

Surly, there would be some difficulties to integrate this
feature. But compare that with the gain! Compare those clumsy
solutions to Markus' problem with the ease of simly overriding
the binary method! Being able to really use binary methods in a
type safe environment would IMHO be worth a lot of effort.

Bye,

Hendrik

Re: subtyping and inheritance

[Didier Remy]

> I completely agree, it is quite difficult (maybe impossible) to do it if you
> want it fully general. 

Beppe, 

You won't be surprised if I tell you that I don't like special cases a lot.
Moreover, I don't really know where and how to draw a clear border. Even on
the particular example of money that you took, things are not so simple....

----------------

Typechecking of classes in Ocaml is (relatively) simple because it relies
only on polymorphism and not on subtyping. Subtyping comes later and it is
not essential. In particular, if you never use explicit coercions, there is
actually no subtyping involved at all, and most examples still typecheck,
including binary methods (and much more)!  As a result of this simple
approach, the type of self in a subclass is just an instance of the type of
self in its parent class.

I suspect that you will have to give up this invariant since your approach
is, conversely, based on subtyping and not on polymorphism.  Then, you may
be loosing much of the simplicity or just be unable to formalize the
``patch'' as an ``extension'' of Ocaml.

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

[the type annotation on "p" is useless you bound "'mytype" as the type of
self in "object (_ : 'mytype)"]

What type do you wish to give to that class? In particular, what should be
the (static) type of an object of that class?

> 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). 

Another essential matter is that type comparisons in Ocaml are structural,
as opposed to by-name: this applies to both type equality and
subtyping. Thus, you cannot just ``make'' money2 a subtype of money. Then,
how would you define the subtyping relation so that the type money2 is a
subtype of money?

In conclusion, I think that even when restricting to a small subcase of the
general problem the solution, if it exists as an extension of Ocaml, is not
easy. In any case, I would be very happy to see it on paper...

Cheers,

        -Didier

Re: subtyping and inheritance

[Giuseppe Castagna]

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---

Re: subtyping and inheritance

[Didier Remy]

Dear Beppe,

> Surely, it would require some modifications to the compiler, but all it
> would have to do is to mark some particular methods and all the objects
> that could call these methods by a natural number (for those who know,
> some sort of De Brujin notation, that a purist may consider as dynamic
> type information). How to do it in practice is described for the language
> O2 in [1] (but without the natural numbers since in O2 the dynamic type
> information is available). This is obtained by simply modifying the
> compiler without affecting the language.  

> ...

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.

        -Didier

Re: subtyping and inheritance

[Markus Mottl]

Hello,

thanks for your information! I have now read your paper on "parasitic
methods" (I like this term!) and found it indeed very interesting. It
seems it would be a fine means of solving the problem which was the
starting point of the earlier thread ((covariant) specialization of
comparison methods) - not to speak of the many other possible advantages.

I wonder what the OO-implementors of OCAML think about it - and generally,
whether there are already any intended "surprises" (I mean: nice ones ;-)
for us in one of the next OCAML-releases...

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

Re: subtyping and inheritance

[Giuseppe Castagna]

Sorry to reopen a thread that is more than 2 months old, but I'm not on the
Caml-List and just today Hugo Herbelin hinted me that some of my work has been
discussed on it. So let me add my two cents worth contribution. 


> [...]
> > So far it seems that things would be unsafe with covariance. But now,
> > Castagna answers my (former) question, whether making "reappear" methods
> > from ancestors would be safe: it is...
> > 
> > The paper looked difficult at first, but turned out to be surprisingly
> > easy to read: Castagna makes the theorie very intuitively clear with his
> > examples of classes "2DPoint" and "3DPoint" and how methods are chosen
> > in the different models.
> > 
> > The record based method (as found in OCAML - the object (record)
> > determines, which method is selected, arguments are not considered)
> > can be obviously extended to support covariance.
> 
> However, it is not possible to apply this extension to Ocaml. Indeed,
> it requires that methods are chosen depending on the dynamic type of
> their arguments. But this information is not available in Ocaml.
> There are also difficulties for type inference.

Jerome is right when he says that dynamic type information is not available 
in Ocaml. Nevertheless I would not be so sure that this means that it is not 
possible to apply this extension to Ocaml. Surely, it would require some 
modifications to the compiler, but all it would have to do is to mark some
particular methods and all the objects that could call these methods by a 
natural number (for those who know, some sort of De Brujin notation, that a
purist may consider as dynamic type information). How to do it in practice is 
described for the language O2 in [1] (but without the natural numbers since
in O2 the dynamic type information is available). This is obtained by simply
modifying the compiler without affecting the language. 

Furthermore if you do not mind to extend the language (notice I said "extend" 
and not "modify") then you can do very nice things. This has been done AND 
implemented for Java. The extension of Java by "encapsulated multi-methods" 
(that's how we christened them) is described in [2]. This is obtained by simply
adding a modifier to Java's syntax. We also have a compiler under Solaris that 
compiles this Java extension. It is interesting to note that it is a
conservative 
extension of Java, which simply means that if you feed the extended compiler by
a 
standard Java program you will obtain the same code as with the standard
compiler
(well, not exactly, object structures will have an extra useless slot).


Let me end with some advertising. Both references should be much easier to read 
than the paper of mine cited in the previous messages. They can be retrieved at
http://www.dmi.ens.fr/~castagna/pub.html
If somebody would like to try to implement it in OCaml I'm ready to help him on
the 
design part (e.g. a student looking for a subject for master thesis ;-)

Cheers

---Beppe---

[1] J.Boyland and G. Castagna. Type-Safe Compilation of Covariant
Specialization: 
A Practical Case. In Proc. of ECOOP'96. Lecture Notes in Computer Science, 
1098:3-25, 1996.

[2] J. Boyland and G. Castagna. Parasitic methods: an implementation of 
multi-methods for Java. In Proc. of OOPSLA'97. SIGPLAN Notices 32(10):66-76. 
1997

P.S. We did not made the compiler public available. So there is no doc, etc.,
etc. ...