Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!samsung!uunet!mcsun!unido!tub!tubopal!opal!simon
From: simon@bear.UUCP (Simon Leinen)
Newsgroups: comp.lang.lisp
Subject: Re: Linking and MACL (really efficiency of local functions)
Message-ID: <SIMON.89Nov21182043@bear.UUCP>
Date: 21 Nov 89 17:20:43 GMT
References: <21316@brunix.UUCP> <1989Nov20.150510.20700@hellgate.utah.edu>
Sender: news@tubopal.UUCP
Organization: TU Berlin, Fachbereich 20 (Informatik)
Lines: 50
In-reply-to: moore%cdr.utah.edu@cs.utah.edu's message of 20 Nov 89 22:05:10 GMT
To:

In article <1989Nov20.150510.20700@hellgate.utah.edu> moore%cdr.utah.edu@cs.utah.edu (Tim Moore) writes:

   In article <21316@brunix.UUCP> mj@monaco.UUCP (Mark Johnson) writes:

   >Thus we would expect using local functions in the LABELS
   >construct would be much more efficient than an equivalent
   >program in which these local functions have been replaced
   >with global definitions.
   >Unfortunately this is not the case in the Lisp I use, viz.
   >MACL.

   It looks like MACL made the trade-off of speed-of-compilation vs.
   speed-of-compiled code. That's certainly valid, given the
   research-problem nature of closure analysis. I don't know what MACL
   really does; I hope I'm not slandering the developers!

Of the Lisp implementations that I know of, Lucid is the only one to
compile local functions efficiently.  I think they use a control-flow
analysis method similar to the one introduced (?) in Orbit, the
production-quality compiler shipped with the T system (CMU's version
of Scheme).

In Orbit, Lisp expressions are converted to continuation-passing style
(CPS) just after macroexpansion and alphatization.  This is a variant
of Lisp (or Scheme) syntax where each expression takes as an
additional argument the continuation that receives the value(s) of the
expression.

The motivation for inventing CPS was the difficutly of data flow
analysis in Lispy languages vs. in Fortran (where this is, in fact,
much less of a research-problem).

You might want to read the article about control-flow analysis in Lisp
written by the people from the T/Orbit project some time ago, but
right now I don't have the reference.

With many compilers, using local functions is always *slower* than
separate functions.  Perhaps this is what prevents so many people from
using LABELS and FLET.

   I would try your queens example again, but don't let the LABEL'ed
   functions be closed; pass everything they need as a parameter. It
   should be as fast, if not faster, than using global function
   definitions.

That's right: It *should* be faster, and in Lucid or Orbit, it will.
Even as the code stands, it must be faster than separate functions.

-- 
Simon Leinen.