jcm@mstr.hgc.edu (James McKim) (05/30/91)
Sorry if the headers you receive look strange. At the moment the only way I can post news is by follow-ups, and in this case I'm trying to follow up an expired article! In an earlier post Craig Chambers writes >2. Do you actually believe that functions should be side-effect-free? Yup. At least as far as the abstract state of the class is concerned. This is really just an application of separation of concerns. Procedures change the state, functions query the state. >My view is that side-effecting procedures (even of the abstract state) >that return a result are too useful to forgo. For example, when I >call Stack.Pop I want to get back the element popped off the stack; I >don't want to have to call Stack.Top, save the result somewhere, and >then call Stack.Pop to remove it from the stack. Well, perhaps a couple of examples might convince you that it's at least as useful to separate Pop and Top as to combine them. Suppose I have stack.pop which removes the top item and stack.top which returns the top item. Meanwhile you have stack.pop_top which does both. Now suppose I want to print the top item on the stack if it's bigger than 10. I write if stack.top > 10 then print stack.top end You write temp := stack.pop_top if temp > 10 then print temp else stack.push( temp ) end That's assuming you don't fall into the following trap if stack.pop_top > 10 then print stack.pop_top end Now suppose I want to empty the stack. The body of my loop consists of stack.pop The body of yours will be temp := stack.pop_top unless of course you're working in C or some other assembly language.:-) The point is pop and top are independently useful and so deserve to be separated. And this independent usefulness comes about precisely because one changes the state and the other merely queries. > Also, I believe that >somewhere in OOSC (I can't find it now) is described a technique >whereby instead of writing a side-effecting function (a procedure that >returns a result) the programmer writes a procedure that stores its >result in some instance variable which can then be accessed by a >corresponding function. This approach seems silly; it's more verbose >for the programmer (both the class implementor and the client) and >less efficient since I assume an extra word of storage needs to be >allocated in every such object. I think you're probably thinking of the matrix equation example on pp. 201-2. The technique you described is used to prevent the need for executing essentially the same complicated algorithm twice. The tradeoff is substantial runtime savings for one word of storage. Anyway, that's the point of view of at least one of the 'Eiffel converted'. What do you think? -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 | _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu | _Teach_ people to fish and they eat for a lifetime.
craig@leland.Stanford.EDU (Craig Chambers) (05/31/91)
In article <1991May30.141218.3446@mstr.hgc.edu>, jcm@mstr.hgc.edu (James McKim) writes: |> The point is pop and top are independently useful and so deserve to be separated. I agree; I never meant to suggest that Top shouldn't exist. |> And this independent usefulness comes about precisely because one changes |> the state and the other merely queries. No, my Stack class would have a Top method that returned the top of the stack and a Pop method that both removed the top element from the stack *and returned this element to me*. Since I don't follow any dogma stating that procedures should not return values, I make my procedures be as helpful as possible, in this case by also returning what the top of the stack was. -- Craig Chambers
jcm@mstr.hgc.edu (James McKim) (05/31/91)
In article <1991May30.195249.16103@leland.Stanford.EDU> craig@self.stanford.edu writes: >In article <1991May30.141218.3446@mstr.hgc.edu>, jcm@mstr.hgc.edu (James McKim) writes: >|> The point is pop and top are independently useful and so deserve to be separated. > >I agree; I never meant to suggest that Top shouldn't exist. > >|> And this independent usefulness comes about precisely because one changes >|> the state and the other merely queries. > >No, my Stack class would have a Top method that returned the top of >the stack and a Pop method that both removed the top element from the >stack *and returned this element to me*. Since I don't follow any >dogma stating that procedures should not return values, I make my >procedures be as helpful as possible, in this case by also returning >what the top of the stack was. > >-- Craig Chambers Well, I'm not sure how to define "helpful". As a user of a class I find it helpful to be able to assume functions have no side effects. I don't find it helpful to be in a situation where features A and B return the same value but B has a side effect (or is it A?). As the implementer/maintainer/designer of a class I find it helpful to be able to separate the concerns of changing state and reading state. A feature that does both just has to be more complex than a feature that does just one. (At least I can't think of a counterexample) On the other hand, if there's a really compelling reason, such as efficiency, I'll bite the bullet and design a procedure that returns a value. (Funny, the phrase 'procedure that returns a value' sounds so much better than 'function with side effects' :-)) So you lean toward adding return values to procedures whenever you think it makes sense and I lean, heavily, toward functions with no side effects. -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 | _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu | _Teach_ people to fish and they eat for a lifetime.
roy@alfrat.uucp (Roy Phillips) (06/01/91)
I've followed with interest the discussion on functions and side-effects,
and one point that has'nt been mentioned (or that I've overlooked) is
the aspect of readability of the application (assuming we wish to build
an application sometime, and not just create examples for academic reasons).
An importent criteria for me is that code be readable - that it represents
the solution to the problem or the model of a system with very little
`superfluous' text. This criteria is, for me, one of the most importent when
designing a class or class cluster, and a major reason for using Eiffel over
other languages. I refuse to pay homage to the mathematical god of
`correctness' by sacrificing the understandability of the application - as in
all things, rules are not the answer, but judgement should be used. Although
agreeing in general to the principle of seperation of state-changing and
state-querying features, I offer the two examples below in support of my
argument that this should not of necessity be the rule.
If one were to model a CPU, perhaps to create a simulator such as ITSIAC, it
would be essential, from the point of view of understandability of the model,
that the POP operation act just like the processor's POP - changing the state
of the processor and returning the value from the stack top into the specified
register.
Having to perform two operations would be a unnecessary complication which
could lead to misunderstanding and to errors.
As a second case for functions with side effects, consider the interface of
a mutual exclusion class, loosely based upon Djistra's P&V algorithm:
--
-- MONITOR -- Resource Allocation Monitor providing mutual
-- exclusion facilities
--
-- %Z%%Y%:%M% %I%
indexing
date: "$Date: %D% %T% $";
revision: "$Revision: %R%.%L% $";
authors: roy;
names: monitor;
access: exclusive;
deferred class MONITOR export
free,
test_and_set,
request,
release,
got_resource
feature
free: BOOLEAN is
-- is the resource we are managing available?
deferred
end; -- free
test_and_set: BOOLEAN is
-- is the resource we are managing available to us?
deferred
ensure
Result = True implies got_resource;
Result = False implies not free and not got_resource
end; -- test_and_set
request: BOOLEAN is
-- return True when we have control of the resource
require
-- not free implies "wait until resource free"
deferred
ensure
got_resource
end; -- request
release is
-- make resource available again
require
free = False and then got_resource
deferred
ensure
not got_resource
end; -- release
got_resource: BOOLEAN
-- return True if we have successfully obtained
-- exclusive accesss to resource
deferred
ensure
Result = True implies not free
end; -- got_resource
end -- class MONITOR
Seperate `request' and `release' operations are an obvious
requirement (implemented as a function and a procedure respectively)
but it is essential to provide a `test_and_set' routine, that returns
a boolean `success/fail' status and grabs the resource if it is free
- hysteresis between calling `free' and `request' could cause the application
to perform an undesired wait inside of `request'. Care should be taken
to provide comments, or better still, assertions that clearly outline
any state changes that a routine may perform, be it a function or a
procedure. Observing pre- and post-conditions is a lot more helpful than
to rely on the rule:
"it's a function so it won't change the object's state"
Roy
--
Roy Phillips
A+F SystemEntwicklung
D-4030 Ratingen
West(ern) Germany
roy@alfrat.UUCPjcm@mstr.hgc.edu (James McKim) (06/03/91)
I've broadened the Newsgroups line, because while this thread began with an Eiffel specific question, it has broadened into a topic of more general interest. I have a hunch people will let me know if they feel this is not appropriate. :-) Let me try to summarize the discussion so far. The question before the groups is "Should there exist a dichotomy between functions and procedures within a class? In particular, should functions return information about the state of an object _without_ changing that state (at least as far as a user of the object can tell) while procedures are used to change the state of the object _without_ returning a value. So far the two most extreme views are held by Craig Chambers and myself. Craig feels that procedures that return values are often extremely useful and so should be designed into the class as a matter of course. He cites Pop and Top in a stack class as a prime example. Top returns the obvious item from the stack with no side effects. Pop removes the top item _and_ returns it. His argument being, I believe, that the vast majority of the time the user will want to use the item she just popped. (Is that a fair summary Craig?) I feel that the separation of concerns that the proposed dichotomization between functions and procedures is too important to give up lightly. The designer of a class should expect to design procedures that don't return values and functions without side effects, and only vary from this heuristic when there is a _compelling_ reason to do so. Thus my Pop would just remove the top element, not return it. Now here's the latest salvo, which is a more middle of the road point of view. In article <327@alfrat.uucp> roy@alfrat.UUCP (Roy Phillips) writes: >An importent criteria for me is that code be readable - that it represents >the solution to the problem or the model of a system with very little >`superfluous' text. This criteria is, for me, one of the most importent when >designing a class or class cluster, and a major reason for using Eiffel over >other languages. I refuse to pay homage to the mathematical god of >`correctness' by sacrificing the understandability of the application - as in >all things, rules are not the answer, but judgement should be used. Although >agreeing in general to the principle of seperation of state-changing and >state-querying features, I offer the two examples below in support of my >argument that this should not of necessity be the rule. Well, I'm not sure how much we disagree. I'm not arguing for an iron-clad rule, either. > If one were to model a CPU, perhaps to create a simulator such as ITSIAC, it > would be essential, from the point of view of understandability of the model, > that the POP operation act just like the processor's POP - changing the state > of the processor and returning the value from the stack top into the specified > register. > Having to perform two operations would be a unnecessary complication which > could lead to misunderstanding and to errors. So for you this is a compelling reason to combine the two concerns in this particular application. > As a second case for functions with side effects, consider the interface of > a mutual exclusion class, loosely based upon Djistra's P&V algorithm: Well, Dijkstra's P operation has been criticized precisely because it combines the two concerns we're discussing. I'll provide a reference or two if there's interest. > > -- > -- MONITOR -- Resource Allocation Monitor providing mutual > -- exclusion facilities > -- > -- %Z%%Y%:%M% %I% > > indexing > > date: "$Date: %D% %T% $"; > revision: "$Revision: %R%.%L% $"; > > authors: roy; > names: monitor; > access: exclusive; > > deferred class MONITOR export > > free, > test_and_set, > request, > release, > got_resource > > feature > > free: BOOLEAN is > -- is the resource we are managing available? > deferred > end; -- free > > test_and_set: BOOLEAN is > -- is the resource we are managing available to us? > deferred > ensure > Result = True implies got_resource; > Result = False implies not free and not got_resource > end; -- test_and_set Why not ensure old free = got_resource ; got_resource implies not free; This allows test_and_set to be a pure procedure. It's every bit as atomic as it was before since you were setting got_resource anyway. Do you really feel that the extra return value makes your code more readable? Or am I missing something basic? > > request: BOOLEAN is > -- return True when we have control of the resource > require > -- not free implies "wait until resource free" > deferred > ensure > got_resource > end; -- request Lost you here. Does this feature ever return False? If so, when? If not what good is the return value? Also ensure not free? > > release is > -- make resource available again > require > free = False and then got_resource > deferred > ensure > not got_resource > end; -- release Also ensure free? Otherwise when is free ever True? > > got_resource: BOOLEAN > -- return True if we have successfully obtained > -- exclusive accesss to resource > deferred > ensure > Result = True implies not free > end; -- got_resource This ensure clause seems unnecessary and out of place. Surely I don't have to call got_resource in order to get free set to False! > > end -- class MONITOR > > Seperate `request' and `release' operations are an obvious > requirement (implemented as a function and a procedure respectively) > but it is essential to provide a `test_and_set' routine, that returns > a boolean `success/fail' status and grabs the resource if it is free > - hysteresis between calling `free' and `request' could cause the application > to perform an undesired wait inside of `request'. Well I don't see how but it's been a long time since I worked with monitors. > Care should be taken > to provide comments, or better still, assertions that clearly outline > any state changes that a routine may perform, be it a function or a > procedure. Certainly if a function has a side effect it should be included in the postconditions. > Observing pre- and post-conditions is a lot more helpful than > to rely on the rule: > > "it's a function so it won't change the object's state" My argument is that most classes will be more readable, simpler, and better specified if _heuristics_ such as "functions should not have side-effects unless there's a compelling reason" are followed. > >Roy >-- >Roy Phillips >A+F SystemEntwicklung >D-4030 Ratingen >West(ern) Germany >roy@alfrat.UUCP This is fun! -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
chrisv@runx.oz.au (Chris Velevitch) (06/04/91)
In article <327@alfrat.uucp> roy@alfrat.UUCP (Roy Phillips) writes: > As a second case for functions with side effects, consider the interface of > a mutual exclusion class, loosely based upon Djistra's P&V algorithm: > > -- > -- MONITOR -- Resource Allocation Monitor providing mutual > -- exclusion facilities > -- > -- %Z%%Y%:%M% %I% > > indexing > > date: "$Date: %D% %T% $"; > revision: "$Revision: %R%.%L% $"; > > authors: roy; > names: monitor; > access: exclusive; > > deferred class MONITOR export > > free, > test_and_set, > request, > release, > got_resource > > feature > > free: BOOLEAN is > -- is the resource we are managing available? > deferred > end; -- free > > test_and_set: BOOLEAN is > -- is the resource we are managing available to us? > deferred > ensure > Result = True implies got_resource; > Result = False implies not free and not got_resource > end; -- test_and_set > > request: BOOLEAN is > -- return True when we have control of the resource > require > -- not free implies "wait until resource free" > deferred > ensure > got_resource > end; -- request > > release is > -- make resource available again > require > free = False and then got_resource > deferred > ensure > not got_resource > end; -- release > > got_resource: BOOLEAN > -- return True if we have successfully obtained > -- exclusive accesss to resource > deferred > ensure > Result = True implies not free > end; -- got_resource > > end -- class MONITOR > > Seperate `request' and `release' operations are an obvious > requirement (implemented as a function and a procedure respectively) > but it is essential to provide a `test_and_set' routine, that returns > a boolean `success/fail' status and grabs the resource if it is free > - hysteresis between calling `free' and `request' could cause the application > to perform an undesired wait inside of `request'. Testing the result of 'test_and_set' routine is the same as testing 'got_resource'. So 'test_and_set' should be a procedure and the result available through some other feature, in this case 'got_resource'. Chris -- -- Chris Velevitch, Voice: +61 2 906 6100, Fax: +61 2 906 6069 Cee Data Systems, 22/39 Herbert St, St Leonards NSW 2065, Australia Internet: chrisv@runxtsa.runx.oz.au, UUCP: uunet!runxtsa.runx.oz.au!chrisv
mbenveni@irisa.fr (Marc Benveniste) (06/04/91)
From article <1991Jun3.145924.28406@mstr.hgc.edu>, by jcm@mstr.hgc.edu (James McKim): > Let me try to summarize the discussion so far. The question before > the groups is "Should there exist a dichotomy between functions and procedures > within a class? In particular, should functions return information > about the state of an object _without_ changing that state (at least > as far as a user of the object can tell) while procedures are used > to change the state of the object _without_ returning a value. Recalling the link between Algebraic Abstract Data Types and O.O.P, I would say that the notions of "generator" and "observer" operations should have corresponding entities in classes. Generators are used to structurally build terms and observers are used to relate them. Objects can be seen as representations of terms although the structure is coded into a state and some information is lost. We can identify methods that change the state and methods that do not. I don't think a dichotomy should exist between procedures and functions, but between state preservers and state changers. In a parallel framework, this distinction at the language level together with the interface-body separation allows a separate compilation scheme that ensures that observers don't change the "global state" (values and other objects through references; note that we don't consider acquaintances as part of the state) and legitimates the generation of code suitable for exploiting a safe parallelism within an object. The parallel class-based language ARCHE we are currently implementing adopts this view. We provide a symetric concurrent read exclusive write synchronisation policy at the object interface level. A conditional synchronisation is also provided at the interface level, but I don't show it here. The stack example looks as follows: TYPE StackT = VIEW Push : (item : INT) (); Pop : () (item : INT) OBSERVER Top : () (item : INT); Empty: () (maybe: BOOLEAN) END; CLASS ArrayStack IMPLEMENTS Lib.StackT = VAR State : SEQ OF INT := <>; TopPtr: INT := 0; PROCEDURE Push = ... END Push; PROCEDURE Pop = ... END Pop; PROCEDURE Top = ... END Top; PROCEDURE Empty = ... END Empty; END ArrayStack; --Marc Benveniste mbenveni@irisa.irisa.fr IRISA Campus de Beaulieu 35042 Rennes Cedex FRANCE
ogden@seal.cis.ohio-state.edu (William F Ogden) (06/05/91)
In article <1991Jun3.145924.28406@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: ... >Let me try to summarize the discussion so far. The question before >the groups is "Should there exist a dichotomy between functions and procedures >within a class? In particular, should functions return information >about the state of an object _without_ changing that state (at least >as far as a user of the object can tell) while procedures are used >to change the state of the object _without_ returning a value. > >So far the two most extreme views are held by Craig Chambers and myself. > >Craig feels that procedures that return values are often extremely >useful and so should be designed into the class as a matter of course. >He cites Pop and Top in a stack class as a prime example. Top returns >the obvious item from the stack with no side effects. Pop removes the >top item _and_ returns it. His argument being, I believe, that the >vast majority of the time the user will want to use the item she just >popped. (Is that a fair summary Craig?) > >I feel that the separation of concerns that the proposed dichotomization >between functions and procedures is too important to give up lightly. >The designer of a class should expect to design procedures that don't >return values and functions without side effects, and only vary from >this heuristic when there is a _compelling_ reason to do so. Thus my >Pop would just remove the top element, not return it. There are a number of considerations that bear upon this issue, but comprehensibility and efficiency are probably the most important. Functions enjoy a prominent position in twentieth century mathematics, and thus in the educational background of most software professionals. It makes sense to exploit this shared knowledge when designing software. Now the principle feature of functions is that they can be composed into arbitrarily large expressions. If you don't anticipate clients forming expressions, then functions offer no particular advantage over procedures as class operations. The answer to the question of whether functions should have side-effects which are visible at the client level is clear when you observe that side-effects will make the value of experessions dependent upon the order of evaluation of subexpressions, and hence quite unapparent. On the other hand, side-effects which only affect the internal representationsof objects (such as changing the shape of a tree being used to realize a set)should be permitted for efficiency reasons. The pop/top discussion raises an important efficiency issue in class design. While we now give lip service to object-oriented design, we often fail to recognize some of the consequences of what we're advocating. If the object based software thesis is correct, then our software will be organized around increasingly large and sophisticated objects, yet when we design things like stacks, we persist in thinking of the objects being stored in stacks as being small objects like integers. Instead, we should recognize that the really serious uses of stacks will involve storing large objects ( sets, polygons, other stacks, etc. ), and that to achieve real reusability, our stack operations should be chosen with an eye to making them efficient for storing large objects. Probably the most significant feature of large objects, as opposed to small objects like integers, is that they are usually quite expensive (if not impossible) to replicate. Consequently operations like Top make poor choices as primary operations, since their implementation inevitably involves making a copy of a data structure entry. The proper choice of primary operation for the stack then is the procedure (not function -- see above) Pop which does return the top value, since this does not entail replicating an entry. Top can be provided as a secondary operation, but clients should be warned that it is potentially an expensive operation. -- /Bill
jezequel@irisa.fr (Jean-Marc Jezequel) (06/05/91)
From article <130242@tut.cis.ohio-state.edu>, by ogden@seal.cis.ohio-state.edu (William F Ogden): > In article <1991Jun3.145924.28406@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: > ... >>Let me try to summarize the discussion so far. The question before >>the groups is "Should there exist a dichotomy between functions and procedures >>within a class? In particular, should functions return information >>about the state of an object _without_ changing that state (at least >>as far as a user of the object can tell) while procedures are used >>to change the state of the object _without_ returning a value. >> >>So far the two most extreme views are held by Craig Chambers and myself. >> >>Craig feels that procedures that return values are often extremely >>useful and so should be designed into the class as a matter of course. >>He cites Pop and Top in a stack class as a prime example. Top returns >>the obvious item from the stack with no side effects. Pop removes the >>top item _and_ returns it. His argument being, I believe, that the >>vast majority of the time the user will want to use the item she just >>popped. (Is that a fair summary Craig?) >> >>I feel that the separation of concerns that the proposed dichotomization >>between functions and procedures is too important to give up lightly. >>The designer of a class should expect to design procedures that don't >>return values and functions without side effects, and only vary from >>this heuristic when there is a _compelling_ reason to do so. Thus my >>Pop would just remove the top element, not return it. Let me summarize even further: It seems that we all agree on: 1) Functions with side effects are dangerous, and don't follow the road towards better software quality 2) Procedures which return values are often usefull So why not trying to make a syntatical difference between the two concepts (keyword like "pure" for pure functions)? I guess it is too late for Eiffel V3, but may be for V4, when we (hope to) have tools to make static analysis of programs in order to prove correctness of pieces of code (i.e. ensuring postconditions and invariants from preconditions and code), and so on. +----------------------------------------------------------------------------+ | Jean-Marc Jezequel, IRISA/CNRS, 35042 RENNES (FRANCE) // jezequel@irisa.fr | +----------------------------------------------------------------------------+ -- +----------------------------------------------------------------------------+ | Jean-Marc Jezequel, IRISA/CNRS, 35042 RENNES (FRANCE) // jezequel@irisa.fr | +----------------------------------------------------------------------------+
diamond@jit533.swstokyo.dec.com (Norman Diamond) (06/05/91)
In article <1991Jun5.072556.19870@irisa.fr> jezequel@irisa.fr (Jean-Marc Jezequel) writes: >Let me summarize even further: It seems that we all agree on: >1) Functions with side effects are dangerous, and don't follow the >road towards better software quality >2) Procedures which return values are often usefull > >So why not trying to make a syntatical difference between the two >concepts (keyword like "pure" for pure functions)? >I guess it is too late for Eiffel V3, but may be for V4, when we (hope >to) have tools to make static analysis of programs in order to prove >correctness of pieces of code (i.e. ensuring postconditions and >invariants from preconditions and code), and so on. There are degrees of purity. Idempotency does not imply an absence of side effects. Even a function which is "practically" "pure" should be able to signal an error handler on occasion, which is likely to cause side effects in both I/O and in the I/O support routines' knowledge of the external state. I think the keywords will have to be on the order of "idempotent" and other precise descriptions. -- Norman Diamond diamond@tkov50.enet.dec.com If this were the company's opinion, I wouldn't be allowed to post it. Permission is granted to feel this signature, but not to look at it.
jcm@mstr.hgc.edu (James McKim) (06/05/91)
In article <1991Jun4.041233.19046@runx.oz.au> chrisv@runx.oz.au (Chris Velevitch) writes: >In article <327@alfrat.uucp> roy@alfrat.UUCP (Roy Phillips) writes: >> As a second case for functions with side effects, consider the interface of >> a mutual exclusion class, loosely based upon Djistra's P&V algorithm: >> >> -- >> -- MONITOR -- Resource Allocation Monitor providing mutual >> -- exclusion facilities >> -- >> -- %Z%%Y%:%M% %I% >> >> indexing >> >> date: "$Date: %D% %T% $"; >> revision: "$Revision: %R%.%L% $"; >> >> authors: roy; >> names: monitor; >> access: exclusive; >> >> deferred class MONITOR export >> >> free, >> test_and_set, >> request, >> release, >> got_resource >> >> feature >> >> free: BOOLEAN is >> -- is the resource we are managing available? >> deferred >> end; -- free >> >> test_and_set: BOOLEAN is >> -- is the resource we are managing available to us? >> deferred >> ensure >> Result = True implies got_resource; >> Result = False implies not free and not got_resource >> end; -- test_and_set >> <parts deleted> >> >> got_resource: BOOLEAN >> -- return True if we have successfully obtained >> -- exclusive accesss to resource >> deferred >> ensure >> Result = True implies not free >> end; -- got_resource >> >> end -- class MONITOR >> >> Seperate `request' and `release' operations are an obvious >> requirement (implemented as a function and a procedure respectively) >> but it is essential to provide a `test_and_set' routine, that returns >> a boolean `success/fail' status and grabs the resource if it is free >> - hysteresis between calling `free' and `request' could cause the application >> to perform an undesired wait inside of `request'. > >Testing the result of 'test_and_set' routine is the same as testing >'got_resource'. So 'test_and_set' should be a procedure and the result >available through some other feature, in this case 'got_resource'. > > >Chris >-- >-- >Chris Velevitch, Voice: +61 2 906 6100, Fax: +61 2 906 6069 >Cee Data Systems, 22/39 Herbert St, St Leonards NSW 2065, Australia >Internet: chrisv@runxtsa.runx.oz.au, UUCP: uunet!runxtsa.runx.oz.au!chrisv Hallellujah and welcome soul brother! -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
jcm@mstr.hgc.edu (James McKim) (06/05/91)
In article <130242@tut.cis.ohio-state.edu> ogden@seal.cis.ohio-state.edu (William F Ogden) writes: > >There are a number of considerations that bear upon this issue, but >comprehensibility and efficiency are probably the most important. > >Functions enjoy a prominent position in twentieth century mathematics, and >thus in the educational background of most software professionals. It >makes sense to exploit this shared knowledge when designing software. >Now the principle feature of functions is that they can be composed >into arbitrarily large expressions. If you don't anticipate clients >forming expressions, then functions offer no particular advantage >over procedures as class operations. > >The answer to the question of whether functions should have side-effects >which are visible at the client level is clear when you observe that >side-effects will make the value of experessions dependent upon the >order of evaluation of subexpressions, and hence quite unapparent. > >On the other hand, side-effects which only affect the internal representationsof objects (such as changing the shape of a tree being used to realize a set)should be permitted for efficiency reasons. > Well said! I obviously agree. >The pop/top discussion raises an important efficiency issue in class >design. While we now give lip service to object-oriented design, we >often fail to recognize some of the consequences of what we're advocating. >If the object based software thesis is correct, then our software will be >organized around increasingly large and sophisticated objects, yet when >we design things like stacks, we persist in thinking of the objects >being stored in stacks as being small objects like integers. Instead, >we should recognize that the really serious uses of stacks will involve >storing large objects ( sets, polygons, other stacks, etc. ), and that >to achieve real reusability, our stack operations should be chosen with >an eye to making them efficient for storing large objects. > >Probably the most significant feature of large objects, as opposed to >small objects like integers, is that they are usually quite expensive (if >not impossible) to replicate. Consequently operations like Top make poor >choices as primary operations, since their implementation inevitably >involves making a copy of a data structure entry. The proper choice >of primary operation for the stack then is the procedure (not function >-- see above) Pop which does return the top value, since this does not >entail replicating an entry. Top can be provided as a secondary operation, >but clients should be warned that it is potentially an expensive operation. > Now I'm confused. The first part of your post argues that functions should, in general, not have side effects that change the visible state of an object. The second part argues that procedures, which do change the state, should often have return values. Are you making a distinction between functions with side effects and procedures with return values? I also must question the premise of the second part of your argument. Most of the OO data structure classes I have seen use referential semantics, so a function like Top does not necessarily involve any replication beyond that of a pointer. But even if I agree that such replication _should_ be the norm I would argue for Top as a side effect free function and Pop as a return free (to coin a phrase) procedure on the basis of comprehensibility. If a particular application requires the efficiency of a Pop_Top then extend the class, possibly via inheritance to include it, but don't include it as a matter of course. All such features make the class harder to understand, and if done as a matter of course there will be _lots_ of them. All the efficiency in the world won't help if users, maintainers, implementers cannot understand the class. >-- > >/Bill Interesting thread! -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
ogden@seal.cis.ohio-state.edu (William F Ogden) (06/06/91)
In article <1991Jun5.144629.5030@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: [my post about functions vs procedures and the Pop/Top choice deleted] >Now I'm confused. The first part of your post argues that functions >should, in general, not have side effects that change the visible state >of an object. The second part argues that procedures, which do change >the state, should often have return values. Are you making a distinction >between functions with side effects and procedures with return values? Indeed. This distinction is based on the fact that functions can be composed into arbitrarily structured expressions in which the order of evaluation is uncertain, whereas procedure calls can only be composed in simple sequences in which the order of execution is obvious. >I also must question the premise of the second part of your argument. >Most of the OO data structure classes I have seen use referential >semantics, so a function like Top does not necessarily involve any >replication beyond that of a pointer. Referential semantics do address the efficiency of replication problem, but unfortunately, in most situations they undermine comprehensibility. In this case, if a client uses the Top operation to obtain a `copy' of some large object from a stack, does a few operations on this copy while pushing a few more objects on the stack, then she will be quite surprised to discover that the value of the entry in the stack from which the copy was made has changed in value. Now the Top operation itself might be a `side effect free' function in such an implementation, but the resulting system would fraught with strange side effects. > But even if I agree that such >replication _should_ be the norm I would argue for Top as a side >effect free function and Pop as a return free (to coin a phrase) >procedure on the basis of comprehensibility. If a particular application >requires the efficiency of a Pop_Top then extend the class, possibly >via inheritance to include it, but don't include it as a matter of >course. All such features make the class harder to understand, and >if done as a matter of course there will be _lots_ of them. All the >efficiency in the world won't help if users, maintainers, implementers >cannot understand the class. Actually, `Pop_Top' is quite comprehensible and at least as useful as the Top and Pitch_Top operations. Certainly many classes are now being designed to include far too many primary operations, as you observe. However, if you analyze the situation here, you will find that it's the traditional Top and Pitch_Top operations which are really secondary and thus should be added as extensions to the basic stack class. -- /Bill
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/06/91)
In article <1991Jun5.140023.4614@mstr.hgc.edu>, jcm@mstr.hgc.edu (James McKim) writes: > In article <1991Jun4.041233.19046@runx.oz.au> chrisv@runx.oz.au (Chris Velevitch) writes: > >Testing the result of 'test_and_set' routine is the same as testing > >'got_resource'. So 'test_and_set' should be a procedure and the result > >available through some other feature, in this case 'got_resource'. > Hallellujah and welcome soul brother! If you two "soul brothers" will have the kindness to label your programs in bright red letters "DANGER -- DO NOT USE" I will much appreciate it. This separation between setting a flag and accessing it is a *disaster* in multi-threaded systems. That includes systems which can handle external interrupts (such as SIGINT). Consider for example C's interface to system calls: if you have an interrupt handler in your program you can *never* be certain that if (open(...) == 1) { /* inspect errno to see what went wrong */ } will work. (The irony is that the _assembly_code_ interface that I occasionally used in UNIX V7 on a PDP-11 *is* safe.) You should *never* allow a separation between return from an operation and delivering the results unless you can be absolutely certain that no other use of that operation will intervene. If you don't like procedures that return a status value, add an extra "status" argument to the interface. But please, in the interests of writing code that stands a chance of working in a multi-threaded environment (like this Encore, or like SunOS 4, or like SVR4) or in an environment with interrupts (like a PC or VMS or ...), *don't* leave "outcomes" lying around in variables where they can be trampled on. -- Should you ever intend to dull the wits of a young man and to incapacitate his brains for any kind of thought whatever, then you cannot do better than give him Hegel to read. -- Schopenhauer.
rick@tetrauk.UUCP (Rick Jones) (06/07/91)
In article <130242@tut.cis.ohio-state.edu> ogden@seal.cis.ohio-state.edu (William F Ogden) writes: | [ on the subject of large objects ] | | Probably the most significant feature of large objects, as opposed to | small objects like integers, is that they are usually quite expensive (if | not impossible) to replicate. Consequently operations like Top make poor | choices as primary operations, since their implementation inevitably ^^^^^^^^^^ | involves making a copy of a data structure entry. The proper choice | of primary operation for the stack then is the procedure (not function | -- see above) Pop which does return the top value, since this does not | entail replicating an entry. Top can be provided as a secondary operation, | but clients should be warned that it is potentially an expensive operation. You are presuming a system with value semantics. OO systems often work very effectively with reference semantics (in Eiffel reference semantics are the default unless you specify "expanded" variables or classes). In this case the Top operation simply returns a pointer to the object on the top of the stack, which is highly efficient. In fact I would suggest that a system in which large objects are used is best handled using reference semantics, otherwise there will be a lot of inefficiencies elsewhere resulting from copying. The programmer must of course be aware of this, and use "clone" operations where required. -- Rick Jones, Tetra Ltd. Maidenhead, Berks, UK rick@tetrauk.uucp Any fool can provide a solution - the problem is to understand the problem
ogden@seal.cis.ohio-state.edu (William F Ogden) (06/07/91)
In article <1177@tetrauk.UUCP> rick@tetrauk.UUCP (Rick Jones) writes: ... | Consequently operations like Top make poor | choices as primary operations, since their implementation inevitably ^^^^^^^^^^ | involves making a copy of a data structure entry. ... >You are presuming a system with value semantics. OO systems often work >very effectively with reference semantics (in Eiffel reference semantics are >the default unless you specify "expanded" variables or classes). In this case >the Top operation simply returns a pointer to the object on the top of the >stack, which is highly efficient. >In fact I would suggest that a system in which large objects are used is best >handled using reference semantics, otherwise there will be a lot of >inefficiencies elsewhere resulting from copying. The programmer must of course >be aware of this, and use "clone" operations where required. I guess I did presume it was obvious that the strange side effects which result from the aliasing inherent in general reference semantics violated the comprehensibility requirement for reusable software. As it turns out, referencs semantics are fine -- provided you only allow _one_ reference to each object. (With this constraint, you effectively have value semantics, of course.) Now the problem, rephrased in these terms, is that our small object bias leads us to design classes with operations like Top which create multiple references to the same object. One of the challenges of object oriented programming is still to design classes so that excess copying can be avoided or (if you insist on reference semantics) so that multiple references can be avoided. -- /Bill
jcm@mstr.hgc.edu (James McKim) (06/07/91)
In article <130803@tut.cis.ohio-state.edu> ogden@seal.cis.ohio-state.edu (William F Ogden) writes: >In article <1991Jun5.144629.5030@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: > > [my post about functions vs procedures and the Pop/Top choice deleted] > >>Now I'm confused. The first part of your post argues that functions >>should, in general, not have side effects that change the visible state >>of an object. The second part argues that procedures, which do change >>the state, should often have return values. Are you making a distinction >>between functions with side effects and procedures with return values? > >Indeed. This distinction is based on the fact that functions can be composed >into arbitrarily structured expressions in which the order of evaluation >is uncertain, whereas procedure calls can only be composed in simple >sequences in which the order of execution is obvious. > Well, maybe I'm being dense, but I don't think you've made any real distinction between functions with side effects and procedures with return values. What you've said is that functions without side effects "can be composed into arbitrarily structured expressions in which the order of evaluation is uncertain" (I agree BTW), and that functions with side effects cannot. >>I also must question the premise of the second part of your argument. >>Most of the OO data structure classes I have seen use referential >>semantics, so a function like Top does not necessarily involve any >>replication beyond that of a pointer. > >Referential semantics do address the efficiency of replication problem, >but unfortunately, in most situations they undermine comprehensibility. >In this case, if a client uses the Top operation to obtain a `copy' of >some large object from a stack, does a few operations on this copy while >pushing a few more objects on the stack, then she will be quite surprised >to discover that the value of the entry in the stack from which the >copy was made has changed in value. Now the Top operation itself might >be a `side effect free' function in such an implementation, but the >resulting system would fraught with strange side effects. > Absolutely right. (But you didn't need me to tell you that :-)) The specs of the class must make clear whether the client is receiving a reference or a copy. When referential semantics are used the client has extra concerns. This is a classic efficiency/simplicity tradeoff. >> But even if I agree that such >>replication _should_ be the norm I would argue for Top as a side >>effect free function and Pop as a return free (to coin a phrase) >>procedure on the basis of comprehensibility. If a particular application >>requires the efficiency of a Pop_Top then extend the class, possibly >>via inheritance to include it, but don't include it as a matter of >>course. All such features make the class harder to understand, and >>if done as a matter of course there will be _lots_ of them. All the >>efficiency in the world won't help if users, maintainers, implementers >>cannot understand the class. > >Actually, `Pop_Top' is quite comprehensible and at least as useful as >the Top and Pitch_Top operations. > >Certainly many classes are now being designed to include far too many >primary operations, as you observe. Right, it's not Pop_Top itself that I'm concerned with, it's the mode of thinking that makes Pop_Top the default. > However, if you analyze the >situation here, you will find that it's the traditional Top and Pitch_Top >operations which are really secondary and thus should be added as >extensions to the basic stack class. > Whoa! I thought you were at least willing to include _Top_ as a primary feature. If you only have Pop_Top then every time you need to make a decision based on the current top, you have to pop the item, save it since it's no longer on top of the stack, do whatever else you want to do with it being careful not to change it, and then push it back on the stack. In any case, my analysis differs from yours, I still want Top and Pop (Pitch_Top) as the primary features. > >-- > >/Bill -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
weide@elephant.cis.ohio-state.edu (Bruce Weide) (06/08/91)
In article <1177@tetrauk.UUCP> rick@tetrauk.UUCP (Rick Jones) writes: > >You are presuming a system with value semantics. OO systems often work >very effectively with reference semantics (in Eiffel reference semantics are >the default unless you specify "expanded" variables or classes). In this case >the Top operation simply returns a pointer to the object on the top of the >stack, which is highly efficient. > >In fact I would suggest that a system in which large objects are used is best >handled using reference semantics, otherwise there will be a lot of >inefficiencies elsewhere resulting from copying. The programmer must of course >be aware of this, and use "clone" operations where required. > For discussion of a paradigm of programming that uses value semantics without the inefficiency of copying, see IEEE Transactions on Software Engineering, May 1991, which should be on your local newsstand very soon :-). The key idea is to replace most copying with swapping, since most uses of copying aren't really necessary anyway. Swapping has two big advantages: it can be implemented efficiently by the language system (by swapping references) even while the programmer sees only value semantics; and it never introduces aliasing. This, as Bill Ogden has pointed out, is very important if you want to produce programs about which it is easy to reason. Doing things like "copying a pointer to the object on the top of the stack" is just asking for trouble, and this has been well-known and repeatedly pointed out by such people as Hoare and Kieburtz for nearly 20 years. As Bill also was saying, copying references is itself not all bad. It is great for efficiency. The problems arise when aliasing produces surprising behavioral side-effects because variables/objects that aren't even mentioned in a piece of code get changed behind your back. This is related to the question of whether functions should have side effects. For example, I'm surprised that some people seem to feel functions should not have side effects ON THEIR ARGUMENTS, but seem perfectly willing to settle for programs with arbitrary aliasing where both functions and procedures may have side effects ON VIRTUALLY ANY OTHER VARIABLES/OBJECTS, even ones not explicitly mentioned in the code in question. This is exactly the situation that arises if you define "Top" as copying a pointer to the object on top of the stack. -Bruce
jgk@osc.COM (Joe Keane) (06/08/91)
I think this is a symptom of a more general problem. People try to make their
classes `whizzy' rather than clean and easy to understand. They add features
because they `might be useful', rather than that there's a good reason that
the features should be part of the class. KISS.
Suppose i'm writing a widget class. Widgets have a property called `part'. I
want to write methods to access and modify this property. The way i would do
this in C++ is the following:
class Widget
{
...
Part get_part();
void set_part(const Part&);
}
This is so simple and easy to understand, you'd think everyone would do it this
way. But no, people will manage to screw it up in new and interesting ways.
One way is by adding unnecessary functionality. For example, they say it
`might be useful' for the set method to return the old value. I think this is
stupid. If i wanted the old value, i would have called get_part first.
Some people would name either or both of these methods just `part', perhaps to
save keystrokes. I think this indicates a confusion between a method and the
value it returns. Here is the way i see it: `widget.part' is an attribute,
`widget.get_part()' is a method call which returns the part, `widget.part()'
is a mistake since you're trying to call an object, and `widget.get_part' is a
method which would return the part if you called it.
Sometimes it may be a good idea to provide a method which combines the
functionality of two simpler methods. But there has to be a good reason, more
than just the fact that the original two methods may be called sequentially.
For example, there may be some good reason you can make the combined method
significantly more efficient than calling the original methods separately.
And i don't mean you'd save a single function call overhead, it has to be more
than that. If you followed that reasoning, you'd have to provide a method for
almost every pair of methods you had originally. For example, in a list class
you'd need to put a method called
`swap_the_last_two_elements_delete_the_first_element_and_return_it'.
--
Joe Keane, amateur mathematician
jgk@osc.com (...!uunet!stratus!osc!jgk)ogden@seal.cis.ohio-state.edu (William F Ogden) (06/08/91)
In article <1991Jun7.135613.1515@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: [Quote deleted] >Well, maybe I'm being dense, but I don't think you've made any real >distinction between functions with side effects and procedures with >return values. What you've said is that functions without side effects >"can be composed into arbitrarily structured expressions in which the >order of evaluation is uncertain" (I agree BTW), and that functions with >side effects cannot. OK. Let's look at the side effecting function Pop_of vs. the value returning Pop_Top procedure on stacks of say integers. If we have a stack whose top two entries are say 5 and 3, then, because there's an indeterminate order of evaluation problem even in fairly simple situations, executing Dif := Pop_of(S) - Pop_of(S); might cause Dif to be either 2 or -2. In contrast, with the Pop_Top procedure, there can be no uncertainty because a programmer must explicitly sequence the operations. Pop_Top(S,t1); Pop_Top(S,t2); Dif := t1 - t2; {or t2 - t1} > .... When referential semantics are used the client >has extra concerns. This is a classic efficiency/simplicity tradeoff. Actually, this particular one is a manufactured efficiency/simplicity tradeoff created by the designer's insistence upon foisting off the Top operation on unsuspecting clients. .... >Right, it's not Pop_Top itself that I'm concerned with, it's the >mode of thinking that makes Pop_Top the default. So I see. >> However, if you analyze the >>situation here, you will find that it's the traditional Top and Pitch_Top >>operations which are really secondary ... >Whoa! I thought you were at least willing to include _Top_ as a primary >feature. If you only have Pop_Top then every time you need to make a >decision based on the current top, you have to pop the item, save it >since it's no longer on top of the stack, do whatever else you >want to do with it being careful not to change it, and then >push it back on the stack. Fine. Let's analyze your alternative: ...then every time you need to make a decision based on the current top, you have to [pop the item] apply the Top function, save [it since it's no longer on top of the stack] the resulting item reference, do whatever else you want to do with it being careful not to change it, and then [push it back on the stack] destroy the reference so you won't inadvertently modify the referenced item. That's a wash in my book, but Top bought us a bunch of aliasing problems that Pop_Top avoided. >In any case, my analysis differs from yours, I still want Top and Pop >(Pitch_Top) as the primary features. At a visceral level, I suppose that all us old timers want Top and Pop to turn out to be the right design, because that's what we grew up with. However, analytically, ... -- /Bill
kers@hplb.hpl.hp.com (Chris Dollin) (06/10/91)
Deep in the heart of James McKim's message I noted: Whoa! I thought you were at least willing to include _Top_ as a primary feature. If you only have Pop_Top then every time you need to make a decision based on the current top, you have to pop the item, save it since it's no longer on top of the stack, do whatever else you want to do with it being careful not to change it, and then push it back on the stack. My vision of Stack is one in which ``every time you need to make a decision based on the current top'' is a non-issue; you stuff things on the stack, later you get them back. Why would you want to ``make a decision'' based on the ``top element''? (All the code I've done with stacks just pops the element when it wants it. Repeated access to that element - while it's still on the stack - just doesn't seem to be one of the desired properties. No, this isn't an artifact of using imperative pop!) Perhaps we're talking about two different data-types both called ``Stack''? -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
paj@mrcu (Paul Johnson) (06/10/91)
>There are degrees of purity. Idempotency does not imply an absence of >side effects. Even a function which is "practically" "pure" should be >able to signal an error handler on occasion, which is likely to cause >side effects in both I/O and in the I/O support routines' knowledge of >the external state. Why not add a keyword `unchanged' to the `ensure' clause? This would be equivalent to something along the lines of `current.equal( old current )' and would assert that the function has not changed anything. Function purity then becomes a run-time checkable assertion. Of course it does not handle internal changes (such as the tree rearangement which someone suggested) but that *is* a little more complicated. For functions which simply return some aspect of the state it would do quite well. Paul. -- Paul Johnson | Isn't modern education wonderful: one size fits all! -------------^------------------v-------------------------v------------------- GEC-Marconi Research is not | Telex: 995016 GECRES G | Tel: +44 245 73331 responsible for my opinions. | Inet: paj@gec-mrc.co.uk | Fax: +44 245 75244
jcm@mstr.hgc.edu (James McKim) (06/10/91)
In article <6135@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <1991Jun5.140023.4614@mstr.hgc.edu>, jcm@mstr.hgc.edu (James McKim) writes: >> In article <1991Jun4.041233.19046@runx.oz.au> chrisv@runx.oz.au (Chris Velevitch) writes: >> >Testing the result of 'test_and_set' routine is the same as testing >> >'got_resource'. So 'test_and_set' should be a procedure and the result >> >available through some other feature, in this case 'got_resource'. > >> Hallellujah and welcome soul brother! > >If you two "soul brothers" will have the kindness to label your programs >in bright red letters "DANGER -- DO NOT USE" I will much appreciate it. Now, now, no need to get testy. >This separation between setting a flag and accessing it is a *disaster* >in multi-threaded systems. No one disagrees that 'test_and_set' must be atomic. The only question is how to inform the client whether 'test_and_set' succeeded. Is it better to return a value directly or set an attribute that the client may check? Whoops! OK I think I see the light. The problem occurs if I call test_and_set and got_resource is set to True, but before I get around to checking it, somebody else calls test_and_set and since I have the resource (but don't know it yet), got_resource is set to False. This is indeed a compelling reason for test_and_set to both return a value and have the side effect of setting free to False and I don't see any reasonably easy way around it. Thanks for exciting the right set of neurons. :-) > >If you don't like procedures that return a status value, add an extra >"status" argument to the interface. Well, conceptually this is still a function with side effects. The return value is simply in a different place. I still argue that the default should be to avoid such things, but there _are_ counterexamples. >Should you ever intend to dull the wits of a young man and to >incapacitate his brains for any kind of thought whatever, then >you cannot do better than give him Hegel to read. -- Schopenhauer. -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
jcm@mstr.hgc.edu (James McKim) (06/10/91)
In article <131732@tut.cis.ohio-state.edu> ogden@seal.cis.ohio-state.edu (William F Ogden) writes: >In article <1991Jun7.135613.1515@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: > > [Quote deleted] > >>Well, maybe I'm being dense, but I don't think you've made any real >>distinction between functions with side effects and procedures with >>return values. What you've said is that functions without side effects >>"can be composed into arbitrarily structured expressions in which the >>order of evaluation is uncertain" (I agree BTW), and that functions with >>side effects cannot. > >OK. Let's look at the side effecting function Pop_of vs. the value >returning Pop_Top procedure on stacks of say integers. If we have >a stack whose top two entries are say 5 and 3, then, because there's >an indeterminate order of evaluation problem even in fairly simple >situations, executing > > Dif := Pop_of(S) - Pop_of(S); > >might cause Dif to be either 2 or -2. In contrast, with the Pop_Top >procedure, there can be no uncertainty because a programmer must >explicitly sequence the operations. > Pop_Top(S,t1); > Pop_Top(S,t2); > Dif := t1 - t2; {or t2 - t1} > OK, so when you say 'procedure with a return value' you mean the value is returned through arguments of the procedure. Conceptually, this is still a function with side effects (the return value is just in a different place). The distinction depends on the language definition or implementation. > >>> However, if you analyze the >>>situation here, you will find that it's the traditional Top and Pitch_Top >>>operations which are really secondary ... > >>Whoa! I thought you were at least willing to include _Top_ as a primary >>feature. If you only have Pop_Top then every time you need to make a >>decision based on the current top, you have to pop the item, save it >>since it's no longer on top of the stack, do whatever else you >>want to do with it being careful not to change it, and then >>push it back on the stack. > >Fine. Let's analyze your alternative: > ...then every time you need to make a decision based on the current top, >you have to [pop the item] apply the Top function, save [it since it's no >longer on top of the stack] the resulting item reference, do whatever else >you want to do with it being careful not to change it, and then [push it >back on the stack] destroy the reference so you won't inadvertently modify >the referenced item. That's a wash in my book, but Top bought us a bunch >of aliasing problems that Pop_Top avoided. > Touche! However, I still favor Top as the conceptually simpler operation. If we extend your reasoning, any time I merely want to glance at an element of any data structure, I have to remove it and then restore it. Better to keep the simpler operations and look for more efficient ways to implement them. > >At a visceral level, I suppose that all us old timers want Top and Pop >to turn out to be the right design, because that's what we grew up >with. However, analytically, ... > Well, I must be an older timer than you :-) All my old data structures books have pop_top. > >-- > >/Bill -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
jcm@mstr.hgc.edu (James McKim) (06/11/91)
In article <1991Jun10.151959.29568@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: (This is me, unfortunately!) >In article <131732@tut.cis.ohio-state.edu> ogden@seal.cis.ohio-state.edu (William F Ogden) writes: >>OK. Let's look at the side effecting function Pop_of vs. the value >>returning Pop_Top procedure on stacks of say integers. If we have >>a stack whose top two entries are say 5 and 3, then, because there's >>an indeterminate order of evaluation problem even in fairly simple >>situations, executing >> >> Dif := Pop_of(S) - Pop_of(S); >> >>might cause Dif to be either 2 or -2. In contrast, with the Pop_Top >>procedure, there can be no uncertainty because a programmer must >>explicitly sequence the operations. >> Pop_Top(S,t1); >> Pop_Top(S,t2); >> Dif := t1 - t2; {or t2 - t1} >> > >OK, so when you say 'procedure with a return value' you mean the >value is returned through arguments of the procedure. Conceptually, >this is still a function with side effects (the return value is just >in a different place). The distinction depends on the language >definition or implementation. > Well, it's now Monday afternoon (I should be banned from posting on Monday morning!) and I now understand (I think) the conceptual difference. Pop_Top as defined above does _not_ return a value for immediate use, rather it changes the state of _two_ objects, the client and the supplier. On the other hand, Pop_of both changes the state of the stack object and returns a value for immediate use, which Bill clearly demonstrates can cause confusion. Now, did I make the same error in another post this morning...? >> >>-- >> >>/Bill > >-- Jim > -- Me again *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
rick@tetrauk.UUCP (Rick Jones) (06/12/91)
In article <956@puck.mrcu> paj@uk.co.gec-mrc (Paul Johnson) writes: > >Why not add a keyword `unchanged' to the `ensure' clause? This would >be equivalent to something along the lines of `current.equal( old >current )' and would assert that the function has not changed >anything. Wait for Eiffel version 3! (not long now, I hope). It will support a construct "strip" which means "the attributes of this object, except for <the parameters given to strip>". If there are no parameters, it is all the attributes. Then the postcondition "strip = old strip" means "no change". Since strip allows you to explicitly omit specified attributes, you can write a postcondition which means "no change to any attributes except those specified". So by omitting attributes which only affect internal state, the postcondition can ensure that the important things are unchanged, even though the internal state may have been modified. -- Rick Jones, Tetra Ltd. Maidenhead, Berks, UK rick@tetrauk.uucp Chairman, NICE (Non-profit International Consortium for Eiffel) Any fool can provide a solution - the problem is to understand the problem
rick@tetrauk.UUCP (Rick Jones) (06/12/91)
In article <KERS.91Jun10083811@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: > >My vision of Stack is one in which ``every time you need to make a decision >based on the current top'' is a non-issue; you stuff things on the stack, later >you get them back. Why would you want to ``make a decision'' based on the ``top >element''? (All the code I've done with stacks just pops the element when it >wants it. Repeated access to that element - while it's still on the stack - >just doesn't seem to be one of the desired properties. No, this isn't an >artifact of using imperative pop!) > >Perhaps we're talking about two different data-types both called ``Stack''? While your vision of Stack corresponds to one particular implementation, common in hardware, it's in fact quite a specific type of stack. There are many other widely used types of stack where you do get at the top element without popping it. Think of an RPN calculator, for example (something HP are quite fond of, if I recall :-) - the result is a view of the top value of the stack. You don't take it off to look at it - it's still there. Also the memory stack used in most modern CPU's for parameter passing is accessed non-destructively. In practice that's actually a hybrid stack, since any element can be accessed directly. In the most general terms, a stack is just a LIFO buffer. In many applications, your view of a Stack is what you want, but if that is the only way you think of stacks, you'll only use them where that sort of stack is required. Having a more generalised notion of a stack may enable you to use a stack structure effectively in other situations. This is what's difficult but ultimately satisfying about OO - tearing yourself away from implementation and seeing the wider abstraction. And in the end, you get better software. -- Rick Jones, Tetra Ltd. Maidenhead, Berks, UK rick@tetrauk.uucp Chairman, NICE (Non-profit International Consortium for Eiffel) Any fool can provide a solution - the problem is to understand the problem
jcm@mstr.hgc.edu (James McKim) (06/13/91)
In article <KERS.91Jun10083811@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: > > >My vision of Stack is one in which ``every time you need to make a decision >based on the current top'' is a non-issue; you stuff things on the stack, later >you get them back. Why would you want to ``make a decision'' based on the ``top >element''? (All the code I've done with stacks just pops the element when it >wants it. Repeated access to that element - while it's still on the stack - >just doesn't seem to be one of the desired properties. No, this isn't an >artifact of using imperative pop!) > >Perhaps we're talking about two different data-types both called ``Stack''? >-- > >Regards, Kers. | "You're better off not dreaming of the things to come; >Caravan: | Dreams are always ending far too soon." Well, this thread began as a question of whether functions should have side effects in general. The stack has just been a convenient example. I take the position that in general functions should not have side effects unless there is a _compelling_ reason (the most common being efficiency) for it. Thus I argue for a side effect free 'top' and a return free, parameter free 'pop'. Others have argued that a side effect free 'top' is good, but let 'pop' return the item it popped as well. (I call this 'pop_top'). In fact some have argued that procedures should return values just like functions do whenever there is some reason to believe the value may be useful. Still others have agreed in principle that side effect free functions are a good thing, but cite exceptions to the rule. And finally, one person has argued that 'pop_top' should be the default because it saves replicating the top object on the stack, which may well be an expensive operation. This has resulted in a spinoff thread on the merits of reference semantics vs value semantics. As to your specific question, examples have been posted that show some value in keeping pop and top separate and I could post more. But let me try appealing to authority instead. Consider D.L. Parnas, "A Technique for Software Module Specification with Examples" CACM, May, 1972. Daniel Hoffman, "On Criteria for Module Interfaces", IEEE TSE, May, 1990 Grady Booch, OOD with Applications, Benjamin Cummings, 1991 (p. 82) and of course Bertrand Meyer, OOSC, Prentice-Hall, 1988 All but Booch specifically discuss stacks. Booch uses a queue. Food for thought. -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
Chris.Holt@newcastle.ac.uk (Chris Holt) (06/15/91)
rick@tetrauk.UUCP (Rick Jones) writes: >In article <KERS.91Jun10083811@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: >> >> [doesn't see why "making a decision" would ever depend on the top >> element of a stack that wouldn't be popped] >> >>Perhaps we're talking about two different data-types both called ``Stack''? >While your vision of Stack corresponds to one particular implementation, common >in hardware, it's in fact quite a specific type of stack. There are many other >widely used types of stack where you do get at the top element without popping >it. Just to add another vision of Stack :-), mine has two operations Push : Stack x Value -> Stack Pop : Stack -> Stack x Value where calls are denoted via equations, and updates via 's (a clumsy syntax, admittedly). Then the usual procedural Push is S' = Push(S,v), the usual Pop might be (S',v) = Pop(S) with v not used again, Pop-Top is the same, with v used as the top value, and the Top function is (T',v) = Pop(S) with T not used again. The equations relating Push and Pop are then (S,v) = Pop(Push(S,v)) and S = Push(Pop(S)) where S != empty. I've always thought this was simpler... ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "They have been at a great feast of languages, and stolen the scraps." - WS
ogden@cis.ohio-state.edu (William F Ogden) (06/15/91)
In article <1991Jun13.135213.28643@mstr.hgc.edu> Jim writes: ... >As to your specific question, examples have been posted that show >some value in keeping pop and top separate and I could post more. >But let me try appealing to authority instead. Consider > D.L. Parnas, "A Technique for Software Module Specification with Examples" > CACM, May, 1972. Now wait a minute. Earlier you claimed that old timers couldn't have a gut level attachment to Top & Pop. But here you are admitting you were aware that those who believed Parnas are almost 20 years into that mode of thinking :-) -- /Bill
jcm@mstr.hgc.edu (James McKim) (06/17/91)
In article <1186@tetrauk.UUCP> rick@tetrauk.UUCP (Rick Jones) writes: > >Wait for Eiffel version 3! (not long now, I hope). Second that (e)motion! And where/how can I get the latest _Eiffel: The Language_ ASAP? > It will support a construct >"strip" which means "the attributes of this object, except for <the parameters >given to strip>". If there are no parameters, it is all the attributes. Then >the postcondition "strip = old strip" means "no change". Since strip allows >you to explicitly omit specified attributes, you can write a postcondition >which means "no change to any attributes except those specified". So by >omitting attributes which only affect internal state, the postcondition can >ensure that the important things are unchanged, even though the internal state >may have been modified. > Hmmm. Is "strip" included in the public interface? Offhand, it seems it should _not_ be since, if I understand correctly, it may include parameters that are private attributes. These the client does not need/want to see and, besides, the public interface should not change if I change the name of a private attribute. Also "strip" wouldn't help with public attributes that change, since the client needs to know _how_ each such attribute changes, not just which ones may. It _does_ look like a very useful compiler directive, though.... >-- >Rick Jones, Tetra Ltd. Maidenhead, Berks, UK rick@tetrauk.uucp >Chairman, NICE (Non-profit International Consortium for Eiffel) > >Any fool can provide a solution - the problem is to understand the problem -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
ogden@seal.cis.ohio-state.edu (William F Ogden) (06/17/91)
In article <1991Jun14.180654.7113@newcastle.ac.uk> Chris.Holt@newcastle.ac.uk (Chris Holt) writes: ... |Just to add another vision of Stack :-), mine has two operations | Push : Stack x Value -> Stack | Pop : Stack -> Stack x Value |where calls are denoted via equations, and updates via 's (a clumsy |syntax, admittedly). Then the usual procedural Push is | S' = Push(S,v), ... Boy this version looks like it would involve a lot of gratuitous stack copying. -- /Bill
jcm@mstr.hgc.edu (James McKim) (06/18/91)
In article <9106141842.AA00313@seal.cis.ohio-state.edu> ogden@cis.ohio-state.edu (William F Ogden) writes: >In article <1991Jun13.135213.28643@mstr.hgc.edu> Jim writes: > ... >>As to your specific question, examples have been posted that show >>some value in keeping pop and top separate and I could post more. >>But let me try appealing to authority instead. Consider >> D.L. Parnas, "A Technique for Software Module Specification with Examples" >> CACM, May, 1972. > >Now wait a minute. Earlier you claimed that old timers couldn't have a >gut level attachment to Top & Pop. But here you are admitting you were >aware that those who believed Parnas are almost 20 years into that mode >of thinking :-) > Just another example of Parnas being well ahead of his time. :-) > > >-- > >/Bill -- Jim *------------------------------------------------------------------------------* Jim McKim (203)-548-2458 _Give_ people fish and they eat for a day. Internet: jcm@mstr.hgc.edu _Teach_ people to fish and they eat for a lifetime.
rick@tetrauk.UUCP (Rick Jones) (06/19/91)
In article <1991Jun17.141842.25702@mstr.hgc.edu> jcm@mstr.hgc.edu (James McKim) writes: |In article <1186@tetrauk.UUCP> rick@tetrauk.UUCP (Rick Jones) writes: |> |>Wait for Eiffel version 3! (not long now, I hope). | |Second that (e)motion! And where/how can I get the latest |_Eiffel: The Language_ ASAP? It's due for publication in July - I have a final draft copy (one of the priveleges of being a member of NICE :-). |> It will support a construct |>"strip" which means "the attributes of this object, except for <the parameters |>given to strip>". If there are no parameters, it is all the attributes. Then |>the postcondition "strip = old strip" means "no change". Since strip allows |>you to explicitly omit specified attributes, you can write a postcondition |>which means "no change to any attributes except those specified". So by |>omitting attributes which only affect internal state, the postcondition can |>ensure that the important things are unchanged, even though the internal state |>may have been modified. |> |Hmmm. Is "strip" included in the public interface? Offhand, it seems it |should _not_ be since, if I understand correctly, it may include parameters |that are private attributes. "strip" is not a feature that can be part of a class interface - it is a language keyword, and its use will yield the attributes of the current object, as seen by the class in which the strip construct is used. This means that even if the object is an instance of a descendant class which introduces new attributes, these attributes will not be included in the result of "strip". It is only really intended for use in postconditions; if you wanted to export the result of a strip expression (which syntactically is an ARRAY[ANY] object), you would have to write a function to do so. (to be precise, you would not actually write "strip = old strip" as I wrote before, the correct expression is "equal (strip, old strip)" - I thought I'd better put that in before someone picks me up on it!) -- Rick Jones, Tetra Ltd. Maidenhead, Berks, UK rick@tetrauk.uucp Chairman, NICE (Non-profit International Consortium for Eiffel) Any fool can provide a solution - the problem is to understand the problem