anw@maths.nott.ac.uk (Dr A. N. Walker) (05/13/91)
In article <1991May10.162820.2662@maths.nott.ac.uk> I wrote [re a delivered procedure in Algol using a scoped variable "x"] > You could always declare "HEAP REAL x" to give "x" global scope, >and then your procedure would work anywhere, I shouldn't post on Friday afternoons! I started to have nagging doubts as I drove home, wondering how to do garbage collection efficiently. My copy of the Report is on loan elsewhere, but assuming that Lindsey and van der Meulen are right [and they usually are], the procedure is indeed scoped by the range of "x", not the scope of "x". Thus, the above is not true, and Steve Knight had a point. This is still not unorthogonal (*all* procedures are scoped this way, there is nothing special about procedures being returned as results), but it is certainly unobvious. -- Andy Walker, Maths Dept., Nott'm Univ., UK. anw@maths.nott.ac.uk
thorinn@diku.dk (Lars Henrik Mathiesen) (05/15/91)
anw@maths.nott.ac.uk (Dr A. N. Walker) writes: >In article <1991May10.162820.2662@maths.nott.ac.uk> I wrote > [re a delivered procedure in Algol using a scoped variable "x"] >> You could always declare "HEAP REAL x" to give "x" global scope, >>and then your procedure would work anywhere, > I shouldn't post on Friday afternoons! I started to have nagging >doubts as I drove home, wondering how to do garbage collection efficiently. >My copy of the Report is on loan elsewhere, but assuming that Lindsey and >van der Meulen are right [and they usually are], the procedure is indeed >scoped by the range of "x", not the scope of "x". Thus, the above is not >true, and Steve Knight had a point. You should never let your Revised Report out of sight :-). However, you (and L&vdM) are right. The environs of Algol68 map very well to a stack model, where each environ is built "upon" another (its dynamic link) and "around" a third (its static link). By 7.2.2.c, to find the environ "necessary for" a routine text (or mode definition) C you follow the static links until you reach one that defines a tag used but not defined in C. I think this rule is forced not just by garbage collection, but by code generation issues in general: Even though the value ascribed to a tag has global scope, the implementation must still store that value in a 'stack slot'. Under the existing rule, the code generated for a routine can just follow static links to get at non-local values, and a value of mode PROCEDURE can just be a code address and a static link. If the rule was to be relaxed, Algol68 would in effect have closures (environment, not parameter): In general, the value yielded by a routine text must somehow contain the values of all non-local tags mentioned in it, without referring to the _current_ stack. In a implementation with support for parallelism (and thus multiple stacks) this might not be hard, but I can see why the committe decided not to demand it (if indeed they thought about it?). >This is still not unorthogonal (*all* >procedures are scoped this way, there is nothing special about procedures >being returned as results), but it is certainly unobvious. See also 2.1.1.3.b: {The scope of an environ is not to be confused with the scope of the values accessed inside its locale. ... } Even so, most of the time a tag is 'associated' only with the scope of the value it accesses, not of its defining environ. -- Lars Mathiesen, DIKU, U of Copenhagen, Denmark [uunet!]mcsun!diku!thorinn Institute of Datalogy -- we're scientists, not engineers. thorinn@diku.dk
mct@praxis.co.uk (Martyn Thomas) (05/16/91)
thorinn@diku.dk (Lars Henrik Mathiesen), commenting on Algol 68's scope
rules for procedures, writes:
:If the rule was to be relaxed, Algol68 would in effect have closures
:(environment, not parameter): In general, the value yielded by a
:routine text must somehow contain the values of all non-local tags
:mentioned in it, without referring to the _current_ stack. In a
:implementation with support for parallelism (and thus multiple stacks)
:this might not be hard, but I can see why the committe decided not to
:demand it (if indeed they thought about it?).
The rule *was* relaxed in the Algol 68 implementation for the FLEX machine
(a microcoded capability architecture, developed at RSRE, Malvern, UK, and
used for general software development for meny years). FLEX had hardware
garbage collection and unforgeable references. Making procedures into
first-class values apparently led to a very natural and powerful programming
style.
Score another point for RSRE (and for Ian Currie in particular).
--
Martyn Thomas, Praxis plc, 20 Manvers Street, Bath BA1 1PX UK.
Tel: +44-225-444700. Email: mct@praxis.co.ukkers@hplb.hpl.hp.com (Chris Dollin) (05/17/91)
Dr A. N. Walker says: In article <KERS.91May13165106@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: >Dr A. N. Walker responds to Steve Knight: [much deleted] > If you want your procedure to > work, you mustn't tell the computer to throw away "x" first! But this > seems to be what Steve wants. Or have I misunderstood something? > >This is what Steve wants; he *hasn't* told the computer to throw anything > away. Yes he has! >Just because x would go out of (lexical) scope need not mean that its >store has to be reclaimed. 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. We have a difference of opinion here. *I'd* say that the (equivalent of) the above code means ``once you hit END, I no longer wish to be able to use the name "x" to refer to ... er ... whatever it did refer to (ie, the variable, or the location, or the value, etc)''. The stuff about stack frames is just an implementation technique which works very well so long as you can't export some sort of reference to (the item named by) x - as was the case in Algol 60, but not in Algol 68. We can argue about what languages are ``Algol-based'', and quite when ``time immemorial'' started and finished, but above description does not apply to ML, or PAL, or SASL (or KRC, or Miranda), or Scheme, or Common Lisp. Dr. Walker continues (quoting me again): >Isn't the latter (weakness of A68 functional composition) just a > consequence of the former (can't export a procedure outside the scope of > one of its free variables)? Arguably, but I don't think so. Composition is a reasonable thing to want, but using a variable out of scope isn't. (Note: "scope" in Algol is a technical term, and differs from "range", which seems to be what some contributors mean by "lexical scope".) Reasonable wants shouldn't be satisfied in unreasonable ways. Yes, it occured to me that there was a terminological problem, and that Algol68 (for some arcane reason) used ``scope'' to mean what was usually called ``extent'' if it was called anything, and then had to introduce a new word to mean what ``scope'' meant. (Clearly, you *cannot* use something that's gone ``out of scope'' in the Algol68 sense - it ain't there. But I think the other contributors mean ``lexical scope'', aka ``range'', by scope. Certainly that's what Steve means [the observant reader will note that we post from the same site, and in fact we regularly discuss issues such as this, so I have a fair idea of what he means!]. It is true if you try to write composition in the obvious way the result has a uselessly narrow scope. The partial parametrisation proposals [see Algol Bulletin #37, p24] get around this without putting unreasonable loads on the implementation, but within the spirit of the scope rules. This possibility shows that composition weaknesses aren't a necessary consequence of tight scope rules. If you can implement partial parameterisation, you can implement full lexcial scope (ie, indefinite scope for locals used in exported procedures) using it. [Proof by example: that's how Poplog Pop11 does lexical closures.] Hence there's no reason not to make (eg) composition have full Algol68-scope if you have partial parameterisation. -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
kers@hplb.hpl.hp.com (Chris Dollin) (05/23/91)
Dr A. N. Walker continues the debate: [Quoting O'Keefe] In article <5809@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >(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. Well, I've just checked several of my old texts on Algol 60, and I haven't found anything that even remotely resembles that. ("Binding"? "Environment"? "Reference"?) I haven't found a text that distinguishes in any way, let alone adequately, between variables, the storage that they occupy, and the identifiers that identify them. Yes, that's likely; since Algol 60 didn't have any reference-type objects (certainly no programmer-allocated ones) that could be passed around, it was easy to confuse (lexical) scope with (dynamic) extent [lifetime - see below]. I checked my books on Pascal and C (and others) with similar lack of success. Plenty of stuff about how "x" can only be used between the "BEGIN ... END", about name hiding, sometimes about stacks. Even some of the books on Algol 68 are distinctly hazy about all this. [I'm pleased to say that Lindsey & van der Meulen and Brailsford & Walker both have explanations that still make sense to me, though I wouldn't have written either of them that way.] Pascal and C are similar to Algol 60 in this regard, except for ``new'' (Pascal) and ``malloc'' (C), where the allocated objects are not scope-controlled at all. Using a modern perspective in an attempt to describe what 20-30 year-old languages were thinking about is at best anachronistic, and almost certainly misleading. If it clarifies the issue, it's ok. (Hmm ... is that a pun?) It would indeed be a mistake to attribute the modern perspective to the designers of the languages of the time. >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. Irrelevant to the semantics of Algol-like languages. Maths has always been cavalier about scope and range of notation. Isn't the lambda-calculus precisely the part of mathematics that *did* have precise ideas about (lexical) scope? [some stuff omitted] In a related posting, <KERS.91May17090215@cdollin.hpl.hp.com>, kers@hplb.hpl.hp.com (Chris Dollin) writes: > *I'd* say that the (equivalent of) the >above code means ``once you hit END, I no longer wish to be able to use the >name "x" to refer to ... er ... whatever it did refer to (ie, the variable, >or the location, or the value, etc)''. Yes, I might say that too, but when [historically, this is not an attempt to discover your age!] would you *first* have said that? Before Algol 68, there was little distinction made between "x" the identifier and "x" the variable inside the computer [at least in the books I read]. You didn't read any books about compilers then? :-) I'll have to pass on this, because I'm not too sure of this historical detail. [Since you didn't ask, I'm 37. Crumbs, that means this year's my 20th Programming Anniversary!] Again judging from books on my shelves, few other authors of books on C, Pascal or other languages are as concise or as accurate as Dennis Ritchie. My conclusion is that the vast majority of authors, and hence of lecturers and students, and hence of practitioners, espouse a very simplistic view of scopes, lifetimes, extents, ranges, call them what you will. Contributors to c.l.m are self-selected to be (relatively) knowledgeable about such things. That's true, and regrettable, otherwise we might not need to have discussions like this (which I'm enjoying, and finding interesting, and I hope others are finding it educational; but I'd rather we didn't need to have it!). >Yes, it occured to me that there was a terminological problem, and that Algol68 >(for some arcane reason) used ``scope'' to mean what was usually called >``extent'' if it was called anything, and then had to introduce a new word to >mean what ``scope'' meant. I asked a few friends in the local CS Dept; none of them had any idea what I might mean by "extent". Mea culpa - I should have said ``lifetime'' (``extent'' was the Oxford word at the time I was their, but ``lifetime'' was the informal word.) Their definitions of "scope" were as garbled as you might expect from the above. They fared better when I asked about "lexical/dynamical scope". Like all surveys, it depends how you ask the question :-) - without some sort of context (eg ``variables in programming languages'') it wouldn't be clear what (kind of) scope; I think we've established that context here. Having been bitten once or twice in the early 70's, I have since tried [not always successfully] to use "scope", "range", "reach", "environ" and other technical words in the Algol sense, to explain [eg "range" == "lexical scope"] the notation when first used, and to be prepared to interpret other usages. That the notation is not more widely understood seems to me to be just another example of an Algol feature that was ahead of its time. I agree that it's right to have a variety of technical terms to cover the concepts, and that the Algol68 ones are fine - *except* that they didn't come into widespread use, and I believe, in the context, that ``scope'' will nowadays be taken to mean ``lexical scope'', unless (again given the context) it were taken to mean ``dynamic scope''. But then, I live a specialised life. > But I think the other >contributors mean ``lexical scope'', aka ``range'', by scope. Certainly that's >what Steve means [...] That's what I assumed Steve meant first time, and what he denied. Then I fear one of you must have misunderstood the other (the other possibility is too horrible to be contemplated). -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."