Why does the order in the Makefile matter?

Why does the order in the Makefile matter?

[Mattias Waldau]

Two runs 'make all', the only difference in the order in the OBJS-line in
the Makefile.

What is the needed order? Should I use the order of .depend?

/mattias

c:\data\ocaml\stocks\extract>make all
ocamlc -g  -c regexp.mli
ocamlc -g   -c source.ml
ocamlc -g   -c regexp.ml
ocamlc -g -o all -custom str.cma unix.cma  extract.cmo source.cmo column.cmo
regexp.cmo
Error while linking source.cmo: Reference to undefined global `Regexp'
make: *** [all] Error 2

c:\data\ocaml\stocks\extract>make depend
make depend
make all
ocamldep  *.ml *.mli > .depend

c:\data\ocaml\stocks\extract>make all
ocamlc -g -o all -custom str.cma unix.cma  column.cmo regexp.cmo extract.cmo
source.cmo
camlprim0.c


The only difference made between these two compilations is that I moved
source.cmo last in
the OBJS-row in the Makefile

OBJS=column.cmo regexp.cmo extract.cmo source.cmo


----
Mattias Waldau

Re: Why does the order in the Makefile matter?

[Pierre Weis]

> Two runs 'make all', the only difference in the order in the OBJS-line in
> the Makefile.
> 
> What is the needed order? Should I use the order of .depend?

A Caml implementation file (a .ml file) is a list of definitions and
expression evaluations.

-- definitions can only refer to preceding definitions (due to the
so-called ``static'' binding rule) and cannot refer to following
definitions.

-- top-level expressions may appear anywhere in implementation files and those
expressions define the runtime computation. They must be evaluated in
the exact order specified by the user in his source file (otherwise
strange things may happen if ``exit 0;;'' is evaluated before ``main
();;''!).

Hence, when the entire program is made of multiple implementation
files, those files must be linked in any order that is compatible with
the static binding rule: no definition can be linked if it refers to
an identifier that is defined after the definition at hand.  In
addition, expressions to be computed must evidently appear in any
order compatible with the desired runtime behaviour.

Hope this helps,

Pierre Weis

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

Why does the order in the Makefile matter? --- Linking with C

[kahl]

Pierre Weis <Pierre.Weis@inria.fr> wrote:
 
> Hence, when the entire program is made of multiple implementation
> files, those files must be linked in any order that is compatible with
> the static binding rule: no definition can be linked if it refers to
> an identifier that is defined after the definition at hand.  In
> addition, expressions to be computed must evidently appear in any
> order compatible with the desired runtime behaviour.

However, yesterday I experimented with implementing a system call in C
(why does the standard library only provide sleep with a granularity of
 whole seconds?),
and I linked it together with the .cmx file containing the external definition
into utils.cmxa.

Then I proceeded to link my application, consisting of other *.ml modules
that use stuff from utils.cmxa, including that external function:

ocamlopt ... -o application utils.cmxa others1*.cmxa others2*.cmx

The result was a link error that the system call could not be found.
(The analogous bytecode variant compiles without complaints,
 but I only use the bytecode compiler as a kind of ``lint''.)
So I had to take utilsC.o out of utils.cmxa and revert to:

ocamlopt ... -o application utils.cmxa others1*.cmxa others2*.cmx utilsC.o

This is logical with my understanding of C linking,
but I would prefer not to have to use that knowledge... ;-)

Is this asymmetry known/documented/on purpose?


Best regards,

Wolfram Kahl

RE: Why does the order in the Makefile matter?

[Mattias Waldau]

The answer was the in manual, page 131, "The order in which .cmo....."

Re: Why does the order in the Makefile matter?

[Stephan Houben]

On Sat, 28 Oct 2000, Pierre Weis wrote:

> Hence, when the entire program is made of multiple implementation
> files, those files must be linked in any order that is compatible with
> the static binding rule: no definition can be linked if it refers to
> an identifier that is defined after the definition at hand.  In
> addition, expressions to be computed must evidently appear in any
> order compatible with the desired runtime behaviour.

I completely understand this point, and I agree that there are legal 
Caml programs that have a different behavior depending on the order
of the .cmo file linking. However, every program I write (and I suppose
that's true for most of us) has an invariant behavior under all legal
permutations of the .cmo files. Mostly because I only have 1 .ml file
that actually does anything; the rest only contain side-effect-free
definitions.

So it would be nice if the compiler itself could put the .cmo files in an order
compatible with the static binding rule. This would remove the tedium of
putting the .cmo files in an appropriate order from the programmer.

Would this be difficult to implement?
Perhaps this could be made a compiler switch?

Stephan
-- 
ir. Stephan H.M.J. Houben
tel. +31-40-2474358 / +31-40-2743497
e-mail: stephanh@win.tue.nl

Re: Why does the order in the Makefile matter?

[Pierre Weis]

> On Sat, 28 Oct 2000, Pierre Weis wrote:
> 
> > Hence, when the entire program is made of multiple implementation
> > files, those files must be linked in any order that is compatible with
> > the static binding rule: no definition can be linked if it refers to
> > an identifier that is defined after the definition at hand.  In
> > addition, expressions to be computed must evidently appear in any
> > order compatible with the desired runtime behaviour.
> 
> I completely understand this point, and I agree that there are legal 
> Caml programs that have a different behavior depending on the order
> of the .cmo file linking. However, every program I write (and I suppose
> that's true for most of us) has an invariant behavior under all legal
> permutations of the .cmo files. Mostly because I only have 1 .ml file
> that actually does anything; the rest only contain side-effect-free
> definitions.

Hmm, no initializations ? For instance table allocations and
computations of default values are often considered side-effect free,
even if the initializations can perform some assignments.

Anyway what about identifiers redefinition ? Then the linking order
will influence the semantics (due to the binding of identifiers in
closures). Also, if there are more than one compatible linking order,
the compiler should prove that all those linking orders will lead to
the same semantics ?

> So it would be nice if the compiler itself could put the .cmo files
> in an order compatible with the static binding rule. This would
> remove the tedium of putting the .cmo files in an appropriate order
> from the programmer.

We can propose an external tool that will try to find for you some
order compatible with static binding if any, something similar to
ocamldep for module compilation dependancy. This existed in Caml Light
and was named ``lorder'':

lorder
------
  A tool to compute the dependencies between a set of .zo files
  and suggest a correct linking order.

> Would this be difficult to implement?

Have a look at the source code in the contrib directory of Caml Light:
you need some knowledge of the structure of .cmo files to extract the
name of the identifiers defined in here, then you just have to output
a depandancy graph and use the topological sort implemented in
contrib/tsort.ml

> Perhaps this could be made a compiler switch?

I think it would be a bad idea, since you just have to use the tool
once and forall (or from time to time in case of linking failure). As
for ocamldep, you should have to run it outside the compiler (even if
this is done automatically by a Makefile entry).

> Stephan
> -- 
> ir. Stephan H.M.J. Houben
> tel. +31-40-2474358 / +31-40-2743497
> e-mail: stephanh@win.tue.nl

Pierre Weis

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

Re: Why does the order in the Makefile matter?

[Judicael Courant]

Pierre Weis a écrit :
> > So it would be nice if the compiler itself could put the .cmo files
> > in an order compatible with the static binding rule. This would
> > remove the tedium of putting the .cmo files in an appropriate order
> > from the programmer.
> 
> We can propose an external tool that will try to find for you some
> order compatible with static binding if any, something similar to
> ocamldep for module compilation dependancy. This existed in Caml Light
> and was named ``lorder'':
> 
> lorder
> ------
>   A tool to compute the dependencies between a set of .zo files
>   and suggest a correct linking order.
> 
> > Would this be difficult to implement?
> 

It is quite easy to implement in bash, using sed and the tsort Unix
utility (in the code of xxargs, you may notice that bash supports
higher-order functions!). I have already done it (*).
Here are the functions you need:

-------------------------------------------------------------
# general-purpose function
# xxargs f reads lines on its standard input an applies f to each
# of them, in order
# ignores the last line if it does not end with a newline
xxargs ()
{
local F
local ARGS
F=$1
while read ARGS
do
 $F $ARGS
done
}


# takes a list of dependency with form
# f f1 ... fn
# meaning f depends on f1 and ... and fn
# and outputs a list within tsort format
format ()
{
read f l
while [ "$f" != "" ]
do
 set -- $l
 while [ "$1" != "" ]
 do
 echo $1 $f
 shift
 done
read f l
done
}

# tidy the input: if a line begins
# with a .cmi or .cmx, we ignore it, since we want to know the
# relations between .cmo files (in order to link).
# otherwise, delete the ":", and change .cmi into .cmo in order to
# have the "must be linked before" relation (if the corresponding .mli
file
# has no associated .ml file, this can introduce fake .cmo files)
# files, that is, files t) 
# Moreover, we delete the prefix "./" in filenames
tidy ()
{
case "$1" in
*.cmo:) echo "$@" | sed -e "s/://g" -e "s/.cmi/.cmo/g" -e "s|\./||g";;
*) ;;
esac
}

# removes .cmo that would not have a corresponding .ml
tidyout ()
{
local BASE
local DIR
BASE=`basename $1 .cmo`
DIR=`dirname $1`
if [ -f "$DIR/$BASE.ml" ]
then
echo "$1"
fi
}

# takes a list of dependencies in ocamldep format and outputs
# the topologically sorted list of .cmo
# typical usage:
# ocamldep -I foo foo/*.ml foo/*.mli *.ml .mli | order
# or: cat .depend
order ()
{
xxargs tidy | format | tsort | xxargs tidyout
}
-------------------------------------------------------------


Enjoy!

Judicaël Courant.

(*) When I wrote this, my aim was to have a script to automagically
check that the code of my students' would compile and do some automated
tests over it. For security reasons (the students would submit through
an anonymous web form), I did not want to do just a "make all". So I
wrote a script that just did the necessary job. The above functions are
part of the script. More about this if anybody is interested.

-- 
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/
(+33) (0)1 69 15 64 85
"Montre moi des morceaux de ton monde, et je te montrerai le mien"
Tim, matricule #929, condamné à mort.
http://rozenn.picard.free.fr/tim.html