Re: Comments on generic stack?

Re: Comments on generic stack?

[Michel Gauthier]

In article <4i6l2t$j1q@dmsoproto.ida.org>, wheeler@aphrodite.csed.ida.org
(David Wheeler) wrote:

>> [...]
>>  
>>  Below is yes, yet another implementation of an unbounded stack. This one
>>  supports assignment (:=), equality (=), and finalizes correctly, as
>>  well as supporting the tried and true Pop and Push operations.
>>  It's a generic that requires the Item to have := and =, but since the
>>  stack itself has those operations it is composable (you can have a
>>  Stack of Stacks of Integers).

Sorry to disturb, but I cannot understand what is a stack of stacks.

Stacks are designed to organise values, not objects. 
Stacks are objects, not values.
How can you define stacks of stacks ?

David probably means either stacks of (item=>references to stacks) or stacks of
(item=> some implementation of the stack abstract type with an initial algebra
behaviour). The latter actual type is an academic feature that has strictly no 
practical use.

----------          ----------          ----------          ---------- 
Michel Gauthier / Laboratoire d'informatique
123 avenue Albert Thomas / F-87060 Limoges
telephone +33 () 55457335 [or ~ 7232]
fax +33 ()  55457315  [or ~7201]
----------          ----------          ----------          ----------
La grande equation de la fin du siecle : windows-X = Mac-Y
The main end-of-century equation : windows-X = Mac-Y
----------          ----------          ----------          ----------
Si l'an 2000 est pour vous un mysticisme stupide, utilisez la base 9
If you feel year 2000 a stupid mystic craze, use numeration base 9
----------          ----------          ----------          ----------

Re: Comments on generic stack?

[David Wheeler]

Michel Gauthier (gauthier@unilim.fr) wrote:
: In article <4i6l2t$j1q@dmsoproto.ida.org>, wheeler@aphrodite.csed.ida.org
: (David Wheeler) wrote:
....
: >>  It's a generic that requires the Item to have := and =, but since the
: >>  stack itself has those operations it is composable (you can have a
: >>  Stack of Stacks of Integers).

: Sorry to disturb, but I cannot understand what is a stack of stacks.

There are two issues here: (1) generality of a reusable component, and
(2) usability of stacks of stacks.  Let's talk about them one at a time.

(1) I strive to make reusable components general enough so that they can be
reused in many different contexts.  One way to _test_ the generality of
a component is to see if it's composable (i.e. can you build more
complex structures using it), and the simplest way to check that is
to try to compose it using itself.  I've written a paper that includes a 
discussion on the subject: "Analysis and Guidelines for Reusable Ada
Software", IDA Paper P-2765, August 1992.

Is composability of reusable components useful?  Well, are arrays of arrays
useful? If you believe the answer is "yes", then you know your answer.

(2) Are stacks of _stacks_ useful?  Well, not as useful as arrays of arrays.
However, if I can support stacks of stacks, I can also support other
combinations that are more likely to be useful.  And I _can_ imagine
"stacks of stacks" being useful in certain complicated parsing systems.

: Stacks are designed to organise values, not objects. 
: Stacks are objects, not values.

Not true.  This stack organizes Items. Items might be values, or they might
be references.  There is no reason to assume they must be one or the other.
For performance reasons you might choose to stack references instead of
the actual values, but there's no reason they MUST be one or the other.

: How can you define stacks of stacks ?

-- Easy; here's a stack of stacks of Integers:

with Generic_Stack, Stack_Int;

package Stack_Stack_Int is new Generic_Stack(Stack_Int.Stack);


with Generic_Stack;

package Stack_Int is new Generic_Stack(Integer);

: David probably means either stacks of (item=>references to stacks) or
: stacks of
: (item=> some implementation of the stack abstract type with an initial algebra
: behaviour).
: The latter actual type is an academic feature that has strictly no 
: practical use.

Disagree; see my example of arrays of arrays.

It _is_ true that my current implementation of adjust makes stack assignment
a big-ticket performance hit, but there are ways to reduce that cost in
most cases if you'd like to implement that.  You wouldn't even need to
change the visible specification.

In summary: the issue of having flexible reusable components is _NOT_
just an academic issue, and checking for composability helps you get there.

If I were _really_ serious about making my generic stack general I'd add
some iterators; for demonstration purposes I'm not sure I'll bother.

--- David
    wheeler@ida.org

"Object" types vs. "Value" types

[John G. Volan]

In article <4ih2pv$pku@dmsoproto.ida.org>
David Wheeler, wheeler@aphrodite.csed.ida.org writes:
>Michel Gauthier (gauthier@unilim.fr) wrote:
...
>: Stacks are designed to organise values, not objects. 
>: Stacks are objects, not values.
>
>Not true.  This stack organizes Items. Items might be values, or they might
>be references.  There is no reason to assume they must be one or the other.
>For performance reasons you might choose to stack references instead of
>the actual values, but there's no reason they MUST be one or the other.
...
>: David probably means either stacks of (item=>references to stacks) or
>: stacks of
>: (item=> some implementation of the stack abstract type with an initial algebra
>: behaviour).
>: The latter actual type is an academic feature that has strictly no 
>: practical use.
>
>Disagree; see my example of arrays of arrays.
...

In his book _Object Oriented Analysis and Design With Applications_,
Grady Booch defines an "object" as something which has "state",
"behavior, and "identity." 
    
Booch defines "state" as:

    The state of an object encompasses all of the (usually static)
    properties of the object plus the current (usually dynamic)
    values of each of these properties.
    
Booch quotes Khoshafian and Copeland's definition of "identity":

    Identity is that property of an object which distinguishes
    it from all other objects.
    
The identity of an object is something ineffably linked with that
object, and with that object alone.  Even if two objects are both in
exactly the same state, they are still distinct objects, because their
identities are different. On the flip side, the identity of an object
is that property which never changes, regardless of all the changes of
state that it experiences.

In light of these notions, I long ago came to the conclusion that, as
far as programming was concerned, there was a useful distinction to be
made between two sorts of data types: "object" types and "value"
types. An "object" type is a data type for which the distinction
between "identity" and "state" was strong, whereas a "value" type would
lack this strong distinction.

A "value" can be duplicated in many different locations, and each
instance of that "value" would be considered "identical" to all the
others.  No matter where you saw it, it would be the "same value".

An "object", on the other hand, can occupy only one location, and cannot
be "duplicated" elsewhere, not as such. You might be able to duplicate
the _state_ of an object into another location, but then you wouldn't 
conclude that you then had the "same object" at that new location. 
Rather, you would conclude that there was a _different_ object at that
location, and now that object happened to have the "same state" as
your original object.

At least, for the moment -- the state of an object can change.  Yet even
when that happens, the object doesn't suddenly become a "different
object." It always remains the "same object."  It just goes into
different states at different times.  Those different states might
change its behavior, but it still remains "itself."

Conversely, "values," as such, do not have states that can change.  In a
certain Platonic-ideal sense, a "value" is something eternal and
unchanging. Now, understand what I mean by this:  Let's say for
instance that you see the number 2 at a particular location at a
particular time, and then later see a different number, say 3, at that
location. The value _at_ that location changed, but in no way did "the
number 2" change. The number 2 is still the integer value that follows
1 and precedes 3 -- always has been and always will be.  And the
behavior of "the number 2" never changes, either:  If you add one to
the number 2, you'll always get the number 3, and if you subtract one
from it, you'll always get the number 1.  Always, forever and ever,
world without end, amen.  :-)

What does all this philosophizing have to do with Ada?  Well, IMHO, this
distinction between "objects" and "values" maps quite neatly to the Ada
concept of limited versus non-limited types.  In my view, if you're
going to categorize something as an "object", and invest it with all
the connotations implied by that designation, then by rights the type
ought to be limited.

Assignment just doesn't make sense for an "object" type.  You shouldn't
be able to just "copy" an object willy-nilly -- what would that mean?
Oh, you could copy the _state_ of that object into another object
(write yourself a Copy procedure). Or you could copy the _identity_
('Access) of that object from one (access) variable to another (access)
variable.  But copy the "object" per se?  No, I'd rather shut off
assignment rather than open up that can of worms.  Physical objects in
the real world don't go around being indiscriminately replicated (Star
Trek's replicators are still just a fantasy), so I'd prefer the
"objects" in my software to share the same kind of "solidity."

On the other hand, if you do have a data abstraction for which
assignment makes sense, that's okay too, you can make it non-limited --
I just wouldn't call that an "object" type, I'd call it a "value" type.

Note that there's nothing about this notion of "value" types that
precludes such "object-oriented" concepts as "inheritance" and
"polymorphism" and "type extension" and "dynamic dispatching."  I think
it's perfectly reasonable to talk about having classes of "value"
types, with derived value types inheriting attributes and behavior from
ancestor value types, and adding new attributes and behavior, and so
forth.  "Value" classes can work just like "object" classes -- the only
difference is that assignment is defined for the former but shut off
for the latter.

(Indeed, it's my humble (and perhaps radical) opinion that the very term
"object-oriented" is a misnomer.  The paradigm that everybody is so
gung-ho about these days should have been called "*CLASS*-oriented"
programming.  A programming language could hypothetically give you
_objects_ without necessarily giving you _classes_ as well.  It's the
_classes_, and the relationships between them, that give you all that
juicy inheritance and polymorphism.)

There's also nothing in this "value" concept that precludes the use of
unbounded dynamic data structures or structural sharing.  All of that
is just private implementation details anyway.  The bottom line is that
if you want assignment to be meaningful for your data abstraction, then
the publicly-visible semantics of your abstraction have to be totally
stripped of any notion of unique identity.  If you use assignment to
duplicate a particular "value" to numerous locations, every single
instance of that "value" must behave exactly like every other instance,
without any "identifiable" distinction between them.  If you assign a
"different value" into one of those locations, this should not affect
the behavior of the original value manifested at any of the other
locations. Moreover, if you do any other kind of operation with a side
effect that changes the "value" in one particular variable, none of the
other variables still holding the old value should behave any
differently, even if secretly all those variables were sharing a data
structure. Whatever machinations you have to engage in behind the
scenes in order to achieve these effects doesn't matter, as long as the
semantics of "value" types is maintained as far as clients are
concerned.

Contrast this with a limited "object" type:  You won't be able to use
assignment to copy an "object" to multiple locations, although you
might make multiple copies of an _access value_ that "identifies" that
object. However, if then you perform an operation through one of these
pointers that changes the state of the designated object, then the same
change of state will automatically be observed through all of the other
pointers designating that same object.

Now, as for a particular abstract data type, such as our moldy old
friend, the stack:  Is a stack an "object"?  Or is it a "value"?
"Object"? "Value"? "OBJECT"? "VALUE"? <getting delirious> WELL, IS IT
ONE OR THE OTHER?!?!?!?!?!?!?!?!?

My answer is: FOR GOODNESS SAKES, YES!!!!!!!!!!!     :-)  :-)  :-)

It can be _either_, depending on how you choose to perceive it.  I
believe most folks would tend to view a stack as an "object" (and
that's how I tend to view it myself), on the grounds that the Push and
Pop operations are thought of as having "side-effects."  However, I
admit that one might reasonably argue for a view that interprets a
stack as a "value," by analogy with another "aggregate" abstraction:
the array.

Array types in Ada are non-limited, so you can do assignment on them. 
If two arrays happen to hold the same sequence of element values, then
they're considered to have the same "array value."  By analogy, one
might say that two stacks that contain the same sequence of stacked
element values should be considered as the same "stack value."

My philosophy: Pick whichever semantic scheme best fits your
application, implement it, and be happy.  Just call it by the right
name. :-)

I even reflect that philosophy in my chosen naming style:  I tend to let
the package name carry the sense of an abstraction, and I use some
"nondescript" identifier for the type encapsulated in the package, on
the grounds that everybody should refer to it as "Package.Type" anyway.
Well, "Object" is the nondescript identifier I will pick, if and only
if the type is limited.  "Value" is the nondescript identifier I'll
pick, if and only if the type is non-limited.

So, for example, if a stack is an "object", I'll have:

    generic
        type Item is private;
    package Stack is
        type Object is limited private;
        ...
    end Stack;
    
Otherwise, if a stack is just a "value", I'll have:

    generic
        type Item is private;
    package Stack is
        type Value is private;
        ...
    end Stack;

------------------------------------------------------------------------
Internet.Usenet.Put_Signature
( Name => "John G. Volan", E_Mail => "John_Volan@dayton.saic.com",
  Favorite_Slogan => "Ada95: The *FIRST* International-Standard OOPL",
  Humorous_Disclaimer => "These opinions are undefined by SAIC, so" &
    "any use would be erroneous ... or is that a bounded error now?" );
------------------------------------------------------------------------

Re: "Object" types vs. "Value" types

[John DiCamillo]

John G. Volan <John_Volan@ccmail.dayton.saic.com> writes:

[a pretty darn good analysis of object vs. value types deleted]

>(Indeed, it's my humble (and perhaps radical) opinion that the very term
>"object-oriented" is a misnomer.  The paradigm that everybody is so
>gung-ho about these days should have been called "*CLASS*-oriented"
>programming.  A programming language could hypothetically give you
>_objects_ without necessarily giving you _classes_ as well.

Not hypothetically, it's been done: see Self, Cecil, and Obliq.

Given your analysis of object vs. value types, you might enjoy
reading the Obliq paper -- Obliq is a distributed scripting
language in which objects behave pretty much as you described
them.  Obliq objects are all 'network objects' which have not
just state but *location* in a distributed computing environment.
Objects can not be assigned, but they can be *cloned*, even
from one machine to another across a network.

>It's the
>_classes_, and the relationships between them, that give you all that
>juicy inheritance and polymorphism.)

Oh, and you were doing so well, too.  Prototypic object-oriented
languages frequently provide inheritance and polymorphism without
classes.  Some languages implement inheritance through 'delegation'
and effectively allow objects to change their 'type' at run time
by redirecting a 'parent' pointer.

-- 
    ciao,
    milo
================================================================
    John DiCamillo                         Fiery the Angels Fell 
    milod@netcom.com       Deep thunder rode around their shores

Re: Comments on generic stack?

[John G. Volan]

In article <milodDoKr88.876@netcom.com> John DiCamillo, milod@netcom.com
writes:
>John G. Volan <John_Volan@ccmail.dayton.saic.com> writes:
>
>[a pretty darn good analysis of object vs. value types deleted]
>
>>(Indeed, it's my humble (and perhaps radical) opinion that the very term
>>"object-oriented" is a misnomer.  The paradigm that everybody is so
>>gung-ho about these days should have been called "*CLASS*-oriented"
>>programming.  A programming language could hypothetically give you
>>_objects_ without necessarily giving you _classes_ as well.
>
>Not hypothetically, it's been done: see Self, Cecil, and Obliq.

I knew that. No, really, I did, I did!  :-)

Seriously though, I had a feeling that someone would bring up
prototype/delegation-based languages.  However, what I really had in
mind was a hypothetical language that allowed you to encapsulate state
data together with state-changing operations, but that lacked any
notion of types/classes/prototypes. It would be something like a
brain-damaged Ada with packages but no record types. A package with
variables hidden in its body can act as a sort of "object", but it
would be a one-of-a-kind thing.  You wouldn't get any sense of having
many instances sharing common behavior and structural layout.  Yet
you'd still be able to claim you had a language that gave you
"objects."

>Given your analysis of object vs. value types, you might enjoy
>reading the Obliq paper -- Obliq is a distributed scripting
>language in which objects behave pretty much as you described
>them.  Obliq objects are all 'network objects' which have not
>just state but *location* in a distributed computing environment.
>Objects can not be assigned, but they can be *cloned*, even
>from one machine to another across a network.

Sounds interesting enough ... how about posting a pointer to this?

>>It's the
>>_classes_, and the relationships between them, that give you all that
>>juicy inheritance and polymorphism.)
>
>Oh, and you were doing so well, too.  Prototypic object-oriented
>languages frequently provide inheritance and polymorphism without
>classes.  Some languages implement inheritance through 'delegation'
>and effectively allow objects to change their 'type' at run time
>by redirecting a 'parent' pointer.

I guess what I was trying to say was that for those languages that do
use classes (Ada95, C++, Eiffel, Smalltalk, etc.) it's the classes, not
the objects, that make things so "sexy."  Likewise, you could say that
the sexy features of prototype-oriented languages are the prototyping
and delegation mechanisms; the "objects" by themselves are more prosaic.

------------------------------------------------------------------------
Internet.Usenet.Put_Signature
( Name => "John G. Volan", E_Mail => "John_Volan@dayton.saic.com",
  Favorite_Slogan => "Ada95: The *FIRST* International-Standard OOPL",
  Humorous_Disclaimer => "These opinions are undefined by SAIC, so" &
    "any use would be erroneous ... or is that a bounded error now?" );
------------------------------------------------------------------------

Re: "Object" types vs. "Value" types

[david scott gibson]

In article <4inn6f$1at@dayuc.dayton.saic.com>,
John G. Volan  <John_Volan@ccmail.dayton.saic.com> wrote:

>In light of these notions, I long ago came to the conclusion that, as
>far as programming was concerned, there was a useful distinction to be
>made between two sorts of data types: "object" types and "value"
>types. An "object" type is a data type for which the distinction
>between "identity" and "state" was strong, whereas a "value" type would
>lack this strong distinction.

An interesting post!  I follow and agree with you most of the way, but
I'm a bit confused with your notion of "value types".  (I digress a bit
before getting to that :-).

>Assignment just doesn't make sense for an "object" type.  You shouldn't
>be able to just "copy" an object willy-nilly -- what would that mean?
>Oh, you could copy the _state_ of that object into another object
>(write yourself a Copy procedure). Or you could copy the _identity_
>('Access) of that object from one (access) variable to another (access)
>variable.  But copy the "object" per se?  No, I'd rather shut off
>assignment rather than open up that can of worms.  Physical objects in
>the real world don't go around being indiscriminately replicated 

Copying the abstract value (or state) of an object seems to require
creating a _new_ object which has the same abstract value as the
original object (although it may have a different concrete
representation).  For scalar types and simple aggregates of scalar
types, the effect of an assignment (:= with no Adjust) generally
corresponds to this behavior.  The old value of the target variable is
destroyed and is replaced by a copy of the source's value. This, in
essence, creates a new object identified by the target variable with
the same abstract value as the old object identified by the source
variable.  The total number of objects (as reflected by the number of
variables) is conserved.  Due partly to the simple one-to-one
correspondence between abstract values and concrete representations,
assignment provides the desired behavior in many cases.  If aliasing
is allowed, however, all bets are off and reasoning about the
resultant software becomes extremely difficult.

So how can you move around non-trivial objects for use in operations
without introducing aliasing?  Use swapping!  The Swap operation
exchanges the abstract values of two objects of any kind.  Swap can
always be implemented for a minimal constant cost and its use
maintains a conservation of objects which works well for modeling many
real world systems.  Copying, which might be implemented by :=
augmented with an appropriate Adjust, is often unnecessary, expensive,
and, cannot always be implemented (although the latter not often a
practical limitation).  For more info on swapping check out references
under: http://www.cis.ohio-state.edu:80/hypertext/rsrg/RSRG.html.

>On the other hand, if you do have a data abstraction for which
>assignment makes sense, that's okay too, you can make it non-limited --
>I just wouldn't call that an "object" type, I'd call it a "value" type.

What's an example of a true abstraction where "assignment" does make
sense?  It's not clear to me what you mean by a "value type".  Do you
consider the Ada type Integer a value type?  That's not an
abstraction, however, that's a representation.  The mathematical
integer type is an abstraction.  

>Note that there's nothing about this notion of "value" types that
>precludes such "object-oriented" concepts as "inheritance" and
>"polymorphism" and "type extension" and "dynamic dispatching."  I think
>it's perfectly reasonable to talk about having classes of "value"
>types, with derived value types inheriting attributes and behavior from
>ancestor value types, and adding new attributes and behavior, and so
>forth.  "Value" classes can work just like "object" classes -- the only
>difference is that assignment is defined for the former but shut off
>for the latter.

I'm not following this.  I don't understand your notion of "value
classes".

>"object-oriented" is a misnomer.  The paradigm that everybody is so
>gung-ho about these days should have been called "*CLASS*-oriented"
>programming.  A programming language could hypothetically give you
>_objects_ without necessarily giving you _classes_ as well.

Sure.  I consider good old Ada83 ADT-style programming to be
programming with objects.

>is just private implementation details anyway.  The bottom line is that
>if you want assignment to be meaningful for your data abstraction, then
>the publicly-visible semantics of your abstraction have to be totally
>stripped of any notion of unique identity.  

I'm not convinced that the assignment operation has a useful role in a
programming style which attempts to convey an abstract (human
understandable) model of a system.

>Contrast this with a limited "object" type:  You won't be able to use
>assignment to copy an "object" to multiple locations, although you
>might make multiple copies of an _access value_ that "identifies" that
>object. 

Use of pointers is embedded in the current state of practice, but it
makes formal reasoning about the code extremely difficult.
Correspondingly, visible use of pointers tends to make maintenance
extremely as difficult.  The RESOLVE language and discipline prohibits
aliasing in any form.  RESOLVE encapsulates much pointer functionality
in an "interesting" component called Chain_Position.  In RESOLVE/Ada,
access types types are only used in certain foundational components
upon which most components are built.  (See reference mentioned above
if you're curious.  BTW, RESOLVE/Ada95 should be out later this year.)

>Now, as for a particular abstract data type, such as our moldy old
>friend, the stack:  Is a stack an "object"?  Or is it a "value"?
>It can be _either_, depending on how you choose to perceive it.  I
>believe most folks would tend to view a stack as an "object" (and
>that's how I tend to view it myself), on the grounds that the Push and
>Pop operations are thought of as having "side-effects."  However, I
>admit that one might reasonably argue for a view that interprets a
>stack as a "value," by analogy with another "aggregate" abstraction:
>the array.

This seems like a purely concrete-level analogy.  Again I'm failing
so see why you would want to view a stack in this way.

>I even reflect that philosophy in my chosen naming style:  I tend to let
>the package name carry the sense of an abstraction, and I use some
>"nondescript" identifier for the type encapsulated in the package, on
>the grounds that everybody should refer to it as "Package.Type" anyway.

This sounds reasonable, but with long descriptive package names and
perhaps nested units, the dotted notation might get a bit unwieldy. 

Dave
--
dgibson@cis.ohio-state.edu

Re: "Object" types vs. "Value" types

[John G. Volan]

In article <4is7s0INN1gp@thalamus.cis.ohio-state.edu> 
david scott gibson, dgibson@thalamus.cis.ohio-state.edu writes:

>In article <4inn6f$1at@dayuc.dayton.saic.com>,
>John G. Volan  <John_Volan@ccmail.dayton.saic.com> wrote:
>
>>In light of these notions, I long ago came to the conclusion that, as
>>far as programming was concerned, there was a useful distinction to be
>>made between two sorts of data types: "object" types and "value"
>>types. An "object" type is a data type for which the distinction
>>between "identity" and "state" was strong, whereas a "value" type would
>>lack this strong distinction.
>
>An interesting post!  I follow and agree with you most of the way, but
>I'm a bit confused with your notion of "value types".  (I digress a bit
>before getting to that :-).
>
>>Assignment just doesn't make sense for an "object" type.  You shouldn't
>>be able to just "copy" an object willy-nilly -- what would that mean?
>>Oh, you could copy the _state_ of that object into another object
>>(write yourself a Copy procedure). Or you could copy the _identity_
>>('Access) of that object from one (access) variable to another (access)
>>variable.  But copy the "object" per se?  No, I'd rather shut off
>>assignment rather than open up that can of worms.  Physical objects in
>>the real world don't go around being indiscriminately replicated 
>
>Copying the abstract value (or state) of an object seems to require
>creating a _new_ object which has the same abstract value as the
>original object (although it may have a different concrete
>representation).  

On the contrary, copying of state does not necessarily imply _creating_
a new object.  The target object might already exist, and have existed
for a long time.  Maybe you're confusiong "copying" with "cloning".

>For scalar types and simple aggregates of scalar
>types, the effect of an assignment (:= with no Adjust) generally
>corresponds to this behavior.  The old value of the target variable is
>destroyed and is replaced by a copy of the source's value. This, in
>essence, creates a new object identified by the target variable with
>the same abstract value as the old object identified by the source
>variable.  

I don't see how any "objects" are either created or destroyed by
scalar assignment.  A variable that once held one value winds up
holding another value.  The assignment has nothing to do with
creating the target variable -- that was either done via a declaration
or by a dynamic allocator.

>The total number of objects (as reflected by the number of
>variables) is conserved.

Precisely.

>Due partly to the simple one-to-one
>correspondence between abstract values and concrete representations,
>assignment provides the desired behavior in many cases.  If aliasing
>is allowed, however, all bets are off and reasoning about the
>resultant software becomes extremely difficult.

Could you elaborate on why you think aliasing makes reasoning about
a program harder?

>So how can you move around non-trivial objects for use in operations
>without introducing aliasing?  Use swapping!  The Swap operation
>exchanges the abstract values of two objects of any kind.  Swap can
>always be implemented for a minimal constant cost and its use
>maintains a conservation of objects which works well for modeling many
>real world systems.

This is interesting because to a certain extent it simulates the
commonly observed behavior of _physical_ objects:  A physical object
can only occupy one location at a time, but it often can be moved from
one location to another.  When moved, an object simultaneously ceases
to occupy its previous location and commences occupying a new location.
If another object already occupies the new location, it will not simply
cease to exist -- it will either obstruct the move in the first place,
or it will be displaced (i.e., it will be moved to another location in
turn).  One possibility is that the displaced object could rush to fill
the vacuum created at the old location -- in other words, the two
objects could swap locations.  Similarly, when an object is moved from
one location into an already-vacant location, leaving behind it a newly
vacant location, I suppose you could look at that as swaping an object
and a vacuum.

This sounds a lot like some of Henry Baker's work.

>Copying, which might be implemented by :=
>augmented with an appropriate Adjust, is often unnecessary, expensive,
>and, cannot always be implemented (although the latter not often a
>practical limitation).  For more info on swapping check out references
>under: http://www.cis.ohio-state.edu:80/hypertext/rsrg/RSRG.html.
>
>>On the other hand, if you do have a data abstraction for which
>>assignment makes sense, that's okay too, you can make it non-limited --
>>I just wouldn't call that an "object" type, I'd call it a "value" type.
>
>What's an example of a true abstraction where "assignment" does make
>sense?

[See below]

>It's not clear to me what you mean by a "value type".  Do you
>consider the Ada type Integer a value type?  

Yes, indeed.

>That's not an
>abstraction, however, that's a representation.  The mathematical
>integer type is an abstraction.

Perhaps we're using different definitions of the word "abstraction".
In software terms, I tend to use Booch's definition:

    abstraction = The essential characteristics of an object that
    distinguish it from all other kinds of objects and thus provide
    crisply-defined conceptual boundaries relative to the perspective
    of the viewer; the process of focusing upon the essential
    characteristics of an object.
    
(quoted from _Object Oriented Analysis and Design With Applications_).

In these terms, Ada integer types are very much an abstraction, not a
representation.  When dealing with integer types, we deliberately
suppress inessential details such as the sequence of bits that make up
the integer, their ordering, the encoding of the sign, and so forth, in
order to focus on essential details such as the meaning of operations
like 'Succ 'Pred + - * / and so forth.
  
Yes, it's true that the semantics of Ada integer types only constitute a
rough approximation of the semantics of the "mathematical integer type".
Certain limitations are necessary in order to make them practical to
implement, such as restricting them to finite sets of values (as
opposed the infinite set of true mathematical integers).  But that does
not preclude the characterization of Ada integers as abstractions.

Indeed, I view _all_ of Ada's types as abstractions to one degree or
another.  In every case, details of underlying representation are
deliberately suppressed in order to focus on a certain set of
crisply-defined semantic properties. 

>>..."Value" classes can work just like "object" classes -- the only
>>difference is that assignment is defined for the former but shut off
>>for the latter.
>
>I'm not following this.  I don't understand your notion of "value
>classes".

A "value class" would be a set of types including a root type and all
types derived from that type directly and indirectly, with the added
property that all the types in the class would be "value types", in the
sense that I've described.  That is, any instance of a value type would
lack all notion of individual identity or state.  A value can be copied
(via assignment) to as many variables as desired, and each
manifestation of that value would be considered the "same value." And
so forth, as I described before ...

>>"object-oriented" is a misnomer.  The paradigm that everybody is so
>>gung-ho about these days should have been called "*CLASS*-oriented"
>>programming.  A programming language could hypothetically give you
>>_objects_ without necessarily giving you _classes_ as well.
>
>Sure.  I consider good old Ada83 ADT-style programming to be
>programming with objects.

Right.

>>is just private implementation details anyway.  The bottom line is that
>>if you want assignment to be meaningful for your data abstraction, then
>>the publicly-visible semantics of your abstraction have to be totally
>>stripped of any notion of unique identity.  
>
>I'm not convinced that the assignment operation has a useful role in a
>programming style which attempts to convey an abstract (human
>understandable) model of a system.

I agree, for those abstractions in which "identity vs. state" is an
essential feature of the semantics.  But I see no problem with
assignment when an abstraction doesn't have a strong sense of "identity
vs. state"

>>Contrast this with a limited "object" type:  You won't be able to use
>>assignment to copy an "object" to multiple locations, although you
>>might make multiple copies of an _access value_ that "identifies" that
>>object. 
>
>Use of pointers is embedded in the current state of practice, ...

Because any non-trivial problem domain is going to involve associations
between different classes of objects.  Those various associations require
that the identity of a given object be referenced, potentially from
multiple locations. 

>...but it
>makes formal reasoning about the code extremely difficult.
>Correspondingly, visible use of pointers tends to make maintenance
>extremely as difficult.  

Why?  Please elaborate.  And at any rate, it seems to me that this issue
is inescapable in the general case.

>The RESOLVE language and discipline prohibits
>aliasing in any form.

And how does it manage that?  It seems to me that no matter how fancy
an abstraction you dress up your object-references, you still wind up
with the same object participating in multiple relationships.

>RESOLVE encapsulates much pointer functionality
>in an "interesting" component called Chain_Position. In RESOLVE/Ada,
>access types types are only used in certain foundational components
>upon which most components are built.

I have often thought that much of the trickyness of pointers (e.g.,
dangling references, garbage generation, etc.) could be avoided if
pointers were replaced with a more sophisticated abstraction that was
bi-directional.  In other words, any time some object A referenced
some other object B, not only would A "know" about the reference,
but B would know about it as well, and would effectively be 
referencing A in turn.  Disconnecting the reference from A to B
would also mean disconnecting the reference from B to A.  Destroying
an object would automatically entail disconnecting it from every
other associated object, thereby guaranteeing that no dangling
references would be left behind -- essentially, all associated
objects would be notified of its demise.

I can see how this might make it easier to reason about program
correctness than raw pointers.  (Is that the sort of thing your
"Chain_Position" component accomplishes?  The name is compelling.) 
Note, however, that this does not eliminate "aliasing" in any way, it
just makes it safer.

>(See reference mentioned above
>if you're curious.  BTW, RESOLVE/Ada95 should be out later this year.)

Um, printing postscript is a bit inconvenient in my environment at the
moment, and it will take some effort on my part.  In the meantime,
could you post a summary of the ideas behind this "RESOLVE" language?

>>...However, I
>>admit that one might reasonably argue for a view that interprets a
>>stack as a "value," by analogy with another "aggregate" abstraction:
>>the array.
>
>This seems like a purely concrete-level analogy.

Not at all.  An array is one kind of abstraction for a collection of
items, with certain semantics (e.g., it's an ordered, indexed
collection with a fixed length, each element of which can be
individually accessed and modified). A stack is another kind of
collection abstraction, with somewhat different semantics (e.g., it's
an ordered, unbounded collection with one active end that you Push onto
and Pop from).

>Again I'm failing
>so see why you would want to view a stack in this way.

Not _me_, other folks are trying to. :-)  Anyway, I was allowing for the
possibility of someone arguing thus:

"A stack is a kind of value with operations such as:

    function Push (The_Stack : in Stack.Value; New_Item : in Item)
        return Stack.Value;
        
    function Pop (The_Stack : in Stack.Value) return Stack.Value;

"When you push an item onto a stack value you generate a new stack value
that is one item deeper than the old stack value, with the new item at
the top and all the old items in the same sequence but one level deeper
than they were before.  When you pop a stack, you generate a new stack
value that is one item less deep than the old stack value, without the
old top item, and with all remaining items in the same sequence but one
level shallower than before.

"Here are some possible usages of these operations:

    My_Stack, Your_Stack, His_Stack : Stack.Value;
    ...
    My_Stack := Push (My_Stack, Next_Item);
    My_Stack := Pop (My_Stack);
    
    Your_Stack := Push (Different_Top_Item, Pop (My_Stack));
    
    My_Stack  := Your_Stack;
    -- now My_Stack = Your_Stack
    
    His_Stack := Your_Stack;
    -- now His_Stack = Your_Stack, too
    -- and His_Stack = My_Stack
    
    Your_Stack := Push (Your_Stack, Another_Item);
    -- now Your_Stack /= My_Stack
    -- and Your_Stack /= His_Stack
    -- but His_Stack = My_Stack, still

"Since Stack.Value is a value type and Push and Pop are functions,
neither operation causes side-effects.  Only the assignments cause side
effects."

Somewhat an unorthodox view of stacks, I admit, and it might be hard
to implement efficiently.  However, there's nothing theoretically unsound
about this, and it would, among other things, allow arbitrary composing of
stacks-of-stacks (without aliasing).

------------------------------------------------------------------------
Internet.Usenet.Put_Signature
( Name => "John G. Volan", E_Mail => "John_Volan@dayton.saic.com",
  Favorite_Slogan => "Ada95: The *FIRST* International-Standard OOPL",
  Humorous_Disclaimer => "These opinions are undefined by SAIC, so" &
    "any use would be erroneous ... or is that a bounded error now?" );
------------------------------------------------------------------------

Re: "Object" types vs. "Value" types

[david scott gibson]

In article <4j4p79$ls1@dayuc.dayton.saic.com>,
John G. Volan  <John_Volan@ccmail.dayton.saic.com> wrote:

>On the contrary, copying of state does not necessarily imply _creating_
>a new object.  The target object might already exist, and have existed
>for a long time.  Maybe you're confusiong "copying" with "cloning".
> ...
>I don't see how any "objects" are either created or destroyed by
>scalar assignment.  A variable that once held one value winds up
>holding another value.  

Of course, no scalar constructors or destructors get called.  It's
just that I'd like to think about all variables in a uniform manner.
For more complex structures, it seems natural to think of variables as
handles for objects.  I believe it would be useful to think of all
variables in this same way.  With this way of thinking, an Integer
variable identifies an Integer object with some state, an integer
value.  (Ada's undefined initial representations for scalar types have
caused serious problems for me here.)  The notion of assignment from
one variable to another doesn't seem to fit well in this model, but
that's where I was coming from.  I think it is confusing to use := for
two conceptually different operations - value assignment as with
scalars, and copying (with object creation and destruction) for more
complex objects when augmented with Adjust.  Your point that limited
types are most appropriate for objects is right on target.

>Could you elaborate on why you think aliasing makes reasoning about
>a program harder?

Well, of course, the side effects that can result from aliasing make
code more difficult to understand and reason about than code without
aliasing.  From a formal reasoning point of view, verification is much
simpler when proof rules can include the implicit assumption that the
states of all objects not explicitly mentioned in a statement do not
change.  I believe that trying to formally specify program behavior in
the presence of aliasing is very difficult.  In order to reason about
systems which use components that allow aliasing (e.g., a polylithic
list), it may be necessary to consider complex interactions between
many components.  For arbitrarily large and complex systems, I believe
that this thwarts the possibility of rigorous reasoning about the
behavior of the system as a whole.  The key problem here is allowing
the ill effects of pointers to cross module abstraction boundaries.

>objects could swap locations.  Similarly, when an object is moved from
>one location into an already-vacant location, leaving behind it a newly
>vacant location, I suppose you could look at that as swapping an object
>and a vacuum.

In RESOLVE however, all objects are initialized to the specified
initial value of their type, thus there are no variables which
represent "vacant locations".  Swapping of two objects always results
in exchanging two objects whose states correspond to two (well
defined) abstract values.

>This sounds a lot like some of Henry Baker's work.

Perhaps the conservation of objects aspect, but RESOLVE is not a
functional language which seems to be the primary focus of Baker's
work as I understand it.

>Perhaps we're using different definitions of the word "abstraction".
>In software terms, I tend to use Booch's definition:

Yes, I think that's the case.  I certainly see how an Ada Integer
satisfies a reasonable definition of an abstraction.  I'm just pushing
the term a little farther beyond the implementation language level.

>I have often thought that much of the trickyness of pointers (e.g.,
>dangling references, garbage generation, etc.) could be avoided if
>pointers were replaced with a more sophisticated abstraction that was
>bi-directional.  In other words, any time some object A referenced
>some other object B, not only would A "know" about the reference,
>but B would know about it as well, and would effectively be 
>referencing A in turn.  Disconnecting the reference from A to B
>would also mean disconnecting the reference from B to A.  Destroying
>an object would automatically entail disconnecting it from every
>other associated object, thereby guaranteeing that no dangling
>references would be left behind -- essentially, all associated
>objects would be notified of its demise.
>
>I can see how this might make it easier to reason about program
>correctness than raw pointers.  (Is that the sort of thing your
>"Chain_Position" component accomplishes?  The name is compelling.) 
>Note, however, that this does not eliminate "aliasing" in any way, it
>just makes it safer.

RESOLVE components Chain_Position, Directed_Acyclic_Graph, and
Permutation (for cyclic structures) provide limited and safe aliasing.
My earlier implication that aliasing was completely prohibited in
RESOLVE was misleading.  These components do not really hide aliasing
from the client, they just ensure any aliasing can only have local
effects.  As a result, most of the problems that can result from
aliasing can be avoided.  For each instance of Chain_Position,
component (package) level state is maintained and shared by all
variables of the exported Position type.  Chain_Position's interface
is such that operations on Position variables (which simulate
pointers) cannot have any effect on similar operations in another
module even when a single instance of Chain_Position is involved.  (If
a Position value is explicitly passed to another module, then its
effects will be specified by the module interfaces.)  Proof rules for
Chain_Position operations are not going to be trivial, but should be
manageable due to the localization of effects.  A good description of
this component is in the Proceedings of the 10th Annual National
Conference on Ada Technology (1992, pp.  82-97).  Note that in this
paper and in the current RESOLVE/Ada83 catalog, Chain_Position and
Directed_Acyclic_Graph are called One_Way_Nilpotent and
N_Way_Nilpotent respectively.

>In the meantime,
>could you post a summary of the ideas behind this "RESOLVE" language?

The fundamental principle of RESOLVE, is that of modular reasoning.
With a RESOLVE component, it is possible to reason about the
correctness of an implementation by only examining the component's
specification, its implementation, and the specification of any
components used by the implementation.  To support generality for
reuse, RESOLVE components are highly parameterized (making heavy use
of generics in RESOLVE/Ada).  To support efficiency at the algorithmic
level, RESOLVE uses swapping instead of copying for most data
movement.  The pervasive use of swapping has a profound influence on
how components are typically designed and implemented.  To support
understandability as well as verifiability, RESOLVE integrates a
model-based specification sub-language and an implementation
sub-language into a single unified language.  Following the RESOLVE
discipline results in components which are readily composed with each
other with little of the "glue" required by many other disciplines.
Weakness of RESOLVE include the fact that it currently does not
address concurrency and it has not been demonstrated on many large
applications.  Also, the RESOLVE language does not have a compiler,
and hence one of the motivations for RESOLVE/Ada and RESOLVE/C++
disciplines.  

The most recent published description of RESOLVE is:

Murali Sitaraman and Bruce W. Weide, editors.  Special Feature: 
Component-Based Software Using RESOLVE, ACM SIGSOFT Software
Engineering Notes, 19(4):21-67, October 1994. 

A good paper discussing swapping is:

Douglas E. Harms and Bruce W. Weide.  Copying and Swapping:
Influences on the Design of Reusable Software Components,
IEEE Transactions on Software Engineering, 17(5): 424-435, May 1991.

More RESOLVE references can be found at:

http://www.cis.ohio-state.edu/hypertext/rsrg/RSRG.html

>Not _me_, other folks are trying to. :-)  Anyway, I was allowing for the
>possibility of someone arguing thus:
>
>"A stack is a kind of value with operations such as:

This doesn't sound quite right -- a "value" with operations.  I think
of behavior as part of the OO notion of object, but not of value.

>    function Push (The_Stack : in Stack.Value; New_Item : in Item)
>        return Stack.Value;
>        
>    function Pop (The_Stack : in Stack.Value) return Stack.Value;
>
>"When you push an item onto a stack value you generate a new stack value
>that is one item deeper than the old stack value, with the new item at
>the top and all the old items in the same sequence but one level deeper
>than they were before.  When you pop a stack, you generate a new stack
>value that is one item less deep than the old stack value, without the
>old top item, and with all remaining items in the same sequence but one
>level shallower than before.
> ...
>Somewhat an unorthodox view of stacks, I admit, and it might be hard
>to implement efficiently.  However, there's nothing theoretically unsound
>about this, and it would, among other things, allow arbitrary composing of
>stacks-of-stacks (without aliasing).

Actually, this looks very familiar.  I implemented some ADT's in ML
not long ago and due to the functional nature of ML they basically
looked like those in your example.  There were some serious questions
about the possibility of efficient implementations as you suggest.  I
suppose in the functional world, it is reasonable to consider anything
as a value.  I see your point, but I'd be surprised to hear of a good
reason to build software like this in Ada.  Thanks for your insights.

Dave
--
dgibson@cis.ohio-state.edu

Re: Comments on generic stack?

[David Wheeler]

Jean-Pierre Rosen (rosen@EMAIL.ENST.FR) wrote:
: At 14:11 13/03/1996 GMT, you wrote:
: >
: >  with Ada.Finalization; use Ada.Finalization;
: >
: >  generic
: >    type Item is private;
: >
: >  package Generic_Stack is
: >    type Stack is new Controlled with private; -- permit assignment.
: Why do you need to make it visibly derived from controlled ? Seems to me that
:      type  Stack is private;
: would be OK (even if completed as derived from Controlled).

Agreed, but by making it visibly derived you can derive controlled children
of the type. E.G.: Stacks that when created do something special.
It's a minor functionality; I think either way would be "right".

--- David