Основные конструкции языка

Основные конструкции языка Рис. 2.1. Классификация основных конструкций языка Пролог Основные конструкции языка - термы и утверждения. Существует единственная структура данных - логический терм. Термы могут быть простыми и составными. Простой терм может быть константой или переменной. Константа - это атом или число. Атом начинается со строчной буквы, знака или резервного имени. Константы в Прологе могут быть шести типов: integer, real, char, symbol, string, file. Пример 2.2: Константы: 0, -l, 123.4, 0.23E-5, а, +, :, 'Фред Блогс' Понятие переменной в Прологе отличается от принятого во многих языках программирования. Переменная не рассматривается как выделенный участок памяти. Она служит для обозначения объекта, на который нельзя сослаться по имени. Переменную можно считать локальным именем для некоторого объекта. Переменные начинаются с прописной буквы или символа подчеркивания и содержат только символы букв, цифр и подчеркивания. Переменные могут быть явными или анонимными. Анонимная переменная обозначается символом '_' и показывает, что конкретное значение данной переменной не представляет интереса. Явные переменные обозначаются любой последовательностью символов, начиная с заглавной буквы латинского алфавита (X, D1, Wer и т.д.). Область действия переменных. Областью действия переменной является утверждение. В пределах утверждения одно и то же имя принадлежит одной и той же переменной. Два утверждения могут использовать одно имя переменной совершенно различным образом. Правило определения области действия переменной справедливо также в случае рекурсии и в том случае, когда несколько утверждений имеют одну и ту же головную цель. Этот вопрос будет рассмотрен далее. Единственным исключением из правила определения области действия переменных является анонимная переменная, например, “_” в цели love (Х,_). Каждая анонимная переменная есть отдельная сущность. Она применяется тогда, когда конкретное значение переменной несущественно для данного утверждения. Таким образом, каждая анонимная переменная четко отличается от всех других анонимных переменных в утверждении. Переменные, отличные от анонимных, называются именованными или связными, а неконкретизированные (переменные, которым не было присвоено значение) называются свободными. Составной терм - состоит из функтора и последовательности одного или нескольких аргументов, являющихся термами. Функтор задается именем (суть атом) и арностью (число аргументов). Пример 2.3: Составные термы: dog(“рекс”), parent(Х,У). // рекс – собака, родителем Y является X В данном примере структура dog имеет арность 1 (записывается как dog /1), а структура parent - арность 2 (parent /2). Заметим, что атом можно рассматривать как структуру арности 0. Для некоторых типов структур допустимо использование альтернативных форм синтаксиса. Это синтаксис операторов для структур арности 1 и 2, синтаксис списков для структур в форме списков и синтаксис строк для структур, являющихся списками кодов символов. Утверждения Программа на Прологе есть совокупность утверждений. Утверждения состоят из целей и хранятся в базе данных Пролога. Таким образом, база данных Пролога может рассматриваться как программа на Прологе. В конце утверждения ставится точка “.”. Иногда утверждение называется предложением. Утверждения бывают трех видов: факты, правила, вопросы. Факты используются для констатации того, что выполнено отношение между объектами, и представляют собой одиночную цель, которая безусловно истинна. Факты могут быть унарные и бинарные, а также простые и универсальные. Простые факты служат для констатации конкретных свойств и отношений. Пример 2.4: like(jhon, apple) - Джон любит яблоки. Универсальные факты определяют совокупность всех возможных решений, удовлетворяющих этому факту. Пример 2.5: like(X, apple) - все любят яблоки. Конечное множество фактов образует программу. Это простейший вид программы. Множество фактов, с другой стороны, составляет описание ситуации. Второй формой утверждения в Прологе являются вопросы. Вопрос – это средство извлечения информации из логической программы. С помощью вопроса выясняется, выполнено ли некоторое отношение между объектами. Например, с помощью вопроса parent(джек,холли)? выясняется, верно ли, что выполнено отношение родитель между объектами джек и холли? Синтаксически вопросы и правила выглядят одинаково, но их можно различить по контексту. Вопрос выглядит так же, как и целевое утверждение, образуется и обрабатывается по тем же правилам, но он не входит в базу данных (программу). В Прологе вычислительная часть программы и данные имеют одинаковый синтаксис. Программа обладает как декларативной, так и процедурной семантикой. Пример 2.6: dog(X). parent (Х,Y), dog (Y). Поиск ответа на вопрос состоит в том, чтобы определить, является ли вопрос логическим следствием программы. Логические следствия выводятся путем применения правил. Простейшее правило вывода – совпадение: из Р выводимо Р. Вопрос иногда называют управляющей командой (директивой), так как он требует от Пролог-системы выполнения некоторых действий. Формальное определение синтаксиса Пролога, используя форму записи Бэкуса-Наура, иногда называемую бэкусовской нормальной формой (БНФ), выглядит так: запрос ::- голова утверждения правило ::– голова утверждения :- хвост утверждения факт ::- голова утверждения голова утверждения ::-атом | структура хвост утверждения ::- атом  структура, термы ::-терм [,термы] терм ::- число | переменная | атом | структура структура ::-атом (термы) Данное определение синтаксиса не включает операторную, списковую и строковую формы записи. Однако любая программа на Прологе может быть написана с использованием вышеприведенного синтаксиса. Специальные формы только упрощают понимание программы. Вопросы могут быть простыми, конъюктивными и экзистенциальными. Простой вопрос состоит из одной цели. Процедура поиска ответа на простой вопрос осуществляется непосредственно. В программе ищется факт, предполагаемый в вопросе. Если факт, тождественный вопросу, найден, то ответ – да. Ответ нет дается в том случае, когда факт, тождественный вопросу, не найден, поскольку данный факт не является логическим следствием программы. Такой ответ не подвергает сомнению истинность вопроса, он просто показывает, что не удалось доказать истинность вопроса с помощью программы. Пример 2.7: В Пролог-программе хранятся факты: dog(jek). // jek - собака dog(rex). // rex - собака dog(holly). // holly – собака Программе задается вопрос: dog(jek). Ответ утвердительный – yes, так как в программе существует тождественный факт. При вопросе: dog(mikky). Ответ отрицательный – no, поскольку в программе не существует тождественного факта, хотя где-то и может существовать собака с такой кличкой. Экзистенциальный вопрос в общем случае содержит переменные и может иметь несколько решений. Пример 2.8: Программе, описанной в примере 2.7, задается вопрос: dog(X). В качестве ответа будет получен результат: X =jek X= rex X= holly Отрицательный ответ может быть получен в том случае, если в программе не найдется ни одного факта, тождественного вопросу. Конъюнктивный вопрос – это конъюнкция целей, поставленная в виде вопроса. Подцели отделяются друг от друга запятой. Пример 2.9: dog(jek),dog(rex),dog(X). Простой вопрос является частным случаем конъюнктивных вопросов с единственной целью. В простейшем конъюнктивном вопросе все подцели простые. Правило - это утверждение вида AB1, B2,…,Bn, где n0. A называется заголовком правила, а B1, B2,…,Bn - телом правила. Как A, так и Bi должны быть целями. Правило состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях. Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей. Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели. Пример 2.10: dog(X) :- parent(X,Y),dog(Y). // X является собакой, если у него есть родитель Y // и Y - собака homo(Х) :-men(Х). // X – человек, если X – мужчина Разница между правилами и фактами чисто семантическая. Хотя для правил мы используем синтаксис операторов (более подробное рассмотрение операторного и процедурного синтаксисов выходит за рамки курса), нет никакого синтаксического различия между правилом и фактом. Так, правило dog(X) :- parent(X,Y),dog(Y) может быть задано как :- dog(X)’,’ parent(X,Y)’,’dog(Y). Запись верна, поскольку :- является оператором “при условии, что”, а ',' - это оператор конъюнкции. Однако удобнее записывать это как dog(X) :- parent(X,Y),dog(Y). и читать следующим образом: “ Х - собака при условии, что родителем Х является Y и Y - собака”. Структуру иногда изображают в виде дерева, число ветвей которого равно арности структуры как показано на рис. 2.2. Рис. 2.2. Структура логического высказывания Логические программы могут включать альтернативные определения или, более формально, - дизъюнкцию, применяя альтернативные правила. Пример 2.11: Родственное отношение «внук» можно описать так: vnuk(X,Y):-fath(Y,Z),fath(Z,X). // X- внук Y, если Y – отец Z и Z – отец X vnuk(X,Y):-moth(Y,Z),fath(Z,X). // X- внук Y, если Y – мать Z и Z – отец X vnuk(X,Y):-fath(Y,Z),moth(Z,X). // X- внук Y, если Y – отец Z и Z – мать X vnuk(X,Y):-moth(Y,Z),moth(Z,X). // X- внук Y, если Y – мать Z и Z – мать X Однако то же самое отношение можно записать компактнее, определив «промежуточное» отношение parent (родитель): parent(X,Y):- fath(X,Y). // X – родительY, если X – отец Y parent(X,Y):-moth(X,Y). // X – родительY, если X – мать Y Тогда родственное отношение «внук» можно определить так: vnuk(X,Y):- parent(Y,Z), parent(Z,X). Совокупность правил с одним и тем же заголовком такая, как пара правил для родителей, называется процедурой. В некотором смысле подобные наборы правил, действительно, аналогичны процедурам и подпрограммам в традиционном программировании. Простой абстрактный интерпретатор Операционная процедура поиска ответа на вопрос была неформально описана в предыдущих разделах. Углубляясь в детали, рассмотрим абстрактный интерпретатор логических программ. Абстрактный интерпретатор выполняет вычисления с ответами «да/нет». Он получает программу P и основной вопрос Q и дает ответ да, если Q выводимо из P, и ответ нет - в противном случае. Кроме того, если цель не выводима, интерпретатор может вообще не завершить работу. В этом случае не выдается никакого ответа. Работу интерпретатора схематично можно описать следующим образом: Вход: Основной вопрос Q и программа P Результат: да, если найден вывод Q из программы P, нет – в противном случае Алгоритм: Положить резольвенту равной Q. Пока резольвента A1,A2,…,An не пуста – начало цикла Выбрать цель Ai, 1  i  n и такой основной пример предложения AB1,B2,…,Bk, где k0 в Р, что A=Ai (если такого предложения нет - выйти из цикла); положить резольвенту равной A1,…,Ai-1, B1,…,Bk , Ai+1,…,An конец цикла если резольвента пуста, то результат – да, иначе результат – нет. На любой стадии вычислений существует текущая цель, называемая резольвентой. Протоколом интерпретатора называется последовательность резольвент, которые строятся в процессе вычисления, вместе с указанием сделанного выбора. Рассмотрим протокол поиска ответа на примере. Пример 2.12: Программа, определяющая родственное отношение «сын»: fath(abram,isak). fath(aran,lot). men(abram). men(lot). men(isak). sun(X,Y):-fath(Y,X),men(X). Вопрос: sun(lot, aran) Протокол интерпретатора: Вход: sun(lot, aran) и программа Резольвента не пуста Выбор: sun(lot, aran) (единственный выбор) Выбор: sun(lot, aran):- fath(aran,lot), men(lot). Новая резольвента: fath(aran,lot), men(lot). Резольвента не пуста. Выбор: fath(aran,lot) // первая подцель в новой резольвенте Выбор: fath(aran,lot). //из двух фактов fath(abram,isak), fath(aran,lot) подходит последний Резольвента не пуста. Выбор: men(lot) // вторая подцель в новой резольвенте Выбор: men(lot). //из трех фактов men(abram), men(isak), men(lot) подходит последний Новая резольвента пуста. Результат: да