vidynath@function.mps.ohio-state.edu (Vidhyanath K. Rao) (08/29/90)
[Here kitty kitty]
A while back I posted an article asking "Why are multiple out paramters
bad?". A disk crash in my home computer together with down time on the
mail server has delayed posting a summary of the responses I got.
Most of the responses I got kept refering to "VAR" parameters leading to
aliases. To me this a totally different problem: "VAR" parameters are
implemented using pointers and pointers lead to aliases. Using "copy out"
and "copy in, copy out" parameters should avoid aliasing. The only "better
known" language [that I also know] that does this, albeit only for simple
types, is Ada. I do not have access to Ada compliers or the lastest
documentation. But Ada-80 reference manual confirms my statement above.
Let me elaborate a little on kind of things one does with functions in
mathematics but require contortions in Modula-2 or C: I can form functions
$$f: D_1 \times \cdots \times D_n \to C_1 \times \cdots \times C_m$$
and compose with "meta-functions": projections, "concantations" [products
in the sense of category theory] and permutations [and I don't have to
invent a special unique name for each codomain I use].
Thus one would have a construct of the form:
DECLARE PROC f( p_1, ..., p_n; RETURNS r_1, ..., r_m);
Space for the r_i's would be allocated on the stack. After the called
procedure returns, these would be >*COPIED*< to the actual out paramters.
Projections can be accommadated by allowing the omission of one or more
of the result parameters in the call. Permutations and concantanations would
require list processing at least at compile time; one can do without
them if the compiler used does reasonable optimization and allows arbitarily
long [and multi-line] macros and, of course, variable declarations at the
start of any block. Given only this much functionality, aliases cannot
occur. [Of course you can use the same variable for two of the result
paramters. But the callee would not go haywire; you would be doing a
projection in an implementation dependent manner :-)]
Of course some extensions may be desirable for efficiency: InOut parameters
[using copy in, copy out] for parameters that are modified, passing pointers
to arrays and large structures rather than copying etc. [In this case,
every one would know that pointers are being used instead of the safer
alternatives, and be on guard for problems.]
The forgoing discussion should make it clear that aliasing is due to the
use of pointers in the guise of "VAR" parameters, and has nothing to do
with having multiple out parameters. So the question still remains
unanswered: Why are multiple out parameters bad?
Most of the responses referred to aliasing when passing pointers. I will
omit them.
There were two other respones worthy of note:
Frank Silbermann <fs@rex.cs.tulane.edu>:
[To my question, by E-Mail, on why returning a record of a named type,
declared just for this purpose is ok, but not multiple out parameters?]
This has nothing to do with returning a record or other complex complex
object. He is talking about functions with side effects, e.g. more than
one VAR parameter. i.e. more than one "thing" gets changed. A record
counts as one "thing" because it can be referenced by a single name.
To me this smacks of name magic. And in any case, out parameters need not
be initiliazied beforehand. They are in fact being initiazied, NOT BEING
CHANGED. It looks that way simply becuase of lacunae in certain languages.
mark@parc.xerox.com (Mark Weiser) writes:
[in response to some follow-up article posted to the board]
Modula-(2 and 3), Cedar, Mesa, lots of others have record returns.
I truly don't understand the comment about a record being inadequate
because of the drastically different types--a record is that data
structure one uses when one has drastically different types. C requires
that to return a record one must separately define it. Cedar (e.g.)
has the convention that the procedure declaration defines an implicit
record type to be the return value...
I am not familiar with Cedar [or Mesa]. I would appreciate a list of easily
available references to such languages. IMHO, just grafting implicit record
types to Modula-2 or C will not allow efficient ways of doing projections,
concantanations and permutations.
Incidentally, every single language I know of does use implicit records:
For domains of procedures. As a mathematician, I find the asymmetry between
the treatments of domain and codomain bizarre.
And a parting, jocular shot: [Mark again, refering to another posting which
I lost. I am very likely quoting out of context. Apologies, but I couldn't
resist.]
Reading the code at the point of the call there is no syntactic
evidence about which parameters are which. When huge semantic
differences are hidden by identical syntax, that is a bad thing.
I agree:-^. VAR parameters are used for (1) out parameters, (2) in-out
parameters, and (3) passing pointers to save space. Let us outlaw VAR
parameters, and make programmers say which of the three they are really
doing.
--
Vidhyanth Rao It is the man, not the method, that solves
function.mps.ohio-state.edu the problem. - Henri Poincare
(614)-366-9341 [as paraphrased by E. T. Bell]dwiggins@atsun.a-t.com (Don Dwiggins) (08/31/90)
In article <1990Aug28.203643.11214@zaphod.mps.ohio-state.edu> vidynath@function.mps.ohio-state.edu (Vidhyanath K. Rao) writes:
Incidentally, every single language I know of does use implicit records:
For domains of procedures. As a mathematician, I find the asymmetry between
the treatments of domain and codomain bizarre.
You'd probably like logic programming then. Not only can there easily be
multiple out parameters, a parameter can be out in one call and in in
another. I don't know what Dijkstra thinks of Prolog, but this symmetry
occurs naturally and is often a useful conceptual and practical tool.
--
Don Dwiggins "If you think training is expensive,
Ashton-Tate, Inc. try ignorance"
dwiggins@ashtate.a-t.com -- Derek Bok, Harvard U.dinucci@ogicse.ogi.edu (David C. DiNucci) (08/31/90)
In article <DWIGGINS.90Aug30195906@atsun.a-t.com> dwiggins@atsun.a-t.com (Don Dwiggins) writes: >In article <1990Aug28.203643.11214@zaphod.mps.ohio-state.edu> vidynath@function.mps.ohio-state.edu (Vidhyanath K. Rao) writes: > > Incidentally, every single language I know of does use implicit records: > For domains of procedures. As a mathematician, I find the asymmetry between > the treatments of domain and codomain bizarre. > >You'd probably like logic programming then. Not only can there easily be >multiple out parameters, a parameter can be out in one call and in in >another. I don't know what Dijkstra thinks of Prolog, but this symmetry >occurs naturally and is often a useful conceptual and practical tool. Prolog likely suffers from exactly the kind of complexity in data flow that the original attribution to Dijkstra seems to have warned about. Strand (a parallel processing variant) at least partially addresses this by identifying parameters as either in or out when a procedure (clause, process) is defined. Large-Grain Data Flow 2 (aka F-Nets) takes the approach that the single out restriction is fine for much of the low-level implementation of any large system, and that traditional imperative textual sequential languages are well suited to express such computation. But at higher "system" levels, modules which each do a fair amount of work, and thus are likely to return many different kinds of results, are being composed. Plugging these results into a record structure just so they can be pulled back apart again is nonproductive, but allowing multiple out parameters in a textual syntax complicates the tracing of data (and in LGDF2's case, control) flow in just the way Dijkstra claims. The problem here is not *multiple out parameters*, but *textual syntax*. A graphical syntax clears those problems up rather nicely, and as stated, is only proposed for the high-level module composition. A module is a function where each argument is identified as in, out, inout, or neither (control flow only), and the graphical syntax shows the data flow clearly with arrows on one, both, or neither end of each arc representing an argument. The symmetry between domain and codomain is preserved. This approach was borrowed directly (by Babb) from DeMarco-style Structured Analysis data flow diagrams, as an attempt to forego the intermediate step of translating the diagram to a structure chart before implementation. The current aim of the model, other than the software-engineering aims expressed above, is to provide an architecture-independent model for parallel processing. -Dave -- David C. DiNucci Oregon Graduate Institute (Formerly Oregon Graduate Center) CSNET: dinucci@cse.ogi.edu 19600 N.W. Von Neumann Dr. UUCP: ..ucbvax!tektronix!ogicse!dinucci Beaverton, Oregon 97006
fs@rex.cs.tulane.edu (Frank Silbermann) (08/31/90)
In article <11831@ogicse.ogi.edu> dinucci@ogicse.ogi.edu (David C. DiNucci) writes: > > ... at higher "system" levels > modules are being composed which each do a fair amount of work, > and thus are likely to return many different kinds of results. > Plugging these results into a record structure > just so they can be pulled back apart again is nonproductive. When a collection of diverse of values forms a single conceptual unit, it should be treated as a unit within the program. Therefore we define a record-type to represent the concept, If a module's different kinds of results do _not_ form a conceptual unit, then the design is kludgy and should be redone. What ever happened to the idea that every module should perform a single conceptual operation (i.e. produce a single conceptual result)? Frank Silbermann fs@rex.cs.tulane.edu Tulane University New Orleans, Louisianna USA
cik@l.cc.purdue.edu (Herman Rubin) (09/01/90)
In article <4019@rex.cs.tulane.edu>, fs@rex.cs.tulane.edu (Frank Silbermann) writes: > > In article <11831@ogicse.ogi.edu> > dinucci@ogicse.ogi.edu (David C. DiNucci) writes: | > | > ... at higher "system" levels | > modules are being composed which each do a fair amount of work, | > and thus are likely to return many different kinds of results. | > Plugging these results into a record structure | > just so they can be pulled back apart again is nonproductive. > > When a collection of diverse of values > forms a single conceptual unit, > it should be treated as a unit within the program. > Therefore we define a record-type to represent the concept, > > If a module's different kinds of results > do _not_ form a conceptual unit, > then the design is kludgy and should be redone. > What ever happened to the idea that every module > should perform a single conceptual operation > (i.e. produce a single conceptual result)? Kludgy it is not. For example, a procedure can produce a result and a domain indicator, such as the truth of a condition. Or an integer quotient and a floating remainder can be produced. Or a short integer exponent and a mantissa. Or the decomposition of a word into fields, one being translated into a sign, another into an integer, and the rest into a floating point number. All of these are natural and useful multiple outputs. Putting these into a record to extract later is very definitely non-productive, just as encoding multiplication as repeated addition is non-productive. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP)
fs@rex.cs.tulane.edu (Frank Silbermann) (09/04/90)
David C. DiNucci: dinucci@ogicse.ogi.edu <11831@ogicse.ogi.edu> >| > ... at higher "system" levels >| > modules are being composed which each do a fair amount of work, >| > and thus are likely to return many different kinds of results. >| > Plugging these results into a record structure >| > just so they can be pulled back apart again is nonproductive. Frank Silbermann: fs@rex.cs.tulane.edu <4019@rex.cs.tulane.edu>, >> Every module should perform a single conceptual operation >> i.e. produce a single conceptual result, >> and should be treated as a unit within the program >> (i.e. as a record). If a module's different kinds of results >> do _not_ form a conceptual unit, then the design is a kludge. In article <2501@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: > All of these are natural and useful multiple outputs: > ...a result and a domain indicator, e.g. the truth of a condition. > ...an integer quotient and a floating remainder. > ...a short integer exponent and a mantissa. > ...the decomposition of a word into fields -- one a sign, > another an integer, and the rest a floating point. (And each combination can be viewed as a single object. So...?) > Putting these into a record to extract later > is very definitely non-productive, > like encoding multiplication as repeated addition. The time loss due to encoding multiplication as repeated addition is O(n). Grouping atomic information into records hurts efficiency by at most a constant factor (and an optimizing compiler might eliminate even that). A better analogy would the claim that "storing a register into memory, only to later load it back, is definitely non-productive, and therefore its is better to program in assembler language." (Such claims have in fact been made.) The real question is where a program ought to lie on the machine-oriented/human-oriented continuum. This is an economic($$) decision, with no universal answer. For most applications, however, the economics are shifting to favor more human-oriented programming, and this includes the clumping of detail into fewer, but larger and more meaningful, concepts. That's what records are for. Frank Silbermann fs@rex.cs.tulane.edu Tulane University New Orleans, Louisianna USA
cik@l.cc.purdue.edu (Herman Rubin) (09/05/90)
In article <4060@rex.cs.tulane.edu>, fs@rex.cs.tulane.edu (Frank Silbermann) writes: > David C. DiNucci: dinucci@ogicse.ogi.edu <11831@ogicse.ogi.edu> | >| > ... at higher "system" levels | >| > modules are being composed which each do a fair amount of work, | >| > and thus are likely to return many different kinds of results. | >| > Plugging these results into a record structure | >| > just so they can be pulled back apart again is nonproductive. > Frank Silbermann: fs@rex.cs.tulane.edu <4019@rex.cs.tulane.edu>, > >> Every module should perform a single conceptual operation > >> i.e. produce a single conceptual result, > >> and should be treated as a unit within the program > >> (i.e. as a record). If a module's different kinds of results > >> do _not_ form a conceptual unit, then the design is a kludge. > In article <2501@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: > > All of these are natural and useful multiple outputs: > > ...a result and a domain indicator, e.g. the truth of a condition. > > ...an integer quotient and a floating remainder. > > ...a short integer exponent and a mantissa. > > ...the decomposition of a word into fields -- one a sign, > > another an integer, and the rest a floating point. > (And each combination can be viewed as a single object. So...?) > > > Putting these into a record to extract later > > is very definitely non-productive, > > like encoding multiplication as repeated addition. > The time loss due to encoding multiplication > as repeated addition is O(n). Grouping atomic information > into records hurts efficiency by at most a constant factor > (and an optimizing compiler might eliminate even that). Assuming fixed length numbers being added, this is so. But if one has 64-bit numbers being multiplied, and performs an addition every nanosecond (I do not believe that this has been quite yet obtained), it can take almost 600 years to perform the multiplication. The storage and reloading process right now can impose a factor of 5 or more now. If load/store continues to get slower compared to arithmetic, the O(n) term gets larger, so maybe it is no longer O(n). > A better analogy would the claim that > "storing a register into memory, only to later load it back, > is definitely non-productive, and therefore its is better > to program in assembler language." (Such claims have in fact been made.) Given a weakly-typed, overloaded-operator, user-extensible method of representing machine operations, with a good flexible macro processor, I would very definitely prefer to program that way. At least at the present time, and for a long time to come, the compiler cannot even begin to recognize what the thinking human finds elementary. > The real question is where a program ought to lie > on the machine-oriented/human-oriented continuum. > This is an economic($$) decision, with no universal answer. > For most applications, however, the economics > are shifting to favor more human-oriented programming, > and this includes the clumping of detail into fewer, > but larger and more meaningful, concepts. > That's what records are for. So the human, who understands what is needed in terms of machine operations, is to be restricted to those clumsy manipulations which the language designer managed to comprehend. This attempt to limit humans to doing what the idiot is capable of, and leaving the rest to the machine, is frustrating to the thinking human, as well as being noneconomic. It results in library programs operating at low speed. The idea that those writing programs to be included in a software library should be restricted to what an undergraduate is expected to do in a beginning programming course is what the above quoted paragraph states. Mathematicians have been dealing with these situations for centuries. That all calculations which can be done on a computer can be done clumsily on a Turing machine does not mean that that should be the way to go. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP)
tom@stl.stc.co.uk (Tom Thomson) (09/05/90)
In article <4060@rex.cs.tulane.edu> fs@rex.cs.tulane.edu (Frank Silbermann) writes: >The real question is where a program ought to lie >on the machine-oriented/human-oriented continuum. >This is an economic($$) decision, with no universal answer. >For most applications, however, the economics >are shifting to favor more human-oriented programming, >and this includes the clumping of detail into fewer, >but larger and more meaningful, concepts. >That's what records are for. > I think records are a red herring here. We may well want to introduce a record type into the language, just so that we can (i) have a label for the type of a function with multiple results (ii) pretend those multiple results are really all one thing There is no need to introduce any objects of these types, though. If I write something like declare decompose:real -> bool * int * int; ........ let (sign, expt, mant) = f(r) ..... then I have provided the call to f with three output parameters (named sign, expt, mant) as required by Rubin while using the structuring concept suggested by FS. But I hope my system never constructs a record at run time. Tom
dlawson@grebyn.com (Drew Lawson) (09/06/90)
In article <2501@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes: >> >> If a module's different kinds of results >> do _not_ form a conceptual unit, >> then the design is kludgy and should be redone. >Kludgy it is not. For example, a procedure can produce a result and a >domain indicator, such as the truth of a condition. Or an integer >quotient and a floating remainder can be produced. All of these examples show an output of a single conceptual object. Returning a quotient and remainder is simply returning the result of a division. This does not complicate things. The problem is procedures which return (set VAR parameters, etc.) a quotient, remainder and the size of the largest available memory block. This is three data items representing two unrelated values. -- +--------------------------------------------------------------------+ | Is life an illusion? | Drew Lawson | | Or does it just seem that way? | dlawson@grebyn.com | +--------------------------------------------------------------------+
jgk@osc.COM (Joe Keane) (09/11/90)
I think returning a record just gets around the issue. We don't use a single record to pass all the in parameters to a function, so why should we do it for out parameters? The original `problem' with multiple problems was really with pointer aliasing, or more generally, modifier aliasing. If objects are returned, there is no possibility of conflict. The caller may actually allocate space on the stack for the returned objects, but this is an implementation issue and there is still no possibility of conflict. There are two ways to deal with aliased modifiers. One way is to say that the modifications are actually sequential. Therefore, if two modifications are done to the same object, one of the modifications is lost, or at least doesn't determine the most current version. The order may be pre-defined, so say the textually earlier parameter is the one that is lost. Or the order may be undefined, so that which ever modifier gets there first loses. The other way is to insist that the modifications are done together, which is more like what we'd expect in a functional language. Then each expression which writes a return value expects to be the last one before the function exits. This works fine as long as they don't both want to write to the same place. What happens if they are aliases? In that case each one has to go before the other. Therefore the problem is deadlock. This makes sense if you think about it; the two problems are really closely related. Two modifiers want exclusive rights to determine a single value, the current state of the returned object. They can't both have it.
norman@d.cs.okstate.edu (Norman Graham) (09/12/90)
From article <3788@osc.COM>, by jgk@osc.COM (Joe Keane): > I think returning a record just gets around the issue. We don't use a single > record to pass all the in parameters to a function, so why should we do it for > out parameters? Counter Example. In my favourite language, Miranda, every function takes exactly one value and returns exactly one value. The question of whether either of those values are tuples (i.e. values of a product type--think of cartesian products of sets here) is irrelevant. This sort of behaviour corresponds well with the set-theoretic view of a function--a map from one set to another. -- Norman Graham Oklahoma State University Internet: norman@a.cs.okstate.edu Computing and Information Sciences BangPath: 219 Mathematical Sciences Building {cbosgd,rutgers}!okstate!norman Stillwater, OK USA 74078-0599
news@usc.edu (09/12/90)
In article <3788@osc.COM> jgk@osc.COM (Joe Keane) writes:
I think returning a record just gets around the issue. We don't
use a single record to pass all the in parameters to a function, so
why should we do it for out parameters?
What's wrong with getting around the issue?
I can see the need for having two "in parameters" (otherwise, joining
hitherto distinct pieces of information is akward), but I fail to see
the need for multiple "out parameters" in a functional language.
Excuse me for being dense, but what is the range?
If you need to do something on the order of passing different pieces
of information (about some core datum) to multiple function
applications, the proper way would seem to be to construct some
derived function which applies the base functions properly. (e.g.
J's conjunctions)eerke@cs.kun.nl (Eerke Boiten) (09/12/90)
In article <3788@osc.COM> jgk@osc.COM (Joe Keane) writes: >I think returning a record just gets around the issue. We don't use a single >record to pass all the in parameters to a function, so why should we do it for >out parameters? In transformational programming (and, probably, elsewhere) it is often convenient to assume that functions have just one argument (which may be a tuple). So we *do* use a single record to pass all the in parameters sometimes. The problem of using a record for the out parameters is that the function f below is not the identity function: f(x) = 7*a+a where (a,a) = x/7 (assuming x/7 = (x DIV 7, x MOD 7)) but who would disagree to this being a (static) semantic error? Eerke Boiten Department of Informatics (STOP Project), K.U.Nijmegen Toernooiveld, 6525 AD Nijmegen, The Netherlands Tel. +31-80-612236. Email: eerke@cs.kun.nl