Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!ucsd!helios.ee.lbl.gov!hellgate.utah.edu!cdr.utah.edu!moore
From: moore%cdr.utah.edu@cs.utah.edu (Tim Moore)
Newsgroups: comp.lang.lisp
Subject: Re: Linking and MACL
Message-ID: <1989Nov20.150510.20700@hellgate.utah.edu>
Date: 20 Nov 89 22:05:10 GMT
References: <21316@brunix.UUCP>
Organization: University of Utah CS Dept
Lines: 82

In article <21316@brunix.UUCP> mj@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                     moore@cs.utah.edu {bellcore,hplabs}!utah-cs!moore
"Ah, youth. Ah, statute of limitations."
		-John Waters