"Yannick Duch�ne (Hibou57)" <yannick_duchene@yahoo.fr> wrote in message 
news:op.v2u8hzeyule2fv@index.ici...
>e Wed, 05 Oct 2011 07:13:16 +0200, Niklas Holsti 
><niklas.holsti@tidorum.invalid> a �crit:
>> Doesn't Ada have a similar theoretical problem with the elaboration 
>> order? I seem to remember that finding a valid elaboration order for an 
>> arbitrary Ada program is rather difficult, in general, and compilers are 
>> allowed to give up on it.
>I am not aware enough of the techniques used there, and not a compiler 
>implementor, but I guess this is a divide-and-conquer strategy. I suppose 
>this end to be solving a graph route problem, not a Turing complete 
>language interpretation.
>
>You raised a good question anyway, I'm curious to know (may be an answer 
>in some GNAT design papers, or some answers from Randy).

I implemented that a long, long time ago, and haven't had to fix anything in 
it in a long time, so my memory may be wrong, but here's a short 
explanation:

Janus/Ada uses a trial-and-error approach. I figured this was only run once 
per program, and the number of units involved is usually not that large, so 
a quadratic algorithm isn't a problem.

Essentially, the algorithm checks the entire list of units (parts, spec and 
bodies are different), with all of the dependencies included, for one all of 
whose dependencies are already elaborated. As soon as it finds one, it 
elaborates that, and then starts over from the beginning. If at any point, 
there is no such unit available, it then gives up trying and produces an 
error message (the program must not have any consistent elaboration order).

The algorithm is complicated by needing to elaborate pure/preelaborated 
units first, by attempting to keep specs and bodies together when possible, 
and by elaboration pragmas. These are resolved by having various "soft" 
dependencies; if no unit can be found that do not violate any of the 
dependencies, the algorithm tries again looking for units that have all of 
their hard dependencies loaded.

I don't know of any real problem with elaboration given the Ada rules; the 
usual problem comes when someone tries to change those rules from dynamic to 
static rules (as GNAT does). Janus/Ada doesn't attempt that.

                                 Randy.