Блог

Я пишу предикат в prolog: calculate(функция, A, значение, выражение) Функция — это функция, которая может иметь переменную A или нет, значение — это значение A, а выражение — это выражение функции.

Например:

calculate(2*3,x,2,E) —возвращает E = 6.

calculate(x 2,x,2,E) —возвращает E = 4.

calculate(2*(5 x*x),x,2,E) —возвращает E= 18.

calculate(x*(3 y*y),y,3,E) —возвращает E=x* 12.

 calculate(Function,A,Value,Expr):-
    A is Value, 
    %obviously, it is wrong, my question is how to unify these two guys.
    atom(A),
    num(Value),
    Expr is Function.
  

Приведенный выше код может привести к примеру 1, который не имеет переменной в функции, но он может быть достигнут, когда функция имеет переменную.

Во-первых, вы не передаете функции, вы передаете выражения, и результатом является то, что они оценивают. Поскольку это Prolog, и мы можем свободно делать такие вещи, я предпочитаю передавать в одном аргументе что-то вроде x=2 , а не два аргумента x, 2 , потому что я нахожу это более читаемым. Итак, предикат, который я ищу, будет больше похож evaluate( Expression, Var=Value, ?Result) .

То, что мы должны здесь делать, — это индукция по форме выражений. Таким образом, базовыми примерами для выражений являются переменные и числа, поэтому давайте сначала разберемся с ними:

 evaluate(Num, _, Num) :- number(Num).
evaluate(Var, Var=Value, Value).
  

Первый из них должен быть очевиден: если я оцениваю 3, я должен вернуть 3, и мне все равно, как выглядит привязка переменной для этого.

Второй, вероятно, выглядит тавтологично, но идея в том, что если я ищу значение переменной x и у меня есть привязка, которая выглядит как x=3 , то результат будет 3 .

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

 evaluate(A*B, Binding, Value) :-
    evaluate(A, Binding, AValue),
    evaluate(B, Binding, BValue),
    Value is AValue * BValue.

evaluate(A B, Binding, Value) :-
    evaluate(A, Binding, AValue),
    evaluate(B, Binding, BValue),
    Value is AValue   BValue.
  

Итак, идея здесь в том, чтобы повторить левую и правую ветви об операторе, а затем применить этот оператор к этим двум сторонам. Этот маленький игрушечный оценщик будет работать для очень простых случаев, подобных этому:

 ?- evaluate(2*(5 x*x), x=2, E).
E = 18 
  

Теперь у вас есть небольшая сложность, с которой будет довольно сложно справиться должным образом, а именно то, что вы хотите сделать здесь, это выполнить своего рода частичную оценку выражения, когда у вас есть несколько переменных. Неприятный пример — это:

 ?- evaluate(x*(3 y*y), y=3, E).
false.
  

Вы действительно хотите, чтобы это вернулось x*12 . Теперь есть две проблемы с toy evaluator, которые препятствуют этому. Во-первых, он не знает, что делать, если вы ищете переменную, и у нас нет привязки к ней, которую мы можем решить, изменив этот базовый вариант:

 evaluate(Var, X=Value, Result) :-
    atom(Var),
    (    Var = X -> 
         Result = Value 
    ; 
         Result = Var
    )
  

Это немедленно приведет к некоторым ошибкам, хотя:

 ERROR: Arithmetic: `x/0' is not a function
ERROR: In:
ERROR:    [9] _3344 is x*3
ERROR:    [7] <user>
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
  

Проблема в том, что is/2 требует, чтобы выражение в правой части не содержало ничего, кроме чисел и операторов; в результате оно никогда не предоставит вам дерево. Мы можем попытаться решить это следующим образом:

 evaluate(A*B, Binding, Value) :-
    evaluate(A, Binding, AValue),
    evaluate(B, Binding, BValue),
    (number(AValue), number(BValue) ->
        Value is AValue * BValue
    ;
        Value = AValue * BValue
    ).
evaluate(A B, Binding, Value) :-
    evaluate(A, Binding, AValue),
    evaluate(B, Binding, BValue),
    (number(AValue), number(BValue) ->
        Value is AValue   BValue
    ;
        Value = AValue   BValue
    ).
  

На первый взгляд это работает:

 ?- evaluate(x*(3 y*y), y=3, E).
E = x*12 ;
false.
  

Однако вы сможете найти множество случаев, когда не выполняются алгебраические манипуляции, которые объединили бы больше констант:

 ?- evaluate(3*3*x*3*3, y=3, E).
E = 9*x*3*3 ;
  

Левые постоянные множители не будут объединяться с правыми постоянными множителями, потому что у нас здесь нет никакого кода для перестановки дерева. И правильные постоянные факторы не удалось объединить по причинам, которые более четко проиллюстрированы с помощью write_canonical/1 :

 ?- write_canonical(3*3*x*3*3).
*(*(*(*(3,3),x),3),3)
  

Как вы, вероятно, можете догадаться из этого, самые внутренние константы складываются вместе, создавая 9 * x, которые затем мы пытаемся умножить на три. Поскольку 9*x это не число, оно не будет складываться вместе с *3 . И теперь, когда у вас есть фрагмент дерева с левой стороны, он также не будет складываться вместе со следующим *3 .

Решение всего здесь специальным способом будет неприятным, но вы могли бы сделать это, если бы вам пришлось. Честно говоря, я понятия не имею, как можно было бы создать достаточно полную систему алгебры, которая могла бы справиться с этими вещами. Я подозреваю, что вам нужна более мощная структура данных, чем дерево синтаксического анализа, но помимо этого я действительно ничего не знаю. В любом случае, я надеюсь, что это поможет на данный момент.

Для этого требуется больше контекста. Глядя на это, кажется, что реальная цель — проанализировать «функции» (арифметические выражения с переменными?) и упростить их.

Prolog предоставляет вам большую часть синтаксического анализа бесплатно, в том смысле, что выражение типа 2*x 3 также является допустимым термином Prolog, и у него даже есть дерево синтаксического анализа, которое вы ожидаете:

 $ swipl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.3-31-g32d2d0a1d)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- T = 2*x   3*y, display(T).
 (*(2,x),*(3,y))
T = 2*x 3*y.
  

Итак, теперь вам нужно выяснить две вещи:

1. Как именно определяется ваш язык: какие операторы, приоритет, что такое значение, а что такое переменная и так далее.
2. Как вы упрощаете?

Второй пункт потенциально может дать вам больше всего работы. Проблема, на которой вы, похоже, застряли прямо сейчас, относительно проста, но вам нужен другой подход. Вам просто нужно пройти по дереву и заменить все вхождения «переменной» (то, что у вас есть во втором аргументе) на значение (то, что у вас есть в третьем аргументе). Тогда вам все равно придется упростить.

Чтобы узнать, как заменить, вы можете попробовать и прочитать «Искусство пролога», глава 3, «Рекурсивное программирование». На страницах 70-80 есть даже примеры программ, которые вы можете использовать почти такими, какие они есть. Существует также полностью проработанный пример программы, которая выполняет производные. Это не то, что вам нужно, но подход очень близок к тому, что вам, вероятно, нужно.

И предупреждение: когда вы говорите «функция» или «переменная» в контексте Prolog, они могут означать разные вещи для людей с мышлением Prolog, поэтому некоторое время вы будете говорить мимо друг друга. Если вы можете перевести свой вопрос на более формальный язык, возможно, будет проще помочь вам с этим.