[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. ...


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

	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

	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.
	((Meaning 2) = (Meaning 3))  ==>  True,


	(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.  



%T A Lazy Evaluator
%A James H. MORRIS, Jr.
%B Third Annual ACM Symposium on Principles of Programming Languages (POPL)
%P 95-103
%D January 1976

%T CONS Should Not Evaluate its Arguments
%A David S. WISE
%J Automata, Languages and Programming: Third Int'l Coll.
%P 257-284
%I Edinburgh University Press
%D July 1976

%T Structure and Interpretation of Computer Programs
%A Gerald Jay 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


%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


%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
%D March 1987

Drew ADAMS, Laboratoires de Marcoussis, Centre de Recherche de la Compagnie 
            Generale d'Electricite, Route de Nozay, 91460 MARCOUSSIS, FRANCE
            Tel., adams@crcge1.cge.fr