🚀 go-pugleaf

In article <10207@goanna.cs.rmit.oz.au> R. A. O'Keefe writes:

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

Richard is absolutely right this time. Here is BinProlog's DEMO2. It is
implemented as a case in the WAM-loop. It corresponds to call/2 and call/N
is not much longer.

                  case DEMO2:
                    CUT_AND_CHECK_HEAP();
                    FDEREF(regs[1]); 
                    arity=GETARITY(arg); 
                    P=(instr) hget(PREDMARK,PUTARITY(arg,++arity));
                    if(!P) 
                      ERRFUN(arg,"undefined predicate in demo/2")
                    SETREF(regs+arity--,regs[2]);
                    copy_cells(regs,acc,arity);
                  continue;

With addresses known at compile time hget/2 (the look-up in the hash
table) can be eliminated. Copy_cells is a leaf routine on the Sparc
(about 5 instructions) that fully takes advantage of pipelining.
Now a few BinProlog (available from 139.103.16.2) tricks that can
help to speed up the overall use of call/N predicates:

- DEMO2 is in the main loop of the WAM interpreter (i.e it _is_ an
  instruction)
- arity is obtained by 1 register-shift (1 Sparc cycle)
- and, the most important, 2 EXECUTE instructions get unfolded into DEMO2:
  the one which "calls" it and the one that it calls.

Here is an example in BinProlog:

?- asm.
and(X,Y):-X,Y.
...

DEFINITE:
and(A,B) :- 
        '$demo'(A),
        '$demo'(B).

BINARY:
and(A,B,C) :- 
        '$demo'(A,'$demo'(B,C)).

WAM-ASSEMBLER:
clause_? and,3
firstarg_? _/0,5
put_structure $demo/2,var(4-4/8,1/2)
write_value put,var(2-2/5,2/2)
write_value put,var(3-3/6,2/2)
put_value arg(2),var(4-4/8,2/2)
execute_? $demo,2

After optimization by the emulator here is what's left of and/2:

?- [user].
compiling(user)...
and(X,Y):-X,Y.
compile_time = 90

?- list_asm(and,2,4).

BINARY PREDICATE: and/3 @code[14690]
<0> [14690]: (10) PUT_STRUCTURE    X4 $demo/2
<1> [14692]: (33) WRITE_VAL_VAL @@ X2,A3
<2> [14693]: (11) MOVE_REG         X2,A4
<3> [14694]: (66) BUILTIN-  4      X1

where BUILTIN-4 is dispatched as DEMO2 by the emulator. Obviously,
PUT_STRUCTURE must be PUT_ADDRESS but I just was too lazy to implement it.

Here is also the WAM-level profiling for DEMO1 and DEMO2 in the case
of BinProlog compiling an extended version of itself.
--------------------------------------------------------------------
     WAM-instruction          Number of uses    Relative frequency
--------------------------------------------------------------------
[65] BUILTIN-  3      -->          606979       (  5.29 %) % call/1
[66] BUILTIN-  4      -->           28351       (  0.24 %) % call/2 

Probably, for higher values of N the profiling data for call/N will go
down quite fast. Obviously, call/1 is so frequent only because BinProlog
uses continuations. Prolog's call/1 corresponds to BinProlog's call/2.

> 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 agree. The following 2 papers contain an analysis similar to Richard's
remarks:

@TECHREPORT{Demoen90a:KUL,
   author={Demoen, Bart and Mari\"{e}n, Andr\'{e}},
   title = {Implementation of Prolog as binary definite Programs},
   institution = "K.U.Leuven",
   number = "129",
   month = dec,
   year = 1990,
}

@TECHREPORT{Demoen90:KUL,
   author={Demoen, Bart},
   title = "On the transformation of a Prolog Program to a
            more efficient binary Program",
   institution = "K.U.Leuven",
   number = "130",
   month = dec,
   year = 1990,
}

The second also shows how by partial evaluation and argument reordering,
in some cases binary programs can be made faster than their definite
sources. And D.H.D Warren's 83 original WAM paper also hints to facts
similar to Richard's remarks (SRI Tech. Report 309, page 22) i.e. that

   "an environment is a compiler-generated goal corresponding to the
    tail of the clause".

On the other hand, although the obvious thing to believe is that having
a dedicated AND-stack is better (standard WAM), you may consider
implementation simplicity and its practical benefits (more code in the
cache, smaller instruction set), the fact that continuations become first
order objects, easier garbage collection, etc. A book that also advocates
a heap only approach (for SML) and which is a delightful reading in itself
is Andrew Appel's:

@BOOK{Appel92,
   author = "Andrew Appel",
   title = "Compiling with Continuations",
   publisher = "Cambridge University Press",
   year = 1992
}

Paul Tarau
tarau@iro.umontreal.ca