Запись преемника Пролога дает неполный результат и бесконечный цикл
Я начал изучать Пролог и впервые узнал о записи преемника.
И здесь я узнаю о написании аксиом Пеано в Прологе.
Смотрите страницу 12 в PDF:
sum(0, M, M).
sum(s(N), M, s(K)) :-
sum(N,M,K).
prod(0,M,0).
prod(s(N), M, P) :-
prod(N,M,K),
sum(K,M,P).
Я положил правила умножения в Пролог. Затем я делаю запрос:
?- prod(X,Y,s(s(s(s(s(s(0))))))).
Что означает найти фактор 6 в принципе.
Вот результаты.
X = s(0),
Y = s(s(s(s(s(s(0)))))) ? ;
X = s(s(0)),
Y = s(s(s(0))) ? ;
X = s(s(s(0))),
Y = s(s(0)) ? ;
infinite loop
Этот результат имеет две проблемы:
- Не все результаты показаны, обратите внимание, что результат X=6,Y=1 отсутствует.
- Это не останавливается, пока я не нажму Ctrl+C и не выберусь.
Итак... мои вопросы:
- Это почему? Я пробовал переключать "prod" и "sum". Полученный код дает мне все результаты. И снова, ПОЧЕМУ это? Это все еще мертвые петли все же.
- КАК это решить?
Я прочитал другой ответ на бесконечный цикл. Но я был бы признателен, если бы кто-нибудь ответил по этому сценарию. Это очень помогает мне.
2 ответа
Если вы хотите подробно изучить свойства завершения, программы, использующие арифметику-преемник, являются идеальным объектом исследования: вы априори знаете, что они должны описывать, поэтому вы можете сосредоточиться на более технических деталях. Вам нужно будет понять несколько понятий.
Универсальное окончание
Самый простой способ объяснить это, это рассмотреть Goal, false, Это заканчивается, если Goal заканчивается универсально. То есть: смотреть на трассировщики - самый неэффективный способ - они покажут вам только один путь выполнения. Но вам нужно понять их все сразу! Также никогда не смотрите на ответы, когда вы хотите всеобщего завершения, они будут только отвлекать вас. Вы видели это выше: у вас есть три аккуратных и правильных ответа, только тогда ваша программа зацикливается. Так что лучше "выключить" ответы с false, Это устраняет все отвлекающие факторы.
Отказ ломтик
Следующее, что вам нужно, это понятие среза сбоя. Возьмите чисто монотонную логику программы и добавьте несколько целей false, Если результирующий фрагмент сбоя не завершается (универсально), то и оригинальная программа этого не делает. В вашем примере рассмотрим:
Prod(0,M,0):- неверно. Prod(s(N), M, P):- подт (N,M,K), ложь,сумма (K, M, P).
Эти false Цели помогают удалить ненужные украшения в вашей программе: оставшаяся часть ясно показывает, почему prod(X,Y,s(s(s(s(s(s(0))))))). не прекращается. Это не заканчивается, потому что этот фрагмент не заботится о P совсем! Вы надеетесь, что третий аргумент поможет prod/3 прекратить, но фрагмент показывает, что это все напрасно, так как P не встречается ни в одной цели. Нет необходимости в болтливых трассировщиках.
Часто не так просто найти минимальные срезы сбоев. Но как только вы нашли его, он почти тривиален для определения его свойств завершения или, скорее, не завершения. Через некоторое время вы можете использовать свою интуицию, чтобы представить фрагмент, а затем вы можете использовать причину, чтобы проверить, является ли этот фрагмент релевантным или нет.
Что примечательно в понятии среза сбоя, так это то, что: если вы хотите улучшить программу, вы должны изменить свою программу в той части, которая видна в приведенном выше фрагменте! Пока вы не измените его, проблема будет сохраняться. Таким образом, фрагмент сбоя является очень важной частью вашей программы.
Вывод о прекращении
Это последнее, что вам нужно: модуль вывода (или анализатор), такой как cTI, поможет вам быстро определить условие завершения. Посмотрите на предполагаемые условия прекращения prod/3 и улучшенный prod2/3 здесь
Изменить: И так как это был домашний вопрос, я не опубликовал окончательное решение. Но чтобы прояснить это, вот условия завершения, полученные до сих пор:
prod (A, B, C) завершается, если b(A),b(B).
prod2(A,B,C) завершается, если b (A), b (B); b (A), b (C).
Итак, новый prod2/3 строго лучше, чем оригинальная программа!
Теперь вам предстоит найти окончательную программу. Условие его прекращения:
prod3 (A, B, C) завершается, если b(A),b(B);b(C).
Для начала попробуйте найти срез ошибки для prod2(A,B,s(s(s(s(s(s(0)))))))! Мы ожидаем, что это закончится, но это все еще не делает. Так что бери программу и добавляй вручную false цели! Оставшаяся часть покажет вам ключ!
Последний совет: вам нужно добавить одну дополнительную цель и один факт.
Изменить: По запросу, здесь есть срез ошибки для prod2(A,B,s(s(s(s(s(s(0))))))):
prod2 (0, _, 0): - неверно. prod2(s(N), M, P):- сумма (М, К, П), prod2(N,M,K), ложь. сумма (0, М, М).сумма (s(N), M, s(K)):- неверно,сумма (N, M, K).
Обратите внимание на значительно упрощенное определение sum/3, Это только говорит: 0 плюс все что угодно. Больше не надо. Как следствие, даже более специализированные prod2(A,0,s(s(s(s(s(s(0))))))) пока prod2(0,X,Y) элегантно заканчивается...
Первый вопрос (ПОЧЕМУ) довольно легко определить, особенно если знать о левой рекурсии. sum(A,B,C) связывает A и B, когда C привязан, но исходный программный продукт (A,B,C) не использует эти привязки, а вместо этого рекурсирует, не прерывая A, B.
Если мы поменяем сумму на сумму, то получим 2 полезных связывания от суммы для рекурсивного вызова:
sum(M, K, P)
Теперь M связан и будет использован для завершения левой рекурсии. Мы можем поменять местами N и M, потому что мы знаем, что произведение коммутативно.
sum(0, M, M).
sum(s(N), M, s(K)) :-
sum(N, M, K).
prod3(0, _, 0).
prod3(s(N), M, P) :-
sum(M, K, P),
prod3(M, N, K).
Обратите внимание, что если мы поменяем местами M,K (то есть sum(K,M,P)), когда prod3 вызывается с P unknown, у нас снова будет бесконечный цикл, но в сумме.
?- prod3(X,Y,s(s(s(s(s(s(0))))))).
X = s(s(s(s(s(s(0)))))),
Y = s(0) ;
X = s(s(s(0))),
Y = s(s(0)) ;
X = s(s(0)),
Y = s(s(s(0))) ;
X = s(0),
Y = s(s(s(s(s(s(0)))))) ;
false.
OT Я озадачен отчетом cTI: prod3(A,B,C)terminates_if b(A),b(B);b(A),b(C).