arun@mandrill (Arun Lakhotia) (03/04/88)
R. O'Keefe passing comment (on comp.lang.prolog) about using Partial
Evaluation to translate Grammar Rules to Prolog led me to read Periera
and Shieber's, "Prolog and Natural-Language Analysis".
After reading the book, referred to as P&S or the book, I have the
following comments to make about it. They are especially concerning
Partial Evaluation. I have some comments about their meta-programming
style too.
Before I get critical let me state the most positive comment I have:
P&S has the shortest, cleanest and most complete PE-ator code that I
have seen in *print*. Complete in the sense that besides the kernel
of PE, the book also shows organization of the code that drives the
``partially_execute/2'' predicate, and organization of the program
to be partially evaluated.
While it has a very neat implementation for PE, the book fails on many
grounds.
1. It does not introduce, address or even hint at what partial
execution actually means. All P&S have to say is that ``it is a
device of general utility for manipulation of Prolog programs. It
involves replacing of certain computations that would normally be
performed at execution time by changes to the program itself'',
page 98.
2. It fails to give adequate references to literature on PE in logic
and/or functional programming paradigm.
On page 135 P&S say: ``PE has long been in the folklore of
logic programming. The notion is implicit in Kowalski's connection
graph resolution proof procedure (1975; Eisinger, 1986).'' They then
go on to talk about `unfolding' [Burstall & Darlington, Tamaki &
Sato etc.]
On page 209 again they refer to some work by Kahn (1982); Takeuchi &
Furukawa (1985). And say ``Much of what is done in this area by
logic programming researchers is still unpublished...''.
By 1987, when the book was published, there had been a significant
amount of work done on PE in the functional programming paradigm.
The landmark papers by Ershov (1977), Jones et al (1985), Futamura
(1971, 82), all appeared much before the book probably went to
print. (A detailed bibliography on PE has appeared in a recent
issue of SIGPLAN.)
3. PE is a more powerful tool than what P&S has portrayed. However, to
understand the beauty of their implementation, it is necessary for
one to be familiar with the notion of PE and the problems related
with it. I believe the book is not intended to be a tutorial in PE.
Just for that reason it makes sense to give the right pointers into
the literature. Otherwise, a whole lot of what they do would make
sense only to people who know what PE is.
4. They consistently use the phrase ``partially execute with respect
to X predicate''. It is not consistent with the phrase
conventionally used in the PE literature, which is ``partial
evaluation with respect to *some data*''. However in the hierarchy
of meta and object, the predicates that they `usually' *unfold* are
at object level and hence may be interpreted as data for the
meta-level.
5. The classification of the interpreter and its data into
program_clause/1 and clause/1 seems to be a solution to a central
problem in PE ie. ``When to stop unfolding''. They take a nice
approach to tackle it without explicitly addressing the problem
itself.
From a software engineering point-of-view and general applicability
of their technique. I find this approach questionable. The idea of
throwing some clauses of essentially the same procedure into two
different clause category, some in program_clause/1 and others
clause/1, bothers me. If the justification is that ``it works in
the case of examples in the book'', then i wouldn't buy it.
6. The beauty of PE is in its application as a compiler,
compiler-compiler and compiler-compiler generator, as projected by
Futamura (1971, 82). P&S, however, fail to do justice to PE by not
mentioning anything about these projections, though they give an
exercise (Problem 6.14 page 207) to partially execute the partial
executor...
7. In their examples P&S use PE as ``compiler''. Neither do they
mention ``compiler generator'' nor anything about self-application
of PE to ``generate a compiler''. With this background their
following statements on page 178 (section 6.4.3)
``The technique used here to build the DCG compiler is quite
general. The `compile' and `partially_execute' predicates can
be thought of together as a metacompiler, in that they will
convert `any'interpreter for a language written in pure Prolog
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
into a compiler for the same language''.
^^^^^^^^^^^^^^^
may be confusing to a novice.
In Exercise 6.8 on the same page their use of the phrase ``using the
compiler generated from the Prolog interpreter'' is incorrect in the
context of the book. P&S do not *generate* a compiler anywhere in
the text.
8. Comment on Meta-programming style.
P&S require the object program that is to be *interpreted* be
available as a set of *clause/1 facts*, page 160-161. Thus to
interpret itself the interpreter should be available as data too.
Whether a program interpreting some data, which is *copy* of itself,
is self-application may be debateable.
I strongly disagree with P&S in their meta-programming style, and
prefer that of Bowen, Shapiro, Sterling and others. The latters use
the clause/2 builtin, which enables referring to program and data in
the uniform manner.
I cannot understand why P&S did not use clause/2. The closest I can
get to is that -- using clause/1 (and program_clause/1) they find a
very simple mechanism for stopping the partial execution.
Arun
PS: This note is cross posted to
comp.lang.prolog,
prolog-pe@mandrill.cwru.edu
and pe-forum@hplb.csnetok@quintus.UUCP (Richard A. O'Keefe) (03/04/88)
In article <2374@mandrill.CWRU.Edu>, arun@mandrill (Arun Lakhotia) writes: > 1. It does not introduce, address or even hint at what partial > execution actually means. All P&S have to say is that ``it is a > device of general utility for manipulation of Prolog programs. It > involves replacing of certain computations that would normally be > performed at execution time by changes to the program itself'', > page 98. Giving some examples and showing what they do doesn't count as "even hinting"? "Replacing execution time computations" doesn't count as introducing or hinting? > 2. It fails to give adequate references to literature on PE in logic > and/or functional programming paradigm. The book is about natural language processing, not about partial execution. There are differences between partial evaluation and partial execution (classical Horn clause programs do no evaluation: unfolding code gives you more code, never data). The question is "what are adequate references"? In a book whose major aim is another topic entirely, I contend that "adequate references" means "enough basic references to get you _started_". If you would care to supply, say, five key references to partial- execution-and-logic-programming, I would very much like to have them. > 4. They consistently use the phrase ``partially execute with respect > to X predicate''. It is not consistent with the phrase > conventionally used in the PE literature, which is ``partial > evaluation with respect to *some data*''. However in the hierarchy > of meta and object, the predicates that they `usually' *unfold* are > at object level and hence may be interpreted as data for the > meta-level. > In (pure) logic programming, a predicate *is* data at any level. What Pereira & Shieber are in fact doing is building the information in a predicate into the rest of the program, so the phrase is apt. It's not an object/meta distinction: the point is that in the functional world constants and function applications belong to a common class, whereas in Horn clause programming terms are terms and literals are literals. Even if you supply your data by adding a goal Var=Term, you have fed in a *literal*. > 6. The beauty of PE is in its application as a compiler, > compiler-compiler and compiler-compiler generator, as projected by > Futamura (1971, 82). P&S, however, fail to do justice to PE by not > mentioning anything about these projections, though they give an > exercise (Problem 6.14 page 207) to partially execute the partial > executor... > "As projected." "Projections." Pereira & Sheiber are talking about *applications*, not *promises*. Certainly work continues in this area, and some impressive things are being reported. But where can I get one? > 8. Comment on Meta-programming style. > > P&S require the object program that is to be *interpreted* be > available as a set of *clause/1 facts*, page 160-161. Thus to > interpret itself the interpreter should be available as data too. > Whether a program interpreting some data, which is *copy* of itself, > is self-application may be debateable. > > I strongly disagree with P&S in their meta-programming style, and > prefer that of Bowen, Shapiro, Sterling and others. The latters use > the clause/2 builtin, which enables referring to program and data in > the uniform manner. > > I cannot understand why P&S did not use clause/2. The closest I can > get to is that -- using clause/1 (and program_clause/1) they find a > very simple mechanism for stopping the partial execution. > There is a very simple reason for not using clause/2. In many Prolog systems (ALS Prolog and Prolog-X are exceptions) clause/2 DOES NOT APPLY to compiled code, and indeed, in some systems clause/2 only applies to explicitly designated :- dynamic predicates. Don't you think "it wouldn't *work*" is a good reason for not doing it? The question of whether clause/2 *should* apply to every user-defined predicate (it obviously isn't going to do much with assembly-coded primitives) is one question. Given that it *doesn't* in many Prologs (including DEC-10 Prolog, for example; and indeed I believe all the Prolog systems used in the CSLI courses this book was written to go with) it would have been irresponsible of Pereira & Shieber to tell their students to use a coding style that wouldn't work. I begin to understand Ross Overbeek's reaction to my review of Warren & Maier's book. I hasten to add that I don't think _their_ references are inadequate for their purpose. > PS: This note is cross posted to > comp.lang.prolog, > prolog-pe@mandrill.cwru.edu > and pe-forum@hplb.csnet What are the other two mailing lists? If there are mailing lists concerning logic-programming-and-partial-execution, I would like to be on them, though I haven't anything to contribute.