Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!snorkelwacker.mit.edu!shelby!neon!craig
From: craig@Neon.Stanford.EDU (Craig D. Chambers)
Newsgroups: comp.lang.modula3
Subject: Re: Closures in m3
Message-ID: <1991Feb22.230729.28053@Neon.Stanford.EDU>
Date: 22 Feb 91 23:07:29 GMT
References: <91Feb21.152416pst.16910@alpha.xerox.com> <1991Feb22.150701.15020@uicbert.eecs.uic.edu>
Organization: Stanford University
Lines: 42

In article <1991Feb22.150701.15020@uicbert.eecs.uic.edu> wilson@uicbert.eecs.uic.edu (Paul Wilson) writes:
>A moderately smart compiler can detect most cases where a procedure can't
>escape, and compile it the cheap way.  The T and Gambit compilers do this
>for Scheme.  I don't see why it wouldn't work for M3.  (One really obvious
>case is to avoid making a closure for any procedure which is only called,
>without ever creating a pointer to it.  That gets rid of most closures 
>right there.
>
>...
>
>Full closures aren't terribly expensive if you optimize away the obvious
>ones.  Being careless about compiling control structures like generators
>can cause a lot of closure-creation, though, so that heap allocation
>is significantly increased.  Depending on how good a garbage collector
>you've got, that may be a factor.  If you've got a generational gc and
>do the obvious optimizations on closures, though, you should be okay.
>(One thing David Kranz' thesis from Yale showed was that closures don't
>have to cost anything to programs that don't use them.  So you may not
>want to make this stuff unsafe, because the cost of doing it right
>may not be all that much.)

Closures can be optimized away as you describe only if the control
structure procedures that eventually call the closure all get inlined
into the function creating the closure.  Kranz' work on eliminating
closures that are only called applies only to closures defined and
invoked locally (within a single procedure).  This is presumably not
the case with the list iterator example being discussed.

Another optimization described in Kranz' work requires interprocedural
analysis to detect when a procedure never stores one of its arguments
into the heap or passes the argument to a function that might do such
a store, i.e. detected which parameters to functions are only ever
passed down or invoked but never "escape" as Kranz calls it.  For
closures passed in non-escaping argument positions to non-inlined
functions, the compiler can use a cheaper (e.g. stack-allocated)
representation of the closure since the compiler has proven that the
block can never escape upwards.  I don't know how often this analysis
succeeds in being effective.  I'd expect the job to be much harder in
an object-oriented language than a procedural language like Scheme,
since the interprocedural analysis is more complicated.

-- Craig Chambers