Common Lisp

406 views
Skip to first unread message

Olin Shivers

unread,
Jul 3, 1986, 4:21:24 AM7/3/86
to
Keywords:

I've been following this flamage about CL. I thought I'd add a few comments
to the fray.

It isn't true that lexical variable references are slow in the interpreter.
The trick is to allow the interpreter to do a pre-execution pass over the
code and resolve variable references. In a lexically scoped lisp, you can
always tell which binding a given reference refers to just by examining the
code; that's the reason why it's called "lexical" scoping. This variable
resolution technique is known to all Algol wizards, not just lisp folks.

You could argue that this constitutes compilation, albeit a very cheap,
fast compilation that preserves the original form of the source. True.
But it retains the interpreter and all the advantages thereof. Some lisps
actually use this technique -- the first thing the interpreter does is (1)
expand all macros, and (2) resolve all variable references. Then the
resulting code tree is interpreted quite speedily. It's a real win.

Compilers also win with lexical scoping. Lexical scoping just gives the
compiler a lot more information about the binding and use of variables.
The semantics of lexical scoping allows a compiler writer to invoke
some powerful invariants that help to generate good code.

>Let's also not forget that (APPLY foo args), where foo is an arbitrary
>structure results in interpretation, not compilation.
Yes, but if FOO turns out to be a compiled function, then the "interpretation"
would last only between function dispatch and the arrival at the code for FOO;
in a good lisp this could be about 3 machine instructions.

Actually, we can do even better than that. Remember that all functions have
to be closed over before they can be executed. That gives the interpreter a
chance at close time to wedge in a simple compiled stub whose only job is to
dispatch off to the evaluator with the actual source to be interpreted. Then
we can guarantee that all blind FUNCALLs or APPLYs actually jump off to
compiled code; i.e. we make the compiled-code-to-interpreted jump in the
function prolog, not in the dispatch. So all blind calls can be compiled as
calls to compiled code.

>Well written LISP code should be almost completely independent of lexical or
>dynamic scoping considerations. A free variable is obviously special; the
>only real problem comes in when a variable is bound.
Well, "free" is a relative term. In the following fragment, the variable A is
free in the inner lambda, but not in the outer.
((LAMBDA (A) [or: (let ((a 3)) (lambda () a)) ]
(LAMBDA () A))
3)
I contest your assertion about well-written code. When you start using some
of the sophisticated techniques that lexical scoping and funargs -- upward and
downward -- give you, it is tremendously important to know that your scoping
is lexical. For example, it is a real gas to write the Sutherland-Hodgeman
polygon clipping algorithm (a 3D graphics thing) in a lexically scoped lisp,
because you can write an arbitrarily stageable version using continuation
passing and lexical scoping. I have *never* seen an equivalent implementation
of this algorithm in another language that is nearly as elegant and easy
to understand. Lexical scoping allows for *powerful* programming techniques.

>>(let ((num 45))
>> (mapcar #'(lambda (x) (+ x num)) '(3 4 5)))
>
>The example you give is meaningless. The results are identical for
>either case.'
That's not true. This is sort of a canonical example. Suppose the definition
of MAPCAR binds NUM. In a dynamically scoped lisp, the lambda expression
would see MAPCAR's NUM, which would shadow the outer NUM. Get it? The fact
that MAPCAR's NUM vanishes as a dynamic variable when MAPCAR is compiled is
due to the inconsistency between old-style lisps' compiler and interpreter
semantics, which is a drag.

In CL, you have to say what you mean, and the compiler and interpreter will
do the same thing. Which seems like a good idea. In the above example,
NUM is bound lexically, and so the inner lambda refers to the NUM bound
by the LET *no matter* what is contained in the definition of MAPCAR. And
that's what the guy that wrote the code wanted -- to add 45 to the
list (3 4 5). He didn't want MAPCAR to have a chance to accidentally shadow
his binding, no matter how MAPCAR was written. This is known as good
modularity. If he'd wanted MAPCAR to have a chance to rebind NUM, he'd have
declared NUM to be dynamic.

>*PLEASE NOTE* that my gripe with CL is that it allows BOTH dynamic
>and lexical binding.
I believe both are important tools to writing good programs. But I think
lexical scoping is far more important. There are several reasons for this:
1) The amazing linguistic power of LAMBDA defined with lexical scoping.
2) You can get the effect of dynamic scoping with lexical scoping
(modulo lightweight processes), but not vice-versa.
3) Lexical scoping gives compiler writers much more leverage for
performing optimising analysis than with dynamic scoping.
4) Tail recursion. I like knowing my tail recursive funtion calls
don't push stack.
If you really want to know what all this fuss about lexical scoping is about,
and to see examples of the claims I've made above, you should read the
Lambda papers, written by Steele & Sussman at MIT in the 70's. The three
basic papers are "The Art of the Interpreter," "Lambda: the Ultimate
Imperative," and "Lambda: the Ultimate Declarative." I'll even volunteer
to send out copies of these papers to folks sending me their mailing address
until I get tired of doing so.

>>>>>to allow both dynamic and lexical makes the performance even worse.
>>>
>>>>This is totally wrong.
>>>
>>>Say WHAT? It certainly is TRUE in an intepreter; it takes longer to look up
>>>a lexical variable than a dynamic variable, and it takes even longer when you
>>>have to determine whether the lookup should be lexical or dynamic. Add a
>>>little more time to check if it's a CONSTANT or DEFVAR...
Doing it that way would certainly be poor interpreter design. See my comments
above. You can do lexical variable reference in an interpreter in constant
time. Constant, as in: two instructions worst case.

>HISTORICAL note: it is much easier to build a dynamically scoped compiler.
>The access time to a special cell is equivalent to a stack based
>variable. A version of UCI LISP at Rutgers did just that; the original
>release of UCI would have had this, but it fell through the cracks.
Whereas in a lexically scoped lisp, access time to a (lexical) variable
turns into a register reference, or a stack reference, or a contour
reference. The point is that lexical scoping gives the compiler a lot
more information about where variables are bound and used. So the compiler
can spot opportunities to put variables in registers, etc., etc..
This is not a gedanken claim; there are compilers that do this.

>I assume that nobody would complain if the compilers had also been
>dynamic, resulting in identical semantics :-)
I would complain. Dynamic scoping is just the wrong default, for the
reasons laid out in the Lambda papers.

>Inference, Carnegie Group and Teknowlege to start.
To the best of my knowledge, Carnegie Group's system, KnowledgeCraft,
is a moby Common Lisp package. I haven't heard a thing about them trying
to move it to C.

Look. I don't even like Common Lisp. The package system is a horrible solution
to a real problem. I hate the idea of separate function/value spaces for
variables. CL makes the classic lisp error of confusing symbols (a data type)
with variables (a language level object). #' is a totally stupid idea. NIL
should not be a list. The design was dragged down by the problem of Zetalisp
compatibility. BUT. I'd much prefer to write in Common Lisp than old-style
lisps like UCI Lisp, Interlisp, franz, or Maclisp. Jeez. At least it's
powerful, lexically scoped, and designed in the eighties by people who had the
benefit of hindsight. You can get some work done in Common Lisp.
@end(flame)
-Olin

Stanley Shebs

unread,
Jul 3, 1986, 7:12:51 PM7/3/86
to
In article <10...@h.cs.cmu.edu> shi...@h.cs.cmu.edu (Olin Shivers) writes:

>You could argue that this constitutes compilation, albeit a very cheap,
>fast compilation that preserves the original form of the source. True.
>But it retains the interpreter and all the advantages thereof. Some lisps
>actually use this technique -- the first thing the interpreter does is (1)
>expand all macros, and (2) resolve all variable references. Then the
>resulting code tree is interpreted quite speedily. It's a real win.

A small caveat for all those who want to run out and do this in their
interpreters - users don't really like to look at their macroexpanded code!
(symbol-function 'foo) returns something that has little apparent relation
to what was typed in. Implementations that do this need to provide some
way of looking at the original input, for instance by hanging on to the
source code and using a debugger to display it, just as for incrementally
compiled Lisps.

>The package system is a horrible solution to a real problem.

The poor package system - everybody hates it, but nobody wants to
chuck it. The only serious alternative I've heard suggested is
some sort of persistent lexical environment (locales in T), but I
don't view the package system as a way to screw around with mapping
of names to values, instead it's a way to increase the size of the
name space without increasing the average size of names.

>CL makes the classic lisp error of confusing symbols (a data type)
>with variables (a language level object). #' is a totally stupid idea. NIL
>should not be a list.

Hmmm, he sounds like a Schemer! Actually, the most ultimate and purest Lisp
dialect I know of is 3-Lisp, which is so clean and regular that it makes
any Scheme look like a kludge. Brian Smith pointed out that (for instance)
conses are used in a multitude of ways in most Lisps, while in 3-Lisp conses
are only used for function applications; the "rail" data structure is
used for lists/sequences. Quotes don't "fall off" as a result of evaluation;
as a result, one doesn't get the Lisp oddity (+ 2 '3) => 5. Closures are
ordinary data structures with 4 slots. Reflection gives one great power,
in fact it hasn't really been exploited yet.
3-Lisp is the way to go for true language purists.

> -Olin

stan

Ken Dickey

unread,
Jul 7, 1986, 3:27:57 PM7/7/86
to
In article <10...@h.cs.cmu.edu> shi...@h.cs.cmu.edu (Olin Shivers) writes:
>
>It isn't true that lexical variable references are slow in the interpreter.
>The trick is to allow the interpreter to do a pre-execution pass over the
>code and resolve variable references. In a lexically scoped lisp, you can
>always tell which binding a given reference refers to just by examining the
>code; that's the reason why it's called "lexical" scoping. This variable
>resolution technique is known to all Algol wizards, not just lisp folks.
>

There is another way to make lexical variable references (typically)
cheaper in interpreters. That is to do the lookup as
V:Id->(Env->Val)
rather than
V:Env->(Id->Val)
as in deep binding. The gist of this is to keep an "Env-list" for
each symbol. Lookup is then essentially a 'getprop' on the env-list.
[Ie if (getenv envN Id) is non-empty, you have found the value, else
(empty) look with a key of the next env, until found or the global
env is reached, then fail].

The cost here for failure is
(* number-of-environments number-of-envlist-bindings)
which is typically (much) less than
(* number-of-environments number-of-ribcage-bindings)
as in deep binding.

The trick with this (ahem) scheme is in the garbage collection. When
the ob-vec (oblist) is collected, the env-lists of the symbols are
not collected (the symbols are themselves valid only if they have a
non-null property-list). When the environments (frames) are
collected, then the (env val) pairs are valid and so is the symbol
[so you need the vars rib of the frame, but not the values rib].

[Note that this strategy differs from that presented by Padget &
Fitch in "Closurize and Concentrate", 12th POPL].

-Ken Dickey
---------------------------------------------------
UUCP: HOST!tektronix!tekla!kend
Where HOST is any one of:
masscomp,decvax,allegra,uf-cgrl,mit-eddie,mit-ems,
uoregon,psu-cs,orstcs,zehntel,ucbcad,ucbvax,purdue,
uw-beaver,reed, ogcvax,ihnp4,tekred,minn-ua,cbosg

CSnet: kend%tekla@tektronix
ARPAnet: kend%tekla%tektronix@csnet-relay
---------------------------------------------------

Reply all
Reply to author
Forward
0 new messages