wille@ethz.UUCP (M. Wille) (10/05/87)
MSRS002@ECNCDC.BITNET writes >Modula allows a variable to be a procedure type, and that variable to >be assigned the "value" of different procedures. This is a very usefull >thing when making programs such as operating systems or I/O drivers, but >it leads to one question. Consider the following scrap of code: PROCEDURE A; VAR P: PROC; PROCEDURE B; VAR X: CARDINAL; PROCEDURE C; BEGIN X := 17 END C; BEGIN P := C; END B; BEGIN B; P END A ; Do you really think that your code scrap makes any sense. Calling 'C' outside of its environment does not work in Modula-2. Our compiler rejects this piece of code, saying that the procedure 'C' in the assignment 'P := C' is not declared on level 0. Hopefully, other compilers do the same. Finally, I will provide you with Wirth's solution of this problem. He simply restricted the use of assigned procedures to non-local procedures (see Programming in Modula-2 3rd. Ed., p. 151). ------------------------------------------------------------------ Matthias Wille | CSNET: wille@ifi.ethz.ch Institut fuer Informatik | wille@komsys.ifi.ethz.ch ETH - Zentrum | UUCP: ..mcvax!cernvax!ethz!wille CH-8092 Zuerich Switzerland | Phone: (00411) 256 23 51
ONM64@DMSWWU1A.BITNET (Kai Henningsen) (04/26/89)
Well, my friendly Pascal Compiler (Turbo Pascal 5.0) does this in
exactly the same way as Wirth defines it for Modula-2, so it has
to be doable ...
The reasons behind the various do's and dont's are as follows:
1. Why not allow "standard procedures"? Simple: the compiler writer
may decide to implement these not like ordinary procedures, but
in some special way. Thus, they have no address that could be
stored in a procedure variable.
For example, try to imagine the following:
v: PROCEDURE (ARRAY OF CHAR) : CARDINAL;
v := SIZE;
Somewhat problematic ...
2. Why not allow local procedures? Simple: because it's NOT simple :-)
Really: This is part of ISO Pascal. Up to now, I have seen one
implementation, in Mac MPW Pascal. I looked at the code. Now I know
why you don't want to implement it ...
It's like this: If you have a local Procedure, then you obviously
have to save the static calling chain. Most Compilers do this by
passing, as an invisible parameter, a pointer to the procedure's
parent's stack frame. In the case of a procedure variable, that means
you have to put this pointer in the variable, too. BUT a global
procedure does not expect to get this parameter! So, you end up
generating code like this:
IF procvar.stackframe#NIL THEN push(procvar.stackframe) END;
call(procvar.adr);
Yechhh!!
By the way, we have another problem here. Suppose the following:
VAR v: PROCEDURE;
PROCEDURE A;
PROCEDURE B;
BEGIN END B;
BEGIN v:=B; END A;
BEGIN A; v(); END;
Where's my stackframe gone to???
There are two approaches to this problem:
First, ISO Pascal. We do not allow procedure variables, except as
parameters. Obviously, the stack frame will thus be there.
Second, Lisp. The stack frame is an (invisible) Lisp object.
As long as there exists a procedure variable pointing to X,
the garbage collector will not kill the stack frame for that
invocation of X's parent. Obviously, stack frames are heap objects
chained with pointers. Nice but SLOWWWW.
Of course, there is always a third way: don't allow this. Modula-2.
3. Now what about non-exported global procedures?
Well, what about it? Non-exported procedures are exactly like exported
ones, except the module importer does not know these by name. Since
he does not know the name of any procedure called via a procedure
variable either, that shouldn't hurt.
Of course, the implementor may choose to optimize those procedures on
the grounds that they will only be used from places known in advance.
So does Turbo Pascal 5.0. But, if they are used with procedure
variables at all (wether exported or not), this must break down.
What do we do? Either, we restrict optimizing in cases where a
procedure is exported or assigned to a procedure variable, or we
allow the user to decide on optimizations (remember compiler
directives?), but allow export & assignment only on non-optimized
procedures. (TP5 really does a mix of the two.)
Kai
onm64 @ dmswwu1a . bitnetdcw@doc.ic.ac.uk (Duncan C White) (04/27/89)
In article <INFO-M2%89042509041995@UCF1VM> Modula2 List <INFO-M2%UCF1VM.bitnet@jade.berkeley.edu> writes: > Why not allow local procedures? Simple: because it's NOT simple :-) {discussion of a rather trivial problem deleted: onto the real problem} > Suppose the following: > > VAR v: PROCEDURE; > PROCEDURE A; > PROCEDURE B; > BEGIN END B; > BEGIN v:=B; END A; > > BEGIN A; v(); END; > > Where's my stackframe gone to??? {3 approaches:} > First, ISO Pascal. We do not allow procedure variables, except as > parameters. Obviously, the stack frame will thus be there. > Second, Lisp. The stack frame is an (invisible) Lisp object. > As long as there exists a procedure variable pointing to X, > the garbage collector will not kill the stack frame for that > invocation of X's parent. Obviously, stack frames are heap objects > chained with pointers. Nice but SLOWWWW. 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! > Of course, there is always a third way: don't allow this. Modula-2. There is a 4th way: this hinges upon the observation that it MAY or MAY NOT be safe to do this.. it's a bit draconian to ban it always just because it may not be safe. (Comparison, let's ban division because division by 0 is unsafe!) So, let us ask ourselves: when does the problem actually occur? Well, I reckon that it's a certain kind of CALL which causes the problem: A CALL (thru a procedure variable) to a procedure whose static outer procedure is NO LONGER on the call-chain. A solution to this problem is know looking irrestibly like a run-time check (just like division!) : when a call-thru occurs, check that the outer procedure is still activated. This check is only needed for procedure-variables which have local-procedures assigned to them - a property which may be determined at compile-time. Hence only users wishing to assign local procedures to procedure-variables would suffer any slowdown on procedure-variable calls. Of course, I guess Wirth couldn't be bothered with this, so took the simple way out: BAN IT. Anyone know of compilers which make this extension? >Kai > >onm64 @ dmswwu1a . bitnet Duncan. [ Reply to: dcw@doc.ic.ac.uk or ...!ukc!icdoc!dcw ] ---------------------------------------------------------------------------- Duncan White, | "Middle East Policy was a fiasco and a Dept. Of Computing, | disaster, but Central American policy was Imperial College, | in better shape - it was merely a disaster!" London SW7, England | Spitting Image on Reagan...
chase@Ozona.orc.olivetti.com (David Chase) (04/28/89)
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