Что подразумевается под "логической чистотой" в Прологе?

Question

Что подразумевается под "логической чистотой" (в контексте программирования на Прологе)? Информация о тэге логической чистоты гласит "программы, использующие только клаузулы Хорна", но затем, как бы предикаты вроде if_/3квалифицируйте, используя столько же, сколько и разрез, и различные мета-логики (какова правильная терминология? var/1 и такие) предикаты, то есть вещи низкого уровня.

Я понимаю, что это дает некоторый "чистый" эффект, но что это значит, точно?

Для более конкретной иллюстрации, пожалуйста, объясните, как if_/3 квалифицироваться как логически чистый, замеченный в использовании, например, в этом ответе?

Answer 1

Давайте сначала привыкнем к декларативному чтению логических программ.

Декларативно, программа Пролог утверждает, что это правда.

Например

natural_number(0).
natural_number(s(X)) :-
        natural_number(X).

Первый пункт гласит: 0 это натуральное число.

Второй пункт гласит: если X натуральное число, то s(X) это натуральное число.

Давайте теперь рассмотрим влияние изменений в этой программе. Например, что меняется, когда мы меняем порядок этих двух предложений?

natural_number(s(X)) :-
        natural_number(X).
natural_number(0).

Декларативно, обмен порядком предложений никоим образом не меняет смысл программы (дизъюнкция является коммутативной).

С оперативной точки зрения, то есть, принимая во внимание фактическую стратегию исполнения Пролога, очевидно, что различные порядки предложений часто имеют существенное значение.

Тем не менее, одно очень приятное свойство чистого кода Prolog сохраняется независимо от выбранного порядка предложений:

Если запрос Q успешно в отношении заказа O1, затем Q не терпит неудачу с другим заказом O2,

Обратите внимание, что я не говорю, что Q всегда также успешно выполняется с другим порядком: это потому, что запрос может также зацикливаться или приводить к ошибке с другим порядком.

Для двух запросов Q1 а также Q2 мы говорим, что G1 является более общим, если оно охватывает G2 по отношению к синтаксической унификации. Например, запрос ?- parent_child(P, C). является более общим, чем запрос ?- parent_child(0, s(0)).,

Теперь, с чистыми программами Prolog, есть еще одно очень приятное свойство:

Если запрос Q1 успешно, тогда каждый более общий запрос Q2 не подведет.

Обратите внимание, опять же, что Q2 может зацикливаться вместо успеха.

Рассмотрим теперь случай var/1 который вы упоминаете, и думать о связанном предикате nonvar/1, Предположим, у нас есть:

my_pred(V) :-
        nonvar(V).

Когда это держится? Понятно, что это справедливо, если аргумент не является переменной.

Как и ожидалось, мы получаем:

?- my_pred(a).
true.

Тем не менее, для более общего запроса ?- my_pred(X)., мы получаем:

?- my_pred(X).
false.

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

?- X = a, my_pred(X).
true.

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

?- my_pred(X), X = a.
false.

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

Ограничения CLP(FD), dif/2 и т.д. все чисто в этом смысле: вы не можете обмануть эти предикаты, давая логически неверные ответы, независимо от режимов, приказов и т. д., в которых вы их используете. if_/3 также удовлетворяет этому свойству. С другой стороны, var/1, nonvar/1, integer/1, !/0 предикаты с побочными эффектами и т. д. все экстралогически ссылаются на что-то за пределами описываемого мира деклараций и поэтому не могут считаться чистыми.

РЕДАКТИРОВАТЬ: Чтобы уточнить: хорошие свойства, которые я упоминаю здесь, ни в коем случае не являются исчерпывающими. Код Pure Prolog обладает многими другими чрезвычайно ценными свойствами, благодаря которым вы можете ощутить славу логического программирования. Например, в чистом коде Prolog добавление предложения может максимально расширить, а не сузить набор решений; добавление цели может быть максимально узким, никогда не расширяться, и т. д.

Использование одного экстралогического примитива может и, как правило, уже разрушит многие из этих свойств. Поэтому, например, каждый раз, когда вы используете !/0 Считай, что это порез прямо в сердце чистоты, и постарайся испытать сожаление и стыд за нанесение вреда этим свойствам.

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

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