Re: [Caml-list] Width subtyping

Re: [Caml-list] Width subtyping

[Dario Teixeira]

Hi,

> The dual of sums is products.  Open (labelled) sums
> are "polymorphic variants".  Their duals are open
> (labelled) products are "rows" (which O'Caml already
> supports, through its objects).

Yes, as I mentioned, for some classes of this particular problem the object
system can be put to good use -- when there is a clear tree for inheritance,
for example.  Unfortunately that is always not the case; there are problems
where you would end up with a tangled web of multiple inheritances just for
the sake of avoiding duplicating methods.

Cheers,
Dario

Re: [Caml-list] Width subtyping

[Till Varoquaux]

There must be something that escapes me.... This seems to be an
example where ocaml objects really shine because of the structural
typing (i.e. an object is defined by the its structure):

type t1 = <a: int; b: int; c: int; >
type t2 = <a: int; b: int; c: int; d: int >
type t3 = <        b: int; c: int; d: int >

let v1 : t1 = object method a = 1; method b = 2; method c =3 end
let v2 : t2 = object method a = 1; method b = 2; method c =3 ; method d = 4 end
let v3 : t3 = object method b = 2; method c =3 ; method d = 4 end

let get_a x : int = x#a

let _ = get_a v1 (** ok*)
let _ = get_a v2 (** ok *)
let _ = get_a v3 (** rejected by the type checker*)

On Fri, May 29, 2009 at 11:45 AM, Dario Teixeira
<darioteixeira@yahoo.com> wrote:
>
> Hi,
>
>> The dual of sums is products.  Open (labelled) sums
>> are "polymorphic variants".  Their duals are open
>> (labelled) products are "rows" (which O'Caml already
>> supports, through its objects).
>
> Yes, as I mentioned, for some classes of this particular problem the object
> system can be put to good use -- when there is a clear tree for inheritance,
> for example.  Unfortunately that is always not the case; there are problems
> where you would end up with a tangled web of multiple inheritances just for
> the sake of avoiding duplicating methods.
>
> Cheers,
> Dario
>
>
>
>
>
> _______________________________________________
> 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
>

Re: [Caml-list] Width subtyping

[Peng Zang]

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


On Monday 01 June 2009 10:21:36 am David Allsopp wrote:
> Dario Teixeira wrote:
> > Thanks -- that is also an interesting solution.  I'm guessing it will
> > be faster, though it might consume more memory in cases where only one
> > field is actually used.  I'll have to try it side-by-side with the
> > object based solution to see how they compare in the real world with my
>
> So as I wouldn't immediately be told "the overhead is irrelevant", I ran a
> "quick" benchmark before my last post. I compared summing 7 million
> 3-int-field records and 7 million 3-int-field objects using names a, b, c.
> On my machine, averaged out and with enough RAM that neither paging nor the
> GC get in the way, objects were nearly 3 times slower. I then tried with
> 10-int-field records and objects - in this case, objects were just over 4
> times slower (read on). This was in bytecode - I didn't bother with native
> code.
>
> The overhead of an object is 2 words (one contains tracking information
> about the actual class of the object and the other is a unique identifier)
> + (I think) 1 extra word for every field (because each int is boxed in a
> 1-tuple so that its tag can be recorded). Importantly, accessing fields in
> a record is an O(1) operation but for objects it's O(log n) for the number
> of fields because a binary search is done to locate the field with the
> correct tag. ocamlopt may of course optimise this search by caching the
> absolute index of the field in a "recognised" object layout; I didn't look
> in the compiler. My test between 3 and 10 fields would suggest that this
> optimisation does not apply in bytecode.
>
>
> David

This also matches what I've seen.  It seems many optimizations are not 
performed in bytecode.  As a result, the performance characteristics of 
objects change dramatically when compiled to native code.  In my experience 
objects incur a 20% hit on runtime in native code.

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

iD8DBQFKJAoUfIRcEFL/JewRAjlOAJ98T4OTRDy9+TxhzZ6bVuzu7pFjHACdFreL
gFn1gN+whdEntNO2JcZguzQ=
=1FQS
-----END PGP SIGNATURE-----

RE: [Caml-list] Width subtyping

[David Allsopp]

Dario Teixeira wrote:
> Thanks -- that is also an interesting solution.  I'm guessing it will
> be faster, though it might consume more memory in cases where only one
> field is actually used.  I'll have to try it side-by-side with the
> object based solution to see how they compare in the real world with my
actual
> problem..

So as I wouldn't immediately be told "the overhead is irrelevant", I ran a
"quick" benchmark before my last post. I compared summing 7 million
3-int-field records and 7 million 3-int-field objects using names a, b, c.
On my machine, averaged out and with enough RAM that neither paging nor the
GC get in the way, objects were nearly 3 times slower. I then tried with
10-int-field records and objects - in this case, objects were just over 4
times slower (read on). This was in bytecode - I didn't bother with native
code.

<snip>
> 
> Which might turn out to be not that big a deal.  After all, the object
> based solution also adds some default overhead per object created,
> right?

The overhead of an object is 2 words (one contains tracking information
about the actual class of the object and the other is a unique identifier) +
(I think) 1 extra word for every field (because each int is boxed in a
1-tuple so that its tag can be recorded). Importantly, accessing fields in a
record is an O(1) operation but for objects it's O(log n) for the number of
fields because a binary search is done to locate the field with the correct
tag. ocamlopt may of course optimise this search by caching the absolute
index of the field in a "recognised" object layout; I didn't look in the
compiler. My test between 3 and 10 fields would suggest that this
optimisation does not apply in bytecode.


David

Re: [Caml-list] Width subtyping

[Dario Teixeira]

Hi,

> If you're willing to give up some of the syntactic
> niceties of records (and the ability to pattern-match) you
> can get what you want using an abstract type.

Thanks -- that is also an interesting solution.  I'm guessing it will
be faster, though it might consume more memory in cases where only one
field is actually used.  I'll have to try it side-by-side with the object
based solution to see how they compare in the real world with my actual
problem...


> Here, we've chosen to use a default value for fields
> that we don't fill in.  We could just as well have used
> options here.  The performance of the above will be roughly
> the same as the performance of a simple record.  Obviously,
> all of the different "subtypes" have the full
> record stored at a physical level.

Which might turn out to be not that big a deal.  After all, the object
based solution also adds some default overhead per object created, right?

Cheers,
Dario Teixeira

Re: [Caml-list] Width subtyping

[Yaron Minsky]

[-- Attachment #1: Type: text/plain, Size: 1987 bytes --]

On Sun, May 31, 2009 at 7:08 PM, Dario Teixeira <darioteixeira@yahoo.com>wrote:

>
> I also meant "heavier" in terms of efficiency.  And like David said, it
> does
> feel wrong to carry the performance penalty of the object system solely
> because
> I need the structural subtyping features.


If you're willing to give up some of the syntactic niceties of records (and
the ability to pattern-match) you can get what you want using an abstract
type.

module type S =
sig
   type 'a
t
   val create_t1 : a : int -> b : int -> c : int -> [ `a | `b | `c ]
t
   val create_t2 : a : int -> b : int -> c : int -> d :
int
     -> [ `a | `b | `c | `d ]
t
   val create_t3 : b : int -> c : int -> d : int -> [ `b | `c | `d ]
t


   val a : [> `a ] t ->
int
   val b : [> `b ] t ->
int
   val c : [> `c ] t ->
int
   val d : [> `d ] t ->
int
end



module M : S =
struct
  type u = { a: int; b: int; c :int; d: int
}
  type 'a t =
u
  let default = { a = 0; b = 0; c = 0; d = 0
}
  let create_t1 ~a ~b ~c = { default with a = a; b = b; c = c
}
  let create_t2 ~a ~b ~c ~d = { a = a; b=b; c=c; d=d;
}
  let create_t3 ~b ~c ~d =  { default with b=b; c=c; d=d
}


  let a t =
t.a
  let b t =
t.b
  let c t =
t.c
  let d t =
t.d
end



let f x = M.a x + M.b
x
let g () = f (M.create_t1 ~a:0 ~b:0 ~c:0) (* accepted by compiler
*)
let g () = f (M.create_t2 ~a:0 ~b:0 ~c:0 ~d:0) (* accepted by compiler
*)
let g () = f (M.create_t3 ~b:0 ~c:0 ~d:0) (* rejected by compiler *)

The compiler error you get on that last line is this:

Error: This expression has type [ `b | `c | `d ]
M.t
       but is here used with type [> `a | `b ]
M.t
       The first variant type does not allow tag(s) `a


Here, we've chosen to use a default value for fields that we don't fill in.
We could just as well have used options here.  The performance of the above
will be roughly the same as the performance of a simple record.  Obviously,
all of the different "subtypes" have the full record stored at a physical
level.

y

[-- Attachment #2: Type: text/html, Size: 7447 bytes --]

Re: [Caml-list] Width subtyping

[Jacques Garrigue]

From: Dave Benjamin <dave@ramenlabs.com>

> Heavier in terms of efficiency, or syntax? If you mean the latter, I 
> wonder if a camlp4 syntax extension might help ease the burden; perhaps 
> something like:
> 
>    #{x=5; y=6}
> 
> could be translated to:
> 
>    object method x = 5 method y = 6 end
> 
> and then you could benefit from a lightweight syntax and still get the 
> static type checking.

This is already possible with pa_oo, which you can get from the same
place as pa_polymap:

http://www.math.nagoya-u.ac.jp/~garrigue/code/ocaml.html

Also, concerning the typing of pa_polymap, the "weakness" is intended,
otherwise you wouldn't be able to add new fields to an existing value
(using the with notation).
If you just want to create values without allowing modifications, here
is a modified of pa_polymap.ml which gives them closed types. (It
still needs the original Polymap module.)

Concerning efficiency, since pa_polymap is based on the Map module,
you cannot expect it to be more efficient than the pa_oo based approach,
neither in terms of data size or runtime speed. It only probably wins
for generated code size, as classes are big.

Of course, both are much worse than real records. But whether it
matters or not depends much on what you use them for in your program.

        Jacques Garrigue

(*
   To compile:
     ocamlc -I +camlp4 -c -pp camlp4orf pa_polymap.ml
     ocamlc -c polymap.ml
   To use:
     ocaml dynlink.cma camlp4o.cma pa_polymap.cmo polymap.cmo
   or
     ocamlc -pp 'camlp4o -I . pa_polymap.cmo'
*)

open StdLabels
open Camlp4.PreCast
module Pcaml = Syntax

let next =
  let n = ref 0 in
  fun () -> incr n; string_of_int !n

let add _loc org (s,e) tv =
  <:expr< Polymap.add (Obj.magic `$s$) (Obj.magic ($e$ : $tv$))
            ($org$ : Polymap.t [> `$s$ of $tv$ ]) >>

let test_key_eq =
  let test strm =
    match Stream.npeek 2 strm with
      [(UIDENT _|LIDENT _), _; KEYWORD "=", _] -> ()
    | _ -> raise Stream.Failure
  in
  Gram.Entry.of_parser "test_key_eq" test

let upper_bound _loc e l =
  match l with
    [] -> e
  | s::l ->
     let typ = List.fold_left ~init:<:ctyp< `$s$ of _ >> l
       ~f:(fun t s -> <:ctyp< `$s$ of _ | $t$ >>)
     in <:expr< ($e$ : Polymap.t [< $typ$ ]) >>

EXTEND Pcaml.Gram
  GLOBAL: Pcaml.expr;
  Pcaml.expr: LEVEL "." [
    [ e = SELF; "."; "`"; s = Pcaml.a_ident ->
      let tv = <:ctyp< '$"pm_"^next()$ >> in
      <:expr<
        (Obj.magic
           (Polymap.find (Obj.magic `$s$) ($e$ : Polymap.t [> `$s$ of $tv$ ]))
        : $tv$)
      >> ]
  ];
  Pcaml.expr: LEVEL "simple" [
    [ "`"; "{"; "}" -> <:expr< Polymap.empty >>
    | "`"; "{"; test_key_eq; lel = lbl_expr_list; "}" ->
        let (e, tl) = lel <:expr< Polymap.empty >> in
        upper_bound _loc e tl
    | "`"; "{"; e = Pcaml.expr LEVEL "."; "with"; lel = lbl_expr_list;
      "}" -> fst (lel e) ]
  ];
  lbl_expr_list: [
    [ fields = LIST1 field SEP ";" ->
        let tl = List.map fields ~f:(fun _ -> <:ctyp< '$"pm_"^next()$ >>) in
        fun org ->
          (match fields with
            [s,e] -> add _loc org (s,e) (List.hd tl)
          | _ ->
            List.fold_left2 ~init:org fields tl ~f:(add _loc)),
          List.map fst fields ]
  ];
  field: [[ s = Pcaml.a_ident; "="; e = Pcaml.expr LEVEL "top"  -> (s,e) ]];
END;;

RE: [Caml-list] Width subtyping

[Dario Teixeira]

Hi,

> > Heavier in terms of efficiency, or syntax?
>
> My concern is the former. The extra two fields per "record" and the heavier
> runtime calls make them so systemically slower that (to me, at least) it
> just feels "wrong" to use objects just to achieve a little syntactic clarity
> and a small reduction in the amount of code written. Polymorphic variants
> (which use only slightly more memory than regular variant values) otherwise
> perform at the same speed as their normal counterparts.

I also meant "heavier" in terms of efficiency.  And like David said, it does
feel wrong to carry the performance penalty of the object system solely because
I need the structural subtyping features.  Ideally, what I should be using
is "record subtyping": something along the lines of the Polymap extension
(which I advise everyone to take a look at), but with compile-time checking.

However, my guess is that proper record subtyping cannot be tacked onto the
language by means of Camlp4, and it probably needs to be a builtin feature
(though I would gladly be proven wrong).  Which leads to the obvious question:
is there any theoretical reason why record subtyping is not available in Ocaml?
Or is the answer simply "just use the object system; it's not as heavy as you
think it is"?...

Cheers,
Dario Teixeira

RE: [Caml-list] Width subtyping

[David Allsopp]

> Dario Teixeira wrote:
> > You are right.  I was probably too fixated on the OOP way of doing this,
> > translating record fields into object fields and the functions acting on
> > records into object methods.  Your solution, where record fields become object
> > methods and external functions act on objects that match a certain structure,
> > does solve the inconveniences I mentioned before.  But objects are still
> > a somewhat heavier solution, right?
> 
> Heavier in terms of efficiency, or syntax?

My concern is the former. The extra two fields per "record" and the heavier runtime calls make them so systemically slower that (to me, at least) it just feels "wrong" to use objects just to achieve a little syntactic clarity and a small reduction in the amount of code written. Polymorphic variants (which use only slightly more memory than regular variant values) otherwise perform at the same speed as their normal counterparts.


David

Re: [Caml-list] Width subtyping

[Dave Benjamin]

Dario Teixeira wrote:
> Hi,
> 
>> There must be something that escapes me.... This seems to be an
>> example where ocaml objects really shine because of the structural
>> typing (i.e. an object is defined by the its structure):
> 
> You are right.  I was probably too fixated on the OOP way of doing this,
> translating record fields into object fields and the functions acting on
> records into object methods.  Your solution, where record fields become object
> methods and external functions act on objects that match a certain structure,
> does solve the inconveniences I mentioned before.  But objects are still
> a somewhat heavier solution, right?

Heavier in terms of efficiency, or syntax? If you mean the latter, I 
wonder if a camlp4 syntax extension might help ease the burden; perhaps 
something like:

   #{x=5; y=6}

could be translated to:

   object method x = 5 method y = 6 end

and then you could benefit from a lightweight syntax and still get the 
static type checking.

Dave

Re: [Caml-list] Width subtyping

[Dario Teixeira]

Hi,

> There must be something that escapes me.... This seems to be an
> example where ocaml objects really shine because of the structural
> typing (i.e. an object is defined by the its structure):

You are right.  I was probably too fixated on the OOP way of doing this,
translating record fields into object fields and the functions acting on
records into object methods.  Your solution, where record fields become object
methods and external functions act on objects that match a certain structure,
does solve the inconveniences I mentioned before.  But objects are still
a somewhat heavier solution, right?

In the meantime I also investigated Polymap, and it is close to being the
ideal solution.  It has one huge drawback, though: type inconsistencies
cannot be detected at compile-time, producing instead runtime exceptions.
The example below illustrates this; note that function printx should accept
both m1 and m2, but not m3.  However, the mistake in 'foobar' is not reported
until runtime:  (In fairness, there's probably no easy technical fix for this.)

let printx m = Printf.printf "X is %d and Y is %s\n" m.`x m.`y

let m1 = `{x=1; y="foo"}
let m2 = `{x=2; y="bar"; z=true}
let m3 = `{y="ola"; z=false}

let foobar =
        printx m1;
        printx m2;
        printx m3

Cheers,
Dario

Re: [Caml-list] Width subtyping

[Dario Teixeira]

Hi,

> I've very tired at the moment, but I think that Garrigue's
> polymap syntax extension does what you want:
> 
> http://www.math.nagoya-u.ac.jp/~garrigue/code/ocaml.html
> 
> If not, just ignore me!

I should have suspected this discussion would eventually lead
to something out of Jacques Garrigue's magic hat! :-)

But on a first glance, yes, it does look like it might be of interest.
I'll explore it further, thanks!

Cheers,
Dario

RE: [Caml-list] Width subtyping

[Dario Teixeira]

Hi,

> This way you're always dealing with the same product type,
> but the sum type tells you which fields are actually valid.
> Of course, it relies on there being an obvious sentinel
> value for unused fields (otherwise you just end up with 'a
> option everywhere) and I still don't think it's that neat as
> you can still match against fields which aren't valid but at
> least the type system prevents you from being handed an
> illegal value. The benefit is that you don't need special
> "get" functions (just a match on type t to extract the t'
> value from each constructor). I can't get my head around how
> private polymorphic variants work to see if they can refine
> this further...

This is indeed a reasonable solution for many classes of problems.
However, the need for a sentinel value for unused fields makes it
somewhat heavyweight for those record variants where just one field
is valid.  Moreover, this solution requires outside functions that
should only operate on T1 (for example) to "voluntarily" check by
pattern matching that the t they are getting is indeed a T1 (and
presumably raise failure otherwise).  The object-based solution can
at least automatically take care of this (though it has other problems).

Cheers,
Dario

Re: [Caml-list] Width subtyping

[Richard Jones]

On Fri, May 29, 2009 at 07:10:12AM -0700, Dario Teixeira wrote:
> type t1 = {a: int; b: int; c: int;        }
> type t2 = {a: int; b: int; c: int; d: int;}
> type t3 = {        b: int; c: int; d: int;}

I've very tired at the moment, but I think that Garrigue's
polymap syntax extension does what you want:

http://www.math.nagoya-u.ac.jp/~garrigue/code/ocaml.html

If not, just ignore me!

Rich.

-- 
Richard Jones
Red Hat

RE: [Caml-list] Width subtyping

[David Allsopp]

> Though it is probably been-there-done-that material for the veterans in
> this list, for the sake of the not-so-veterans I have to ask: how do you guys
> typically model width subtyping in Ocaml?

Definitely not a veteran, but might private types help a little?

> Consider for example three record types that share some of their fields:
> 
> type t1 = {a: int; b: int; c: int;        }
> type t2 = {a: int; b: int; c: int; d: int;}
> type t3 = {        b: int; c: int; d: int;}

Modelled as...

module M : sig
  type t' = {a: int; b: int; c: int; d: int}
  type t = private T1 of t' | T2 of t' | T3 of t'
  val makeT1 : int -> int -> int -> t
  val makeT2 : int -> int -> int -> int -> t
  val makeT3 : int -> int -> int -> t
end = struct
  type t' = {a: int; b: int; c: int; d: int}

  type t = T1 of t' | T2 of t' | T3 of t'

  let makeT1 a b c = T1 {a = a; b = b; c = c; d = 0}
  let makeT2 a b c d = T2 {a = a; b = b; c = c; d = d}
  let makeT3 b c d = T3 {a = 0; b = b; c = c; d = d}
end

This way you're always dealing with the same product type, but the sum type tells you which fields are actually valid. Of course, it relies on there being an obvious sentinel value for unused fields (otherwise you just end up with 'a option everywhere) and I still don't think it's that neat as you can still match against fields which aren't valid but at least the type system prevents you from being handed an illegal value. The benefit is that you don't need special "get" functions (just a match on type t to extract the t' value from each constructor). I can't get my head around how private polymorphic variants work to see if they can refine this further...


David

Re: [Caml-list] Width subtyping

[Jacques Carette]

Dario Teixeira wrote:
> In other words, polymorphic variants provide a very elegant solution for subtyping
> with sum types.  Is there some brilliant idea that could do the same for product types?
>   
The dual of sums is products.  Open (labelled) sums are "polymorphic 
variants".  Their duals are open (labelled) products are "rows" (which 
O'Caml already supports, through its objects).

See TAPL for a nice introduction to the type theory of labelled records 
with subtyping (i.e. rows).

Jacques

PS: note that O'Caml's products are positional while its sums are 
labelled, so the duality present in the theory isn't as clear there.  
The better dual for O'Caml's sums is really records.