Orderly Conduct

In the preceding post, we looked at all the various problems that make initializing all the "global state" of a program particularly tricky.  In essence, packages have to be initialized ("elaborated") before they can be accessed, but doing so may access code or data in other packages, which obviously have to be done prior.  The compiler can't do it all for you, so you have to work together to ensure you select an order that works.

Luckily, figuring all this out is not altogether difficult (or, at least, doesn't have to be).  Earlier we saw all the reasons why the compiler couldn't do this itself; it basically boiled down to lots of esoteric edge cases that could happen, but which don't often happen.  But since the LRM can't just decide to ignore the inconvenient edge cases, we are all stuck having to deal with the fallout, even for problems we never encounter.

But what if we had some mechanism to indicate to the compiler that our program didn't go in for any of these mutually recursive elaboration time dependency shenanigans?  By promising the compiler that all those complex edge cases can't occur in our code (and, of course, letting to compiler reject our code if we try), all the problems we spent so much time discussing suddenly vanish.

And so the easiest way through the elaboration swamp is around it.  That is, subject our units to more rigorous and restrictive checks (that are acceptable most of the time), and nipping elaboration problems in the bud. Of course, there still has to be a way to get something correct if you do need to utilize the complicated edge cases, so Ada arms you (get it?) with an arsenal of pragmas to accomplish both.

At the most basic level, every package can be classified into one of two fundamental groups:

1. Units that don't contain any elaboration time code.
2. Units that do.

We saw from before that only select things actually cause dynamic, arbitrary code to be executed during elaboration, notably initialization of 'module level' objects via functions calls from other units (there are of course others, but we restrict ourselves to objects for simplicity).  If a unit, for example, doesn't contain any module level objects at all, then there can't be any elaboration problems since it's not actually elaborating any code.

Now if we have two of these units that each have no elaboration order dependencies, it's clear that we can elaborate them in any order we please.  If neither A nor B have global variables that reference each other for their initialization, then I can just flip a coin when it comes time to pick which package goes first, because there's nothing in either that can fail.

Furthermore, if I take a third unit without any elaboration dependencies and add it into the mix, I again can pick any order I want.  A-B-C is just as good as C-B-A, as is any of the other permutations, since none of these units have any elaboration code that could fail.  Following this line of thought, given any 'N' number of units, none of which have any constructs that might cause access before elaboration, I can elaborate them in any order I please.

These types of units are classified in Ada as the surprisingly difficult to pronounce name preelaborable (pre-e-lab-or-a-bull).  Any unit that abides by a few select restrictions (e.g. global variables initialized from function calls) can be marked as being preelaborable, which places it squarely into the first group of units and essentially informs the compiler that the unit has zero elaboration time dependencies.  Consequently, the compiler forces all these units to the front of the elaboration line, and effectively 'flips a coin' as to what order they get done within that group, since they can never fail, and can even avoid having to check that they didn't.

As a general rule of thumb, there's rarely a good reason why your unit shouldn't be preelaborable.  The list of restrictions is actually fairly short:

1. No package body initialization portion
2. No module-level objects initialized from functions (or by default)
3. Preelaborable units can only depend on other Preelaborable units.

And that's about it.  There are of course exceptions and caveats to these rules, and you can read about them in the LRM if you feel so inclined, but there's a very good chance that so long as you are following basic programming etiquette (i.e. packages provides types and operations that act on those types), most of your units should abide by these rules already.  That being the case, you can mark all your units with the preelaborate pragma and call it a day, confident that your program can never fail to start.

Before moving onto the next group of units, there are two other pragmas associated with preelaborable units that are worth discussing: Preelaborable_Initialization and Pure.

The first concerns private types.  We said before that one of the rules is that an object can't be "dynamically" initialized (no function calls, no other objects, no default initialization, etc); for example, if some module-level object was a controlled type, then its default initialization (or that of any of its components) would call its Initialize procedure, which puts us right back into the realm of arbitrary elaboration time code.  On the other hand, if a record is just a bunch of integers or other discrete types, then just leaving it uninitialized doesn't cause any harm.

But if our record type is private, we are in trouble; we can't see if that record is a controlled type (or perhaps contains other controlled types), or if it's just full of integers, or for that matter even if it's a null record with nothing.  We can't assume anything about a private type, so we must assume the worst.  We would have to assume that any private type is potentially trouble, and thus prohibit any preelaborable unit from having an uninitialized object of a private type.

But this is aggravating, since much of the time records are just discrete types with no elaboration concerns.  So to help mitigate this, the Preelaborable_Initialization pragma is available to allow a package to specify that the default initialization of private type does not have elaboration order concerns (this is in contrast to most other elaboration pragmas, which apply to packages as a whole).  With this applied, other units can have uninitialized objects of the private type and still stay preelaborable.

The second pragma, Pure, imposes all the same restrictions as Preelaborate, plus several more; call it preelaborate on steroids.  A pure unit has absolutely no saved state, which is important because it means that the procedures it contains are "true" functions (in the mathematical sense); i.e. the same inputs always supply the same exact outputs.  From an elaboration standpoint there's no difference, but it does allow the compiler to make certain important optimizations it couldn't otherwise.  For instance, if a 'sine' function is declared in a Pure package, the compiler knows that sin(0) will always be zero, no other side effects could occur, and thus cache the result for reuse.  Otherwise, it has to assume that the function might do something nefarious (print to the screen, log to a file, etc), and make the same call every time.

In any case, take together, these three pragmas create a closed group of preelaborable units, none of which have any elaboration order concerns, and all which depend only on other units in the group.  The compiler can go through and elaborate them all first in whatever way it wants, and even forgo the check to ensure it's correct.

But what about units that don't meet the criteria of being preelaborable?

What if, like before, we want to initialize a object in the body of 'A' to a value returned by a function in 'B'?  We are not preelaborable, but then again we aren't doing anything particularly egregious.  In this case, our previously hypothesized "tweak" of the LRM, that is to elaborate the spec directly before it's body, instead of just some point before its body, would be completely acceptable.  B's spec would have to come before A's body (because of the with clause), but we would also have to do B's body directly after B's spec (for an order of <B> [B] [A]), and all is well.

Ada actually has a pragma that essentially achieves this, but on a package-by-package basis: Elaborate_Body.  When applied to a package, the compiler ensures that the body of a unit is evaluated directly after the spec, without anything else in-between.  Applying this to packages gives you a nice, neat, orderly elaboration of a body right after its spec, so you can be confident that if you 'with' in a package marked as elaborate body, its body will be there when your package is elaborated.

All this leads to the general "rule of thumb" specified in the Ada 95 Rationale (et al): All packages should be marked as either Pure, Preelaborate, or Elaborate_Body, in that order of preference.

These impose decreasing levels of restrictions on units, but also an increasing chance of elaboration problems.  However, for the vast majority of the time, supposing you don't do anything fancy, these three pragmas will give you what you need.

Which begs one last question: what if we do want to do something "fancy"?

Consider the following code:

package A is
  one : integer := 1;  -- no dependencies
  function X return integer;
end A:

with B;
package body A is

  three : integer := B.two + 1; -- dependency on <B>

  function X return integer is
  begin
    return three;
  end X;

end A;

with A;
package B is
  two: integer := A.one + 1;  -- dependency on <A>
  ...(other stuff to make a body legal)
end B;

package body B is
  four : integer := A.X + 1;
  ... 
end B;

Now we have big fun.  Note the following dependencies:

• The spec of A depends on nothing
• The spec of B depends on the spec of A (via 'one')
• The body of A depends the spec of B (via 'two')
• The body of B depends on the spec and body of A (via A.X)

Perhaps most surprising is that this obviously convoluted code is, in fact, legal.  But we have a problem, because there is only a single elaboration order that will work:

<A> - <B> - [A] - [B]

That is, we need 'one' to exist so we can create 'two', which has to exist so we can make 'three', which has to exist so we can return it from A.X to create 'four'.

But none of our rules of thumb work for this.  We are clearly not preelaborate, but we also can't elaborate the bodies directly after the spec!  Now we have the dreaded edge case: multiple legal elaboration orders, not all of which are correct, that we must specify by hand.  To do so, we have two more pragmas:

Elaborate
Elaborate_All

Unlike the previous pragmas, which the programmer applied to the package he was creating, these pragmas are put amongst the with statements to apply to units he's referencing.  They ensure that the unit called out in the pragma is elaborated before the current unit, such as:

with A;
pragma Elaborate(A);
package body B is....

This instructs the compiler that it must select an order in which the body of A is elaborated before the current unit (B).  Given that small addition, the compiler now has the additional requirement that [A] must come before [B], which along with the original rules gives us a legal (albeit strange) program. (Note that in the above example, you would have to add another seemingly redundant with clause to [B]).

But from a practical standpoint, this is tougher than it looks.  Sure, we can go through and add Elaborate pragmas everywhere, but most real code is far more complex and contains many more units.  What if, in the above, A.X called out to other units doing other things, which themselves called other things, and so on?  This has massive scalability problems.

We aim to put software together from reusable components, so often we can't change package A (i.e. it's a COTS library).  Plus, this violates our inherent sense of encapsulation, because we shouldn't need to peek into the body of A and start mucking with things based on what we see.  But there's not much we can do, since the person writing the body for A can't possibly know that sometime in the future, some errant unit B was going to call it's function at elaboration time, instead of at run time.  And what if A calls a procedure in C that calls something from D?  Must we open up every single unit in the entire call tree?

For these reasons, Ada95 added the "Elaborate_All" pragma, which is essentially a recursive form of Elaborate; instead of just elaborating the body of the unit you specify, it elaborates that unit and all the bodies of units on which it depends, all the way down.  Now the package you depend on is a true "black box", and you can be assured that your single pragma in the client will make the entire subsystem available  (in most cases, Elaborate_All is the better choice than Elaborate, which is for the most part obsolete).

Though just because Ada has this ability doesn't necessarily mean you should utilize it.  Of course there are situations where this is desired, if not necessary, but for the most part, adding Elaborate_All pragmas is a sign of bad design.  Avoid the problem altogether and redesign the code such that your packages are Preelaborate (or at least Elaborate_Body).

But at the same time, don't just rely on GNAT's static checking crutch.  Take elaboration into account as you write the code, not simply because it's the right thing to do or because your code will get better, but because most of the time you won't find the problems until it's far too late.  Do you really want to go back and add 500 pragmas to 500 packages since it didn't occur to Joe the C Programmer that this would ever be a problem?  And before you let Joe the C Programmer slander Ada for requiring such pedantic verbosity in the first place, go and Google "static initialization order fiasco"; C++ has the same problem as Ada, except it's so problematic and unsolvable that it's even got its own cute name containing the word fiasco!

So go forth, enlightened one, and banish elaboration circularities and access elaboration exceptions back from whence they came!  Every time your program starts, a slight smile should creep to your lips, since now you know it's no accident how it happened.

Elaboration Station

One of the great niceties of programming is that, fundamentally, programs execute one statement at a time, plodding along in a nice, neat, well-defined order.  It begins at the first instruction and ends at the last, and nothing out of the ordinary (threads and interrupts notwithstanding) messes that up.

Well, almost nothing.  Programs have but a single entry point, but most languages, Ada included, have the ability to declare objects at a scope just above the main subprogram.  We normally call these global variables, or library-level objects, or module level objects, or by whatever other name your particular flavor of language calls them.  But by any name, these objects get created before the main program starts, and live (just) past where the program ends.

(Note: I will talk exclusively about initializing 'global' variables in regular units, regardless of whether they are in the spec or a body.  As always, this is an over-simplification, and ignores things like child/parent packages, and other elaboration time code like library level tasks or packages containing initialization code.  However, the rules are essentially the same).

This opens up an interesting loophole in the "start at the beginning" philosophy, because this means there are actually TWO beginnings to any program.  The program has to go through and initialize all these global variables to whatever their initial values are supposed to be, before the main function begins in earnest, so that when it comes time for the 'real' beginning, everything is as it ought to be.

But in any modestly complex language, this is a much more subtle and difficult problem than at first it may appear.  Usually we just initialize constants to values, such as "pi : constant Float := 3.14", and there are no particular concerns, or for that matter anything that the program actually has to do at runtime (the compiler can normally handle these sort of static objects itself as a hardcoded variable in the file).  But, as always, general purpose languages have general purpose problems.

We have to consider the unpleasant fact that these global objects can also be initialized from other expressions apart from numeric literals; particularly, we might initialize them from other objects in other packages, or from the results of function calls (among others). For example:

package X is

  R : constant Float := P1.Calculate_Radius;

  C : constant Float := 2*P2.pi*R;

end X;

Here, we initialize R from the result of a function in another package (P1), and then initialize C via a calculation using both the previous object R and our declaration of pi in a third package (P2).  We can quickly see this start to spiral out of control, because what can be said about the Calculate_Radius subprogram?  It might execute any arbitrary code at all, perhaps prompting the user for a value, or communicating with a satellite to retrieve a value from the Mars rover.  In general, we might execute any code at all.

The issue at hand is that we've got all these packages with all these objects that need initialization, and no good way to figure out the order in which to do it.  For instance, in the above example, we need to ensure that P2 (with the 'pi' constant) is initialized before we try and use it to calculate C (or else the program is nonsense).  Of course, if the calculation of pi depends on some other unit, we have to do that unit before P1, before X, and so on and so on.

To help untangle this mess of "elaboration order", Ada has basically two rules governing the order in which the compiler should go through and initialize all the units:

1. A package spec must be initialized before its corresponding package body.
2. The package spec of any 'withed' unit must be initialized before the unit that 'withs' them.

But the perhaps unexpected thing about these rules is not just that you end up with several different potential elaboration orders, but that not all of them are necessarily correct.  To account for this, Ada also mandates that if the order the compiler selects is wrong, an exception should be raised when you start the program and stop things dead in their tracks.

This raises two interesting questions.  First, why don't we have rules that make sure the order is correct in the first place, and second, why do we get a run-time exception instead of a compile-time failure?  After all, at first blush, these rules seem pretty good.  A global variable can't be initialized from anywhere except either something in its spec, which is gaurenteed to be there by rule #1, or another unit that is 'withed in', which is handled by rule #2.  So what gives?

If you go back and re-read rule #1 like a language lawyer, you might note a conspicuous omission.  It requires that a unit's spec must be initialized before its body, but not immediately before, only at some point before.  The compiler is allowed to try and elaborate any number of other units between a spec and its body, and this creates interesting loopholes.

For instance, suppose a global variable in the body of A is initialized to the result of a function declared in B.  Ada's built in rules require the following:

1. <A> is elaborated before [A] (rule 1)
2. <B> is elaborated before [B] (rule 1)
3. <B> is elaborated before [A] (rule 2)

 

Note that both the following orders are legal in accordance with our rules:

• <B> - <A> - [B] - [A]
• <A> - <B> - [A] - [B]

but the latter one would result in the dreaded "access before elaboration".  We initialize the body of A, including the global variable, which executes code from [B] which has NOT been initialized yet, and we have a flawed program with undefined values.  In the first one, however, [A] is not initialized until after [B], and everything is acceptable.

Why then can't we just tweak the LRM to specify that a body should be elaborated DIRECTLY after its spec?  It would appear that such a modification would be a good thing, since it would narrow down our choices to just a single, correct order:

• <B> - [B] - <A> - [A]

The problem is that, like we said before, general-purpose languages have general-purpose problems.  Such a modification would be far too restrictive, since it would impose a strict hierarchical structure for a program.  We could not, for instance, have two mutually recursive functions in different packages, or have finite state machines, or many other interesting and fun software solutions that involve code in two different packages calling each other at elaboration time.

If we were to add such a 'direct' elaboration rule, these case examples would become illegal, despite not having any elaboration problems.  Consequently, we have to leave some bit of ambiguity to the order so that legal albeit niche programs are still possible.

But while this answers the question of why the LRM cannot specify rules that work for every program in every situation, it doesn't really answer why they can't put the onus on the compiler to find an order that works on a program-by-program basis.  The compiler has to analyze the source code, right?  Why can't we program it to be smart enough to check for elaboration dependencies as it goes, to narrow down the potential list to one that's correct?

For example, let's take the same example from above.  The compiler identifies the global variable in the body of [A], identifies it as being initialized from a call to <B>, and can in theory prune down the list of potential elaboration orders so that only those with [B] ahead of [A] are acceptable.  If we have some sort of untenable situation, such as a global variable in both [A] and [B] that are initialized from functions in <B> and <A> respectively, then we can spit out an error indicating that no correct order is ever possible, and thus prevent bad programs from ever being ran at all.

Again, at first glance this seems like an acceptable rule and in fact early drafts of Ada actually did require these sorts of checks.  But at the risk of repeating myself, general purpose languages have general purpose problems.  Don't forget, *we can run any arbitrary code* during elaboration, and nothing says that code has to work the same way every time.  It can have any manner of if/else blocks, which means the behavior (and success or failure) of the initialization can be drastically different.

Suppose we write the following function, which perhaps questionably puts the code for gladly paying people Tuesday for hamburgers today into the calculation of how many hamburgers liabilities we currently have:

function Hamburger_Debt return Integer is

begin

  if Day_Of_Week = Tuesday then

     Hamburger_Database.Glady_Pay_All_Lendors

     return 0;

  else

     return Current_Liabilities.Hamburgers;

  end if;

   

end Hamburger_Debt;

 

For or better or worse, this code is legal.  But if somewhere in another unit we have a global constant (perhaps "Starting_Hamburger_Debt") initialized to the return value of this function, this function gets executed during elaboration time, and real fun begins.

Now we are in real trouble, because the elaboration now depends on what day of the week it is when we start the program.  The compiler needs to elaborate the Hamburger_Database prior to whatever unit our function is in, but only on tuesdays.  On any other day of the week, we don't touch the hamburger database and have no care as to when it's elaborated, but in that case we need to ensure the Current_Liabilities package is elaborated prior.  The required elaboration order changes based on the date, which we obviously can't know until we run the program!

Alright, perhaps you argue the compiler should take a "worst case" approach, and say that any unit referenced at all, regardless of any control transfers, should be considered as a potential elaboration issue, and we should sort things out like that.  But then what do we do with something like this:

function F return Integer is

begin

  if false then

    return P2.X;

  else

    return 0;

  end if;

end F;

 

Obviously this is dead code and no elaboration order problem possibly exists (in fact, this entire subprogram can be optimized away).  But we just said the compiler should not perform this type of exhaustive analysis!  Should this code, statically known to be free of any elaboration order problems, potentially fail to compile because of a non-existent elaboration problem?

So we can see that trying to statically prove something that's inherently dynamic is a slippery slope.  The 'correctness' of a particular elaboration order can only be determined by somehow knowing the outcome of every if statement, which even in the best case means exhaustively testing all the possible combinations of states, and even then dynamically choosing how to elaborate packages as decisions are made.  Clearly this is hard, not just in the algorithmic sense but certainly in the programming sense, and it's unlikely any compiler could ever hope to implement it (and still have programs compile before the sun burns out).  We must either be overly strict and reject legal code (as is the case with accessibility), or be dynamic and account for the possibility of runtime failures (as with elaboration).

And so, at the end of the day, the compiler has no other recourse than to simply dump the responsibility of elaboration order on the programmer, but then double check at runtime that the order was sufficient (e.g. tracking the initialization state of each package, and verifying it has been set prior to access).  Various pragmas exist to let the programmer try to solve their own unsolvable problems, which perhaps we'll see in a future post.

But wait, there's more: GNAT stirs up the already murky water by deviating from the LRM-specified behavior by actually attempting to statically prove the correctness at the expense of being overly pessimistic.  The default behavior of the binder is to take the 'worst case' approach detailed above, and try to analyze the code for constructs that cause elaboration time dependencies (e.g. global variables).  Should they be found, it takes up the slack for the programmer and ensures the "right" order is used.  But like we said, this means GNAT is "overly strict", and many valid Ada programs fail to compile in GNAT due to elaboration circularities.  I suppose they feel the trade off is one worth making (and, of course, switches exist to enforce the less-strict Ada rules).

Like most non-standard GNAT behavior, this is both a blessing and a curse.  On the plus side, it means that the program can be proven, statically, to not fail the elaboration check, which means the check is obviously unnecessary.  No chance of failure and faster startup times are a good thing.

But at the same time, it also means your program is not necessarily portable between compilers, or for that matter even between versions of GNAT (their static checker gets better each time around, so dubious situations marked 'safe' in one version might suddenly no longer compile).  More importantly, though, it makes us all dumber.  Many programmers go their entire career without ever realizing elaboration is a thing or considering how it might fail, let alone inserting the appropriate pragmas and in some (rare) cases, actually making a concerted effort to take them out (true story).

      

Moreover, apart from being good at your job just for the sake of it, worrying about elaboration dependencies makes you code better.  It's not a coincidence that most of my outlier problem-causing examples seem convoluted; code is cleaner and better when these sorts of dependencies don't exist in the first place (Text_IO, I'm looking in your direction!).  Having to deal with them is the best incentive to restructure your code so that you don't have to deal with them, and GNAT is making us all lazy by cleaning up our mess.

So that's the problem; but what's the solution? To be continued...