Re: Ada.strings.bounded problems?

Re: Ada.strings.bounded problems?

[Robert Dewar]

Tarjei, you can certainly write a generic package on top of bounded
strings. Simply include a parameter that is a formal derived pacakge,
then the user of your generic will supply the instantiation.

In GNAT, we are thinking of redoing the bounded strings so that they lie
on top of a non-generic package where there is a discriminant giving the
maximum length.

Not only will this avoid unnecessary duplication of code, but we could
also think of giving direct access to the underlying package. Of course
programs that took advantage of this would be potentially non-portable
(although not really, they could just include the GNAT version of these
packages, even if they were using some other compiler).

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <TARJEIJ.95Jan11183331@ulrik.uio.no>, tarjeij@ulrik.uio.no
(Tarjei Jensen) writes: 

|> How can anybody create generic string packages when there is an abundance of
|> bounded string types around and none are compatible? It looks like a mess to
|> me. I am used to think of (bounded) strings much like integers; they come in
|> different sizes, but are basically compatible.

Answer 1:  Base it on unbounded strings instead.

Answer 2: Use generic formal packages: 

   with Ada.Strings.Bounded;
   generic
      package Bounded_String_Instance is
         new Ada.Strings.Bounded.Generic_Bounded_Length (<>);
   package Generic_Additional_Bounded_String_Facilities is
      ...
   end Generic_Additional_Bounded_String_Facilities;


   Use of the package: 
   -------------------

   with Ada.Strings.Bounded;
   package Bounded_80 is new Ada.Strings.Bounded.Generic_Bounded_Length(80);

   with Bounded_80, Generic_Additional_Bounded_String_Facilities;
   pragma Elaborate (Generic_Additional_Bounded_String_Facilities);
   package Additional_Bounded_80_Facilities is
      new Generic_Additional_Bounded_String_Facilities (Bounded_80);

   with Bounded_80, Additional_Bounded_80_Facilities;
   procedure Client is
      ...
   end Client;

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Ada.strings.bounded problems?

[Robert Dewar]

Robert Eachus says just use the Bounded Strings package and it should do
just what you want.

Suppose what you want is the following (easily provided by PL/1 for example).

I want several different strings, all bounded, with different maximum lengths,
and I want to be easily able to do operations between them.

True I can do:

      if To_String (A) = To_String (B) then

but first of all, it is annoying to have to write the To_String calls, and
second, I will be willing to bet that all compilers will generate extra
copies to implement this (at least one for each call, and possibly more
than one).

I think that's the sort of thing that was being requested ...

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <D29L78.J9@nntpa.cb.att.com>, ka@socrates.hr.att.com
(Kenneth Almquist) writes: 

|> Tarjei Jensen <tarjeij@ulrik.uio.no> wrote: 

|> This is definitely a weakness of Ada.  There is no way to implement a
|> single bounded string type that can be constrained to implement various
|> maximum string lengths.  It would not be too hard to add a bounded
|> arrays (a generalization of bounded string) to Ada, but I don't recommend
|> it, given the current complexity of Ada.

This is definitely a weakness of Jensen's understanding of Ada.

There IS a way to implement bounded strings with the bound given as a
constraint, so simple that it is found in many introductory examples: 

   package Bounded_Strings is
      type Bounded_String (Max_Length: Positive) is private;
      ...  -- all sorts of useful operations
   private
      type Bounded_String (Max_Length: Positive) is
        record
           Current_Length : Natural := 0;
           Text           : String (1 .. Max_Length);
        end record;
   end Bounded_Strings;

This approach is easily generalized to other kinds of arrays.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Ada.strings.bounded problems?

[Robert Dewar]

Kenneth says it is a weakness of Ada that you cannot implement bounded
strings of different lengths.

Sorry I don't see this at all, a type like

   type str (max_length : natural) is record
      current_length : natural;
      S : String (1 .. Max_Length);
   end record;

will do just fine, what's the problem?

In fact we were thinking of implementing the Ada 95 bounded string in terms
of this abstraction.

Re: Ada.strings.bounded problems?

[Tarjei Jensen]

In article <3f3rl7$kts@watnews1.watson.ibm.com> ncohen@watson.ibm.com (Norman H. Cohen) writes:


>   This is definitely a weakness of Jensen's understanding of Ada.
>
>   There IS a way to implement bounded strings with the bound given as a
>   constraint, so simple that it is found in many introductory examples: 
>
>      package Bounded_Strings is
>	 type Bounded_String (Max_Length: Positive) is private;
>	 ...  -- all sorts of useful operations
>      private
>	 type Bounded_String (Max_Length: Positive) is
>	   record
>	      Current_Length : Natural := 0;
>	      Text           : String (1 .. Max_Length);
>	   end record;
>      end Bounded_Strings;
>

The problem is not to find _a_ defininition. The problem is to have _one_
standard variable length bounded_string type that can be used by all packages
(libraries).

There should be no need for me to edit packages to make them use my personal
bounded string type (and I don't want to end up with nearly all modules being
generic).



Greetings,
 
 
--
// Tarjei T. Jensen 
//    tarjeij@ulrik.uio.no       || +47 51 563411
//   Support you local rescue centre: GET LOST!
// Working, but not speaking for the Norwegian Hydrographic Service.

Re: Ada.strings.bounded problems?

[Mats Weber]

In article <3f3rl7$kts@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote:

> There IS a way to implement bounded strings with the bound given as a
> constraint, so simple that it is found in many introductory examples: 
> 
>    package Bounded_Strings is
>       type Bounded_String (Max_Length: Positive) is private;
>       ...  -- all sorts of useful operations
>    private
>       type Bounded_String (Max_Length: Positive) is
>         record
>            Current_Length : Natural := 0;
>            Text           : String (1 .. Max_Length);
>         end record;
>    end Bounded_Strings;
> 
> This approach is easily generalized to other kinds of arrays.

The BIG problem with this approach is that testing two Bounded_Strings for
equality is erroneous (Ada 83 terminology). In Ada 95, this would be a
bounded error, but two bounded strings may compare different while being
logically equal. The problem comes from the unused characters in Text
beyond Max_Length.

Mats

Re: Ada.strings.bounded problems?

[Mats Weber]

In article <3f3jlh$kts@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote:

>    [beginning if example deleted]
> 
>    with Bounded_80, Generic_Additional_Bounded_String_Facilities;
>    pragma Elaborate (Generic_Additional_Bounded_String_Facilities);

Is this pragma still necessary in Ada 95 ? I thought some Ada 95 rule
removed its need for the case of generic units.

>    package Additional_Bounded_80_Facilities is
>       new Generic_Additional_Bounded_String_Facilities (Bounded_80);

Mats

Re: Ada.strings.bounded problems?

[Robert Dewar]

Mars worries whether the use of unbounded strings is incompatible with
programs that run for ever.

Not at all, or more accurately, no more or less incomaptible than any use
of the heap. You have to make sure that you don't have memory leaks in
your implementation, and that you have sufficient heap memory to avoid
fragmentatino problems, but other than that ...

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <Mats.Weber-1701951908250001@mlma11.matrix.ch>,
Mats.Weber@matrix.ch (Mats Weber) writes: 

|> In article <3fduto$ta7@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote: 
|>
...
|>
|> > Ada 95 allows predefined equality to be overridden, even for nonlimited
|> > types, so the declaration of a type Bounded_String with a discriminant
|> > specifying the maximum length should be accompanied by the declaration
|> > for the following function: 
|> >
|> >    function "=" (Left, Right: Bounded_String) return Boolean is ...
|>
|> This helps some, but still has severe problems. For instance if I write
|>
|>    type Pair is
|>       record
|>          First,
|>          Second : Bounded_String;
|>       end record;
|>
|> then "=" is broken for Pair. This situation is very bad because overriding
|> "=" on Bounded_String gives the programmer the feeling that the problem is
|> solved, but it reappears whenever a Bounded_String is used as a component
|> of a composite type.

Yes, but Ada 9X provides a straightforward solution for this too.  If a
private type is implemented as a tagged type with user-defined "=", then
equality tests for composites containing the private type invoke the
user-defined "=".  (See RM95 4.5.2(15) and 4.5.2(24).  In paragraph 24,
it is unclear whether a component belonging to a private type with a
tagged implementation is a "tagged component", but because of paragraph
15, it doesn't matter.)

Thus, what we have to write is: 

   package Interoperable_Bounded_Strings is
      type Bounded_String (Max_Length: Natural) is private;
      function "=" (Left, Right: Bounded_String) return Boolean;
      ...
   private
      type Bounded_String (Max_Length: Natural) is
         tagged record
            Current_Length : Natural;
            Text           : String (1 .. Max_Length);
         end record;
   end Interoperable_Bounded_Strings;

Because we have added the word "tagged" to the full-type declaration,
predefined "=" for type Pair will now invoke user-defined "=" for type
Bounded_String.

(This is not the usual use for tagged types, since, even though the full
type can be extended in the body or in a private child package, this is
unlikely to happen.  In this case, the type is declared tagged solely so
that the new composition rules for "=" will apply to it.  Tucker Taft
will correct me if I am wrong, but I believe that these are the rules he
would have liked to apply to ALL types if he had been starting with a
blank slate.  Upward compatibility with Ada 83 constrained him to "do the
right thing" only for tagged types, which of course do not arise in
Ada-83 programs.)

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Ada.strings.bounded problems?

[Cyrille Comar]

Mats.Weber@matrix.ch (Mats Weber) writes:
: 
:    type Pair is
:       record
:          First,
:          Second : Bounded_String;
:       end record;
: 
: then "=" is broken for Pair. This situation is very bad because overriding
: "=" on Bounded_String gives the programmer the feeling that the problem is
: solved, but it reappears whenever a Bounded_String is used as a component
: of a composite type.

This is not true if Bounded_String is implemented as a tagged type
since in this case the *primitive* "=" on Bounded_String is used in
the *predefined* "=" on Pair. So there is a way of having it safe...
Although implementing Bounded_String as a tagged type just for that
purpose seems an overkill.

-- 
------------------------------------------------------------------------
Cyrille Comar,                                  E-mail: comar@cs.nyu.edu
Gnat Project                                    US phone: (212) 998-3489

Re: Ada.strings.bounded problems?

[Robert Dewar]

I think probably the best thing if you want to follow this idea for
bounded strings is to make them a limited type and live with the
inconvenience of no initialization. 

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <3fja22$fab@source.asset.com>, weisek@source.asset.com (Kevin
Weise) writes: 

|> I know!  I know!  The traditional response to this is that a good
|> optimizing compiler will remove the discriminant. But in practice, I
|> haven't seen this happen.
...
|>                      Perhaps, if this is truly possible, GNAT may make
|> some inroads in this area of optimization.

It isn't always a win.  If you pass a discriminated object to a procedure
with an unconstrained parameter (which is possible even if the
discriminant has no default initial value), and if the actual does not
have a discriminant stored with it, you have to either pass the
discriminant as a hidden extra parameter or make a copy of the actual
that does have the discriminant.  If you have an access type designating
a type with nondefaulted discriminants, you must store discriminants of
the designated objects either with the objects themselves or with the
pointers.  Which one saves more space or time depends on the relative
numbers of objects pointed to and objects pointing at them.

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Ada.strings.bounded problems?

[Keith Thompson]

In <Mats.Weber-1701951908250001@mlma11.matrix.ch> Mats.Weber@matrix.ch (Mats Weber) writes:
> In article <3fduto$ta7@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote:
> > Ada 95 allows predefined equality to be overridden, even for nonlimited
> > types, so the declaration of a type Bounded_String with a discriminant
> > specifying the maximum length should be accompanied by the declaration
> > for the following function: 
> > 
> >    function "=" (Left, Right: Bounded_String) return Boolean is ...
> 
> This helps some, but still has severe problems. For instance if I write
> 
>    type Pair is
>       record
>          First,
>          Second : Bounded_String;
>       end record;
> 
> then "=" is broken for Pair. This situation is very bad because overriding
> "=" on Bounded_String gives the programmer the feeling that the problem is
> solved, but it reappears whenever a Bounded_String is used as a component
> of a composite type.

Interesting.  This is a potential problem that didn't occur (as seriously)
in Ada 83.  Since Ada 83 only allowed "=" to be overloaded for limited
types, and a type with a limited component is also limited, a type with
a subcomponent that has a user-defined "=" operator generally wouldn't
have its own "=" operator unless the user explicitly defined one (unless
you used the generic trick).

In Ada 95, it's very easy to have a case like the above where the
user-defined "=" operator for a subcomponent is bypassed.  Section II-6.3
of the Rationale, which discusses overloading of "=" and "/=", doesn't
mention this problem.  Quite possibly it was simply overlooked.

It's obviously too late to fix this in the language by requiring
predefined "=" to invoke user-defined "=" for subcomponents.

I suggest that Ada 95 compilers should issue a warning for a type
whose predefined "=" operator bypasses a user-defined "=" operator
for a subcomponent.  Determining exactly when to issue such a warning
may be difficult ("=" can be declared to return a type other than
Standard.Boolean, the left and right operands can be different types,
"=" and "/=" can be overloaded separately in some circumstances, the
declaration for "=" needn't be in the same scope as the operand type(s),
etc.), but catching the most common cases shouldn't be difficult.

-- 
Keith Thompson (The_Other_Keith)  kst@thomsoft.com (kst@alsys.com still works)
TeleSoft^H^H^H^H^H^H^H^H Alsys^H^H^H^H^H Thomson Software Products
10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2718
When you're a nail, every problem looks like a hammer.

Re: Ada.strings.bounded problems?

[Mats Weber]

In article <3fj8gs$h9b@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote:

> (This is not the usual use for tagged types, since, even though the full
> type can be extended in the body or in a private child package, this is
> unlikely to happen.  In this case, the type is declared tagged solely so
> that the new composition rules for "=" will apply to it.  Tucker Taft
> will correct me if I am wrong, but I believe that these are the rules he
> would have liked to apply to ALL types if he had been starting with a
> blank slate.  Upward compatibility with Ada 83 constrained him to "do the
> right thing" only for tagged types, which of course do not arise in
> Ada-83 programs.)

So sad ! I think it is the biggest defect I know of in Ada 95.

Mats

Re: Ada.strings.bounded problems?

[Jacob Sparre Andersen]

Keith Thompson (kst@alsys.com) wrote:

[ Mats.Weber@matrix.ch and ncohen@watson.ibm.com wrote about problems with 
  implementing Bounded_String. ]

|^^^^^^^^^^
| In Ada 95, it's very easy to have a case like the above where the
| user-defined "=" operator for a subcomponent is bypassed.  Section II-6.3
| of the Rationale, which discusses overloading of "=" and "/=", doesn't
| mention this problem.  Quite possibly it was simply overlooked.
|
| It's obviously too late to fix this in the language by requiring
| predefined "=" to invoke user-defined "=" for subcomponents.
|
| I suggest that Ada 95 compilers should issue a warning for a type
| whose predefined "=" operator bypasses a user-defined "=" operator
| for a subcomponent.  Determining exactly when to issue such a warning
| may be difficult ("=" can be declared to return a type other than
| Standard.Boolean, the left and right operands can be different types,
| "=" and "/=" can be overloaded separately in some circumstances, the
| declaration for "=" needn't be in the same scope as the operand type(s),
| etc.), but catching the most common cases shouldn't be difficult.
|__________

I agree with KT's suggestion about compiler warnings.
Is it allready time to start writing down what to do with Ada0X? Is somebody 
making a (mental) note of this problem for the '0X team, and where should 
such comments be sent?

Regards,
                Jacob Sparre Andersen
--
A good movie? - What about three? - Kieslowskis 'White', 'Blue' and 'Red'!
--
URL's: "mailto:sparre@nbi.dk", "http://meyer.fys.ku.dk/~sparre", 
       "mailto:sparre+@pitt.edu" & "http://www.pitt.edu/~sparre".
--
"We need a plan to diverge from", Fesser

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <1995Jan19.124412@lglsun.epfl.ch>, nebbe@lglsun.epfl.ch
(Robb Nebbe) writes: 

|> There couldn't have been any upward compatibility problems since you
|> couldn't override "=".

That's what Jean Ichbiah thought, but John Goodenough proved him wrong.

(A loophole resulted from the fact that you could override "=" for a
generic formal limited private type, but you could pass a nonlimited type
as the corresponding generic actual parameter.)

In any event, there is an upward compatibility problem with Ada-83
limited types: 

   package P is
      type T is limited private;
      function "=" (Left, Right: T) return Boolean;
      type R is
         record
            C: T;  -- makes R limited
            ...
         end record;
   private
      type T is ...;
   end P;

   package body P is
      -- Neither T nor R is limited here, so R has an "=" operator, but
      --    it uses predefined "=" for type T to compare Left.C and Right.C.
   end P;

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Ada.strings.bounded problems?

[Robert Dewar]

"The traditional response is that a good optimizing compiler will remove
the discriminant"

Not likely, this is a VERY hard optimization, and not one that I have seen
any Ada compiler do except in VERY specific cases.

Re: Ada.strings.bounded problems?

[Robb Nebbe]

In article <1995Jan19.185316.2225@nbivax.nbi.dk>,
sparre@meyer.fys.ku.dk (Jacob Sparre Andersen) writes:

|> 
|> I agree with KT's suggestion about compiler warnings.
|> Is it allready time to start writing down what to do with Ada0X? Is somebody 
|> making a (mental) note of this problem for the '0X team, and where should 
|> such comments be sent?
|> 
|> Regards,
|>                 Jacob Sparre Andersen

There should probably be a section in the programming FAQ about
these cases where the semantics of the language are goofy (if
not outright wrong). If you wrote something up I'm sure Magnus
would include it in the FAQ.

Robb Nebbe

Re: Ada.strings.bounded problems?

[Magnus Kempe]

In article <1995Jan20.120612@lglsun.epfl.ch>, nebbe@lglsun.epfl.ch (Robb Nebbe) writes:
: 
: There should probably be a section in the programming FAQ about
: these cases where the semantics of the language are goofy (if
: not outright wrong). If you wrote something up I'm sure Magnus
: would include it in the FAQ.

I'd rather see it fixed in the language than described in the FAQ :-)

Anyway, if you want to see something added to the FAQ, write it (the
question _and_ answer, not just the question) and email it to me.

The case of "lost equality" is actually quite unfortunate, because there
is no justification in trying to preserve "backward compatibility".  If
some reckless soul did use the "Goodenough trick" in production code,
they would have to check their code, but that'd hardly be an undeserved
task (and that's what a reckless course of action is about).

It really turns out to be a major failure for type composition.
User-defined equality should be treated like user-defined control.
It should transparently compose, not be shackled with tags and
obscure rules.  "Free Equality!"

Maybe an artistic interpretation of RM 9X 4.5.2(14) could declare
that what the paragraph intended was
  For a type extension, predefined equality is defined in terms of the
  primitive (possibly user-defined) equals operator of the parent type
  and of the components of the extension part.

instead of
  For a type extension, predefined equality is defined in terms of the
  primitive (possibly user-defined) equals operator of the parent type
  and of any tagged components of the extension part, and predefined
  equality for any other components not inherited from the parent type.

And then another artistic interpretation would say that RM 9X 4.5.2(24)
really means
  Otherwise, the result is defined in terms of the primitive equals
  operator for any matching components.

instead of
  Otherwise, the result is defined in terms of the primitive equals
  operator for any matching tagged components, and the predefined equals
  for any matching untagged components.

If artists are not permitted to offer their interpretations of rm9x, we
can still go for GNAT, add a -artistic option, and ask other compiler
vendors to do the same.  Finally, note that comments on rm9x should be
sent to ada-comment@sei.cmu.edu, following the format described in the
introduction of the reference manual.  I don't know how artistic the
interpretations will be, though.


Don't ask me what I think of the selection of operations for "generic
formal derived types" that are not "formal private extensions" (12.5.1).
-- 
Magnus Kempe		"I know not what course others may take, but as for me,
Magnus.Kempe@di.epfl.ch  Give me Liberty... or give me Death!" -- Patrick Henry

Re: Ada.strings.bounded problems?

[Robert Dewar]

There would be problems in implementation of generics with shared code if   
equal were always compositional. Certainly a consideration (it would mean
that equality had to be passed in for all types, quite expensive).

Second: it IS possible to define equality on non-limited types in Ada 83
using the generic trick. This trick is well known, and widely used, so you
cannot ignore it in considering upwards compatibility.

Re: Ada.strings.bounded problems?

[Robert Dewar]

Mats says:

"So sad ! I think it is the biggest defect I know of in Ada 95."
[it is not having introduced the upwards incompatible feature of user
defined equality being compositional]

Gosh Mats, if that's the biggest defect, then Ada 95 must be in
*very* good shape!

Re: Ada.strings.bounded problems?

[Robert Dewar]

Magnus may not like the fact that you can legitimately override equality
for non-limited types in Ada 83, but you can, and it is well known how
to do it.

Upwards compatibility means that existing code must work, it does not mean
that existing code that meets Magnus' criterion for what he thinks is OK
must work!

Also, as Norm points out, the incompatibility extends beyond the use of
the Goodneough tecnnique for redefinition of equality.

It's easy to get heated up over minor things in the environment of suitable
heated statements, but in practice I think this is a fairly small issue.
After all it is up to an Ada 95 programmer whether to take advantage
of the new capability or not. It will often mean that the proper decision
is to either make the type limited or tagged. 

It is important to realize the hit on shared generics. THe design of Ada 95
has been carefully done to preserve the practicality of using shared
generics, as is currently done by at least two implementations. In particular,
suppose we have a simple generic with some discrete types as arguments. It
seems unfortunate (both in terms of implementation complexity, and in 
efficiency) to require all equality operations to be done with thunks.

Note that in the case of tagged types, the comparison operations are complex
in any case, and often dispatching, so it is not a significant additional
burden (just always dispatch inside the shared generic).

As is so often the case in language design, delicate compromises are the
order of the day. THis is particularly true when upwards compatibility
must be maintained. It is true that the upwards compatibility criterion 
can result in some compromises that one might prefer not to settle for
(look after all at C and C++!) Some during the ADa 95 felt that we were
not adventurous enough in being incompatible, and some thought we should
have been much MORE compatible. I think that the middle path steered was
about right.

Note incidentally that the non-upwards compatibilities here are of the
worst possible kind: old code compiles fine and executes giving wrong
results.

Re: Ada.strings.bounded problems?

[Tucker Taft]

In article <1995Jan18.164836.2222@nbivax.nbi.dk>,
Jacob Sparre Andersen <sparre@meyer.fys.ku.dk> wrote:

>Mats Weber (Mats.Weber@matrix.ch) wrote:
>| In article <3fduto$ta7@watnews1.watson.ibm.com>, 
>| ncohen@watson.ibm.com wrote:
>| >    function "=" (Left, Right: Bounded_String) return Boolean is ...
>|
>| This helps some, but still has severe problems. For instance if I write
>|
>|    type Pair is
>|       record
>|          First,
>|          Second : Bounded_String;
>|       end record;
>|
>| then "=" is broken for Pair. This situation is very bad because overriding
>| "=" on Bounded_String gives the programmer the feeling that the problem is
>| solved, but it reappears whenever a Bounded_String is used as a component
>| of a composite type.
>|__________
>
>It this really true? I would say that if it is, it a serious problem with 
>Ada.

This is true for untagged types, for upward compatibility reasons.
In general in Ada 83, predefined operators "reemerge" under certain
contexts (e.g. in a generic on the formal type, or in a composite operation
such as "<" on an array).  The reason for the reemergence can be traced
both to semantic and implementation difficulties associated with
disallowing reemergence.  For example, when a predefined operator
of an untagged type is overridden, the overriding need not necessarily
conform exactly to the original operators profile, nor satisfy the original
operator's semantic properties (as might be expected by a generic unit).

For tagged types, once "=" is overridden, the predefined operator will
never "reemerge," neither in generics nor in a composite operation such
as "=" on an array, record, or type extension.  Exact "subtype" conformance 
is required when overriding "=" on a tagged type (or when overriding any 
inherited primitive operation on a tagged type).

This distinction should be remembered when deciding whether to make a given
abstract type tagged or not.  In general, if the programmer wants complete 
control over a type, the type will need to be tagged (and perhaps also 
"controlled").

As pointed out by others, providing a default initialization for 
the "tail" of an array is an alternative way to avoid any problems 
associated with "partially" initialized nested arrays.

>Regards,
>                Jacob Sparre Andersen

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

Re: Ada.strings.bounded problems?

[Tucker Taft]

In article <D2J8H0.DMu@aplcenmp.apl.jhu.edu>,
Mars J. Gralia <gralia@aplcenmp.apl.jhu.edu> wrote:

>ka@socrates.hr.att.com (Kenneth Almquist) writes:
>> ... Often it is better in the long
>>run to use unbounded strings in place of bounded strings, so your code
>>doesn't have to change if ...
>
>Hummm.  My programs are supposed to run for years without rebooting.
>And typical memory is 16 Mbytes/no_disk. Doesn't that rule out
>unbounded strings for me?

No, not necessarily.  Unbounded strings are required to be implemented
in a way that does not "leak" storage, presumably using a "controlled"
type.  Of course, one may still get fragmentation of the heap, though
that can be bounded if you are willing to implement your own storage pool,
and perhaps use an extra level of indirection in the implementation of
bounded strings (to allow easy compactification).

-Tucker Taft  stt@inmet.com
Intermetrics, Inc.

Re: Ada.strings.bounded problems?

[Robb Nebbe]

dewar@cs.nyu.edu (Robert Dewar) writes:
|> It is important to realize the hit on shared generics. THe design of Ada 95
|> has been carefully done to preserve the practicality of using shared
|> generics, as is currently done by at least two implementations. In particular,
|> suppose we have a simple generic with some discrete types as arguments. It
|> seems unfortunate (both in terms of implementation complexity, and in 
|> efficiency) to require all equality operations to be done with thunks.

And of course redefining equality on discrete types is a very common
programming idiom. (For all those people who can't put up with the
overhead of comparing those unused bits :-) This is a strawman. It would
have made more sense (to me) to exclude discrete types, where the
reemergence of primitive operations is much less likely to cause a
problem and provide clean semantics for record types.

What probably bothers Magnus and others is that the justifications for
not providing semantics that are consistent with tagged types are all
pragmatic. Clearly the semantics as they are defined, which allow the
reemergence of predefined equality, are not desirable (or even justifyable)
from a language design point of view; rather, they must be justified
from on implementation point of view or other pragmatic concerns such
as upwards compatability. (which are certainly legitimate)

Maybe the cost of not providing consistant semantics between tagged
and untagged record types will exceed the cost of introducing an
upward incompatability, maybe not. It is a really tough call right
now. Especially since there really isn't any data, just speculation,
to base the decision on.

Robb Nebbe

Re: Ada.strings.bounded problems?

[Mats Weber]

In article <3foq6h$9n3@gnat.cs.nyu.edu>, dewar@cs.nyu.edu (Robert Dewar) wrote:

> There would be problems in implementation of generics with shared code if   
> equal were always compositional. Certainly a consideration (it would mean
> that equality had to be passed in for all types, quite expensive).

I would prefer the compiler giving me a warning like:
   "potential loss of ability to share generic instances"
over one like this:
   "potential loss of some aspects of exported abstraction".

> Second: it IS possible to define equality on non-limited types in Ada 83
> using the generic trick. This trick is well known, and widely used, so you
> cannot ignore it in considering upwards compatibility.

In article <3fmnc1$rns@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote:

> In article <1995Jan19.124412@lglsun.epfl.ch>, nebbe@lglsun.epfl.ch
> (Robb Nebbe) writes: 
> 
> |> There couldn't have been any upward compatibility problems since you
> |> couldn't override "=".
> 
> That's what Jean Ichbiah thought, but John Goodenough proved him wrong.
> 
> (A loophole resulted from the fact that you could override "=" for a
> generic formal limited private type, but you could pass a nonlimited type
> as the corresponding generic actual parameter.)

I can't believe that the `Goodenough trick' is used as an excuse for not
repairing the rules on "=". If there had been an AI on this trick, then it
would certainly have been forbidden by some additional rule, as was
clearly the intent in the design of the language.

I'm not saying that it was a good idea to forbid overloading of "=", but
that except for the Goodenough trick, Ada 83 was consistent in its
treatement of "=" and the programmer never got ripped off by the language.

Mats

Re: Ada.strings.bounded problems?

[Robert Dewar]

Robb Nebbe is exactly right, it is a tough call to decide between upwards
compatible semantics, and "doing things right". Of course you also have to 
be sure you understand what right is :-)

THe standard certainly contains the results of some delicate discussions in
this area. What is remarkable I think is that in pretty much every case, the
ISO group was able to reach a consensus on the right way to go. Doesn't mean
we made the right decision in every case, but it is remarkable how few
contentious issues there were once things settled down to final decisions.

Re: Ada.strings.bounded problems?

[Robert A Duff]

In article <Mats.Weber-2301951656460001@mlma11.matrix.ch>,
Mats Weber <Mats.Weber@matrix.ch> wrote:
>I can't believe that the `Goodenough trick' is used as an excuse for not
>repairing the rules on "=". If there had been an AI on this trick, then it
>would certainly have been forbidden by some additional rule, as was
>clearly the intent in the design of the language.

I think the first time I saw that trick, it was *in* an AI, which
confirmed that you can define "=" using the trick (but not the
straightforward way).  I don't have the AI number -- I'm too lazy to
look it up.

I completely agree that the non-composability of "=" was a bad idea in
Ada 83.  However, fixing it for Ada 95 would not have been so easy.

For one thing, you have to think about all the other operators.  Suppose
I redefine "<" on character type.  Should that compose properly, so that
"<" on an array-of-that-character type uses the redefined "<"?  Of
course, you want that, but this is a more serious upward
incompatibility.  You don't have to use any Goodenough Tricks to define
that "<" -- it's a perfectly reasonable thing to do.  Changing the
run-time behavior of perhaps many existing programs would have been
rather disruptive.

But if you don't fix "<", then why fix "="?  It would seem strange for
"=" on the array to call the redefined "=" on the characters, but "<"
does not call the redefined "<".

Another issue is how far to go in the composability.  For example, if I
redefine "=" on a discrete type, does it affect the way case statements
work?  After all case statements compare the value of an expression for
equality with the various when's.  But what would the full coverage
rules mean if "=" does something weird, like always returning True?

Similarly, the expression X.all checks that X /= null.  Should it use
the programmer's notion of "/=" there?  Probably not.  Constraint checks
on discriminated types check for equality of the discriminants.

We sidestepped all those issues by drawing the line in a different place
-- "=" composes properly for tagged types, and not for untagged types.
Arrays of tagged types don't automatically have "<", and you can't do
case statements on them, and so on.  In fact, "=" and "/=" are the
*only* predefined operators for tagged types, so it's not so
unreasonable to treat them specially.

- Bob

Re: Ada.strings.bounded problems?

[Tucker Taft]

In article <1995Jan23.135503@lglsun.epfl.ch>,
Robb Nebbe <nebbe@lglsun.epfl.ch> wrote:
>... Clearly the semantics as they are defined, which allow the
>reemergence of predefined equality, are not desirable ...

Actually, the Ada 9X design team proposed in 1991 or thereabouts
that predefined operators would never "reemerge" in generics or 
composite operations.  However, at least at the time, there were
those who defended the Ada 83 behavior as *desirable*, mostly
based on examples where a generic which presumed predefined
semantics for an operator could become quite confused
if the operators did not satisfy various presumed invariants.
For example, one might presume that X < Y implied not X >= Y.
However, one could imagine an overriding of the predefined operators
such that there were "incomparable" values, and both X < Y and 
X >= Y would return False.  

At the time, the example that was mentioned several 
times was an overriding of user-defined operators 
to create modular arithmetic.  It was easy to
construct generics which could get pretty confused because
they presumed normal non-modular invariants such as
A > 0 implies A + B > B.  Text_IO.Integer_IO was one
possible example of this.

Although we (the design team) argued for no reemergence at 
the time, we ultimately reached the conclusion that, for 
untagged types, predefined operators should continue 
to reemerge, as they did in Ada 83.  I suppose
upward compatibility was the strongest argument, though the
argument about desirability and simplicity of semantics for
generics was considered as well.

Fully general support for user-defined "=" came somewhat later
during the Ada 9X design process, but in any case the goal
was to treat "=" *more* like other operators, rather than *less*.

Having decided to retain predefined operator reemergence for
scalar types, we were reluctant to make a special case for the
equality operator on untagged record types.  The same thing
applied to untagged derived types.  

Basically, we decided that tagged types would be used for
"fully" abstract types, since only on such types could you
handle levels of indirection, etc., where a user-defined
equality was clearly important.  

In other words, we decided to keep uniformity across all
untagged types, and across all tagged types, but sacrifice 
some uniformity between tagged and untagged types.

The general "philosophical" difference between tagged types
and untagged types is that untagged types are simpler and
leaner and better for relatively "concrete" types, whereas
tagged types are a bit more expensive but more flexible and
better for more "abstract" types.  

For derived types, untagged derived types are presumed 
to be types that are essentially identical internally, 
but with a strong type distinction created between them to help 
support compile-time checking of one sort or another (such
as two integer types where one counts apples and the other oranges).  

Tagged derived types (i.e.  type extensions), on the other hand, 
are potentially completely different internally from their parent
type, and it is intentionally possible to *avoid* strong 
compile-time type distinctions between them by using a class-wide type,
which makes sense when the differences are merely implementation
differences, rather than significant interface differences.

Or in short, untagged derived types can be used to create arbitrary
interface differences on top of identical implementations, whereas
tagged type extensions can be used to preserve a common interface
across significantly different implementations.

>Maybe the cost of not providing consistant semantics between tagged
>and untagged record types will exceed the cost of introducing an
>upward incompatability, maybe not.   ...

There was also the issue of consistency between untagged record
types and untagged non-record types.  As mentioned above, we chose
to make the "break" between tagged and untagged.  One could instead
have made the break between records and non-records, but we felt
that was not as natural a breaking point, particularly since in Ada 83,
one could implement a given private type with a record or a non-record
without any signicant effect on the clients.

> ... It is a really tough call right
>now. Especially since there really isn't any data, just speculation,
>to base the decision on.

It is always painful to break consistency.  Clearly the issue
of reemergence of predefined operators will continue to reemerge
over time ;-).

>Robb Nebbe

-Tucker Taft  stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.

Re: Ada.strings.bounded problems?

[Robert Dewar]

Mats, it is no so easy to forbid the "Goodenough trick". Do you in fact know
it? Once you see it, it is a pretty straightforward and fundamental use of
basic generic capabilities. In fact part of the reason that Ada 95 allows
definition of equality on non-limited types is precisely that it is very
hard to forbid it. I do not think the ARG would have managed to forbid it,
I certainly don't see how.

Second, you misunderstand the shared generic situation. You talk about a
compiler warning about a potential loss of capbility for shared generics.
That's not the issue. There are at least two existing Ada compilers that
ONLY know how to make shared generics, and a pragmatic design point was
to be consistent with this approach.

It is one thing to warn of potential loss of shared generic capbility (I
guess that happens in your model for ALL generics with type parameters,
since there might be an equality???) and quite another to have to make the
painful choice of rejecting such generics, or implementing them very
inefficiently.

You may come to a different conclusion on this particular issue than the
one we reached by consensus, but I certainly won't be very convinced by
your thoughts till it is clear that you understand the issues on both
sides. It is easy to take a broad brush view of things without hearing
all the details (sort of like all the people who "know" whether O.J.Simpson
is guilty or innocent without having heard the evidence :-)

Try the excercise if you like of stating a clean rule that forbids the
"goodenough trick", and does not take away other useful functionality.
After all if we take away useful functionality, your twin brother will
be complaining about that! :-)

If you are not familiar with this technique, I think you really ought to
be before you make pronouncements on it. If you are familiar, I am 
interested to know what restrictive rule you have in mind.

Re: Ada.strings.bounded problems?

[Robb Nebbe]

In article <D2xAyz.6L2@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:

A good coherent explanation of the problems associated allowing the
redefinition of operations on scalar types and not allowing them to
reemerge deleted.

|> 
|> We sidestepped all those issues by drawing the line in a different place
|> -- "=" composes properly for tagged types, and not for untagged types.
|> Arrays of tagged types don't automatically have "<", and you can't do
|> case statements on them, and so on.  In fact, "=" and "/=" are the
|> *only* predefined operators for tagged types, so it's not so
|> unreasonable to treat them specially.
|> 
|> - Bob

I don't see any particularly compelling reasons to prefere having
drawn the line between tagged and untagged types rather than record
and non-record types. Tucker touched on this subject in a post in
this same thread but he sort of glossed over it by saying that
making the distinction between tagged and untagged types is more
"natural".

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <3g3k5c$7bu@gnat.cs.nyu.edu>, dewar@cs.nyu.edu (Robert Dewar)
writes: 

|> Try the excercise if you like of stating a clean rule that forbids the
|> "goodenough trick", and does not take away other useful functionality.

Easy enough, if you want to do it.  Add to the end of RM83 12.3.6(1): 

   If the designator of the formal subprogram is "=", then the
   actual subprogram must be an equality operator.

This plugs the loophole in RM83 6.7(5), which states that a renaming
declaration for an equality operator can only rename another equality
operator.  Generic formal parameters are supposed to act like renamings
of the corresponding generic actual parameters, but this property of
renaming declarations was overlooked.

("Legitimate" users of generic formal functions named "=" would have to
use names like Equal instead.  I don't count that as a loss of useful
functionality.)


--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Ada.strings.bounded problems?

[Robert Dewar]

Mats Weber says:

"Given this choice, IMO, it would have been best to continue forbidding the
overloading of "=" for non-tagged types, as in Ada 83. Was this ever
considered ?"

Reading through this thread, I tend to agree, this was probably a change
that we should have left alone.

Anyway, it isn't so serious, because an appropriate proper response if you
don't think this "feature" should have been added is to forbid its use.

Re: Ada.strings.bounded problems?

[David Emery]

>I think those compiler vendors would have served their users much
>better by implementing dead code elimination, which still is very seldom
>in Ada environments :-(.

Shared generics is one of those Ada-specific optimizations that can
hasve a real impact on design.  ('Passive tasks' is another.)  I've
developed systems that made very extensive use of generics, and, if
the compiler did not support shared generics, the resulting 'core
bloat' would have made the system too big to fit in the (virtual)
machine.  

Although dead code elimination (particularly eliminating unused
subprograms from packages) is important, I consider it much less
important than shared generics and passive tasks.

				dave
--
--The preceeding opinions do not necessarily reflect the opinions of
--The MITRE Corporation or its sponsors. 
-- "A good plan violently executed -NOW- is better than a perfect plan
--  next week"                                      George Patton
-- "Any damn fool can write a plan.  It's the execution that gets you
--  all screwed up"                              James Hollingsworth
-------------------------------------------------------------------------

Re: Ada.strings.bounded problems?

[William Brennan]

In article <EMERY.95Jan30091540@goldfinger.mitre.org>,
David Emery <emery@goldfinger.mitre.org> wrote:
>Shared generics is one of those Ada-specific optimizations that can
>have a real impact on design.  ('Passive tasks' is another.)  

Please, what are "passive tasks"? (Non-periodic ones?)
Why is it important for the optimizer to recognize them?


-- 
----------------------------------------------------------------------------
                                                     === Team-Ada member ===
Bill Brennan                                  brennan@panther.warm.inmet.com

Re: Ada.strings.bounded problems?

[William Brennan]

In article <D3Bqzw.D12@inmet.camb.inmet.com>,
William Brennan <brennan@panther.warm.inmet.com> wrote:
>In article <EMERY.95Jan30091540@goldfinger.mitre.org>,
>David Emery <emery@goldfinger.mitre.org> wrote:
>>Shared generics is one of those Ada-specific optimizations that can
>>have a real impact on design.  ('Passive tasks' is another.)  
>
>Please, what are "passive tasks"? (Non-periodic ones?)
>Why is it important for the optimizer to recognize them?
                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   

Err..., I mean, why is it important to design with passive tasks in mind?


-- 
----------------------------------------------------------------------------
                                                     === Team-Ada member ===
Bill Brennan                                  brennan@panther.warm.inmet.com

Re: Ada.strings.bounded problems?

[Robert Firth]

In article <D3Bqzw.D12@inmet.camb.inmet.com> brennan@panther.warm.inmet.com (William Brennan) writes:

>Please, what are "passive tasks"? (Non-periodic ones?)
>Why is it important for the optimizer to recognize them?

Let's start with a typical problem: two tasks, a producer
and a consumer, connected by a bounded buffer.  The producer
creates data and drops each datum into the buffer; the
consumer takes the data out and consumes them.  If the buffer
is full, the producer is suspended; if empty, the consumer
is suspended.

Producer: forever do { produce(datum); put(buffer, datum) }

Consumer: forever do { get(buffer, datum); consume(datum) }

In many older realtime systems, we had the "buffer" as a
primitive of the kernel, and so the above system had two
"real" tasks, a bit of hairy assembler in the get and
put primitives, and, typically, two context switches for
each burst of data, or, at worst, for each datum.

The paradigm is called "loose coupling": producer and consumer
can run at variable rates, and the buffer takes up the slack.

But the Ada task communication mechanism, the rendezvous,
requires tight coupling.  Producer must hand each datum
directly to consumer, like a runner in a relay race passing
the baton.  And this may not be convenient.

The canonical solution is to write a third task, called Buffer,
with Get and Put as entries.  The producer calls Buffer.Put,
the consumer calls Buffer.Get, and the Buffer maintains an
internal data structure to buffer the data:

	loop
	    select
		when buffer_not_full =>
		    accept Put do ... end;
	    or
		when buffer_not_empty =>
		    accept Get do ... end;
	    end select;
	end loop;

Canonically, that's *four* context switches per datum: from
Producer to Buffer and back, and from Consumer to Buffer and
back.  A not inconsiderable overhead.

However, the buffer task is "passive".  That is, it has no
independent thread of control; it never does anything on
its own.  Apart from the elaboration of the select statement
and its guards, *all* the processing is done during a
rendezvous with somebody else.

The optimisation, then, is to perform that processing in
the context of the *entry caller*, and then you never have to
create a real buffer task: no stack, no context switch; the
entry call is (almost) a procedure call.

Trouble is, that's not an easy optimisation, not least because
it involves a rather complex loop rotation: the guards are
evaluated not at the top of the loop, but at the bottom of the
*previous* loop, folded into the last rendezvous.  Even more
trouble is, that routine maintenance of the Buffer code may
quite abruptly make the optimisation go away, either by
making it formally impossible or by defeating the compiler's
ingenuity.  So the code is very, very fragile.

That's the technical gist of it; you've almost certainly
guessed my opinion.  Hope that helps.

Robert Firth

Re: Ada.strings.bounded problems?

[Mark A Biggar]

In article <D3Bqzw.D12@inmet.camb.inmet.com> brennan@panther.warm.inmet.com (William Brennan) writes:
>Please, what are "passive tasks"? (Non-periodic ones?)
>Why is it important for the optimizer to recognize them?

A "passive task" is one that does nothing significant outside of any
of its accept statements; such a task doesn't really need a separate
thread of control as it can do all its work piggy backed on the thread of
control of any task that calls one of its entries.  A simple example is:

task foo is 
    entry a;
    entry b;
end foo;

task body foo is
begin
    loop
        select
            accept a do
                -- do task operation a
            end a;
        or
            accept b do
                -- do task operation b
            end b;
        end select;
    end loop;
end foo;

The simple buffer tasks often required by the Ada tasking model a usually
passive tasks.

Recognizing that a task is passive can greatly reduce the amount of code 
necessary to be generated for it and also reduces the run time burden on
the tasking run time system.  That this optimization can be so useful
is one of the reasons that "protected objects" were added to the Ada95
specification.

--
Mark Biggar
mab@wdl.loral.com

Re: Ada.strings.bounded problems?

[Norman H. Cohen]

In article <D3H6qD.AD6@inmet.camb.inmet.com>, stt@henning.camb.inmet.com
(Tucker Taft) writes: 

|> One other nice feature -- we get rid of the oxymoronic term
|> "passive task" ;-).  (I know ... "oxymoron" is supposed to
|> be used for "poetic" juxtapositions only...).

But to make up for it, Ada 95 introduces a child of package Ada.Numerics
named Complex_Elementary_Functions. ;-)

--
Norman H. Cohen    ncohen@watson.ibm.com

Re: Passive tasks (was: bounded strings)

[Schilling J.]

In article <3grvi1$jvm@gnat.cs.nyu.edu> dewar@cs.nyu.edu (Robert Dewar) writes:

[thread regarding passive task optimizations] 

>However, it turned out to be harder than expected to do this optimization, 
>so many vendors did not get around to it (verdix is a notable exception). 

Several other vendors did it as well, including DDC-I and Telesoft.  The paper 
"Automatic Compiler Recognition of Monitor Tasks" in ACM Ada Letters May/June 
1994 discusses different approaches to the optimization and also gives some
additional references on the subject.

-- 
Jonathan Schilling
Novell, UNIX Systems Group
jls@summit.novell.com

Re: Passive tasks (was: bounded strings)

[Robert Dewar]

Jonothan Shilling says that Telsoft marketed a compiler with passive
task optimization. Is this true, because my impression was that they
had talked about it but did not actually do it. If this impression is
wrong, I would like to be corrected (by someone who has definitely seen 
and used such a product)

Re: Ada.strings.bounded problems?

[David Weller]

In article <3h8kqr$led@watnews1.watson.ibm.com>,
Norman H. Cohen <ncohen@watson.ibm.com> wrote:
>|> One other nice feature -- we get rid of the oxymoronic term
>|> "passive task" ;-).  (I know ... "oxymoron" is supposed to
>|> be used for "poetic" juxtapositions only...).
>
>But to make up for it, Ada 95 introduces a child of package Ada.Numerics
>named Complex_Elementary_Functions. ;-)
>

Kinda reminds me of an early college torture class with a deceptive
name: Ordinary Differential Equations.

I never noticed anything "ordinary" about them :-)


-- 
      Frustrated with C, C++, Pascal, Fortran?  Ada95 _might_ be for you!
	  For all sorts of interesting Ada95 tidbits, run the command:
"finger dweller@starbase.neosoft.com | more" (or e-mail with "finger" as subj.)