[Caml-list] Bug? Constraints get ignored in methods

[Goswin von Brederlow]

Hi,

I want to keep a linked list of structures that have a common subset
of functionality. I thought this would be a good use of ocaml objects.
A base class with the common subset of functionality and methods to
link them. And then derived classes for the specific types. Most
simplified it looks like this:

# class type base_type = object val mutable next : base_type option method set_next : base_type option -> unit end;;
class type base_type =
object
val mutable next : base_type option
method set_next : base_type option -> unit
end

# class base : base_type = object val mutable next = None method set_next n = next <- n end;;
class base : base_type

# class foo = object inherit base method foo = () end;;
class foo :
object
val mutable next : base_type option
method foo : unit
method set_next : base_type option -> unit
end

# let a = new base in
let b = new foo in
a#set_next (Some (b :> base_type));;
- : unit = ()

# let a = new base in
let b = new foo in
a#set_next (Some b);;
^
Error: This expression has type foo but is here used with type base_type
The second object type has no method foo

This last error isn't nice. I don't want to have to cast the objects
all the time. So I thought there must be a better way using
polymorphic methods with a constraint. But here is where everything
breaks down. First lets look at just the set_next method:

# class type virtual vbase_type = object method virtual set_next : 'a. 'a option -> unit constraint 'a = #vbase_type end;;
class type virtual vbase_type =
object method virtual set_next : 'a option -> unit end

# class virtual vbase : vbase_type = object method virtual set_next : 'a. 'a option -> unit constraint 'a = #vbase_type end;;
class virtual vbase : vbase_type

# class base = object inherit vbase method set_next _ = () end;;
class base : object method set_next : 'a option -> unit end

# let b = new base;;
val b : base = <obj>

# b#set_next (Some 1);;
- : unit = ()

Huh? That should not work. 1 is not a superset of #vbase_type. The
constraint gets completly ignored by ocaml. Adding back the next gives
further problems:

# class type virtual vbase_type = object val mutable next : #vbase_type option method virtual set_next : 'a. 'a option -> unit constraint 'a = #vbase_type end;;
class type virtual vbase_type =
object
val mutable next : #vbase_type option
method virtual set_next : 'a option -> unit
end

# class virtual vbase : vbase_type = object val mutable next = None method virtual set_next : 'a. 'a option -> unit constraint 'a = #vbase_type end;;
class virtual vbase : vbase_type

# class base = object inherit vbase
method set_next n = next <- (n :> vbase_type option) end;;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This method has type #vbase_type option -> unit
which is less general than 'a. 'a option -> unit

Again I blame ocaml for dropping the constraint. Given the constraint
the type would be correct.

So how do I have to specify the set_next method that any superset of
#base_type will be accepted as argument? Or is that a bug in ocaml and
my syntax is perfectly fine?

MfG
Goswin

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[Martin Jambon]

Goswin von Brederlow wrote:
> Hi,
>
> I want to keep a linked list of structures that have a common subset
> of functionality. I thought this would be a good use of ocaml objects.

It is not a good use of objects. You'll notice this pretty soon as you'll run
into a variety of problems:

- polymorphism
- initialization
- verbosity
- performance

All of these issues are inexistent if you use records instead of objects for
the list structure (or just a classic list).

You can still use objects as elements of the list, but the elements would have
to share the base type, as you know.

(continued below)

I have no idea. It looks way too complicated.
Use a classic list:

class base = ...
class derived = ... (* inherits base *)

type obj = Base of base | Derived of derived

let obj_list = [ Base (new base); Derived (new derived); ... ]

let iter_base f l =
List.iter (function Base x -> f x | Derived x -> f (x :> base)) l

let iter_derived f l =
List.iter (function Derived x -> f x | Base _ -> ()) l

..

Martin

--
http://mjambon.com/

[Martin Jambon]

Martin Jambon wrote:
> Use a classic list:
>
>
> class base = ...
> class derived = ... (* inherits base *)
>
> type obj = Base of base | Derived of derived
>
> let obj_list = [ Base (new base); Derived (new derived); ... ]
>
> let iter_base f l =
> List.iter (function Base x -> f x | Derived x -> f (x :> base)) l
>
> let iter_derived f l =
> List.iter (function Derived x -> f x | Base _ -> ()) l
>

> ...

Or simply one list per type, each list containing all the elements compatible
with the type.

I would stay away from any solution that requires special methods in order to
solve the polymorphism/heterogeneity problem. Keep the modifications non-invasive.

Cheers,

[Goswin von Brederlow]

Martin Jambon <martin...@ens-lyon.org> writes:

> Goswin von Brederlow wrote:
>> Hi,
>>
>> I want to keep a linked list of structures that have a common subset
>> of functionality. I thought this would be a good use of ocaml objects.
>
> It is not a good use of objects. You'll notice this pretty soon as you'll run
> into a variety of problems:
>
> - polymorphism

Works fine without constraint.

> - initialization

Yep, already run into that one. I basically need 2 constructors. But I
solved that.

> - verbosity

???

> - performance

The disk is the slow part. :)

> All of these issues are inexistent if you use records instead of objects for
> the list structure (or just a classic list).
>
> You can still use objects as elements of the list, but the elements would have
> to share the base type, as you know.

You can not put things of different type into a list. So the elements
of the list must be unified to a common type. Since I need virtual
functions that means either a record of closures bound to a reference
of the actual data (ugly) or objects. So let it be objects.

Now with objects as elements of a normal list the problem remains. I
need to coerce them to the base type before calling the function(s)
handling the base type. And in the real use case there is not a simple
list but a more complicated structure (links between objects of state
clean, dirty, pending read, pending write, ...) so this occurs on more
than one place.

That would make this module depend on all possible types. And the
different types depend on this module as they have to alter the
location in the list to implement a move-to-front caching algorithm.
That would cause all my types and the list handling to be in one huge
ml file. No way.

Anyway, it currently looks more like this:

class base = ...
class ['a] data = ...

type t1 = M1.t data
type t2 = M2.t data
type t3 = M3.t data
type t3a = M3.A.t data
type t3b = M3.B.t data
..

where t3a/t3b are derived from t3.

> let obj_list = [ Base (new base); Derived (new derived); ... ]
>
> let iter_base f l =
> List.iter (function Base x -> f x | Derived x -> f (x :> base)) l
>
> let iter_derived f l =
> List.iter (function Derived x -> f x | Base _ -> ()) l

Now imagine that with 100 types. It really doesn't scale well. Before
I do that I will use (x :> base) in all places calling set_next like
functions.

MfG
Goswin

[Goswin von Brederlow]

Hi,

small add on to my last mail.

Think of it as having a set of work queues: clean, dirty, reading,
writing, write_prepare. The objects need to be able to quickly jump
from one queue to the back of another when the objects internal state
changes. And is not only the objects at the head of the queue that
change states. Can be pretty random what object changes.

If I put the prev/next links into the objects themself they can easily
detach themself from a queue and insert themself into another.

If I put the objects into other generic queue structures then I have to
find the position in the old queue to remove an object and that would
be slow.

If you can think of a solution that would allow

type 'a data = { next : 'b data option; data : 'a }

without having to know possibly types of 'b then I could use functors.

This would have to work:

let s = { next = None; data = "string" }
let i = { next = Some s; data = 23 }

MfG
Goswin

PS: and I don't mean using obj.magic. :)

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

Here's an example of how constraints are specified for polymorphic methods.
In this example I define a list type which can compare to anything that is
foldable.

class type ['a] foldable = object
method foldl : 'z. ('z -> 'a -> 'z) -> 'z -> 'z
end

class type ['a] mylist = object
inherit ['a] foldable
method compare : 'z. ('a #foldable as 'z) -> int
end

Direct application to your example would not work:

# class virtual base = object
method virtual setnext : 'a. (#base as 'a) option -> unit
end
Error: This type scheme cannot quantify 'a : it escapes this scope.
#

OCaml does not allow the recursive reference when the method is polymorphic.
One option is to just deal with coercions or a function that does it for you:

class virtual base = object
method virtual setnext : base option -> unit
end

let callsetnext (obj:#base) (n:#base option) =
obj#setnext (n :> base option)

Another option is to factor out the basic operations you need like the in list
example. I didn't make the list compare method work with other lists, I made
it more general to work with anything that is foldable. This avoids the
recursive reference because foldable is defined ahead of time.

Cheers,

Peng

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFJ0sJWfIRcEFL/JewRAr9iAKDXaZNlIZDlCdTaxWrIy7+5nObIZgCeIJ2d
qcvcX2pc/F899JuMgRa3S4A=
=lNOb
-----END PGP SIGNATURE-----

[Goswin von Brederlow]

Peng Zang <peng...@gmail.com> writes:

That is the part I wanted to clean up / simplify. Doesn't look nice if
some methods are called with # and others need the wrapper function.

> Another option is to factor out the basic operations you need like the in list
> example. I didn't make the list compare method work with other lists, I made
> it more general to work with anything that is foldable. This avoids the
> recursive reference because foldable is defined ahead of time.

That was what I did except with virtual methods where the implementation is
type specific.

> Cheers,
>
> Peng

So something like this:

class type linked = object val mutable next : #linked option end

class type base_type = object

inherit linked
method set_next : 'a. (#linked as 'a) option -> unit
end

That could actually work. I hope. Thanks.

[Martin Jambon]

Goswin von Brederlow wrote:
> Hi,
>
> small add on to my last mail.
>
> Think of it as having a set of work queues: clean, dirty, reading,
> writing, write_prepare. The objects need to be able to quickly jump
> from one queue to the back of another when the objects internal state
> changes. And is not only the objects at the head of the queue that
> change states. Can be pretty random what object changes.
>
> If I put the prev/next links into the objects themself they can easily
> detach themself from a queue and insert themself into another.
>
> If I put the objects into other generic queue structures then I have to
> find the position in the old queue to remove an object and that would
> be slow.
>
>
> If you can think of a solution that would allow
>
> type 'a data = { next : 'b data option; data : 'a }
>
> without having to know possibly types of 'b then I could use functors.
>
> This would have to work:
>
> let s = { next = None; data = "string" }
> let i = { next = Some s; data = 23 }

Would the following work for you:

type 'a linked = {
data : 'a;
mutable next : < > linked option
}
(* constraint 'a = < .. > *)

let create data next = {
data = data;
next = (next :> < > linked option)
}

let set_next x y =
x.next <- (y :> < > linked option)

class s =
object
method s = "abc"
end

class i =
object
method i = 123
end

let s = create (new s) None
let i = create (new i) (Some s)

val create : 'a -> < .. > linked option -> 'a linked = <fun>
val set_next : 'a linked -> < .. > linked option -> unit = <fun>
class s : object method s : string end
class i : object method i : int end
val s : s linked = {data = <obj>; next = None}
val i : i linked = {data = <obj>; next = Some {data = <obj>; next = None}}

--
http://mjambon.com/

[Goswin von Brederlow]

Martin Jambon <martin...@ens-lyon.org> writes:

> Would the following work for you:

No. Not just like this.

> type 'a linked = {
> data : 'a;
> mutable next : < > linked option
> }
> (* constraint 'a = < .. > *)
>
> let create data next = {
> data = data;
> next = (next :> < > linked option)
> }
>
> let set_next x y =
> x.next <- (y :> < > linked option)
>
>
> class s =
> object
> method s = "abc"
> end
>
> class i =
> object
> method i = 123
> end

class s and i have no access to the linked type. You could not remove
a class s or i from the linked structure in O(1) from within class s
or i. So linked would have to handle any function that might require
altering the linked structure and pass parts of it to its data. But
data is an unknown type so no method of it can be called.

I would first need a class type containing the common
functionality. Then 'a needs to be constraint to a superset of that
class and next has to be an linked option of that class.

Only then can the linked type call methods of its data.

Your suggestion has one benefit though. By using a record + normal
functions instead of a class one avoids a recursively constraint
method, which ocaml doesn't like.

MfG
Goswin

----------------------------------------------------------------------
PS: below is a completly object free solution. It comes at the cost of
requireing Obj.magic though. But its evilness is contained in M alone
and can't escape. Not sure yet what way I will go.

module M : sig
type 'a fn = { to_string : 'a -> string; alter : 'a -> 'a }
type 'a base
val make : 'a -> 'a fn -> 'a base
val to_string : 'a base -> string
val alter : 'a base -> unit
val iter : ('a base -> unit) -> unit
end = struct
type 'a fn = { to_string : 'a -> string; alter : 'a -> 'a }
type 'a base = { mutable next : unit base; mutable prev : unit base; mutable data : 'a; fn : 'a fn }
let unit_fn = { to_string = (fun () -> ""); alter = (fun () -> ()) }
let rec head = { next = head; prev = head; data = (); fn = unit_fn }
let make data fn =
let e = { next = head; prev = head.prev; data = data; fn = fn }
in
head.prev.next <- Obj.magic e;
head.prev <- Obj.magic e;
e
let to_string x = x.fn.to_string x.data
let alter x = x.data <- x.fn.alter x.data
let iter (fn : 'a base -> unit) =
let fn : unit base -> unit = Obj.magic fn in
let rec loop = function
x when x == head -> ()
| x -> fn x; loop x.next
in
loop head.next
end

let string_fn = { M.to_string = (fun s -> s); M.alter = (fun s -> s ^ "+") }
let int_fn = { M.to_string = (fun i -> Printf.sprintf "%d" i); M.alter = (fun i -> i +1) }
let s = M.make "s" string_fn
let i = M.make 1 int_fn
let _ = M.iter (fun x -> Printf.printf "%s\n" (M.to_string x))
let _ = M.iter M.alter
let _ = M.iter (fun x -> Printf.printf "%s\n" (M.to_string x))

=>

s
1

s+
2

[Martin Jambon]

Goswin von Brederlow wrote:
> Martin Jambon <martin...@ens-lyon.org> writes:
>
>> Would the following work for you:
>
> No. Not just like this.
>
>> type 'a linked = {
>> data : 'a;
>> mutable next : < > linked option
>> }
>> (* constraint 'a = < .. > *)
>>
>> let create data next = {
>> data = data;
>> next = (next :> < > linked option)
>> }
>>
>> let set_next x y =
>> x.next <- (y :> < > linked option)
>>
>>
>> class s =
>> object
>> method s = "abc"
>> end
>>
>> class i =
>> object
>> method i = 123
>> end
>
> class s and i have no access to the linked type.

Yes, that's exactly what I'm trying to achieve.
They are contained in cells of the list.
You need to handle cells if you want to change the linkage.

> You could not remove
> a class s or i from the linked structure in O(1) from within class s
> or i. So linked would have to handle any function that might require
> altering the linked structure and pass parts of it to its data. But
> data is an unknown type so no method of it can be called.

< > is your base class. Replace it by whatever you like.

Martin

--
http://mjambon.com/

[Jacques GARRIGUE]

From: Goswin von Brederlow <goswi...@web.de>

> I want to keep a linked list of structures that have a common subset
> of functionality. I thought this would be a good use of ocaml objects.
> A base class with the common subset of functionality and methods to
> link them. And then derived classes for the specific types. Most
> simplified it looks like this:
>
> # class type base_type = object val mutable next : base_type option method set_next : base_type option -> unit end;;

[...]

> # class foo = object inherit base method foo = () end;;

[...]

> # let a = new base in
> let b = new foo in
> a#set_next (Some (b :> base_type));;
> - : unit = ()
>

> I don't want to have to cast the objects
> all the time. So I thought there must be a better way using
> polymorphic methods with a constraint. But here is where everything
> breaks down. First lets look at just the set_next method:

>From your other posts I gather that your objects have a uniform
interface once they are in the list, and a specific interface just after
creating them. Hopefully you never need to recover the specific
interface from an object in a list (if that were the case, then I
strongly suggest using normal sum types...)

You don't want to write the coercions. That's natural. I see two ways
out. One is to realize that a method is just a weaker function, so
just write a function doing the coercion:

let set_next (x : #base_type) y =
x#set_next (Some (y :> base_type))

You might not like using a function, but you just have to realize that
methods are kind of second class in ocaml...

If you really want to stick to methods only (because of library
design, for instance), then a clever trick is to use a coercion
methods:

class virtual base_type =
object (self)
val mutable virtual next : base_type option
method virtual set_next_base : base_type option -> unit
method as_base = (self :> base_type)
method set_next : 'a. <as_base : base_type; ..> as 'a -> unit =
fun x -> self#set_next_base x#as_base
end

This may seem verbose here, but self-coercion methods are a good idea
anyway.

Hope this helps,

Jacques Garrigue

[Goswin von Brederlow]

Jacques GARRIGUE <garr...@math.nagoya-u.ac.jp> writes:

> From: Goswin von Brederlow <goswi...@web.de>
>
>> I want to keep a linked list of structures that have a common subset
>> of functionality. I thought this would be a good use of ocaml objects.
>> A base class with the common subset of functionality and methods to
>> link them. And then derived classes for the specific types. Most
>> simplified it looks like this:
>>
>> # class type base_type = object val mutable next : base_type option method set_next : base_type option -> unit end;;
> [...]
>> # class foo = object inherit base method foo = () end;;
> [...]
>> # let a = new base in
>> let b = new foo in
>> a#set_next (Some (b :> base_type));;
>> - : unit = ()
>>
>> I don't want to have to cast the objects
>> all the time. So I thought there must be a better way using
>> polymorphic methods with a constraint. But here is where everything
>> breaks down. First lets look at just the set_next method:
>
>>From your other posts I gather that your objects have a uniform
> interface once they are in the list, and a specific interface just after
> creating them. Hopefully you never need to recover the specific
> interface from an object in a list (if that were the case, then I
> strongly suggest using normal sum types...)

There will be more than one way to get an object. One is through the
list and that only uses the common methods. The other is through a
tree where the specific type is known at compile time. That is why I
need the list internal to the objects. Because some method will walk
through the tree and obsolete a node. That node then needs to be
removed from the list as well as from the tree.

> You don't want to write the coercions. That's natural. I see two ways
> out. One is to realize that a method is just a weaker function, so
> just write a function doing the coercion:
>
> let set_next (x : #base_type) y =
> x#set_next (Some (y :> base_type))
>
> You might not like using a function, but you just have to realize that
> methods are kind of second class in ocaml...
>
> If you really want to stick to methods only (because of library
> design, for instance), then a clever trick is to use a coercion
> methods:
>
> class virtual base_type =
> object (self)
> val mutable virtual next : base_type option

Why is next virtual here? Doesn't that require that anyone inheriting
base_type has to define their own version of next? Seems like needless
duplication.

> method virtual set_next_base : base_type option -> unit
> method as_base = (self :> base_type)
> method set_next : 'a. <as_base : base_type; ..> as 'a -> unit =
> fun x -> self#set_next_base x#as_base
> end
>
> This may seem verbose here, but self-coercion methods are a good idea
> anyway.
>
> Hope this helps,
>
> Jacques Garrigue

This helps a lot. Nice little trick to go through an immediate object
type.

MfG
Goswin

[Jacques Garrigue]

From: Goswin von Brederlow <goswi...@web.de>

> > If you really want to stick to methods only (because of library
> > design, for instance), then a clever trick is to use a coercion
> > methods:
> >
> > class virtual base_type =
> > object (self)
> > val mutable virtual next : base_type option
>
> Why is next virtual here? Doesn't that require that anyone inheriting
> base_type has to define their own version of next? Seems like needless
> duplication.

No real reason. Just that you class type contained such field, so I
pasted it it the least effecting way. But since no method inside
base_type accesses it, I agree that it seems better not to put it
there.

> > method virtual set_next_base : base_type option -> unit
> > method as_base = (self :> base_type)
> > method set_next : 'a. <as_base : base_type; ..> as 'a -> unit =
> > fun x -> self#set_next_base x#as_base
> > end

A small typo in the above. Like in the function example it should be

fun x -> self#set_next_base (Some x#as_base)

> This helps a lot. Nice little trick to go through an immediate object
> type.

Actually, the self coercion and the use of a non-abbreviated object
type are independent, but in general it is too heavy to use the second
without the first.

Jacques Garrigue