From: mash@mash.engr.sgi.com (John R. Mashey)
Newsgroups: comp.lang.c++,comp.sys.unisys,comp.arch
Subject: Re: call by name
Date: 26 Jun 1995 21:52:44 GMT
Organization: Silicon Graphics, Inc.

In article <9517616.19875@mulga.cs.mu.OZ.AU>, conway@munta.cs.mu.OZ.AU
(Thomas Charles CONWAY) writes:

|> #define foo(x, y)	do { \
|> 	some stuff using x and y
|> 	} while (0)

|> 
|> You're telling me that C macros are not call by name? Sure, they're
|> limited in their application (they cannot be properly recursive for
|> instance), but they still use call by name.

C macros are *not* call-by-name, but just (relatively simple) textual
substitutions with none of the effects of the (various) Algol
call-by-names in potentially importing into a procedure references to
names declared outside.  [See for example: "Programming Languages and
Systems, Saul Rosen, ed., McGraw-Hill, 1967, p.73-77.]
I.e., call-by-name:
	a) Can require some very different semantic effects.
	b) Can strongly induce thunks (or equivalents) in implementation.

While call-by-name can sometimes allow some elegant expressions of
algorithms, I think it fits into a certain category of features:

a) The feature is the default [i.e., call-by-name, unless you explicitly
said call-by-value].
b) The feature is very general, with unanticipated complexities in
interpretation (recall that changes occurred betweeen the 1960 and 1963
ALGOL reports, for example).
c) The feature's generality is actually not often used, but implementations
may get very complicated to deal with the weirder cases.

Such features show up in many places:
1) Consider the difference between FORTRAN and C with regard to aliasing
of pointers to arguments: FORTRAN says they don't, C says they can;
the former choice is easier to optimize code for; one would prefer a
default that says "no parameters aliased unless so declared".

2) In computer architectures, offering the very general concatenations
of addressing modes (a la VAX or MC68020) that can require the handling
of very long instructions ... despite the statistically low rate of such
usage.

|> Do the particular set of tradeoffs used by
|> the current generation of processors imply particular
|> implementation strategies? (For instance, thunks have been
|> implemented by having the application construct a short
|> code sequence at runtime, and then at some later time
|> execute it. With a split cache this could have bad consequences)

CPU designers *really* do not want to be required to implicitly
synchronize I-cache with D-cache on a near-instantaneous basis.
Sometimes you may get away with it, but if you *ever* allow the
following code to be legal:

	ST	reg,label
label:	???

you are going to add gates to many potential implementations ... even those
with no caches [because there may well be pre-fetch buffers...]

For this reason, most archiecture+software combinations started in recent
years require *some* explicit notification by the program that it thinks
it is modifying code dynamically, and that doing so without notifying
the hardware/OS is undefined.	

-- 
-john mashey    DISCLAIMER: <generic disclaimer, I speak for me only, etc>
UUCP:    mash@sgi.com 
DDD:    415-390-3090	FAX: 415-967-8496
USPS:   Silicon Graphics 6L-005, 2011 N. Shoreline Blvd, Mountain View, CA 94039-7311

From: mash@mash.engr.sgi.com (John R. Mashey)
Newsgroups: comp.lang.c++,comp.sys.unisys,comp.arch
Subject: Re: C++: CDC6600 vs B5500, RISC vs CISC (attn Peter Juhl)
Date: 19 May 1995 21:13:29 GMT
Organization: Silicon Graphics, Inc.

In article <D8syEH.Dx4@cwi.nl>, dik@cwi.nl (Dik T. Winter) writes:
(me:)
|>  > The B5xxx (in my opinion) was a brilliant and elegant design, with many
|>  > fine ideas; it actually had practical hardware for running Algol-like
|>  > languages, which was non-trivial, and getting good performance from them
|>  > without current optimization technology.
(Dik):
|> I doubt it.  The design was indeed brilliant and elegant, but not
|> unprecedented (see for instance the KDF-9).  But I doubt whether stack
|> architectures are indeed particulary suited for Algol-like languages.

I don't think we disagree on some of that [I didn't say unprecedented :-)],
but let me explain more.  People may recall that Algol60 used "call by
name" ... which was "non-trivial" to execute efficiently on most
machines (which is why many commonly-used languages use call-by-reference
or call-by-value or value-result).  The "practical hardware" above had
little to do with being a stack machine, but with the hardware
implementation of decriptors that otherwise required many instructions on
other systems [I once looked at IBM S/360 ALGOL-generated code, and once
was enough - it was hard.]  To put it simply, bringing a value to the
top of a stack wasn't just a "LOAD" or "MOV" instruction, it was
OPDC (Operand Call), whose description required half a dozen pages.
But specifically, if you did:
	OPDC	simple-value		=> load simple value
	OPDC	subroutine-descriptor	=> invoke the subroutine, which
					would leave value on top of stack,
					just like it had been a simple value

That is, when compiling code for a function, you could generate a
simple OPDC aimed at an incoming parameter, and it would work without
a bunch of checking to see if it was a simple value or a thunk of
code implementing an expression that should be re-evaluated each time it
was referenced.  Of course, call-by-name seems to have mostly
disappeared from common use, by now.



-john mashey    DISCLAIMER: <generic disclaimer, I speak for me only, etc>
UUCP:    mash@sgi.com 
DDD:    415-390-3090	FAX: 415-967-8496
USPS:   Silicon Graphics 6L-005, 2011 N. Shoreline Blvd, Mountain View, CA 94039-7311

From: corbett@lupa.eng.sun.com (Robert Corbett)
Newsgroups: comp.std.c
Subject: Re: Why does indexing begin at 0
Date: 2 Jul 1999 01:20:42 GMT

In article <19990701003605.06502.00005900@ng-fo1.aol.com>,
Wclodius <wclodius@aol.com> wrote:
>
>>BTW, I doubt that the authors of the Algol 60 Report meant to specify
>>call-by-reference.  The notion of call-by-name is solidly established
>>in combinatory logic.  Combinatory logic was popular in the 1950s and
>>1960s.  I suspect that the authors did not understand how complex the
>>implementations would be.
>
>You may doubt it, but several of the authors are on record that call by name
>was intended to describe call by reference.  I don't recall at the moment
>whether the point is discussed in the most obvious reference, the Algol 60
>section of proceedings of the first conference on "The History of Programming
>Languages", edited by Wexelblat. However, the topic has arisen several times in
>comp.compilers and other references can be found there.
>
>William B. Clodius

I would love to see a citation on this point.  The difference between
call-by-name and call-by-reference seems so obvious, I find it hard to
believe the authors of the Algol 60 Report could have made such a mistake,
but I am prepared to change my mind given evidence to the contrary.

					Sincerely,
					Bob Corbett

From: wclodius@aol.com (Wclodius)
Newsgroups: comp.std.c
Subject: Re: Why does indexing begin at 0
Date: 02 Jul 1999 04:26:50 GMT

>I would love to see a citation on this point.  The difference between
>call-by-name and call-by-reference seems so obvious, I find it hard to
>believe the authors of the Algol 60 Report could have made such a mistake,
>but I am prepared to change my mind given evidence to the contrary.

As I noted the topic  has arisen in the comp.compilers newsgroup.

John Levine, the moderator, was a student of Perlis, one of the eight member of
the Algol 58/60 committee. Levine claims that Perlis told him several times
that the committee adopted call by name because they thought it described call
by reference.

On the other hand, apparently Naur in later years said that that he was aware
of the distinction at the time of the first Algol 60 report. Whether he was
aware of the full implications of the distinction, or was aware of the
distinction at the first few such meetings is less clear.

I can imagine one of the members proposing call by name as a way of describing
call by reference without resorting to a machine model at an early meeeting,
others acceepting without having time to examine the consequences, recognizing
the consequences between meetings, and not making a major issue of the
distinction because it did not seem important for Algol's primary purpose which
was the description of algorithm's in papers, and not as the implementation of
algorithms.

William B. Clodius

From: Dennis Ritchie <dmr@bell-labs.com>
Newsgroups: comp.std.c
Subject: Re: Why does indexing begin at 0
Date: Fri, 02 Jul 1999 07:18:54 +0100

Wclodius wrote, first quoting Corbett:
>
> >I would love to see a citation on this point.  The difference between
> >call-by-name and call-by-reference seems so obvious, I find it hard to
> >believe the authors of the Algol 60 Report could have made such a mistake,
> >but I am prepared to change my mind given evidence to the contrary.
>
 ...
> On the other hand, apparently Naur in later years said that that he was aware
> of the distinction at the time of the first Algol 60 report. Whether he was
> aware of the full implications of the distinction, or was aware of the
> distinction at the first few such meetings is less clear.
>
> I can imagine one of the members proposing call by name as a way of describing
> call by reference without resorting to a machine model at an early meeeting,
> others acceepting without having time to examine the consequences, recognizing
> the consequences between meetings, and not making a major issue of the
> distinction because it did not seem important for Algol's primary purpose which
> was the description of algorithm's in papers, and not as the implementation of
> algorithms.

The papers and discussions in the HOPL I book's section on Algol are,
for the most part, surprisingly uninformative, or at best
allusive, on the subject.  Naur does say (I'm condensing considerably)--

 "On the one hand, the ALGOL 58 report very clearly has a paragraph
 talking about replacement: that is, at call time, the formal parameter
 is supposed to be replaced, literally, as a substitution of text, by the
 actual parameter....

 [huge snip, skipping over meetings and letters ca. 1959] "Something else
 had to be done, and finally the meeting had a subcommittee...which, on
 the very last meeting of the meeting when everyone was really exhausted,
 came along with a proposal.... This seemed to be all right, until I woke
 up the next morning and decided it wasn't.  I could not understand it,
 and I was supposed to report on it, you see.  So I sent out a letter to
 every member that something had to be done.  This was clarified very
 adequately by Perlis, and actually later careful studies of notes by
 Mike Woodger...show that what he clarified was perfectly what had been
 proposed during the meeting, but I would say not clearly, not fully
 understood by the committee.  The whole thing took place under the great
 pressure of time and other issues, of course....

 "Well, this is the way the concept came in....There are certain
 desirable consequences of the parameters called by name, that is,
 desirable flexibility....  This is what is now called the Jensen Device.
 And for that reason I thought that there would be general agreement that
 call by name would be a good concept."

I would have to quote a lot more to give the real flavor of what the
disagreements and controversies actually were.  In particular, recursive
functions seem to have generated far more anguish than one would have
expected.  But I don't think the Algol committee created their
concept of call-by-name under the misapprehension that it was
call by reference and the words somehow came out wrong in the report.

	Dennis