From: Mark Johnson
Subject: Linking and MACL
Date: 
Message-ID: <21316@brunix.UUCP>
#|
All this talk about compilation in Lisp has started me thinking
about the dynamic linking (via the symbol table) that I guess
most Lisp implementations must use.  It would seem to me that
for "simple" functions the symbol-table lookup time (and
associated type and argument count checking) could take a
significant fraction of the time needed to execute the function
call.  Static linking could avoid the need to do this checking
on every function entry, but would be hard to incorporate in
an interactive Lisp (or one where you could redefine functions
at run-time).

However, there is one case where static linking would seem
to be ideal - the LABELS construct.  In most cases (where
the local function definitions are not closed ove) it should
be possible to statically link the local functions and perform
the argument-count checking at compile-time.  Moreover, references
in the local functions to lexical variables in the enclosing
definition should be able to be compiled to stack-offsets, so
there should be no need to close over them.

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.  I demonstrate this on two programs that solve the 
nqueens problem that are listed below.

The first one uses the LABELS construct: I regard it as the
neater of the programs.  Unfortunately, it is also
the slower.

  ? (time (and (queens1 8) nil))
  (AND (QUEENS1 8) NIL) took 493 ticks (8.217 seconds) to run.
  NIL

The second function "unpacks" all of the local LABELS functions
into independent functions.  It runs about twice as fast as
the first.  Moreover, adding INLINE declarations speeds up
QUEENS2 more than it speeds up QUEENS1!

  ? (time (and (queens2 8) nil))
  (AND (QUEENS2 8) NIL) took 321 ticks (5.350 seconds) to run.
  NIL

I find this most unfortunate, since it encourages programmers
to use a less elegant programming style for efficiency reasons,
particularly when as far as I can see, the more elegant style
should actually be more efficient!

Mark Johnson
|#

(defun queens1 (n)
  (labels ((find-queens (sofar col safeset)
             (if (> col n)
               (cons safeset sofar)
               (place-queen sofar col n safeset)))
           (place-queen (sofar col row safeset)
             (labels ((safe (rest-safeset)
                        (or (null rest-safeset)
                            (and (/= col (caar rest-safeset))
                                 (/= row (cdar rest-safeset))
                                 (/= (abs (- col (caar rest-safeset)))
                                     (abs (- row (cdar rest-safeset))))
                                 (safe (cdr rest-safeset))))))
               (if (= row 0)
                 sofar
                 (place-queen (if (safe safeset)
                                (find-queens sofar 
                                             (1+ col)
                                             (cons (cons col row)
                                                   safeset))
                                sofar)
                              col
                              (1- row)
                              safeset)))))
    (find-queens '() 1 '())))

(defun find-queens (n sofar col safeset)
  (if (> col n)
    (cons safeset sofar)
    (place-queen n sofar col n safeset)))

(defun safe (rest-safeset row col)
  (or (null rest-safeset)
      (and (/= col (caar rest-safeset))
           (/= row (cdar rest-safeset))
           (/= (abs (- col (caar rest-safeset)))
               (abs (- row (cdar rest-safeset))))
           (safe (cdr rest-safeset) row col))))

(defun place-queen (n sofar col row safeset)
  (if (= row 0)
    sofar
    (place-queen n (if (safe safeset row col)
                     (find-queens n sofar (1+ col) (cons (cons col row) safeset))
                     sofar)
                 col
                 (1- row)
                 safeset)))

(defun queens2 (n)
  (find-queens n '() 1 '()))

From: Tim Moore
Subject: Re: Linking and MACL
Date: 
Message-ID: <1989Nov20.150510.20700@hellgate.utah.edu>
In article <·····@brunix.UUCP> ··@monaco.UUCP (Mark Johnson) writes:
>All this talk about compilation in Lisp has started me thinking
>about the dynamic linking (via the symbol table) that I guess
>most Lisp implementations must use.  It would seem to me that
>for "simple" functions the symbol-table lookup time (and
>associated type and argument count checking) could take a
>significant fraction of the time needed to execute the function
>call.  Static linking could avoid the need to do this checking
>on every function entry, but would be hard to incorporate in
>an interactive Lisp (or one where you could redefine functions
>at run-time).

The time consuming part of the link, hashing the symbol to produce an
address in the symbol table, can be done at load time. Then, a
function call is pretty trivial: fetch an address from the function
slot of the symbol and jsr to it. Or, if you're feeling adventurous,
extravagant, and unportable, jsr to symbol's function slot, which
could contain a jump to the beginning of the function code.

Argument count checking isn't that time consuming. Usually the number
of arguments is passed to the function as a "magic" parameter; a simple
comparison in the called function suffices for the check. Processing
of &optional and &key arguments can be very time consuming, but there
are tricks to speed up their processing too.

>However, there is one case where static linking would seem
>to be ideal - the LABELS construct.  In most cases (where
>the local function definitions are not closed ove) it should
>be possible to statically link the local functions and perform
>the argument-count checking at compile-time.

True.

>  Moreover, references
>in the local functions to lexical variables in the enclosing
>definition should be able to be compiled to stack-offsets, so
>there should be no need to close over them.

Maybe in some trivial cases, but not in general. Consider the
following case:

(defun foo (on-u)
  (labels ((uses-on-u (a b)
	     (+ a b on-u))
	   (another-fun (bar)
	     (uses-on-u bar on-u)))
    (+ (uses-on-u 1 3)
       (another-fun 4))))

Assuming that uses-on-u and another-fun both create stack frames, the
relative position of on-u on the stack will be different when
uses-on-u is called from foo from when it is called from another-fun.
In general, you need to provide some sort of static link or display
mechanism for the closed functions to get at their environment. This
can involve several levels of indirection.

Also, closure analysis in general can be very tricky. It should be
trivial to determine that the local functions in the above example
aren't upward funargs, so  an environment doesn't need to be
constructed for them, but I think the general case is much harder to analyse.

>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!

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.

>Mark Johnson

Tim Moore                     ·····@cs.utah.edu {bellcore,hplabs}!utah-cs!moore
"Ah, youth. Ah, statute of limitations."
		-John Waters
From: Simon Leinen
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <SIMON.89Nov21182043@bear.UUCP>
In article <······················@hellgate.utah.edu> ··················@cs.utah.edu (Tim Moore) writes:

   In article <·····@brunix.UUCP> ··@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.
From: Sandra J Loosemore
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <1989Nov22.082200.3230@hellgate.utah.edu>
In article <···················@bear.UUCP> ·····@bear.UUCP (Simon Leinen) writes:
>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'm getting tired of seeing LABELS and FLET slandered where the blame
really rests on lousy implementation of these constructs in some
compilers. 

Depending on how you implement symbols and functions, calling a
globally named function generally requires an indirection through the
symbol object to access its symbol-function component.  That requires
at least one and maybe more memory references to get the address of
the code for the function.

On the other hand, the easiest way to implement locally named
functions is to treat them just like local variables.  Some compilers
will keep these in registers whenever possible, so that there is no
need to reference memory to get the address of the function.  In the
case of non-closed functions, the address of the code for the called
function can be computed as a load-time constant and patched directly
into the code for the caller.

Once you have the address of the function in hand, the overhead of
calling it is the same no matter whether it is named locally or
globally or not at all.  I suspect that in most implementations, the
cost of computing the function address is very small compared to all
the other work involved in setting up the call (such as moving
arguments to the right places) anyway.

Calling a closure can involve extra overhead in some implementations
(again, this varies) but whether or not a function is closed is again
independent of how it is named.  Creating a closure is usually even
slower, but there is no reason for it to be any slower for FLET and
LABELS than it is for anonymous lambdas.

-Sandra Loosemore (······@cs.utah.edu)
From: Lou Steinberg
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <Nov.22.12.11.49.1989.1498@atanasoff.rutgers.edu>
In article <···················@bear.UUCP> ·····@bear.UUCP (Simon Leinen) writes:

> 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.

There is another issue with LABELS and FLET: interactive programming
environments for LISP (at least the ones I am familiar with) do not
have good ways to handle local functions.  E.g. to trace a function,
you must give the function name, and what gets traced is the global
function definition.  There is no way to even specify that you want
tracing for a local definition.  There are similar problems with
anonymous functions, e.g. closures produced with FUNCTION.

I would guess that this, more than efficiency issues, is what leads
people not to use local function definitions in lisp.
-- 
					Lou Steinberg

uucp:   {pretty much any major site}!rutgers!aramis.rutgers.edu!lou 
arpa:   ···@cs.rutgers.edu
From: Barry Margolin
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <31762@news.Think.COM>
In article <·························@atanasoff.rutgers.edu> ···@atanasoff.rutgers.edu (Lou Steinberg) writes:
>There is another issue with LABELS and FLET: interactive programming
>environments for LISP (at least the ones I am familiar with) do not
>have good ways to handle local functions.  E.g. to trace a function,
>you must give the function name, and what gets traced is the global
>function definition.  There is no way to even specify that you want
>tracing for a local definition.  There are similar problems with
>anonymous functions, e.g. closures produced with FUNCTION.

Both Common Lisp implementations I'm familiar with -- Symbolics and Lucid
-- have names for local functions.  They are named (:INTERNAL <parent> <n>
<name>), where <parent> is the name of the function containing the local
definition, <n> is an index used to distinguish multiple local functions in
the same parent, and <name> is an optional name produced when FLET, LABELS,
or SYS:NAMED-LAMBDA are used (anonymous local functions are just named
(:INTERNAL <parent> <n>).  You can pass these names to TRACE, DISASSEMBLE,
etc.

You are right that development environments don't deal with local functions
as well as with top-level functions.  For instance, control-shift-A in
Zmacs, which is supposed to show the argument list of the function in the
form surrounding the cursor, doesn't recognize local function names (of
course, if you follow the age-old guideline of keeping your function
definitions within a screenful in size, you should only need to look up a
few lines to find this information).

Barry Margolin, Thinking Machines Corp.

······@think.com
{uunet,harvard}!think!barmar
From: Simon Leinen
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <SIMON.89Nov23120357@packer.UUCP>
In article <·····@news.Think.COM> ······@leander.think.com (Barry Margolin) writes:

   Both Common Lisp implementations I'm familiar with -- Symbolics and
   Lucid -- have names for local functions.  They are named (:INTERNAL
   <parent> <n> <name>), where <parent> is the name of the function
   containing the local definition, <n> is an index used to
   distinguish multiple local functions in the same parent, and <name>
   is an optional name produced when FLET, LABELS, or SYS:NAMED-LAMBDA
   are used (anonymous local functions are just named (:INTERNAL
   <parent> <n>).  You can pass these names to TRACE, DISASSEMBLE,
   etc.

This is what makes local functions expensive: They are called through
a (synthetic) symbol's function cell.  When you use the `production
compiler' of Lucid Lisp, this overhead is avoided.  As Sandra
Loosemore argued, calls to local functions should be *cheaper* than
calls to global functions.

The Lucid implementation often integrates local functions into their
callers, thus eliminating function call overhead *completely*.  This
is the way to do local functions in production compilers: Using them
costs nothing in many cases, and there is no need to write huge
function bodies because of efficiency considerations when you would
rather like to have many small (local) functions.

I agree completely with what Sandra said about use of Common Lisp
constructs and the quality of present Lisp implementations.  Don't
blame every efficiency problem to the language; many `expensive'
features of Lisp can be implemented quite efficiently at the expense
of additional brain work (see Orbit and Lucid Lisp).
-- 
Simon Leinen.
From: Dan Weinreb
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <1989Nov24.154940.9739@odi.com>
In article <···················@packer.UUCP> ·····@packer.UUCP (Simon Leinen) writes:


   This is what makes local functions expensive: They are called through
   a (synthetic) symbol's function cell.  When you use the `production
   compiler' of Lucid Lisp, this overhead is avoided.  As Sandra
   Loosemore argued, calls to local functions should be *cheaper* than
   calls to global functions.

   The Lucid implementation often integrates local functions into their
   callers, thus eliminating function call overhead *completely*. 

But remember, the earlier posting's complaint was that it was too hard
to trace internal (local) functions.  You can't have it both ways: if
they are integrated, they certainly can't be traced.

Actually, distinguishing between external and internal functions here
is a red herring.  What you really want is two modes: one in which
debugging all works well, at the cost of performance, and another
optimized for speed but in which debugging is more difficult.  This
should exist for all kinds of functions.

In the Lisp machines, the goal was to design hardware so that you
could have speed and debuggability at the same time; many people feel
that they come close enough to this ideal that it's not worth having
separate compiler modes (debug versus optimize), although the point is
debatable.
From: Barry Margolin
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <31768@news.Think.COM>
In article <···················@packer.UUCP> ·····@packer.UUCP (Simon Leinen) writes:
>In article <·····@news.Think.COM> ······@leander.think.com (Barry Margolin) writes:
>   Both Common Lisp implementations I'm familiar with -- Symbolics and
>   Lucid -- have names for local functions.
>This is what makes local functions expensive: They are called through
>a (synthetic) symbol's function cell.

I don't know about Lucid, but the Symbolics implementation doesn't actually
indirect through function names when calling the function, either local or
global.  The calling function contains a pointer to the callee function
object.  The indirection through the function name is done only once, at
load time.  The actual calling mechanism is the same for both global and
local functions.

Barry Margolin, Thinking Machines Corp.

······@think.com
{uunet,harvard}!think!barmar
From: News Owner
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <14230@boulder.Colorado.EDU>
From: ·····@boulder.Colorado.EDU (Repenning Alexander)
Path: boulder!ralex

> I don't know about Lucid, but the Symbolics implementation doesn't actually
> indirect through function names when calling the function, either local or 
> global.  The calling function contains a pointer to the callee function
> object.  The indirection through the function name is done only once, at
> load time.  The actual calling mechanism is the same for both global and
> local functions.

I can certainly believe this works fine for local functions. However, if 
the indirection is done only once at load time how does this 
schema account for modifications of the callee? Or even worse, the called 
function might not be defined yet. How does the Symbolics handle this? 
Lazy evaluation? In order to propagate modification the callee needs 
to have some sort of backward pointers to all callers to update the 
indirections.


   Alex
From: Barry Margolin
Subject: Redefining functions on Symbolics Lispm
Date: 
Message-ID: <31772@news.Think.COM>
In a previous posting, I think I made a slight misstatement when I
described function linkage on Symbolics workstations.  I said that the
caller has a pointer to the callee function object.  Repenning Alexander
asked how redefinition and forward reference works in such a scheme.

Actually, I think it has a pointer to the function cell of the callee, not
the function object itself.  In the case of functions named by symbols,
this is the actual function cell in the symbol structure; for functions
named by lists it's a pointer to a cons cell in the function specifier hash
table.  And in the case of forward references it's a pointer into a fixup
table that contains back pointers to be used when the function is loaded.

Barry Margolin, Thinking Machines Corp.

······@think.com
{uunet,harvard}!think!barmar
From: Lou Steinberg
Subject: Re: Linking and MACL (really efficiency of local functions)
Date: 
Message-ID: <Nov.24.13.04.15.1989.4066@porthos.rutgers.edu>
In article <·····@news.Think.COM> ······@leander.think.com (Barry Margolin) mentions:

> the age-old guideline of keeping your function definitions within 
> a screenful in size

Ah, yes, that's another reason for internal (FLET or LABELS) functions
being less popular in lisp than in other languages.  In a language
like Pascal, it is normal to have only one top-level routine, with all
others nested to some level within it.  But if you do this, then
really only the leaf-level routines fit completely on one screen (or
maybe also the next-to-leaf level routines if the leaf-level ones are
small).  So in the highly interactive environment typical of lisp you
don't want to use internal functions for ALL subroutines.  Given that
most routines are external, people tend to make ALL routines external,
which probably makes sense in some kind of psychological-parsimony
terms.

(Note that the size of a function affects not only how much of it you
can see at once, but how long it takes to reload it after editing a
piece of it.  If the whole file is one top-level function there is no
way to reload or recompile a small piece of it.)
-- 
					Lou Steinberg

uucp:   {pretty much any major site}!rutgers!aramis.rutgers.edu!lou 
arpa:   ···@cs.rutgers.edu
From: Charles Martin
Subject: T and Orbit
Date: 
Message-ID: <6392@tank.uchicago.edu>
In article <···················@bear.UUCP> Simon Leinen writes:
>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).

T was developed at Yale University:

    Rees, J.A. and Adams, N.I. (1982).  T: A dialect of Lisp, or, lambda:
    the ultimate software tool.  Conference Record of the 1982 ACM
    Symposium on Lisp and Functional Programming.

    Rees, J.A., Adams, N.I., and Meehan, J.R. (1984).  The T manual, fourth
    edition.  Yale University.

Orbit was also developed at Yale University:

    Kranz, D.A., Kelsey, R., Rees, J.A., Hudak, P., Philbin, J., and Adams,
    N.I. (1986).  ORBIT: An optimizing compiler for Scheme.  Proceedings of
    teh SIGPLAN 1986 Symposium on Compiler Construction.

    Kranz, D.A. (1988).  ORBIT: An optimizing compiler for Scheme.  Ph.D.
    Dissertation, Yale University Technical Report #632.

Charles Martin // ······@gargoyle.uchicago.edu