[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Recognizing QUOTE deemed harmful to EVAL's laziness
I too am quite perplexed by Drew's essay.
I would only add one change to the argument: full laziness lends
itself most naturally not to applicative (functional) languages in
general but, more precisely, to those respecting "*reduction*
semantics". In particular, the purely functional language "pure
LISP" (without side effects but with built-in quotation) does *not*
respect such semantics and is thus not easily made (fully) lazy. The
issue is quotation. Without its built-in recognition of quotation
LISP otherwise has reduction as its operational semantics.
To be "applicative" or "purely" functional a language must be
"referentially transparent", meaning that the same expression, in the
same definitional context, is always evaluated to the same result.
Pure LISP has this property.
I don't see how. A counterexample, assuming FOO is bound to 2 in the
(QUOTE FOO) -> (QUOTE 2) by innermost reduction
But (QUOTE FOO) and (QUOTE 2) are different objects. Indeed, the term
"referential transparency" was coined by logicians precisely to
distinguish between things like (QUOTE FOO) and FOO. (QUOTE FOO)
"mentions" FOO, whereas FOO (or (+ FOO 1)) "uses" it. Referential
opacity is not necessarily bad. It is bad only if it is ambiguous
whether a particular occurrence of a symbol denotes a "mention" of it,
or a "use" of it. The point of QUOTE is precisely to eliminate any
such ambiguity, by distinguishing mentions from uses. The reduction I
showed above is thus invalid, because (QUOTE FOO) clearly means a
mention of FOO, so I can't replace FOO by something equivalent to it.
The LISP expression (QUOTE FOO) might be said in a sense to denote
the expression (value) FOO to which it evaluates, but the two aren't
Precisely. They aren't equivalent. So, why say that (QUOTE FOO)
denotes FOO? The confusion is probably caused by the fact that a Lisp
interpreter prints FOO rather than (QUOTE FOO) when we type in
(QUOTE FOO). I do wish Lisp interpreters didn't do that. They should
print (QUOTE FOO) to be precise. But, they print FOO for the sake of
convenience, I presume. Since FOO can never be the normal form value
of any expression (if FOO is bound, then its binding is the normal
form and, if it is unbound, then it is an error) they print FOO and
expect the user to understand it as (QUOTE FOO).
Having such a denotation mechanism available in a language
facilitates a leveled view of things. However, it would seem that
most programmer use of quotation in LISP doesn't really involve
intentional semantic leveling. The most frequent uses of quotation
in LISP would appear to be:
* to prevent the attempted evaluation of something which is
undefined, together with the ensuing error treatment
* to prevent the immediate evaluation of a defined expression
because the moment isn't right.
The most common use of quotation is merely to denote data objects.
Since Lisp does not have a separate syntax for data objects and
programs (which many Lispers consider to be an asset), data objects
are treated as "mentions" of S-expressions and programs are treated as
"uses" of them. This is one way of doing it. There are other ways,
of course. Prolog uses different syntax for atoms and variables.
Pascal and ML use declarations for atoms and constructors. Using a
normalizer instead of an evaluator (which Drew mentions later) is
another way. But, there are strong arguments against normalizers.
Firstly, they are inefficient compared to evaluators. Secondly, when
there is an error it is better to tell the user about it immediately
rather than printing a large expression and expecting the user to
search for the erroneous application in it.
The use of quotation for delayed evaluation is now widely recognized
to be misguided. Modern Lisps, such as Scheme, have constructs like
"delay" to achieve lazy evaluation.
Likewise, it would seem that in our daily reasoning we are rarely
conscious of using more than few semantic levels at once.
Nevertheless, there *are* times when a device for manipulating
programmer-defined levels of denotation is useful. Implementation/
manipulation of languages is a typical example where quotation is
appropriate. As such leveling is a very powerful abstraction
construct, it would be desirable not to have to do without denotation
in opting for reduction semantics. One would like to be able to
define meta-meta-levels, and so on. Fortunately it's easy to have
our cake and eat it too in a reduction-only setting by simply
programming quotation/denotation *explicitly* for use just where we
But suppose now that for a given application a programmer wants to
consider that the true meaning of -12 is, say, the object represented
by the expression OVERDRAWN. It's straightforward to define a
function MEANING which will perform such an EVALuation.
Such a MEANING function can be defined in any Lisp as well. (It is no
different from any other function). If such a MEANING function
differes from the standard meaning in minor ways, then Lisp allows you
to share it by calling EVAL from your MEANING function. If you indeed
want to use the standard meaning it should not be necessary to write a
brand new interpreter.
The quotation mechanism itself may of course be provided quite simply
by the general rule:
Meaning (Quote x) = x
where QUOTE is simply a constructor (undefined symbol). Then:
Meaning (Quote -12) ==> -12
This works only if outermost evaluation is the default (standard)
evaluation of the language. All Lisps use innermost evaluation
(though other modes of evaluation are provided by constructs like
"delay", "freeze" and "future"), so this trick does not work. It is
by no means universally accepted that outermost evaluation as the
default is "good", and many people who work with outermost evaluation
have reservations about using it as the default.
Drew ADAMS, Laboratoires de Marcoussis, Centre de Recherche de la Compagnie
Generale d'Electricite, Route de Nozay, 91460 MARCOUSSIS, FRANCE
Tel. 18.104.22.168, email@example.com
In summary, I can see no difference between "applicative semantics"
and "reduction semantics". The question of referential transparency
is orthogonal to applicative semantics. I believe Drew's comments are
largely motivated by the minor misuse of notation by Lisp interpreters
in not printing the outermost QUOTE.