Friday, August 31, 2007

The Fundamental Theory of Ada

About 20 years ago, in the late 80s, I was at an Ada Conference attending a seminar being taught by Doug Bryan, who was then at Stanford University. Bryan was talking about how to get the most out of Ada, of which a critical aspect is understanding the underlying design principles of the language. The key concept he was trying to get across in this seminar was that Ada's design centered around a "type model". If you understood how Ada's type model worked, he said, then you understood why the language came out the way it did, and how to work with the language, instead of fighting against it.

While I'd been programming in Ada for a few years by then, this was the first time that I truly realized there might be something underlying and guiding the definition of a programming language, that there might be more to creating a programming language than getting a bunch of people together to make up declaration and statement and packaging syntax and semantics.

The realization that a type model for Ada existed turned out to be the genesis of what eventually coalesced into my idea of a programming language's Fundamental Theory. Today I recognize that the Fundamental Theory of Ada is its type model.

By enshrining the type model as its FT, Ada allows a huge amount of information to be intrinsically embedded within Ada programs with a simple type definition. This information is then readily accessible to the developer through the use of Ada's attributes.

Take a simple example:

type Speed_Range is range 0 .. 1000;

With nothing more than a reference to an object of that type:

Speed : Speed_Range;

One can know its minimum value (Speed_Range'First), maximum value (Speed_Range'Last), the minimum number of bits needed to represent all possible values of the type (Speed_Range'Size), the actual number of bits representing a variable of that type (Speed'Size, which is often larger than the type size since objects almost always occupy a whole number of bytes), the number of characters needed to represent the longest possible string representation of values of that type (Speed_Range'Width), etc. You can convert values to and from strings (Speed_Range'Image, Speed_Range'Value), do min/max comparisons (Speed_Range'Min(100, Speed), Speed_Range'Max(Current_Max, Speed)), and use the type as a loop controller ("for S in Speed_Range loop" and "while S in Speed_Range loop"), and more. And none of this information needs to be explicitly programmed by a developer, it is all implicitly provided by the mere definition of the type.

Different kinds of scalar types may have these and other attributes appropriate to the nature of the type: floating point types have attributes for identifying the underlying constituents, accuracy and representational limitations of a floating point type definition, while enumeration types also have attributes to access all positional aspects of the type's values.

Ada's type model extends well beyond simple scalar types: inheritance is obviously based on inheriting from other types via the "tagged" modifier, static polymorphism comes through generic (template) instantiations with the desired types, and dynamic polymorphism is provided by tagged, "abstract" types. Even Ada's concurrency constructs are type-oriented, i.e. task types and protected types (while singletons of each of these can be declared, what goes on under the surface is that a corresponding anonymous type is implicitly defined of which the singleton is the only object). By declaring a subprogram profile type, subprograms themselves are treatable as type objects.

The supporting infrastructure of executable constructs, i.e. the statements, are all then integrated with this type model, and able to exploit the information that is an implicit part of each type, for example in the "loop over the type" statements mentioned above, as well as is done with array handling:

for I in Race_Speeds_List'Range loop ...

There is one area of non-conformance, though. For some reason the whole exception mechanism was not well integrated with the type model. There's nothing that can be construed as an "exception type" in the language (although an exception type mechanism was proposed for the Ada 2005 language revision, it was rejected). So there's no hierarchy of exceptions, no inheritance, and while the Ada 95 revision did incorporate the creation of exception "objects" to which data could be attached (which must, though, be in the form of a string), exception handling is recognized as admittedly inferior to that of most other commonly used languages.

Despite the exception deficiencies, the Ada standard has conformed very well to its fundamental type model theory throughout its evolution. Even when major revisions were made during the Ada 83 to Ada 95 revision process to incorporate full object orientation, that capability was defined as an extension of the existing type mechanisms. (And the fact that improvements to the exception mechanism center around "type-ifying" exceptions show that the type model is recognized as the driving factor of the language's design.)

Understanding and exploiting the Fundamental Theory of Ada leads to more reliable and more efficient software. One issue programmers new to Ada invariably run into and complain about is the preponderance of compilation failures due to "type mismatches" in their code. "Why can't I multiply velocity by a time interval and add it to distance? They're all just numbers!" That's just it, they're not just numbers, they are abstracted entities, each with their own characteristics and constraints, modeled in the language's typing system, and that are only allowed to interact in well-defined ways. Other languages model entities this way, too, except that they require the developer to explicitly model them as classes, while in Ada the language itself effectively performs the type modeling for these kinds of quantities.

By understanding and exploiting the Fundamental Theory of Ada, by understanding what an Ada type represents, an abundance of information about the problem domain can be embedded within the software, can be easily exploited, and can lead to the efficient production of reliable software.


Dan said...

Types are just types. A strongly typed language is good for many problem domains. Conversely, a weakly-typed language like Perl 5 can be very powerful. The power to morph quickly as one uses Perl to process Query Design Language files into C accessors for Oracle, as I did in 1997 for Lockheed Martin, was very powerful and prodigious. At that point in time Perl was a hot item in the software community. I loved using Perl because it was easy to learn, it was very terse, and was very powerful for text processing. Using Ada, C, or C++ for that particular job would have been painful. With Perl it was a breeze.

This gets back to my premise from earlier responses in this blog. Pick the right tool for the job. Marc has significant experience building complex ground breaking systems for the U.S. Navy and beyond. For these systems, which need to failsafe, Ada is an excellent choice.

In 2007, I think object models, name spaces, and domain-specific programming languages rule the day. Languages will continue to morph. Computer science is a very young discipline. It has only been around for roughly 60 years.

As we move toward service-oriented architectures, dynamically composed programs, and grammar-oriented architectures, much work will need to be done to realize the dream of self-configuring systems that adjust to threats and loads in real-time. Guaranteed quality of service and guaranteed service delivery are important.

I believe one of Ada 83's biggest contributions was the notion of package specifications and package bodies as a mechanism for information hiding and abstraction. Grady Booch pressed further with the notion of subsystems that were composed of Ada packages (or namespaces).

To me extensibility and the composition of reusable components is very important.

But, let's get back to what is the central issue. Pick the right tool for the job. There are many excellent languages and software development platforms.

Marc said...

Ah, but you're not getting my point underlying this Fundamental Theory stuff. Hopefully the
Picking the Right Tool
post will help clarify where I'm coming from.

Anonymous said...

I got my CS degree from a university where Ada is a required language used in CS III "Data Structures." Most students absolutely hated Ada, whereas I actually thought it not too bad, though a tad verbose. I noticed the usefulness of type declarations that you explain here and still think it's a wonderful feature. But eventually I got frustrated with it, because of those type mismatches you mention. "Why can't I multiply velocity by a time interval and add it to distance? They're all just numbers!" is a very poor, straw-man example. A better one would be, why should it be so difficult to get half of pi? Or for another, why does it have to require me to overload operators and/or wrap subexpressions in multiple layers of ugly casts, to write a hash function for, say, a Bloom filter?

JC said...


A better one would be, why should it be so difficult to get half of pi? Or for another, why does it have to require me to overload operators and/or wrap subexpressions in multiple layers of ugly casts, to write a hash function for, say, a Bloom filter?

Ada.Numerics.Pi / 2

What's so difficult about that?

There are no casts in Ada. The fact that you're using C terminology indicates that you're probably thinking in C and trying to implement it in Ada. That path guarantees conflicts with the language. When your thinking follows the SW engineering discipline that Ada enforces, you'll find that such conflicts don't arise. That's why coders hate Ada, and SW engineers (about 2% of developers) love it.

Anonymous said...

Casts, type-conversions, whatever you choose to call them. To my thinking, acting like the plane is crashing if I dare try to divide a floating-point number by an integer is inconsistent with mathematical convention. But by adopting your "better than you" tone of the rarefied software engineer versus the lowly coder, you have pretty much guaranteed that I will not bother with discussing the matter with you further. Thanks for confirming some of what I already thought about Ada programmers.

poppafuze said...

For the exact reasons the pi-dividers complain about, the planes, in fact, do not crash.

Pi-dividers: Please do not apply for a job where my money or my life will depend on your code.