Generating Prolog source code.
Author Message
Generating Prolog source code.

From time to time I want to generate a range of versions of an algorithm,
in order to benchmark them.

In a great many cases, composition from higher order fragments followed by
partial execution does the trick nicely.

However, some of the things I want to try involve
- variable numbers of clauses
- variable numbers of conjuncts/disjuncts/if-then-parts
- variable numbers of arguments in goals
or the like.

For example, I wanted to try out radix sort with various radices.
If you want to do a radix-K sort, you need a distribution predicate
with two input arguments and K accumulator pairs, and it needs K clauses.

Here is radix sort for K=4, from which you may be able to see the pattern.
(To follow Z, U, D, T, think en Francais; too many digits have the same
initial in English.)

sort2(Input, Bits, Output) :-
sort2(Input, Bits, Output, 0).

sort2(List0, Bits, List, Offset) :-
(   Offset < Bits ->
Offset1 is Offset + 2,
sort2(List1, Bits, List, Offset1)
;   Offset >= Bits,
List = List0
).

radb2(Input, Offset, Output, Z, Z, U, U, D, D, []).

radb2([], _, Z, Z, U, U, D, D, T, T).
radb2([X|Xs], Offset, Z0, Z, U0, U, D0, D, T0, T) :-
Digit is (X >> Offset) /\ 3,
radb2(Digit, Offset, Z0, Z, U0, U, D0, D, T0, T, X, Xs).

radb2(0, Offset, [X|Z0], Z, U0, U, D0, D, T0, T, X, Xs) :-
radb2(Xs, Offset, Z0, Z, U0, U, D0, D, T0, T).
radb2(1, Offset, Z0, Z, [X|U0], U, D0, D, T0, T, X, Xs) :-
radb2(Xs, Offset, Z0, Z, U0, U, D0, D, T0, T).
radb2(2, Offset, Z0, Z, U0, U, [X|D0], D, T0, T) :-
radb2(Xs, Offset, Z0, Z, U0, U, D0, D, T0, T).
radb2(3, Offset, Z0, Z, U0, U, D0, D, [X|T0], T) :-
radb2(Xs, Offset, Z0, Z, U0, U, D0, D, T0, T).

To generate versions of this, I have a fairly small (and incredibly ugly)
`predicate' called expand/2.  Basically:
F(X1,...,Xm)`G(Y1,...,Yn)
expands to FG(X1',...,Xm',Y1',...,Yn')
where Z' is the expansion of Z;
[...,for(Gen,[T1,...,Tn],...]
or      F(...,for(Gen,[T1,...,Tn],...)
lets you generate a sequence of list elements or compound term arguments.
for(Gen,T,S,E)
generates
T1 S T2 S ... S Tn S E
where T1 ... Tn are the expansions of T.

For example,
turns into
radb2([], Offset, Y0,Y0, Y1,Y1, Y2,Y2, Y3,Y3)

%   memb(Xs, X)         if X is an element of Xs
%   memb(Xs, X, Ys, Y)  if X, Y are elements of Xs, Ys in the same position.
%   inx0(I, Xs, X)      if X is element I of Xs (zero-origin)
%   inx0(I, Xs,X, Ys,Y) if X, Y are elements of Xs, Ys at position I.

mk_sort(K) :-
integer(K), K > 0,
N is 1 << K,
M is N - 1,
length(Xs, N),
length(Ys, N),
[_|Zs] = Xs,

numberVars([Input,Bits,Output,List,List0,List1,
Offset,Offset1,Digit,A,As,Xs,Ys], 0, T1),

expand([

(sort`K`''(Input, Bits, Output) :-
sort`K`''(Input, Bits, Output, 0)),

(sort`K`''(List0, Bits, List, Offset) :-
(   Offset < Bits ->
Offset1 is Offset + K,
sort`K`''(List1, Bits, List, Offset1)
;   Offset >= Bits,
List = List0
)),

radb`K`''(Input, Offset, Output, for(memb(Zs, Z), [Z, Z]), [])),

(radb`K`''([A|As], Offset, for(memb(Xs,X, Ys,Y), [X,Y])) :-
Digit is (A >> Offset) /\ M,
radb`K`''(Digit, Offset, for(memb(Xs,X, Ys,Y), [X,Y]), A, As)),

for(inx0(I, Xs, _), [
for((inx0(J,Xs,X, Ys,Y), (J =:= I -> Q = [A|X] ; Q = X)),
[Q,Y]), A, As) :-
radb`K`''(As, Offset, for(memb(Xs,X, Ys,Y), [X,Y])) )
])
], Clauses),

numberVars(Clauses, T1, _),
!,
(   memb(Clauses, Clause),
portraycl(Clause), put(46), nl, nl,
fail
;   true
).

In developing this I ran into some problems:  would you believe a Prolog
system where the predicate for getting the name of an atom FAILS when the
atom in question is ''?  (Jeff, can I be the first to notice this?)

However, I have to say that it is *much* easier to get this right than
direct Prolog code for generating the clauses.  For example, to generate
a version of map_integer_list/2+K we'd do

mk_map_integer_list(K, Clauses) :-
length(Xs, K),
length(Xss, K),
numbervars([Pred,N,N0,N1,Xss,Xs], 0, _),

expand([
(map_integer_list(Pred, N, for(memb(Xss,As), [As])) :-
( integer(N) -> N >= 0 ; var(N) ),
map_integer_list_(for(memb(Xss,As), [As]), 0, N, Pred)),

(map_integer_list_(for(memb(Xs,A), [[]]), N, N, Pred) :- !),
(map_integer_list_(for(memb(Xs,A, Xss,As), [[A|As]]),
N0, N, Pred) :-
( var(N) -> true ; N0 < N ),
N1 is 1 + N0,
call(Pred, N1, for(memb(Xs,A), [A])),
map_integer_list_(for(memb(Xss,As), [As]), N1, N, Pred))
], Clauses).

Efficiency is not a concern, because this takes place at program generation
time, not compile time, not run time.  What I principally care about here is
clarity.  Something like Goedel's meta-level stuff would be more elegant, I
suppose, but it is even bulkier than the Prolog code I'm replacing.

Does anyone have a better notation for this kind of thing that I can switch
to?  I would be very happy to junk my expand/2 implementation.

--
"conventional orthography is ... a near optimal system for the
lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.*-*-*.com/ ~ok; RMIT Comp.Sci.

Mon, 13 Jul 1998 03:00:00 GMT
Generating Prolog source code.

Quote:
>In a great many cases, composition from higher order fragments followed by
>partial execution does the trick nicely.

>However, some of the things I want to try involve
>    - variable numbers of clauses
>    - variable numbers of conjuncts/disjuncts/if-then-parts
>    - variable numbers of arguments in goals
>or the like.

It seems to me that these can all fit in the framework of higher order
code and partial evaluation.  You just need a sufficiently good
partial evaluator.

For example, variable numbers of arguments in goals can be handled
by passing a list; if the partial evaluator notices that the list
is always the same length, then it can use a separate argument
for each list element.

If you need variable numbers of clauses, write the code recursively, or
using a higher-order predicate disj/1 that takes a list of goals and
evaluates their disjunction.

disj([X|Xs]) :- call(X) ; disj(Xs).

If the partial evaluator notices that the argument to disj/1 is
always of the same length, then it can fully unfold such calls.

Now, if your next question is "where can I get such a partial evaluator?",
I'm afraid I don't have a good answer for you.

Quote:
>    integer(K), K > 0,
>    N is 1 << K,
>    M is N - 1,
>    length(Xs, N),
>    length(Ys, N),
>    [_|Zs] = Xs,
[...]
>            radb`K`''(Input, Offset, Output, for(memb(Zs, Z), [Z, Z]), [])),

You could write this instead as

N is 1 << K,
length([_|Zs], N),
for(List, memb(Zs, Z), [Z, Z]),

and rely on your partial evaluator to optimize this in the case
when K is known at compile time.

--
Fergus Henderson                WWW: http://www.cs.mu.oz.au/~fjh

Fri, 17 Jul 1998 03:00:00 GMT
Generating Prolog source code.

Quote:

>>In a great many cases, composition from higher order fragments followed by
>>partial execution does the trick nicely.

>>However, some of the things I want to try involve
>>    - variable numbers of clauses
>>    - variable numbers of conjuncts/disjuncts/if-then-parts
>>    - variable numbers of arguments in goals
>>or the like.
>It seems to me that these can all fit in the framework of higher order
>code and partial evaluation.  You just need a sufficiently good
>partial evaluator.

My question is not "how do I get from a specification to usable Prolog
code".  My question is "what is a good notation to write the original
specification in".

Quote:
>For example, variable numbers of arguments in goals can be handled
>by passing a list; if the partial evaluator notices that the list
>is always the same length, then it can use a separate argument
>for each list element.

I am in complete agreement with you about that; for several years I've
been calling the transformation "argument N is always passed instantiated
with the same principal functor -> replace argument N by the arguments of
the instance" 'argument unpacking' or 'argument unwrapping'; if you
unwrap p([a,b]) three times the three functors ./2 ./2 []/0 disappear and
you get p(a,b).  Fine.

That's not the problem.  SPECIFYING THE LIST is the problem.

Quote:
>Now, if your next question is "where can I get such a partial evaluator?",
>I'm afraid I don't have a good answer for you.

That was never my question.  I am happy to write any partial executor I want.
My question was and remains solely concerned with NOTATION for the input to
this partial executor.

Quote:
>>    integer(K), K > 0,
>>    N is 1 << K,
>>    M is N - 1,
>>    length(Xs, N),
>>    length(Ys, N),
>>    [_|Zs] = Xs,
>[...]
>>            radb`K`''(Input, Offset, Output, for(memb(Zs, Z), [Z, Z]), [])),
>You could write this instead as
>        radb(K, Input, Offset, Output) :-
>            N is 1 << K,
>            length([_|Zs], N),
>            for(List, memb(Zs, Z), [Z, Z]),
>            radb(Input, Offset, Output, List, []).
>and rely on your partial evaluator to optimize this in the case
>when K is known at compile time.

I am sorry, but that completely misses the point.  Twice, in fact.
(a) I want control over the name of the resulting predicate.
I want it to be called radb1 or radb2 or whatever; I do NOT want
the notation taking that bit out of my hands.

However, I would be willing to put up with that.  The problem is

(b) It is precisely the for(_,_) notation that I am most unhappy with.
By the way, passing it as a list either will not work or will not
work easily.  In this very example I wanted to say
Output, {X<i>, X<i>, for i = 2..n} []
in one place, but
{X0<i>, X<i>, for i = 1..n}
in another place.  The lists, in short, do not always line up, so
that the unwrapping transformation can't get off the ground.
To make that work, I would have to use lists _everywhere_, which
would leave me pretty much where I started.

In strict point of fact, I have seriously considered writing

I also note that Fergus seems to have elided the bit where I grounded all
the object-level variables.  I assure you all that that bit was not of
minor significance.  I have a very strong preference for amalgamated
but found for this kind of stuff it really did NOT pay.  I have also given
consideration to writing

...)

and may switch to that, but will still need to cons up ground terms to
stand for the variable lists.

So, can anyone help with my actual question:  what's a good NOTATION for
this, that can handle the fact that the variable parts of a call to
P/(N+K) are not always in the same place, so that unwrapping doesn't always
work?

--
"conventional orthography is ... a near optimal system for the
lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Fri, 17 Jul 1998 03:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages