Label Names Space - philosophy or implementation?

Label Names Space - philosophy or implementation?

[John Gerard Malecki]

A co-worker has (vehemently) pointed out to me that record label names
cannot be shared.  For example, the following fails

	type foo = { name : string; x : int }
	let    a = { name = "foo";  x = 1 }

	type bar = { name : string; y : float }
	let    b = { name = "bar";  y = 9. }

	let   a' = { name = "foo";  x = 2 }

With an error message on the last line that "The label x belongs to
the type foo but is here mixed with labels of type bar".  This annoys
my co-worker to no end.  He would like many of his records to have a
field with a standardized label.  This makes it easier for him to
write printers for his data-structure.  Does anyone have a
recommendation to make to him?

Until this morning I would have guessed that the type of a record was
not resolved until all of the labels were examined.  As I re-read the
caml-light and ocaml manuals I see that this is not true.

Are there good reasons for this "restriction"?  I can see how this
this might be considered a good software practice.  Maybe, due to
pattern matching, it is not possible to have shared labels.

Any comments?

Re: Label Names Space - philosophy or implementation?

[Pierre Weis]

> A co-worker has (vehemently) pointed out to me that record label names
> cannot be shared.  For example, the following fails
> 	type foo = { name : string; x : int }
> 	let    a = { name = "foo";  x = 1 }
> 
> 	type bar = { name : string; y : float }
> 	let    b = { name = "bar";  y = 9. }
> 
> 	let   a' = { name = "foo";  x = 2 }
> With an error message on the last line that "The label x belongs to
> the type foo but is here mixed with labels of type bar".  This annoys
> my co-worker to no end.  He would like many of his records to have a
> field with a standardized label.  This makes it easier for him to
> write printers for his data-structure.  Does anyone have a
> recommendation to make to him?

This feature is used for sake of simplicity in the type-checking process.
We used to have label overloading in records, but it was a bit
complex to implement, since you can guess no more the type of a label
from its name. In the worst case (polymorphic labels), the
type-checking of labels is exponential (I mean, noticeably exponential
in practice, instead of our good old apparently quasi-linear regular
algorithm). Furthermore, people do not use it that much.
Its a common habit to prefix the labels with the name of the type:
something like:

 	type foo = { foo_name : string; foo_x : int }
 	type bar = { bar_name : string; bar_y : float }

> Until this morning I would have guessed that the type of a record was
> not resolved until all of the labels were examined.  As I re-read the
> caml-light and ocaml manuals I see that this is not true.
>
> Are there good reasons for this "restriction"?  I can see how this
> this might be considered a good software practice.  Maybe, due to
> pattern matching, it is not possible to have shared labels.

It is definitively possible to have what you call ``shared'' labels,
that is overloaded labels. It is just a bit complex to add to the
type-checker.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis

Label Names Space - philosophy or implementation?

[pbrisset]

John Gerard Malecki writes:
> 
> A co-worker has (vehemently) pointed out to me that record label names
> cannot be shared.  For example, the following fails
> 
> 	type foo = { name : string; x : int }
> 	let    a = { name = "foo";  x = 1 }
> 
> 	type bar = { name : string; y : float }
> 	let    b = { name = "bar";  y = 9. }
> ...
> field with a standardized label.  This makes it easier for him to
> write printers for his data-structure.  Does anyone have a
> recommendation to make to him?

	type 'a foobar = { name : string; x : 'a}
	let print_name {name = s} = print_string s
	print_name { name = "foo"; x = 1 }
	print_name { name = "bar";  x = 9. }

or using classes and inheritance (I do not like it but ...) :

	class named (s:string) =
	  val private name = s
	  method name = name
	end
	class foo n (x:int) =
	  inherit named n
	  val private x = x
	  method x = x
	end
	class bar n (y:float) =
	  inherit named n
	  val private y = y
	  method y = y
	end
	let print_name x = print_string x#name
	print_name (new foo "foo" 1)
	print_name (new bar "bar" 9.)

My 0.02 euros...

--Pascal

Re: Label Names Space - philosophy or implementation?

[Xavier Leroy]

> A co-worker has (vehemently) pointed out to me that record label names
> cannot be shared. Are there good reasons for this "restriction"?

There's one: it simplifies type inference greatly. More formally, it
guarantees the principal type property. Apart from this, I agree it's
a major pain.

Labels that belong to several record types cause no problems as long
as all labels of a record are given. This is always the case at record
construction time { lbl1 = val1; ... lblN = valN }. Then, it's not
hard to determine the type of the record from the labels lbl1 ... lblN.

The problem is with access to a record field x.lbl and matching with
record patterns { lbl = pat }. Consider for instance

        let f x = x.lbl

What type should be inferred for x if there are several record types
with a label "lbl"? There are at least three options:

a- Consider that lbl belongs to at most one record type t (the one
declared last) and infer that x : t. That's the Caml Light and
Objective Caml approach.

b- Try to gather more information on how f is used in the remainder of
the program to resolve the ambiguity. If this is not possible, fail
with a type error, requesting the user to put a type annotation

        let f (x:t) = x.lbl

This is essentially identical to resolving overloading on arithmetic
operators, e.g. + which is both integer addition and floating-point
addition. Both Caml V3.1 and SML/NJ allow overloading on operators and
on record labels, with more or less clever overloading resolution
strategies. The bad news is that type inference in the presence of
overloading is costly and rejects as ambiguous many perfectly
well-typed definitions, such as

        let f x = x.lbl
or
        let g x = x + x

c- Introduce record polymorphism, i.e. the function fun x -> x.lbl
is given a type that says "I accept as arguments all records with a
label lbl of type T, and I return a value of type T". On the typing
side, record polymorphism is well understood, reasonably efficient,
and preserves the principal type property. (The typing of objects in
Objective Caml relies on similar techniques.)

The challenge is on the compilation side. With conventional records,
all record accesses are at fixed, statically-known offsets inside the
memory blocks that represent the records. With record polymorphism,
this is no longer true. For instance, in fun x -> x.lbl, the position
of lbl in x cannot be determined statically and has to be computed at
run-time in a way similar to method lookup for objects. This entails a
big performance hit, at least if done naively. It is still unclear how
much of this overhead can be reduced through clever compile-time
analyses.

- Xavier Leroy

Re: Label Names Space - philosophy or implementation?

[Andrew Conway]

[ Francais: Il y a quelques choses (dessous) que je n'aime pas avec ocaml, 
            mais, les autres langues ont des plus grands problemes. ]


> > A co-worker has (vehemently) pointed out to me that record label names

I agree with the vehemently part.

This is an annoyance which I have frequently run into. 

> Its a common habit to prefix the labels with the name of the type:

That is an ugly hack to work around a problem with the language.


Don't get me wrong, I think that, all in all, ocaml is my favourite
language, and I am very greatful to you for making it. The fact that 
something is the best doesn't mean that it couldn't be better, however, 
so it is about time for me to reorder my current list of annoyances.

Below is a list of the common mistakes I make in CAML that
I don't make in other languages, or annoyances that I have with CAML. The
list is ordered, most annoying coming first. Many of these have been mentioned
by other people before; I am just adding support.

1) Writing "+" instead of "+."
     [ I know this is effectively intractable, and I am willing to put
       up with it. It is, however, my major source of type mistakes when
       I am doing numeric work. ]

2) Putting an extra semicolon before a "done" or "end" statement

     [ This is especially annoying when adding a line after the last line,
       such as a debugging printf statement, or re-ordering lines. ]

3) I have written my own library of (amongst other things) standard list
   and array manipulation routines, in modules Mylist and Myarray. If I
   want a function such as map2 on lists, I type in List.map2. If I
   want an analagous function on arrays, I do Myarray.map2. Frequently I
   mistakenly do Array.map2 instead, remembering that it is defined for
   arrays, and since it is in the standard library for List, it is also
   in the standard library for arrays. I appreciate the reasons why these
   are not symmetyric, but it would be nice if it were possible to merge
   modules, so that I could refer to my own libraries through the List
   or Array modules.

4) Using a record label twice

5) Annoyance: one can make a custon toplevel, linking in custom code
   to manipulate ones own datatypes. This is really useful. However,
   one cannot link in a command to automatically use a prettyprinter,
   and this command has to be done by hand. Having a startup script
   would be really useful.
  
6) There is no deep copy.

7) One cannot use ocamlopt compiled routines in camltop, though one can use
   C routines. I realise that the memory allocation register usage makes
   this difficult. On the other hand, a few days ago, I was considering 
   rewriting some matrix manipulation routines in C instead of ocaml,
   so that I could run them at a reasonable speed under ocamltop, even
   though they ran acceptably quickly when compiled by ocamlopt. Then it 
   suddenly dawned on me that it seemed a little silly to convert something 
   FROM ocaml to make it easier to work WITH ocaml.

Anyway, I should again say that these are, of course, just annoyances, 
and I still really like the language. However, having you aware that they
are frustrations can't hurt.

Thanks again,

Andrew.