Welcome to Programming in Ada 2012 which has been triggered by the recent ISO standardization of Ada 2012.

The original language, devised in the 1980s, is known as Ada 83 and was followed by Ada 95, Ada 2005, and now Ada 2012. Ada has gained a reputation as being the language of choice when software needs to be correct. And as software pervades into more areas of society so that ever more software is safety critical or security critical, it is clear that the future for Ada is bright. One observes, for example, the growth in use of Spark, the Ada based high integrity language widely used in areas such as avionics and signalling.

Ada 83 was a relatively simple but highly reliable language with emphasis on abstraction and information hiding. It was also notable for being perhaps the first practical language to include multitasking within the language itself.

Ada 95 added extra flexibility to the strongly typed and secure foundation provided by the Software Engineering approach of Ada 83. In particular it added the full dynamic features of Object Oriented Programming (OOP) and in fact was the first such language to become an ISO standard. Ada 95 also made important structural enhancements to visibility control by the addition of child units, it greatly improved multitasking by the addition of protected types, and added important basic material to the standard library.

The previous chapters have covered the intrinsic aspects of the Ada language; that is all the various syntactic forms. This chapter and the next two chapters describe the predefined library which comes with every implementation of Ada. As outlined in Chapter 4, the predefined library is structured as three packages: Ada, System and Interfaces with numerous child packages. These three packages are themselves (like all root library units) considered to be child units of Standard. This chapter is largely about the packages Standard and Ada, apart from the huge package Ada.Containers which is described in Chapter 24; System and Interfaces are discussed in Chapter 25.

The main facilities provided by the package Ada are string and character handling, the mathematical library including elementary functions and random number generation, various forms of input-output and communication with the operational environment.

The package Standard

As mentioned earlier, certain entities are predefined through their declaration in the special package Standard. It should not be thought that this package necessarily actually exists; it is just that the compiler behaves as if it does. Indeed, as we shall see, some entities notionally declared in Standard cannot be truly declared in Ada at all. The general effect of Standard is indicated by the outline specification below.

The predefined operators are given in comments since they are implicitly declared. Italics are used for identifiers not available to users (such as universal_real) and for implementation-defined information.

Amajor feature of the predefined library of Ada 2012 is the container library. This is rather extensive and merits this separate chapter on its own.

The main part of the library comprises several generic packages for the manipulation of various kinds of important data structures. These structures are vectors, doubly linked lists, maps and sets (both hashed and ordered), multiway trees, a holder (or wrapper), and various task safe queues. There are also generic packages for sorting arrays and other general structures.

Organization of library

The container library comprises a root package Ada.Containers plus various child generic packages. The main generic packages form three groups. The first group concerns objects of definite types; the second group concerns indefinite types, and the third group has bounded capacity for objects of definite types.

It will be remembered that an indefinite (sub)type is one for which we cannot declare an object without giving a constraint (either directly or indirectly from its initial value).

The reason for distinct containers for definite and indefinite types concerns efficiency. It is much easier to manipulate definite types and although the packages for indefinite types can be used for definite types, this would be rather inefficient.

Another consideration is reliability. For high integrity applications it is generally unacceptable to use dynamic storage allocation. Accordingly, a separate group of containers with bounded capacity is provided for definite types.

Note that there are no bounded containers for indefinite types because objects of indefinite types (such as the type String) by their very nature are of variable size and thus inevitably need dynamic storage management.

The containers can also be categorized in other ways.

Sequence containers – these hold sequences of elements. There are packages for manipulating vectors and for manipulating linked lists. These packages have much in common. But they have different behaviours in terms of efficiency according to the pattern of use. In general (with some planning) it should be possible to change from one to the other with little effort.

Multiway tree containers – these hold elements as a multiway tree. They have much in common with the sequence containers.

Associative containers – these associate a key with each element and then store the elements in order of the keys. There are packages for manipulating hashed maps, ordered maps, hashed sets and ordered sets.

Ada 2012 is a comprehensive high level programming language especially suited for the professional development of large or critical programs for which correctness and robustness are major considerations. In this introductory chapter we briefly trace the development of Ada 2012 (and its predecessors Ada 83, Ada 95, and Ada 2005), its place in the overall language scene and the general structure of the remainder of this book.

Standard development

Ada 2012 is a direct descendant of Ada 83 which was originally sponsored by the US Department of Defense for use in the so-called embedded system application area. (An embedded system is one in which the computer is an integral part of a larger system such as a chemical plant, missile or dishwasher.)

The story of Ada goes back to about 1974 when the United States Department of Defense realized that it was spending far too much on software, especially in the embedded systems area. To cut a long story short the DoD sponsored the new language through a number of phases of definition of requirements, competitive and parallel development and evaluation which culminated in the issue of the ANSI standard for Ada in 1983. The team that developed Ada was based at CII Honeywell Bull in France under the leadership of Jean D Ichbiah.

The language was named after Augusta Ada Byron, Countess of Lovelace (1815–52). Ada, the daughter of the poet Lord Byron, was the assistant and patron of Charles Babbage and worked on his mechanical analytical engine. In a very real sense she was therefore the world's first programmer.

Ada 83 became ISO standard 8652 in 1987 and, following normal ISO practice, work leading to a revised standard commenced in 1988. The DoD, as the agent of ANSI, the original proposers of the standard to ISO, established the Ada project in 1988 under the management of Christine M Anderson. The revised language design was contracted to Intermetrics Inc. under the technical leadership of S Tucker Taft. The revised ISO standard was published on 15 February 1995 and so became Ada 95.

The maintenance of the language is performed by the Ada Rapporteur Group (ARG) of ISO/IEC committee SC22/WG9. The ARG under the leadership of Erhard Plödereder identified the need for some corrections and these were published as a Corrigendum on 1 June 2001.

The following syntax rules are taken from Annex P of the ARM. The rules have been reordered to correspond to the order of introduction of the topics in this book but individual rules have not been changed.

It should be noted that the rules for the construction of lexical elements, which are under the subheading of Chapter 5, have a slightly different status from the other rules since spaces and newlines may be freely inserted between lexical elements but not within lexical elements.

The rules have been sequentially numbered for ease of reference; an index to them will be found in Section A3.2. Note that in rules 74 (discrete_choice_list), 98 (component_choice_list), 111 (membership choice_list), 201 (exception_handler), and 226 (discriminant_association), the vertical bar following the brace stands for itself and is not a metasymbol.

Syntax rules

Chapter 5

• 1 identifier ::= identifier_start ﹛identifier_start | identifier_extend﹜

• 2 identifier_start ::= letter_uppercase | letter_lowercase | letter_titlecase | letter_modifier | letter_other | number_letter

• 3 identifier_extend ::= mark_nonspacing | mark_spacing_combining | number_decimal | punctuation_connector

• 4 numeric_literal ::= decimal_literal | based_literal

• 5 decimal_literal ::= numeral [. numeral] [exponent]

• 6 numeral ::= digit ﹛[underline] digit﹜

• 7 exponent ::= E [+] numeral | E - numeral

• 8 digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

• 9 based_literal ::= base # based_numeral [. based_numeral] # [exponent]

• 10 base ::= numeral

• 11 based_numeral ::= extended_digit ﹛[underline] extended_digit﹜

• 12 extended_digit ::= digit | A | B | C | D | E | F

• 13 character_literal ::= ‘graphic_character'

• 14 string_literal ::= “﹛string_element﹜“

• 15 string_element ::= “” | non_quotation_mark_graphic_character

• 16 comment ::= -- ﹛non_end_of_line_character﹜

• 17 pragma ::= pragma identifier [(pragma_argument_association ﹛, pragma_argument_association﹜)];

• 18 pragma_argument_association ::=

• | [pragma_argument_identifier =>] name

• | [pragma_argument_identifier =>] expression

• | pragma_argument_aspect_mark => name

• | pragma_argument_aspect_mark => expression

• Chapter 6

• 19 basic_declaration ::=

• type_declaration | subtype_declaration

• | object_declaration | number_declaration

• | subprogram_declaration | abstract_subprogram_declaration

• | null_procedure_declaration | expression_function_declaration

• | package_declaration | renaming_declaration

• | exception_declaration | generic_declaration

• | generic_instantiation

• 20 object_declaration ::=

• | defining_identifier_list : [aliased] [constant] subtype_indication [:= expression] [aspect_specification];

• | defining_identifier_list : [aliased] [constant] access_definition [:= expression] [aspect_specification];

• | defining_identifier_list : [aliased] [constant] array_type_definition [:= expression] [aspect_specification];

• | single_task_declaration

• | single_protected_declaration

• 21 number_declaration ::=

• defining_identifier_list : constant := static_expression;

• 22 defining_identifier_list ::= defining_identifier ﹛, defining_identifier﹜

• 23 defining_identifier ::= identifier

• 24 assignment_statement ::= variable_name := expression;

For building large systems, it is essential to build them from components and use module abstraction, that is, abstraction of both data and control in modules or components, to separate what functionalities are provided by a component from how the functionalities are implemented inside the component. Module abstraction is best supported as abstract data types. An abstract data type is an interface for a certain set of operations on a certain kind of data, that is, the “what”, shielding users from having to know how the data are represented and how the operations are implemented, that is, the “how”. It is a fundamental concept in modern high-level programming languages, particularly object-oriented languages.

Unfortunately, clear and modular implementations of the modules or components result in poor performance when nontrivial query operations are frequently performed and values of query parameters are gradually updated. At the same time, efficient implementations that incrementally maintain the query results with respect to updates to parameter values are much more difficult to develop and to understand, because the code grows significantly and is no longer clear or modular. Because the definitions and uses of queries and updates can cross multiple components, transforming clear implementations of the queries into efficient incremental implementations requires incrementalization across module abstraction.

We have shown a systematic method that succeeds in designing efficient implementations for many problems in many application domains starting with clear specifications of these problems using high-level language constructs. The method is systematic by being based on the language constructs used in the specifications and being guided by the cost considerations taken from the application domains.

The method, even though consisting of Steps Iterate, Incrementalize, and Implement in order, is driven by the middle step—Step Incrementalize. Because efficient computations on nontrivial input must proceed repeatedly on incremented input, Step Incrementalize aims to make the computation on each incremented input efficient by storing and reusing values computed on the previous input. Steps Iterate and Implement are enabling mechanisms: to maximize reuse by Step Incrementalize, Step Iterate determines a minimum input increment to take repeatedly; to support efficient access of the stored values by Step Incrementalize, Step Implement designs a combination of linked and indexed data structures to hold the values.

We first take a deeper look at incrementalization, showing how to systematically exploit the previous result, intermediate results, and auxiliary values for incremental computation. This will use simple examples specified using recursive functions, followed by several different sorting programs as additional examples. We then discuss abstractions in general, focusing on the importance of and principles for not only building up, but also breaking through, abstractions. The latter may sound surprising at first, but it is natural when query functions are incrementalized with respect to updates.

Many complex computational problems are most clearly and easily specified using logic rules. Logic rules state that if certain hypotheses hold then certain conclusions hold. These rules can be used to infer new facts from given facts. Example applications include queries in databases, analysis of computer programs, and reasoning about security policies. Datalog, which stands for Database logic, is an important rule-based language for specifying how new facts can be inferred from existing facts. Its fixed-point semantics allows the computation of the set of all facts that can be inferred from a given set of facts. It is sufficiently powerful for expressing many practical analysis problems.

While a Datalog program can be easily implemented using a logic programming system, such as a Prolog system, evaluated using various evaluation methods, such as well-established tabling methods, or rewritten using transformation methods for more efficient evaluation, such as using the well-known magic-sets method, these implementations are typically for fast prototyping. The running times of Datalog programs implemented using these methods can vary dramatically depending on the order of rules and the order of hypotheses in a rule. Even less is known about the space usage. Developing and implementing efficient algorithms specialized for any given set of rules and with time and space guarantees is a nontrivial, recurring task.

We first look at computational problems programmed using loops over numbers and arrays. A loop is a command for repeating a sequence of operations. A number is an integer or a real number with an internal representation in a computer. An array is an arrangement of computer memory elements in one or more dimensions. Problems involving arithmetic on numbers were the first problems for which computing devices were built. Problems involving operations on arrays were at the center of many subsequent larger computer applications. Because nontrivial computations involve performing operations iteratively, loops are a most commonly used, most important construct in programming solutions to problems.

Clear and straightforward problem solutions tend to have expensive computations in loops, where the values that these computations depend on are updated slightly in each iteration. To improve efficiency, the results of these computations can be stored and incrementally maintained with respect to updates to the values that they depend on. The transformation of programs to achieve this is called incrementalization.

We will use a small example and several variations to explain the basic ideas of incrementalization. We then describe two larger examples: one in hardware design, to show additional loop optimizations enabled by incrementalization, and the other in image processing, to show handling of nested loops and arrays in incrementalization. We discuss the need for higher-level languages at the end.

Many combinatorics and optimization problems can be solved straightforwardly by combining solutions to subproblems, where the subproblems may overlap in complicated manners. Such ways of solving the problems can be easily specified using recursive functions—functions whose definitions involve calls to the functions themselves, called recursive calls. The recursive calls are used for solving subproblems. Applications include many kinds of data analysis and decision-making problems, such as the great many kinds of analysis and manipulations needed on sequences, be they sequences in biological computing, document processing, financial analysis, or sensor data analysis.

Straightforward evaluation of recursive functions may be inefficient, and may in fact be extremely inefficient when they are used to solve overlapping subproblems, because subproblems may share subsubproblems, and common subsubproblems may be solved repeatedly. An efficient algorithm solves every subsubproblem just once, saves the result appropriately, and reuses the result when the subsubproblem is encountered again. Such algorithms are called dynamic programming algorithms. To arrive at such efficient algorithms, we must determine how efficient computations should proceed, and how computed results should be saved and reused. These correspond to Steps Iterate and Incrementalize. Step Implement just determines a straightforward way of storing the saved results in appropriate data structures.

Design may refer to both the process of creating a plan, a scheme, or generally an organization of elements, for accomplishing a goal, and the result of that process. Wikipedia states that design is usually considered in the context of applied arts, engineering, architecture, and other creative endeavors, and normally requires considering aesthetic, functional, and many other aspects of an object or a process [319]. In the context of this book in the computing world, design refers to the creation of computer programs, including algorithmic steps and data representations, that satisfy given requirements.

Design can be exciting because it is linked to problem solving, creation, accomplishments, and so on. It may also be frustrating because it is also linked to details, restrictions, retries, and the like. In the computing world, the creation of a computer program to accomplish a computation task clearly requires problem solving; the sense of excitement in it is easy to perceive by anyone who ever did it. At the same time, one needs to mind computation details and obey given restrictions in often repeated trials; the sense of frustration in the process is also hard to miss.

Systematic design refers to step-by-step processes to go from problem descriptions to desired results, in contrast to ad hoc techniques. For program design, it refers to step-wise procedures to go from specifications prescribing what to compute to implementations realizing how to compute. The systematic nature is important for reproducing, automating, and enhancing the creation or development processes. Clarity of the specifications is important for understanding, deploying, and evolving the programs. Efficiency of the implementations is important for their acceptance, usage, and survival.

Most computer applications must handle collections of data. A set is a collection of distinct elements. Operations on sets, such as union and difference of the elements of two sets, are higher-level than operations on arrays, which are assignment and access of elements at indexed positions. The largest class of computer applications that involve collections is database applications, which typically handle large collections of data and provide many kinds of queries and other functionalities. Because of their higher-level nature, sets and set operations can be used to express problem solutions more clearly and easily, and have been used increasingly in programming languages, though typically only in applications that are not performance critical.

Problem solutions programmed using high-level set operations typically have performance problems, because high-level set operations typically involve many elements and are often repeatedly performed as sets are updated. To improve performance of applications programmed using sets, expensive high-level operations on sets must be transformed into efficient incremental operations, and sets must be implemented using data structures that support efficient incremental operations. These correspond to Steps Incrementalize and Implement, respectively. Step Iterate just determines a simple way of iteration that adds one element at a time to a set.

Because graph problems are typically specified using sets, we first describe the method using the graph reachability problem as an example, showing how efficient graph algorithms can be derived systematically.

From clarity to efficiency: systematic program design

At the center of computer science, there are two major concerns of study: what to compute, and how to compute efficiently. Problem solving involves going from clear specifications for “what” to efficient implementations for “how”. Unfortunately, there is generally a conflict between clarity and efficiency, because clear specifications usually correspond to straightforward implementations, not at all efficient, whereas efficient implementations are usually sophisticated, not at all clear. What is needed is a general and systematic method to go from clear specifications to efficient implementations.

We give example problems from various application domains and discuss the challenges that lead to the need for a general and systematic method. The example problems are for database queries, hardware design, image processing, string processing, graph analysis, security policy frameworks, program analysis and verification, and mining semi-structured data. The challenges are to ensure correctness and efficiency of developed programs and to reduce costs of development and maintenance.

Example problems and application domains

Database queries. Database queries matter to our everyday life, because databases are used in many important day-to-day applications. Consider an example where data about professors, courses, books, and students are stored, and we want to find all professor-course pairs where the professor uses any of his own books as the textbook for the course and any of his own students as the teaching assistant for the course.