🚀 go-pugleaf

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