[Caml-list] Ocaml: typing by name vs. typing by structure

[Caml-list] Ocaml: typing by name vs. typing by structure

[Matej Kosik]

Hello,

When I try to compile the following program:

   let f1 = function
     {re=a;im=b} ->
        print_float a;
        print_float b
    in
    f1 {re=10.0;im=20.0

I get an error message:

    File "tmp.ml", line 2, characters 2-13:
    Error: Unbound record field label re

I know how to "fix" the program to be compilable---I have to add

    type whatever = {re:float; im:float}

at the top.
Then type inference is able to figure out that "f1" has type "whatever -> unit".

Why did language designers chosen:
- typing by structure in case of tuples (tuples can be viewed as records with unlabled fields),
- typing by name in case of records.

Why wasn't typing by structure chosen both for tuples and for records?
If it were, then type of "f1" would be "{re=float;im=float}".

Best regards.
-- 
Matej Košík

Re: [Caml-list] Ocaml: typing by name vs. typing by structure

[Gabriel Scherer]

If record were structurally typed, there would be an ambiguity as to,
for example, what this function mean:

  let access_foo t = t.foo

What would the type of `access_foo` be ? { foo : 'a } -> 'a ? { foo :
'a; bar : 'b } -> 'a ?
Should `access_foo { foo = 1 }` be typable? And `access_foo { foo = 1;
bar = true }` ?

In this situation, you want record subtyping. This get more
complicated than the relatively simple OCaml records. In fact, OCaml
has structurally typed structures with named fields : objects

  # let access_foo t = t#foo;;
  val access_foo : < foo : 'a; .. > -> 'a = <fun>
  # access_foo (object method foo = 1 method bar = true end);;
  - : int = 1

Tuples don't have this issue as they don't have an universal accessor
function : there is no way to get the first element of a tuple
whatever its width is. Therefore, all tuples manipulation make the
structure concrete, and structural subtyping comes at no complexity
cost ... if you accept the absence of universal accessors. SML has
them (#1 #2 etc.) and I'm not sure how they handle this.

On Sun, Oct 16, 2011 at 8:51 PM, Matej Kosik <kosik@fiit.stuba.sk> wrote:
> Hello,
>
> When I try to compile the following program:
>
>   let f1 = function
>     {re=a;im=b} ->
>        print_float a;
>        print_float b
>    in
>    f1 {re=10.0;im=20.0
>
> I get an error message:
>
>    File "tmp.ml", line 2, characters 2-13:
>    Error: Unbound record field label re
>
> I know how to "fix" the program to be compilable---I have to add
>
>    type whatever = {re:float; im:float}
>
> at the top.
> Then type inference is able to figure out that "f1" has type "whatever -> unit".
>
> Why did language designers chosen:
> - typing by structure in case of tuples (tuples can be viewed as records with unlabled fields),
> - typing by name in case of records.
>
> Why wasn't typing by structure chosen both for tuples and for records?
> If it were, then type of "f1" would be "{re=float;im=float}".
>
> Best regards.
> --
> Matej Košík
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Ocaml: typing by name vs. typing by structure

[Matej Košík]

On 10/16/2011 09:24 PM, Gabriel Scherer wrote:
> If record were structurally typed, there would be an ambiguity as to,
> for example, what this function mean:
> 
>   let access_foo t = t.foo
> 
> What would the type of `access_foo` be ? { foo : 'a } -> 'a ? { foo :
> 'a; bar : 'b } -> 'a ?

{ foo : 'a } -> 'a

seems plasible

> Should `access_foo { foo = 1 }` be typable? And `access_foo { foo = 1;
> bar = true }` ?
> 
> In this situation, you want record subtyping. This get more
> complicated than the relatively simple OCaml records.

This may be too troublesome to support but I guess it is plausible language change and it would enable additional Ocaml terseness. Let me clarify.

At the moment, it is not possible to do this:

  type t = {l1:int} * {l2:int};;

It is a syntax error. We are forced to do it gradually:

  type t1 = { l1 : int; }
  type t2 = { l2 : int; }
  type t = t1 * t

This is somewhat cumbersome.

Similarly, you cannot do this

  type t = A of {l1:int}
         | B of {l2:float}
         | C of {l1:int; l2:float}

Only this works:

  type t1 = { l1 : int}
  type t2 = { l2 : float}
  type t3 = { l1 : int; l2: float}
  type t = A of t1
         | B of t2
         | C of t3

We were forced to introduce three superfluous type-names [t1;t2;t3].
How would you feel if you were forced to do that for every tuple-type?

Sometimes tuples are not ideal
(when they have lots of members)
Records are better in those cases because you can access elements by their label and when you construct records with lots of fields, the labels clarify which field has what meaning. But switching from tuples to records is not smooth. What could be gained in readability (labeled fields) is lost by cluttering the program by auxiliary record type definitions.

> In fact, OCaml
> has structurally typed structures with named fields : objects
> 
>   # let access_foo t = t#foo;;
>   val access_foo : < foo : 'a; .. > -> 'a = <fun>
>   # access_foo (object method foo = 1 method bar = true end);;
>   - : int = 1

Interesting.

> 
> Tuples don't have this issue as they don't have an universal accessor
> function : there is no way to get the first element of a tuple
> whatever its width is. Therefore, all tuples manipulation make the
> structure concrete, and structural subtyping comes at no complexity
> cost ... if you accept the absence of universal accessors. SML has
> them (#1 #2 etc.) and I'm not sure how they handle this.

-- 
Matej Košík

Re: [Caml-list] Ocaml: typing by name vs. typing by structure

[Gabriel Scherer]

> Similarly, you cannot do this
>  type t = A of {l1:int}
>         | B of {l2:float}
>         | C of {l1:int; l2:float}

You can do that with object types:

type t =
  | A of < l1 : int >
  | B of < l2 : float >
  | C of < l1 : int; l2 : float >

Similarly, polymorphic variants are structural counterparts of variant types.

  # if true then `Foo (object method l1 = 1 end) else `Bar (object
method l1 = 2 method l2 = 2. end);;
  - : [> `Bar of < l1 : int; l2 : float > | `Foo of < l1 : int > ] = `Foo <obj>

Those types are more complex to use that named variant and structures,
tend to generate hard-to-read error messages (unless you carefully
annotate your code to avoid having too many unknowns in the exact type
used), and are slightly less efficient at runtime. Flexibility comes
at a price.

Most Ocaml programmers actually favor plain, simple language
constructs. Objects and polymorphic variants are used when their
flexibility is clearly required by the application, which is actually
not very often. You can learn more about objects in the OCaml manual,
and about polymorphic variant in Jacques Garrigue's article "Code
reuse through polymorphic variants":
- http://caml.inria.fr/pub/docs/manual-ocaml/manual005.html
- http://www.math.nagoya-u.ac.jp/~garrigue/papers/fose2000.html

On Sun, Oct 16, 2011 at 10:24 PM, Matej Košík <kosik@fiit.stuba.sk> wrote:
> On 10/16/2011 09:24 PM, Gabriel Scherer wrote:
>> If record were structurally typed, there would be an ambiguity as to,
>> for example, what this function mean:
>>
>>   let access_foo t = t.foo
>>
>> What would the type of `access_foo` be ? { foo : 'a } -> 'a ? { foo :
>> 'a; bar : 'b } -> 'a ?
>
> { foo : 'a } -> 'a
>
> seems plasible
>
>> Should `access_foo { foo = 1 }` be typable? And `access_foo { foo = 1;
>> bar = true }` ?
>>
>> In this situation, you want record subtyping. This get more
>> complicated than the relatively simple OCaml records.
>
> This may be too troublesome to support but I guess it is plausible language change and it would enable additional Ocaml terseness. Let me clarify.
>
> At the moment, it is not possible to do this:
>
>  type t = {l1:int} * {l2:int};;
>
> It is a syntax error. We are forced to do it gradually:
>
>  type t1 = { l1 : int; }
>  type t2 = { l2 : int; }
>  type t = t1 * t
>
> This is somewhat cumbersome.
>
> Similarly, you cannot do this
>
>  type t = A of {l1:int}
>         | B of {l2:float}
>         | C of {l1:int; l2:float}
>
> Only this works:
>
>  type t1 = { l1 : int}
>  type t2 = { l2 : float}
>  type t3 = { l1 : int; l2: float}
>  type t = A of t1
>         | B of t2
>         | C of t3
>
> We were forced to introduce three superfluous type-names [t1;t2;t3].
> How would you feel if you were forced to do that for every tuple-type?
>
> Sometimes tuples are not ideal
> (when they have lots of members)
> Records are better in those cases because you can access elements by their label and when you construct records with lots of fields, the labels clarify which field has what meaning. But switching from tuples to records is not smooth. What could be gained in readability (labeled fields) is lost by cluttering the program by auxiliary record type definitions.
>
>> In fact, OCaml
>> has structurally typed structures with named fields : objects
>>
>>   # let access_foo t = t#foo;;
>>   val access_foo : < foo : 'a; .. > -> 'a = <fun>
>>   # access_foo (object method foo = 1 method bar = true end);;
>>   - : int = 1
>
> Interesting.
>
>>
>> Tuples don't have this issue as they don't have an universal accessor
>> function : there is no way to get the first element of a tuple
>> whatever its width is. Therefore, all tuples manipulation make the
>> structure concrete, and structural subtyping comes at no complexity
>> cost ... if you accept the absence of universal accessors. SML has
>> them (#1 #2 etc.) and I'm not sure how they handle this.
>
> --
> Matej Košík
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Ocaml: typing by name vs. typing by structure

[AUGER Cedric]

Le Sun, 16 Oct 2011 22:24:06 +0200,
Matej Košík <kosik@fiit.stuba.sk> a écrit :

> On 10/16/2011 09:24 PM, Gabriel Scherer wrote:
> > If record were structurally typed, there would be an ambiguity as
> > to, for example, what this function mean:
> > 
> >   let access_foo t = t.foo
> > 
> > What would the type of `access_foo` be ? { foo : 'a } -> 'a ?
> > { foo : 'a; bar : 'b } -> 'a ?
> 
> { foo : 'a } -> 'a
> 
> seems plasible
> 
> > Should `access_foo { foo = 1 }` be typable? And `access_foo { foo =
> > 1; bar = true }` ?
> > 
> > In this situation, you want record subtyping. This get more
> > complicated than the relatively simple OCaml records.
> 

So, now, how would you type:

let f x = x.bar + x.foo

let g x = x.bar + x.foobar

?

-> typing error for g, since "x is of type {bar:int; foo:int} while it
                              expected to be of type {bar:int;
                                                      foobar:int}
-> parse all the file to find out that the whished type is:
   "{foo:int; bar:int; foobar:int}"
   and thus leading to:
   1. modularity break, since fields could be defined/used out of the
      file
   2. extra care when using fields to avoid doing stuff like:

      let f x = x.bar + x.foo
      let g x = x.bsr + x.foobar

      where bsr is a typo, leading to disjoint types/extra field
      making data inconstistent.
-> other stuff

For me, only the first is acceptable (or maybe otherstuff?),
and so you need to declare the type somewhere (and you lost your
ability to hide type definitions) or ensure that the
first function uses all its arguments.

Furthermore, it is always wishable for someone reading your code to
have some place where they can find ALL fields, to know their names,
or understand what it represents.

> This may be too troublesome to support but I guess it is plausible
> language change and it would enable additional Ocaml terseness. Let
> me clarify.
> 
> At the moment, it is not possible to do this:
> 
>   type t = {l1:int} * {l2:int};;
> 
> It is a syntax error. We are forced to do it gradually:
> 
>   type t1 = { l1 : int; }
>   type t2 = { l2 : int; }
>   type t = t1 * t
> 
> This is somewhat cumbersome.
> 
> Similarly, you cannot do this
> 
>   type t = A of {l1:int}
>          | B of {l2:float}
>          | C of {l1:int; l2:float}
> 
> Only this works:
> 
>   type t1 = { l1 : int}
>   type t2 = { l2 : float}
>   type t3 = { l1 : int; l2: float}
>   type t = A of t1
>          | B of t2
>          | C of t3
> 

In fact I guess it doesn't work due to "field collision":
you cannot use the same field name for different records.

Note that your first example is not pertinent to me, since I see no
point in naming structures which have only one field, so I would prefer

type t = {l1:int;l2:int}
or
type t = int * int

for the sum types, that means, you may have difficulties to do:

let f x = match x with
 | A x1 -> g x1
 | B x2 -> h x2
 | C x3 -> i x3

since g, h and i won't have type, as x1, x2 and x3 won't have one
either.


> We were forced to introduce three superfluous type-names [t1;t2;t3].
> How would you feel if you were forced to do that for every tuple-type?
> 
> Sometimes tuples are not ideal
> (when they have lots of members)

I would rather say
 "when they have lots of members sharing the same type"

> Records are better in those cases because you can access elements by
> their label and when you construct records with lots of fields, the
> labels clarify which field has what meaning. But switching from
> tuples to records is not smooth. What could be gained in readability
> (labeled fields) is lost by cluttering the program by auxiliary
> record type definitions.
> 
> > In fact, OCaml
> > has structurally typed structures with named fields : objects
> > 
> >   # let access_foo t = t#foo;;
> >   val access_foo : < foo : 'a; .. > -> 'a = <fun>
> >   # access_foo (object method foo = 1 method bar = true end);;
> >   - : int = 1
> 
> Interesting.
> 
> > 
> > Tuples don't have this issue as they don't have an universal
> > accessor function : there is no way to get the first element of a
> > tuple whatever its width is. Therefore, all tuples manipulation
> > make the structure concrete, and structural subtyping comes at no
> > complexity cost ... if you accept the absence of universal
> > accessors. SML has them (#1 #2 etc.) and I'm not sure how they
> > handle this.
>