rbj@icst-cmr.ARPA (Root Boy Jim) (07/03/86)
In article <1836@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >It may be amusing and/or instructive to contemplate the fact that >there is no way to write a function that exchanges the contents of >two variables in a language where parameters are passed "by name". How so? It seems rather simple. I have here a C program that effects call-by-name and does indeed perform a swap: [Example using `thunks' deleted] Yow! Are we talking about the same thing yet? I seem to remember three types (possibly four) of parameter passing: 1) Call by value C scalars 2) Call by reference C pointers, arrays, Fortran variables 3) Call by name Algol call by name (it also does val & ref) Call by reference went something like this: the calling routine would pass the string representation of the argument and the caller would parse it to figure out the argument. Thus if we had a declaration and call: (I forgot Algol so I'm bastardizing C) int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; int i = 5; main() { snafu(a[i]); } snafu(bar) call_by_name bar; { printf("%d\n",bar); /* prints 5 */ i = 7; printf("%d\n",bar); /* prints 7 */ } At least that's what Dr. Vic the BASILIsk told me. Now it does seem that Chris's thunktions will provide a similar effect, so forgive me if this whole article is unnecessary. However, while I could write a thunktion similar to snafu to return the address of any single array element, call by name would allow me to pass a multidimensioned array reference to the same function as well and muck with it. I have never understood the motivation for this technique, or if I ever did, I probably didn't like it. Can you say interpreter? The fourth method I have heard is `Call by value-result'. It seems to be a variation on call by reference or value depending on how it is done. (Root Boy) Jim Cottrell <rbj@icst-cmr.arpa> RHAPSODY in Glue!
throopw@dg_rtp.UUCP (Wayne Throop) (07/03/86)
> gwyn@brl-smoke.UUCP (Doug Gwyn (VLD/VMB) <gwyn>) > It may be amusing and/or instructive to contemplate the fact that > there is no way to write a function that exchanges the contents of > two variables in a language where parameters are passed "by name". Amusing, instructive.... and wrong. I am assuming that you mean "Given a language which passes arguments to functions with call-by-name semantics, it is impossible write an 'exchange argument pair' function, no matter what other facilities the language provides". This is clearly incorrect. In fact, the C language is a counterexample (assuming that the C language includes the preprocessor). Consider: macros act much like functions with by-name arguments. The trick is to utter the swap while mentioning the arguments only once. Thus, one needs a bind-by-reference operation, which in C is nicely provided by the '&' operator (with some restrictions, granted). My conclusion: a swap function is easy to implement even with pass-by-name functions, *provided* there is a bind-by-reference operator in the language. -- It is a lovely language, but it takes a very long time to say anything in it, because we do not say anything in it, unless it is worth taking a long time to say, and to listen to. --- J. R. R. Tolkien -- Wayne Throop <the-known-world>!mcnc!rti-sel!dg_rtp!throopw
chris@maryland.ARPA (Chris Torek) (07/04/86)
From: Root Boy Jim <rbj@icst-cmr.arpa>
I seem to remember three types (possibly four) of parameter passing:
1) Call by value C scalars
2) Call by reference C pointers, arrays, Fortran variables
3) Call by name Algol call by name (it also does val & ref)
The fourth method (as you mention later) is call by value-result.
Call by reference went something like this: the calling
routine would pass the string representation of the argument
and the caller would parse it to figure out the argument.
This much work is not necessary. You simply build static links or
a display and use conventional non-local references in the thunk
procedures. Each thunk procedure returns a pointer to the variable
that represents the evaluation of the appropriate argument, as
performed in the context of the caller. (If a compiler-generated
thunk requires a temporary variable---all expression-thunks do---that
temporary is unnamed, so the fact that a Pascal-ish thunk would be
nested one level greater than the caller is irrelevant. To put it
another way, a compiler can do whatever it wants. :-) )
From: Doug Gwyn (VLD/VMB) <seismo!BRL.ARPA!gwyn>
[Giving equal time to UUCP domains . . . :-)]
No, you just implemented an elaborate form of "call by reference".
I merely chose a poor example. Call by reference and call by name
often have identical effects. See my followup for a better example.
(Incidentally, my expression `example', contained in a comment,
has a different problem: it returns the address of a stack variable
that is no longer active by the time the caller uses it. `t' should
have been declared `static'. This is what comes of dashing off an
article just before bed . . . .)
It is possible to implement full call by name in C, but it is
difficult, for nonlocal reference is difficult; and no one ever
used call by name after Algol anyway---most likely because everyone
thinks it is terrible. Nonlocal reference *is* possible, but
probably best left to a compiler. Kludges are not too hard to
write, but are error-prone: the programmer must keep track of the
lexical level of each routine, and know how many levels up to look,
and at what offset, for each nonlocal variable.
The other three of Root Boy's methods of parameter passing are also
available to C programmers. Call by value is of course trivial.
Call by reference is easy to achieve using pointers (though in fact
the call is still `by value': the value of the pointer expression).
Call by value-result is also easy enough in C, though as with call
by reference, it requires cooperation of both caller and callee:
/* Call by value-result */
f()
{
int i, j;
i = 1;
j = 2;
call_by_value_result(&i, &j);
}
call_by_value_result(addr1, addr2)
int *addr1, *addr2;
{
/* perform the entry protocol: obtain the arguments */
int arg1 = *addr1, arg2 = *addr2;
/*
* code dealing with `arg1' and `arg2' as though
* those were the arguments; no `return's; then:
*/
/* perform the exit protocol: modify the arguments */
*addr1 = arg1;
*addr2 = arg2;
}
The entry protocol is the `value' part; the exit protocol supplies
the `result'. Incidentally, call by value-result is a legal
implementation in at least one of the many FORTRAN standards. It
tends to surprise those who alias a variable and depend on call by
reference to modify two parameters at once:
PROGRAM CALLBY
INTEGER ARG
C Translate the following two PRINTs as appropriate for whatever
C compiler restrictions you have.
PRINT *, ' If it says "3 3" then "7 7", you have call by reference;'
PRINT *, ' if it says "3 3" then "7 3", you have call by value-result.'
ARG = 3
CALL TESTIT (ARG, ARG)
C N.B.: If value-result, ARG could be either 3 or 7 now!
STOP
END
SUBROUTINE TESTIT (I, J)
INTEGER I, J
PRINT *, I, J
I = 7
PRINT *, I, J
RETURN
ENDgwyn@BRL.ARPA (VLD/VMB) (07/04/86)
I'm not sure how one would implement a bind-by-reference operator in a language with call-by-name function interface, though. Are the names to be forced through the bind or not? I think my original statement is correct no matter what else you add to the language, unless you break call-by-name. In any case, I was just trying to illuminate one aspect of the problem; you have added some more light to that. Who needs a universal swap macro anyway?
rbj@icst-cmr.ARPA (Root Boy Jim) (07/05/86)
Previously I wrote: Call by reference went something like this: the calling routine would pass the string representation of the argument and the caller would parse it to figure out the argument. Oops! I meant Call By Name. I seem to have proven one of Murphy's Laws, addressing it to my old prof. We all know what call by reference is. The rest of this article is a response to Chris Torek. From: Doug Gwyn (VLD/VMB) <seismo!BRL.ARPA!gwyn> No, you just implemented an elaborate form of "call by reference". > I merely chose a poor example. Call by reference and call by name > often have identical effects. That doesn't mean they are the same. In fact, call by {value,reference} have the same effect if one does not modify the arguments. > See my followup for a better example. > (Incidentally, my expression `example', contained in a comment, > has a different problem: it returns the address of a stack variable > that is no longer active by the time the caller uses it. `t' should > have been declared `static'. This is what comes of dashing off an > article just before bed . . . .) You mean you wrote this at noon? :-) > It is possible to implement full call by name in C, but it is difficult, I was going to say no, but you need one thunk for each argument you pass. The distinguishing characteristic about call by name is that you evaluate your argument every time you use it. Thunks seem to qualify. > for nonlocal reference is difficult; and no one ever > used call by name after Algol anyway---most likely because everyone > thinks it is terrible. Nonlocal reference *is* possible, but > probably best left to a compiler. Kludges are not too hard to > write, but are error-prone: the programmer must keep track of the > lexical level of each routine, and know how many levels up to look, > and at what offset, for each nonlocal variable. I would dispute that no one uses call by name. Consider that in APL you can pass a character string and execute it to get the result. I suppose I am splitting hairs, but the effect is the same. I imagine one could do the same thing in LISP, or any interpretive language. > Call by value-result is also easy enough in C, though as with call > by reference, it requires cooperation of both caller and callee: I was thinking of the caller squirrelling away the value in a temporary location, passing it by reference (thus allowing modification by the callee) and then copying the result to the real variable. As the fortune program says, "A fifth theory is held by idiots, but it is doubtful whether they know anything more than the others do". Which brings me to Univac's PLUS compiler. It stored its arguments directly into the callee's statically declared variables and grabbed the results after the callee returned. Ask zben@umd[25] about this if you care. (Root Boy) Jim Cottrell <rbj@icst-cmr.arpa> I'd like MY data-base JULIENNED and stir-fried! P.S. Zippy whipped up this saying just for Chris :-)
chris@maryland.ARPA (Chris Torek) (07/05/86)
From: Root Boy Jim <rbj@icst-cmr.arpa> > I merely chose a poor example. Call by reference and call > by name often have identical effects. [me] That doesn't mean they are the same. [rbj] That was my point. They are not the same, except in a particular set of cases. That is why (and when) it is important to know what methods of parameter passing are legal in whatever language you are using. I would dispute that no one uses call by name. Consider that in APL you can pass a character string and execute it to get the result. I suppose I am splitting hairs, but the effect is the same. I imagine one could do the same thing in LISP, or any interpretive language. Actually, this is a good point. In Lisp, a fexpr is in fact a sort of call-by-name, though depending on your scope rules it may do something very unexpected: evaluating `v' in the callee may provide the callee's `v', rather than the caller's. This is a particularly nasty problem in Gosling Emacs MLisp, where all MLisp `arguments' are in fact fexpr's. However, I stand by my statement, at least with a little modification: no one wants to be forced to use call by name exclusively. (Not that other methods are not available in Algol.) And I understand taht Common Lisp does not have fexpr's. ~> call by value-result I was thinking of the caller squirrelling away the value in a temporary location, passing it by reference (thus allowing modification by the callee) and then copying the result to the real variable. That works too---which just goes to show that there is more than one way to skin a function. `A swap, by any call by name, would smell as sweet ....' `You can call me Ref, or you can call me Val, ....' -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1516) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
basili@maryland.ARPA (Victor R. Basili) (07/05/86)
Thanks for letting me in on the discussion. I haven't read the interchange carefully but I am delight that there is cause for an intellictual debate. It only proves that we all continue to learn - Thank God! Vic Basili
zben@umd5.UUCP (Ben Cranston) (07/07/86)
In article <1964@brl-smoke.ARPA> rbj@icst-cmr.ARPA (Root Boy Jim) writes: ... > I was thinking of the caller squirrelling away the value in a temporary > location, passing it by reference (thus allowing modification by the > callee) and then copying the result to the real variable. Of course the difference between this and real call-by-name comes when the subroutine has an alternate access to the global in question - perhaps because of scoping rules, or access to a pointer-to-it or something. In real call-by-name the data item would change as soon as the parameter is modified by the subroutine. In the proposed scheme the transfer does not take place until the subroutine returns. > ... Univac's PLUS compiler. It stored its arguments directly > into the callee's statically declared variables and grabbed the results > after the callee returned. Ask zben@umd[25] about this if you care. Well, since Plus was to be written in Plus there was the old bootstrap problem. The solution taken was to hack beat and fiddle an existing Jovial [1] compiler to be the Plus compiler. The stuff-into-callee's static-data-area scheme Jim refers to was inherited from the old code. He's also been away from things awhile - Plus Plus (the second generation compiler) has been here for years now, and it uses a slightly more conventional scheme - the arguments are built on the end of the data stack and in the process of calling the subroutine the stack pointer is pushed just enough to make the arguments the first N locals of the called routine. Perhaps my usage of "stack pointer" is unusual here - the 1100 does not have any builtin stack so stacks must be implemented with index registers. What I called "stack pointer" here is what many people call "frame pointer". [1] Jules schwartz's Own Version of the International Algebraic Language Or some YABA [2] like that... [2] Yet Another (questioned parentage) ALGOL... Cheers -- umd5.UUCP <= {seismo!umcp-cs,ihnp4!rlgvax}!cvl!umd5!zben Ben Cranston zben @ umd2.UMD.EDU Kingdom of Merryland Sperrows 1100/92 umd2.BITNET "via HASP with RSCS"
chris@umcp-cs.UUCP (Chris Torek) (07/07/86)
>In article <1964@brl-smoke.ARPA> rbj@icst-cmr.ARPA (Root Boy Jim) writes: >>I was thinking of the caller squirrelling away the value in a temporary >>location, passing it by reference (thus allowing modification by the >>callee) and then copying the result to the real variable. In article <1060@umd5.UUCP> zben@umd5.UUCP (Ben Cranston) replies: >Of course the difference between this and real call-by-name comes when >the subroutine has an alternate access to the global in question - perhaps >because of scoping rules, or access to a pointer-to-it or something. Careful, Ben: this was under a section about call by value-result, and it does accomplish that quite handily. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1516) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
throopw@dg_rtp.UUCP (Wayne Throop) (07/07/86)
> gwyn@BRL.ARPA (VLD/VMB) > I'm not sure how one would implement a bind-by-reference > operator in a language with call-by-name function interface, > though. Relatively simple. It implies that the bind-by-reference operator must not be a function, but this is no stranger than allowing a bind-by-reference operation in C, where function arguments are bind-by-value. > Are the names to be forced through the bind or not? > I think my original statement is correct no matter what else > you add to the language, unless you break call-by-name. I seem to have been unclear. The bind-by-reference operator would not affect the way values are passed to functions. It would be an operator that could be applied to (perhaps) any expression. In a language with lisp-like syntax but with call-by-name, we might implement swap something like so: (define-function swap (a b) (declare t) (bind-by-reference ((a-alias a) (b-alias b)) (assign t a-alias) (assign a-alias b-alias) (assign b-alias t) ) ) "define-function", "declare" and "bind-by-reference" must be special forms, but "assign" and "swap" can be functions. The bind-by-reference form coins new names, which, when evaluated, always yield the same instance. Thus, swap only mentions "a" and "b" once. I have glossed over detail (what type is "t", for example?), but I hope everybody can see how this would work. Casting it in C, it might work something like this: void swap( a, b ) int *(*a)(), *(*b)(); { int t, *a_alias = (*a)(), *b_alias = (*b)(); t = *a_alias; *a_alias = *b_alias; *b_alias = t; } Of course, to be exactly proper, t, a_alias, and b_alias ought to be of type (int *(*)()) also. The t function would always return an address in swap's local frame, a_alias would always return what a returned at bind-time, and so on. Can be done, but makes the function a *lot* uglier. I'll leave that as an excersize for the masochistic. > In any case, I was just trying to illuminate one aspect of > the problem; you have added some more light to that. Who > needs a universal swap macro anyway? Well, the "weak form" of your original point (the meaning of "swap" in the presense of by-name binding is a real problem) is still quite valid. I just was trying to point out that implicit by-name binding doesn't mean that the language can't provide explicit by-reference binding. Just as in C, the fact that the language binds by-value implicitly, doesn't mean that one can't bind by-reference or by-name explicitly. And I don't know who needs a universal swap macro. I guess I view these "devise a swap such that..." challenges as finger excersizes. -- It is possible by ingenuity and at the expense of clarity ... [to do almost anything in any language]. However, the fact that it is possible to push a pea up a mountain with your nose does not mean that this is a sensible way of getting it there. --- Christopher Strachey -- Wayne Throop <the-known-world>!mcnc!rti-sel!dg_rtp!throopw
zben@umd5.UUCP (Ben Cranston) (07/08/86)
In article <1964@brl-smoke.ARPA> rbj@icst-cmr.ARPA (Root Boy Jim) writes: > I was thinking of the caller squirrelling away the value in a temporary > location, passing it by reference (thus allowing modification by the > callee) and then copying the result to the real variable. In article <1060@umd5.UUCP> zben@umd5.UUCP (Ben Cranston) replies: > Of course the difference between this and real call-by-name comes when > the subroutine has an alternate access to the global in question - perhaps > because of scoping rules, or access to a pointer-to-it or something. In article <2293@umcp-cs.UUCP> chris@maryland.UUCP (Chris Torek) cautions: > Careful, Ben: this was under a section about call by value-result, > and it does accomplish that quite handily. Er, yeah. Another difference between call-by-name and value-result comes when the actual is subscripted like a[i] and different array indices can be selected on each reference to the formal (assuming i modified). This would have been a better example than the one I actually gave. No criticism of you or Root Boy was meant, I was only adding information. Your point that I should have reviewed the entire discussion before posting is well taken. -- umd5.UUCP <= {seismo!umcp-cs,ihnp4!rlgvax}!cvl!umd5!zben Ben Cranston zben @ umd2.UMD.EDU Kingdom of Merryland Sperrows 1100/92 umd2.BITNET "via HASP with RSCS"
rbj@icst-cmr.ARPA (Root Boy Jim) (07/09/86)
> ~> call by value-result > > I was thinking of the caller squirrelling away the value > in a temporary location, passing it by reference (thus > allowing modification by the callee) and then copying the > result to the real variable. [me] > > That works too---which just goes to show that there is more than > one way to skin a function. [chris@maryland (as in Torek)] Changing the subject a bit here, I am referencing Wayne Throop's article on taking the address of a register variable, where he quotes H&S (how about that folks, they're mainstream enuf to be ref'ed like K&R). I have said all along that there is no reason why a compiler can't perform the following transformation: LEGAL DESIRED foo() foo() { register int j; { register int j; auto int k; k = j; bar(&k); bar(&j); j = k; } } Sort of a Call by Value-Result, eh? As H&S notes, some machines have registers that really *are* addressable, so this does provide something that is missing, and is not just syntactic sugaring. Even if it were, look at all the language implementation chatter we have removed. Just let the user say what he means. I agree with H&S that the syntax `ought' not to be illegal, but go the other way with the fix. They wish to ignore the register declaration making the variable auto, whereas I wish to simulate register addressibility. Consider a function which uses a register variable heavily in three or four loops. Now consider modifying the code to include a call to one that wants the address of a variable. Oops! All too often the fix is to change the register declaration to auto rather than add the extra variable and two assignments. Down the drain goes performance. (Root Boy) Jim Cottrell <rbj@icst-cmr.arpa> Yow! Is my fallout shelter termite proof?