[Caml-list] Recursive classes are impossible?

[Caml-list] Recursive classes are impossible?

[Alessandro Baretta]

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

Alex

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

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

[Gerd Stolpmann]

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

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

[james woodyatt]

On Monday, June 24, 2002, at 02:34 PM, Gerd Stolpmann wrote:
>
> 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

Here's a more graphic explanation of why this is a bad idea:

	let t = new tree;;
	let b = new broccoli;;
	(b :> tree)#set_children [t];;

Here, the compiler-- quite sensibly-- errors on the coercion.

The "set_children" method of class tree takes a list of tree objects.  
The "set_children" method of class broccoli takes a list of broccoli 
objects.  If you were able to coerce a broccoli object into a tree 
object, you could then set its children to a list of non-broccoli tree 
objects-- which would violate the invariant for objects of the broccoli 
class.


--
j h woodyatt <jhw@wetware.com>

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

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

[Alessandro Baretta]

Gerd Stolpmann wrote:
> On 2002.06.24 15:59 Alessandro Baretta wrote:
> 
> 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. 

Why, yes! Of course, I should have thought about 
inheritance. It did not occur to me that maybe the "more or 
less impossible" should refer to inheritance. But of course, 
inheritance has some typing idiosyncrasies in "ordinary" C++ 
as well.

class Tree {
	Tree *left, *right
}

This is already enough to get into trouble, 'cause you need 
to get into the nasty business of type casting, which very 
soon gets out of control. Of course C++ works under the 
assumption that anything anything can be cast to anything 
else; so you actually have the expressive power to get 
"classy" trees and the like. What you don't get in C++ is 
the ability to define a type variable and impose the 
constraint that it be equal to the type of the current 
class. That is, you can't write

class Tree {
	this_class *left, *right
}

which is the meaning of (self:'self) in you declaration of 
class tree in O'Caml. Is this not the real problem?
****
Hmmm... apparently not. I tried with the following code, 
which seems rather intuitively inheritance savvy.

class tree =
	object (s)
	val mutable ch = ( [] : tree list )
	method get = ch
	method set x = ch <- x
end;;

class broccoli =
	object (s)
	inherit tree
	method color = "green"
end;;
	
let b = new broccoli
and t = new tree;;

But even this way "t # set b" and "b # set b" both fail. 
Now, without the covariance of 'self in the formal parameter 
of method set, I would expect the compiler to consider b to 
be truly a subtype of t, but this is not the case, although 
I am allowed to explicitly upcast b to tree type and write

t # set [(b :> tree)];;
b # set [(b :> tree)];;

And this is what I get:

# t # set [(b :> tree)];;
- : unit = ()
# b # set [(b :> tree)];;
- : unit = ()
# t # set [b];;
This expression has type
   broccoli = < color : string; get : tree list; set : tree 
list -> unit >
but is here used with type
   tree = < get : tree list; set : tree list -> unit >
Only the first object type has a method color
# b # set [b];;
This expression has type
   broccoli = < color : string; get : tree list; set : tree 
list -> unit >
but is here used with type
   tree = < get : tree list; set : tree list -> unit >
Only the first object type has a method color


Why is it that an explicit upcast is needed?

> 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

Thank you very much.

Alex

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

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

[John Prevost]

>>>>> "ab" == Alessandro Baretta <alex@baretta.com> writes:

    ab> Why is it that an explicit upcast is needed?

In this case, the explicit cast is needed to "remove" the color method
and make it into a real tree.

Something to note in this case is that you may not get what you
intended with the classes you defined.  You said:

class tree =
  object (s)
    val mutable ch = ( [] : tree list )
    method get = ch
    method set x = ch <- x
  end

class broccoli =
   object (s)
     inherit tree
     method color = "green"
   end

In this case, you'll notice that the children of broccoli are a tree
list, not a broccoli list.  So while broccoli can hold broccolis, you
can't call the color method on its children.  And, you can put normal
trees into broccolis as well.

As for the broader view, contravariance begins to show up whenever you
have a set method.  One way to get around it in the case of broccoli
and trees might be this:

class type ['a] read_tree =
  object ('s)
    method children : 's list
    method contents : 'a
  end

class type ['a] read_broccoli =
  object ('s)
    method children : 's list
    method contents : 'a
    method color : string
  end

class ['a] tree x =
  object (_ : 's)
    val mutable ch = ([] : 's list)
    val mutable co = (x : 'a)
    method children = ch
    method set_children ch' = ch <- ch'
    method contents = x
    method set_contents co' = co <- co'
  end

class ['a] broccoli x =
  object
    inherit ['a] tree x
    method color = "green"
  end


Now there are several ways to work with variance issues.  First, while
you can't cast a broccoli to a tree, you *can* cast it to a read_tree:


# let a = new broccoli 10;;
val a : int broccoli = <obj>
# (a :> 'a read_tree);;
- : int read_tree = <obj>


This is because a read_tree has no way to set the value, so we've
excluded the contravariant case.  The other good thing about this is
that we've removed two contravariant cases.  One case is the
set_children call, the other is the set_contents call.  This allows us
to go a step further--'a read_tree is covariant now in 'a, so we can
take a function that expects a "'c read_tree" and hand it a "'d
read_tree", assuming that 'c :> 'd.  (Or coerce it.)

Finally, there's a certain distinction between methods and functions
when it comes to these things.  When you define a function, you'll see
polymorphism work better.  For example:

let rec count_nodes x =
  List.fold_left (+) 1 (List.map count_nodes (x #children))

With this function, you can do:

# let a = new broccoli 10;;
val a : int broccoli = <obj>
# let b = new tree 10;;
val b : int tree = <obj>
# count_nodes a;;
- : int = 1
# count_nodes b;;
- : int = 1

You still need explicit coercions if you want to make a list
containing both broccolis and trees:

# List.map count_nodes [(a :> 'a read_tree); (b :> 'a read_tree)];;
- : int list = [1; 1]

but noticing this feature of row-polymorphism goes a long way towards
making good use of the object features of O'Caml.  O'Caml's more
powerful type discipline means we can step on our own feet with these
co- vs. contravariance issues, but it also means we can do more
powerful interesting things: since subtyping isn't bound to
inheritance, polymorphic functions can be very very powerful.

John.


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