Re: Jensen's device

Uday S. Reddy wrote:
> One of the guiding principles of the Algol committee was to define
> the language at a high-level without involving any implementation
> concepts such as memory locations, addresses, pointers etc.


Possibly. But this does not appear in any of the Reports,
as far as I can see. The nearest to it in Algol 60 is to do with
the character set for the reference language:


The characters are determined by ease of mutual understanding
and not by any computer limitation, coders [sic] notation, or
pure mathematical notation.


For IAL [Algol 58], I can find only the same statement about the
reference language as above, and also Objective III:


The new language should be mechanically translatable into
machine programs.


By contrast, Algol 68 has quite a lot to say in these areas:


0.1.b ALGOL 68 is designed to communicate algorithms, to execute
them efficiently on a variety of different computers, and
to aid in teaching them to students.
0.1.c ... The Working Group has tried to ... balance ...
experience ... [and] the needs of ... implementation, ....
0.1.4 ALGOL 68 allows the programmer to specify programs which
can be run efficiently on present-day computers and yet do
not require sophisticated ... optimisation ....
0.2.3 ... Whereas ALGOL 60 ... implies a "stack"-oriented storage-
allocation scheme, ... ALGOL 68 provides, in addition, ...
the "heap", ....
0.2.5 ... "environment enquiries" ... make it possible to
determine certain properties of the implementation, ....
0.4.4.b A model of the hypothetical computer much more closely
related to a real one has been introduced. ....


> Giving such a
> high-level description of call-by-reference is quite a challenge. In
> fact, this challenge has been met only recently when Standard ML was
> defined. (Algol 68 tried to do it too, but their descriptions are too
> complicated for mere mortals to understand.)


Really? Section 5.4.3.2.b of the Revised Report:


The yield W of the "calling" of a routine R in an environ E1,
possibly with [parameter] values V1, ..., Vn is determined as
follows:
* let E2 be the environ established upon E1, around the
environ of R, according to the declarative of the declarative-
pack, if any, of the routine-text of R, with the values V1,
..., Vn, if any;
* W is the yield in E2 of the unit of the routine-text of R.


The establishment of environs is the only "complicated" bit there; the
rest of it simply says that you get whatever happens when you run R in
the correct environment. But the environment of a procedure *is* an
intrinsically complicated matter, and it is rather easier in Algol 68
than in Algol 60 [where the environment of the parameters needs to be
"retained" so that the "thunks" can be evaluated whenever necessary],
as the actual parameters are, conceptually, used only outside the
procedure.


Indeed, the explanatory matter to 5.4.3.2.b includes the same
"samelson" procedure that proved that Jensen's device was familiar to
the authors of the Algol 60 Report and shows how "call by reference"
[at least in the Algol 68 sense] is virtually equivalent to the
concept of "identity declaration", ie the bog-standard declaration of
almost every programming language before or since.


> A second issue the committee must have faced is to find a uniform
> mechanism for parameter passing that applies to all kinds of
> parameters.


Well, not really, or they wouldn't have come up with the
"botch" of having two kinds of parameters ["value" or default], and
then having to add all sorts of warnings [4.7.5] about what happens to
strings, switches, arrays and procedures. They seem to have tried to
minimise the syntax, but not to make the mechanism uniform.


> Call-by-reference is something that applies to variable
> parameters. But, what about, say procedure parameters? Is there such
> a thing called a "reference" to a procedure?


Well, not in Algol 60 [which makes it slightly awkward that
procedures are almost always passed by name rather than by value]. In
Algol 68, the uniform "identity" mechanism makes this problem moot.


> It must have appeared to the committee that call-by-name was the
> *simplest* solution. They probably ensured before writing the report
> that call-by-name was implementable. But, they probably didn't have a
> very good idea of what it would cost.


This is safer ground. As late as the mid-60s, I was being
told "No-one writes programs in Algol, that's just for publishing
algorithms. Use Atlas Autocode for Real Programs."


> The simplicity of call-by-name is still a reality.


But the Algol 68 style is even more simple, and ...


> The theory of
> call-by-value (and call-by-reference) lags behind that of call-by-name
> by decades [...]


... has had a complete theory for nearly 30 years now!
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk
--

Return to the comp.compilers page.
Search the comp.compilers archives again.