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

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

Комментарии записываются либо в скобках /* */, либо после символа % до конца строки. Команда (директива) используется для управления процессом трансляции программы во внутреннее представление. Логическая программа состоит из определений предикатов. Предикат (отношение) – это элементарная формула в логическом выражении, которая является истинной, если выполняется ли некоторое свойство или отношение для указанных аргументов, и ложной в противном случае. Определение предиката позволяет проверить истинность предиката и состоит из набора фактов и правил с одинаковым именем и количеством аргументов (предикат с именем name и двумя аргументами часто обозначают как name/2). Язык Пролог не включает средств для указания типа аргументов, и аргументами предикатов могут быть произвольные термы, при этом аргументы не вычисляются, а передаются в виде термов, являющихся основной структурой данных в логических программах. Тело правила и запрос должны содержать обращения только к встроенным или определяемым в программе предикатам.

Обычно для программирования на языке Пролог достаточно только целых чисел, но большинство реализаций допускает использование также и вещественных чисел. Перед числом можно указать основание системы счисления (0x1A, 0o12 или 0b101). Для получении числа, являющегося ASCII-кодом символа, перед символом нужно написать 0' (например, 0'a это число 97). Строки в Прологе рассматриваются как списки ASCII-кодов символов, что позволяет их обрабатывать так же, как и другие списки. Некоторые версии интерпретаторов могут включать в себя и другие типы констант.

Атомы используются как имена для объектов и отношений в программе. В качестве имени можно использовать 1) традиционный идентификатор, состоящий из букв, цифр и символов "_" и начинающийся со строчной буквы, 2) произвольную последовательность символов в апострофах (т.е. даже неадаптированная версия интерпретатора допускает использование русских наименований), 3) последовательность специальных символов, которым относятся + – * / < > = : & ~ и др. Например, следующие цепочки являются атомами:

Переменная в логической программе используется только как ссылка на конкретный объект. Переменная, еще не имеющая значения, называется неконкретизированной. Имя переменной состоит из букв, цифр и символов "_" и начинается с прописной латинской буквы или символа подчеркивания. Область действия переменной ограничена одним предложением. Если переменная при согласовании цели получит какое-либо значение, то значение этой переменной не может быть изменено в ходе дальнейшего логического вывода, так как подобное изменение могло бы повлечь изменение истинности проверенных ранее предикатов. Переменная с именем "_" называется анонимной. Анонимные переменные избавляют программиста от необходимости давать имена переменным, которые используются в предложении только один раз. После трансляции программы каждому вхождению анонимной переменной соответствует своя временная переменная.

Если в языке Scheme все данные, имеющую сложную структуру, представляются в виде списков, то в языке Пролог основной формой представления являются структуры. Структура состоит из функтора (имени структуры) и набора компонент (составных частей структуры). Число аргументов функтора называется арностью. Для структур удобно использовать графическое представление в виде дерева, корнем дерева является функтор, а ветвями – компоненты. Например, представление для структуры дата(1, январь, 2001) показано на рис. 1. Как набор структур представляется и текст программы. Это позволяет программам интерпретировать свой текст как данные, вносить изменения в программу в процессе выполнения.

Арифметическое выражение также можно представить как некоторую структуру, например, выражение x+2*y может быть записано как +(x,*(2,y)). Такая форма сложнее для восприятия, но, к счастью, язык Пролог позволяет определить функторы как операторы с нужными свойствами (приоритетом, позицией и ассоциативностью) и использовать привычную форму записи арифметических выражений и предикатов. Для этого используется команда

:-op(приоритет, тип, функтор).

Приоритет оператора должен быть в диапазоне от 1 до 1200, самый высокий приоритет – 1, самый низкий – 1200. Тип оператора определяет его позицию и ассоциативность. Если оператор инфиксный, то указывается тип xfx, xfy (правоассоциативный) или yfx (левоассоциативный). Для постфиксного оператора указывается тип xf или yf, для префиксного – fx или fy. Буква f указывает расположение функтора, буква x указывает на аргумент, чей приоритет должен быть строго выше приоритета оператора, а буква y обозначает аргумент с приоритетом выше или равным приоритету оператора. В таблице 1 показан приоритет предопределенных операторов.

Таблица 1

Приоритет операторов в языке Пролог

При необходимости программист может ввести свои операторы или переопределить существующие. Например, определив оператор

:-op(600, xfx, нравится).

можно записать факт нравится(мэри,кино) в виде

Списки (последовательности значений произвольной длины) широко применяются в программировании для представления различной информации. Списки в языке Пролог представляются в виде структур с функтором '.'. Первым компонентом этой структуры является голова списка, вторым – хвост. Пустой список является специальным атомом в виде квадратных скобок "[]". Например, список из трех элементов a, b и с может быть записан в виде структуры

'.'(a,'.'(b,'.'(c,[])))

Графически эту структуру можно изобразить так, как показано на рис. 2.

              Рис. 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. Определите операторы для логических выражений: и, или, не.