swi пролог: соединение и сокращение

Я пытаюсь реализовать интерпретатор пролога в java. Я пытаюсь понять, как должен работать оператор ','. Я попытался реализовать такое эквивалентное правило:

and(A, B) :- A, B.

Я тестирую свою реализацию на основе приведенной ниже логической базы с тестовыми примерами c1, c2 и c3. Все они должны вывести «1» и «ложь». Однако я заметил, что последнее правило (c3) печатает «12» и «false». Я провел тот же тест в прологе SWI, и там последнее правило также выводит «12» и «false».

Итак, мое предположение неверно, что оператор запятой может быть закодирован как ','(X, Y) :- X, Y.?

n(1).
n(2).
and(X, Y) :- X, Y. % this is used to compare with the built in operator ','

c1 :-     n(X),     write(X),     =(1, X),     !, fail.
c2 :- ','(n(X), ','(write(X), ','(=(1, X), ','(!, fail)))).
c3 :- and(n(X), and(write(X), and(=(1, X), and(!, fail)))).

prolog prolog-cut
person wolare    schedule 01.08.2018    source источник
comment
Сокращение применяет отсечение с возвратом в контексте предложения предиката, в котором оно вызывается. Итак, and(!, fail) потерпит неудачу и вернется в то место, где он был вызван. Принимая во внимание, что ','(!, fail), будучи тем же самым, что и !, fail, не будет возвращаться. Таким образом, поведение and(!, fail) отличается от поведения !, fail. Придется написать and(!, fail), !.   -  person lurker    schedule 02.08.2018
comment
@lurker IOW это больше о семантике cut, чем о и?   -  person Daniel Lyons    schedule 02.08.2018
comment
@DanielLyons Да, конечно.   -  person lurker    schedule 02.08.2018
comment
@lurker, спасибо за ответ. Мне нужно будет пожевать его некоторое время. Мне трудно понять, что c1, по-видимому, эквивалентен c2, но c2 не эквивалентен c3. Кажется, разница в том, что «,» - это оператор, а «и / 2» - правило?   -  person wolare    schedule 03.08.2018
comment
c1 эквивалентно c2, потому что ','(A, B) эквивалентно A, B. Фактически, внутри Пролога A, B канонически представлен как ','(A, B). Однако c3 не эквивалентен, потому что and(A, B) не эквивалентен A, B, поскольку and(A, B) добавляет уровень вызова предиката. ','(A, B) не является предикатным вызовом. ',' - встроенный оператор.   -  person lurker    schedule 03.08.2018
comment
В Прологе есть предикат write_canonical(X), который позволяет писать термин так, как Пролог считает его канонически. Попробуйте write_canonical((A, B)).   -  person lurker    schedule 03.08.2018

Ответы (1)


arrow_upward
2
arrow_downward

Вы правы относительно природы , как двоичной функции, но перевод на and еще не объясняет, как интерпретировать соединение. Давайте посмотрим на общее правило Пролога:

head :-  % we disregard variables at the moment
  goal1,
  goal2,
  goal3.

fact. % a fact is a rule without a body

Это можно прочитать как «цели подразумевают голову» или, альтернативно, «получить голову, которая нам нужна для получения каждой из целей». Но goal1 может быть самим правилом, поэтому нам нужен какой-то список TODO (обычно реализуемый в виде стека, но точное поведение сейчас не имеет значения). Начнем с запроса в нашем списке TODO. Если элемент списка является фактом, мы можем просто удалить его. Чтобы удалить правило, нам нужно вывести все цели, поэтому мы заменим заголовок в списке на цели. Давайте посмотрим на это на примере:

make(coffee).
make(tea).
make(orange_juice).
make(croissant).
make(scrambled_eggs).

prepare(beverage) :-
    make(coffee).
prepare(beverage) :-
    make(tea).
prepare(beverage) :-
    make(orange_juice).
prepare(food) :-
    make(croissant).
prepare(food) :-
    make(scrambled_eggs).

breakfast :-
    prepare(beverage),
    prepare(food).

Когда мы запрашиваем завтрак, мы получаем:

?- breakfast.
true ;
true ;
true ;
true ;
true ;
true.

Немного скучно не знать, что у нас на завтрак, но есть шесть способов позавтракать. Итак, как мы туда попали?

Мы начали с завтрака в списке дел:

  • завтрак

единственная подходящая глава правила - последняя, ​​поэтому мы меняем наш TODO на:

  • приготовить (напиток)
  • Готовить пищу)

Теперь у нас есть несколько правил, которые говорят нам, какой напиток делать, давайте выберем первое:

  • сделать кофе)
  • Готовить пищу)

К счастью, make(coffee) - это факт, поэтому мы можем просто вычеркнуть его из нашего списка.

  • Готовить пищу)

Аналогичным образом мы можем приготовить еду:

  • сделать (круассан)

и поскольку есть соответствующий факт, мы закончили готовить завтрак (результат true). Но мы сделали некоторый выбор: мы могли приготовить чай или апельсиновый сок вместо кофе, а могли бы приготовить яичницу-болтунью вместо круассана. Это означает, что мы можем вернуться:

  • сделать (круассан)

ок, выбора тут не было, вернемся еще дальше:

  • Готовить пищу)

и расширите это до

  • сделать (scrambled_eggs).

что снова факт (снова true :)). Когда мы возвращаемся еще дальше, мы получаем все комбинации приготовления напитков и еды и печатаем true для всех 6 из них.

Разрез предотвращает возврат к точке до того, как он был размещен. Изменим правило следующим образом:

breakfast :-
    prepare(beverage),
    !,
    prepare(food).

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

?- breakfast.
true ;
true.

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

Надеюсь, это немного поможет с реализацией.

person lambda.xy.x    schedule 08.08.2018