Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.misc
Subject: Re: Algol68 (and standards diatribe)
Message-ID: <5809@goanna.cs.rmit.oz.au>
Date: 17 May 91 10:04:55 GMT
References: <1991Mar28.011025.16337@ico.isc.com> <2400047@otter.hpl.hp.com> <1991May15.181833.19502@maths.nott.ac.uk>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 78

In article <1991May15.181833.19502@maths.nott.ac.uk>, anw@maths.nott.ac.uk (Dr A. N. Walker) writes:
> 	From time immemorial, whatever the equivalent of
> 
> 		BEGIN REAL x; ... END
> 
> is in your favourite Algol-based language has meant something like
> 
> 		start a new stack frame, allocate some *local* space for a
> 		real variable identified by "x", ..., deallocate the space
> 		and close the frame.
> 
Let me rephrase that.  The outcome you describe results from the
interaction of two rules:

(1) BEGIN REAL x; ... END
    opens a new environment extending its lexically enclosing environment
    allocates some space 
    adds a binding (x->the new space) to the new environment
    ...
    closes the environment
(2) Space is reclaimed when the last reference to it goes away.

Algol 60, Pascal, and (I think) Algol W had no way of creating a
reference to a variable that would outlast the environment.

However, "since time immemorial", the lambda calculus has permitted the
capture of outer variables in results:
	(\x. \y. + y x)(3)
returns a function equivalent to \y. + y 3.

Remember that the Algol 68 statement
	( REAL x = 3.2 ; ... )
need not (and in actual implementations may well not) allocate ANY
storage for x.  What goes in the environment is a _binding_ not a
storage location per se.

The thing is that in Common Lisp, Scheme, ML, Haskell, and so on,
*both* the rules above are fully obeyed, *but* they have means for
creating values that can outlast the environment.

It is possible to sort the bindings in a frame so that the first
binding to become "dead" is at the far end, the next binding to
become "dead" is just below it, ... so that space can be reclaimed
from a stack frame _before_ the procedure/block/what-have-you is
exited.  This is standard practice in Prolog compilers, for example,
in order to try to minimize stack size.  What is criterial is not
"is this the end of the scope", but "have we passed the last use
of the variable".

> 	Arguably, but I don't think so.  Composition is a reasonable
> thing to want, but using a variable out of scope isn't.

Example:
    BEGIN
	REAL x;
	PROCEDURE store x(y); x := y; 
	REAL PROCEDURE fetch x; fetch x := x;
	...
	BEGIN
	    INTEGER x;
	    ...
	    store x(2.0);
	    ...
	    store x(fetch x + 1.0);
	END;
	...
    END
If the dots are filled in correctly, this can become a legal Algol 60
program (no, you did _not_ have to declare arguments in Algol 60, and
yes, spaces _were_ legal inside identifiers).  Here the inner block
is using the variable x at a point where its name isn't visible.  All
that going out of scope means is that the name becomes invisible and
remains invisible.  Why is it ok to continue to use a variable in one
case but not the other; why is not having a visible name venial in one
case but deadly in the other?

-- 
There is no such thing as a balanced ecology; ecosystems are chaotic.