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

[John G. Volan <John_Volan@ccmail.dayton.saic.com>]

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?" );
------------------------------------------------------------------------