Пролог всех возможных выражений данного x

У меня есть пролог-программа с заданной грамматикой: 

sum --> [+], mult, sum | mult | num.
mult --> [*], num, xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] ... etc
У меня есть абстрактное древовидное представление моих выражений. Например: mul(num(2),var(x)), который равен [*,2,x], является допустимым. Я хочу иметь возможность создавать все выражения, удовлетворяющие заданному x и решению. Использование 
allExpressions(Tree, X, Solution).

Например: 

?- allExpressions(Tree, 2, 6)
Tree = mul(num(3),x)
Tree = sum(num(2),mul(num(2),var(x))
etc.
Из-за моей грамматики это, очевидно, не будет неограниченным набором уравнений для этого. Я уже запрограммировал evaluation(Tree, X, Solution), который вычисляет ответ, заданный переменной X. Так что мне нужно помощь заключается в том, чтобы сгенерировать возможный набор уравнений для данной x-переменной и ее решения.

Есть идеи, как мне подойти к этому? Спасибо

1 4
prolog arithmetic-expressions

1 ответ:

Это просто: поскольку все ваши арифметические операции могут только увеличивать значение выражений, то легко ограничить глубину при поиске решений. Просто опишите индуктивно, как может выглядеть решение. Вы можете сделать это, например, с ограничениями конечной области SWI-Prolog для сложения и умножения следующим образом: 

:- use_module(library(clpfd)).

expression(var(x), X, X).
expression(num(N), _, N) :- phrase(num, [N]).
expression(mul(A,B), X, N) :-
        N1 * N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).
expression(sum(A,B), X, N) :-
        N1 + N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).

Я оставляю другие операции как упражнение.

Пример запроса и некоторые результаты: 

?- expression(Tree, 2, 6).
Tree = mul(var(x), num(3)) ;
Tree = mul(num(2), num(3)) ;
    [...solutions omitted...]
Tree = sum(num(2), mul(num(2), var(x))) ;
Tree = sum(num(2), mul(num(2), num(2))) ;
    [...solutions omitted...]
Tree = sum(sum(num(2), num(2)), num(2)) ;
false.

+1 за использование чистого, представление без дефолта для деревьев выражений(var(x), num(N) и т.д.), что позволяет использовать сопоставление шаблонов при рассуждении об этом.

4