Path: utzoo!mnetor!uunet!husc6!sri-unix!quintus!sun!decwrl!decvax!mandrill!arun From: arun@mandrill (Arun Lakhotia) Newsgroups: comp.lang.prolog Subject: Comments of Periera & Shieber wrt Partial Evaluation Message-ID: <2374@mandrill.CWRU.Edu> Date: 4 Mar 88 00:36:51 GMT Sender: arun@mandrill.CWRU.Edu Reply-To: arun@mandrill (Arun Lakhotia) Organization: CWRU Dept of Computer Engineering and Science Lines: 128 Keywords: Partial Evaluation, Meta-programming, Comments 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