Re: Discriminated records/Language Design Error(?)/COmpiler Bug(?)

Re: Discriminated records/Language Design Error(?)/COmpiler Bug(?)

[cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!spool.mu.ed]

In article <CDtszF.33M@bandelier.cs.unm.edu> 
  shapiro@bandelier.cs.unm.edu (Henry Shapiro) writes:

>DESPITE THE FACT THAT I USE/TEACH ADA I DON'T READ THIS NEWSGROUP VERY OFTEN S
O 
>PLEASE E-MAIL ANY RESPONSES TO shapiro@cs.unm.edu AS WELL AS POSTING THEM
>TO THE NEWSGROUP.  I THINK/HOPE THIS IS OF GENERAL INTEREST.
>
>Consider the following, which is from an Ada program I develop and
>describe in a case studies book I am writing for a beginning software
>engineering class.
>-- An infinite precision arithmetic package that uses the "infinite array"
>--   representation.  A (nonnegative) infinite precision integer is stored
>--   as a discriminated record, which contains an array of the correct length.
>
>package LONG_ARITHMETIC is
>  type LONG_INTEGER is private;
>    -- The normal, language defined meaning of  :=  and  =  can be used.
>    -- Furthermore, operators like + can be overloaded so that they appear
>    -- to the user as normal operators.
> ... [ stuff deleted] ...
>  -- THIS IS THE RELEVANT PART
>  type LONG_INT(NUM_DIGITS: NATURAL := 0) is
>	 record
>	   INITIALIZED: BOOLEAN := FALSE;
>	   NUMBER: DIGIT_ARRAY(1..NUM_DIGITS);
>	 end record;
>  -- This extra layer is needed to prevent the discriminant field from being
>  --   user visible.
>  type LONG_INTEGER is
>	 record
>	   NUM: LONG_INT;
>	 end record;
>end LONG_ARITHMETIC;
>
>All three of the Ada compilers here at the University of New Mexico produce
>errors when this program is run (with the corresponding body and driver).
>They behave as follows
>DEC Ada (for the DECstation under Ultrix)
>  Compiles the program as written, but raises CONSTRAINT_ERROR at runtime
>SUN Ada (for the Sun 4 under SunOS Release 4.1.1 [some version of Unix]).
>  Compiles the program as written (with a warning), but raises
>    STORAGE_ERROR at runtime.
>IBM Ada (for the RS/6000 under AIX)
>  Produces a compile time error message and will not compile the program.
>
>If NATURAL is redefined to be
>  subtype NATURAL is INTEGER range 0..1000;
>then the program works fine on all three systems (but of course the
>maximum number of digits in a LONG_INTEGER) is 1000.
>
>THE PROBLEM:
>  It appears that the compilers allocate the maximum amount of space
>  the discriminated record can possibly use, whether that much is used
>  or not.  Now this is easy for the compiler writer -- he/she just allocates
>  a fixed amount of storage and as objects of type LONG_INTEGER are reassigned
>  the amount of storage that is used within what is allocated varies, but
>  no storage management is required.  THIS MAY OR MAY NOT BE ALLOWED BY
>  THE STANDARD -- I've heard it argued that raising an exception when
>  the object is allocated doesn't violate a strict reading of the rules.
>  On the other hand, this form/use of discriminated records is pretty
>  worthless if
>    (1) the user has to declare his objects to have a maximum length --
>	the whole point of the exercise is to not be so limited.
>    (2) the amount of storage is always the maximum amount possible -- there
>	is no savings.
>  The examples at the end of Section 3.7.1 don't really clarify the situation.
>
>HAS THIS PROBLEM BEEN RESOLVED IN ADA-ISSUES?  HAS IT BEEN DISCUSSED IN
>THIS NEWSGROUP?  ARE THERE ANY OPINIONS ABOUT THIS?  DOES ANYBODY HAVE
>A COMPILER THAT DOESN'T DO THIS/WORKS "CORRECTLY".

I believe the Alsys compiler, in at least one of its incarnations,
uses an implicit level of indirection for stand-alone objects when the
type is similar to your "LONG_INT," but even the Alsys compiler does
not use this level of indirection for record components (I think).
Several compilers use an implicit level of indirection always for
dynamic arrays, including as components.  This includes RR, Meridian,
and perhaps Irvine (and TLD?).

Whether or not it is a "good thing" to provide an implicit level of 
indirection, with the requirement for automatic deallocation/reallocation 
on size-growing assignment is a matter of some debate.  There are those
who believe as you do that any compiler worth its "salt" will do the
"right thing" here and grow and shrink automatically.  There are others
(myself included) who believe that it is part of the philosophy of
Ada as a systems-programming language that there should be minimal
"implicit" semantics, and the programmer should use abstraction to
handle growing and shrinking.  

One reason is that as you go down the path between 
fully static allocation, and more and more automatic/dynamic
allocation/reallocation, the level of control and predictability
decreases.  Ada essentially requires support for some amount of
non-compile-time-known-sized allocation, but all local variable allocation 
can be handled with strictly mark/release data structures, since the size
of an object need not change after creation.
 
In C and C++, all local variables have compile-time-known size.  Languages
like SmallTalk and Eiffel have an implicit level of indirection for
almost everything, and provide full garbage collection, and the size
of an object can be "thought of" as changing dynamically, though even
in Eiffel and Smalltalk, the data objects don't change in size, it is 
the implicit pointers that change to point to a new data object, while
the old data object generally becomes susceptible to garbage collection.

Unfortunately, as you have no doubt recognized, Ada 83 does not provide
sufficient user control over equality, assignment, and finalization,
to allow you to define an indefinitely extensible data structure like
you want, while still using the familiar ":=" syntax for assignment
and relying on scope exit for automatic reclamation of storage.
You can do it with limited types, and explicit "Assign" and "Free"
procedures, but that is not very satifying.

This problem has been addressed in Ada 9X, with "controlled types" which
allow users to define operations that are invoked automatically
during assignment and scope exit.  With a controlled type, you could
represent your numbers as a linked list of "chunks," each containing
some number of the digits (e.g. 10).  By using fixed-size chunks, you
could easily and efficiently recycle storage as the number of digits
required grew and shrank, and you could choose to use reference
counts rather than deep copy to minimize the overhead of assigning large
values.  

Now of course this isn't as quick and easy as just having the compiler
do the "right thing" and do automatic deallocation/reallocation on
size-growing assignment.  However, it is almost certain that you could
implement a more efficient and application-appropriate storage management
approach than any sort of default approach the compiler would use.
And of course, there will always be data structures, like trees, that there
is no way the compiler is going to be able to automagically do the
right thing on assignment and finalization.

If you are just prototyping a quick example, it is very frustrating to
do things the "long way" when if the compiler would just "do what I mean"
it would all be straightforward.  However, the advantage of getting the
compiler out of the way is that there is less "hidden" overhead in
the semantics of the language, the compiler is simpler (every little bit
helps with Ada ;-), and you can tailor the representation and storage
management strategy to your application.

So... to make a long story short, we have not created a requirement in Ada 9X.
that compilers do automatic deallocation/reallocation on discriminant-changing
assignments.  Instead, we have beefed up the data abstraction support
in Ada 9X so that programmers can more completely control assignment
and finalization, and do for themselves exactly what they want, rather
than having to "hope" the compiler used a strategy that was ideal for
their application.  This reflects our philosophy that Ada 9X should
be an excellent systems programming language, for building production
quality, reliable, long-lived systems.  This may mean that it will be
less ideal for the "quick and easy" problems, but hopefully a growing
war-chest of reusable components (e.g. generic packages, etc.) can help.

>Henry D. Shapiro
>The University of New Mexico
>shapiro@cs.unm.edu

S. Tucker Taft
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138