[Caml-list] illegal permutation of structure fields?

[Caml-list] illegal permutation of structure fields?

[Markus Mottl]

Hello,

I've just found out to my surprise that the following does not work:

file: bla.ml
---------------------------------------------------------------------------
module type FOO = sig
  val x : int
  val y : int
end
---------------------------------------------------------------------------

file: bla.mli
---------------------------------------------------------------------------
module type FOO = sig
  val y : int
  val x : int
end
---------------------------------------------------------------------------

This yields the following error:

  The implementation bla.ml does not match the interface bla.cmi:
  Module type declarations do not match:
    module type FOO = sig val x : int val y : int end
  is not included in
    module type FOO = sig val y : int val x : int end
  Illegal permutation of structure fields

Why is this illegal? Wouldn't it be very straightforward to normalize
the signatures (e.g. sort elements by name) before matching them?

I knew that there is a somewhat similar restriction for record types,
which does not allow permutation of record elements in the type
definitions of implementation and interface.

In the latter case I see that without normalization there would be
problems correctly accessing record elements, but I don't quite understand
the rationale behind the first restriction.

Wouldn't normalization get rid of the problems in both cases? Or am I
overlooking anything?

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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] illegal permutation of structure fields?

[Xavier Leroy]

> I've just found out to my surprise that the following does not work:
> 
> file: bla.ml
> ---------------------------------------------------------------------------
> module type FOO = sig
>   val x : int
>   val y : int
> end
> ---------------------------------------------------------------------------
> 
> file: bla.mli
> ---------------------------------------------------------------------------
> module type FOO = sig
>   val y : int
>   val x : int
> end
> ---------------------------------------------------------------------------
> 
> This yields the following error:
>   Illegal permutation of structure fields
> 
> Why is this illegal? Wouldn't it be very straightforward to normalize
> the signatures (e.g. sort elements by name) before matching them?

That's more or less what old versions of OCaml did, but it's
incorrect.  The reason is that a module signature determine the layout
of the corresponding structure: if

  module A : sig val x : int val y : int end

then A is represented as the tuple (value_of_x, value_of_y), while

  module B : sig val y : int val x : int end

is represented as the tuple (value_of_y, value_of_x).

When you perform signature matching, the compiler recomputes the
structure representation to match the new signature.  For instance:

  module C : sig val y : int val x : int end = A

causes the compiler to generate roughly the following code

  let C = (snd A, fst A)

so that the representation of C matches what clients of C expect from
its signature.

If we were to allow module type equivalence up to permutation, this
strategy would be invalid.  Consider:

file bla.ml

  module type FOO = sig val x : int val y : int end
  module A : FOO = ...

file bla.mli

  module type FOO = sig val y : int val x : int end
  module A : FOO

Since the implementation of A and its declaration in the signature
have the same module type FOO, no field rearrangement is performed.
Yet, A is represented as (val_x, val_y), while clients of A expect
(val_y, val_x).

On this example, expanding the FOO module type before generating the
coercion code (that rearranges fields) would suffice.  However, I
believe there are more complex examples involving abstract module types
(e.g. as functor parameters) where expanding module type names would
not suffice.  So, let's keep it simple: no permutation!

- Xavier Leroy
-------------------
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] illegal permutation of structure fields?

[Andreas Rossberg]

Xavier Leroy wrote:
> 
> > file: bla.ml
> > ---------------------------------------------------------------------------
> > module type FOO = sig
> >   val x : int
> >   val y : int
> > end
> > ---------------------------------------------------------------------------
> >
> > file: bla.mli
> > ---------------------------------------------------------------------------
> > module type FOO = sig
> >   val y : int
> >   val x : int
> > end
> > ---------------------------------------------------------------------------
> >
> > This yields the following error:
> >   Illegal permutation of structure fields
> >
> > Why is this illegal? Wouldn't it be very straightforward to normalize
> > the signatures (e.g. sort elements by name) before matching them?
> 
> That's more or less what old versions of OCaml did, but it's
> incorrect.  The reason is that a module signature determine the layout
> of the corresponding structure: if
> 
>   module A : sig val x : int val y : int end
> 
> then A is represented as the tuple (value_of_x, value_of_y), while
> 
>   module B : sig val y : int val x : int end
> 
> is represented as the tuple (value_of_y, value_of_x).

Then the followup question of course is: isn't it trivial to use a
canonical layout instead, where the tuple components are sorted wrt. to
the corresponding fields' label? This way layout is invariant wrt
permutation in signatures. Or is there a particular problem with such a
scheme?

(BTW, the same holds for record and variant types, where Ocaml does not
allow reordering of fields/constructors either.)

Best regards,

	- Andreas Rossberg

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids.
 If Pac Man affected us as kids, we would all be running around in
 darkened rooms, munching pills, and listening to repetitive music."
-------------------
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] illegal permutation of structure fields?

[Markus Mottl]

Hm, well, thanks a lot for the very elaborate explanation! ... But I am
still not fully convinced (evil me! ;)

On Mon, 23 Jul 2001, Xavier Leroy wrote:
> That's more or less what old versions of OCaml did, but it's
> incorrect.  The reason is that a module signature determine the layout
> of the corresponding structure: if

Why doesn't the normalized inferred signature of the module determine
its layout? E.g.:

  module A = struct
    let y = 1
    let x = 2
  end

could be transformed to (tuple that describes memory layout):

  (2, 1)

Of course, one would have to make sure that side effects are executed
in the right order when the creation of the values involves any, but
this should only require sorting the computations accordingly. This
marginally complicates things, but ...

> When you perform signature matching, the compiler recomputes the
> structure representation to match the new signature.  For instance:
> 
>   module C : sig val y : int val x : int end = A
> 
> causes the compiler to generate roughly the following code
> 
>   let C = (snd A, fst A)

... such glue code wouldn't be necessary in this case anymore: the
compiler could just generate:

  let C = A

Of course, if the signature of C were more restrictive than A, we might
have to generate a fresh tuple again, because some tuple slots could
disappear.

> so that the representation of C matches what clients of C expect from
> its signature.

The client would always expect the order of the normalized signature,
which should make it match the order used in the implementation, which
is also normalized.

> If we were to allow module type equivalence up to permutation, this
> strategy would be invalid.  Consider:

[snip]

The snipped example wouldn't lead to any problems with the mentioned
approach where the module implementation is already in normalized order.

> However, I believe there are more complex examples involving abstract
> module types (e.g. as functor parameters) where expanding module type
> names would not suffice.  So, let's keep it simple: no permutation!

I don't see any inherent problem here, but maybe I just don't fully
understand your argument. Am I missing some hidden catch?

Anyway, I don't feel terribly restricted without permutation, and not
having to rearrange the elements of the tuple on some simple module
equations doesn't look like a big performance gain either. So even if
my idea worked, I wouldn't mind if you put them on your "superfluous
features"-staple... ;)

Best regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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] illegal permutation of structure fields?

[John Max Skaller]

Xavier Leroy wrote:
> 
> > I've just found out to my surprise that the following does not work:

[]

> > This yields the following error:
> >   Illegal permutation of structure fields
> >
> > Why is this illegal? Wouldn't it be very straightforward to normalize
> > the signatures (e.g. sort elements by name) before matching them?
> 
> That's more or less what old versions of OCaml did, but it's
> incorrect.  The reason is that a module signature determine the layout
> of the corresponding structure: if

[]

I don't understand this explanation. Markus suggested
_normalising_ the order by name. That is, the 'actual'
storage order of elements is determined by their names,
not by the order of writing.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net
-------------------
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] illegal permutation of structure fields?

[Xavier Leroy]

> Then the followup question of course is: isn't it trivial to use a
> canonical layout instead, where the tuple components are sorted wrt. to
> the corresponding fields' label? This way layout is invariant wrt
> permutation in signatures. Or is there a particular problem with such a
> scheme?

It seems possible to proceed this way; I was just explaining that this
is not the way it's currently done in OCaml.

In other words, I read Markus' question as "why not compare module
types after sorting their components?", and replied to that question,
but maybe he meant "why not determine the memory layout of structures
after sorting their components?".  In the latter case, the answer is
that it could probably be done, but I see no real strong need for this
(see below).

> (BTW, the same holds for record and variant types, where Ocaml does not
> allow reordering of fields/constructors either.)

Yes, but would this be really useful?  Manifest type declarations and
manifest module types in signatures must be implemented by the same
type/module type declaration in the matching structure.  This is
generally done by generous cut&paste between the signature and the
structure.  What would we gain by allowing reordering fields,
constructors or module type components?  Except making it harder for
the programmer to spot mismatches between the two declarations...

- Xavier Leroy
-------------------
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] illegal permutation of structure fields?

[Markus Mottl]

On Thu, 26 Jul 2001, Xavier Leroy wrote:
> In other words, I read Markus' question as "why not compare module
> types after sorting their components?", and replied to that question,
> but maybe he meant "why not determine the memory layout of structures
> after sorting their components?".  In the latter case, the answer is
> that it could probably be done, but I see no real strong need for this
> (see below).

Yes, that's what I meant. Maybe my question was ill-formulated: in my
first mail I only mentioned signatures and implicitly assumed that the
order of memory layout would follow.

> Yes, but would this be really useful?  Manifest type declarations
> and manifest module types in signatures must be implemented by
> the same type/module type declaration in the matching structure.
> This is generally done by generous cut&paste between the signature
> and the structure.  What would we gain by allowing reordering fields,
> constructors or module type components?  Except making it harder for
> the programmer to spot mismatches between the two declarations...

I mostly agree on this (what concerns variants and records). I still
think that module types are a bit different, because their purpose is
to abstract, whereas variants and records are concrete representations.
I don't think anybody would be hurt by a more relaxed handling of "law
and order": you can still use cut&paste then, and there is less of a
chance that people run into mile long compiler output due to conflicting
signature definitions. The latter is surely much more difficult to deal
with than comparing two sum type definitions for equality.

Anyway, I don't feel particulary annoyed by the current way things are
handled. It has taken quite a while before I even noticed this kind
of behaviour...

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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