[Caml-list] Proposal for separate compilation

[Caml-list] Proposal for separate compilation

[Alain Frisch]

Hello list,

I'd like to get feedback on a suggestion to modify the way OCaml
handle separate compilation. I already mentioned that proposal to
Xavier and Jacques.

This is an attempt to address the issue of collision between the names
of two external modules. This should also merge the concept of
-pack'ed units and libraries, to get the best of both worlds.

First, let me describe (my understanding of) the current system.

i) The compiler transforms a source interface (.mli) to a compiled
interface (.cmi). When other external modules are referenced in the
.mli file, the corresponding .cmi files are looked up in the "include"
directories (-I options on the command line). The name of these
interfaces are stored symbolically in the .cmi. Their md5 are stored
in the produced .cmi so as to detect inconsistencies.

ii) The bytecode compiler transforms a source implementation (.ml)
to a compiled implementation (.cmo). This name of the external
implementation and interfaces used in .ml are stored in the .cmo.
The md5 of the interfaces are all stored in the .cmo.

iii) The native compiler produces a .cmx and a .o files. If the .cmx
of other compiled implementation are found at compile time,
they are used to propagate constants are perform cross-unit
inlining. Their md5 are also stored in the produced .cmx.


Currently, a compiled unit (.cmi,.cmo,.cmx,.o) refers to another unit
through its symbolic name, as used in the source file.  My proposal is
to replace these names with unique identifiers.

Bottom-line: when a unit (.ml,.mli) is compiled, the external units
are looked up. The information we really want to store in the compiled
unit is a pointer to the external units as found during compilation.
Since we want to be able to move or to repackage (in a library)
compiled units, we can implement these pointers with unique
identifiers: either a random number, or a md5 hash of the unit.


Let me give an example.

==a.mli==
type t
====

==b.mli==
type s = X of A.t
====

First you compile a.mli and you get a.cmi. When you compile b.mli,
the file a.cmi is found, and intuitvely, the content of b.cmi
corresponds to something like:

==b.cmi==
type s = X of #{a.cmi}.t
====

where #{a.cmi} denote the unique identifier (uid) of a.cmi as found during
compile time. Same story for implementations.


The compiler needs two distinct lookup mechanisms:

- a mapping from symbolic names (found in source code) to uids
- a mapping from uids to compiled units (either files, or part of an
  archive/library)

The first mapping is (almost) a preprocessing pass.

Now it possible to have several units with the same name.
For instance, consider a project with these files:

dir1/a.ml
dir1/a.mli
dir1/b.ml
dir1/b.mli
dir2/a.ml
dir2/a.mli

Imagine that the only dependency is from dir1/b to dir1/a.
To compile these:
(cd dir1; ocamlopt -c a.mli a.ml b.mli b.ml)
(cd dir2; ocamlopt -c a.mli a.ml)

ocamlopt produces: dir1/{a,b}.{cmi,cmx,o} and dir2/a.{cmi,cmx,o}.
dir1/b.{cmi,cmx} reference dir1/a.{cmi,cmx} through the uid
of these files.

Now you can compile a module x.ml that uses dir1/b.cmx and dir2/a.cmx.
You just need to let the compiler/linker know how to find a compiled
unit given its uid. For instance, you could just give it a list
of directoroes, and it would look for all the .cmi,.cmx files in this
directory. More realistically, you would keep into the uid the symbol
name of the unit, so as to look only at the .cmi,.cmx files with
the correct name. (You also want to store where the unit was
found, for error messages, see below.)

A library (.cma,.cmxa) would just be an archive of compiled units
(*including* compiled interfaces) (plus probably an index: uid ->
component).  It can be used for both mappings.  You need only to add a
reference to the library file on the compiler command line (no need
for a -I flag). Additionnaly, when building and/or compiling with a
library, it should be possible to specify a prefix, or to give new
names to its components. This would only affect the mapping from names
to compiled units. This replaces the -pack option, with a slightly
different semantics: when the same units is packaged in several
libraries, and several of these libraries are used, the fact that it
is the same module is retained (for the typing and link phases: types
are compatibles, and only one implementation of the module is
included). As a side product, one no longer needs to rename symbols in
.o objects when we -pack (we get rid of objutils), because the symbols
in the .o objects would be prefixed with the uid.

We can imagine fancy features on the command line, like adding a
prefix for a library:

ocamlopt -c -prefix:A=mylib.cmxa x.ml

or for a directory:

ocamlopt -c -prefix:A=/home/joe/mylib/ x.ml

It would compile x.ml, and references to modules A.* in x.ml would actually
be resolved in mylib.cmxa (resp. ~/mylib/).
(And for linking, simply: ocamlopt -o mylib.cmxa x.cmx, resp.:
ocamlopt -o -I /home/joe/mylib x.cmx).

You no longer get an error message:
« Files b.cmo and a.cmo make inconsistent assumptions over interface A »
but something like:
« Couldn't find interface A with hash XXXXXX (which was found in
  /home/joe/mylib.cma during compilation) »


There are a lot of practical issues to deal with (such as: getting
decent outputs for ocamlc -i and gprof, etc...).

What do people think about the proposal ?


-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Richard Jones]

On Fri, May 21, 2004 at 06:32:23PM +0200, Alain Frisch wrote:
> You no longer get an error message:
> « Files b.cmo and a.cmo make inconsistent assumptions over interface A »

I don't really understand the intricacies of your proposal, but I do
have a small suggestion.  Can the error messages be made more
explicit.

For example, at the moment one of my colleagues is having lots of
problems building our Merjis test environment on his machine (as is
often the case, sadly ...).  The problems manifest themselves as
the Dynlink error message:

interface mismatch on <module>

This is quite an annoying error message because it doesn't tell you
what module is loading what other module and where it's finding them.
A better message would be:

interface mismatch:
  expected to find <module> with hash <0123456789abcdef>
  but found instead <module> in /usr/lib/ocaml/3.07/foo/bar.cma with
    hash <fedcba9876543210>

This would help greatly with tracking down these problems.

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
If I have not seen as far as others, it is because I have been
standing in the footprints of giants.  -- from Usenet

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Nicolas Cannasse]

> Hello list,
>
> I'd like to get feedback on a suggestion to modify the way OCaml
> handle separate compilation. I already mentioned that proposal to
> Xavier and Jacques.
 [...]
> What do people think about the proposal ?

To put it simple, and if I understood correctly :

Right now the linking lookup is done on a name basis, with an additionnal
MD5 check. Your proposal is to make a lookup on a (Name+MD5) basis. This way
you can have overlapping names that differs only by MD5.

That looks simple and nice, since it corrects two problems at once :
- module name overlapping
- versionning : having several versions on the library installed or packaged
into the same CMA would be ok this way !

Where can I vote for ? :)

Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Xavier Leroy]

> Currently, a compiled unit (.cmi,.cmo,.cmx,.o) refers to another unit
> through its symbolic name, as used in the source file.  My proposal is
> to replace these names with unique identifiers.

This is an interesting proposal.  You might be interested in Martin
Elsman's PhD (DIKU, 1998), which uses techniques along these lines in
a defunctorizing, whole-program SML compiler.

There is one thing that puzzles me in your proposal.  Consider two
compilation units A and B, where B refers to A.  

When we compile B.ml, it can be that the only thing the compiler knows
about A is its interface A.cmi.  This is certainly true for ocamlc.
ocamlopt can take advantage of information on A's implementation, as
found in A.cmx, but in the current model the presence of A.cmx isn't
mandatory to compile B.ml, ocamlopt will generate less efficient but
correct code if A.cmx isn't there.

So, what unique identifier is B going to use to refer to A's definition?
Since A.cmi is the only available info on A, that
identifier must be tied to A.cmi: either a hash of A's interface, or
some unique identifier generated when A.mli is compiled into A.cmi.
It looks like you're going to get name collisions when several
compilation units have the same interface.  More generally, you
haven't fully severed the connection that we have in the current
system between the identifier representing the definitions of a
compilation unit and the name or identifier of its interface.

There are several ways to work around this issue.  One is to restrict
your scheme to native-code compilation (ocamlopt) and demand that
A.cmx is available when compiling B.ml where B depends on A.  Then,
A.cmx can contain the truly unique identifier for A's implementation,
and that identifier can be used in the code generated for B.  But the
bytecode compiler will not be able to take advantage of your scheme.

Another option is to generate unique identifiers not just for the
exports of a compilation unit but also for its imports.  That is,
compiling B.ml will use some random ident "xyz" for B's exports
and another random ident "abc" for A's exports.  Compiling A.ml will
assign a different ident "def" to A's exports.  All these (ident, name)
associations are recorded in the generated .cmo and .cmx files, of course.
At link-time, the linker recognizes that "abc" and "def" are two
identifiers for the same thing, and equates them.  (Most native-code
linkers allow to identify two symbols, although I'm not sure all of
them support this feature.)

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Nicolas Cannasse]

> > Currently, a compiled unit (.cmi,.cmo,.cmx,.o) refers to another unit
> > through its symbolic name, as used in the source file.  My proposal is
> > to replace these names with unique identifiers.
>
> This is an interesting proposal.  You might be interested in Martin
> Elsman's PhD (DIKU, 1998), which uses techniques along these lines in
> a defunctorizing, whole-program SML compiler.
>
> There is one thing that puzzles me in your proposal.  Consider two
> compilation units A and B, where B refers to A.
>
> When we compile B.ml, it can be that the only thing the compiler knows
> about A is its interface A.cmi.  This is certainly true for ocamlc.
> ocamlopt can take advantage of information on A's implementation, as
> found in A.cmx, but in the current model the presence of A.cmx isn't
> mandatory to compile B.ml, ocamlopt will generate less efficient but
> correct code if A.cmx isn't there.
>
> So, what unique identifier is B going to use to refer to A's definition?
> Since A.cmi is the only available info on A, that
> identifier must be tied to A.cmi: either a hash of A's interface, or
> some unique identifier generated when A.mli is compiled into A.cmi.
> It looks like you're going to get name collisions when several
> compilation units have the same interface.  More generally, you
> haven't fully severed the connection that we have in the current
> system between the identifier representing the definitions of a
> compilation unit and the name or identifier of its interface.
>
> There are several ways to work around this issue.

Maybe I didn't understand well, but I think I have a more easy answer :
if the identifier is composed of both the hash of the cmi and the name of
the module (so something like (A,hash A)) then we have name collision only
when we have several compilation units with both the same name and same
interface. This is more unlikely to happen, or the user is using two
different implementations of the same module at the same time, and then a
linker error will make him choose one (whatever the choice, the program is
correctly typed but both implementations can have different semantics and
then leave some bugs). Other way is to add some random data to the hash when
the CMI is compiled (and of course ignore this extra-data when recompiling
to avoid spending CPU ).
BTW, is there any way such a proposal will end up into the caml distribution
?

Best Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Alain Frisch]

On Wed, 26 May 2004, Xavier Leroy wrote:

> This is an interesting proposal.  You might be interested in Martin
> Elsman's PhD (DIKU, 1998), which uses techniques along these lines in
> a defunctorizing, whole-program SML compiler.

Thanks for the pointer.

> There is one thing that puzzles me in your proposal.  Consider two
> compilation units A and B, where B refers to A.
>...
> So, what unique identifier is B going to use to refer to A's definition?
> Since A.cmi is the only available info on A, that
> identifier must be tied to A.cmi: either a hash of A's interface, or
> some unique identifier generated when A.mli is compiled into A.cmi.

If I understand the point correctly, an example would two modules
MyString1 and MyString2, with myString1.mli == myString2.mli:

type t = string
val compare: t -> t -> unit

but different implementations. One solution is simply, as Nicolas
suggests, to store the original name of the compilation unit in the uid.
Still, one could imagine two modules with the same name and the same
interface in unrelated libraries. This would be a good argument for using
reallly unique ids instead of hash. When you compile an interface a.mli,
you just mark a.cmi with a fresh random uid (with possibly a check that
the real content of a.cmi has been modified, otherwise don't touch the
uid). This will be used to make reference to module A from b.cmo (and of
course a.cmo). In other words: compilation of interfaces is given a
generative semantics.

Since you mention the generation of the unique identifier, I guess I
missed something.


-- Alain


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Jacques GARRIGUE]

From: Alain Frisch <Alain.Frisch@ens.fr>

> On Wed, 26 May 2004, Xavier Leroy wrote:

> > There is one thing that puzzles me in your proposal.  Consider two
> > compilation units A and B, where B refers to A.
> >...
> > So, what unique identifier is B going to use to refer to A's definition?
> > Since A.cmi is the only available info on A, that
> > identifier must be tied to A.cmi: either a hash of A's interface, or
> > some unique identifier generated when A.mli is compiled into A.cmi.
> 
> If I understand the point correctly, an example would two modules
> MyString1 and MyString2, with myString1.mli == myString2.mli:
> 
> type t = string
> val compare: t -> t -> unit
> 
> but different implementations. One solution is simply, as Nicolas
> suggests, to store the original name of the compilation unit in the uid.
> Still, one could imagine two modules with the same name and the same
> interface in unrelated libraries. This would be a good argument for using
> reallly unique ids instead of hash. When you compile an interface a.mli,
> you just mark a.cmi with a fresh random uid (with possibly a check that
> the real content of a.cmi has been modified, otherwise don't touch the
> uid). This will be used to make reference to module A from b.cmo (and of
> course a.cmo). In other words: compilation of interfaces is given a
> generative semantics.

Yes, but by doing that you are breaking two things:
* a .cmi does no longer depend only on the contents of the .mli
  i.e., if you recompile twice the same library, then all the
  dependencies must be recompiled, eventhough nothing has changed
  (This may make bootstrapping the compiler rather complicated!
   Every recompilation of the standard library would be incompatible.)
* one can imagine a strange situation where you generated two
  differents .cmo with the same .cmi (i.e. two .ml for one .mli, and
  you compiled the .mli only once). Your scheme cannot cope with this
  case: the two .cmo would conflict.
  (I agree this is a bit far fetched)

The bootstrapping problem may be a show-stopper.
 
> Since you mention the generation of the unique identifier, I guess I
> missed something.

This looks like an attempt to solved the above compatibility problem.
Do not change the semantics of interfaces, only the compilation of
implementation.
Both imports and exports of libraries have "abstract" names (in
practice unique ids, different for import and export) and the linker
connects imports to the corresponding exports. Sound pretty powerful,
and theoretically nice. But you get bigger .cmo/.cmx, and linking is
more complex.

Jacques

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Nicolas Cannasse]

[...]
> > but different implementations. One solution is simply, as Nicolas
> > suggests, to store the original name of the compilation unit in the uid.
> > Still, one could imagine two modules with the same name and the same
> > interface in unrelated libraries. This would be a good argument for
using
> > reallly unique ids instead of hash. When you compile an interface a.mli,
> > you just mark a.cmi with a fresh random uid (with possibly a check that
> > the real content of a.cmi has been modified, otherwise don't touch the
> > uid). This will be used to make reference to module A from b.cmo (and of
> > course a.cmo). In other words: compilation of interfaces is given a
> > generative semantics.
>
> Yes, but by doing that you are breaking two things:
> * a .cmi does no longer depend only on the contents of the .mli
>   i.e., if you recompile twice the same library, then all the
>   dependencies must be recompiled, eventhough nothing has changed
>   (This may make bootstrapping the compiler rather complicated!
>    Every recompilation of the standard library would be incompatible.)

That's why I'm suggesting we should still use a hash of the cmi as uid, and
add a random id in order to resolve ambiguous cases only.

> * one can imagine a strange situation where you generated two
>   differents .cmo with the same .cmi (i.e. two .ml for one .mli, and
>   you compiled the .mli only once). Your scheme cannot cope with this
>   case: the two .cmo would conflict.
>   (I agree this is a bit far fetched)

This is clearly forbidden by both current and "improved" linking model, I'm
not sure we want that "feature" :)

> This looks like an attempt to solved the above compatibility problem.
> Do not change the semantics of interfaces, only the compilation of
> implementation.
> Both imports and exports of libraries have "abstract" names (in
> practice unique ids, different for import and export) and the linker
> connects imports to the corresponding exports. Sound pretty powerful,
> and theoretically nice. But you get bigger .cmo/.cmx, and linking is
> more complex.

This is also a solution, but as you told, it's more complex to implement.
I'm worried also about this complexness when using Dynamic linking . Alain's
idea - still not perfect - is simple enough to be worth implemented.

Best Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Alain Frisch]

On Fri, 28 May 2004, Jacques GARRIGUE wrote:

> Yes, but by doing that you are breaking two things:
> * a .cmi does no longer depend only on the contents of the .mli
>   i.e., if you recompile twice the same library, then all the
>   dependencies must be recompiled, eventhough nothing has changed
>   (This may make bootstrapping the compiler rather complicated!
>    Every recompilation of the standard library would be incompatible.)

The method used for generating of the uid for a given unit can be decided
at compile time: one could compile some interfaces (like the stdlib) with
a "transparent" semantics (the uid is a hash of the name, the content of
the interface, and maybe a "salt" to be used as a namespace for the
library), and some with a generative semantics. The problem with the
transparent semantics is the one mentionned by Xavier (several modules
with the same name, same interface, different implementation, all linked
together), which should be extremely rare (does it happen for the whole
set of OCaml modules written so far) ?  The "salt" could handle these very
rare cases.

> * one can imagine a strange situation where you generated two
>   differents .cmo with the same .cmi (i.e. two .ml for one .mli, and
>   you compiled the .mli only once). Your scheme cannot cope with this
>   case: the two .cmo would conflict.
>   (I agree this is a bit far fetched)

Indeed, this is a bit far fetched. Given that the two .ml have the same
name, with the current scheme, you cannot link them together directly
(you could -pack them, or burry them in libraries, etc...)

> This looks like an attempt to solved the above compatibility problem.
> Do not change the semantics of interfaces, only the compilation of
> implementation.

Ok, thanks.

> Both imports and exports of libraries have "abstract" names (in
> practice unique ids, different for import and export) and the linker
> connects imports to the corresponding exports. Sound pretty powerful,
> and theoretically nice. But you get bigger .cmo/.cmx, and linking is
> more complex.

I don't see what the solution brings compared to the current scheme if one
stores names (and not only uids) in compiled units. In case of name
collision, how would the linker know what to do ?


-- Alain

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Proposal for separate compilation

[Christian Lindig]

On May 28, 2004, at 11:55 AM, Alain Frisch wrote:
>
> The method used for generating of the uid for a given unit can be 
> decided
> at compile time: one could compile some interfaces (like the stdlib) 
> with
> a "transparent" semantics (the uid is a hash of the name, the content 
> of
> the interface, and maybe a "salt" to be used as a namespace for the
> library), and some with a generative semantics.

When talking about the name of a module, I assume people so far refer to
"a", when the file is actually /some/where/lib/a.{ml,mli,cmi,cmo}. 
Would it make sense to consider a configurable suffix of the file's 
path instead? Say, you can tell the compiler to consider "lib/a" or 
"where/lib/a" as the module's name when computing the hash. This would 
be similar to a "salt". The longer the path, the more difficult it will 
become to move files around; hence it is a guarantee, that the file is 
used in the proper context.

-- Christian  

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners