Re: Ada Generic vs. C++ Templates

[Colin_Paul_Gloster@ACM.org (Colin Paul Gloster)]

In article <9afpi0$irv$1@news.huji.ac.il>, Ehud Lamm wrote:

"Josef Widder <e9625114@student.tuwien.ac.at> wrote in message
news:MPG.1532ab1cc6ed7b4989682@news.chello.at...
> As project for university i'd like to compare the power of the Ada
> Generic construct relative to C++ templates.
>
> Could someone please tell me where to find good articles on the generic
> construct ?
>


In fact this is a pretty large subject. I'd restrict it to something more
managable (like "automatic instantiation vs. explicit instantiation" or the
way generic paramaters are specified etc.).

Some useful (I think) references are:
* the Ada83 Rationale chapter on generics
* Alexander Stepanov writings and intervies (some are available on the net,
and I gave URLs in this newsgroup a couple of times). He discusses some this
he considers shortcomings in Ada, as opposed to C++, as related to creating
the STL."

Specifically I would like to comment on the next bit before most of the
original content of this followup:
"* You may want to check specific uses. The are several examples of C++
temlate libraries that are hard if not impossible to mimic in Ada. Esp.
attempts at providing high-order programming facilties. (I don't have a URL
handy, but a search at http://lambda.weblogs.com should get you started. You
may also raise your question at that site)."

Do note that when The Booch Components were implemented in C++ the
implementation depended heavily on templates. Yet C++ did not have
concrete realisations of templates at the time. For example from page 6
of [2]:
"Type parameterization [..] Depending on a mechanism supporting this
abstraction was essentially a question of timing (of C++ language
release). In the end, we decided to provide an early implementation of
the  template  mechanism [Stroustrup88] as an interim measure."
and from page 7:
"Our design relied on several important abstraction concepts:
[..] type parameterization[..] We found the following mechanisms to be most
significant from a design perspective:
* [..]
*templates (type parameterization)
* [..]
* [..]
The existing (2.1) version of C++ provides mechanisms supporting the
first concept, future versions will support the next two[including
"templates (type parameterization)"], [..]"
and from page 8:
"We decided, instead, to built a filter which accepted the proposed C++
template mechanism. There are two parts to the mechanism: instantiating a
new class declaration, which happens upon encountering a declarative
use; and instantiating the class definition, which is done by
hand. Figure 11 illustrates how the template utility fits into the
compilation environment."
and from page 10:
"5.2 Conclusions
We found that the concepts of inheritance, composition, and type
parameterization were equally valuable aids in structuring the design.

[..]

It is nearly impossible to design a useful library of
collection/container data structures  without using type
parameterization. Implementing the template scheme proposed for C++ seems
to have been a reasonable investment for the resulting leverage gained
for this library.

C++ proved to be an effective language for implementing an
object-oriented design. The existing and planned features of C++
(especially templates and exceptions) are indeed useful for library
design. By conforming to the existing (and proposed)  standard C++
techniques, and adding a little support for features that are not yet
generally available, we were able to implement our design in C++."

Back to quoting Ehud Lamm:

"* Another thing that may be interesting is to check specific programming
styles. For example Ada's formal package paramters are a bit like using
classes to specify generic parameters, but they induce a different
programming style.

Any way, as I said, this is really a big subject. I suggest you check some
of these and focus your research on something a bit more specific. (Or more
general, like paramateric polymorphism in general).

I'd be glad to help. Email me or use the above mentioned site. (Or here, of
course).

Good luck,

Ehud Lamm"

Generics are used in The Booch Components (original Ada 83 version and
subsequent Ada 95 port). Pre-Ada 95 it was written on page 192 of "The
Design and Evolution of C++" [1] by Bjarne Stroustrup:
"[..Grady Booch implemented the Ada [83] version of The Booch Components
and he and Mike Vilot later implemented the C++ [of the time] version of
The Booch Components. The Ada [83] version] is 125,000 [since you
probably speak German I point out that 125,000 in English is equal to one
hundred and twentyfive thousand (big); not one hundrend and twentyfive
(small)] non-commented source lines compared to the C++ version's 10,000
[10000 not 10] lines - inheritance combined with templates can be a very
powerful mechanism for organising libraries without loss of performance
or clarity", referencing the second edition of "Object-oriented Analysis
and Design with Applications" by Grady Booch.

Remarkably Grady Booch and Mike Vilot did not mention this 12.5:1 ratio
in their paper "The Design of the C++ Booth Components" [2], ECOOP/OOPSLA
90 Proceedings October 21-25, 1990. Before I present extensive quoting
from [2] some of which still favourably rates the emerging C++ of the
time instead of Ada 83 despite the absence of an admission of such a
relative scale, see [3] for information on the porting of the C++ version
to Ada95 begun in 1994 (sic). Also you may find [4] useful.

You should probably be able to track down a copy of [2] if you do not
already have one. It may be stored as hardcopy paper in your library. If
not but you have access to the Association for Computing Machinery's
Digital Library then
http://WWW.ACM.org/pubs/citations/proceedings/oops/97945/p1-booch/ links
to an Adobe Acrobat .pdf version of the paper of size 1095370 bytes. If
you are not a paid up subscriber to the ACM DL (you do not seem to be as
the Find-A-Member facility did not show you on a search for
"Widder") perhaps your library is or perhaps one of your lecturers is. Be
warned however that this year some portions of the ACM website have been
a bit slow/unusable/unreachable.

Okay, excerpts from [2] follow.

Paragraph 3 of page 1:
"A key insight gained from this project: the design process centered on
developing a "template for the templates" - designing a component
framework and orderly process for generating the template classes."

Top of righthandside column on page 1:
"We learned an important lesson about designing with multiple class
lattices: the tradeoffs of various inheritance structures turned out to
be a fundamental design issue."

Top of righthandside column on page 4:
"3 Design - Key Abstractions
In the design of the library s key abstractions, we addressed four
fundamental issues:
* How to use inheritance
[..]

3.1 Using Inheritance
A drawback to the Ada design was redundancy: significant portions of the
library had similar, but slightly different implementations. This made it
an obvious candidate for implementation in an object-oriented programming
language. The use of inheritance was the most significant change in going
from an object-based design to an object-oriented one. The main issue was
whether or not to be "completely object-oriented" or just apply it where
it proved to be useful and effective. We chose a "forest" approach over a
"tree" approach for three reasons:

[..]"

On page 6:
"[..] we decided to provide an early implementation of the
"template" mechanism [Stroustrup88] as an interim measure."

Also on page 6:
"Clients can also avoid the overhead of indirect function calls in cases
where such performance issues are important. This exploits the difference
between in-line expansion during template compilation, and passing
function pointers in constructors during object creation."

From page 7:
"One aspect of exceptions in C++ not present in Ada is the opportunity to
combine them with inheritance. This provides a natural classification
mechanism (and the corresponding extensibility and flexibility to
clients)."

From page 7:
"4 Implementation - Mechanisms in C++
C++ provides many features that are helpful to those implementing
software intended for reuse. Indeed, much recent activity in evolving the
language has been specifically geared towards supporting library
development. Our design relied on several important abstraction
concepts: encapsulation, inheritance, composition, type parameterization,
exceptions, and concurrency. We found the following mechanisms to be most
significant from a design perspective:
*classes (especially inheritance)
*templates (type parameterization)
*exceptions (as a uniform error reporting mechanism)
* [..]
The existing (2.1) version of C++ provides mechanisms supporting the
first concept, future versions will support the next two, [..]"

Page 8 includes:
"The data structure classes simply invoke new and de1ete operations as
required. This turned out to be far simpler than the original Ada design,
which required a completely different syntax when using the library's
Storage Manager instead of the predefined free store operators."

Importantly on page 8:
"4.2 Templates Because type parameterization is central to the design of
the library, Ada's generic facility was widely used in the original
version."

Lower righthandside of page 9:
"5 Summary
The design of this library focused on:
[..]
* ways to structure and combine forms into templates
* effective implementation (C++ language features) of the mechanisms
(made easier with the addition of specific support)

The central design activity was careful consideration of the basic
"building block" components (the core data structures, the storage
managers). The key insight was designing a simple way of composing them
into the various templates in the library."

From page ten:
"It is nearly impossible to design a useful library of
collection/container data structures  without using type
parameterization. Implementing the template scheme proposed for C++ seems
to have been a reasonable investment for the resulting leverage gained
for this library.

C++ proved to be an effective language for implementing an
object-oriented design. The existing and planned features of C++
(especially templates and exceptions) are indeed useful for library
design. By conforming to the existing (and proposed) "standard
C++" techniques, and adding a little support for features that are not
yet generally available, we were able to implement our design in C++."

References and footnotes
/\/\/\/\/\/\/\/\/\/\/\/\
[1] "The Design and Evolution of C++" by Bjarne Stroustrup, ISBN
0-201-54330-3, published by Addison Wesley, there is a review on
http://www.accu.org/bookreviews/public/reviews/d/d000452.htm

Note that this is unlikely to be the book Georg Bauhaus
<sb463ba@l1-hrz.uni-duisburg.de> of Gerhard-Mercator-Universitaet -
Gesamthochschule Duisburg mentioned with timestamp Wed, 4 Apr 2001
13:24:26 +0000 (UTC) in
news:9af7aa$5io$1@a1-hrz.uni-duisburg.de
: "Bjarne Stroustrup's Book, 3rd ed., says where C++ templates
originally came from, namely a now outdated version of Ada
and CLU." That book is probably "The C++ Programming Language".

[2] "The Design of the C++ Booth Components" by Grady Booch and Michael
Vilot, ECOOP/OOPSLA  90 Proceedings October 21-25, 1990.
Permission to copy without fee all or part of this [the ECOOP/OOPSLA
paper] material is granted provided that the copies are not made or
distributed for direct commercial advantage, the ACM copyright notice and
the title of the publication and its date appear, and notice is given
that copying is by permission of the Association for Computing
Machinery. To copy otherwise, or to republish, requires a fee and/or
specific permission. (C) 1990 ACM 083791-411-2/90/0010-0001...$1.50

[3] HTTP://WWW.AdaPower.com/booch/overview.html	last updated in June 2000

[4] HTTP://WWW.AdaPower.com/original_booch/ which has amongst other
things Ada 83 and Ada 95 implementations' source code.	Last updated in
November 2000.

-- 
This signature file is included in protest against the hosting of Nazi
facist propaganda "Mein Kampf" written by Adolf Hitler on the Dublin City
University Networking Society (committee@RedBrick.DCU.Ie, DCU Networking
Society, c/o Clubs and Socs Office, The Hub, DCU, Glasnevin, Dublin 9,
Ireland) website at HTTP://WWW.RedBrick.DCU.Ie/~mellow/Adolf/ by
R. O'Brien whose username is mellow. On 22nd March 2001 Dublin City
University webmaster Niall O'Leary (niall.oleary@DCU.Ie, +353-1-700 5864, 
Room C203, Computer Services Department, Henry Grattan Building, DCU,
Glasnevin, Dublin 9, Ireland) authorised "Mein Kampf" to be on the
Internet via DCU and HEAnet (info@HEAnet.Ie, +353-1-6623412, HEAnet Ltd.,
Ground Floor, Marine House, Clanwilliam Court, Dublin 2, 
Ireland) resources. Please also complain to The President's Office, DCU,
Glasnevin, Dublin 9, Ireland, dcupres@DCU.Ie.