Re: [Caml-list] Recursive classes are impossible?

[Gerd Stolpmann <info@gerd-stolpmann.de>]

On 2002.06.24 15:59 Alessandro Baretta wrote:
>  > Due to the typing system it is more or less impossible to
>  > derive recursive classes in O'Caml. To get around this, it
>  > is common practice to put the modifiable or extensible
>  > part of recursive objects into parallel objects.
> <http://www.ocaml-programming.de/packages/documentation/pxp/manual/x550.html#AEN582>
> 
> Hmmm... Now I am no object specialist, but this sounds a 
> little weird to me. Now, let's see, doesn't the following 
> code show that recursive classes are indeed possible in 
> O'Caml? Or have I completely misunderstood what is meant by 
> recursive object?
> 
> class ['a] broccoli =
> 	object (s)
> 	val mutable portion = None;
> 	method set (x:'a option) = portion <- x
> end;;
> 
> let broccolo = new broccoli in
> 	broccolo#set (Some new broccoli);;
> 
> let broccolo = new broccoli in
> 	broccolo#set (Some broccolo);;
> 
> Sorry for mentioning broccoli, but it seemed appropriate 
> given the recursive nature of their geometry.

No, this is not the problem. Try the following:

class tree =
object(self:'self)
  val mutable v = (None : int option)
  val mutable ch = ([] : 'self list)
  method get = v
  method set x = v <- x
  method children = ch
  method set_children x = ch <- x
end

This definition works at the first glance, but if you try to
inherit from this class and subtype this class at the same
time, you will run into problems.

class broccoli =
object
  inherit tree
  method color = "green"
end

# let t = new tree;;
val t : tree = <obj>
# let b = new broccoli;;
val b : broccoli = <obj>
# t # set_children [b];;
This expression has type
  broccoli =
    < children : broccoli list; color : string; get : int option;
      set : int option -> unit; set_children : broccoli list -> unit >
but is here used with type
  tree =
    < children : tree list; get : int option; set : int option -> unit;
      set_children : tree list -> unit >
Only the first object type has a method color
# t # set_children [ (b :> tree) ];;
This expression cannot be coerced to type
  tree =
    < children : tree list; get : int option; set : int option -> unit;
      set_children : tree list -> unit >;
it has type
  broccoli =
    < children : broccoli list; color : string; get : int option;
      set : int option -> unit; set_children : broccoli list -> unit >
but is here used with type
  < children : broccoli list; color : string; get : int option;
    set : int option -> unit; set_children : tree list -> unit >
Type
  broccoli =
    < children : broccoli list; color : string; get : int option;
      set : int option -> unit; set_children : broccoli list -> unit >
is not compatible with type
  tree =
    < children : tree list; get : int option; set : int option -> unit;
      set_children : tree list -> unit > 
Only the first object type has a method color

What's going on? broccoli is not a subtype of tree, although it "only"
adds a new method, which is normally no hindrance.

Why is broccoli not a subtype of tree? The method set_children does not
fulfill the contravariance rule. This rule is a general subtyping rule,
and here it would mean that for all methods m:

- if broccoli.m has the function type s -> t
- and if tree.m has the function type u -> v
- the type u must be a subtype of s, and t must be a subtype of v.

broccoli.set_children has the type broccoli list -> unit,
and tree.set_children has the type tree list -> unit, but
tree list is not a subtype of broccoli list because tree is
not a subtype of broccoli. This means: if you want to show that 
broccoli is a subtype of tree, you need the assumption that tree is a
subtype of broccoli - this works only if both types are identical.
And the cause for this strange result is that the argument of the
method set_children refers recursively to the class type.

That means: You cannot define classes with methods whose arguments
refer recursively to the class, and extend the class definitions later
by inheritance. This is the reason why PXP does not have a DOM-like
interface that can be extended by inheritance.

See the thread http://caml.inria.fr/archives/200111/msg00302.html for
more explanations of subtyping rules.

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners