Search code examples
prologprolog-defaulty

Prolog - subsitution and evaluation

Hello good people of programming .

Logic programming is always fascinating compare to imperative programming. As pursuing unknown of logic programming, there is some problems encountering arithmetic expressions.

Here is the code I have done so far.

number_atom(N) :-
(number(N) -> functor(N, _, _); functor(N, _, _), atom(N)).
arithmeticAdd_expression(V,V,Val,Val).
arithmeticAdd_expression(N, _Var, _Val, N) :-
   number_atom(N).

arithmeticAdd_expression(X+Y, Var, Val, R) :-
   arithmeticAdd_expression(X, Var, Val, RX),
   arithmeticAdd_expression(Y, Var, Val, RY),
   (number(RX), number(RY) -> R is RX + RY; R = RX + RY).

Taking add operation as example:

arithmeticAdd_expression(Expression, Variable, Value, Result)

?- arithmeticAdd_expression(a+10, a, 1, Result).
?- Result = 11;
?- Result = a + 10.

?- arithmeticAdd_expression(a+10, b, 1, Result).
?- Result = a + 10.

What I would like to achieve is that if the atom(s) in the Expression can only be substituted by given Variable and value, then Result is the number only like the example shown above(Result = 11). Else, the Result is the Expression itself only. My problem with the code is somewhere there, I just could figure it out. So, Please someone can help me? Thank you.

Solution

  • An important attraction of logic programming over, say, functional programming is that you can often use the same code in multiple directions.

    This means that you can ask not only for a particular result if the inputs are given, but also ask how solutions look like in general.

    However, for this to work, you have to put some thought into the way you represent your data. For example, in your case, any term in your expression that is still a logical variable may denote either a given number or an atom that should be interpreted differently than a plain number or an addition of two other terms. This is called a defaulty representation because you have to decide what a variable should denote by default, and there is no way to restrict its meaning to only one of the possible cases.

    Therefore, I suggest first of all to change the representation so that you can symbolically distinguish the two cases. For example, to represent expressions in your case, let us adopt the convention that:

    • atoms are denoted by the wrapper a/1
    • numbers are denoted by the wrapper n/1.
    • and as is already the case, (+)/2 shall denote addition of two expressions.

    So, a defaulty term like b+10 shall now be written as: a(b)+n(10). Note the use of the wrappers a/1 and n/1 to make clear which case we are dealing with. Such a representation is called clean. The wrappers are arbitrarily (though mnemonically) chosen, and we could have used completely different wrappers such as atom/1 and number/1, or atm/1 and nmb/1. The key property is only that we can now symbolically distinguish different cases by virtue of their outermost functor and arity.

    Now the key advantage: Using such a convention, we can write for example: a(X)+n(Y). This is a generalization of the earlier term. However, it carries a lot more information than only X+Y, because in the latter case, we have lost track of what these variables stand for, while in the former case, this distinction is still available.

    Now, assuming that this convention is used in expressions, it becomes straight-forward to describe the different cases:

    expression_result(n(N), _, _, n(N)).
expression_result(a(A), A, N, n(N)).
expression_result(a(A), Var, _, a(A)) :-
        dif(A, Var).
expression_result(X+Y, Var, Val, R) :-
        expression_result(X, Var, Val, RX),
        expression_result(Y, Var, Val, RY),
        addition(RX, RY, R).

addition(n(X), n(Y), n(Z)) :- Z #= X + Y.
addition(a(X), Y, a(X)+Y).
addition(X, a(Y), X+a(Y)).

    Note that we can now use pattern matching to distinguish the cases. No more if-then-elses, and no more atom/1 or number/1 tests are necessary.

    Your test cases work as expected:

    ?- expression_result(a(a)+n(10), a, 1, Result).
Result = n(11) ;
false.

?- expression_result(a(a)+n(10), b, 1, Result).
Result = a(a)+n(10) ;
false.

    And now the key advantage: With such a pure program (please see for more information), we can also ask "What do results look like in general?"

    ?- expression_result(Expr, Var, N, R).
Expr = R, R = n(_1174) ;
Expr = a(Var),
R = n(N) ;
Expr = R, R = a(_1698),
dif(_1698, Var) ;
Expr = n(_1852)+n(_1856),
R = n(_1896),
_1852+_1856#=_1896 ;
Expr = n(_2090)+a(Var),
R = n(_2134),
_2090+N#=_2134 .

    Here, I have used logical variables for all arguments, and I get quite general answers from this program. This is why I have used constraints for declarative integer arithmetic.

    Thus, your immediate issue can be readily solved by using a clean representation, and using the code above.

    Only one very small challenge remains: Maybe you actually want to use a defaulty representation such as c+10 (instead of a(c)+n(10)). The task you are then facing is to convert the defaulty representation to a clean one, for example via a predicate defaulty_clean/2. I leave this as an easy exercise. Once you have a clean representation, you can use the code above without changes.