Читаем отрывок! в Прологе

Я читаю Изучите Пролог прямо сейчас! глава о сокращениях и в то же время Программирование на языке Prolog для искусственного интеллекта Братко, глава 5: Управление обратным отслеживанием. Сначала казалось, что сокращение - это простой способ имитировать предложение if-else, известное из других языков программирования, например

# Find the largest number
max(X,Y,Y):- X =< Y,!. 
max(X,Y,X).

Однако, как отмечено в строке, этот код завершится ошибкой в ​​тех случаях, когда все переменные создаются, даже если мы ожидаем false, например.

?- max(2,3,2).
true.

Причина ясна: первое правило не работает, второе не имеет больше связанных условий, поэтому оно будет успешным. Я понимаю это, но затем предлагается решение (вот swish):

max(X,Y,Z):- X =< Y,!, Y = Z. 
max(X,Y,X).

И я не понимаю, как мне это читать. Я думал, что ! означает: «если все, что предшествует этому !, верно, прекратить завершение, включая любые другие правила с тем же предикатом». Однако это не может быть правильным, потому что это означало бы, что создание экземпляра Y = Z происходит только в случае сбоя, что было бы бесполезно для этого правила.

Так как же следует читать отрывок «по-человечески»? И, в качестве дополнения, как мне прочитать предложенное решение для max/3 выше?


prolog prolog-cut swi-prolog-for-sharing
person Bram Vanroy    schedule 02.12.2016    source источник
comment
Почти все, что вы говорите, верно, но не хватает следующего: !/0 всегда работает успешно. Следовательно, ошибка в ваших рассуждениях проистекает из смешения понятий завершение, неудача, успешное выполнение и прекращение поиска. дерево. Эта путаница отражена в формулировке прекращения действия. Чтобы ответить на ваш вопрос: «Человеческий» способ читать !/0 - это сказать: С этого момента я больше не могу понимать все последствия того, что я делаю. Это потому, что быстро становится слишком сложно рассуждать о программах, содержащих такие нечистые конструкции.   -  person mat    schedule 02.12.2016
comment
это , если все, что предшествует этому !, является истинным, перестаньте помнить о любых других правилах с тем же предикатом (чтобы продолжить, в случае неудачи) - и продолжайте на то, что у вас есть как на единственную правду. поэтому, поскольку вы успешно достигли этого !, поскольку все, что было до этого, было true, создание экземпляра Y = Z происходит только в случае успех, а не неудача.   -  person Will Ness    schedule 02.12.2016
comment
@WillNess Спасибо за поясняющий комментарий. Я добавил пример из книги Братко, чтобы еще больше усомниться в моем понимании.   -  person Bram Vanroy    schedule 06.12.2016
comment
@BramVanroy Было бы гораздо полезнее, если бы вы задали новый, дополнительный вопрос со всем новым материалом из вашего нового редактирования, со ссылкой на эту запись для справки. Таким образом, в каждой записи вопросов и ответов будет меньше путаницы относительно того, о чем спрашивают, и на что отвечают.   -  person Will Ness    schedule 06.12.2016
comment
@WillNess Done, новая тема здесь < / а>.   -  person Bram Vanroy    schedule 06.12.2016

Ответы (2)


arrow_upward
5
arrow_downward

См. Также этот ответ и этот вопрос.

как мне прочитать предложенное решение для max / 3 выше?

max(X,Y,Z):- X =< Y, !, Y = Z. 
max(X,Y,X).

Вы можете прочитать это так:

Когда X =< Y, забудьте второе предложение предиката и объедините Y и Z.

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

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

Есть множество приемов, которые вы можете использовать, чтобы не создавать точек выбора, которые вам не нужны. Однако это довольно большая тема. Вам следует прочитать доступный материал и задать конкретные вопросы.

person Community    schedule 02.12.2016
comment
Привет, Борис, большое спасибо за информацию. Чтобы убедиться, что я уловил концепцию, я добавил пример из книги Братко к моему исходному посту и свою интерпретацию рядом с ним - и небольшой вопрос по этому поводу. Не могли бы вы просмотреть добавленную информацию и вопрос? Заранее спасибо! - person Bram Vanroy; 06.12.2016
comment
Изменить: WillNess посоветовал мне опубликовать новый вопрос для последующей проблемы, поэтому новая тема здесь. - person Bram Vanroy; 06.12.2016
comment
Это яркий пример того, что известно как красный разрез. Меня учили, что это хорошая практика - использовать сокращения только для повышения эффективности, а не как способ реализации логики if / else. Другими словами, логика вашего кода должна работать корректно, без сокращений; как только это сработает, вы можете добавить сокращения, чтобы удалить ненужное хранилище для отслеживания возвратов и тем самым повысить эффективность; такие разрезы известны как зеленые разрезы. - person Stewart; 19.12.2020

arrow_upward
0
arrow_downward

Проблема с вашим кодом заключается в том, что при оценке вашего запроса разрез никогда не достигается.

Первый шаг попытки оценить цель с помощью правила - сопоставление с образцом.

Цель max(2,3,2) не соответствует шаблону max(X,Y,Y), поскольку второй и третий аргументы одинаковы в шаблоне, а 3 и 2 не соответствуют друг другу по шаблону. Таким образом, это правило уже не удалось на этапе сопоставления с образцом, поэтому оценщик не доходит до тестирования X =< Y, не говоря уже о достижении !.

Но ваше понимание сокращений в значительной степени верное. Учитывая этот код

a(X) :- b(X).
a(X) :- c(X).
b(X) :- d(X), !.
b(X) :- e(X).
c(3).
d(4).
d(5).
e(6).

и цель

?- a(X).

Интерпретатор начнет с первого правила, пытаясь удовлетворить b(X). В процессе он обнаруживает, что d(4) предоставляет решение, поэтому привязывает значение 4 к X. Затем начинается сокращение, которое отбрасывает обратное отслеживание на b(X), поэтому дальнейшие решения для b(X) не найдены. Однако он не удаляет отслеживание с возвратом на a(X), поэтому, если вы попросите Prolog найти другое решение, он найдет X = 3 с помощью правила a(X) :- c(X).. Если вы измените первое правило на a(X) :- b(X), !., то X = 3 не будет найдено.

Хотя сокращение означает, что X = 5 решение не найдено, если ваш запрос

?- a(5).

тогда интерпретатор вернет истину. Это потому, что a(5) вызывает b(5), который вызывает d(5), что определено как истинное. Факт d(4) не соответствует шаблону, поэтому он не запускает вырезку, как при запросе a(X).

Это пример красного сокращения (см. Мой комментарий к ответу user1812457). Возможно, хорошая причина избегать красных сокращений, помимо того, что они нарушают логическую чистоту, состоит в том, чтобы избежать ошибок, возникающих из-за такого поведения.

person Stewart    schedule 19.12.2020