Calling call//1 makes DCG nonfunctional? (+ "difference list" in DCGs vs. "difference list" for appending)

Help!
,
19

accumulator pattern -
In reading “The Craft of Prolog” by Richard A O`Keefe (WorldCat) it is noted as accumulator passing so I will go with that. Still working on a more formal description of this thus the book.

difference list pattern - I now better understand what a difference list is after having created a has_type/2 for it (ref), but for your use of the word pattern I have not found a formal description. At present I don’t know exactly how to interpret that.

My plan of trying to resolve this is to build up solid understandings of each concept independently then to see if they are equivalent or not; thus the note about the equivalence principle. I will probably switch to a pointer model and show that both concepts are the same by using pointer models.

EDIT

In working up to the pointer models did this which should be just as convincing without needing to do all of the graphics to show the pointers.

Details 
% "Difference list" by Frank Pfenning page L11.4
% Difference list version
reverse(Xs, Ys) :-
    rev_1(Xs, (Ys-[])).
rev_1([X|Xs], (Ys-Zs)) :-
    rev_1(Xs, (Ys-[X|Zs])).
rev_1([], (Ys-Ys)).

% "Difference list" by Frank Pfenning page L11.4
% Difference list version
% Difference list as two parameters
reverse_2(Xs, Ys) :-
    rev_2(Xs, Ys,[]).
rev_2([X|Xs], Ys,Zs) :-
    rev_2(Xs, Ys,[X|Zs]).
rev_2([], Ys,Ys).

% "Difference list" by Frank Pfenning page L11.4
% Difference list version
% Difference list as two parameters
% with variables renamed
reverse_3(List, Reverse) :-                 % Rename Xs -> List, Ys -> Reverse
    rev_3(List, Reverse,[]).
rev_3([Head|Tail], Reverse0,Reverse) :-     % Rename X -> Head, Xs -> Tail, Ys -> Reverse0, Zs -> Reverse
    rev_3(Tail, Reverse0,[Head|Reverse]).
rev_3([], Reverse,Reverse).                 % Rename Ys -> Reverse

% "Difference list" by Frank Pfenning page L11.4
% Difference list version
% Difference list as two parameters
% with variables renamed
% with predicates reordered
reverse_4(List, Reverse) :-
    rev_4(List, Reverse,[]).
rev_4([], Reverse,Reverse).
rev_4([Head|Tail], Reverse0,Reverse) :-
    rev_4(Tail, Reverse0,[Head|Reverse]).

% "Difference list" by Frank Pfenning page L11.4
% Difference list version
% Difference list as two parameters
% with variables renamed
% with predicates reordered
% with arguments reordered
reverse_5(List, Reverse) :-
    rev_5(List, [],Reverse).
rev_5([], Reverse,Reverse).
rev_5([Head|Tail], Reverse0,Reverse) :-
    rev_5(Tail, [Head|Reverse0],Reverse).

% "The Craft of Prolog" by Richard A. O`Keefe page 22
% Accumulator passing version
% Compare this to reverse_5/2 which started out using difference list.
rev(List,Reverse) :-
    rev(List,[],Reverse).

rev([],Reverse,Reverse).
rev([Head|Tail],Reverse0,Reverse) :-
    rev(Tail,[Head|Reverse0],Reverse).

:- begin_tests(reverse).

reverse_test(1,[],[]).
reverse_test(2,[a],[a]).
reverse_test(3,[a,b],[b,a]).
reverse_test(4,[a,b,c],[c,b,a]).
reverse_test(5,[a,b,c,d],[d,c,b,a]).

test(reverse,[forall(reverse_test(_,Forward,Reverse))]) :-
    reverse(Forward,Reverse).

test(reverse_2,[forall(reverse_test(_,Forward,Reverse))]) :-
    reverse_2(Forward,Reverse).

test(reverse_3,[forall(reverse_test(_,Forward,Reverse))]) :-
    reverse_3(Forward,Reverse).

test(reverse_4,[forall(reverse_test(_,Forward,Reverse))]) :-
    reverse_4(Forward,Reverse).

test(reverse_5,[forall(reverse_test(_,Forward,Reverse))]) :-
    reverse_5(Forward,Reverse).

test(rev,[forall(reverse_test(_,Forward,Reverse))]) :-
    rev(Forward,Reverse).

:- end_tests(reverse).

Example run

?- run_tests(reverse).
% PL-Unit: reverse ................................... done
% All 35 tests passed
true.

** EDIT **

In working on the images with the pointer models thought of this question.

Where is it factually stated that the pair of a difference list have to be kept together in the same clause? In other words can you pass just one of the pair around to other predicates/clauses and still have an effective difference list?

1 Like