ok@quintus.uucp (Richard A. O'Keefe) (09/01/88)
In article <1416@kulcs.kulcs.uucp> bimbart@kulcs.UUCP (Bart Demoen) writes: >Tutorial No:8 of LP'88 Seattle (R. O'Keefe) makes 'interesting' reading, but >don't think that the topics were completely exhausted; here is an example: Again, how very 'kind'. No topic in _any_ book is "completely exhausted". >Section 9 p.106 shows some meta-interpreters >and their timings on naive reverse. Lest anyone who has not read the section be misled, it is worth pointing out that the text makes no optimality claims, and that Demoen's interpreter can easily be derived from the ones presented there by following the suggestions in the last paragraph of the section. You have to stop _somewhere_. Demoen's interpreter would look something like this: prove_goal(Goal) :- % This is the entry point into the prove_goals([Goal]). % interpreter; it isn't called again. prove_goals([]). prove_goals([Goal|Goals]) :- rule(Goal, Body), prove_goals(Body), prove_goals(Goals). rule(rule(X,Y), []) :- % each built-in predicate has a rule(X, Y). % linkage clause like this one. rule(prove_goal(X), Goals) :- % For each predicate p(X1,...,Xn), prove_goal_(X, Goals). % there is a clause in this table rule(prove_goals(X), Goals) :- % of the form prove_goals_(X, Goals). % rule(p(X1,...,Xn), Goals) :- rule(reverse(X,Y), Goals) :- % p_(X1, ..., Xn, Goals). reverse_(X, Y, Goals). % A clause p(T1,..Tn) :- G1,..,Gk rule(append(X,Y,Z), Goals) :- % turns into an interpreter clause append_(X, Y, Z, Goals). % p_(T1, .., Tn, [G1,..,Gk]). prove_goal_(Goal, [ % These two predicates and prove_goals([Goal]) ]). % the corresponding clauses in prove_goals_([], []). % rule/2 are present so that prove_goals_([Goal|Goals], [ % the interpreter can interpret rule(Goal, Body), % (a variant of) itself, and can prove_goals(Body), % interpret that interpreter prove_goals(Goals) ]). % interpreting itself and so on. reverse_([], [], []). % These two predicates and reverse_([H|T], R, [ % the corresponding clauses in reverse(T, L), % rule/2 are the definition of append(L, [H], R) ]). % naive reverse which serves append_([], R, R, []). % as a test case; they are not append_([H|T], L, [H|R], [ % needed by the interpreter as append_(T, L, R) ]). % such. It is easy to make a tail-recursive difference-list version: prove_goal(Goal) :- prove_goals([Goal]). prove_goals([]). prove_goals([Goal|Goals]) :- rule(Goal, Goals1, Goals), prove_goals(Goals1). The speeds I measured on a Sun-3/50 running Quintus Prolog 2.3 were rule/3 demoen/2 demoen/3 Task plain 5.5 6.4 6.2 prove(reverse([1,..,30],_)) iterated 2.4 2.4 2.8 prove(prove(reverse([1,..,30],_))) where rule/3 is the fastest version described in the tutorial, and demoen/2 and demoen/3 are the versions shown and outlined above. Well, do I have any excuse for not having described these faster versions in my tutorial? Several. a) The goal of the section was to develop a *clean* interpreter. The point of showing several variants was just to show that, to quote the summary: Interpreters are just programs that do things with trees, and can be optimised and combined just like other programs. b) One of the themes of the chapter is, to quote the summary: Unfolding can be used to "compile away" an interpreter. I believe that the rule/3 version makes a better basis for this than Demoen's version. The next draft of this chapter will show the actual operation of an unfolding program on some small examples. You'll note that all the information about the interpreted program resides in a single table in the rule/3 version. c) The more one presents, the more one has to explain. I'd reached a point where I thought that one more variant would confuse most readers more than it would help them. Was I wrong about that? d) The method of adding extra arguments is not universally applicable. While I used Quintus Prolog in all my examples and measurements, I did bear other Prologs in mind. Some PC Prologs have very small limits on the number of arguments (e.g. 14). I really didn't want to go into that in the middle of another topic. (Which is why I didn't show examples resulting from compiling away the count/1 interpreter.) >This is not the topspeed in meta-interpreting nrev: > 10 KLips is also reachable. So it is, and rather easily. But the main task of a meta-interpreter, as I see it, is to be a clean specification which is itself amenable to program transformation.