From: pds@analog.ingr.com (peter schachte)
Subject: re: call/n (was finding min/max no. from a list)
Organization: dazix, san ramon, ca
Date: Fri, 10 Apr 1992 22:56:19 GMT

I had a long reply typed in, but xrn bombed on me and left me with
nothing.  This reply will be shorter.

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

Again, if vendors would consider implementing my proposal efficiently
(richard's pseudocode is just what i had in mind) where they wouldn't
consider efficiently implementing the traditional call/N, then I
maintain this proposal is still a good idea.  If vendors won't
implement either, or would implement both, then I think the
traditional version is preferable.

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.

Partial deduction may well be the answer to this problem.  For this to
be the case, PD systems will have to meet four simple criteria:  they
must
	1.  be available;
	2.  be reasonably easy to use;
	3.  not slow compilation too much; and
	4.  be predicatable.
By "predictable" I mean that I must be able to know as I write a
program that what I'm writing will be transformed into something
efficient.  I must know what I'm going to get, just as I know what
indexing and tail recursion will do.

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.

-- 
-Peter Schachte
pschachte@analog.ingr.com