[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Recognizing QUOTE deemed harmful to EVAL's laziness
WARNING: This is a bit long
In article 444 of comp.lang.misc Robert Firth writes:
... In applicative languages, repeated evaluations of an
expression always yield the same result, so we can replace
delayed evaluation by true lazy evaluation, ie evaluate
once only when first referenced. ...
SUMMARY:
I agree, but argue that this is not true of all applicative
languages; in particular, it's not true of pure LISP, due to its
treatment of quotation.
The meaning of the term "lazy evaluation" is not universally agreed
upon. Some use it to mean "call-by-need", i.e. the one-shot
evaluation referred to above. Others identify it with "call-by-name"
(or "normal order reduction" in the context of the lambda calculus
and combinatory logic.) "True" call-by-need is now more commonly
termed "fully lazy reduction" in functional programming circles.
Henderson & Morris and Friedman & Wise are usually credited with the
introduction of "lazy evaluation". I believe Wadsworth was the first
to speak of "call-by-need" and in any case he was the first to point
out the delicacies of "full laziness", although I believe the latter
term is due to Hughes. The concepts of different evaluation orders
are of course much older than these terms, predating the electronic
computer age [Church, Curry, Rosser].
The simple argument given above by Firth bears repeating and is the
basis for the assertion that "lazy evaluation and side effects don't
mix" (cf. Abelson & Sussman).
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.
"Reduction semantics" refers to the property of always being able to
replace an expression by its result, in the same definitional
context, without altering the result of the overall computation.
Because of this property, an expression and its reduction may thus be
said to "*denote* equivalent values". The property which Mr. Firth
referred to above, of obtaining the same result no matter how many
times an expression is evaluated, is implied by reduction semantics,
but not, I believe, by the semantics of pure LISP.
Of course, due to the possibility of side effects, in *impure* LISP,
re-interpretation of even the *same* code may produce different
results. Here, however, the issue is *repeated* interpretation of
code -- not that original source code is interpreted more than once,
but that the *result* of interpretation is then interpreted and
possibly re-interpreted ....
Once *reduction* of an expression is started we can assume that it
proceeds all the way to some kind of an irreducible (normal) form, so
that further attempts at reduction have no effect. In lazy
functional languages this final form is not usually "*the* normal
form" of the lambda calculus in which no redexes (reducible
subexpressions) appear, but the so-called "weak head", or "lazy"
normal form, in which only the outermost function application need be
irreducible. In reduction-based languages intermediate forms aren't
normally even available to the programmer. This is not a problem
semantically; one never need worry about reduction having "gone too
far", because the intermediate, as well as initial and normal forms,
may all be seen as equivalent.
I don't know what (pure) LISP's operational semantics should be
called. If it weren't already in use we might consider the term
"denotational" to characterise its *operational* semantics, since the
built-in recognition of quotation provides the ability to distinguish
*different levels* of representation of meaning.
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
equivalent; i.e. there are many contexts in which one can't be
replaced by the other without changing the overall meaning and
result. For example, if the value of FOO is defined to be 2 then
(NUMBERP FOO) is true (T), whereas (NUMBERP (QUOTE FOO)) is false
(NIL). (For simplicity, let's assume denoted values are always
expressions; values of the function represented by the functor QUOTE
are necessarily so.)
In a reduction-based language, if A is defined as B, and B as C,
reducing A gives C, and all three may be said to have equivalent
meaning, as determined, or shown, by the operation of the language's
equality predicate. In LISP on the other hand, if A is defined to
have the value B, and B to have the value C, evaluating A gives B,
not C. This behavior is due to the recognition of QUOTE. The
meaning of A isn't necessarily the same as that of B, let alone that
of C, as determined by LISP predicates such as EQ and EQUAL.
Denotation, unlike reduction, is leveled: A may denote B which
denotes C..., but we need not (indeed had better not) assume this
means, e.g., that A denotes C. Thus, if A (LISP-) evaluates to B,
and (independently) B evaluates to C, we can assume neither that A is
equivalent to C, nor that A denotes C. (In this case, the fact that
evaluation of A stops at B means that (QUOTE B) was necessarily
encountered during the evaluation of A.)
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 first of these is by definition unnecessary in a language
"tolerant of the undefined". By this I mean that undefined
expressions are simply regarded as irreducible (in normal form) and
provoke no error treatment. (By "undefined expression" I mean an
expression matching no definition left hand side.) Most "rewriting
systems" are so tolerant; most functional languages are not, although
many permit the declaration of constructions.
The second common use of LISP quotation may be motivated by concerns
of correctness, as well as efficiency. The correctness concern is
due to the fact that replacing an expression by its value doesn't, in
general, preserve semantic equivalence, as was indicated above.
Besides the special treatment of quotations, this is due to the
non-declarative nature of (impure) LISP. The efficiency concern is
due to the "eager" (non-lazy) nature of LISP. Even if it would not
be incorrect in a given situation to evaluate certain expressions, it
may be advisable on efficiency grounds to postpone their evaluation,
perhaps indefinitely.
Reduction semantics dispense with the first of these concerns, and
lazy interpretation (*normal order* reduction) may be used to
alleviate the second: subexpressions of an interpreted expression
are not necessarily reduced. In LISP, for example, one often places
oneself at a meta-level to construct some code which is passed around
and manipulated, and then at an opportune moment is executed. In a
lazy language such code need not be treated as quotation: as long as
its interpretation isn't needed by the functions which pass it around
it won't be reduced. Even without laziness, as long as the code is
underdefined little or no reduction can take place, so that code may
be constructed directly without it needing to pass through a phase
where it takes on the form of a construction such as a list. (A
function application may be underdefined either because all its
arguments are not yet present ("partial parameterization") or because
no definition for it has yet been interpreted.)
In other words, QUOTE is mainly used by LISP programmers to offset
the eagerness of EVAL. If one weren't afraid of throwing oil on
forscoming lithpian flames (this one can feel the heat already) one
*might* argue that, as all computation in LISP is evaluation (in a
denotational sense), the programmer is obliged to conceptually move
up and down between semantic levels that are essentially artificial
in a purely declarative setting. They don't correspond to her
conception of the meaning of the program but rather function as an ad
hoc mechanism to keep the eagerness of EVAL at bay. She in fact
eventually learns to ignore or abstract from them when mentally
interpreting code. LISP requires programmers to employ quotation
even when it serves no apparent semantic purpose. (Such overuse
would of course be greatly reduced were programmers not obliged to
consider also the side effects and referential opacity of (impure)
LISP.) (Cf. Wadler)
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
need it.
Consider the hypothetical question
"What is the denotation of ((3 - 7) + (4 / 2)) * 6 ?".
A reduction interpreter is only in effect able to respond
"It's the denotation of -12, whatever that may be".
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. (Function
application is represented here by juxtaposition: Sin 3.14159, not
sin(3.14159)):
Meaning -12 = Overdrawn
Suppose now that OVERDRAWN in turn is defined (though its *meaning*
is not):
Overdrawn = More-debits-than-credits
where the right hand side is simply an undefined term. If this is
the case then the original request is reduced as follows:
Meaning (((3 - 7) + (4 / 2)) * 6)
==> Meaning -12 ==> Overdrawn ==> More-debits-than-credits
Of course, this result has nothing to do, a priori, with the
*meaning* of the expression OVERDRAWN. The latter (which is the same
as the *meaning of the meaning* of the expression -12) might be
defined:
Meaning More-debits-than-credits = Spendthrift
Assuming, again, that the right hand side is undefined, we have:
Meaning Overdrawn
==> Meaning More-debits-than-credits ==> Spendthrift
Such a simple denotational mechanism makes no assumption about the
meanings of constructions (undefined terms) such as, e.g., that they
denote themselves. In this it is a more flexible device than that
provided by LISP's EVAL. If 5 is a construction, then, although 5
*reduces* to itself (i.e. is irreducible), the MEANING of 5 is not 5
(or anything else) by default, nor are we prohibited from defining it
to be 6. This is a good reminder that denotational evaluation need
not be equivalence-preserving. For, while in our own eyes and the
eyes of a function such as MEANING we may identify, say, 2 and 3 by
defining their MEANINGs to both be, say, 7, or RHUBARB, or whatever,
this equivalence is fictive as far as the interpreter is concerned.
Then:
((Meaning 2) = (Meaning 3)) ==> True,
whereas
(2 = 3) ==> False.
More importantly, it is not even operationally possible for us to
assign two expressions which have the same normal form, such as
(2 + 2) and 4, different meanings.
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
Note incidentally that we are of course in no way limited to a single
MEANING function, but may easily define as many different denotations
as we like. Likewise it might sometimes be useful to have various
quoting constructors. Such constructors are in effect used to
establish different denotational levels (meta, meta-meta, etc.), and
having different such quoting devices would allow different meaning
functions to move differently among the various levels, even with
respect to the same argument expression.
Similarly, a given meaning function might recognize more than one form
of quotation. E.g.,
My-meaning (My-quote x) = x
Your-meaning (Your-quote x) = x
Your-meaning (My-quote x) = Nonsense!
Then, for example:
My-meaning (My-quote Foo) ==> Foo
Your-meaning (My-quote Foo) ==> Nonsense!
My-meaning (Your-quote Foo) ==> My-meaning (Your-quote Foo)
[already in normal form]
To recapitulate, the argument I have with (pure) LISP's EVAL (leaving
aside side effects and eagerness) is not that it is denotational, but
that it's recognition of quotation is omnipresent. It is as though
LISP were a reduction interpreter that automatically provided a
function such as MEANING, respecting quotation, with every prompt.
That is, one might say that every expression FOO evaluated by LISP is
first regarded as (MEANING FOO), and is then reduced. It is
difficult in general to ask LISP for a simpler version of the same
expression; EVAL looks for meaning behind each input. In a reduction
setting on the other hand, denotational evaluation is still
available, using only the mechanism of reduction, just by defining
explicit denotation functions such as MEANING.
References:
==========
Laziness:
--------
%T A Lazy Evaluator
%A Peter HENDERSON
%A James H. MORRIS, Jr.
%B Third Annual ACM Symposium on Principles of Programming Languages (POPL)
%P 95-103
%I ACM
%D January 1976
%T CONS Should Not Evaluate its Arguments
%A Daniel P. FRIEDMAN
%A David S. WISE
%J Automata, Languages and Programming: Third Int'l Coll.
%P 257-284
%E S. MICHAELSON and R. MILNER
%I Edinburgh University Press
%D July 1976
%T Structure and Interpretation of Computer Programs
%A Harold ABELSON
%A Gerald Jay SUSSMAN
%A Julie SUSSMAN
%I The MIT Press and McGraw-Hill
%C Cambridge, Massachusetts, and New York
%D 1985
"Full" laziness:
---------------
%T Semantics and Pragmatics of the Lambda-calculus
%A Christopher Peter WADSWORTH
%I Oxford University
%D September 1971
%O Ph.D. Thesis
%T Design and Implementation of Programming Languages
%A Robert John Muir HUGHES
%R Technical Monograph PRG-40
%I Oxford University Computing Laboratory, Programming Research Group
%C Oxford
%D July 1983, as monograph September 1984
%O Ph.D. Thesis
Reduction:
---------
%T The Calculi of Lambda-Conversion
%A Alonzo CHURCH
%J Annals Math. Studies
%V 6
%I Princeton University Press
%C Princeton, New Jersey
%D 1941
%T Combinatory Logic
%A Haskell B. CURRY
%A Robert FEYS
%A William CRAIG
%V 1
%I North-Holland
%C Amsterdam
%D 1968
%T Highlights of the History of the Lambda Calculus
%A J. Barkley ROSSER
%J Annals of the History of Computing
%V 6
%N 4
%P 337-349
%I American Federation of Information Processing Societies
%D October 1984
Quotation:
---------
%T A Critique of Abelson and Sussman - or - Why Calculating is
Better Than Scheming
%A Philip WADLER
%J SIGPLAN Notices
%V 22
%N 3
%P 83-94
%I ACM
%D March 1987
--
Drew ADAMS, Laboratoires de Marcoussis, Centre de Recherche de la Compagnie
Generale d'Electricite, Route de Nozay, 91460 MARCOUSSIS, FRANCE
Tel. 64.49.11.54, adams@crcge1.cge.fr