ЛАБОРАТОРНАЯ РАБОТА
Тема: Арифметические выражения.Использование простейших правил логического вывода
Цель работы: Закрепить знания о применении простейших правил вывода. Научиться давать логическим программам декларативную и процедурную трактовку
Отчет: Тексты программ. Протоколы трассировок с необходимыми комментариями. Ответы на поставленные в лабораторной работе вопросы.
Декларативная и процедурная трактовка утверждений логических программ
В процедурном программировании семантика некоторой конструкции языка означает поведение вычислительной системы при обработке этой конструкции.
В логике предикатов под семантикой формулы понимается приписывание этой формуле истинностного значения.
Пролог является одновременно и логическим языком, и языком программирования, поэтому к нему применимы обе трактовки термина “семантика”.
а) Декларативная семантика программ — это рассмотрение утверждений программы как объявления случаев истинности рассматриваемых отношений.
Если утверждение содержит переменные, то декларативная трактовка начинается с кванторов. Например, правило
сын( X,Y ):– отец (Y,X), мужчина (X).
имеет следующую декларативную трактовку:
Для всех X и Y отношение “X — сын Y”выполняется,
когда выполняютсяотношения“Y — отец X” и “X — мужчина”.
Это не алгоритм для доказательства истинности, а констатация некоторой связи между отношениями.
б) Процедурная семантика программы на Прологе — это рассмотрение утверждений как описания процесса установления истинности отношений. В процедурной трактовке правила — это описание последовательности шагов, которые необходимо успешно выполнить, чтобы соблюдалось отношение, приведенное в заголовке правила. Т.е. процедурная интерпретация придает логическим программам операционный характер.
Рассмотренное ранее утверждение в процедурной интерпретации выглядит как алгоритм доказательства выполнения отношения:
Чтобы показать, что "X — сын Y", необходимо показать, что “ Y — отец X ”, а затем, учитывая полученный результат, показать, что “ X — мужчина ”.
Говорят об исследовании декларативного смысла логической программы. Под этим понимают анализ того, что в ней объявлено. Этот анализ может быть выполнен путем выяснения набора вопросов, на которые способна отвечать программа.
Арифметические выражения
В общем случае для арифметических выражений могут применяться разные формы записи. Например, для операций с двумя операндами может одна из трех форм записи:
а) инфиксная, когда оператор (знак операции) помещается между операндами: 2 + 3;
б) префиксная, когда оператор записывается перед операндами: + 2 3;
в) постфиксная, когда оператор записывается после операндов: 2 3 +;
Пролог по своей природе не предназначен для программирования задач с большим количеством арифметических вычислений. Для этого существуют процедурные языки. Однако в реальных задачах обойтись совсем без вычислений практически невозможно.
Поэтому реализации Пролога включают свои средства для программирования несложных математических вычислений, которые должны трактоваться процедурно.
Для Пролога естественным является использование префиксной формы, похожей на вызов функций — имя функций и список аргументов. Чтобы не нарушать идеологию логического программирования, знаки арифметических операций рассматриваются в языке как специальные функторы. Поэтому арифметическое выражение в Прологе — это структура.
Например, обычное алгебраическое выражение X+Y*Z при преобразовании в префиксную форму приобретает вид составного терма (в некоторых случаях операторы, являющиеся атомами, можно даже не заключать в одиночные кавычки):
'+'(X,'*'(Y,Z)).
Преимущество префиксной формы в том, что в ней явно определен порядок выполнения операций. В примере структура с функтором * является аргументом структуры с функтором + и ясно, что умножение нужно выполнить раньше. Инфиксная форма менее громоздкая, но её трактовка требует учитывать старшинство операций.
Чтобы сделать программирование выражений более привычным, в Прологе для ряда операторов (символов операций) разрешено дополнительно использовать привычную инфиксную запись. Например, для термов с бинарными функторами +, –, /, *:
X+Y 2/3 5*X.
Аналогично можно использовать обычную префиксную запись для термов с унарным функтором '–', т.е. вместо '–'(X) можно писать –X.
Замечание.
Полный перечень операторов, для которых разрешен альтернативный синтаксис, можно найти в разделе Prolog Terms|Operators файла помощи (Help|Prolog language).
Чтобы однозначно интерпретировать выражения, записанные этими способами, каждому из допустимых операторов приписан свой уровень приоритета и свойство ассоциативности.
Замечание.
Любопытно, что в Прологе имеется возможность менять свойства операторов с помощью специального системного предиката op. Например, можно сделать так, что оператор сложения + будет иметь более высокий приоритет, чем оператор умножения *.
Предикат is
Знаки операций в Прологе, в какой бы форме они не использовались, остаются обычными функторами. Например, выражение 3+4 является просто другим способом записи терма '+'(3,4). Т.е. в контексте логической программы оно является не более чем составным термом и вычисляться не будет, поэтому никак не связано с числом 7.
Единственной естественной операцией с составными термами в Прологе является унификация. Это относится и к конструкциям с операторами. В следующем примере '+'(1,2)участвует в обычной унификации, а не вычисляется:
?- '+'(1,2)=X+Y.
X = 1
Y = 2
yes
Во внутреннем представлении выражение X+Y по-прежнему хранится в стандартной форме составного терма, т.е. в виде '+'(X,Y), а для унификации применены обычные правила.
В программировании на Прологе деление на данные и программу является относительным. Арифметические выражения, которые нам привычнее считать фрагментами выполняемых инструкций (программой), по умолчанию в Прологе трактуются как данные (термы). Но, с другой стороны, их можно трактовать процедурно (вычислять, рассматривать как программу). Для этого требуется специальное указание.
"Принуждение" к вычислению выражений в Прологе выполняет бинарный предикат is/2:
?- is(X,1+2).
X = 3
Этот предикат можно использовать (и чаще всего используется) в инфиксной форме т.е. X is Y. Причем левый операнд предиката is — должен быть неконкретизированной переменной или числом, а правый операнд — арифметическим выражением.
Доказательство целевого утверждения X is Y успешно в следующих случаях (отношение is истинно).
1) Если X — неконкретизированная переменная, а результат вычисления Y есть число. В этой ситуации переменная X конкретизируется вычисленным значением Y — похоже на присваивание.
2) Если X — число (или конкретизированная числом переменная) и это число равно результату вычисления выражения Y. Т.е. фактически выполняется проверка на равенство значений.
Если выражение, к которому применяется is, содержит переменные с числовыми значениями, то эти значения используются, независимо от того, как они были приобретены — в результате унификации или с помощью is.
Когда по какой-то причине результат выражения вычислить нельзя (переполнение, выражение справа не арифметическое, правый операнд имеет нечисловое значение, содержит не конкретизированную переменную и т.п.), то выдается сообщение об ошибке.