Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cwjcc!gatech!purdue!mentor.cc.purdue.edu!pur-ee!hankd
From: hankd@pur-ee.UUCP (Hank Dietz)
Newsgroups: comp.lang.misc
Subject: Re: swap(x,y) in Algol 60
Summary: Does Algol 60 have address-of?
Keywords: swap, algol
Message-ID: <12768@pur-ee.UUCP>
Date: 4 Sep 89 22:16:14 GMT
References: <31690@cornell.UUCP> <31728@cornell.UUCP>
Reply-To: hankd@pur-ee.UUCP (Hank Dietz)
Organization: Purdue University Engineering Computer Network
Lines: 40

In article <31728@cornell.UUCP> samuel@cs.cornell.edu (Samuel M. Weber) writes:
>In article <31690@cornell.UUCP> bard@cs.cornell.edu (Bard Bloom) writes:
>>I have seen a folk theorem that it is impossible to define swap(x,y) in
>>Algol, where swap is supposed to be a procedure with two call-by-name integer
>>arguments which exchanges their values.
>>
>>I've asked around MIT and some at Cornell, and nobody seems to have a
>>reference to the statement or proof.  Anyone remember where this came from?
>
>On page 428 of the new Dragon book it says "A correctly working version
>of swap apparently cannot be written if call-by-name is used.", and
>references Fleck, A. C. "The impossibility of content exchange through
>the by-name parameter transmission technique." SIGPLAN Notices 11:11
>(November 1976)
>
>    -- Sam Weber
>       samuel@cs.cornell.edu


Call by name in Algol is call by thunk:  the address of a routine to
evaluate the lvalue of each argument is passed.  Hence, using the notation
of C (but assuming call by thunk):

swap(a, b)
int a, b;
{
	int *p = &a;	/* a's side-effect occurs */
	int *q = &b;	/* b's side-effect occurs */
	int t = *p;
	*p = *q;
	*q = t;
}

Would do a swap invoking side-effects exactly once for each argument (and in
a specified order).  Call by thunk only prohibits writing a swap function if
your language doesn't support an lvalue operator, such as C's "&" address-of.
I don't recall if Algol has such an operator or not, but certainly the fact
that call by name is used does not prevent it.

							-hankd@ecn.purdue.edu