🚀 go-pugleaf

In article <INFO-M2%89042509041995@UCF1VM> Modula2 List <INFO-M2%UCF1VM.bitnet@jade.berkeley.edu> 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