[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Recognising QUOTE deemed harmful to EVAL's laziness

WARNING: Too long (again!)

Regarding My Original Posting and Replies:

Thanks for the commentaries.  I'm sorry my posting wasn't clearer 
(and shorter).  I wish this reply were shorter as well.

FIRST, some general remarks aimed to clear up misunderstandings due
(I think) to terminology, etc..  

1) By EVAL I mean the LISP (or SCHEME) interpreter itself, as well as
explicit calls to  the procedure  EVAL in  the program.   Some people
quite naturally assumed I mean the latter only,  thus wondering about
the "relevance to SCHEME (which has no EVAL)".  [J.  Rees]

2)  DELAY/FORCE  vs.    QUOTE/EVAL:    The  former are  used in eager
implementations  to  simulate   (program,  implement,   etc.)    lazy
evaluation.  E.g., Uday Reddy mentions that 

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

DELAY  and  FORCE  achieve  "call-by-name" which  is sometimes called
"laziness", but they don't  usually achieve  "*full* laziness", (what
Robert Firth called "true laziness"  in the  original posting), which
was the  issue under  discussion.   My point  has nothing  to do with
whether or  not people  would be  better off  avoiding QUOTE/EVAL and
using  DELAY/FORCE.    My  point  is  that  implicit  recognition  of
quotation by the interpreter (EVAL) gets in the way of *implementing*
(in the interpreter)  full laziness,  as repeated  evaluations of the
same  (quotation)  expression  *don't*  yield  the same  result.  
[A. Freeman, U.  Reddy] 

3) I think the biggest communication problem arose from my not making
sufficiently  clear  that  I'm  not  concerned  with  differentiating
external expressions from internal data  structures etc.,  as well as
 from the different meanings "expression",  "symbol" etc.   might have
in different communities.  I'm  ignoring what  goes on  inside a LISP
implementation   (data   structure   representation,   binding  etc.)
completely and am referring only  to externally  observed behavior as
determined by input and output *expressions* (= Sexprs).   Thus, when
I refer to the "result" or "value" of  an expression  I by definition
mean the printed result.  An example of the confusion [U.  Reddy]:  

	"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 

I equate the expression FOO with its binding, as the normal form.  If
unbound, I consider the expression FOO itself to be the normal form.
[J.  Rees, A.  Freeman, U.  Reddy] 

4) When I speak of that which  is "denoted"  by an  expression I mean
(in LISP) the  printed result  of the  expression, and  I equate this
with whatever the programmer might have  in mind  that the expression
represents *for her*.  Thus, in this view everything is regarded only
in its external aspect, as an expression, and all  denoted values are
themselves expressions.  Hence I wrote:  

	"(For simplicity, let's assume denoted values are always
	 expressions; values of the function represented by the 
	 functor QUOTE are necessarily so.)  

An  expression  then  *is*  "use"  of  that  expression  and a quoted
expression is  "mentioned" (although  the entire  quotation itself is
"used",  the  "use"  of  the functor  QUOTE serving  to "mention" its
argument.)  [U. Reddy]

5) When I speak of two expressions being denotationally *equivalent* 
I thus mean 
	a) they both mean the same thing to the programmer,
	b) they have the same operational behavior; that is, the
	   function (EVAL, MEANING etc.) which identifies their 
	   meanings returns the "same" result for both,
	c) "same", or "equivalent" *meaning* is operationally
	   determined (defined) by the interpreter's equality 
	   predicate itself (EQ, EQUAL, =, etc.)
This is why I referred to
	"equivalent meaning, as determined, or shown, by the operation  
	 of the language's equality predicate"
	"meaning ... the same as ... as determined by LISP predicates 
	 such as EQ and EQUAL"
[U. Reddy]

6)  Of  course LISP  may be  made lazy,  the function  MEANING may be
programmed in LISP,  the LISP  evaluator may  be rendered QUOTE-less,
etc..  My point was rather that 

	a) it's simple to leave quotation recognition out of LISP 
	   *to begin with*, 
	b) the result of doing so is a *reduction* engine, no more, 
	   no less, 
	c) a function such as MEANING, to perform what I'm calling 
	   denotation, is simple to define in a reduction setting,
	   so that LISP's implicit recognition of quotation *isn't
	   necessary* in order to have a useful denotation 
	d) without getting rid of LISP's automatic treatment of 
	   quotation it's not *simple* (direct, straightforward, 
	   etc.) to implement lazy interpretation.
[J. Rees, A. Freeman, U. Reddy]

SECOND, a few specific comments on some of the replies:

1)  I admit I'm not sure I understand your proposal correctly.
I think you mean to
	(1) keep the standard LISP (or SCHEME) interpreter but 
	    replace explicit programmer calls to the procedure 
	    EVAL by calls to NORMALIZE.
	(2) reserve quotation for things that aren't self 
	    evaluating (i.e. "things  which don't [I assume you 
	    mean 'do'] need it")
	(3) change PRINT a bit so that the printed result of 
	    evaluation is always a quotation or a self-evaluating
I don't see how this provides reduction semantics.  Let's leave aside
(1) for the moment,  assuming nobody  explicitly normalizes anything.
Here's the  original example  I gave,  with some  cosmetic changes to
protect the innocent:  

	if the value of FOO is defined to be BAR then (EQUAL 'BAR FOO)
	is true (T), whereas (EQUAL 'BAR 'FOO) is false (NIL).

Thus FOO and (QUOTE FOO) *aren't* equivalent, as determined by
EQUAL, yet the former is the result of interpreting the latter.
Such an interpretation isn't, therefore, a reduction.

Now, let the value of BAR be TOTO.  Then,  asking for  the meaning of
the meaning of FOO:   (NORMALIZE  FOO) gives  (QUOTE TOTO).   Why not
TOTO?  I think that you, as well as U.  Reddy (see  number 3), below)
and perhaps  others, were  aiming at  a different  kind of denotation
mechanism  than  what  I  had  in  mind:   one that,  instead of just
removing a  level of  "mention", returns  a *mention*  of the denoted
value.    Anyway,  that's  what I  understand from  your treatment of
PRINT, etc..  That's fine too, although in that case I  would opt for
consistency  in  the  case  of  numbers,  strings,  etc.   too.  Such
consistency is important, if not always  for users  in an interactive
setting,  at  least  for *programs*  that might  manipulate or reason
about evaluation results.  

1) Here's your

 	"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"

As mentioned  above, I'm  using the  interpreter's equality predicate
(e.g.  EQUAL) to  measure semantic  equivalence.   Assuming this, and
assuming  that  we're  both  talking expression  reduction and aren't
concerned  with  LISP  "objects"  as  different  from  their external
Sexprs,  I don't  agree that  the values  denoted by  (QUOTE FOO) and
(QUOTE  2)  are  different.    (EQUAL (QUOTE  FOO) (QUOTE  2)) ==> T.
Likewise:  (EQUAL FOO  2) ==>  T.   The two  quotations "mention" the
*same* (as judged by EQUAL) value, which  happens to  have (at least)
two names:  FOO and 2.  

This  of  course means  that reduction  rules are  not to  be used to
establish values (in the sense of meanings), but rather equivalences.
 From the moment that we equate two  expressions via  a reduction rule
we no longer have any  external way  to distinguish  them; we've just
declared them to be indistinguishable.  This means that if we want to
differentiate, we must do it at an external meta-level:   *we* (or an
external  program)  can  *see* a  difference between  (QUOTE FOO) and
(QUOTE  2).   By accepting  to recognize  such a  difference we place
ourselves at a meta-level *unknown to the interpreter*.   This is not
a meta-level *defined*  to the  interpreter via  MEANING.   It is not
even definable, once we've declared FOO and 2 to be indistinguishable.  

2) Regarding (QUOTE FOO) and FOO, you write:
	"They aren't equivalent.  So why say that (QUOTE FOO) denotes

Would you be happy reading "mentions" for "denotes"?   Be happy then;
that's  what  I  mean  by  "denotes".    QUOTE mentions  and EVAL (or
MEANING) returns the value mentioned by a quotation.  I say "denotes"
because I want to use EVAL/MEANING for other than just quotations.  

3) You write:

	"Since LISP does not have a separate syntax for data objects
	 and programs ..., data objects are treated as "mentions" of 
	 S-expressions and programs are treated as "uses" of them."

Exactly.  This is one of my points, that LISP  obliges the programmer
to use the *same* mechanism/notation when  expressing data structures
etc. as when shifting semantic levels.  I wrote:

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

The last line would  be better  written "serves  a different semantic
purpose, if any".  

4)  You  mention  that  "[normalizers]  are  inefficient  compared to
evaluators."  How does taking quotation recognition out  of pure LISP
leave it less efficient?  The answer, I  suppose, is  that some other
mechanism must  then be  found for  preventing unintended evaluation.
Normal order reduction is an obvious  candidate, and  is perhaps what
you had in mind.  It is indeed in general  less efficient.   But it's
not the only mechanism possible.  Wouldn't it be desirable to perform
strictness analysis to find arguments to be interpreted "by-value"?  

5) I wrote:

	"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).  

		   Meaning (Quote -12)  ==>  -12"

You write:

	"This works only if outermost evaluation is the default 
	 (standard) evaluation of the language."

I  can see  why you  might say  this, considering  the confusion over
number 1), above.  Otherwise, I can't see why this would be true.  As
reduction is equivalence-preserving, it can't matter  where you start
reducing,  inside,  outside,  mix  and  match, ....   (excepting,  of
course, non-terminating interpretation).  

6) You write:

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

I agree.  You and I are both, I believe, two such people.   I mention
this  so  folks  who aren't  familiar with  your work  may  know that
you're "lazier" than your reply might indicate.   :) 


As I'm going on vacation for a month I won't be around to keep up the
provocation.  I look forward however to  seeing how  things will turn
out.  Again, thanks for the comments and sorry about  the confusion &
length.  -- drew

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