A general iterative processing tool
Peter Van Roy
in a simple way. For example, it may traverse a list and combine
results from each list element. Here's an example without a list:
(1) Given a predicate p(N,A,B).
For N in [1..100], A/B is a difference list giving some result.
I would like to concatenate all the elements in all 100 difference lists.
One way to write this in Prolog is:
(2) map_p(N, Max, A, B) :- N>Max, !, A=B.
map_p(N, Max, A, B) :- N=<Max, !,
p(N, A, C),
N1 is N+1,
map_p(N1, Max, C, B).
The query
(3) map_p(1, 100, A1, A101)
has an identical result to:
p(1, A1, A2), p(2, A2, A3), ..., p(100, A100, A101)
The problem is that the predicate (2) is rather tedious to write. All
I want to do is link the difference lists together!
One possible solution is a preprocessor that converts something like:
map(p(N,A,B), [range(1,N,100),dlist(A,B)->concat(A1,A101)])
(where the second argument of map is a description of the operations
desired) into a dummy predicate similar to (2) and a call similar to (3).
This problem is not as simple as it looks--it is not enough to use a simple
'mapcar-like' predicate because successive iterations *communicate*:
the difference list is concatenated, which means that the third argument
of p(I,..) is unified with the second argument of p(I+1,..). In mapcar,
each iteration is independent of each other.
It is also not enough to *hide* an accumulator (in the way that the DCG
expansion does) because this only solves one special case of the problem
and because it does not relieve one of the burden of writing the dummy
predicate.
Does anyone have a solution to this problem or a reference to a solution?
(I am able to dereference such a reference.) Is there a preprocessor out
there that solves this problem in a nice way?
Thanks,
Peter Van Roy
Andre Marien
iterator. The following predicate iter/3 is an attempt to satisfy the
requirements.
% iter/3 : iter(N,Goal,Transformname)
% N : integer : Number of iterations
% Goal : term : Goal to be executed the first time
% TransformName : atom :
% TransformName/3 is called as TransformName(OldGoal,Newgoal,Iteration)
% right after OldGoal succeeds, with Iteration == Remaining iterations
% It should instantiate Newgoal when Iteration > 0
%
iter(N,G,T) :- N > 0, !,
NN is N - 1,
call(G),
TG =..[T,G,NG,NN],
call(TG),
iter(NN,NG,T) .
iter(N,G,T) .
% example 1: built a open-ended list
%
% ?- t1(3,R) .
%
t1(N,R) :-
iter(N,p1(1,R,_),tr11) .
t1(N,R) :-
iter(N,p1(N,R,_),tr12) .
p1(1,[a|L],L) .
p1(2,[b|L],L) .
p1(3,[c|L],L) .
p1(4,[d|L],L) .
p1(5,[e|L],L) .
tr11(p1(N,_,B),p1(NN,B,_),_) :- NN is N + 1 .
tr12(p1(_,_,B),p1(N,B,_),N) .
% example 2: get the end result with an acc. parameter
%
% ?- t2(3,R) .
%
t2(N,R) :-
iter(N,p2(one,B,R),tr2) .
tr2(p2(_,B,R),p2(B,_,R),IT) :- IT > 0, ! .
tr2(p2(_,R,R),_,IT) .
p2(A,B,R) :-
p2(A,B) .
p2(one,two) .
p2(two,three) .
p2(three,four) .
p2(four,five) .
p2(five,six) .
% example 3: get the end result with an acc. parameter (diff. list)
%
% ?- t3(3,R) .
%
t3(N,B/R) :-
iter(N,p3(N,B,_,R),tr3) .
tr3(p3(N,_,B,R),p3(N,B,_,R),IT) :- IT > 0, ! .
tr3(p3(_,_,R,R),_,IT) .
p3(N,A,B,R) :-
p1(N,A,B) .
% example 4: chains of predicates
%
% ?- t4(3,R) .
%
t4(N,R) :-
iter(N,p41(R,_),tr4) .
tr4(p41(_,B),p42(B,_),_) .
tr4(p42(_,B),p41(B,_),_) .
p41([1|L],L) .
p42([2|L],L) .
Andre' Marien Bart Demoen
bima...@cs.kuleuven.ac.be bim...@cs.kuleuven.ac.be
Mark Lutz
In <1991Aug20.1...@prl.dec.com> Peter Van Roy writes:
> 1) Given a predicate p(N,A,B).
> For N in [1..100], A/B is a difference list giving some result.
>
> I would like to concatenate all the elements in all 100 difference lists.
> One way to write this in Prolog is:
>
> (2) map_p(N, Max, A, B) :- N>Max, !, A=B.
> map_p(N, Max, A, B) :- N=<Max, !,
> p(N, A, C),
> N1 is N+1,
> map_p(N1, Max, C, B).
>
> The query
>
> (3) map_p(1, 100, A1, A101)
Why not just use a generalized version? It does not seem too tedious to use
the (2) form above, provided it is generalized to apply to any predicate;
the general form then only need be written once, and kept in a library or
start-up file:
map_pred(N,Max,Pred,Inputs,Inputs) :-
N > Max, !.
map_pred(N,Max,Pred,Inputs,Outputs) :-
Pred(N,Inputs,NextOutputs),
N1 is N+1, !,
map_pred(N1,Max,Pred,NextOutputs,Outputs).
map_pred_to_list(N,Max,Pred,List) :- map_pred(N,Max,Pred,List,[]).
and used as follows:
?- map_pred(1,100,p,List,Tail).
?- map_pred_to_list(1,100,p,List).
p(N,A,C) :- ....
where the 'Inputs' are a single term, or a list of terms which are
the outputs of the prior iteration, 'Outputs' is a single or list of
terms matched with the final output, and 'NextOutputs' are the
outputs of each iteration;
Of course, if the prolog being used does not support variable fuctors,
the goal must be constructed with '=..' (which may be arbitrarily slow),
and called:
Goal =.. [Pred,N,Inputs,NextOutputs],
call(Goal),
...
One could also add something clever to concatenate the input/output
lists, to make their nodes individual arguments of the called goal (at
a large cost in execution speed); in the specific case you mentioned,
concatenating difference lists, it seems that there would be no other
inputs or outputs to the mapped function, besides the loop count, the
input list, and the output list, so I dont think that would be an issue.
Its not clear why a preprocessor is desirable here; I don't see a big win
for expanding the call into 100 (or more) goals at assert/compile time, and
I see a big loss in speed and space for expanding it at run time; the
generalized predicate is tail-recursive, and should not be a big
space/speed factor.
If you really want a preprocessor, the following will work for the
case you gave, and a few more-- any iteration which executes N times,
where each iteration N gets the outputs of iteration N-1 as its inputs.
This would have to be installed in some sort of assert() hook, which
traverses and transforms goals in a clause's rhs, and in queries;
this can be done by writing a hook or extension for assert(), etc.:
asserth(Clause) :- assert_hook(Clause,NewClause), assert(NewClause), !.
asserth(Clause) :- assert(Clause).
assert_hook((Lhs :- Rhs),(NewLhs :- NewRhs)) :-
expand_lhs(Lhs,NewLhs),
expand_rhs(Rhs,NewRhs).
expand_lhs(LhsIn,LhsOut) :- ...
expand_rhs((G1,G2),(NewG1,NewG2)) :-
expand_rhs(G1,NewG1), expand_rhs(G2,NewG2).
expand_rhs((G1;G2),(NewG1;NewG2)) :-
expand_rhs(G1,NewG1), expand_rhs(G2,NewG2).
expand_rhs((not G1),(not NewG1)) :-
expand_rhs(G1,NewG1).
....[and so on, for if/then, forall, findall, etc.]
expand_rhs(G1,NewG1) :-
expand_goal(G1,NewG1).
expand_rhs(G1,G1).
the important part:
expand_goal(rept(Pred,N,M,Start,End),GoalList) :-
integer(N),
integer(M),
N <= M, !,
rept_inline(N,M,Pred,Start,End,GoalList).
expand_goal(rept(Pred,N,M,Start,End),map_pred(N,M,Pred,Start,End)).
rept_inline(M,M,Pred,Prior,Final,Pred(M,Prior,Final)).
rept_inline(N,M,Pred,Prior,Final,(Pred(N,Prior,Next) , Goals)) :-
N1 is N+1,
rept_inline(N1,M,Pred,Next,Final,Goals).
rept_inline() makes a conjunction of goals rather than a list, to avoid
manually flattening later-- the conjunction gets flattened when asserted.
Here, N and M have to be ground at assert time for the preprocessor to
work [or else we would need to expand the call at run time by replacing it
with a call to expand_goal(), which would be pointless]; if either is
unknown, we instead expand to a call to the generalized dynamic looping
predicate above. The Pred predicate name need not be ground if the prolog
system allows for variable functors.
This is not much unlike a standard dcg rule preprocessor. Again, the
inputs and outputs in each generated goal can be lists of terms-- the
called predicate must expect a list in each slot, unless single terms are
always passed. '=..' would need to be used to construct the goals at
assert time if variable functors are not supported.
example:
p_list(List) :- rept(p,1,1,List,[]).
becomes:
p_list(List) :- p(1,List,[]).
example:
p_list(List) :- rept(p,1,4,List,[]), !.
expands into:
p_list(List) :- (p(1,List,V1),(p(2,V1,V2),(p(3,V2,V3),p(4,V3,[])))), !.
which is just:
p_list(List) :- p(1,List,V1), p(2,V1,V2), p(3,V2,V3), p(4,V3,[]), !.
which should build the difference list you described.
Mark Lutz
ml...@convex.com