ADA is too complex to be correct
Many may still remember the mathematician who made that statement back in the eighties. It came as no surprise when he started some kind of so-called logic for proving correctness of programs. Those were the days, we were young and such were the beginnings of programming. Few of us noticed that the person griping about the complexity of a compiler was using UNIX, mainframe and supercomputer operating systems without complaining about their complexity.
While verifying Z++, which will continue towards the end of year 2012, I thought I should answer the question of correctness before I hear similar claims. Indeed, there is a notion of complexity versus correctness. However, it is not of mathematical nature.
The complexity of an application cannot be reduced without reducing its functionality. A simple language provides fewer linguistic abstractions through the deception of delaying the complexity of implementation to programs written in that language. A major purpose of a language is to hide the complexity of computational notions behind linguistic abstractions. Thus, the implementation of a more evolved language is necessarily more complex.
Consider a language with a few built-in types and without user-defined mechanisms for conversion. Testing assignment of objects in this language is straightforward. In presence of conversions, the number of combinations rises in proportion to the number of built-in types times the number of ways conversions can be defined. Let us take a look at a part of a case from Z++.
String is a built-in type. Furthermore, one-dimensional arrays of characters, and pointers to characters can be assigned to objects of type string. A few type mechanisms that allow user-defined conversions are class, collection, task, union etc. So now, when assigning to an object of type string one has to check whether the right side is a string, array of characters, or pointer to characters. Then, one has to see whether a user-defined type on the right of the assignment provides one of two possible conversions. In particular if it provides both possible conversions the compiler must report the case as an error, asking that one of the conversions be specified with explicit cast.
The above is a simplified description of only one case. In addition consider that the compiler cannot be aware of values of objects. The run-time engine must be tested for boundary conditions such as assigning an empty string, or a null pointer. In particular, when the right-hand side is a null pointer, should the program crash or raise a suitable exception? This should give the reader a sense of complexity of testing. Missing any combination may result in unexpected random executions. We generally categorize the latter behavior as incorrectness.
The type of defect we just mentioned is not fundamental because once it is discovered it can be corrected without having to make fundamental changes to the implementation of the compiler and its run-time engine. Defects relating to the design are far more complicated to correct.
When testing reveals inadequacy in design developers generally resort to the wrong approach of patching. When you start erecting a pyramid at 45 degrees, and halfway through you realize you should have started at 43 degrees, patching will not give you the intended goal of a perfect pyramid. Instead, you must abandon the work and start over. On the other hand, localized implementation fixes are integral part of development. When you fine one stone of pyramid protruded, you fix the stone in place without collapsing the entire pyramid and starting over.
A touted design defect is the C++ exception mechanism. The design prevents the introduction of a linguistic abstraction for class-invariants. Instead, the programmer must do the work of the compiler and test for validity of invariants at end of each public function. This is an example of passing the complexity from the language on to the programs written in that language. Furthermore, the same defective design prevents the addition of resumption to C++ language. In effect, the code that discovers an invalid case with regard to invariants might as well terminate execution at that point instead of throwing an exception.
In general, when testing reveals an issue relating to a defect in design, the situation becomes hopeless. This is where, the imagination of designer, his tolerance in testing, and if necessary discarding the work of months becomes important. There is no glory in achieving the implementation of a defective design.
The main characteristic of software is its ability to evolve. The design determines the degree by which software can evolve. When the design becomes the consequence of a specific implementation, evolution gets locked up in the prison of the implementation. The evolution of a software product becomes possible when its implementation is only a service to a well-thought design.
Dr.Z. April 2012.
While verifying Z++, which will continue towards the end of year 2012, I thought I should answer the question of correctness before I hear similar claims. Indeed, there is a notion of complexity versus correctness. However, it is not of mathematical nature.
The complexity of an application cannot be reduced without reducing its functionality. A simple language provides fewer linguistic abstractions through the deception of delaying the complexity of implementation to programs written in that language. A major purpose of a language is to hide the complexity of computational notions behind linguistic abstractions. Thus, the implementation of a more evolved language is necessarily more complex.
Consider a language with a few built-in types and without user-defined mechanisms for conversion. Testing assignment of objects in this language is straightforward. In presence of conversions, the number of combinations rises in proportion to the number of built-in types times the number of ways conversions can be defined. Let us take a look at a part of a case from Z++.
String is a built-in type. Furthermore, one-dimensional arrays of characters, and pointers to characters can be assigned to objects of type string. A few type mechanisms that allow user-defined conversions are class, collection, task, union etc. So now, when assigning to an object of type string one has to check whether the right side is a string, array of characters, or pointer to characters. Then, one has to see whether a user-defined type on the right of the assignment provides one of two possible conversions. In particular if it provides both possible conversions the compiler must report the case as an error, asking that one of the conversions be specified with explicit cast.
The above is a simplified description of only one case. In addition consider that the compiler cannot be aware of values of objects. The run-time engine must be tested for boundary conditions such as assigning an empty string, or a null pointer. In particular, when the right-hand side is a null pointer, should the program crash or raise a suitable exception? This should give the reader a sense of complexity of testing. Missing any combination may result in unexpected random executions. We generally categorize the latter behavior as incorrectness.
The type of defect we just mentioned is not fundamental because once it is discovered it can be corrected without having to make fundamental changes to the implementation of the compiler and its run-time engine. Defects relating to the design are far more complicated to correct.
When testing reveals inadequacy in design developers generally resort to the wrong approach of patching. When you start erecting a pyramid at 45 degrees, and halfway through you realize you should have started at 43 degrees, patching will not give you the intended goal of a perfect pyramid. Instead, you must abandon the work and start over. On the other hand, localized implementation fixes are integral part of development. When you fine one stone of pyramid protruded, you fix the stone in place without collapsing the entire pyramid and starting over.
A touted design defect is the C++ exception mechanism. The design prevents the introduction of a linguistic abstraction for class-invariants. Instead, the programmer must do the work of the compiler and test for validity of invariants at end of each public function. This is an example of passing the complexity from the language on to the programs written in that language. Furthermore, the same defective design prevents the addition of resumption to C++ language. In effect, the code that discovers an invalid case with regard to invariants might as well terminate execution at that point instead of throwing an exception.
In general, when testing reveals an issue relating to a defect in design, the situation becomes hopeless. This is where, the imagination of designer, his tolerance in testing, and if necessary discarding the work of months becomes important. There is no glory in achieving the implementation of a defective design.
The main characteristic of software is its ability to evolve. The design determines the degree by which software can evolve. When the design becomes the consequence of a specific implementation, evolution gets locked up in the prison of the implementation. The evolution of a software product becomes possible when its implementation is only a service to a well-thought design.
Dr.Z. April 2012.
Labels: abstract language, ADA, C++, Complexity, software design, software development, Z++
posted by Dr.Z. at 2:06 PM
0 Comments:
Post a Comment
<< Back to Blogger Start Page >>