Draft of article submitted to EE Times
by S. Tucker Taft
Copyright (C) 1994 Intermetrics, Inc.
Copying permitted if accompanied by this statement.
An edited version was published in the June 6, 1994 issue of EE Times on page 112. The author prefers the original version, thus it is presented here.
Ada 9X, a new version of the Ada programming language, is on the verge of international standardization. Anyone involved with the development of embedded systems should take a serious look at this new version of Ada, as it retains the excellent readability and safety of the original version, while providing the flexibility and control of lower-level languages, and full support for object-oriented programming and multitasking.
The original version of Ada (dubbed Ada 83 for its year of ANSI standardization) was designed 15 years ago as part of a competition to provide a common high order language for the US Department of Defense. Ada was based on Pascal, and its syntax should look very familiar to a Pascal user:
with Ada.Text_IO; use Ada.Text_IO; procedure Hello is begin Put_Line("Hello, Ada9X!"); end Hello;
To the Pascal-based core, Ada 83 added support for packages (modules) with abstract data types, generic units (also called templates), exceptions, and multitasking. Ada 83 broke new ground in integrating these various features into a single language, though now other programming languages are beginning to adopt many of these capabilities pioneered by Ada.
Despite the flattery of imitation, Ada remains unmatched in its extraordinary readability. The excellent syntactic foundation of Pascal was extended carefully, to ensure that all features had a consistent syntax, emphasizing natural English word order, while minimizing the use of abbreviations or special characters. An interesting phenomenon resulting from this concern for readability is that it seems to rub off on Ada programmers, largely independent of their background. An aesthetic emphasizing readability has grown up as part of the Ada programming culture (much as an aesthetic for conciseness has grown up as part of the APL programming culture).
Ada 9X builds on the Ada 83 foundation of readability and integration, by generalizing and enhancing certain of the features to further support modern programming paradigms. In particular, the existing support for abstract data types has been generalized to provide full support for object-oriented programming, including inheritance and run-time polymorphism. The existing support for packages has been enhanced to allow for the construction of hierarchies of compilation units, providing for the disciplined organization and extension of large software subsystems. The existing support for multitasking has been enhanced to better support data-oriented synchronization paradigms, through a building block called "protected types." And finally, a number of smaller enhancements have been made to give the programmer even more control and flexibility, including direct support for pointers to statically allocated data, pointers to subprograms, bit manipulations of unsigned data types, and complete control over dynamic storage management.
Very few syntactic extensions have been necessary to provide these enhanced capabilities; instead the existing capabilities have been generalized. For example, rather than adding an object-oriented "corner" to the language, we were able to extend the existing mechanism for abstract data types and packages to support the more dynamic capabilities of full object-oriented programming.
As an illustration, in Ada 83, one could define one abstract data type in terms of another:
type Disk_Device is new Device;
However, in Ada 9X, this capability to derive a new type from an existing one has been generalized to allow the specification of additional components as well:
type Disk_Device is new Device with record Current_Cylinder : Cylinder_Number; end record;
These additional components can be declared visibly, as above, or declared privately and then they are only directly accessible from within the package in which the type is declared:
type Disk_Device is new Device with private;
This allows the programmer to choose the level of information hiding appropriate to their application. Having defined a number of types all derived, directly or indirectly, from some root type such as Device, Ada 9X allows the programmer to talk about the entire set of such types. Ada 9X calls such a set of types a "class" of types, and provides the notation Device'Class to refer to them. A subprogram may specify a formal parameter to have a "class-wide type" such as Device'Class, and then within the subprogram, when a primitive operation is applied to the formal parameter, a run-time dispatch to the "appropriate" implementation of the operation is performed automatically.
For example, presuming that one defines the primitive operations Open and Close on the root type Device, each type derived from Device inherits these primitive operations, and may override them. One can then define a subprogram such as this:
procedure Reset(Dev : in out Device'Class; New_Mode : in Device_Mode) is begin Close(Dev); Open(Dev, Mode => New_Mode); end Reset;
One could then call such a "class-wide" subprogram as follows:
Dsk_1 : Disk_Device; begin Reset(Dev => Dsk_1, New_Mode => Out_Mode);
The calls on Close and Open inside Reset will dispatch automatically at run-time to the particular implementation of Close and Open associated with the specific type of the actual parameter passed in as the Dev parameter, in this case the Close and Open for Disk_Device. This run-time dispatch is called "run-time polymorphism," and is implemented with a simple indirection through a type descriptor identified by a run-time type tag carried with objects of a type like Disk_Device. Note that such an indirect call would be the way that such "device independence" would be implemented in a "conventional" operating system, but here, thanks to the object-oriented programming support in Ada 9X, a safe, efficient, and readable implementation is possible without resorting to explicit device tables or subprogram pointers.
type Flags is mod 2**4; -- a 4-bit flags field F : Flags := 2#0100#; -- initialize using a binary number begin F := F or 2#1001#; -- Set the first and last bit.
Because even numeric types in Ada are strongly typed, one can define mnemonically-named masks that are specific to a type like Flags, and have confidence that these masks are only applied to values of type Flags. For example:
Status_Mask : constant Flags := 2#1001#; -- Status bits Status_Ready : constant Flags := 2#1000#; -- Status = Ready type Control is mod 2**4; -- A 4-bit control field Start_Xfr : constant Control := 2#0001#; -- Initiate xfr command type DCU_Device is record State : Flags; Action : Control; end DCU_Device; DCU_1 : DCU_Device; -- A Disk Control Unit for DCU_1'Address use 16#FFFF_FE00# -- Specify address begin if (DCU_1.State and Status_Mask) = Status_Ready then -- Initiate transfer if controller is ready DCU_1.Action := Start_Xfr; end if;
Any attempt to apply a mask of type Flags to a value of type Control would be caught at compile-time. This is an example where the very strong typing capabilities of Ada can be used to aid the programmer in writing a correct and readable program that has a good chance of surviving the slings and arrows of long-term maintenance.
Many embedded systems involve multiple threads of control, either explicitly with multiple tasks using some kind of priority scheduler, or implicitly with the various threads of control arising from interrupts. In either case, there is a need to synchronize between the various threads of control, both interrupt level and user task level.
Multitasking is built into Ada. In Ada 83, the language provided support for synchronization through a synchronous message-oriented mechanism called "rendezvous." Ada 9X complements this message-oriented mechanism with an asynchronous data-oriented mechanism called "protected types." The protected type feature is a building block that allows a programmer to implement essentially any of the popular synchronization constructs, such as various flavors of semaphores (binary/counting, queued/private), mailboxes, multi-task barriers, etc. By design, protected types simplify the development of race-free synchronization objects that work equally well in a monoprocessor and a multiprocessor environment.
For example, here is the specification for a counting semaphore using a protected type:
protected type Counting_Semaphore(Initial : Integer := 1) is entry Acquire; -- the "P" operation procedure Release; -- the "V" operation function Count return Integer; -- a function to return the count -- of available resources private Current_Count : Integer := Initial; end Counting_Semaphore;
One would declare and operate on an object of this type as follows:
Sem : Counting_Semaphore(2); begin Sem.Acquire; ... Sem.Release;
In a protected type, one may define one or more "protected" operations, each of which is either an "entry," a "procedure," or a "function." When called, protected procedures and entries automatically get exclusive read/write access to the data components of the protected object (declared following the word private -- Current_Count in this case). Protected functions get shared read-only access, allowing parallel invocations of functions on the same protected object in a multiprocessor environment.
Protected procedures and entries differ in that protected procedures gain exclusive access, but perform no other synchronization, whereas protected entries synchronize with the state of the protected object, by specifying a boolean "entry barrier" that must be true prior to executing the body of the entry. To illustrate this, here is an implementation of the above protected type:
protected body Counting_Semaphore is entry Acquire when Current_Count > 0 is -- Acquire a resource, but first wait until there is one. begin Current_Count := Current_Count - 1; end Acquire; procedure Release is -- Release a resource, thereby possibly enabling -- waiting entry callers to proceed. begin Current_Count := Current_Count + 1; end Release; function Count return Integer is begin return Current_Count; end Count; end Counting_Semaphore;
In the above examples, the operations have no explicit formal parameters. The protected object of interest is identified using a prefix in the call, such as Sem in Sem.Release. However, protected operations may also have explicit parameters, as illustrated in the following example of a mailbox type:
type Message_Array is array(Natural range <>) of Message; protected type Mailbox(Size : Natural) is entry Put(Msg : in Message); entry Get(Msg : out Message); private In_Index, Out_Index : Positive := 1; Count : Natural := 0; Buffer : Message_Array(1..Size); end Mailbox;
In this case, the only protected operations are entries. As in other constructs in Ada, the logical interface (the protected operations) and the physical interface (the protected components) are separated by the word "private." The component declarations in the physical interface are visible only inside the body of the protected type, but are included in the specification to allow for efficient compilation.
The implementation of this mailbox type could be:
protected body Mailbox is entry Put(Msg : in Message) when Count < Size is -- Add a message to the mailbox, -- but first wait until there is room begin -- Insert the message, and bump the index and the count Buffer(In_Index) := Msg; In_Index := In_Index mod Size + 1; Count := Count + 1; end Put; entry Get(Msg : out Message) when Count > 0 is -- Remove a message from the mailbox, -- but first wait until there is at least one begin -- Extract the message, bump the index, and decrement the count Msg := Buffer(Out_Index); Out_Index := Out_Index mod Size + 1; Count := Count - 1; end Get; end Mailbox;
Note that in both of the above examples, the type has a parameter to control the size or initialization of the object. This type parameter is called a "discriminant." In Ada 83, only record types could have discriminants. However, in Ada 9X, we made a natural generalization of this concept so that all composite types could have discriminants, adding flexibility and control without increasing the number of concepts in the language.
Protected entries are called "potentially blocking" operations, because if they are called when the entry barrier evaluates to False, the calling task is blocked until some subsequent operation on the same protected object causes the state to change and the barrier to evaluate to True, or until the call is cancelled. A caller may choose to call an entry unconditionally, meaning that the caller will be blocked until the barrier evaluates to True. Alternatively, the caller may use a "timed" or "conditional" entry call, allowing the caller to control the maximum length of the blocking.
For example, should the caller want to wait at most 0.1 seconds for a message, the timed entry call construct could be used:
Mbox : Mailbox(Size => 20); M : Msg; begin loop select Mbox.Get(M); Handle_Message(M); or delay 0.1; Do_Something_Else; end select; end loop;
The call on Mbox.Get is cancelled automatically if the entry barrier for Get is False upon call, and remains so for 0.1 seconds. In this case, the code following the "delay" statement (a call on "Do_Something_Else" in this case) is executed. On the other hand, if the entry barrier is True upon call, or becomes so within 0.1 seconds of the call, the entry body is performed, a message is returned in M, and the code following the entry call (a call on "Handle_Message" in this case) is performed; the code following the delay statement is skipped.
Unconditional, timed, and conditional entry calls already existed in Ada 83, and were used as part of the task rendezvous feature. In Ada 9X, we generalized the concept of entry, and the various kinds of entry calls, to apply to the new data oriented synchronization mechanism. This allowed us to provide maximum flexibility while minimizing the number of new concepts in the language.
The choice between unconditional, timed, and conditional entry calls gives the caller significant control. The choice between procedure, function, and entry operations, plus the choice of entry barrier, gives the implementor of the protected type great flexibility. This combination of flexibility and control allows the protected type to act as an efficient "building block" for tailoring the synchronization mechanisms to support the needs of a particular application.
Protected types also provide the basis for the implementation of efficient device drivers and interrupt handlers. Protected procedures may be designated as interrupt handlers. Other operations in the same protected type may act as interfaces for starting I/O operations, querying the state of the device, etc. The appropriate interrupt is masked automatically during an operation on a protected object with an interrupt handling protected procedure. This allows the state of the device to be queried safely, or a new operation to be initiated, without allowing an interrupt to intervene inappropriately.
For example, here is a simple protected object acting as a device driver, for the Disk Control Unit referenced in an earlier example:
protected type DCU_Driver( DCU : access DCU_Device; DCU_ID : Interrupt_ID) is entry Initiate_Transfer(Data : Buffer); entry Wait_For_Completion; procedure Reset_Controller; function Query_State return Flags; private procedure Handler; pragma Interrupt_Handler(Handler, DCU_ID); end DCU_Driver;
An object of type DCU_Driver provides access to the lowest level operations on DCUs, plus an interrupt handler. Some of the operations are entries, allowing their callers to be blocked automatically until the device is in a desired state. The other operations are nonblocking, allowing them to proceed independently of the current state of the device. All of the operations will automatically mask the associated interrupt (identified by the discriminant DCU_ID) while the operation's body is executing, to prevent an unwanted interrupt from interfering with the logic. Note that there is no data "inside" the protected object. Instead, the "access" discriminant DCU points to a DCU_Device data structure, whose address would be specified with an Address clause, as in the earlier example:
DCU_1 : aliased DCU_Device; for DCU_1'Address use 16#FFFF_FE00# Driver_1 : DCU_Driver(DCU_1'Access, DCU_ID_1); begin Driver_1.Reset_Controller; Driver_1.Initiate_Transfer(Buf); select Driver_1.Wait_For_Completion; -- Wait for transfer to complete or delay 1.0; -- Wait a maximum of 1.0 second -- A time-out occurred, log it and raise an exception Log_Error("DCU_1 time-out"); Driver_1.Reset_Controller; raise Controller_Error; end select;
The above example illustrates the combination of readability, time-based and interrupt-driven processing, and low-level control that Ada 9X provides. With the availability of a free Ada 9X compiler from NYU using the multi-targeted GNU C backend, and the imminent appearance of Ada 9X offerings from the commercial Ada 83 vendors, developers of embedded systems should take the opportunity to evaluate Ada 9X for their upcoming projects. A growing number of companies have discovered that the unique combination of capabilities provided by Ada give them a competitive advantage in the development and rapid deployment of efficient, robust, and maintainable systems.