Решения с помощью Пролога

Question

представить функцию

f(x) = 
    if x < -2 then -1 
    else 
     if x > 2 then +1 
     else 
      0 

Дерево решений представлено в виде

[-1, [lt, -2], [1, [gt, 2], 0] ] 

Аналогично, для представления функции

f(x) = 
    if x < 0 then 
     if x < -3 then -1 
     else 0 
    else 
     if x < 3 then +1 
     else +2 

мы используем дерево:

[-1,[lt,-3],0],[lt,0],[1,[lt,3],2]] 

Как написать код Пролога для предиката evaluate(DT, X, Y), который выполняется, если Y - это значение, полученное путем вычисления дерева решений DT по значению X?

вход и выход образца выглядит следующим образом:

?- evaluate([-1,[lt,-2],[1,[gt,2],0]],1,X). 
X = 0 ? ; 

?- evaluate([[-1,[lt,-3],0],[lt,0],[1,[lt,3],2]],7,X). 
X = 2 ? ; 

Answer 1

Я нахожу ваше промежуточное представление немного нелогичным. Было бы справедливым сказать, что списки должны пониматься как 3-кортеж, например: [TrueValue, Condition, ElseValue], где TrueValue и FalseValue могут быть значениями или другими условными 3-мя кортежами? Я собираюсь ответить, полагая, что это правильное понимание.

У вас есть базовое абстрактное синтаксическое дерево (AST). Мы будем иметь два шаблона: значение или 3-кортеж. Оценка значения легко:

evaluate(Value, _, Value) :- number(Value). 

С этой стороны, оценка условной довольно легко:

evaluate([TrueCase, Condition, FalseCase], X, Result) :- 
    evaluate_condition(Condition, X) 
     -> evaluate(TrueCase, X, Result) 
     ; evaluate(FalseCase, X, Result). 

Я переместил условие проверки себя отдельный предикат. Это позволяет добавлять новые операторы. Теперь нам просто нужно написать код:

evaluate_condition([lt, Y], X) :- X < Y. 
evaluate_condition([gt, Y], X) :- X > Y. 

Это даже немного лучше, чем вы рассчитывали, потому что он не производит паразитные точки выбора:

?- evaluate([-1,[lt,-2],[1,[gt,2],0]],1,X). 
X = 0. 

?- evaluate([[-1,[lt,-3],0],[lt,0],[1,[lt,3],2]],7,X). 
X = 2.