2

I read some question on this site but could not find one of them answering my question.

And it is from prolog book, where author defined procedure substitute that replace all Subterm with another Subterm in some Term and stores result in Term1.

Specifically, the code is from the book:

substitute(Term, Term, Term1, Term1):- !.
substitute(_, Term, _, Term):- atomic(Term), !.
substitute(Sub, Term, Sub1, Term1):-
    Term=..[F|Args],
    substlist(Sub, Args, Sub1, Args1),
    Term1=..[F|Args1].
substlist(_, [], _, []).
substlist(Sub, [Term|Terms], Sub1, [Term1|Terms1]):-
    substitute(Sub, Term, Sub1, Term1),
    substlist(Sub, Terms, Sub1, Terms1).

So, when we call substitute(5, plus(5, plus(5, 5)), plus(2, 17), X). We get back X = plus(plus(2,17),plus(plus(2,17),plus(2,17))).

Now onto my question. We leave Term non-ground so we store the result there. What if I already have a result, i.e. Term is ground with say value plus(55, plus(4, 55)) and I want to find all expressions that yield this above value when we substitute 2 with 55, so the call would be substitute(2, X, 55, plus(55, plus(4, 55))), which would yield X = plus(2, plus(4, 2)), X = plus(2, plus(4, 55)), X = plus(55, plus(4, 2)), X = plus(55, plus(4, 55)). I think. So I want all expressions that obtain the result by substitution.

If you try the code, you get instantiation error for list when decomposing with =.. built in predicate.

EDIT:

So, I was thinking about checking if Term is ground variable, to avoid instantiation error and write two rules, the code would look like this right now.

substitute(Term, Term, Term1, Term1):- !.
substitute(_, Term, _, Term):- atomic(Term), !.
substitute(Sub, Term, Sub1, Term1):-
    \+ var(Term),
    Term=..[F|Args],
    substlist(Sub, Args, Sub1, Args1),
    Term1=..[F|Args1].
substitute(Sub, Term, Sub1, Term1):-
    \+ var(Term1),
    Term1=..[F|Args1],
    substlist(Sub, Args, Sub1, Args1),
    Term=..[F|Args].
substlist(_, [], _, []).
substlist(Sub, [Term|Terms], Sub1, [Term1|Terms1]):-
    substitute(Sub, Term, Sub1, Term1),
    substlist(Sub, Terms, Sub1, Terms1).

Now, I do not get instantiation error but when I want all possible expressions to be found, only first one is found and then prolog quits with message no.

So, I am only trying to solve, find all solutions case now. Current code:

replace1(Term, Term, Term1, Term1) :- !.

replace1(Term, _, _, Term) :- atomic(Term).

replace1(Term, Subterm, Subterm1, Term1) :-
    Term1 =.. [Functor|Args],
    substitute1(Args1, Subterm, Subterm1, Args),
    Term =.. [Functor|Args1].

substitute1([], _, _, []).
substitute1([Term|Terms], Subterm, Subterm1, [Term1|Terms1]) :-
    replace1(Term, Subterm, Subterm1, Term1),
    substitute1(Terms, Subterm, Subterm1, Terms1).

The result is interesting, if all terms are ground as above, then I get back the same result every time: replace1(X, 2, 17, plus(3, 17)).

X = plus(3,2) ? ;
X = plus(3,2) ? ;

When the other X should be plus(3, 17).

Rahn
  • 4,787
  • 4
  • 31
  • 57
LogicProgrammer
  • 77
  • 9
  • Ok, so I can see why it is failing with instantitation error. When Term is not ground, then we are trying to decompose Term into a list of functors and arguments but since Term is not ground, we fail. – LogicProgrammer Oct 21 '15 at 14:14
  • I tried your example: `?- substitute(plus(2, 17), plus(5, plus(5, 5)), 5, X).`. It yields: `X = plus(5, plus(5, 5))`, which differs from what you show. – mat Oct 21 '15 at 14:46
  • 1
    Sorry, changed it. I should have copy pasted, not typed it in. – LogicProgrammer Oct 21 '15 at 14:53
  • 1
    Check out some highly illogical properties of the original code that is shown in the book: The query `?- substitute(X, t(a, b), c, T), X = any.` **fails**, but `?- X = any, substitute(X, t(a, b), c, T).` **succeeds**. The query `?- substitute(a, Y, c, T), Y = f(a).` **fails**, but `?- Y = f(a), substitute(a, Y, c, T).` **succeeds** with `T = f(c)`. etc., etc. Please try to make this more declarative, so that it somehow resembles a logic program instead of an imperative one. Consider using `dif/2` to state that two terms are *different*. Ideally, your program should become more general. – mat Oct 21 '15 at 15:03
  • I edited my question where I get the same answer in all cases. I found that ! operator binds my choice of variable in the next backtrack step, so after removing it I started to get more solutions instead of one but they are always the same. – LogicProgrammer Oct 21 '15 at 20:22
  • That's OK: In general, it does not hurt to get a solution multiple times. What matters a lot though is when actual solutions are inadvertently lost just because you change the order of your goals. Such programs can only be read procedurally, and you lose many of the benefits of declarative solutions, like their generality and logical properties. – mat Oct 23 '15 at 08:27
  • Possible duplicate of [Prolog - replacing subterms](https://stackoverflow.com/questions/37260614/prolog-replacing-subterms) – Anderson Green Nov 06 '18 at 23:25

0 Answers0