printЛогическое программирование

printСинтаксис. Операторы. Списки

Синтаксис программ на языке Пролог можно описать следующей грамматикой:
<программа>::=<предложение> | <программа> <предложение>
<предложение>::=<утверждение> | <запрос> | <команда>
<утверждение>::=<факт> | <правило>
<факт>::=<терм>.
<правило>::=<терм>:–<термы>.
<запрос>::=?–<термы>.
<команда>::=:–<терм>.
<термы>::=<терм> | <термы>,<терм>
<терм>::=<атом> | <структура> | <константа> | <переменная>
<структура>::=<атом>(<термы>)
<атом>::=<идент> | '<символы>' | <спецсимволы>
<константа>::=<число> | <строка>
<строка>::="<символы>"
Комментарии записываются либо в скобках /* */, либо после символа % до конца строки. Команда (директива) используется для управления процессом трансляции программы во внутреннее представление. Логическая программа состоит из определений предикатов. Предикат (отношение) – это элементарная формула в логическом выражении, которая является истинной, если выполняется ли некоторое свойство или отношение для указанных аргументов, и ложной в противном случае. Определение предиката позволяет проверить истинность предиката и состоит из набора фактов и правил с одинаковым именем и количеством аргументов (предикат с именем name и двумя аргументами часто обозначают как name/2). Язык Пролог не включает средств для указания типа аргументов, и аргументами предикатов могут быть произвольные термы, при этом аргументы не вычисляются, а передаются в виде термов, являющихся основной структурой данных в логических программах. Тело правила и запрос должны содержать обращения только к встроенным или определяемым в программе предикатам.
Обычно для программирования на языке Пролог достаточно только целых чисел, но большинство реализаций допускает использование также и вещественных чисел. Перед числом можно указать основание системы счисления (0x1A, 0o12 или 0b101). Для получении числа, являющегося ASCII-кодом символа, перед символом нужно написать 0' (например, 0'a это число 97). Строки в Прологе рассматриваются как списки ASCII-кодов символов, что позволяет их обрабатывать так же, как и другие списки. Некоторые версии интерпретаторов могут включать в себя и другие типы констант.
Атомы используются как имена для объектов и отношений в программе. В качестве имени можно использовать 1) традиционный идентификатор, состоящий из букв, цифр и символов "_" и начинающийся со строчной буквы, 2) произвольную последовательность символов в апострофах (т.е. даже неадаптированная версия интерпретатора допускает использование русских наименований), 3) последовательность специальных символов, которым относятся + – * / < > = : & ~ и др. Например, следующие цепочки являются атомами:
atom
x_23
'М.Е. Салтыков–Щедрин'
::=
->
Переменная в логической программе используется только как ссылка на конкретный объект. Переменная, еще не имеющая значения, называется неконкретизированной. Имя переменной состоит из букв, цифр и символов "_" и начинается с прописной латинской буквы или символа подчеркивания. Область действия переменной ограничена одним предложением. Если переменная при согласовании цели получит какое-либо значение, то значение этой переменной не может быть изменено в ходе дальнейшего логического вывода, так как подобное изменение могло бы повлечь изменение истинности проверенных ранее предикатов. Переменная с именем "_" называется анонимной. Анонимные переменные избавляют программиста от необходимости давать имена переменным, которые используются в предложении только один раз. После трансляции программы каждому вхождению анонимной переменной соответствует своя временная переменная.
Если в языке Scheme все данные, имеющую сложную структуру, представляются в виде списков, то в языке Пролог основной формой представления являются структуры. Структура состоит из функтора (имени структуры) и набора компонент (составных частей структуры). Число аргументов функтора называется арностью. Для структур удобно использовать графическое представление в виде дерева, корнем дерева является функтор, а ветвями – компоненты. Например, представление для структуры дата(1, январь, 2001) показано на рис. 1. Как набор структур представляется и текст программы. Это позволяет программам интерпретировать свой текст как данные, вносить изменения в программу в процессе выполнения.
15134.png
         Рис. 1
Арифметическое выражение также можно представить как некоторую структуру, например, выражение x+2*y может быть записано как +(x,*(2,y)). Такая форма сложнее для восприятия, но, к счастью, язык Пролог позволяет определить функторы как операторы с нужными свойствами (приоритетом, позицией и ассоциативностью) и использовать привычную форму записи арифметических выражений и предикатов. Для этого используется команда
:-op(приоритет, тип, функтор).
Приоритет оператора должен быть в диапазоне от 1 до 1200, самый высокий приоритет – 1, самый низкий – 1200. Тип оператора определяет его позицию и ассоциативность. Если оператор инфиксный, то указывается тип xfx, xfy (правоассоциативный) или yfx (левоассоциативный). Для постфиксного оператора указывается тип xf или yf, для префиксного – fx или fy. Буква f указывает расположение функтора, буква x указывает на аргумент, чей приоритет должен быть строго выше приоритета оператора, а буква y обозначает аргумент с приоритетом выше или равным приоритету оператора. В таблице 1 показан приоритет предопределенных операторов.
Таблица 1
Приоритет операторов в языке Пролог
ПриоритетТипФункторы
1200xfx:– -->
1200fx:–
1100xfy;
1050xfy->
1000xfy,
900fy\+
700xfx= \= == \== is =.. > < >= =< =:= =\=
500yfx+ – /\ \/
400yfx* / // div mod rem << >>
200xfy^
200fx+ – \
При необходимости программист может ввести свои операторы или переопределить существующие. Например, определив оператор
:-op(600, xfx, нравится).
можно записать факт нравится(мэри,кино) в виде
мэри нравится кино.
Списки (последовательности значений произвольной длины) широко применяются в программировании для представления различной информации. Списки в языке Пролог представляются в виде структур с функтором '.'. Первым компонентом этой структуры является голова списка, вторым – хвост. Пустой список является специальным атомом в виде квадратных скобок "[]". Например, список из трех элементов a, b и с может быть записан в виде структуры
'.'(a,'.'(b,'.'(c,[])))
Графически эту структуру можно изобразить так, как показано на рис. 2.
15136.png
              Рис. 2
Так как запись списка с помощью функтора '.' чересчур сложна, в Прологе используется скобочная форма записи, в которой список записывается как последовательность элементов, разделенных запятыми, в квадратных скобках. Например, вышеуказанный список может быть записан как [a,b,c]. Списочная форма записи автоматически преобразуется в структуру при трансляции программы. Аналогичное преобразование происходит при обработке строк в двойных кавычках, которые заменяются списками ASCII-кодов символов. Например, строка "abc" является списком [97,98,99].
Для разделения списка на голову и хвост в Прологе используется специальная форма для представления списка с головой X и хвостом Y, которая записывается как [X|Y]. Перед вертикальной чертой можно перечислить любое число первых элементов списка, после вертикальной черты указывается одно значение, соответствующее хвосту списка. Например, список [a,b,c] может быть записан следующими способами: [a|[b,c]], [a,b|[c]], [a,b,c|[]], [a|[b|[c|[]]]].
Упражнения
1. Изобразите в виде дерева следующие структуры: f(a,g(b,c),h(d)), x+2*a–y, дата(14/2/2001).
2. Изобразите в виде дерева следующие списки: [1,[2,3]], [[1],[2,3],4], [1,2|3].
3. Определите операторы для логических выражений: и, или, не.
loading