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

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

"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

[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

[Jean-Pierre Rosen]

At 01:31 20/03/1996 GMT, you 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.
>
> [lots of valuable stuff deleted]

This subject was raised at one of the  Ada-France meetings, when  Michel
Gauthier came and said "Hey guys, I don't know what an assignment statement
does". We told him "sit down, we'll explain to you". Two hours of discussion
later, nobody knew anymore how to define the semantics of assignment...

However, we came to the conclusion that there were two cases where the
semantics of assignment could be defined, and this is very close to what you
said.

Given a (private) type, and two variables X and Y, we say that the type has:

1) "Value semantics" if Y:=X means that the contents of X is copied into Y.
2) "Reference semantics" if Y:=X means that from now on, X and Y designate
the same object.

1) is for "usual" values, 2) is for pointers of course, but also any other
kind of reference (like the (private) type being actually a string used as
an entry in a symbol table).

Note that there is no syntactic way (without looking at the private part) to
tell which semantic a private type has : it has to be commented.

An important consequence of this finding is that you should never mix in a
record fields with "value" semantics and fields with "reference" semantics;
if you do, it is impossible to give a simple semantics to assignment for
objects of this record type.

The issue of limited types is a bit different. Limited types (and controlled
types) are useful when the predefined assignment would have the wrong semantic.

This issue is discussed at length in my book, and in several of Michel
Gauthier's publications (I don't have the reference at hand, but he will
tell you if you want).
+------------------------------------o-------------------------------------+
| P-mail:                            | E-mail: rosen@enst.fr               |
|   ADALOG - 27 avenue de Verdun     |    Tel: +33 1 46 45 51 12           |
|   92170 Vanves - FRANCE            |    Fax: +33 1 46 45 52 49           |
+------------------------------------o-------------------------------------+

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

[Robert Dewar]

"1) "Value semantics" if Y:=X means that the contents of X is copied into Y.
2) "Reference semantics" if Y:=X means that from now on, X and Y designate
the same object."

I think this can be a bit confusing, because it describes what are high
level notions in terms of one particular implementation approach.

Now of course, "as if" applies, so what is meant for example is that
"Value Semantics" if Y := X means that it is AS IF the contents of X
 is copied into Y.

Why is the distinction important. Well a standard, and often efficient
way of achieving value semantics is to copy on modification, rather
than copy on assignment. 

In this model the value is represented by a pointer and indeed the
assignment copies the pointer so that the original and the assigned
object both "reference the same object" at the implementation level.

However, if either is modified, it is copied before modification, so
that there is no sharing from a logical point of view.

It is the visible sharing that is the issue here, i.e. after the assignment
A := B, can a subsequent modification to any aspect of A affect any aspect
of B and vice versa. If the answer is NO, then we have value semantics,
if YES, then we have reference semantics.

The distinction is indeed critical, but no wonder you got confused talking
about assignment if you immediately started talking about low level
implementation details (use of pointers, and copying of values on
assignment). You need to describe the difference at an operational
semantic level, as I have done here, rather than at an implementation
level.

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

[Jean-Pierre Rosen]

At 07:24 25/03/1996 -0500, you wrote:
>"1) "Value semantics" if Y:=X means that the contents of X is copied into Y.
>2) "Reference semantics" if Y:=X means that from now on, X and Y designate
>the same object."
>
>I think this can be a bit confusing, because it describes what are high
>level notions in terms of one particular implementation approach.
>
>Now of course, "as if" applies, so what is meant for example is that
>"Value Semantics" if Y := X means that it is AS IF the contents of X
> is copied into Y.
>
>[...] explanation of lazy assignment deleted
>
>The distinction is indeed critical, but no wonder you got confused talking
>about assignment if you immediately started talking about low level
>implementation details (use of pointers, and copying of values on
>assignment). You need to describe the difference at an operational
>semantic level, as I have done here, rather than at an implementation
>level.
>

Yes, of course, I was talking about abstract behaviour. Note that I
described it in terms  of *private* types (which is actually totally
irrelevant to the discussion), just to mean that I intended to described a
perceivable behaviour, not an implementation issue. That's also why I tried
to give an example of non-pointer reference semantics.

So the real issue is the abstract meaning of assignment. Note for example
that you can consider pointers as a "value" type (the value being the
designation of an object), or directly as a  "reference" type. Grossly, this
would be the  former case for a visible pointer type, and the latter for a
private pointer type.
+------------------------------------o-------------------------------------+
| P-mail:                            | E-mail: rosen@enst.fr               |
|   ADALOG - 27 avenue de Verdun     |    Tel: +33 1 46 45 51 12           |
|   92170 Vanves - FRANCE            |    Fax: +33 1 46 45 52 49           |
+------------------------------------o-------------------------------------+

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

[Michel Gauthier]

In article <199603250902.KAA21800@email.enst.fr>, Jean-Pierre Rosen
<rosen@EMAIL.ENST.FR> wrote:

>>  This issue is discussed at length in my book, and in several of Michel
>>  Gauthier's publications (I don't have the reference at hand, but he will
>>  tell you if you want).

The initial publication about objects versus values is by Bruce MacLennan
in a Sigplan paper in 1982 (and a 1981 printed school course).

Later, and without knowledge of this paper, I have studied the issue, and
hesitated for a long time to publish such heretic ideas. The first papers were
published during my sabbatical half-year in Lausanne. You can refer
to a paper at Ada-UK 1993, but the major contribution remains in
French only (Michael Feldman, Ed Schonberg and Dan Roy have a copy,
if you work in the same universities).
    I can make a PostScript copy ftp-available if requested.

Essential idea : equality has no meaning. Only non-distinguishability has.
Therefore, anything kept in a data structure (variable, file, stack,...) and 
later retrieved must have this non-distinguishability property. Moreover,
this property must be a precondition of any such generic construct,
independently of the language kind of the type.
   Note : this is mathematically the only possible definition of equality.

Identities do not have the non-distinguishability property. They are better
defined as purely abstract entities, that require conversion functions to
and from some suitable value type. These conversion functions can be
straightforward for some cases and very complex for others.

Some programming consequences of the distinction :
 - lists organize objects only, and I am not sure that they are objects
    (they are not values)
 - stacks and queues organize values only, and are objects
 - implementing stacks with lists implies some (generally hidden)
    handling of objects designed to keep values
 - lists of values are sequences rather than really lists

I guess a paper in Ada Letters could be a good idea.
Phil, are you interested ?

I am convinced that the distinction between objects and values is essential for
the future of programming. I try to convince other people.

----------          ----------          ----------          ---------- 
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: "Object" types vs. "Value" types

[Richard A. O'Keefe]

gauthier@unilim.fr (Michel Gauthier) writes:
>The initial publication about objects versus values is by Bruce MacLennan
>in a Sigplan paper in 1982 (and a 1981 printed school course).

Surely the _initial_ publication of the idea goes back at least as far
as Simula 67, which used ":=" for value assignment and ":-" for object
reference assignment, precisely because they were understood as distinct.

>Some programming consequences of the distinction :
> - lists organize objects only, and I am not sure that they are objects
>    (they are not values)

This is news to the functional programming community, who think that
the sequence [1,2,3,4] is every bit as much a value as the sequence 1234.
In functional languages, [1,2,3,4] = [1,2,3,4].

> - stacks and queues organize values only, and are objects

(a) Why can't a stack or queue hold an object?  (Consider the case where
    this is the _only_ occurrence of the object.)
(b) I have used stacks and queues in programming languages with no notion
    of assignment, no notion of object identity, and where two stacks
    holding the same sequence of values necessarily satisfied the built
    in equality.

> - implementing stacks with lists implies some (generally hidden)
>    handling of objects designed to keep values
> - lists of values are sequences rather than really lists

We can all play definitional games if we want to.  Haskell programmers
think the things they are dealing with "are ... really lists" despite
the fact that they behave like mathematical values.  I heartily agree
with the to-me-familiar distinction between objects and values, but to
me it is mutable lists which feel as if they are "not really lists".  
But this is to argue about *words* rather than *realities*.

There is already a 'mutable'/'immutable' distinction around; how exactly
does that relate to the 'object'/'value' distinction?

>I am convinced that the distinction between objects and values is essential for
>the future of programming. I try to convince other people.
-- 
The election is over, and Australia lost; the idjits elected _politicians_!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

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

[Michel Gauthier]

In article <4jahd9$906@goanna.cs.rmit.EDU.AU>, ok@goanna.cs.rmit.EDU.AU
(Richard A. O'Keefe) wrote:

>>  gauthier@unilim.fr (Michel Gauthier) writes:
>>  >The initial publication about objects versus values is   [...]
>>  Surely the _initial_ publication of the idea goes back at least as far
>>  as Simula 67, which used ":=" for value assignment and ":-" for object
>>  reference assignment, precisely because they were understood as distinct.

Not quite that sure. You speak of a low-level language view, which cannot
imply anything at conceptual level view. MacLennan's paper is at this level.
Simula was a great pioneer language, which surely led to interesting concepts,
but most of them were discovered later. I leave to historians the work of
studying whether the object/value distinction was already in Simula, but
the example is too weak to conclude so.

>>  >  - lists organize objects only, and I am not sure that they are objects
>>  >     (they are not values)
>>  This is news to the functional programming community, who think that
>>  the sequence [1,2,3,4] is every bit as much a value as the sequence 1234.
>>  In functional languages, [1,2,3,4] = [1,2,3,4].

What happens if you try to insert something in this ? Either you have some
order property (which implies the location of your inserted item) or you must
indicate this location. These two behaviors should better correspond to 
different names (also see later). One is a value, the other is not.

As long as you cannot update things, _different_ things like cons(a,b) and
cons(a,b) are _non_distinguishable_. This is why pure functional languages
do not reach the problem.

I continue to assert that _non_distinguishability_ is essential if we want to
understand assignment.
 
>>  > - stacks and queues organize values only, and are objects
>>  (a) Why can't a stack or queue hold an object?  (Consider the case where
>>      this is the _only_ occurrence of the object.)

How can you define the relationship between the entered object, the kept object 
and the retrieved object ? How can you guarantee them to be the same ?

>>  (b) I have used stacks and queues in programming languages with no notion
>>      of assignment, no notion of object identity, and where two stacks
>>      holding the same sequence of values necessarily satisfied the
built in equality.

Yes, _built_in_ equality, but what is its meaning between objects ?
It can at most be the equality of their states, which are essentially values.
This leads us back to entered/kept/retrieved objectS.

>>     [...]
>>  We can all play definitional games if we want to.   [...]
>>  But this is to argue about *words* rather than *realities*.

Agreed with. I Apologize. There are some different kinds of lists :
 - sequences (most of public list packages)
 - structures built by a pointer head and a pointer record field
 - structures added to existing object classes such as to organize them
    as multiple easy_to_scan subsets
 - and probably others that I am not currently remembering
Use whatever name you wish, as soon as the different kinds are not confused.

Note that there can be 'value' sequences and objects to keep them (exactly 
like value arrays/records and object arrays/records).

>>  There is already a 'mutable'/'immutable' distinction around; how exactly
>>  does that relate to the 'object'/'value' distinction?

The 'mutable'/'immutable' distinction is part of the 'object'/'value'
distinction, but
there are many others.

----------          ----------          ----------          ---------- 
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: "Object" types vs. "Value" types

[Robert Dewar]

">The initial publication about objects versus values is by Bruce MacLennan
>in a Sigplan paper in 1982 (and a 1981 printed school course).

Surely the _initial_ publication of the idea goes back at least as far
as Simula 67, which used ":=" for value assignment and ":-" for object
reference assignment, precisely because they were understood as distinct."

This is much older. The distinction between these notions is clearly
apparent in LISP 1.5, whre incidentally, for the most part, lists
have value semantics -- the idea that lists are necessarily objects
must have been invented later with the advent of lower level languages :-)

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