🚀 go-pugleaf

In article <1992Apr10.225619.20691@quintus.com>, pds@analog.ingr.com (peter schachte) writes:
> Richard pointed out that the traditional call/N can more often be used
> without having to write an intermediate predicate just to reorder
> arguments than my proposal (which was for call/N to add its N-1
> arguments BEFORE the arguments of its closure argument, rather than
> after).  I agree; I never denied this.

A rhetorical question "is there any other reason than tradition" is
hard to distinguish from a denial that there is no other reason.  But
that was not my main point.  My main point was that the current call/N
interface is CONSISTENT with (most of) the other built-in predicates,
while PDS's interface, sensible in itself, is _not_ consistent with
(most of) the other built-in predicates.

> Richard also pointed out that
> the extra complication in implementing the traditional version
> efficiently is only in an extra loop to shift the first N-1 argument
> registers up where they belong for the call.  Richard's notation made
> that seem a very small additional implementation effort.

The _implementation_ effort is not what counts here; what counts is
the _runtime cost_.  I know how to do the implementation for the old
Quintus runtime system, and for that system I don't think it is very
great.  The amount of code needed is about half a page of Progol code
or less.  Managing the procdure cache and trapping out to a general
look-up routine when the called procedure is not in the cache is rather
harder.

> I think the
> additional effort is not so small.  I expect most Prolog implementations
> already have code to splat a term into argument registers, and already
> have code to look up a procedure given a term, and call it.  But I don't
> expect many implementation have code to shift an arbitrary number of
> argument registers up an arbitrary amount.  If some argument registers
> are kept in machine registers, this code could be fairly bulky.

I investigated the whole question rather thoroughly when I was at Quintus.
There is a very simple way of doing it.  For each A/X register mapped onto
a machine register, keep a "shadow" register in memory.  (This is a good
idea in multi-host systems anyway, and provides a good place to dump the
registers when you want to trap to C, do a GC, or whatever.)  So the process
for call/N+1 is
	(1) dump registers A2..Ar into their shadows
	(2) decode A1
	(3) do the shift with all A/X registers in memory
	(4) pick registers A1..Ar up from the shadow registers
Not at all hard, not at all bulky.  (For example, if you have a VAX
with A1..A4 kept in registers, you can do (1) and (4) with just 4
instructions.)

> But really, after making some timing tests, I conclude that the proposed
> efficiency improvement for call/N wouldn't be adequate.  I did some
> timings of various flavors of predicate call under Quintus Prolog 3.1.1
> on my Sparcstation 1 (which I lost along with my reply when xrn died on
> me; these numbers are from memory, but I think I'm pretty close).
> call/3 from the Quintus library takes well over 500 microseconds.  If
> implemented efficiently, it could come pretty close to the speed of
> call/1, which I timed at a bit over 200 microseconds.  Quite a bit
> better.  But ordinary compiled predicate calls take less than 4
> microseconds, probably quite a bit less.  It's pretty hard to swallow a
> factor of more than 50 when you're writing a piece of even moderately
> time-critical code.

Yes, that's why I wanted Quintus to implement the call/N family at the
WAM level.  call/1 does not have to be that slow.  In the absence of a
module system, it is possible to implement call/1 with an overhead of
one binary clause per actual predicate.  You literally do
	call(p(A,B,C)) :- p(A,B,C).
	(get_A1_struct p/3; unify_var_A1; unify_var_A2; unify_var_A3;
	 tail_call p/3)
except that the switch instruction you use traps instead of failing
when the principal functor of the (only) argument can't be found.  This
gives us an existence proof that the overhead for call/1 can be about
the same as the overhead for an ordinary procedure call.

Why does call/1 actually take longer?  Because it actually runs (what is
essentially) the first pass of the compiler.  This does things like
checking that the whole call is well-formed, so that call((p,1)) may
report an error before p is called, and doing module system work (including
resolving predicates to addresses).  The important point is that (assuming
no major change) the implementation of call/1 that PDS measured is NOT
the WAM-level implementation that he and I are talking about.  Therefore

> Partial deduction may well be the answer to this problem.

is unwarranted.  The "problem" he is talking about simply doesn't exist.
call/N *can* be fast in something pretty close to a straight WAM.

> If for some reason partial deduction does not prove to be the answer,
> I'd like to put in a plug for another of Richard's ideas:  efficient
> compilation of metapredicates and metapredicate calls.  If the compiler
> knows which predicates are metapredicates as they, and calls to them,
> are compiled, the compiler can sometimes be smart.  In cases where a
> meta argument is bound at compile time, the compiler can look up the
> procedure at compile time and pass that information in the call.  If the
> compiler also knew the number of extra arguments to be added to the term
> before calling it, it could do the same optimization for meta terms
> which will be called with call/N. This optimization would also be useful
> to speed up assert and retract, and other built in metapredicates.

It's worth mentioning that Paul Tarau hints at this in one of his papers
on BinProlog.  That gives me an opportunity to say something about
BinProlog.  Rememer that the idea of BinProlog is to work with binary
clauses, so something like

	p(X,X).
	p(X,Y) :- q(X,Y).
	p(X,Y) :- r(X,Z), s(Z,Y).

would turn into

	p(X,X,Continuation) :- call(Continuation).
	p(X,Y,Continuation) :- q(X,Y,Continuation).
	p(X,Y,Continuation) :- r(X,Z,s(Z,Y,Continuation)).

Suppose we improve this by having the compiler look up the address of
the continuation predicate, and pass that as another argument.

	p(X,Y,Addr,Cont) :- :(Addr,Cont).
	p(X,Y,Addr,Cont) :- q(X,Y,Addr,Cont).
	p(X,Y,Addr,Cont) :- r(X,Z,s/4'addr,s(Z,Y,Addr,Cont)).

where s/4'addr is the address of the s/4 predicate in the transformed
program.  Now let's add one more refinement.  When breaking a clause
into binary pieces, do it by adding new predicates this way:
	p(...) :- q(...), r(...), s(...)
=>
	p(...)  :- q(...), c1(...).
	c1(...) :- r(...), c2(...)
	c2(...) :- s(...).
where the arguments of c2 are the distinct variables common to the
s(...) goal and any preceding goal or the head, the arguments of c1
are the distinct variables common to the (r & s) goals and any preceding
goal or head, and so on.  For example,

    represent_terms([Term|Terms], [Rep|Reps], N0, N) :-
	N1 is 1+N0,
	represent_term(Term, Rep),
	represent_terms(Terms, Reps, N1, N).

would turn into


	represent_terms([Term|Terms], [Rep|Reps], N0, N) :-
		N1 is 1+N0,
		c1(Terms, Reps, N1, N, Term, Rep).

	c1(Terms, Reps, N1, N, Term, Rep) :-
		represent_term(Term, Rep),
		represent_terms(Terms, Reps, N1, N).

(Here c2 and s coincide.)  This now turns into

	represent_terms([Term|Terms], [Rep|Reps], N0, N, A, C) :-
		N1 is 1+N0,
		c1(Terms, Reps, N1, N, Term, Rep, A, C).

	c1(Terms, Reps, N1, N, Term, Rep, A, C) :-
		represent_term(Term, Rep, <address>,
		represent_terms(Terms, Reps, N1, N, A, C).

If you stare at examples like this long enough, you suddenly realise
that the last two arguments are _exactly_ the CP and CE registers of
the WAM, and that the only difference between this "optimised" binary
Prolog and the WAM is that the continuation environments are kept on
the heap instead of on a special continuation stack.

-- 
I am writing a book on debugging aimed at 1st & 2nd year CS students using
C/Modula/Pascal-like languages.  Please send suggestions (other than "you
_must_ cite "C Traps and Pitfalls") to ok@goanna.cs.rmit.oz.au