Sunday, March 17, 2013
Ada access types, part IV
Thus far we've seen just about all of the "normal" uses of Ada95 general access types, which all boil down to basically two things: using subtypes to placate the compiler into ensuring local pointers cannot be copied out into the world, and using so-called 'anonymous' access discriminants and parameters to safely copy them out if required.
We've also seen two special circumstances where the static rules are insufficient for ensuring lifetime control and thus require runtime checks inserted by the compiler to keep you honest. The first was a function that returned an record containing access discriminants, since nothing in the syntax prevented you from returning a pointer to a local object. The second was an explicit typecast of an access parameter which, while valid, is dangerous and not recommended.
However, there is one final circumstance (in Ada95) that requires a runtime check, and while you are unlikely to stumble across this situation through normal everyday programming, it's important in all situations to know when your program can never fail, and when it might. This final circumstance involves generics.
Suppose we have two packages, where one passes the address of a 'global' object to the other, which saves it into a global pointer:
package P1 is
type Int_Ptr is access all Integer;
Global_Pointer : Int_Ptr;
procedure Save (Arg : Int_Ptr) is
begin
Global_Pointer := Arg;
end Save;
end P1;
package P2 is
Global_Object : aliased Integer := 42;
procedure Store is
begin
P1.Save (Arg => Global_Object'access); -- pass
end Store;
end P2;
By all accounts, this is safe code. The static check compares the lifetime of the object in question (Global_Object) with that of the access type being created (Int_Ptr), and finds they are both at the top-most library level. Obviously the object is going to be there until P2 is finalized, which is essentially the entire life of the program, so we can copy pointers to it wherever we please.
Now suppose we make P2 generic for some reason (the reason does not matter):
generic
type T is (<>);
package P2 is
Global_Object : aliased Integer := 42;
procedure Store is
begin
P1.Save (Arg => Global_Object'access);
end Store;
end P2;
This complicates matters greatly, since we don't know where the package is going to be instantiated. If we instantiate P2 as its own, stand-alone library package then the code is as before, Global_Object is a library-level object, and everything is hunky-dory. However, there is nothing stopping us from doing, say, this:
procedure P is
type Some_Type is range 0 .. 100;
package Dangly is new p2 (T => Some_Type );
begin
Dangly.Store;
end P;
Now the package is actually nested inside a procedure, so everything is one level deeper, including our previously "global" object. When P ends, our package ceases to exist along with the our now-no-longer-global object, and P1 contains a dangling pointer.
Checking for this is complicated further by the requirement of separate compilation for generic bodies. Some compilers implement the so-called "macro expansion" model, in which each instantiation basically recompiles the entire generic soup-to-nuts. An alternative model, 'shared generics', compiles the body once and then reuses the same code. In a shared generic model, there would no way to know during the compilation of the body where the instantiation would be, and therefore no way to know what the accessibility level of the object would be during the check. Indeed, we might instantiate this generic any number of places at any number of levels, so some might be safe while others might fail.
The only way out of this problem is to insert a runtime check that verifies the actual level of our 'global' object is not deeper than the pointer being created. If this check fails, like other checks, Program_Error is raised. Note that any worthy "macro expansion" compiler should note the inevitable accessibility violation (since it knows where the generic is instantiated) and report a warning (to its credit, GNAT 2012 correctly generates both the warning and the exception).
And this about does it for the wild and wacky ways that Ada95 deals with general access types. One static check, access parameters, access discriminants, and three runtime checks (as needed). Correct and judicious use of them can only make your programs safer and better.
Friday, March 15, 2013
Ada access types, part III
Thus far we've seen how accessibility rules "imprison" a local pointer at the scope in which it was declared, but how access parameters and access discriminants provide a safe mechanism for passing them around when needed. But there is trouble in paradise, and it involves a brief side trip into a seemingly unrelated topic: OOP.
(It should be noted that this post is mostly my own opinions, moreso than usual. I was obviously not there when they designed the language, nor do I know all the reasons for the design that was chosen. In fact, much of the 'why' below is different than the 'official why', so please make your own judgements and take everything with a grain of salt. Or ask your friendly neighborhood ARG member.)
Aside from general access types (and many other things), Ada95 also added support for so-called "object-oriented programming". I can't possibly go into all the details, suffice to say that it is a programming model that relies on dynamic dispatching to select the correct subprogram at runtime, thus making programs much less brittle.
For example, suppose we want to create an abstract "file stream" parent, that allows us to read a single byte from a file. This will be implemented by two child types, Normal_File and ZIP_File, where the former will simply read bytes from disk as expected, but the latter will do the messy work of decompressing the bytes 'on the fly'. The first one will likely be quite simple (and just ferry calls to whatever the underlying disk is), whereas the second will be much more complicated, involving all manner of caching, maintaining file pointers, and so on. We might establish our types like so:
type File is abstract tagged null record.
function Read (This : in out File) return Byte;
But right off the bat, we find an issue: functions cannot have out parameters. It's an almost certainty that the ZIP_File will need to modify its own state during a read, since it will likely have to decompress a large chunk of data, and then return each byte from inside the cache. But by being restricted to 'in' parameters, this is a non-starter.
Before Ada2012 solved the problem once and for all, there were two main workarounds to this problem. The first, which was so widely used that it still exists in almost all Ada code, is to replace the function with a procedure and use an 'out' parameter, like so:
procedure Read(This : in out File, That : out Byte);
Of course this is not a general solution, since there are cases where only a return value will do (unconstrained arrays, discriminated records, etc). The other method is, of course, to use an access value. The only requirement is that the parameter itself not be updated, so we can modify anything we wish simply by adding an '.all'. That means our function now looks like so:
function Read (This : File_Ptr) return Byte;
But while this is a step forward, it's also two steps back. Remember that dynamic dispatching only happens for object types, not access types. Read is no longer a dispatching primitive operation, which was the whole point to begin with!
And you can't call your language "object oriented" if, in a practical sense, you can only have dispatching on your procedures. You can't just add named access values to the list of primitive operations either, since it would be a nightmare deciphering what overrides what (not to mention restrict you from using those fancy new general access types). So as a kludge to the kludge, access parameters were added to the list of primitive operations, since they have the nice property of being able to accept any named type. They said this was a "convenience" to avoid having to write '.all' at every place, since OOP is pointer heavy, but I don't buy that. This was just a way to save face and avoid admitting fault vis a vis function out parameters. But for whatever the reason, dispatching could now occur for access types, so long as the function was declared with an access parameter:
function Read (This : access File) return Byte;
Of course, this has nothing to do with the original intent of the access parameter (for accessibility control), and everything to do with getting yourself an 'out' parameter for a function. If you peruse some Ada95-style "OOP" frameworks (e.g. GtkAda), you will find a rash of access parameters used in this manner. Again, it's about dispatching, not accessibility.
But again, this created more problems than it solved. Access parameters allowed you to get the needed dispatching, but you were also forced to take an anonymous access type. Remember, all the same accessibility rules from the previous post still apply, whether you want them or not. That means within the function body, there is no copying of the 'This' pointer to anywhere, or passing it to other subprograms. It's imprisoned just the same, like it or not.
This puts you in a bind if you actually want to copy the pointer (and obviously do your work on the heap to avoid dangling references). Suppose some fancy version of the Read subprogram is done so that if a certain byte-sequence is read, it inserts itself onto a linked list somewhere, or registers itself as an observer, or some other pattern that involves saving an access value. Now you are stuck, since your Faustian bargain signed away any possibility of copying the object to gain dispatching ability.
So, as a kludge to the kludge to the kludge, Ada95 put in a loophole so that you could "get your type back" after being forced to cast it aside.for dispatching: access parameters can be typecasted. Doing so, however, incurs a runtime check that raises an exception if the accessibility rules are violated (i.e. if the actual pointer in question was a local, and you saved it off somewhere longer lived).
The bottom line, however, is just don't do this. There were only isolated cases in Ada95 and Ada2005 where this would have been necessary, and Ada2012 solved the problem once and for all by adding out parameters for functions. There is no reason to ever try and cast an access parameter, and you are foolish to try. If you need to copy a pointer, use a named access type (actually, you are even more foolish to to use a named access type anywhere in a public interface, but that's another post). Moreover, there is no reason to even dispatch on an access value anymore, so start converting your OOP frameworks to use nothing but normal types. In fact, as we will see later, Ada has evolved to a point where even the use of access parameters in the 'normal' sense (i.e. accessibility) is mostly antiquated.
So that's a lot of history about a feature that was bad to begin with and should never be used. But it's just as important, if not moreso, to know how not to use the language; especially when it's confusing and misleading in the first place.
(It should be noted that this post is mostly my own opinions, moreso than usual. I was obviously not there when they designed the language, nor do I know all the reasons for the design that was chosen. In fact, much of the 'why' below is different than the 'official why', so please make your own judgements and take everything with a grain of salt. Or ask your friendly neighborhood ARG member.)
Aside from general access types (and many other things), Ada95 also added support for so-called "object-oriented programming". I can't possibly go into all the details, suffice to say that it is a programming model that relies on dynamic dispatching to select the correct subprogram at runtime, thus making programs much less brittle.
For example, suppose we want to create an abstract "file stream" parent, that allows us to read a single byte from a file. This will be implemented by two child types, Normal_File and ZIP_File, where the former will simply read bytes from disk as expected, but the latter will do the messy work of decompressing the bytes 'on the fly'. The first one will likely be quite simple (and just ferry calls to whatever the underlying disk is), whereas the second will be much more complicated, involving all manner of caching, maintaining file pointers, and so on. We might establish our types like so:
type File is abstract tagged null record.
function Read (This : in out File) return Byte;
But right off the bat, we find an issue: functions cannot have out parameters. It's an almost certainty that the ZIP_File will need to modify its own state during a read, since it will likely have to decompress a large chunk of data, and then return each byte from inside the cache. But by being restricted to 'in' parameters, this is a non-starter.
Before Ada2012 solved the problem once and for all, there were two main workarounds to this problem. The first, which was so widely used that it still exists in almost all Ada code, is to replace the function with a procedure and use an 'out' parameter, like so:
procedure Read(This : in out File, That : out Byte);
Of course this is not a general solution, since there are cases where only a return value will do (unconstrained arrays, discriminated records, etc). The other method is, of course, to use an access value. The only requirement is that the parameter itself not be updated, so we can modify anything we wish simply by adding an '.all'. That means our function now looks like so:
function Read (This : File_Ptr) return Byte;
But while this is a step forward, it's also two steps back. Remember that dynamic dispatching only happens for object types, not access types. Read is no longer a dispatching primitive operation, which was the whole point to begin with!
And you can't call your language "object oriented" if, in a practical sense, you can only have dispatching on your procedures. You can't just add named access values to the list of primitive operations either, since it would be a nightmare deciphering what overrides what (not to mention restrict you from using those fancy new general access types). So as a kludge to the kludge, access parameters were added to the list of primitive operations, since they have the nice property of being able to accept any named type. They said this was a "convenience" to avoid having to write '.all' at every place, since OOP is pointer heavy, but I don't buy that. This was just a way to save face and avoid admitting fault vis a vis function out parameters. But for whatever the reason, dispatching could now occur for access types, so long as the function was declared with an access parameter:
function Read (This : access File) return Byte;
Of course, this has nothing to do with the original intent of the access parameter (for accessibility control), and everything to do with getting yourself an 'out' parameter for a function. If you peruse some Ada95-style "OOP" frameworks (e.g. GtkAda), you will find a rash of access parameters used in this manner. Again, it's about dispatching, not accessibility.
But again, this created more problems than it solved. Access parameters allowed you to get the needed dispatching, but you were also forced to take an anonymous access type. Remember, all the same accessibility rules from the previous post still apply, whether you want them or not. That means within the function body, there is no copying of the 'This' pointer to anywhere, or passing it to other subprograms. It's imprisoned just the same, like it or not.
This puts you in a bind if you actually want to copy the pointer (and obviously do your work on the heap to avoid dangling references). Suppose some fancy version of the Read subprogram is done so that if a certain byte-sequence is read, it inserts itself onto a linked list somewhere, or registers itself as an observer, or some other pattern that involves saving an access value. Now you are stuck, since your Faustian bargain signed away any possibility of copying the object to gain dispatching ability.
So, as a kludge to the kludge to the kludge, Ada95 put in a loophole so that you could "get your type back" after being forced to cast it aside.for dispatching: access parameters can be typecasted. Doing so, however, incurs a runtime check that raises an exception if the accessibility rules are violated (i.e. if the actual pointer in question was a local, and you saved it off somewhere longer lived).
The bottom line, however, is just don't do this. There were only isolated cases in Ada95 and Ada2005 where this would have been necessary, and Ada2012 solved the problem once and for all by adding out parameters for functions. There is no reason to ever try and cast an access parameter, and you are foolish to try. If you need to copy a pointer, use a named access type (actually, you are even more foolish to to use a named access type anywhere in a public interface, but that's another post). Moreover, there is no reason to even dispatch on an access value anymore, so start converting your OOP frameworks to use nothing but normal types. In fact, as we will see later, Ada has evolved to a point where even the use of access parameters in the 'normal' sense (i.e. accessibility) is mostly antiquated.
So that's a lot of history about a feature that was bad to begin with and should never be used. But it's just as important, if not moreso, to know how not to use the language; especially when it's confusing and misleading in the first place.
Thursday, March 14, 2013
Ada access types, part II
In the previous part, we took a look at the accessibility rules that Ada implements for access values, specifically local ones, to prevent the so-called 'dangling reference' problem. The main point was that, for better or worse, these rules are mostly static and checked at compile-time. The trade-off we all make for that particular benefit is that the rules are in many cases overly strict. As mentioned several times, Ada restricts you from creating a pointer to any value that might potentially ever become a dangling reference, even if your code is written in a way where it does not.
As demonstrated earlier, the only way you can create a local access value is to organize your types so that the access type can't exist for longer than the object (i.e. if there is no longer-lived object to copy the value into, then there can be no dangling reference). By declaring the access value as a shorter-lived type, we 'imprison' it locally to the scope in which it was created.
But this isn't the end of the story. Imprisoning an access value within a procedure is often of very little value in a large, complex program. More often is the case that we must pass the pointer out to another subprogram (usually one not under our control), which presents a catch-22. Consider the following example:
package K
type Int_Ptr is access all Integer;
procedure Q (arg : Int_Ptr) is
begin
Ada.Text_IO.Put_Line(Integer'Image(arg.all));
end Q:
procedure P is
x : aliased Integer := 42;
x_ptr1 : Int_Ptr := x'access; -- accessibility failure
type Local_Ptr is access all Integer;
x_ptr2 : Local_Ptr := x'access; -- accessibility pass...
begin
Q(x_ptr2); -- but type conversion failure
end P;
end K;
Just like before, the accessibility rules are doing what they are designed to do. Both our attempts to copy the pointer outside of P are thwarted for the rules we studied before.
Note in this case, however, that there is no dangling reference. Nothing 'bad' happens inside Q. There are no attempts to copy the parameter elsewhere, or any other sort of nefarious, dangling-reference creating behavior. As written, this code is perfectly safe.
But alas, the pessimistic language rules prevent this from ever compiling. Q is always at a higher scope than x, so we have no recourse apart from relocating Q inside P (which is rarely possible in production code), or perhaps redefining Q to take an Integer instead unnecessarily using a pointer (assume for example's sake that we cannot).
This is a shame, because there is nothing inherently wrong with this code. The only problem is that the compiler can't "see into" Q to verify nothing sketchy is taking place, and therefore must assume the worst. But what if a language construct existed to let Q 'promise' the access value would never be copied to a longer lived type during its execution? The compiler could then allow P to pass x into Q, confident that no dangling references would be created inside.
To this end, alongside the accessibility rules and 'Access attribute, Ada95 introduced the idea of the anonymous access type. Like the name suggests, instead of declaring a named type to use for the access value, the declaration is simply put 'in line' where the type would normally be. For instance, we can rewrite Q from above as follows:
procedure Q (arg : access Integer) is -- Access Parameter
begin
Ada.Text_IO.Put_Line(Integer'Image(arg.all));
end Q:
Note the 'type' of arg is now of an anonymous nature, known as an access parameter. Remember, though, an "access parameter" is a special construct with special rules, which is much different than a parameter of a named access type.
"Anonymizing" our parameter has several important consequences on our program. Most importantly, we (as the programmers of Q) have essentially "stripped" the parameter of its type information. Within the body of Q, we have no idea what the 'real' type of arg really is, only that it is of some type of access value that points to an Integer.
But remember, assignment in Ada requires that both types match. By removing all the type information from our parameter, the object is now incompatible with all types! If we try to copy arg into a global Int_Ptr, it will fail because, after all, we're not sure arg is an Int_Ptr. If we try to pass arg as a (named) parameter to some other procedure, it will fail because they are not the same type. In fact, there isn't a single place we can ever copy arg to, except another access parameter (which, of course, can't copy it anywhere except another access parameter, and so on).
In addition, we clearly don't want Q reassigning the parameter, either, since this would have the unpleasant effect of changing the underlying type of the actual named type to something else. For this reason, access parameters are defined to be constant (in) parameters.
Now we have turned the tables. Q can now accept any access value (provided it's to an integer), of any type, with any scope, heap and stack values alike. P, on the other hand, can be confident no dangling references will exist, since Q will never know the actual type, and thus won't be able to copy it anywhere (this even includes even local values, which would obviously be safe, but that's the trade-off we have to make).
So to recap, access parameters are a mechanism that can be used to safely pass shorter-lived access values to longer-lived subprograms, by ensuring the subprogram can't copy it. Given that, it's almost always preferably to use an access parameter in lieu of a named access type, assuming you don't need to copy the access value, since it allows your subprogram to work with both general and pool-specific access values. Unfortunately, the aforementioned confusion, fear, uncertainty, and doubt about accessibility has created a environment where developers refuse to use access parameters, and then complain that the accessibility rules inhibit them. Such is life, i suppose.
Of course, if you a glass-is-half-empty programmer, you might have noticed the example was deliberately convoluted. After all, even the least experienced Ada programmer would know better than to use an access value of any kind for Q, and simply used an Integer. One of the joys of working with Ada is that as mentioned in the first post, you don't have to use pointers for everything like in C.
The majority of the time access values are required, it's for complex data structures (linked lists, etc) which embed the access value within an enclosing record. An access parameter will not help us with that, since the parameter is not actually an access value. For instance, let's suppose our integer pointer is within a larger record containing some other meaningless data:
package K
type Int_Ptr is access all Integer;
type Big_Record is
record
e1 : boolean;
e2 : Some_Enum;
e3 : Int_Ptr;
end record;
procedure Q (arg : Big_Record ) is
begin
Ada.Text_IO.Put_Line(Integer'Image(arg.e3.all));
end Q:
procedure P is
x : aliased Integer := 42;
y : Big_Record := (foo, bar, x'Access); -- failure!
begin
Q(y); -- but type conversion failure
end P;
end K;
So we have the same situation, except that x is enclosed within a bigger record. Now we are in trouble, since we must have a type to declare our Big_Record, but such a type would always end up being of a higher scope, resisting any attempt at filling e3 with a local pointer. This is still a shame, since Q continues to do nothing dubious with the pointer.
In keeping with the same philosophy of access parameters, what if there was a way to provide a kind of "anonymous record element"? That solution worked for parameters, and might seemingly work for this situation too. All we want to do is make sure that Q does not copy e3 out to somewhere and create a dangling pointer.
Unfortunately, things are much more complex for record types. We don't just need to prevent the copying of e3, because copying the entire record type itself implies copying each element, including the pointer. Similarly, it still needs to be constant so that we cannot change the type to something else, yet records can't have constant elements.
Luckily for us, both constructs already exist in Ada for doing both: limited, discriminated records. Recall that a record type marked as limited cannot be assigned (or reassigned), which would prevent the copying of the entire record (and consequently the access value embedded inside). And while Ada does not have the concept of 'constant' record elements, a record's discriminants do have this unique property.
And so along with access parameters, Ada95 also included access discriminants. They are defined similarly to access parameters, except in a limited record declaration:
type Big_Record (e3 : access Integer) is limited
record
e1 : boolean;
e2 : Some_Enum;
end record;
It should be noted at this point that qualifies as an 'abuse of notation' since the record is not, in the strict sense, discriminanted. The discriminants are simply playing double-duty as normal elements that need to be constant. Perhaps a better name would have been constant access elements, but i suppose it's a little late for could-of's.
In any case, access discriminants provide the same type of restrictions as access parameters, along with the same benefits. We can now write our example using local access values, like so:
package K
type Big_Record (e3 : access Integer) is limited
record
e1 : boolean;
e2 : Some_Enum;
end record;
procedure Q (arg : Big_Record) is
begin
Ada.Text_IO.Put_Line(Integer'Image(arg.e3.all));
end Q:
procedure P is
x : aliased Integer := 42;
y : Big_Record := (x'Access, foo, bar); -- pass!
Q(y);
end P;
end K;
Just like access parameters, access discriminants give us the ability to pass around local access values to longer lived subprograms, while remaining certain no harm (in the form of dangling references) will come to them. If Q tries to copy the pointer, it will fail because of the same 'anonymous' type failures as access parameters. If it tries to copy or reassign the whole record, it will fail because of the limitedness.
But there is one last problem: Thus far we've assumed that we will be passing values into subprograms, which for access parameters was obviously true. But an access discriminant is part of a declared object that can be equally as well passed out of a subprogram (i.e. as a return value), instead of going in. This has obviously dire consequences, since the scope will be going the wrong way. For instance
function F return Big_Record is
x : alised Integer := 42;
begin
return (x'Access, foo, bar);
end F;
is the textbook example of a dangling reference (x ceases to exist when the function returns, yet the return value has a reference to it).
Solving this conundrum requires one of the few runtime checks in the Ada accessibility rules (specifically mentioned in 6.5~21/3). This code will compile and run, yet raise Program_Error upon executing. Or, at least, it should: most versions of GNAT (and GNAT-based compilers) completely blow this discriminant check, and such buggy implementations produce code that actually does have dangling references. Hopefully a supported GNAT Pro user will use their clout to get such problems fixed (they don't seem to listen to me). Such is life.
So between access parameters and access discriminants, a programmer has the mechanisms to work safely with local access values while being statically (in most cases) guaranteed that pointers won't be left dangling. The only situations where the preceding methods won't work are those in which you want to copy a pointer, which is, of course, the exact thing the rules are trying to prevent. If you do need to copy a pointer somewhere longer-lived, you need to use a named access type (in actuality, you need to use a shared pointer, but that's a different post).
Yet all is not well. Next time, we will see how a simple idea like access parameters got way, way out of hand.
Sunday, March 10, 2013
Ada access types, part I
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.
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.
Subscribe to:
Posts (Atom)