156
F F F F iii ig g g gu u u ur r r re e e e AAAA....7777:::: LLLLiiiissssttttiiiinnnngggg ooooffff PPPPrrrroooolllloooogggg tttteeeesssstttt pppprrrrooooggggrrrraaaammmm
% these predicates test the type of an operation, given its ID.
is_insert(ID) :- operation(ID, insert(_, _)).
is_move(ID) :- operation(ID, move(_, _, _)).
is_copy(ID) :- operation(ID, copy(_, _, _)).
is_delete(ID) :- operation(ID, delete(_, _)).
first_change_of(address([X | _], _), X).
% Here we define the notion of "legal" addresses, ones that meet the
% syntactic and operation type restrictions on the legal Palimpsest
% addresses. Some of these restrictions actually carry important
% semantic weight. The possibility of cyclic structures where
% data is repeatedly moved is prevented by the fact that
% addresses are finite in size and that no change-ID can appear
% more than once in a given address.
legal(address([], 0)).
legal(address([I], X)) :- valid_index(I, X).
legal(address([I|T], X)) :-
operation(I, _),
not(is_insert(I)),
not(is_delete(I)),
legal(address(T, X)).
% This predicate tests (and enumerates) the valid indices within an
insertion.
% These are the positions of gaps in the sequence that the insertion
adds to the
% P-sequence in question.
valid_index(I, Index) :-
operation(I, insert(_, SEQ)),
append(A, B, SEQ),
length(A, Index).
% This predicate returns a legal address for a given set of changes. On
failure it
% will produce another until the entire list has been enumerated.
legal_address_for(LIST, A) :-
permutation_dropping(LIST, P),
A = address(P, Index),
legal(A).
F F F F iii ig g g gu u u ur r r re e e e AAAA....7777:::: LLLLiiiissssttttiiiinnnngggg ooooffff PPPPrrrroooolllloooogggg tttteeeesssstttt pppprrrrooooggggrrrraaaammmm
% these predicates test the type of an operation, given its ID.
is_insert(ID) :- operation(ID, insert(_, _)).
is_move(ID) :- operation(ID, move(_, _, _)).
is_copy(ID) :- operation(ID, copy(_, _, _)).
is_delete(ID) :- operation(ID, delete(_, _)).
first_change_of(address([X | _], _), X).
% Here we define the notion of "legal" addresses, ones that meet the
% syntactic and operation type restrictions on the legal Palimpsest
% addresses. Some of these restrictions actually carry important
% semantic weight. The possibility of cyclic structures where
% data is repeatedly moved is prevented by the fact that
% addresses are finite in size and that no change-ID can appear
% more than once in a given address.
legal(address([], 0)).
legal(address([I], X)) :- valid_index(I, X).
legal(address([I|T], X)) :-
operation(I, _),
not(is_insert(I)),
not(is_delete(I)),
legal(address(T, X)).
% This predicate tests (and enumerates) the valid indices within an
insertion.
% These are the positions of gaps in the sequence that the insertion
adds to the
% P-sequence in question.
valid_index(I, Index) :-
operation(I, insert(_, SEQ)),
append(A, B, SEQ),
length(A, Index).
% This predicate returns a legal address for a given set of changes. On
failure it
% will produce another until the entire list has been enumerated.
legal_address_for(LIST, A) :-
permutation_dropping(LIST, P),
A = address(P, Index),
legal(A).