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

radb2(List0, Offset, List1),

Offset1 is Offset + 2,

sort2(List1, Bits, List, Offset1)

; Offset >= Bits,

List = List0

).

radb2(Input, Offset, Output) :-

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,

(radb`K`''([], Offset, for(memb(Ys, Y), [Y,Y])))

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

radb`K`''(List0, Offset, List1),

Offset1 is Offset + K,

sort`K`''(List1, Bits, List, Offset1)

; Offset >= Bits,

List = List0

)),

(radb`K`''(Input, Offset, Output) :-

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

(radb`K`''([], Offset, for(memb(Ys, Y), [Y,Y]))),

(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, _), [

(radb`K`''(I, Offset,

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.