[Caml-list] difficulties narrowing OO types

[Caml-list] difficulties narrowing OO types

[William Harold Newman]

OCaml seems generally reluctant to narrow OO types.

E.g., dynamically casting from a base class to a subclass is
unsupported (though I've seen the hack to work around this in Jason
Hickey's online introduction). And as far as I can tell, it's
impossible for a method on a subclass to guarantee that it returns a
narrower type than the method on the base class.

I'm still trying to understand the language, so it was only as I was
trying to express what I thought was an analogous limitation for
variant types I realized that there seems to be no such limitation
after all. I can define types like
  type tagged_reg = { tagged_n : int } ;;
  type untagged_reg = { untagged_n : int } ;;
  type reg = Tagged_Reg of tagged_reg | Untagged_Reg of untagged_reg ;;
and then define things like
  let rec tagged_regs regs = match regs with
  | [] -> []
  | Tagged_Reg(tr) :: rest -> tr :: tagged_regs rest
  | Untagged_Reg(_) :: rest -> tagged_regs rest ;;
But I still don't see how to do things like this with classes.

My immediate motivation for thinking about narrowing types is that I
have a class "sq" which lives on a grid where I know from global
constraints that all the other "sq" objects on the grid are of the
same class, and furthermore that this will be true of any subclasses.
I.e. if it's a pure "sq", all elements of its grid will be pure "sq"
also, and it it's a subclassed objects "subsq" all elements will be
"subsq", and so on for "subsubsq" and "subsubsubsq" and so forth. I'd
like to be able to define a "neighbors" method which returns a list of
"sq" when the object is exactly of class "sq", and returns a list of
"subsq" when the object is exactly of class "subsq", and so on. Or,
I'd be satisfied with a "map_on_neighbors" function which mapped onto
neighboring "sq" objects in the "sq" case, and neighboring "subsq"
objects in the "subsq" case, and so forth. An approximate analogy in
the register example above might be functions like "colliding_regs" or
"alternative_regs" which are meaningful both for tagged and untagged
registers, and return only values of the same type as their register
argument.

If there really are systematic obstacles to narrowing OO types in
OCaml, not just beginner confusion on my part, is there some deep
reason? Perhaps because it causes problems with type inference? At
first I thought it might be because it tends to be strongly correlated
with typecase operations which miss the point of OO, but that doesn't
explain why I can't narrow the return type of a subclass method.

-- 
William Harold Newman <william.newman@airmail.net>
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] difficulties narrowing OO types

[Jacques Garrigue]

From: William Harold Newman <william.newman@airmail.net>

> OCaml seems generally reluctant to narrow OO types.
OCaml is reluctant to do anything unsafe.

> E.g., dynamically casting from a base class to a subclass is
> unsupported (though I've seen the hack to work around this in Jason
> Hickey's online introduction).
No surprise, this is unsafe. Work arounds are available, but they may
all fail at runtime. The technical reason for not having it as a
construct in the language is that checking casts for parametric
classes is much harder than for classes without parameters.

> And as far as I can tell, it's
> impossible for a method on a subclass to guarantee that it returns a
> narrower type than the method on the base class.

That's actually a quite different problem. Having a method in a
subclass return a narrower type is type-safe, and is allowed by OCaml
subtyping rules. Unfortunately, OCaml inheritance rules does not allow
it.

[Snipped lots of goods reason why one would want to narrow methods in
subclasses]

> If there really are systematic obstacles to narrowing OO types in
> OCaml, not just beginner confusion on my part, is there some deep
> reason? Perhaps because it causes problems with type inference? At
> first I thought it might be because it tends to be strongly correlated
> with typecase operations which miss the point of OO, but that doesn't
> explain why I can't narrow the return type of a subclass method.

You pointed it: type inference. Inferring class types is already
pretty complicated, it would become nightmarish if method types can
change with inheritance. Type inference is based on unification, which
doesn't play well with subtyping.

Since the problem is with inheritance, and not with subtyping, there
are workarounds to define such classes. Basically the idea is to keep
the type of self as a parameter to the class.

class ['a] base_t ~pos ~friends =
  object
    method pos : int = pos
    method friends : 'a list = friends
  end

class base = [base] base_t

class ['a] extended_t ~pos ~friends ~name =
  object
    inherit ['a] base_t ~pos ~friends
    method name : string = name
end

class extended = [extended] extended_t

Here are the types:
class ['a] base_t :
  pos:int ->
  friends:'a list -> object method friends : 'a list method pos : int end
class base : pos:int -> friends:base list -> [base] base_t
class ['a] extended_t :
  pos:int ->
  friends:'a list ->
  name:string ->
  object method friends : 'a list method name : string method pos : int end
class extended :
  pos:int -> friends:extended list -> name:string -> [extended] extended_t

The point is that extended is actually a subtype of base:
# let b = new base ~pos:1 ~friends:[(e : extended :> base)];;
val b : base = <obj>

Note that this only works as long as base has no contravariant
method. If base_t contained an add_friend : 'a -> unit method, then
subtyping would break.


It might be possible to add method narrowing in the language with a
special syntax, but again parametric classes are hard to handle.

Cheers,

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] difficulties narrowing OO types

[Jacques Garrigue]

From: Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp>

> Since the problem is with inheritance, and not with subtyping, there
> are workarounds to define such classes. Basically the idea is to keep
> the type of self as a parameter to the class.

Actually, I realized after posting my previous message that it was a
bit far-fetched for simple cases. If you just want to be able to list
objects which have the type of the current class, then recursion on
the type of self is enough and simpler.

Here is the same example as before:

class base ~pos ~friends =
  object (_ : 'a)
    method pos : int = pos
    method friends : 'a list = friends
  end

class extended ~pos ~friends ~name =
  object
    inherit base ~pos ~friends
    method name : string = name
  end

Which give types:
class base :
  pos:int ->
  friends:('a list as 'b) ->
  object ('a) method friends : 'b method pos : int end
class extended :
  pos:int ->
  friends:('a list as 'b) ->
  name:string ->
  object ('a) method friends : 'b method name : string method pos : int end

And you can even coerce with semi-explicit coercions:
# let e = new extended ~pos:1 ~friends:[] ~name:"e";;
val e : extended = <obj>
# let b = new base ~pos:2 ~friends:[(e :> base)];;
val b : base = <obj>

Hope this helps.

Jacques Garrigue
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr