On the surface, access values in Ada are pretty straightforward stuff:
A value of an access type provides indirect access to the object or subprogram it designates (LRM 3.10/1).
All variables are stored in RAM and every byte of RAM has an address, so, like most languages, Ada lets us store the address of one variable in another variable. This is colloquially known as a pointer, often the bane of many a collegiate freshman and professional programmer alike. Pointers are notoriously prone to human error, given their multiple levels of indirection, low-level nature, and all-to-often habit of trying to address values in memory that no longer exist.
So back in 1983, Ada made it a point to avoid all this pointer-fussing business. In fact, Ada83 didn't have pointers, as a C programmer might understand them. C has the "address operator" (&), which can be liberally applied to any object or subprogram, which resolves into the address at which it is stored. Ada, on the other hand, had been designed to eliminate many of these unnecessary uses of pointers, most notably arrays and pass-by-reference semantics. Pointers were therefore seen as mostly superfluous, except for the case of heap allocations, which cannot be implemented any other way. Consequently, the only way to create a pointer (or 'access value' in the Ada parlance) was through a heap allocation (i.e. 'new').
This also circumvented those thorny lifetime problems, also known as dangling pointers. An object only exists for the time it is "in scope". A variable local to a subprogram (or a nested package) is only valid for the time the subprogram is executing, after which said variable ceases to exist. In the canonical example, a subprogram saves the address of a local variable into a global pointer, which is then accessed after the subprogram ends, with unpleasant results. This is particularly hard to diagnose, since there is no indication anything is wrong until the object is overwritten, which may not even happen unless the conditions are right. A heap allocation, on the other hand, is there forever and always, unless specifically deallocated (which, in Ada, is always unchecked).
But as well-intentioned as the 'no pointer' philosophy was, this was found to limiting. Ada95 therefore added the ability to generate access values to locally declared objects via the 'Access attribute (and its counterpart, 'Unchecked_Access). However, dangling pointers were of course still undesirable, and it was decided that rules should be in place to prevent these from occurring.
These rules, known as the accessibility rules, have arguably become the most complex, confusing, and contentious part of the entire language. Very little literature even addresses them, and few programmers even try to understand them. Many simply avoid the problem altogether by using the heap or the 'unchecked' mechanisms. Frankly, this is a shame, because the rules are just not that complex. There are many edge cases and esoteric constructs that can cause heap-spinning conundrums, but these are concerns for the ARG, and not the everyday programmer. Learning about how and why the accessibility rules exist can make your programmers much safer, more functional, less reliant on the heap, and guaranteed free of dangling pointers.
Lifetime is inherently dynamic in nature, and the only 'true' way to prevent dangling references is via a runtime check at every dereference. Such checks would be expensive both in size and speed, it is far more desirable to check for these statically, when compiling, rather than have to deal with an exception at runtime (which, as mentioned before, might not happen until the program is in the hands of the user). To this end, Ada takes a perhaps surprising approach to accessibility: it doesn't prevent dangling pointers, it prevents the creation of pointers that might ever dangle.
This is the key point to understanding the accessibility rules and leveraging them in your programs, so re-read it a few times until it sinks in. Ada prevents the creation of any pointer that might ever dangle, that even has the chance it might dangle at some point, even if it never does. Consequently, programmers are often at odds with the compiler, which staunchly refuses to accept completely safe code. We will have much more to say about the ramifications of this later, but for now let's look at how (and why) this works, and what we can do about it.
The crux of the problem is that once an access value is created, the compiler cannot be counted on to keep track of what happens to it. We could, in theory, ensure that an access value of a local object is not assigned into a global variable, but things are much more complex than just that. We might, for instance, assign the pointer to a local object (which is okay), but then try and assign that local object to a global object (which may or may not be okay). Furthermore, we might use an access value as a parameter to another subprogram, which might already be compiled and could clearly not be checked at all.
So, the one and only chance a compiler has at preventing a dangling reference is at the point it is created: that is, when the 'Access attribute is applied to an object. This is the one and only place the accessibility rules are checked (apart from a few special runtime cases discussed later). After the access value is (successfully) created, no more checks are performed, and that pointer can be safely passed around anywhere. How is it then, that a static check can gaurentee the behavior of the dynamic nature of lifetime?
The accessibility rules hinge on just one obvious programming rule: to declare an object of a certain type, you have to be able to 'see' that type. Ada is block-structured, which means that code at a 'higher' level cannot use declarations at a 'lower level'. For instance, a subprogram within a package can use types, objects, and subprograms declared in the enclosing package, but declarations within the package cannot access types, objects, and subprograms declared within its subprograms (they are 'local'). Since subprograms can be nested within subprograms, this extends all the up (and down) the hierarchy. For instance:
procedure P1 is
type T1 is ...;
x : T1 := ...;
procedure P2 is
y : T1 := x -- Legal! Can see T and x outside in P1
type T2 is ...;
z : T2 := ...;
begin
null;
end;
Bad : T2 := z; -- Error! Cannot see T2 or Z inside of P2
begin
null;
end;
Here we have declared a type T and an object x of type T locally within procedure P1, as well as another nested procedure P2. Within procedure P2, we can access the type T1 and object x, and for that matter anything else declared up in P1. However, we cannot "see into" P2 from P1 and use its local declarations. This makes intuitive sense, since the declarations within P2 don't conceptually exist unless P2 is executing (and cease to exist after it ends).
This is the key to the accessibility rules. Creating a dangling reference involves copying the pointer into an object that is longer lived (either directly with an assignment, or by passing it as a parameter to a subprogram that performs the assignment, which for our purposes is the same). However, declaring that object obviously requires a type which must be visible. Or, looking at it another way, if you can't see the type, you can't create the object.
This presents a nice, neat, logical trap: we can be absolutely certain that no objects of a given type exist outside of (i.e. higher than) the block where that type is defined. Revisiting the example above, the only objects of type T2 that can ever possibly exist are within P2 itself, or else within other procedures that are themselves within P2.
So, applying this to access values, we know that there can never be dangling pointers so long as the type of the access value being created is not declared outside of where the object is declared. There can be no object to copy the value into, since the declaration can not see the type! In the language of the LRM, the level of the object cannot be deeper than that of the access type. Let's see an example.
package K is
type Int_Ptr is access all Integer;
Global : Int_Ptr;
procedure P is
y : alaised Integer := 42;
y_ptr : Int_Ptr := y'Access; -- accessibility check failure
begin
null;
end P;
end K;
Applying the check to y'Access (which is, remember, the only place the check is applied), we see that the type of access value being created (Int_Ptr) is declared at a higher level than the object being accessed (y). This means objects (or subprograms having parameters) of that type can exist outside the procedure P (such as Global), and that the resulting pointer might, at some point, somewhere, be copied into it. Consequently, the creation of y_ptr is prohibited outright, even though in this particular case no dangling references are created. Remember, accessibility checks prevent creation of pointers that might dangle, and not necessarily ones that do.
Now let's see a version that works.
package K is
type Int_Ptr is access all Integer;
Global : Int_Ptr;
procedure P is
y : alaised Integer := 42;
type Local_Int_Ptr is access all Integer; -- new, local type
y_ptr : Local_Int_Ptr := y'Access; -- pass
begin
null;
end P;
Bad_Global : Local_Int_Ptr; -- error, no scope
procedure Bad_P (arg : Local_Int_Ptr); -- error, no scope.
end K;
This is the same example, except instead of declaring y_ptr as the higher-scoped Int_Ptr, we've created a new local type, Local_Int_Ptr. This time, when we apply the check, we find that the type (Local_Int_Ptr) is declared at the same level as the object (y). The compiler knows there can be no Local_Int_Ptr's declared up in K somewhere, since those declarations would be invalid. Trying to copy y_ptr into Global would fail, because they are, after all, two different types. Similarly, trying to pass y_ptr as a Int_Ptr parameter (or casting it to an Int_Ptr) would fail because of incompatible types. It's worth noting that these are regular old type check failures that have nothing to do with access values.
In fact, the only places we can ever have objects or subprogram parameters of Local_Int_Ptr is inside P (or within subprograms within P, or within subprograms within subprograms, etc). Try as we might, the existing type system and scoping rules will prevent y_ptr from ever being copied out of P, which can therefore never dangle. We can copy it around inside of P (and to any subprograms within P) as much as we like, and maintain certainty that it will never 'escape' out into K (or other subprograms directly within K).
So we can start to see the "assume-the-worst" philosophy that Ada takes towards access values. If it's possible that an access value could ever be copied out to a longer-lived object, then you are forbidden from ever creating that access value. The only way to work with access values to locally declared objects is to type them in such a way that ensures they can never be copied out of their local scope, no matter what.
And in many cases, this is all that's required: redeclare a new type (not a subtype) at the same level at which the objects are declared, which ensures that these access values can never escape. Of course, things are rarely this simple; in the upcoming posts, we will see the various problems that occur with this mechanism, and the various ways in which we can work around them.
No comments:
Post a Comment