Safety of the Booch Ada 95 Components

Safety of the Booch Ada 95 Components

[Harry Erwin]

In C++, the equate operation for a container class C<T> is preferably
defined as follows (Sutter, Exceptional C++, Addison-Wesley, 2000):

template <typename T>
C<T>& operator=(const C<T>& c)
{
    if(&c == this) return *this; // not required; done for efficiency
    C temp(c); // uses the copy constructor, may throw
    swap(temp, *this); // swaps the guts of this container with
                       // temp. May not throw.
    return *this; // May not throw.
} // the destructor for temp releases the memory originally in this
  // container, and destructors may not throw

This is strongly exception-safe and exception-neutral, since only the
copy constructor can throw, and that occurs before the guts are swapped.
Hence the container remains useable, and no objects are lost from it.
Now I've been looking at the Booch components for Ada 95, and have
noticed that the Copy function typically starts by clearing the To
container. That immediately implies that they are not exception-safe,
but I'm concerned that they may not be safe under self-assignment as
well. Is there something about the Ada 95 standard that guarantees that
there will be no aliasing of container args?

-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

herwin@gmu.edu (Harry Erwin) writes:

> In C++, the equate operation for a container class C<T> is preferably
> defined as follows (Sutter, Exceptional C++, Addison-Wesley, 2000):
> 
> template <typename T>
> C<T>& operator=(const C<T>& c)
> {
>     if(&c == this) return *this; // not required; done for efficiency
>     C temp(c); // uses the copy constructor, may throw
>     swap(temp, *this); // swaps the guts of this container with
>                        // temp. May not throw.
>     return *this; // May not throw.
> } // the destructor for temp releases the memory originally in this
>   // container, and destructors may not throw
> 
> This is strongly exception-safe and exception-neutral, since only the
> copy constructor can throw, and that occurs before the guts are swapped.
> Hence the container remains useable, and no objects are lost from it.
> Now I've been looking at the Booch components for Ada 95, and have
> noticed that the Copy function typically starts by clearing the To
> container. That immediately implies that they are not exception-safe,
> but I'm concerned that they may not be safe under self-assignment as
> well. Is there something about the Ada 95 standard that guarantees that
> there will be no aliasing of container args?

(1) the Copy subprogram -- in this case

  procedure Copy (From : Queue'Class; To : in out Queue'Class);

is used for copying queues using the same element type but different
storage allocation strategies (Bounded, Unbounded). It's the
equivalent of the C++

  virtual BC_TQueue<Item>& operator=(const BC_TQueue<Item>&);

in the abstract class template<class Item> class BC_TQueue.

(2) I'm not quite sure what should occur if an exception happened in
the middle of copying a queue; it would be reasonable to expect the
data structure to be uncorrupted, but you couldn't expect any
particular subset of the elements in the queue to have been copied.

Nevertheless, I need to look at this one ..

(3) The deep copy you expect on normal assignment of one Queue to
another (Second := First;) is managed by having them be Controlled:

  type Container is abstract new Ada.Finalization.Controlled with private;
  type Queue is abstract new Container with private;
  type Bounded_Queue is new Queue with private;

and (ALRM 7.6(17)):

  For an assignment_statement, after the name and expression have been
  evaluated, and any conversion (including constraint checking) has
  been done, an anonymous object is created, and the value is assigned
  into it; that is, the assignment operation is applied. (Assignment
  includes value adjustment.) The target of the assignment_statement
  is then finalized. The value of the anonymous object is then
  assigned into the target of the assignment_statement. Finally, the
  anonymous object is finalized. As explained below, the
  implementation may eliminate the intermediate anonymous object, so
  this description subsumes the one given in 5.2, ``Assignment
  Statements''.

GNAT 3.11p not only eliminates the intermediate anonymous object, it
special-cases the "A := A;" case; well, in the quick check I've just
run:

...
  Queue_B_P1, Queue_B_P2 : Queue_Finalization_Test.Queue;

begin

  Append (Queue_B_P2, '1');
  Append (Queue_B_P2, '2');
  Append (Queue_B_P2, '3');
  Append (Queue_B_P2, '4');

  Put_Line ("Queue_B_P2:");
  Print (Queue_B_P2);
  
  Queue_B_P1 := Queue_B_P2;
  Put_Line ("Queue_B_P1:");
  Print (Queue_B_P1);
  
  Queue_B_P1 := Queue_B_P1;
  Put_Line ("Queue_B_P1:");
  Print (Queue_B_P1);
...

outputs

initializing a Queue
initializing a Queue
Queue_B_P2:
Item: 1
Item: 2
Item: 3
Item: 4
finalizing a Queue
adjusting a Queue
Queue_B_P1:
Item: 1
Item: 2
Item: 3
Item: 4
Queue_B_P1:
Item: 1
Item: 2
Item: 3
Item: 4
finalizing a Queue
finalizing a Queue

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

Simon Wright <simon@pogner.demon.co.uk> writes:

> herwin@gmu.edu (Harry Erwin) writes:
> 
> > In C++, the equate operation for a container class C<T> is preferably
> > defined as follows (Sutter, Exceptional C++, Addison-Wesley, 2000):
> > 
> > template <typename T>
> > C<T>& operator=(const C<T>& c)
> > {
> >     if(&c == this) return *this; // not required; done for efficiency
> >     C temp(c); // uses the copy constructor, may throw
> >     swap(temp, *this); // swaps the guts of this container with
> >                        // temp. May not throw.
> >     return *this; // May not throw.
> > } // the destructor for temp releases the memory originally in this
> >   // container, and destructors may not throw
> > 
> > This is strongly exception-safe and exception-neutral, since only the
> > copy constructor can throw, and that occurs before the guts are swapped.
> > Hence the container remains useable, and no objects are lost from it.
> > Now I've been looking at the Booch components for Ada 95, and have
> > noticed that the Copy function typically starts by clearing the To
> > container. That immediately implies that they are not exception-safe,
> > but I'm concerned that they may not be safe under self-assignment as
> > well. Is there something about the Ada 95 standard that guarantees that
> > there will be no aliasing of container args?
[...]
> (2) I'm not quite sure what should occur if an exception happened in
> the middle of copying a queue; it would be reasonable to expect the
> data structure to be uncorrupted, but you couldn't expect any
> particular subset of the elements in the queue to have been copied.
> 
> Nevertheless, I need to look at this one ..

.. and it seems fine to me, at least for queues. The structure is
still valid, though it's not possible to say what the contained values
are.

Harry sent me private mail to the effect that there do indeed seem to
be problems here with the BCs. Well, I don't agree; at least, not that
Harry's suggested semantics are any better in practice.

The postcondition of HA = HB; seems to be (primed names indicate
input values)

  HB == HB' and (HA == HB'
                 or an exception is raised and HA == HA')

In the last case, Harry is going to have to do something about HA,
because whatever else it means it does _not_ hold the value it should!
Perhaps it contains _last_ month's balance of his bank account,
perhaps it's the _old_ state of the helicopter's fuel supply ..

The BCs equivalent for assignment is (no warranties, remember)

  BB == BB' and (BA == BB'
                 or an exception is raised)

The above analysis with regard to exceptions holds also for the Copy
operation (between queues of the same element type but possibly with
different allocation strategies).

There is, however, a defect (OK, guys? :-) in the Copy operation,
since it fails under self-assignment. Oops. Logged.

Re: Safety of the Booch Ada 95 Components

[Matthew Heaney]

In article <x7vu2lowfr2.fsf@pogner.demon.co.uk> , Simon Wright 
<simon@pogner.demon.co.uk>  wrote:

> The BCs equivalent for assignment is (no warranties, remember)
>
>   BB == BB' and (BA == BB'
>                  or an exception is raised)

That's exactly it.

Yes, this lacks "rollback semantics," but I'm perfectly happy with this
postcondition, as it's likely to be far more efficient than its stronger
alternative:

   HB == HB' and (HA == HB'
                  or an exception is raised and HA == HA')

I'd be willing to bet that most systems programmers would NOT be
satisfied with this postcondition, if they knew how inefficient it is
compared to the other.

Perhaps there is a middle position.  We could guarantee that if
assignment fails, then the target data structure is cleared, instead of
being left in some unknown state:

  HB == HB' and (HA == HB'
                 or an exception is raised and HA.Length == 0)


--
The political forces that try to eliminate evolution from science
classrooms impose a narrow, sectarian doctrine on our educational
systems. This imposition represents an affront not only to the
constitutional separation of church and state but also to the moral and
intellectual integrity embedded in that constitution.

<http://www.nabt.org/evolutionks.html>

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Simon Wright <simon@pogner.demon.co.uk> wrote:

> herwin@gmu.edu (Harry Erwin) writes:
> 
> > In C++, the equate operation for a container class C<T> is preferably
> > defined as follows (Sutter, Exceptional C++, Addison-Wesley, 2000):
> > 
> > template <typename T>
> > C<T>& operator=(const C<T>& c)
> > {
> >     if(&c == this) return *this; // not required; done for efficiency
> >     C temp(c); // uses the copy constructor, may throw
> >     swap(temp, *this); // swaps the guts of this container with
> >                        // temp. May not throw.
> >     return *this; // May not throw.
> > } // the destructor for temp releases the memory originally in this
> >   // container, and destructors may not throw
> > 
> > This is strongly exception-safe and exception-neutral, since only the
> > copy constructor can throw, and that occurs before the guts are swapped.
> > Hence the container remains useable, and no objects are lost from it.
> > Now I've been looking at the Booch components for Ada 95, and have
> > noticed that the Copy function typically starts by clearing the To
> > container. That immediately implies that they are not exception-safe,
> > but I'm concerned that they may not be safe under self-assignment as
> > well. Is there something about the Ada 95 standard that guarantees that
> > there will be no aliasing of container args?
> 
> (1) the Copy subprogram -- in this case
> 
>   procedure Copy (From : Queue'Class; To : in out Queue'Class);
> 
> is used for copying queues using the same element type but different
> storage allocation strategies (Bounded, Unbounded). It's the
> equivalent of the C++
> 
>   virtual BC_TQueue<Item>& operator=(const BC_TQueue<Item>&);

In C++ 99, we'd use:

C1<T> source;   //      assume initialized
C2<T> destination(source.begin(), source.end());  // strongly safe

This uses the copy constructor with two iterator arguments. 

Or we'd use:

destination.insert(position, source.begin(), source.edu());

which, like your Copy, is not strongly safe.

> 
> in the abstract class template<class Item> class BC_TQueue.
> 
> (2) I'm not quite sure what should occur if an exception happened in
> the middle of copying a queue; it would be reasonable to expect the
> data structure to be uncorrupted, but you couldn't expect any
> particular subset of the elements in the queue to have been copied.
> 
> Nevertheless, I need to look at this one ..
> 
> (3) The deep copy you expect on normal assignment of one Queue to
> another (Second := First;) is managed by having them be Controlled:
> 
>   type Container is abstract new Ada.Finalization.Controlled with private;
>   type Queue is abstract new Container with private;
>   type Bounded_Queue is new Queue with private;
> 
> and (ALRM 7.6(17)):
> 
>   For an assignment_statement, after the name and expression have been
>   evaluated, and any conversion (including constraint checking) has
>   been done, an anonymous object is created, and the value is assigned
>   into it; that is, the assignment operation is applied. (Assignment
>   includes value adjustment.) The target of the assignment_statement
>   is then finalized. The value of the anonymous object is then
>   assigned into the target of the assignment_statement. Finally, the
>   anonymous object is finalized. As explained below, the
>   implementation may eliminate the intermediate anonymous object, so
>   this description subsumes the one given in 5.2, ``Assignment
>   Statements''.

Thanks.  I'll nose around into this.  It looks like the Ada language
hides a lot of the detail that a C++ 99 student has to learn to be anal
about.

> 
> GNAT 3.11p not only eliminates the intermediate anonymous object, it
> special-cases the "A := A;" case; well, in the quick check I've just
> run:
> 
> ...
>   Queue_B_P1, Queue_B_P2 : Queue_Finalization_Test.Queue;
> 
> begin
> 
>   Append (Queue_B_P2, '1');
>   Append (Queue_B_P2, '2');
>   Append (Queue_B_P2, '3');
>   Append (Queue_B_P2, '4');
> 
>   Put_Line ("Queue_B_P2:");
>   Print (Queue_B_P2);
>   
>   Queue_B_P1 := Queue_B_P2;
>   Put_Line ("Queue_B_P1:");
>   Print (Queue_B_P1);
>   
>   Queue_B_P1 := Queue_B_P1;
>   Put_Line ("Queue_B_P1:");
>   Print (Queue_B_P1);
> ...
> 
> outputs
> 
> initializing a Queue
> initializing a Queue
> Queue_B_P2:
> Item: 1
> Item: 2
> Item: 3
> Item: 4
> finalizing a Queue
> adjusting a Queue
> Queue_B_P1:
> Item: 1
> Item: 2
> Item: 3
> Item: 4
> Queue_B_P1:
> Item: 1
> Item: 2
> Item: 3
> Item: 4
> finalizing a Queue
> finalizing a Queue

Good, so self-assignment works.

-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

herwin@gmu.edu (Harry Erwin) writes:

>                                       It looks like the Ada language
> hides a lot of the detail that a C++ 99 student has to learn to be anal
> about.

Not sure that "hides" is the right word there! If you mean "defines in
the standard", OK .. or "defines in such a way you don't need to
worry"!

> Good, so self-assignment works.

Turns out that one of the free compilers has a serious bug^H^H^Hdefect
here (or else it's me .. usually it's me ..)

Re: Safety of the Booch Ada 95 Components

[Matthew Heaney]

In article <1e2lds4.7trgj21rgj9i0N%herwin@gmu.edu> , herwin@gmu.edu 
(Harry Erwin) wrote:

> Now I've been looking at the Booch components for Ada 95, and have
> noticed that the Copy function typically starts by clearing the To
> container.

I haven't studied the Booch components specifically, but here's how Copy
operations should be implemented in general.

Assuming the data structure is implemented as a by-reference type (the
type is tagged and/or limited), you can invoke RM95 13.3 (16) to legally
compare the addresses of the subprogram parameters:

  procedure Copy
    (From : in     Source_Type;
     To   : in out Target_Type) is
  begin
    if From'Address = To'Address then
      return;  -- do nothing, because From is same object as To
    end if;

    Clear (To);  -- safe, because we now know To isn't From

    <do rest of copy>
  end Copy;

If the Booch Components don't first check whether aliasing has occurred,
prior to clearing the target object, then perhaps something is wrong.


> That immediately implies that they are not exception-safe,
> but I'm concerned that they may not be safe under self-assignment as
> well.

I don't understand your comment about not being "exception-safe."
Perhaps you could elaborate on that point.


>  Is there something about the Ada 95 standard that guarantees that
> there will be no aliasing of container args?

No, it's up to you the programmer to determine whether aliasing has
occurred.

The idiom for determining whether aliasing has occurred is to compare
object addresses, per RM95 13.3 (16).


--
Help keep evolution in the science classroom and religion out: become a
member of the National Center for Science Education.

<http://www.natcenscied.org/>

Re: Safety of the Booch Ada 95 Components

[Hyman Rosen]

"Matthew Heaney" <matthew_heaney@acm.org> writes:
> I don't understand your comment about not being "exception-safe."
> Perhaps you could elaborate on that point.

In C++, class objects are copied through a class method called the
copy-constructor, to allow for resource control. If an exception is
thrown during copy-construction of one of the elements, it's possible
that the target data structure may be left in an invalid state.

Re: Safety of the Booch Ada 95 Components

[Matthew Heaney]

In article <t790326901.fsf@calumny.jyacc.com> , Hyman Rosen 
<hymie@prolifics.com>  wrote:

> In C++, class objects are copied through a class method called the
> copy-constructor, to allow for resource control.

Data structures (in Ada95) are written as generics that accept the
container item as a nonlimited generic formal private type:

generic
  type Item_Type is private;
package Stacks is ...;

The "copy constructor" in Ada95 is just the assignment operator that
comes with Item_Type.  Typically, the client of the assignment operator
(here, the implementation of the Copy operation for stack types) assumes
that assignment doesn't raise an exception.

We make this assumption per the "design-by-contract" model.  If you give
me an assignment operator that doesn't work, and it raises an exception
(say), then yes, that would leave the target object in an inconsistent
state.

If you don't like that, then don't give me a broken assignment operator.

> If an exception is thrown during copy-construction of one of the elements,
> it's possible that the target data structure may be left in an invalid state.

I suppose if you don't trust your client's assignment operator, then you
could make a copy of the target object, clear the target, and then do
the copy.  If there's an error during assignment, then you use the copy
of the target to restore the target back to its original state, and then
reraise the exception.

(But then again, I don't know how you would even implement this.  How do
you make a copy of the target, if you can't trust the copy constructor
for items?)

But this is an awfully heavy way to implement a Copy operation for a
data structure.  The canonical implementation of a Copy operation should
choose the more efficient implementation, which assumes that assignment
works (again, per DBC).

If you don't like the canonical Copy, then just extend the abstraction
with a child operation implemented using the pessimistic algorithm
(which I'm not convinced is even implementable).

--
Why stop at evolution and cosmology, though? Let's make sure that the
schoolkids of Kansas get a really first-rate education by loosening up
the teaching standards for other so-called scientific ideas that are,
after all, just theories. The atomic theory, for example. The theory of
relativity. Heck, the Copernican theory--do we really know that the
universe doesn't revolve around the earth?

John Rennie, Scientific American, Oct 1999

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Matthew Heaney <matthew_heaney@acm.org> wrote:

> In article <t790326901.fsf@calumny.jyacc.com> , Hyman Rosen 
> <hymie@prolifics.com>  wrote:
> 
> > In C++, class objects are copied through a class method called the
> > copy-constructor, to allow for resource control.
> 
> Data structures (in Ada95) are written as generics that accept the
> container item as a nonlimited generic formal private type:
> 
> generic
>   type Item_Type is private;
> package Stacks is ...;
> 
> The "copy constructor" in Ada95 is just the assignment operator that
> comes with Item_Type.  Typically, the client of the assignment operator
> (here, the implementation of the Copy operation for stack types) assumes
> that assignment doesn't raise an exception.
> 
> We make this assumption per the "design-by-contract" model.  If you give
> me an assignment operator that doesn't work, and it raises an exception
> (say), then yes, that would leave the target object in an inconsistent
> state.

Such exceptions in C++ are thrown if resources necessary for creating
the object are not available. These are most commonly memory, but
construction is the idiom used _in_general_ for resource management.
Also, in C++, termination semantics are default for exception handling.

> 
> If you don't like that, then don't give me a broken assignment operator.

A deep copy of a pointer data structure may require more memory than is
available. Similarly for a dynamic data structure. In C++, the
constructor throws a bad_alloc exception, and the class instance is
cleaned up. Not broken at all.

> 
> > If an exception is thrown during copy-construction of one of the
> > elements, it's possible that the target data structure may be left in an
> > invalid state.
> 
> I suppose if you don't trust your client's assignment operator, then you
> could make a copy of the target object, clear the target, and then do
> the copy.  If there's an error during assignment, then you use the copy
> of the target to restore the target back to its original state, and then
> reraise the exception.

template <typename T>
C<T>& operator= (const C(T)& c)
{
    if(this==&c) return *this; // for efficiency, not required
    C<T> temp(c); // may throw
    swap(temp,this); // swaps the guts, does not throw
    return *this; // does not throw
} // temp is deleted when it goes out of scope. does not throw

(per Sutter, 2000)

This idiom supports commit/rollback semantics.

> 
> (But then again, I don't know how you would even implement this.  How do
> you make a copy of the target, if you can't trust the copy constructor
> for items?)
> 
> But this is an awfully heavy way to implement a Copy operation for a
> data structure.  The canonical implementation of a Copy operation should
> choose the more efficient implementation, which assumes that assignment
> works (again, per DBC).
> 
> If you don't like the canonical Copy, then just extend the abstraction
> with a child operation implemented using the pessimistic algorithm
> (which I'm not convinced is even implementable).
> 
> --

-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Robert Dewar]

In article <1e2ns7h.cx85ir1azwo9iN%herwin@gmu.edu>,
  herwin@gmu.edu (Harry Erwin) wrote:
> A deep copy of a pointer data structure may require more
> memory than is available.


A naive copy may have that characteristic, but it is always
possible on modern machines to do such a copy with no additional
storage. It just takes a bit of cleverness. Remember that every
pointer has at least two spare bits.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Robert Dewar <robert_dewar@my-deja.com> wrote:

> In article <1e2ns7h.cx85ir1azwo9iN%herwin@gmu.edu>,
>   herwin@gmu.edu (Harry Erwin) wrote:
> > A deep copy of a pointer data structure may require more
> > memory than is available.
> 
> 
> A naive copy may have that characteristic, but it is always
> possible on modern machines to do such a copy with no additional
> storage. It just takes a bit of cleverness. Remember that every
> pointer has at least two spare bits.
> 

If what you're suggesting is sharing the underlying data, it's risky in
C++ since we have to manage the free store explicitly, rather than
relying on garbage collection. It is done that way for STL strings, but
there are some known problems, especially in a multithreaded
environment.

In any case, this discussion has been very educational. I now know where
in the documentation to go look for answers.

With thanks,
-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Kent Paul Dolan]

Robert Dewar  <robert_dewar@my-deja.com> wrote:
>  herwin@gmu.edu (Harry Erwin) wrote:
>> A deep copy of a pointer data structure may require more
>> memory than is available.

>A naive copy may have that characteristic, but it is always
>possible on modern machines to do such a copy with no additional
>storage. It just takes a bit of cleverness. Remember that every
>pointer has at least two spare bits.

This one sets alarm bells ringing like crazy.  I was a user of
AmigaBASIC, whose developers assumed that the 24 bits in use of 32 bit
pointers they saw when the machine in an early OS rev would be the law
forever, ignored the developer manuals warnings to the contrary, used
the other 8 bits for string lengths or some such, in a petty search for
"efficiency" at the expense of clean coding, and had their software die
a horrible death when the OS was upgraded within a couple of years to
use all 32 bits of a pointer.

I can already trick out a Mac G4 box with a gig of physical memory for
an obscene price, (but lower than the tag on a pretty old used car, and
less than the cost of a megabyte of memory retail in 1981), and not one
revision down the line support for a second gig will be in place, one
of your spare pointer bits has disappeared and gone, and your code is
broken.  Did you remember to instrument the breaks to be easily
located, and pre-design a workaround for conditional compilation or
conditional linking into place?

Some "efficiencies" aren't worth the risk, and the damage to pointer
semantics of using some bits for "non-pointer purposes" would be nearly
incalculable.

Oh, and did you lock your structures against traversal by other threads
while the (possibly time consuming) deep copy was ongoing, or are the
munged pointers going to be visible outside the deep copy process?

[I'd say "I am but an egg" here, w.r.t. my compiler writing near
non-experience, but some "eggs" hatched out moa birds, after all.]
--
Kent Paul Dolan.
<xanthian@well.com> <xanthian@aztec.asu.edu> <xanthian@whistle.com>
Using modern technology to commit errors at previously unachievable rates.

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

xanthian@well.com (Kent Paul Dolan) writes:

> Robert Dewar  <robert_dewar@my-deja.com> wrote:
> >  herwin@gmu.edu (Harry Erwin) wrote:
> >> A deep copy of a pointer data structure may require more
> >> memory than is available.
> 
> >A naive copy may have that characteristic, but it is always
> >possible on modern machines to do such a copy with no additional
> >storage. It just takes a bit of cleverness. Remember that every
> >pointer has at least two spare bits.
> 
> This one sets alarm bells ringing like crazy.  I was a user of
> AmigaBASIC, whose developers assumed that the 24 bits in use of 32 bit
> pointers they saw when the machine in an early OS rev would be the law
> forever, ignored the developer manuals warnings to the contrary, used
> the other 8 bits for string lengths or some such, in a petty search for
> "efficiency" at the expense of clean coding, and had their software die
> a horrible death when the OS was upgraded within a couple of years to
> use all 32 bits of a pointer.

I suspect Robert was thinking of the low-order 2 bits (on the
assumption that malloc() always returns something longword-aligned. I
rather thought it was often 16-byte-aligned??).

Re: Safety of the Booch Ada 95 Components

[Ted Dennison]

In article <Yk354.42$tb.10677@news.wenet.net>,
  xanthian@well.com (Kent Paul Dolan) wrote:
> AmigaBASIC, whose developers assumed that the 24 bits in use of 32 bit
> pointers they saw when the machine in an early OS rev would be the law
> forever, ignored the developer manuals warnings to the contrary, used
> the other 8 bits for string lengths or some such, in a petty search

Yikes, why did you have to remind me of that? I had a pretty neat
basketball game on my 1000, but on the 2000 the ball turned into a
square brown blotch. I could still play it, but my wife called it
"basketbrick". :-)

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Safety of the Booch Ada 95 Components

[Robert I. Eachus]

Kent Paul Dolan wrote:
  
> This one sets alarm bells ringing like crazy.  I was a user of
> AmigaBASIC, whose developers assumed that the 24 bits in use of 32 bit
> pointers they saw when the machine in an early OS rev would be the law
> forever, ignored the developer manuals warnings to the contrary, used
> the other 8 bits for string lengths or some such, in a petty search for
> "efficiency" at the expense of clean coding, and had their software die
> a horrible death when the OS was upgraded within a couple of years to
> use all 32 bits of a pointer.

  1) The Amiga coding standards from day one emphasized "32-bit" clean,
since
there were already plans for a 68020 based machine.  (In fact, the first
68020 demo I saw, under non-disclosure, was running AmigaDOS 1.1.)

  2) Actually the problem was that it stored pointers in 3 bytes, not 4,
I 
think I still have the patch to fix it floating around.  (It was an
extremely small patch.)

  3) The developer of AmigaBASIC was Microsoft, and they refused to make
the
fix even when asked by Commodore.

  4) That was why AmigaBASIC was dropped in the next version of
AmigaDOS.
    
> Some "efficiencies" aren't worth the risk, and the damage to pointer
> semantics of using some bits for "non-pointer purposes" would be nearly
> incalculable.

    I think that Robert Dewar was referring to the low-order two bits,
which
were, of course, unavailable in Microsoft's AmigaBASIC.
 
> Oh, and did you lock your structures against traversal by other threads
> while the (possibly time consuming) deep copy was ongoing, or are the
> munged pointers going to be visible outside the deep copy process?

    You had better do lcoking in any case.  But since the flipped bits
can be in your new data structure only, you don't have to worry about
some other assignment geting at them.

-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Safety of the Booch Ada 95 Components

[Hyman Rosen]

"Matthew Heaney" <matthew_heaney@acm.org> writes:
> We make this assumption per the "design-by-contract" model.  If you give
> me an assignment operator that doesn't work, and it raises an exception
> (say), then yes, that would leave the target object in an inconsistent
> state.
> 
> If you don't like that, then don't give me a broken assignment operator.

Why is an assignment operator that raises an exception broken?

Re: Safety of the Booch Ada 95 Components

[Robert I. Eachus]

Hyman Rosen wrote:
 
> Why is an assignment operator that raises an exception broken?

   It isn't.  But in Ada, an assignment that raises an exception does so
before actually "copying the bits."  So that objects that were
consistant are not broken except by an explicit abort from some other
task while outside an abort-deferred region.  However, one explicit
abort-deferred operation is: "an assignment operation to an object with
a controlled part." RM9.8(11)  There other such operations included so
that a user of an object of a controlled type can expect that the value
is never corrupted.

   So any user of an Ada package which did corrupt objects in this
manner would be consider it to be broken.
 
-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

"Robert I. Eachus" <eachus@mitre.org> writes:

> Hyman Rosen wrote:
>  
> > Why is an assignment operator that raises an exception broken?
> 
>    It isn't.  But in Ada, an assignment that raises an exception does so
> before actually "copying the bits."

I don't believe this is true. See LRM 7.6(2).

>                                      So that objects that were
> consistant are not broken except by an explicit abort from some other
> task while outside an abort-deferred region.  However, one explicit
> abort-deferred operation is: "an assignment operation to an object with
> a controlled part." RM9.8(11)  There other such operations included so
> that a user of an object of a controlled type can expect that the value
> is never corrupted.
> 
>    So any user of an Ada package which did corrupt objects in this
> manner would be consider it to be broken.

Since (LRM 7.6(2)) Adjust is called as the _last_ step of an
assignment, I don't see how the provider of an Ada package can do as
you ask.

I'm going to do a deep copy.

I have an object containing a pointer to the value that has been
assigned, so I need to make the deep copy and then put a pointer to
the copy in the current object.

If that fails, presumably because of memory exhaustion, I can

(1) make sure that the assignee has a valid but partial copy

(2) make sure that the assignee has a null pointer

(3) leave the assignee pointing to the value that has been assigned,
    so that the copy isn't deep after all

(4) not bother

In *none* of these cases is the assignee "valid". Whether that equates
to being "corrupt" is a question I prefer to leave to the reader ..

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Simon Wright <simon@pogner.demon.co.uk> wrote:

> "Robert I. Eachus" <eachus@mitre.org> writes:
> 
> > Hyman Rosen wrote:
> >  
> > > Why is an assignment operator that raises an exception broken?
> > 
> >    It isn't.  But in Ada, an assignment that raises an exception does so
> > before actually "copying the bits."
> 
> I don't believe this is true. See LRM 7.6(2).
> 
> >                                      So that objects that were
> > consistant are not broken except by an explicit abort from some other
> > task while outside an abort-deferred region.  However, one explicit
> > abort-deferred operation is: "an assignment operation to an object with
> > a controlled part." RM9.8(11)  There other such operations included so
> > that a user of an object of a controlled type can expect that the value
> > is never corrupted.
> > 
> >    So any user of an Ada package which did corrupt objects in this
> > manner would be consider it to be broken.
> 
> Since (LRM 7.6(2)) Adjust is called as the _last_ step of an
> assignment, I don't see how the provider of an Ada package can do as
> you ask.
> 
> I'm going to do a deep copy.
> 
> I have an object containing a pointer to the value that has been
> assigned, so I need to make the deep copy and then put a pointer to
> the copy in the current object.
> 
> If that fails, presumably because of memory exhaustion, I can
> 
> (1) make sure that the assignee has a valid but partial copy
> 
> (2) make sure that the assignee has a null pointer
> 
> (3) leave the assignee pointing to the value that has been assigned,
>     so that the copy isn't deep after all
> 
> (4) not bother
> 
> In *none* of these cases is the assignee "valid". Whether that equates
> to being "corrupt" is a question I prefer to leave to the reader ..

For comparison, the C++ 98 solution is that the deep copy will throw a
bad_alloc exception, and return the memory to the free store. If the
deep copy was being done as an initialization step during a constructor,
the constructor is unwound, and the bad_alloc exception propagates up.
If the deep copy was being done in a different context, the calling
routine needs to catch the bad_alloc exception, or it will propagate up.
STL containers will be left usable (and for most operations, unchanged
and with their iterators still valid).  The pointer being assigned to,
if it is still in scope after the bad_alloc is caught, will have its
original value. If that was corrupt, it will still be corrupt. I teach
my students to habitually tie off all pointers so that they either point
to valid memory or have the sentinel value of 0, so that delete and
delete[] will work correctly.

-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Mats Weber]

Simon Wright wrote:

> I'm going to do a deep copy.
> 
> I have an object containing a pointer to the value that has been
> assigned, so I need to make the deep copy and then put a pointer to
> the copy in the current object.
> 
> If that fails, presumably because of memory exhaustion, I can
> 
> (1) make sure that the assignee has a valid but partial copy
> 
> (2) make sure that the assignee has a null pointer
> 
> (3) leave the assignee pointing to the value that has been assigned,
>     so that the copy isn't deep after all
> 
> (4) not bother

(5) raise or propagate and exception. I think this is the only right
thing to do. Being tagged, controlled types are passed by reference, so
you can also make sure the target of the assignement has a null pointer.

> In *none* of these cases is the assignee "valid". Whether that equates
> to being "corrupt" is a question I prefer to leave to the reader ..

How could it possibly be valid if memory is exhausted, in any
programming language ?

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

Mats Weber <matsw@mail.com> writes:

> Simon Wright wrote:
> 
> > I'm going to do a deep copy.
> > 
> > I have an object containing a pointer to the value that has been
> > assigned, so I need to make the deep copy and then put a pointer to
> > the copy in the current object.
> > 
> > If that fails, presumably because of memory exhaustion, I can
[...]
> (5) raise or propagate and exception. I think this is the only right
> thing to do. Being tagged, controlled types are passed by reference, so
> you can also make sure the target of the assignement has a null pointer.

I forgot to say that I was going to do that anyway! thanks for the
note ..

Re: Safety of the Booch Ada 95 Components

[Matthew Heaney]

In article <t7g0x64nw6.fsf@calumny.jyacc.com> , Hyman Rosen 
<hymie@prolifics.com>  wrote:

>> If you don't like that, then don't give me a broken assignment operator.
>
> Why is an assignment operator that raises an exception broken?

Perhaps the case is better stated in terms of the postcondition of the
copy.  If item assignment raises an exception during a copy of a data
structure (which contains zero or more items), then

1) You can implement Copy without handling item assignment errors.  This
is the most efficient way to implement copy, but it will leave the
target data structure in an unknown state.

2) You can implement Copy so that if item assignment raises an
exception, then the target data structure is cleared or only a partial
copy.  This is slightly less efficient than (1) -- unless your compiler
implements zero-cost exception handlers -- but it has the virtue of
guaranteeing the target state.

3) You can implement Copy so that if assignment raises an exception,
then the target data structure is rolled back to its original state
prior to the call.  This is much less efficient than (1), but has the
virtue of leaving target state unchanged.

So take your pick.  As with all system design problems, there is no such
thing as a free lunch, and you're going to have to live with some
compromise.

--
It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Hyman Rosen <hymie@prolifics.com> wrote:

> "Matthew Heaney" <matthew_heaney@acm.org> writes:
> > I don't understand your comment about not being "exception-safe."
> > Perhaps you could elaborate on that point.
> 
> In C++, class objects are copied through a class method called the
> copy-constructor, to allow for resource control. If an exception is
> thrown during copy-construction of one of the elements, it's possible
> that the target data structure may be left in an invalid state.

And it usually takes some care to avoid that happening. Strong exception
safety goes even further, requiring commit/rollback semantics.

-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Matthew Heaney <matthew_heaney@acm.org> wrote:

> In article <1e2lds4.7trgj21rgj9i0N%herwin@gmu.edu> , herwin@gmu.edu 
> (Harry Erwin) wrote:
> 
> > Now I've been looking at the Booch components for Ada 95, and have
> > noticed that the Copy function typically starts by clearing the To
> > container.
> 
> I haven't studied the Booch components specifically, but here's how Copy
> operations should be implemented in general.
> 
> Assuming the data structure is implemented as a by-reference type (the
> type is tagged and/or limited), you can invoke RM95 13.3 (16) to legally
> compare the addresses of the subprogram parameters:
> 
>   procedure Copy
>     (From : in     Source_Type;
>      To   : in out Target_Type) is
>   begin
>     if From'Address = To'Address then
>       return;  -- do nothing, because From is same object as To
>     end if;

That's missing from the code I've been looking at.

> 
>     Clear (To);  -- safe, because we now know To isn't From
> 
>     <do rest of copy>
>   end Copy;
> 
> If the Booch Components don't first check whether aliasing has occurred,
> prior to clearing the target object, then perhaps something is wrong.
> 
> 
> > That immediately implies that they are not exception-safe,
> > but I'm concerned that they may not be safe under self-assignment as
> > well.
> 
> I don't understand your comment about not being "exception-safe."
> Perhaps you could elaborate on that point.

Strong exception-safety == supports commit/rollback semantics.
Apparently in the Booch components, if the copy goes bad, the To
container has been cleared and is partially written. Basic exception
safety (== the container is still useable) is probably supported.

> 
> 
> >  Is there something about the Ada 95 standard that guarantees that
> > there will be no aliasing of container args?
> 
> No, it's up to you the programmer to determine whether aliasing has
> occurred.

That may not be possible.

> 
> The idiom for determining whether aliasing has occurred is to compare
> object addresses, per RM95 13.3 (16).

Got it.  Thanks!

> 
> 
> --
> Help keep evolution in the science classroom and religion out: become a
> member of the National Center for Science Education.
> 
> <http://www.natcenscied.org/>


-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

herwin@gmu.edu (Harry Erwin) writes:

> Matthew Heaney <matthew_heaney@acm.org> wrote:
> 
> >   procedure Copy
> >     (From : in     Source_Type;
> >      To   : in out Target_Type) is
> >   begin
> >     if From'Address = To'Address then
> >       return;  -- do nothing, because From is same object as To
> >     end if;
> 
> That's missing from the code I've been looking at.

Yes, a clear defect, logged.

> Strong exception-safety == supports commit/rollback semantics.

Is that a standard definition?

> Apparently in the Booch components, if the copy goes bad, the To
> container has been cleared and is partially written. Basic exception
> safety (== the container is still useable) is probably supported.

Yes, this is the case for the Copy operation (which is *not* the
standard assignment operation!).

In a previous reply, I quoted the ALRM [7.6(17)] on controlled
assignment. I must say I don't fully understand from that what is
expected. At first (& nth) sight I don't see how one could achieve
your idea of strong exception safety.

I wonder what happens in C++ STL-based programming if operator new
fails in the middle of things?

Re: Safety of the Booch Ada 95 Components

[Harry Erwin]

Simon Wright <simon@pogner.demon.co.uk> wrote:

> herwin@gmu.edu (Harry Erwin) writes:
> 
> > Matthew Heaney <matthew_heaney@acm.org> wrote:
> > 
> > >   procedure Copy
> > >     (From : in     Source_Type;
> > >      To   : in out Target_Type) is
> > >   begin
> > >     if From'Address = To'Address then
> > >       return;  -- do nothing, because From is same object as To
> > >     end if;
> > 
> > That's missing from the code I've been looking at.
> 
> Yes, a clear defect, logged.

That's the feedback I needed.  Thanks.

> 
> > Strong exception-safety == supports commit/rollback semantics.
> 
> Is that a standard definition?

Herb Sutter, Exceptional C++, Addison-Wesley, 2000, page 38.

"2. Strong guarantee: If an operation terminates because of an
exception, program state will remain unchanged. This always implies
commit-or-rollback semantics, including that no references or iterators
into the container be invalidated if an operation fails. . . ."

Also see <http://www.metabyte.com/~fbp/stl/eh_contract.html>

> 
> > Apparently in the Booch components, if the copy goes bad, the To
> > container has been cleared and is partially written. Basic exception
> > safety (== the container is still useable) is probably supported.
> 
> Yes, this is the case for the Copy operation (which is *not* the
> standard assignment operation!).

What is the standard assignment operation, then?  I'm new to Ada 95.  In
C++ 99, we rarely trust the compiler-defined default versions of copy
constructors and assignment operations, because they do bit-by-bit
copies. 

> 
> In a previous reply, I quoted the ALRM [7.6(17)] on controlled
> assignment. I must say I don't fully understand from that what is
> expected. At first (& nth) sight I don't see how one could achieve
> your idea of strong exception safety.
> 
> I wonder what happens in C++ STL-based programming if operator new
> fails in the middle of things?

The constructor is rolled back, with destructors applied in reverse
order to all the data members that were successfully constructed, and
then the memory is returned to the free store.  Finally, the bad_alloc
exception is thrown. Eventually a catch block for bad_alloc is
encountered as the function calls are unwound on the stack, and the
processing is done there. Or, eventually, the main function is unwound,
and the program is terminated.

-- 
Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

Re: Safety of the Booch Ada 95 Components

[Simon Wright]

herwin@gmu.edu (Harry Erwin) writes:

> Simon Wright <simon@pogner.demon.co.uk> wrote:
[...]
> > > Apparently in the Booch components, if the copy goes bad, the To
> > > container has been cleared and is partially written. Basic exception
> > > safety (== the container is still useable) is probably supported.
> > 
> > Yes, this is the case for the Copy operation (which is *not* the
> > standard assignment operation!).
> 
> What is the standard assignment operation, then?  I'm new to Ada 95.  In
> C++ 99, we rarely trust the compiler-defined default versions of copy
> constructors and assignment operations, because they do bit-by-bit
> copies. 

The standard Ada assignment operation is :=

However, it's not an operation that you have control over in the way
that C++ gives you with operator=.

What you do have is Controlled types (types that inherit from
Ada.Finalization.Controlled).

From ALRM,

7.6 User-Defined Assignment and Finalization

(1) Three kinds of actions are fundamental to the manipulation of
     objects: initialization, finalization, and assignment. Every
     object is initialized, either explicitly or by default, after
     being created (for example, by an object_declaration or
     allocator).  Every object is finalized before being destroyed
     (for example, by leaving a subprogram_body containing an
     object_declaration, or by a call to an instance of
     Unchecked_Deallocation). An assignment operation is used as part
     of assignment_statements, explicit initialization, parameter
     passing, and other operations.

(2) Default definitions for these three fundamental operations are
     provided by the language, but a controlled type gives the user
     additional control over parts of these operations. In particular,
     the user can define, for a controlled type, an Initialize
     procedure which is invoked immediately after the normal default
     initialization of a controlled object, a Finalize procedure which
     is invoked immediately before finalization of any of the
     components of a controlled object, and an Adjust procedure which
     is invoked as the last step of an assignment to a (nonlimited)
     controlled object.

[...]

(17) For an assignment_statement, after the name and expression have
     been evaluated, and any conversion (including constraint
     checking) has been done, an anonymous object is created, and the
     value is assigned into it; that is, the assignment operation is
     applied. (Assignment includes value adjustment.) The target of
     the assignment_statement is then finalized. The value of the
     anonymous object is then assigned into the target of the
     assignment_statement. Finally, the anonymous object is
     finalized. As explained below, the implementation may eliminate
     the intermediate anonymous object, so this description subsumes
     the one given in 5.2, ``Assignment Statements''.

I don't think there's a web version of the ALRM at
www.adapower.com. There is one at www.adahome.com (no longer
maintained, it seems, but still with goodies like this).

Re: Safety of the Booch Ada 95 Components

[Tucker Taft]

Harry Erwin wrote:
> ... I'm concerned that they may not be safe under self-assignment as
> well. Is there something about the Ada 95 standard that guarantees that
> there will be no aliasing of container args?

No.  On the other hand, self-assignment is always safe in Ada,
even if the type is controlled, because the "official" semantic model
is that there is an anonymous intermediary object created for
an assignment statement (see RM95 7.6(17)).  If a compiler "optimizes"
this away, it must not create problems with self-assignment.

The simplest way to avoid creating self-assignment problems is to take
advantage of RM95 7.6(19) which says self-assignment may be implemented as a 
no-op.  This permission, plus the ability to do slice-assignment either
left-to-right or right-to-left, means that there is never a need
for an intermediary object in an assignment (and our front end never 
creates one).  

From other responses, it sounds like GNAT uses this approach as well.
But whatever (non-buggy ;-) approach the compiler uses, self-assignment is always safe in Ada.

> Harry Erwin, PhD, <http://mason.gmu.edu/~herwin>

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA