* Re: Comments on generic stack? [not found] <4i6l2t$j1q@dmsoproto.ida.org> @ 1996-03-15 0:00 ` Michel Gauthier 1996-03-17 0:00 ` David Wheeler 1996-03-20 0:00 ` "Object" types vs. "Value" types John G. Volan 0 siblings, 2 replies; 9+ messages in thread From: Michel Gauthier @ 1996-03-15 0:00 UTC (permalink / raw) 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 ---------- ---------- ---------- ---------- ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Comments on generic stack? 1996-03-15 0:00 ` Comments on generic stack? Michel Gauthier @ 1996-03-17 0:00 ` David Wheeler 1996-03-20 0:00 ` "Object" types vs. "Value" types John G. Volan 1 sibling, 0 replies; 9+ messages in thread From: David Wheeler @ 1996-03-17 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* "Object" types vs. "Value" types 1996-03-15 0:00 ` Comments on generic stack? Michel Gauthier 1996-03-17 0:00 ` David Wheeler @ 1996-03-20 0:00 ` John G. Volan 1996-03-20 0:00 ` John DiCamillo 1996-03-21 0:00 ` "Object" types vs. "Value" types david scott gibson 1 sibling, 2 replies; 9+ messages in thread From: John G. Volan @ 1996-03-20 0:00 UTC (permalink / raw) 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?" ); ------------------------------------------------------------------------ ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: "Object" types vs. "Value" types 1996-03-20 0:00 ` "Object" types vs. "Value" types John G. Volan @ 1996-03-20 0:00 ` John DiCamillo 1996-03-21 0:00 ` Comments on generic stack? John G. Volan 1996-03-21 0:00 ` "Object" types vs. "Value" types david scott gibson 1 sibling, 1 reply; 9+ messages in thread From: John DiCamillo @ 1996-03-20 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Comments on generic stack? 1996-03-20 0:00 ` John DiCamillo @ 1996-03-21 0:00 ` John G. Volan 0 siblings, 0 replies; 9+ messages in thread From: John G. Volan @ 1996-03-21 0:00 UTC (permalink / raw) 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?" ); ------------------------------------------------------------------------ ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: "Object" types vs. "Value" types 1996-03-20 0:00 ` "Object" types vs. "Value" types John G. Volan 1996-03-20 0:00 ` John DiCamillo @ 1996-03-21 0:00 ` david scott gibson 1996-03-25 0:00 ` John G. Volan 1 sibling, 1 reply; 9+ messages in thread From: david scott gibson @ 1996-03-21 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: "Object" types vs. "Value" types 1996-03-21 0:00 ` "Object" types vs. "Value" types david scott gibson @ 1996-03-25 0:00 ` John G. Volan 1996-03-28 0:00 ` david scott gibson 0 siblings, 1 reply; 9+ messages in thread From: John G. Volan @ 1996-03-25 0:00 UTC (permalink / raw) 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?" ); ------------------------------------------------------------------------ ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: "Object" types vs. "Value" types 1996-03-25 0:00 ` John G. Volan @ 1996-03-28 0:00 ` david scott gibson 0 siblings, 0 replies; 9+ messages in thread From: david scott gibson @ 1996-03-28 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
[parent not found: <199603141053.LAA21095@email.enst.fr>]
* Re: Comments on generic stack? [not found] <199603141053.LAA21095@email.enst.fr> @ 1996-03-17 0:00 ` David Wheeler 0 siblings, 0 replies; 9+ messages in thread From: David Wheeler @ 1996-03-17 0:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~1996-03-28 0:00 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <4i6l2t$j1q@dmsoproto.ida.org> 1996-03-15 0:00 ` Comments on generic stack? Michel Gauthier 1996-03-17 0:00 ` David Wheeler 1996-03-20 0:00 ` "Object" types vs. "Value" types John G. Volan 1996-03-20 0:00 ` John DiCamillo 1996-03-21 0:00 ` Comments on generic stack? John G. Volan 1996-03-21 0:00 ` "Object" types vs. "Value" types david scott gibson 1996-03-25 0:00 ` John G. Volan 1996-03-28 0:00 ` david scott gibson [not found] <199603141053.LAA21095@email.enst.fr> 1996-03-17 0:00 ` Comments on generic stack? David Wheeler
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox