Using a prolog DCG to find & replace - code review

Question

I came up w/ the following code to replace all occurences of Find w/ Replace in Request & put the answer in Result. This is using a DCG, so they are all lists of character codes. The predicate that client code would use is substitute.

findReplace(_, _, [], []) -->
    [].  % The end.
findReplace(Find, Replace, Result, ResultRest) -->
    Find,  % Found Find.
    { append(Replace, Intermediate, Result) },  % Put in Replace in Find's place.
    !,  % Make sure we don't backtrack & interpret Find as the next case.
    findReplace(Find, Replace, Intermediate, ResultRest).
findReplace(Find, Replace, [ C | Intermediate ], ResultRest) -->
    [ C ],  % Any other character.
    findReplace(Find, Replace, Intermediate, ResultRest).

substitute(Find, Replace, Request, Result):-
    phrase(findReplace(Find, Replace, Result, []), Request).

This works in SWI-Prolog. Does anyone have any comments on how I could improve it? I'm learning how to use DCG's & difference lists. E.g., I put in the cut so that, after finding Find, prolog doesn't ever backtrack & interpret that as an ordinary character in the [ C ] case. Is this needed, or is there a more declarative way of doing so?

Another question - is there a predicate already available to do the same thing that substitute does, maybe on atoms?

Thanks in advance.

Laine

Answer 1

Consider using semicontext notation to replace subsequences in DCGs:

eos([], []).

replace(_, _) --> call(eos), !.
replace(Find, Replace), Replace -->
        Find,
        !,
        replace(Find, Replace).
replace(Find, Replace), [C] -->
        [C],
        replace(Find, Replace).

substitute(Find, Replace, Request, Result):-
        phrase(replace(Find, Replace), Request, Result).

Example:

?- substitute("a", "b", "atesta", R), atom_codes(A, R).
R = [98, 116, 101, 115, 116, 98],
A = btestb.

Also, underscores_are_much_more_readable thanMixedCaseNamesAsYouSee.

Kandykane

This is ingenious. BTW, I noticed that this expands to the following. replace(_, _, A, B) :- call(eos, A, C), !, B=C. replace(A, D, B, F) :- phrase(A, B, C), !, E=C, replace(A, D, E, G), phrase(D, F, G). replace(B, C, A, E) :- A=[F|D], replace(B, C, D, G), E=[F|G]. substitute(A, B, C, D) :- phrase(replace(A, B), C, D). eos([], []). Is this tail recursive? There is a phrase call after the 1st recursive replace call & a list binding after the 2nd. – Laine

In the example, the phrase/3 will translate and execute the "a" and "b". The solution is not that efficient, since the translation is redone over and over. Not sure what the fix would be. – Scheers

Answer 2

About the second question, i.e. working with atoms, I wrote this utility perusing atomic_list_concat

%%  replace_word(+Old, +New, +Orig, -Replaced)
%%  is det.
%
%   string replacement
%   doesn't fail if not found
%
replace_word(Old, New, Orig, Replaced) :-
    atomic_list_concat(Split, Old, Orig),
    atomic_list_concat(Split, New, Replaced).

Example:

?- replace_word(a, b, atesta, X).
X = btestb.

Hamrah