Re: _My_ ideas for current research!

In article 91-11-099, eifrig@blaze.cs.jhu.edu (Jonathan Eifrig) writes:


> 1) Functional Program Compilation. The basic notions of functional
> programming are well understood from a _language_ point of view, but
> problems still remain with their implementation. Most functional
> languages permit nested function declarations; these are usually
> implemented as closures in the heap, with activation's return points kept
> on a stack.


Actually, lots of compilers manage to keep closures in the stack a
quite high percentage of the time. For example, if you have the
Scheme code


(define fact
    (lambda (n)
        (letrec ((fact-helper
                            (lambda (n acc)
                                (if (zero? n) acc
                                        (fact-helper (- n 1) (* n acc))))))
              (fact-helper n 1))))


any good Scheme compiler these days will transform the calls to the inner
lambda into a loop, obviating the need for creating a closure for it in
the heap. What you say is of course still true for some closures, though.


> Is this the right way to go? It is possible to eliminate the
> run-time stack altogether using _continuations_. This may, or may not,
> turn out to be a better approach in the long run.


Andrew Appel has proven that heap allocation is faster than stack
allocation under fairly reasonable circumstances, assuming that you have
enough memory. (The basic idea is that if you allocate things on the
stack then you have to deallocate dead objects explicitly, whereas if you
allocate things in the heap and use stop-and-copy garbage collection, you
only touch live objects, not the dead ones; so if your typical dead
object/live object ratio is high enough, you are better off allocating
everything in the heap.) But his and David MacQueen's SML/NJ compiler is
the only one that I know of that does this.


david carlton
carlton@husc.harvard.edu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.