Каковы оптимальные зеленые срезы для суммы арифметики преемника?
Чтобы получить зеленые сокращения в Прологе, я пытаюсь добавить их к стандартному определению суммы в арифметике-преемнике (см. Предикат plus Что такое дерево SLD для этого запроса?). Идея состоит в том, чтобы "очистить" вывод как можно больше, исключив все бесполезные возвратные дорожки (т. Е. Нет ... ; false) при сохранении идентичного поведения при всех возможных комбинациях экземпляров аргументов - все экземпляры, один / два / три полностью необработанные, и все варианты, включая частично созданные аргументы.
Это то, что я смог сделать, пытаясь максимально приблизиться к этому идеалу (я признаю ложный ответ на вопрос о том, как вставлять зеленые нарезки вappend/3 как источник):
natural_number(0).
natural_number(s(X)) :- natural_number(X).
plus(X, Y, X) :- (Y == 0 -> ! ; Y = 0), (X == 0 -> ! ; true), natural_number(X).
plus(X, s(Y), s(Z)) :- plus(X, Y, Z).
Под SWI это работает нормально для всех запросов, кроме тех, которые имеют форму ?- plus(+X, -Y, +Z)., как для обозначения SWI описания предикатов. Например, ?- plus(s(s(0)), Y, s(s(s(0)))). доходность Y = s(0) ; false., Мои вопросы:
- Как мы можем доказать, что вышеупомянутые сокращения являются (или не являются) зелеными?
- Можем ли мы сделать лучше, чем в приведенной выше программе, и устранить также последний возврат, добавив некоторые другие зеленые сокращения?
- Если да, то как?
1 ответ
Сначала небольшая проблема: общее определение plus/3 имеет обмен первым и вторым аргументом, что позволяет использовать индексацию первого аргумента. См. Программу 3.3 Искусства Пролога. Это также должно быть изменено в вашем предыдущем посте. Я назову ваше обмененное определение plusp/3 и ваше оптимизированное определение pluspo/3, Таким образом, учитывая
плюс (X, 0, X):- натуральный номер (X). плюс (X, s(Y), s(Z)):- плюс (X, Y, Z).
Обнаружение красных порезов (вопрос первый)
Как доказать или опровергнуть красные / зеленые срезы? Прежде всего, следите за "записью" объединений в карауле. То есть для любых таких объединений до разреза. В вашей оптимизированной программе:
pluspo(X, Y, X) :- (Y == 0 -> ! ; Y = 0), (X == 0 -> ! ; true), ...
Я замечаю следующее:
pluspo(X, Y, X) :- (...... -> ! ; ... ), ...
Итак, давайте построим контрпример: чтобы вырезать красным, "объединение записи" должно быть реальным защитником Y == 0 правда. Это означает, что цель построения должна содержать константу 0 как-то. Есть только две возможности для рассмотрения. Первый или третий аргумент. Ноль в последнем аргументе означает, что у нас есть не более одного решения, и, следовательно, нет возможности исключить другие решения. Итак, 0 должно быть в первом аргументе! (Второй аргумент не должен быть 0 с самого начала, иначе объединение записи не будет иметь пагубных последствий.) Вот один из таких контрпримеров:
?- pluspo(0, Y, Y).
который дает одно правильное решение Y = 0, но скрывает все остальные! Так вот у нас такой злой красный срез! И противопоставьте это неоптимизированной программе, которая дала бесконечно много решений:
Y = 0; Y = s (0); Y = s (s (0)); Y = s (s (s (0)));...
Итак, ваша программа неполная, и поэтому любые вопросы по дальнейшей ее оптимизации не актуальны. Но мы можем добиться большего, позвольте мне переформулировать фактическое определение, которое мы хотим оптимизировать:
плюс (0, X, X):- натуральный номер (X). плюс (s(X), Y, s(Z)):- плюс (X, Y, Z).
Практически во всех системах Prolog существует индексация по первому аргументу, которая определяет следующий запрос:
? - плюс (с (0),0, Х). X = s(0).
Но многие системы не поддерживают (полную) индексацию третьего аргумента. Таким образом, мы получаем в SWI, YAP, SICStus:
? - плюс (X, Y, 0). X = Y, Y = 0; ложь
Что вы, вероятно, хотели написать:
плюс (X, Y, Z):- % Часть первая: зеленые порезы ( X == 0 ->! % Индексация первого аргумента; Z == 0 ->! % 3-й аргумент индексации, например, Jekejeke, ECLiPSe; правда), % Часть вторая: оригинальные унификации Х = 0, Y = Z, natural_number(Z). плюс (s(X), Y, s(Z)):- плюс (X, Y, Z).
Обратите внимание на различия pluspo/3: Теперь есть только тесты до разреза! Все объединения после этого.
? - плюс (X, Y, 0). X = Y, Y = 0.
Оптимизация до сих пор опиралась только на расследование глав двух пунктов. Они не приняли во внимание рекурсивное правило. Как таковые, они могут быть включены в компилятор Prolog без какого-либо глобального анализа. В терминологии О'Киф эти зеленые срезы можно считать синими. Процитировать Craft of Prolog, 3.12:
Синие срезы служат для предупреждения системы Пролога к определенности, которую она должна была заметить, но не заметила. Синие срезы не изменяют видимое поведение программы: все, что они делают, - это делают это возможным.
Зеленые срезы предназначены для того, чтобы убрать попытки доказательства, которые будут успешными, или не будут иметь значения, или будут обречены на неудачу, но вы не ожидаете, что система Prolog сможет сказать это.
Тем не менее, суть в том, что эти порезы нуждаются в защите для правильной работы.
Теперь вы рассмотрели еще один запрос:
? - плюс (X, s(s(0)), s(s(s(0)))). X = s(0); ложь
или поставить более простой случай:
? - плюс (X, s(0), s(0)). Х = 0; ложь
Здесь применяются обе головы, поэтому система не может определить детерминизм. Тем не менее, мы знаем, что нет решения для цели plus(X, s^n, s^m) с n > m, Итак, рассматривая модель plus/3 мы можем также избежать выбора точек. Я вернусь после этого перерыва:
Лучше использовать call_semidet/1!
Это становится все более и более сложным, и есть вероятность, что оптимизации могут легко привести к новым ошибкам в программе. Также оптимизированные программы являются кошмаром в обслуживании. Для практического программирования используйте скорее call_semidet/1, Это безопасно и приведет к чистой ошибке, если ваши предположения окажутся ложными.
Вернемся к делу: вот дальнейшая оптимизация. Если Y а также Z идентичны, второй пункт не может применяться:
плюс2(X, Y, Z):- % Часть первая: зеленые порезы ( X == 0 ->! % Индексация первого аргумента; Z == 0 ->! % 3-й аргумент индексации, например, Jekejeke, ECLiPSe; Y == Z, земля (Z) ->!; правда), % Часть вторая: оригинальные унификации Х = 0, Y = Z, natural_number(Z). pluso2(s(X), Y, s(Z)):- pluso2(X, Y, Z).
Я (в настоящее время) считаю, что pluso2/3 оптимальное использование зеленых / синих срезов с оставшимися точками выбора. Вы просили доказательства. Ну, я думаю, что это далеко за рамки ответа SO...
Цель ground(Z) необходимо обеспечить не терминирующие свойства. Цель plus(s(_), Z, Z) не заканчивается, это свойство сохраняется ground(Z), Может быть, вы думаете, что это хорошая идея, чтобы удалить бесконечные ветви ошибок тоже? По моему опыту, это довольно проблематично. В частности, если эти ветви удаляются автоматически. Хотя на первый взгляд это кажется хорошей идеей, это делает разработку программ гораздо более хрупкой: в противном случае изменение программы в противном случае могло бы отключить оптимизацию и, таким образом, вызвать "прекращение". Но в любом случае, мы идем
Помимо простых зеленых нарезок
pluso3(X, Y, Z):- % Часть первая: зеленые порезы ( X == 0 ->! % Индексация первого аргумента; Z == 0 ->! % 3-й аргумент индексации, например, Jekejeke, ECLiPSe; Y == Z ->!; var(Z), nonvar(Y), \+ unify_with_occurs_check(Z, Y) ->!, ошибка; var(Z), nonvar(X), \+ unify_with_occurs_check(Z, X) ->!, ошибка; правда), % Часть вторая: оригинальные унификации Х = 0, Y = Z, natural_number(Z). pluso3(s(X), Y, s(Z)):- pluso3(X, Y, Z).
Можете ли вы найти случай, когда pluso3/3 не заканчивается, пока есть конечное число ответов?