adams@crcge1.UUCP (Drew Adams) (07/23/87)
Further References
------------------
I neglected to mention that the idea that QUOTE is properly treated
as a constructor (in a reduction setting) is due to Alan Robinson.
Thanks to Jan Prins for reminding me.
Here's the paper where he discusses denotation vs. reduction with
respect to quote. I don't know of a more recent one.
%T New Generation Knowledge Processing
%A J. A. ROBINSON
%R First Annual Progress Report
%I Syracuse University
%C Syracuse, New York
%D December 1984
That paper introduces the "unknown-tolerant" fully lazy functional
logic language SUPER being developed at Syracuse University. The
essential reference dealing with the functional basis of SUPER is:
%T A Fully Lazy Higher Order Purely Functional Programming Language
with Reduction Semantics
%A Kevin J. GREENE
%I Syracuse University
%C Syracuse, New York
%D August 1985
%O Ph.D. Thesis
Thanks also to Stan Shebs for reminding me of Brian Smith's work on
3-LISP, which (among other things) is another attempt to clean up the
semantics of quotation (and more). Here are two accessible
references.
%T The Implementation of Procedurally Reflective Languages
%A Jim des RIVIERES
%A Brian Cantwell SMITH
%B ACM Symposium on LISP and Functional Programming
%C Austin, Texas
%I ACM
%P 331-347
%D August 6-8, 1984
%T Reflection and Semantics in Lisp
%A Brian Cantwell SMITH
%B Eleventh Annual ACM Symposium on Principles
of Programming Languages (POPL)
%C Salt Lake City, Utah
%I ACM
%P 23-35
%D January 15-18, 1984
In case some who read this didn't see Stan's message, here is part:
"His basic point of view is that quoting is important to
distinguish levels of meta-ness, and so quoted objects
are promoted to first-class types known as handles.
There are operations UP and DOWN that add and remove
handles, since evaluation does not; (eval '2) => '2.
Also, (+ 2 '3) is an semantic error, like taking the car
of an number.
In other words, Smith also uses an essentially *reducing* EVAL,
separating out a separate denotation mechanism.
--
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.fradams@crcge1.UUCP (Drew Adams) (07/23/87)
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
(QUOTE FOO)."
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"
and
"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
mechanism,
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:
To J. REES:
----------
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
expression
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.
To U. REDDY:
-----------
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
FOO?"
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).
Then:
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. 64.49.11.54, adams@crcge1.cge.fr