Recognizing QUOTE deemed harmful to EVAL's laziness

[reddy@b.cs.uiuc.edu (Uday S. Reddy)]

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
context:
	(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
   equivalent;

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
   need it.  

   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. 64.49.11.54, adams@crcge1.cge.fr


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.  

Uday Reddy
reddy@a.cs.uiuc.edu