betz@decvax.UUCP (David Betz) (11/21/83)
Robert Munyer asked me to post this to net.lang.lisp
================================================================
From genrad!wjh12!unixvax:munyer Mon Nov 21 09:17:04 1983
Received: by decvax.UUCP (4.12/4.2)
id AA02623; Mon, 21 Nov 83 09:16:46 est
Date: Mon, 21 Nov 83 09:16:46 est
From: genrad!wjh12!unixvax:munyer
Message-Id: <8311211416.AA02623@decvax.UUCP>
To: genrad!decvax!betz@wjh12
Subject: LISP: Flame on dynamic scoping; plug for T & Scheme
Status: R
David,
I apologize if this bores you; much of what I'm going to say has
already been said in the discussion on lisp-forum, but a lot of it
was so deeply buried in other random argument that I think it may
be worthwhile to restate it.
[[[---Flame on---]]]
If I had to pick one language feature that has held Lisp back more than
any other, it would be dynamic scoping. This unfortunate misfeature
was included in the earliest Lisps, and stuck around for an amazingly
long time. This is not the place to go into all the reasons that
dynamic scoping loses, but I will mention one major problem: dynamic
Lisps violate the principle of "referential transparency". As an
example, consider this function:
-> (defun add-to-every-number (l increment)
(mapcar '(lambda (number) (plus number increment))
l))
This will work right ONLY IF THE DEFINITION OF MAPCAR DOES NOT HAVE AN
ARGUMENT CALLED "INCREMENT". Admittedly, mapcar probably doesn't have
an argument called "increment". But "probably" is not a welcome word
in programming. Clearly, referential opacity is a serious defect for:
* Programming -- it is not reasonable to expect a programmer to know
about the formal parameter names and local variable names of a
function (like mapcar) that was written by someone else.
* Compiling -- what good does it do to compile a function into
machine language if the machine language version has to know the
names that were used for the variables in the Lisp source code?
The way this problem is usually dealt with is to make the compiler
DELIBERATELY INCOMPATIBLE with the interpreter -- compiled
functions DON'T use dynamic binding, unless the programmer
explicitly requests dynamic binding with a "special" declaration.
There are functions on these systems that will work compiled but
not interpreted, or vice versa, because of this trick.
* Computer Science -- dynamic Lisps are NOT valid implementations of
the Lambda Calculus, because they do not allow "alpha conversion".
In other words, changing the name of a function's formal parameter
can change what the function does.
Dynamic scoping seems to be at the root of a lot of the cruft you can
find in the typical dynamic Lisp -- "function cells", "special"
declarations, #', incompatible compilers, the practice of passing
around the name of a function rather than the function itself, global
variables, etc...
The point of this article is supposed to be function cells.
Here goes...
Imagine running the following function in a system WITH dynamic
scoping and WITHOUT function cells.
-> (defun smallest (list) (mergesort list 'lessp))
The problem with this is that "mergesort", and any functions called
by "mergesort", cannot use the function "list"! If they try to,
they will be calling some random list instead of the function which
is the GLOBAL value of "list".
There are several ways you can get around this problem:
* Let the programmer deal with it: When he writes a new function,
he has to be sure that its name is different from all the variable
names that exist in his system, or that will exist in the future.
(and vice versa, when he chooses a variable name).
* You can make a symbol's "function binding" separate from its "value
binding".
* You can use lexical scoping instead of dynamic.
So, if XLISP is dynamically scoped, I would say you would be better
off with separate function cells. But you certainly aren't violating
a basic principle of Lisp.
Background Material:
The first lexically scoped Lisp was called Scheme, and was developed
by Steele and Sussman at MIT. Here are some references:
Sussman, Gerald Jay, and Steele, Guy Lewis Jr. SCHEME: An Interpreter
for Extended Lambda Calculus. AI Memo 349. MIT AI Lab (Cambridge,
December 1975).
Steele, Guy Lewis Jr., and Sussman, Gerald Jay. LAMBDA: The Ultimate
Imperative. AI Memo 353. MIT AI Lab (Cambridge, March 1976).
Steele, Guy Lewis Jr. LAMBDA: The Ultimate Declarative. AI Memo 379.
MIT AI Lab (Cambridge, November 1976).
Steele, Guy Lewis Jr. "Debunking the 'Expensive Procedure Call' Myth."
Proc. ACM National Conference (Seattle, October 1977), 153-162.
Revised as MIT AI Memo 443 (Cambridge, October 1977).
Steele, Guy Lewis Jr., and Sussman, Gerald Jay. The Revised Report on
SCHEME. MIT AI Memo 452 (Cambridge, January 1978).
And, if you really want to get into the technical details,
Steele, Guy Lewis Steele Jr. RABBIT: A Compiler for SCHEME. AI-TR-74.
MIT AI Lab. (Cambridge, May 1978).
Scheme is a research language; it has a few rough edges (mostly due to
its implementation in MACLISP), and all of the implementations I know
of are NBF (Not Blindingly Fast).
A group at the Yale CS department embarked last year on a project to
create a new lexically scoped Lisp. The result, T, is a real,
production-quality language, with the ideals of Scheme but considerably
more power and speed. The most basic difference between T and Common
Lisp, the other new "lexically" scoped Lisp (I use disbelief quotes
here because it didn't have real lexical scoping last time I looked),
is that T makes absolutely no concessions to MacLisp backward-
compatibility. The result is a cleaner, more modern language; the
disadvantage is that you can't run crufty old MacLisp programs.
Because of its lexical scoping, T offers:
* A beautifully transparent way of mixing object-oriented programming
with traditional Lisp functional programming;
* A completely compatible compiler and interpreter;
* Compiled code fast enough to compete with Bliss and C (actually,
it's not that fast YET, but just wait a year or so!);
* Neat stuff like multiple namespaces (implemented as regular lexical
environments, without the overhead of separate symbol-tables etc.)
* Consistent terminology (e.g., NULL?, ATOM?, and LIST?, rather than
NULL, ATOM, and LISTP);
* A rich selection of data structures.
(Well, actually the last two aren't really because of lexical scoping).
Questions about T can be addressed to "T-Discussion@YALE" on the
ARPANET, or to
Jonathan Rees
Department of Computer Science
Yale University
P.O. Box 2158 Yale Station
New Haven, Connecticut 06520
[Disclaimer: there is a lot of personal opinion in this letter.
I believe, however, that it is relatively easy to determine what
is and what isn't.]
((name "Robert Munyer")
(address (uucp "...!decvax!genrad!wjh12!u:munyer")
(arpa "MUNYER@HARV-10")
(Snail "15 Waldo Ave, Somerville MA 02143")
(voice "(617)628-3718")))
P.S. Could you post this letter to net.lang.lisp for me?
I have read-only access to netnews from here. Thanks.