Path: utzoo!attcan!uunet!lll-winken!ames!oliveb!Ozona!chase From: chase@Ozona.orc.olivetti.com (David Chase) Newsgroups: comp.lang.modula2 Subject: Re: procedure variables Message-ID: <41110@oliveb.olivetti.com> Date: 27 Apr 89 21:27:44 GMT References: <784@gould.doc.ic.ac.uk> Sender: news@oliveb.olivetti.com Reply-To: chase@Ozona.UUCP (David Chase) Organization: Olivetti Research Center, Menlo Park, CA Lines: 128 In article Modula2 List writes: > Why not allow local procedures? [It's not easy; it's slow; LISP does it.] It's easy, if you just slap all the stack frames on the heap. It's only hard if you try to optimize them away, and if you believe the LISP (and other garbage-collected languages) literature, it's not *that* hard and it works pretty well. [see reference list 1] Other people make the claim that garbage collection, done right, is fast enough that it isn't worth the trouble to optimize away the heap-allocated frames. [see reference list 2] In article <784@gould.doc.ic.ac.uk> dcw@doc.ic.ac.uk (Duncan C White) writes: >This sounds very dangerous to me: it allows procedure B to examine and >modify the outer-scope variables of the defunct procedure A, even though >these variables cannot be accessed by anyone else! I cannot see the danger in this, really. I can imagine people writing some pretty squirrelly code, but that always seems to be possible. First-class functions let people write some really nice code, too. "We" (= me, plus unindicted co-conspirators) considered implementing first-class functions as a silent extension in a Modula-3 compiler, but VAR parameters cause real problems. One can obtain a pointer into the frame of a *caller* of an outer-scope procedure; this forces lots more frames to be heap-allocated, and makes it harder to optimize away heap-allocated frames. As if that weren't enough, VAR parameters ALSO make it more difficult (though not impossible) to implement copying-compacting garbage collectors (the "best" garbage collectors are all based on the same copying-compacting algorithm; see Baker's article in the April 1978 CACM for an excellent explanation of the algorithm, plus his "real-time" extension to it). Note that even some of the problems of VAR parameters fall out if "variables" are stored in the heap instead of in the activation record (as is done in compilers for ML and Russell, and probably Scheme also. This slows some things down, but this, too, can be optimized). REFERENCE LIST FOLLOWS. IT MIGHT NOT HURT TO READ SOME OF THESE BEFORE DEBATING THE MERITS/FAULTS OF PROCEDURE VARIABLES. CC = "{SIGPLAN} Symposium on Compiler Construction" LaFP = "{SIGPLAN} Symposium on {LISP} and Functional Programming" PLDI = "{SIGPLAN} Symposium on Programming Language Design and Implementation" FPLCA = "Functional Programming Languages and Computer Architecture" POPL = "Conf. Record of {ACM} {SIGACT/SIGPLAN} Symposium on Principles of Programming Languages" cacm = "Communications of the {ACM}" [1] papers that talk about optimizing away closures and things (there are more than this; this is the quick list, and only includes papers that actually discuss allocation and representation choices for activation records): (techreport) AUTHOR = "Guy L. {Steele Jr.}", TITLE="{RABBIT}: A Compiler for {SCHEME}", INSTITUTION= MIT, YEAR=1978, AUTHOR = "Rodney A. Brooks and Richard P. Gabriel and Guy L. {Steele Jr.}", TITLE = "An Optimizing Compiler for Lexically Scoped {LISP}", YEAR = 1982, PAGES = {261--275}, BOOKTITLE = CC AUTHOR = "Luca Cardelli", TITLE = "Compiling a Functional Language", YEAR = 1984, PAGES = {208--217}, BOOKTITLE = LaFP AUTHOR= "Hans-Juergen Boehm and Alan Demers", TITLE= "Implementing {R}ussell", INSTITUTION=RICE, NUMBER="COMP TR85-25", YEAR=1985 AUTHOR="David Kranz and Richard Kelsey and Jonathan Rees and Paul Hudak and James Philbin and Norman Adams", TITLE="{ORBIT}: {An} Optimizing Compiler for {S}cheme", BOOKTITLE=CC, YEAR=1986, PAGES={219--233} [2] papers that talk about collecting garbage quickly: AUTHOR = "C. J. Cheney", TITLE = "A Nonrecursive List Compacting Algorithm", JOURNAL = cacm, VOLUME = 13, NUMBER = 11, YEAR = 1970, MONTH = nov, PAGES = {677--678} AUTHOR = "Baker, Jr., Henry G.", TITLE = "List Processing in Real Time on a Serial Computer", JOURNAL = cacm, VOLUME = 21, NUMBER = 4, YEAR = 1978, MONTH = apr, PAGES = {280--294} (note -- this is actual real-time, though the lower bound in response time may not be low enough for everyone.) TITLE = "A Real-Time Garbage Collector Based on the Lifetimes of Objects", AUTHOR = "Henry Lieberman and Carl Hewitt", JOURNAL = cacm, NUMBER = 6, VOLUME = 26, YEAR = 1983, MONTH = jun, PAGES = {419--429} AUTHOR="David Ungar", TITLE="Generation Scavenging: {A} Non-disruptive High Performance Storage Reclamation Algorithm", YEAR=1984, PAGES={157--167}, BOOKTITLE="Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments" AUTHOR = "A. W. Appel and D. B. MacQueen", TITLE = "A Standard {ML} Compiler", BOOKTITLE = FPLCA87, YEAR = 1987, PAGES = {301--324} AUTHOR = "Andrew W. Appel and John R. Ellis and Kai Li", TITLE = "Real-time concurrent garbage collection on stock multiprocessors", BOOKTITLE = PLDI, YEAR = 1988, PAGES= {11--20} (note -- this is actually "probably real-time", not "really real-time". It should work well enough in an interactive system, but I wouldn't want it flying any airplanes.) And others, including something recent by Joel Bartlett of DEC Western Research Labs; I lack a handy reference. Robert Shaw, now (?) at HP Labs in Palo Alto, also studied this in his graduate work at Stanford. There is also the not necessarily high-performance (but not offensively slow) collector of Boehm and Weiser; it is non-compacting, conservative, and somewhat portable. We use it with C, Modula-2+, and Modula-3 code; it is used with Russell, and has been adapted for use with the Xerox PARC "Portable Common Runtime" for their Cedar system. When appropriately configured (change two flags and recompile to make it even more conservative) it appears to work with the X11 library without modifications to the X11 source. It will even work with the dreaded VAR parameters if activation records are heap-allocated. AUTHOR = "Hans Boehm and Mark Weiser", TITLE = "Garbage Collection in an Uncooperative Environment", JOURNAL = spe, YEAR = 1988, MONTH = sep, PAGES={807--820} David