УТВЕРЖДЕН ОПЕРАЦИОННАЯ СИСТЕМА RT-11 С_И_С_Т_Е_М_А П_Р_О_Г_Р_А_М_М_И_Р_О_В_А_Н_И_Я P_R_O_L_O_G БАРНАУЛ, НТП "АЛЬТЕРНАТИВА" ПЕРВ.ПРИМЕН. ЛИТЕРА 1992 АННОТАЦИЯ В данном документе дается краткое описание системы программирования PROLOG, предназначенной для создания и отладки программ на языке PROLOG на ЭВМ совместимых с ЭВМ PDP-11(Электроника-60, ДВК, СМ-4, БК-11М и т.д.). СОДЕРЖАНИЕ АННОТАЦИЯ .......................................... 2 1. ВВЕДЕНИЕ............................................ 2. ЗАПУСК И ИСПОЛЬЗОВАНИЕ СИСТЕМЫ ПРОГРАММИРОВАНИЯ..... 2.1. СОСТАВ СИСТЕМЫ ПРОГРАММИРОВАНИЯ.................. 2.2. УСТАНОВКА И ЗАПУСК СИСТЕМЫ....................... 3. КОМАНДЫ ТУРБО-ОБОЛОЧКИ СИСТЕМЫ ПРОГРАММИРОВАНИЯ..... 3.1. КОМАНДА "ОЧИСТКА" ............................... 3.2. КОМАНДА "ЧТЕНИЕ" ................................ 3.3. КОМАНДА "ЗАПИСЬ" ................................ 3.4. КОМАНДА "РЕДАКТИРОВАНИЕ" ........................ 3.5. КОМАНДА "ПРОЛОГ" ................................ 3.6. КОМАНДА "КОНФИГУРАЦИЯ" .......................... 3.7. КОМАНДА "ВЫХОД" ................................. 4. ЭКРАННЫЙ РЕДАКТОР ТЕКСТА............................ 4.1. УПРАВЛЯЮЩИЕ КЛАВИШИ РЕДАКТОРА.................... 4.1.1. КЛАВИШИ ПЕРЕМЕЩЕНИЯ ПО ТЕКСТУ................. 4.1.1.1. КЛАВИША "СТРЕЛКА ВПРАВО"...................... 4.1.1.2. КЛАВИША "СТРЕЛКА ВЛЕВО"....................... 4.1.1.3. КЛАВИША "СТРЕЛКА ВВЕРХ"....................... 4.1.1.4. КЛАВИША "СТРЕЛКА ВНИЗ"........................ 4.1.1.5. КЛАВИШИ "СТРЕЛКА ВПРАВО"............... 4.1.1.6. КЛАВИШИ "СТРЕЛКА ВЛЕВО"................ 4.1.1.7. КЛАВИШИ "СТРЕЛКА ВВЕРХ"................ 4.1.1.8. КЛАВИШИ "СТРЕЛКА ВНИЗ"................. 4.1.2. КЛАВИШИ КОРРЕКТИРОВКИ ТЕКСТА.................. 4.1.2.1. КЛАВИША <ЗБ>.................................. 4.1.2.2. КЛАВИША ................................. 4.1.2.3. КЛАВИША <ВК>.................................. 4.1.2.4. КЛАВИШИ ............................... 4.1.2.5. КЛАВИШИ ............................ 4.1.2.6. КЛАВИШИ ............................ 4.1.2.7. КЛАВИШИ ............................ - 4 - 1. ВВЕДЕНИЕ. Система программирования PROLOG предназначена для разработки и исполнения программ на языке PROLOG в среде ОС RT-11 на ЭВМ: - серии ДВК-3,4, снабженных контроллером цветного гра- фического дисплея (КЦГД), - БК-0011М, - "Электроника МС-0511" (УКНЦ). Для каждого из перечисленных типов ПЭВМ имеется соответству- ющие версии системы. Система PROLOG написана на языке MACRO-11. Для работы системы программирования PROLOG необходима ОС RT-11 версии не ниже 5.0. 2. ЗАПУСК И ИСПОЛЬЗОВАНИЕ СИСТЕМЫ ПРОГРАММИРОВАНИЯ. 2.1. СОСТАВ СИСТЕМЫ ПРОГРАММИРОВАНИЯ. В состав системы программирования входят: 1. Интерпрeтатор с языка PROLOG, 2. Встроенный редактор текста, 3. Управляющая Турбо-оболочка. Все эти компоненты содержатся в файле PROLOG.SAV и зани- мают около 15KB. 2.2. УСТАНОВКА И ЗАПУСК СИСТЕМЫ. Для запуска системы необходимо набрать команду .RU PROLOG <ВК> После этого экран очищается и в верхней строке экрана появ- ляется меню функций оболочки системы : Очистка Чтение Запись Редактирование Пролог параМетры Выход Для того, чтобы задействовать функцию меню, необходимо выб- рать инверсным указателем ключевое слово и нажать клавишу "ВК". В качестве быстрого задействования функции может быть ис- пользована "горячая" клавиша, характерная для каждого ключевого слова. Буква при нажатии клавиши не отображается на экране. При выполнении функции на экране появляются дополнтельные меню. 3. КОМАНДЫ СИСТЕМЫ ПРОГРАММИРОВАНИЯ. 3.1. Команда "Очистка" (горячая клавиша <О>). Команда "Очистка" позволяет провести инициализацию системы и удаление текста программы на языке PROLOG с экрана. При ее задействовании появляется дополнительное меню, в ко- тором необходимо подтвердить или отказаться от выбора функции с помощью инверсного указателя. 3.2. Команда "Чтение" (горячая клавиша <Ч>). Эта команда производит чтение текста программы с диска в оперативную память ЭВМ. При этом происходит дополнение или замещение содержимого старого текстового буфера в зависмости от установленного параметра "Текст" (см. "параМетры" ). При задействовании функции появляется дополнительное меню, в которое выводится каталог файлов по заданному образцу просмотра ("фильтру"). Образец выводится в середине первой строки меню . Доступ к изменению образца происходит при помощи клавиши <ТАБ>. После ввода отредактированного образца выдается каталог дискового устройства. ПРИМЕР: Образец : DK:*.PRO Каталог диска: DOG.PRO FAMILY.PRO PRAVIL.PRO Далее, с помощью инверсного указателя можно выбрать необхо- димый для чтения файл. 3.3. Команда "Запись" (горячая клавиша <З>). Команда "Запись" производит сброс текстового буфера на диск виде файла, для которого необходимо ввести имя в дополни- тельном меню. 3.4. Команда "Редактирование" (горячая клавиша <Р>). По команде "Редактирование" производится вход в тексто- вый редактор, который описан в главе 4 данного документа. 3.5. Команда "Пролог" (горячая клавиша <П>). Команда "Пролог" предназначена для запуска программы на исполнение. По ее задействовании на экран выводится надпись вида "Пролог" v 2.0 фирма Альтернатива г. Барнаул с дальнейшей интерпретацией текстового буфера. Если при исполнении программы была найдена ошибка, то последующие действия системы зависят от установки параметра "Ошибка" ( см. "параМетры" ): - пропуск, в этом случае интерпретатор игнорирует ошибки с выводом на эк- ран листинга типов пропущенных ошибок. - индикация, в этом случае происходит интерпретация до первой ошибки. при этом на экран выводится надпись вида: Ошибка: <тип ошибки> Нажмите любую клавишу... Далее, производится поиск места появления ошибки и вход в редактор. Курсор встает на место встреченной ошибки. 3.6. Команда "параМетры" (горячая клавиша <М>). При ее задействовании появляется дополнительное меню, в ко- тором можно установить/изменить параметры редактора и интерпрета- тора с помощью инверсного указателя и клавиши <ВК> или горячей клавиши. Вставка (горячая клавиша <В>) Нет/Да Ошибка (горячая клавиша <О>) Пропуск/Индикация Текст (горячая клавиша <Т>) Добавление/Замещение 3.7. Команда "Выход" (горячая клавиша <В>). По этой команде происходит выход в ОС. При ее задействовании появляется дополнительное меню, в ко- тором необходимо подтвердить или отказаться от выбора функции с помощью инверсного указателя. Примечание: При нажатии комбинации клавиш "СУ"+"Ц": - при нахождении в дополнительном меню происхoдит выход в ос- новное меню Турбо-оболочки. - при нахождении в редакторе происхдит выход в основное меню Турбо-оболочки. 4. ЭКРАННЫЙ РЕДАКТОР ТЕКСТА. Экранный редактор текста предназначен для создания текста программы и внесения в него изменений. Идеология работы с текстовым буфером в редакторе близка к идеологии редактора "NED". Текст при работе в редакторе рассматривается как непре- рывная последовательность литер, разбитая на строки символа- ми конца строки. в тексте есть позиция, называемая "теку- щей". Она располагается м_е_ж_д_у какими-либо двумя соседни- ми символами, и индицируется на экране курсором. На экране отображен текст редактируемого файла. Все из- менения в тексте немедленно отображаются на экране. При работе с текстом весь текст находится в оперативной памяти, поэтому размер исходного текста программы не должен превышать об'ем доступной оперативной памяти (это составляет примерно 800 строк текста). Вы имеете возможность, пользуясь клавишами редактирова- ния, перемещаться в пределах всего экрана. Редактор работает в режимах вставка/замена взависимости от установленного параметра "вставка" в меню "параМетры". Максимальная длина строки текста, допустимая в редакто- ре, -- 80 литер. Редактор текста не использует режим дополнительной кла- виатуры дисплея 15ИЭ-00-013-01. 4.1. УПРАВЛЯЮЩИЕ КЛАВИШИ РЕДАКТОРА. К управляющим клавишам редактора относятся: стрелка вправо -- <команда редактирования> стрелка влево -- <команда редактирования> стрелка вниз -- <команда редактирования> стрелка вверх -- <команда редактирования> клавиша <ВК> -- <команда редактирования> клавиша -- <выход из редактора> клавиша -- <нижняя левая на стрелочной клавиатуре дисплея 15ИЭ-00-013-01, клавиша ПФ1 для ПЭВМ ДВК-3/4, клавиша К1 (УКНЦ), клавиша ПОВТ (БК-0011,БК-0011М)>. Эта клавиша выполняет функции префиксной клавиши, изме- няя действие клавиши, перед которой она была нажата. клавиша -- <нижняя правая на стрелочной клавиатуре дисплея 15ИЭ-00-013-01, клавиша ПФ3 для ПЭВМ ДВК-3/4, клавиша К3 (УКНЦ), клавиша "БЛОК РЕД" (БК-0011,БК-0011М)>. <команда редактирования> клавиша -- клавиша <УДАЛ> для пэвм ДВК-3/Ч, клавиша К4 (УКНЦ), клавиша "|<---" (БК-0011,БК-0011М)>. <команда редактирования> 4.1.1. КЛАВИШИ ПЕРЕМЕЩЕНИЯ ПО ТЕКСТУ. 4.1.1.1. Клавиша "стрелка вправо". Нажатие на эту клавишу перемещает текущую позицию на один символ вперед по тексту. Если достигнут конец файла, то никаких действий не производится. При переходе через символ конца строки производится сдвиг текста на экране вверх. 4.1.1.2. Клавиша "стрелка влево". Нажатие на эту клавишу перемещает текущую позицию на один символ назад по тексту. Если достигнуто начало файла, то никаких действий не производится. При переходе через сим- вол конца строки производится сдвиг текста на экране вниз. 4.1.1.3. Клавиша "стрелка вверх". Эта клавиша приводит к перемещению текущей позиции на позицию в предыдущей строке. 4.1.1.4. Клавиша "стрелка вниз". Эта клавиша приводит к перемещению текущей позиции на позицию в следующей строке. 4.1.1.5. Клавиши "стрелка вправо". Ввод этой последовательности клавиш приводит к установ- ке текущей позиции на конец текущей строки (если она там не находилась) и к установке на конец следующей строки, если текущая позиция уже находилась в конце строки. 4.1.1.6. Клавиши "стрелка влево". Ввод этой последовательности клавиш приводит к установ- ке текущей позиции на начало текущей строки (если она там не находилась) и к установке на начало предыдущей строки, если текущая позиция уже находилась в начале строки. 4.1.1.7. Клавиши "стрелка вверх". Ввод этой последовательности клавиш эквивалентен двадцати нажатиям одиночной клавиши "стрелка вверх". 4.1.1.8. Клавиши "стрелка вниз". Ввод этой последовательности клавиш эквивалентен двадцати нажатиям одиночной клавиши "стрелка вниз". 4.1.2. КЛАВИШИ КОРРЕКТИРОВКИ ТЕКСТА. 4.1.2.1. Клавиша <ЗБ>. Нажатие на клавишу <ЗБ> приводит к удалению литеры сле- ва от текущей позиции. если удаляемая литера -- символ конца строки (то есть, текущая позиция находится в начале строки), то происходит "склейка" текущей и предыдущей строк текста. нажатие клавиши <ЗБ> в начале текста игнорируется. 4.1.2.2. Клавиша . Нажатие на клавишу приводит к удалению литеры справа от текущей позиции. если удаляемая литера -- символ конца строки (то есть, текущая позиция находится в конце строки), то происходит "склейка" текущей и следующей строк текста. нажатие клавиши в конце текста игнорируется. 4.1.2.3. Клавиша <ВК>. Нажатие на клавишу <ВК> приводит вставке символа кон- ца строки слева от текущей позиции. это приводит к "разреза- нию" текущей строки на две, или, если текущая позиция нахо- дится в начале или конце строки, к появлению пустой строки. 4.1.2.4. Клавиша . Нажатие на клавишу приводит к удалению строки справа от текущей позиции в буфер строки. 4.1.2.5. Клавиши . Ввод этой последовательности клавиш приводит к выводу справа от текущей позиции буфера строки. 4.1.2.6. Клавиши . Ввод этой последовательности клавиш приводит к выводу пос- ледних 20 строк текстового буфера. 4.1.2.7. Клавиши . Ввод этой последовательности клавиш приводит к выводу пер- вых 20 строк текстового буфера. 5. РАБОТА С СИСТЕМОЙ ТУРБО - ПРОЛОГ. В данном руководстве рассказывается о системе Турбо-Пролог, сообщаются основные сведения о стандартной версии языка Пролог, дан ряд иллюстрационных программ для этой версии, указаны отличия системы Турбо-Пролог от стандартной версии. Пролог - язык программирования, используемый для решения задач, сводимых к об'ектам и отношениям между об'ектами. Например, когда мы говорим: "Петя имеет книгу", мы об'являем, что между одним об'ектом "Петя" и другим об'ектом "книга" имеет место отношение обладания. Это отношение имеет определенный порядок: "Петя имеет книгу " совсем не то, что "книга имеет Петю". Подобные отношения в Прологе называются ФАКТАМИ. Программирование на Прологе состоит из следующих этапов: 1) об'явления некоторых ФАКТОВ об об'ектах и отношениях между ними. 2) об'явления некоторых ПРАВИЛ об об'ектах и отношениях между ними. 3) формулировки ВОПРОСОВ об об'ектах и отношениях между ними. Пролог является диалоговым языком. Система Турбо-Пролог будет ждать, пока Вы введете факты и правила, относящиеся к задаче, которую хотите решить. Затем Вы сможете задать вопросы о задаче и если Вы сделаете это правильно, то система Пролог будет искать ответы и выводить их на экран. Начнем с первого этапа программирования: задание фактов об об'ектах. ФАКТЫ. Предположим, мы хотим сообщить Прологу факт, что Васе нравится Оля. В данном факте имеется два об'екта: Вася и Оля и отношение "нравиться". На языке Пролог факт записывается в виде: нравится(вася,оля). При этом соблюдаются следующие правила: 1) имена всех отношений записываются со строчной буквы. 2) сначала записывается имя отношения. Затем через запятую, записываются имена об'ектов, а весь список об'ектов заключа- ется в круглые скобки. 3) каждый факт должен заканчиваться точкой. Определяя с помощью фактов отношения между об'ектами, необходимо учитывать порядок об'ектов в скобках. Этот порядок может быть произвольным, но выбрав его один раз, необходимо следовать ему далее. Например, для отношения "нравится" на первом месте стоит об'ект , "кому нравится", а на втором "который нравится". Поэтому для нового факта: Лене нравится Сережа, мы должныа использовать запись: нравится(лена,сережа). Посмотрите примеры фактов, записанных на Прологе. Справа приводится их запись на естественном языке. ценный(золото). Золото является ценным. дарить(коля,ира,книга). Коля дарит Ире книгу. отец(виктор,юля). Виктор является отцом Юли. Как видно из приведенных примеров, отношение может связывать произвольное количество об'ектов. В Прологе используется еще и следующая терминология: об'екты, заключенные в скобки называются АРГУМЕНТАМИ, а отношение - ПРЕДИКАТОМ. Совокупность ФАКТОВ и ПРАВИЛ называется БАЗОЙ ДАННЫХ Пролога. БОЛЕЕ ПОДРОБНОЕ ОПИСАНИЕ ФАКТОВ. Отношения или предикаты должны состоять из русских букв, латинских букв, цифр и знаков подчеркивания, причем первым символом должна быть строчная русская или латинская буква. Длина имени может быть произвольной, но следует иметь в виду, что имя заносится в таблицу имен, и выбирая длинные имена, вы сокращаете размер рабочей области, пропорционально длине имени. Аргументы, кроме того могут быть целыми числами в диапазоне от -32767 до 32767 . Примеры: домашнее_животное(кошка). животное(dog). возраст(человек_1,37). Если имеется необходимость использовать для имени отношения или аргумента другие символы, то все имя должно быть заключено в апострофы. Между апострофами разрешается испоьзовать любые символы. Пример: художник('Петров-Водкин'). В данном примере во-первых начальный символ - заглавная буква, а во-вторых используется знак "-". Следует иметь в виду, что "обычные имена" взятые в апострофы, не отличаются от имен без апострофов. Например, следующие два факта полностью тождественны: артист(иванов). и артист('иванов'). ВОПРОСЫ Имея совокупность фактов, мы можем обращаться с вопросами о них. В Прологе вопрос записывается также как факт, только перед ним ставится символы: ?- . Рассмотрим примеры вопросов Прологу и ответы на них. Набираем следующие факты: ценный(золото). нравится(оля,книга). и задаем вопросы: ?-ценный(золото). ДА ?-нравится(оля,книга). ДА ?-ценный(бриллиант). НЕТ ?-нравится(коля,оля). НЕТ Несмотря на то, что в реальном мире бриллианты бесспорно ценные, система Пролог отвечает "НЕТ" потому, что такой факт отсутствует в базе данных Пролога. ПЕРЕМЕННЫЕ И АТОМЫ. В Прологе есть два типа аргументв - переменные и атомы. Конкретные об'екты (напрмер, коля) называются атомами, а абст- рактные неоределенные об'екты вроде X или Y (см. ниже) называ- ются переменными. В предыдущем разделе мы рассмотрели простейшие вопросы, на которые может быть дан ответ "ДА" или "НЕТ". Такие вопросы на естественном языке формулируются в виде: "Верно ли, что ..." Однако, если мы хотим выяснить, какие вещи являются ценными, мы должны использовать другой тип вопроса: "Какие ..." или "Что ..." Для задания подобных вопросов используются переменные. Переменные в Прологе начинаются с заглавных букв или символа подчеркивания. При поиске ответа на вопрос, Пролог организует просмотр всех фактов в базе данных, чтобы обнаружить об'екты, которые переменные могут обозначать. Рассмотрим небольшой пример. Формируем следующую небольшую базу данных: нравится(саша,оля). нравится(саша,фильм). В этой базе данных мы определили два факта, что Саше нравится Оля и фильм. Теперь попробуем задать вопрос: что или кто нравится Саше? ?-нравится(саша,X). Вы сразу же получите ответ: X=оля Что же произошло ? При поступлении такого вопроса, переменная X вначале не имеет никакого значения, или иначе она называется НЕКОНКРЕТИЗИРОВАННОЙ. Пролог просматривает базу данных в поисках факта, сопоставимого с вопросом. При этом переменная сопоставляется с любым аргументом, находящимся в той же позиции факта. При обнаружении такого факта, переменная становится КОНКРЕТИЗИРОВАННОЙ, т.е. равной найденному аргументу. После полного согласования с фактом, Пролог печатает значения всех переменных и ждет дальнейших указаний. Если после получения ответа вы введете символ ; ( точка с запятой ), то Пролог продолжит поиски дальше, пытаять найти новый согласующий факт. В рассмотренном примере сразу же появится новый ответ: X=фильм нажав еще раз точку с запятой, мы получим ответ "НЕТ", поскольку не существует других фактов, сопоставимых с данным вопросом. Получив очередной ответ Пролога, можно закончить дальнейший поиск, введя вместо точки с запятой любой другой символ. БОЛЕЕ ПОДРОБНОЕ ОПИСАНИЕ ПЕРЕМЕННЫХ Переменные в Прологе должны начинаться с заглавной буквы (русской или латинской) или с символа подчеркивания. Остальными символами могут быть буквы( русские, латинские, большие и маленькие), цифры и знаки подчеркивания. Другие символы в переменных недопустимы. Длина переменных может быть произвольной, ограниченной лишь размерами машинной памяти. Ниже приводится пример диалога с Пролог системой, в которой используются разлиные переменные. нравится(лена,книга). нравится(лена,фильм). нравится(коля,лена). ?-нравится(Кому,Кто). Кому=лена Кто=книга ; Кому=лена Кто=фильм ; Кому=коля Кто=лена ; НЕТ ?-нравится(лена,_что_нравится_лене). _что_нравится_лене=книга ; _что_нравится_лене=фильм ; НЕТ В дальнейшем мы рассмотрим общий принцип согласования утверждений Пролога, по которому решения получаются в опреде- ленном порядке. СТРУКТУРЫ. Аргументы предикатов сами могут представлять собой предикат. Например, мы хотим задать факт, что у Вити есть книга "Три мушкетера", автором которой является Дюма. На языке Пролог такое утверждение выглядит следующим образом: имеет(витя,книга(три_мушкетера,дюма)). Теперь можно спросить, что имеет витя. ?-имеет(витя,Что). Что=книга(три_мушкетера,дюма) ; НЕТ Можно также задать вопрос "Кто имеет какие книги ? " ?-имеет(Кто,книга(Название,Автор)). Кто=витя Название=три_мушкетера Автор=дюма ; НЕТ Из этого примера видно, что переменные можно согласовывать со всей структурой или с отдельными компонентами структуры. КОНЬЮНКЦИИ Запишем следующую небольшую базу данных, связанную с предикатом 'нравится'. нравится(витя,фильм). нравится(оля,витя). нравится(лена,фильм). нравится(лена,мороженое). нравится(лена,книга). нравится(лена,витя). нравится(витя,лена). нравится(витя,книга). Пусть мы хотим узнать, нравятся ли Лена и Витя друг другу. На естественном языке подобный вопрос формулируется следующим образом: "Нравится ли Вите Лена И нравится ли Лене Витя ? " Специально выделенный союз И означает, что для утвердительного ответа на вопрос необходим утвердительный ответ на оба отдельных вопроса: "Нравится ли Вите Лена ? " "Нравится ли Лене Витя ? " Такая связь между вопросами в математической логике, а также в языке Пролог называется КОНЬЮНКЦИЕЙ. В прологе для обозначения коньюнкции вопросов ставится запятая. Вопрос, сформулированный выше, следует задать в виде: ?-нравится(витя,лена),нравится(лена,витя). ДА А теперь спросим нравятся ли Оля и Витя друг другу. ?-нравится(оля,витя),нравится(витя,оля). НЕТ Первый вопрос согласуется с нашей базой данных ( на него получен утвердительный ответ ), но второй нет, так как в базе отсутствует факт, что Вите нравится Оля. Таким образом запятая с одной стороны отделяет аргументы внутри предиката, а с другой стороны отделяет и сами предикаты, связывая их коньюнкцией. Рассмотрим теперь пример коньюнкции вопросов с использованием переменных. Пусть мы хотим выяснить, что одновременно нравится Вите и Лене. ?-нравится(лена,Что),нравится(витя,Что). Что=фильм ; Что=книга ; НЕТ Рассмотрим, что происходит при попытке Пролога СОГЛАСОВАТЬ (доказать) коньюнктивный вопрос. 1) База данных просматривается в попытке согласовать первый вопрос. Так как второй аргумент (Что) не конкретизирован, ему может соответствовать что угодно. Первый факт сопоставимый с вопросом есть: нравится(лена,фильм). С этого момента КАЖДОМУ появлению переменной Что во всем коньюнктивном вопросе соответствует значение фильм. Пролог отмечает место в базе данных, где был обнаружен соответствующий факт, чтобы при необходимости начать поиск другого соответствия с этого места. 2) Теперь в базе данных ищется факт: нравится(витя,фильм), так как переменная Что имеет значение фильм. Следует заметить, что процесс поиска нового факта начинается с начала базы данных. Такой факт имеется и Пролог выводит полученное решение: Что=фильм. 3) При вводе точки с запятой, Пролог начинает поиск новых решений. Поиск начинается с последнего факта. Поскольку других экземпляров факта : нравится(витя,фильм) в базе данных нет, этот факт повторно согласовать не удается, и тогда начинается попытка доказать предыдущий вопрос. При этом переменная Что снова становится неконкретизированной и процесс поиска начинается с отмеченного места. 4) Следующий факт, который удается согласовать есть: нравится(лена,мороженое). Переменная Что принимает значение мороженое, и начинает согласовываться факт: нравится(витя,мороженое). Процесс поиска опять начинается с начала базы данных. Такой факт отсутствует и Пролог пытается снова доказывать вопрос: нравится(лена,Что). 5) И вновь при просмотре базы с отмеченного места удается найти соответствие:нравится(лена,книга). Для второго вопроса : нравится(витя,книга) также находится соответствие и Пролог выводит второе решение: Что=книга. 6) При нажатии точки с запятой Пролог снова ищет решение. Для первого вопроса: нравится(лена,Что) Пролог находит еще одно соответствие: нравится(лена,витя), но факт: нравится(витя,витя) отсутствует в базе данных. 7) Больше согласований для первого вопроса обнаружить не удается и поиск решений прекращается. Пролог выводит "НЕТ". Коьюнкциями можно связывать произвольное количество вопросов. Например, добавим в базу данных факт, что Витя нравится сам себе. нравится(витя,витя). Тогда можно спросить, кто нравится Вите, Оле и Лене одновременно. ?-нравится(витя,Кто),нравится(лена,Кто),нравится(оля,Кто). Кто=витя ; НЕТ АНОНИМНЫЕ ПЕРЕМЕННЫЕ Анонимная переменная представляет собой одиночный знак подчеркивания. Анонимная переменная, как и всякая другая, может согласовываться с любым об'ектом, причем две анонимные переменные в одном утверждении могут быть согласованы с различными об'ектами. Значения анонимных переменных не выводятся в качестве решения. Анонимные переменные позволяют избавить программиста придумывать разные имена переменным в тех случаях, когда эти имена в утверждении больше нигде не употребляются. Рассмотрим следующую базу данных: имеет(коля,магнитофон). имеет(витя,книга(три_мушкетера,дюма)). имеет(лена,книга(бесы,достоевский)). имеет(наташа,книга(двадцать_лет_спустя,дюма)). Теперь зададим вопросы: 1. Кто имеет книги Дюма ? ?-имеет(Кто,книга(_,дюма)). Кто=витя ; Кто=наташа ; НЕТ 2. Кто имеет вообще какие-нибудь книги ? ?-имеет(Кто,книга(_,_)). Кто=витя ; Кто=лена ; Кто=наташа ; НЕТ 3. Кто вообще,что-нибудь имеет ? ?-имеет(Кто,_). Кто=коля ; Кто=витя ; Кто=лена ; Кто=наташа ; НЕТ ПРАВИЛА Теперь рассмотрим одно из самых важных и трудных понятий Пролога - правила. Пусть мы хотим сформулировать утверждение, что Васе нравятся все люди, которым нравится рок-музыка. В базе данных имеются сведения о людях, которым нравится рок-музыка. На естественном языке формулировка выглядит примерно так: Васе нравится человек, ЕСЛИ человеку нравится рок-музыка. Аналогичные утверждения можно задать и в Прологе, причем выделенному слову "ЕСЛИ" соответствует знак " :- " , а само такое утверждение называется правилом. К базе данных: нравится(андрей,'рок-музыка'). нравится(виталий,'рок-музыка'). нравится(вася,лена). добавим правило о Васе: нравится(вася,Человек):-нравится(Человек,'рок-музыка'). Теперь мы можем задать вопрос, кто нравится Васе. ?-нравится(вася,Кто). Кто=лена ; Кто=андрей ; Кто=виталий ; НЕТ Андрей и Виталий нравятся Васе, потому, что любят рок- музыку, а Лена просто нравится(т.к. этот факт неосредственно указан в базе данных), хотя может и не любит рок-музыку. Рассмотрим еще один пример правила и на этом примере разберем процесс поиска ответа Прологом. Пример представляет собой родственные отношения между людьми. Аналогичные примеры стали уже классическими для Пролога и повторяются практически во всех книгах о Прологу. [см. список литературы в конце данного руководства] Имеем предикаты: женщина(Х) - об'ект Х является женщиной. мужчина(Х) - об'ект Х является мужчиной. сестра(Х,Y) - об'ект Х является сестрой Y. родители(X,Y,Z) - Y и Z являются родителями X , причем Y - отец, а Z - мать. Формируем базу данных: женщина(лариса). родители(лариса,виктор,татьяна). родители(константин,виктор,татьяна). родители(елена,виктор,татьяна). женщина(елена). сестра(виктория,константин). А теперь определим первое правило. Об'ект X будет являться сестрой об'екта Y, в том случае, если у X и Y общие родители и кроме того X является женщиной ( иначе это брат ). сестра(X,Y):-женщина(X),родители(X,Папа,Мама),родители(Y,Папа,Мама). Переменные "Папа" и "Мама" являются вспомогательными и используются для поиска решения. А теперь зададим несколько вопросов. 1) Кто является сестрой Константину ? ?-сестра(Кто,константин). Кто=виктория ; Кто=лариса ; Кто=елена ; НЕТ В базе содержится факт, что Виктория является сестрой Константина, а то, что Лариса и Елена являются сестрами Константина выводится на основе правила о сестрах. Рассмотрим подробнее как это происходит. 1) Сначала вопрос: сестра(Кто,константин) согласуется с фактом из базы данных: сестра(виктория,константин). При этом переменная Кто принимает значение виктория и это значение выводится в качестве ответа. 2) После ввода точки с запятой, Пролог начинает поиск нового решения с отмеченного места, но следующее утверждение с которым согласуется вопрос, является правило: сестра(X,Y):-женщина(X),родители(X,Папа,Мама),родители(Y,Папа,Мама). Вопрос согласуется с левой частью правила, при этом Y принимает значение константин, а переменные X и Kто остаются неконкретизированными, но становятся СЦЕПЛЕННЫМИ. Если одна из них получит какое-нибудь значение, то другой будет автоматически присвоено то же значение. Теперь, чтобы доказать вопрос, Прологу необходимо доказать правую часть правила. 3) Начинает согласовываться правая часть правила - коньюнкция следующих утверждений: женщина(X),родители(X,Папа,Мама),родители(константин,Папа,Мама). ( Напомним,что Y заменен на константина ) Первый вопрос согласуется с фактом:женщина(лариса). Процесс согласования очередного утверждения, как обычно, начинается с начала базы данных. Переменная X принимает значение лариса и переменная Кто также теперь имеет значение лариса из-за сцепле- ния. Теперь начинает согласовываться второй вопрос коньюнкции: родители(лариса,Папа,Мама). 4) Вопрос: родители(лариса,Папа,Мама) согласуется с фактом: родители(лариса,виктор,татьяна), переменная Папа становится равной виктор, а Мама - татьяна. 5) Остается доказать последний вопрос: родители(константин,виктор,татьяна). Все переменные в правиле уже получили значения, и последний вопрос уже не содержит переменных. В базе имеется факт: родители(константин,виктор,татьяна) , и вопрос доказан. 6) Теперь доказаны все утверждения и Пролог выводит полученное решение: значение переменной Кто через сцепление с X оказалось равной лариса, что и выводится на экран. 7) После ввода точки с запятой Пролог пытается повторно доказать последнее из доказанных утверждений. Вопрос: родители(константин,виктор,татьяна) повторно не может быть согласован, т.к. второго такого факта нет, поэтому выполняется возврат к предыдущему вопросу: родители(лариса,Папа,Мама) . Переменные Папа и Мама снова стали неконкретизированные и процесс повторного согласования начинается с третьего факта базы, поскольку второй факт был как раз согласован с данным вопросом ранее. Этот вопрос тоже не удается повторно согласовать. 8) Теперь снова выполняется согласование вопроса: женщина(X); переменные Х и Кто снова свободны, но остаются сцепленными. Этот вопрос удается согласовать с фактом: женщина(елена). Переменные Х и Кто принимают значение елена, и теперь Пролог снова пытается доказать второе и третье утверждения правила, ПРИЧЕМ ПРОЦЕСС ДОКАЗАТЕЛЬСТВА НАЧИНАЕТСЯ С НАЧАЛА БАЗЫ ДАННЫХ. 9) Второй вопрос: родители(елена,Папа,Мама) согласуется с базой данных и переменные Папа и Мама принимают значения соответст- венно: виктор и татьяна. 10)Третий вопрос: родители(константин,виктор,татьяна) согласуется с соответствующим фактом и Пролог выводит очередной ответ: Кто=елена. 11)Снова после ввода точки с запятой Пролог пытается передоказать правую часть правила в обратном порядке. Но больше согласований ни у одного утверждения нет. Нет также и согласований у исходного вопроса: сестра(Кто,константин). Поэтому выводится НЕТ и процесс решения закончен. Зададим теперь следующий вопрос: Кто является сестрой Елены ? ?-сестра(елена,Кто). Кто=лариса ; Кто=елена ; НЕТ Итак, Елена оказалась сестрой самой себе. Правило определения сестры явно содержит дефект. Для его устранения можно использовать встроенный предикат Пролога "\=" ( не равно ), который мы в дальнейшем рассмотрим. В книге [1] приводится несколько наглядных примеров процесса согласования утверждений Пролога, которые рекомендуется внимательно изучить. К вопросу согласования мы вернемся в разделе о трассировке. ПРИМЕРЫ ДРУГИХ ПРАВИЛ РОДСТВЕННЫХ ОТНОШЕНИЙ. Определение отца: отец(X,Y) X - является отцом Y. отец(X,Y):-родители(Y,X,_). Определение корректно, так как второй аргумент предиката родители определяет отца. Зададим вопросы к рассмотренной ранее базе данных: Кто является отцом Ларисы ? ?-отец(X,лариса). X=виктор ; НЕТ Кто является отцом кому-нибудь ? ?-отец(X,_). X=виктор ; X=виктор ; X=виктор ; НЕТ Три ответа получилось потому, что у Виктора трое детей. Теперь определим дедушку. дедушка(X,Y) X - является дедушкой Y. Об'ект X является дедушкой Y, если существует такой об'ект A, что X является отцом A и A является отцом Y. Определить понятие дедушки можно через родителей или через уже определенное понятие отца. дедушка(X,Y):-отец(X,A),отец(A,Y). Сформируем следующую базу данных: отец(виктор,константин). отец(константин,борис). отец(борис,николай). Зададим вопрос: Кто кому является дедушкой ? ?-дедушка(Кто,Кому). Кто=виктор Кому=борис ; Кто=константин Кому=николай ; НЕТ Определим теперь более сложное понятие предок. ( Точнее предок только по отцовской линии ) Добавим в базу данных еще одно отношение: отец(николай,александр). Теперь цепочка от предков к потомкам выглядит следующим образом: виктор --> константин --> борис --> николай --> александр . Конечно, X будет предком Y, если X отец Y . А вот дальше можно попытаться определить прадедушку, прапрадедушку и т.д. Например, прадедушку можно определить следующей цепочкой: предок(X,Y):-отец(X,A),отец(A,B),отец(B,Y). Существует, однако, более изящное определение предка, используя понятие РЕКУРСИИ. РЕКУРСИВНЫМ называется определение, в котором об'екты определяются сами через себя. Рекурсивное оределение понятия предка выглядит следующим образом: об'ект X является предком об'екта Y, если X - отец Y, или существует такой об'ект Z, для которого X является отцом, а Z в свою очередь является предком Y. Интуитивно такое определение очевидно, и на Прологе оно записывается в виде двух правил: предок(X,Y):-отец(X,Y). предок(X,Y):-отец(X,Z),предок(Z,Y). После ввода правил зададим вопрос:кто кому является предком ? ?-предок(Кто,Кому). Кто=виктор Кому=константин ; Кто=константин Кому=борис ; Кто=борис Кому=николай ; Кто=николай Кому=александр ; Кто=виктор Кому=борис ; Кто=виктор Кому=николай ; Кто=виктор Кому=александр ; Кто=константин Кому=николай ; Кто=константин Кому=александр ; Кто=борис Кому=александр ; НЕТ Итак, были получены все возможные ответы на вопрос о предках. Постарайтесь понять, почему ответы выводятся именно в таком порядке, посмотрев еще раз принцип согласования утверждений Пролога. Понятие рекурсии является довольно сложным, но чрезвычайно полезным и широко используется при конструировании программ на Прологе. Более подробно мы не можем останавливаться на этом понятии и отсылаем Вас к литературе, список которой приведен в конце данного руководства. Правда, в дальнейшем нам еще встре- тятся несколько рекурсивных примеров. СПИСКИ Списки - широко используемая структра данных во многих языках прграммирования. Существует даже специальный язык программирования - ЛИСП, в котором список является единственной структурой данных. В Прологе также имеются списки, но их роль более скромная, хотя они используются во многих задачах. Список представляет собой упорядоченную последовательность элементов,заключенную в квадратные скобки "[]". Причем, сами элементы могут являться списками. Рассмотрим примеры: [] - пустой список, не содержащий элементов [1,2,3,4] - числовой список из четырех элементов [книга,[дюма,три_мушкетера]] - список из двух элементов, причем второй элемент является списком. [[a,b],c,[a,l]] - список из трех элементов: [a,b], c, [a,l] Процесс согласования для элементов списка может выполняется обычным образом. Посмотрите, на приведенные ниже примеры: p([1,2,3]). p([эта,кошка,сидела,[на,этой,подстилке]]). ?-p(X). X=[1,2,3] ; X=[эта,кошка,сидела,[на,этой,подстилке]] ; НЕТ ?-p([X,Y,Z]). X=1 Y=2 Z=3 ; НЕТ ?-p([A,B,_,D]). A=эта B=кошка D=[на,этой,подстилке]] ; НЕТ Кроме того имеется специальное разбиение списка на ГОЛОВУ и ХВОСТ. ГОЛОВОЙ списка называется первый элемент списка, а ХВОСТОМ - оставшйся список, исключая первый элемент. Рассмотрим примеры: СПИСОК ГОЛОВА ХВОСТ [1,2,3,4] 1 [2,3,4] [[A,B],C] [A,B] [C] [[a]] [a] [] - пустой список [1] 1 [] [1,[2]] 1 [[2]] Для отделения головы и хвоста списка используется специальное обозначение: [X|Y] X - обозначает голову списка, а Y - хвост списка. Таким образом к рассмотренной выше базе данных можно обратиться с вопросами: ?-p([X|Y]). X=1 Y=[2,3] ; X=эта Y=[кошка,сидела,[на,этой,подстилке]] ; НЕТ ?-p(_,_,_,[X|Y]]). X=на Y=[этой,подстилке] ; НЕТ Существует еще одна область применения списков - представление литер. Если строка символов заключена в двойные кавычки, то эта строка представляется как список кодов, соответствующих символам строки. Пример: p("system"). ?-p(X). X=[115,121,115,116,101,109] ; НЕТ ПРИМЕРЫ ОПРЕДЕЛЕНИЯ ПРЕДИКАТОВ ДЛЯ ОБРАБОТКИ СПИСКОВ. Предположим, что имеется некоторый список, например, список домашних животных: [кошка,собака,курица,корова] . Мы хотим определить, содержится ли некоторое имя животного в указанном списке. С этой целью определим предикат : принадлежит(Элемент,Список) . Как и для подавляющего большинства предикатов обработки списков определение рекурсивно. Эмемент может содержаться или в голове или в хвосте списка, а в связи с этим и появляются два простых правила: принадлежит(X,[X|_]). принадлежит(X,[_|Y]):-принадлежит(X,Y). Проверим правильность определения предиката на простых примерах. ?-принадлежит(курица,[кошка,собака,курица,корова]). ДА ?-принадлежит(овца,[кошка,собака,курица,корова]). НЕТ Рассмотрим кратко принцип работы предиката на указанных примерах. Пусть мы ввели первый вопрос. Сначала делается попытка согласовать вопрос с первым правилом. Поскольку значение X ( курица ) не совпадает с головой списка ( кошка ), происходит попытка согласовать вопрос со вторым правилом. При этом значение Y становится равным хвосту исходного списка: Y=[собака,курица,корова], и процесс согласования начинается сначала. Снова элемент X не совпадает с головой списка и опять происходит обращение ко второму правилу. После согласования со вторым правилом, целевое утверждение принимает вид:( правая часть второго правила ) принадлежит(курица,[курица,корова]) Теперь данное утверждение согласуется с первым правилом, причем переменная X имеет значение "курица", а анонимная переменная равна хвосту списка "[корова]" . Больше несогласованных целей не осталось, и Пролог выводит ответ "ДА" . Во втором случае ситуация другая. В этом запросе также происходит постепенное уменьшение списка с головы, но согласования с первым правилом не происходит, и, наконец, наступает момент, когда после очередного согласования со вторым правилом, цель принимает вид: принадлежит(овца,[]) . Данная цель уже не согласуется ни с первым, ни со вторым утверждением. Поэтому ответ на данный запрос "НЕТ" . Можно задать вопрос и с переменными. ?-принадлежит(Элемент,[кошка,собака,курица,корова]). Элемент=кошка ; Элемент=собака ; Элемент=курица ; Элемент=корова ; НЕТ При каждом повторном обращении к предикату, переменная Элемент принимает значение очередного элемента списка. Это свойство предиката широко используется в задачах, где нужно применить какое-нибудь действие к каждому элементу списка. Второй пример, состоит в определении предиката "присоединить". Данный предикат имеет три аргумента: присоединить(X,Y,Z) и позволяет два списка X и Y об'единить в один список Z. Этот предикат в ответ на запросы должен работать следующим образом: ?-присоединить([a,b,c],[1,2],[a,b,c,1,2]). ДА ?-присоединить([кошка,собака,курица],[корова,овца],Сцепленный_список). Сцепленный_список=[кошка,собака,курица,корова,овца] Можно даже спросить: ?-присоединить(X,[3,4],[1,2,3,4]). X=[1,2] В последнем примере появляется возможность восстановить первый из сцепленных списков. Такова одна из приятных особенностей языка Пролог, определив некоторый предикат, у нас появляется возможность решать не только прямую, но и обратные задачи. Предикат "присоединить" определяется с помощью двух правил: присоединить([],L,L). присоединить([X|L1],L2,[X|L3]):-присоединить(L1,L2,L3). Выход на граничное условие происходит, когда первый аргумент является пустым списком. Любой список, присоединенный к пустому списку, дает тот же самый список. Во всех других случаях будет согласовываться второе правило, смысл которого можно пояснить следующим образом: 1) Первый элемент первого списка (X) всегда будет и первым элементом третьего списка. 2) Хвост третьего аргумента(L3) всегда будет результатом присоединения второго аргумента(L2) к хвосту первого списка(L1). 3) Так как при каждом обращении к пправилу удаляется голова первого списка, то постепенно этот список будет исчерпан и станет пустым, так что произойдет выход на граничное условие. Более подробно останавливаться на списках мы не имеем возможности и отсылаем вас к списку литературы. РАВЕНСТВО В Прологе существует особый предикат РАВЕНСТВО, обозначаемый "=" . Этот предикат ставится между операндами, т.е. является ИНФИКСНЫМ ОПЕРАТОРОМ. Для большей наглядности скажем что оператор + в формуле 2+2 является инфиксным, а в формуле 2 2 + (такая формула может исользоваться при счете на калькуляторе МК-61 или при программировании на языке Форт) дан- ный оператор будет являться постфксным, т.е. стоящим после аргументов. Об операторах мы поговорим в отдельной главе, а пока поговорим о равенстве. Предикат РАВЕНСТВО является ВСТРОЕННЫМ, т.е. он определен в Пролог - системе. При согласовании с базой цели X=Y, где X и Y -произвольные элементы действуют следующие правила: 1) Если X и Y неконкретизированные переменные, то производится их сцепление, и если в дальнейшем одна из них получит какое- нибудь значение, то и другая примет то же значение. 2) Как только одна из величин X или Y станет неконкретизирован- ной переменной, то она сразу же примет значение другой величины. 3) атомы и числа равны сами себе. 4) Две структуры равны, если они имеют один и тот же предикат и одинаковое количество аргументов, причем аргументы согласуются друг с другом по приведенным выше правилам. Примеры: ?-рейс(Откуда,москва)=рейс(барнаул,москва). Откуда=барнаул ; НЕТ Кроме предиката равенства в Прологе имеется более строгий предикат "==". Он действует точно также, как и равенство, но две неконкретизированные переменные, ранее не сцепленные друг с другом, не согласуются для данного предиката. Примеры: школьник(коля). ?-X=Y,школьник(X). X=коля Y=коля ; НЕТ ?-X==Y,школьник(X). НЕТ ?-школьник(X),X==Y. X=коля Y=коля ; НЕТ Кроме равенства и строгого равенства существуют и обратные к ним предикаты: "\=" и "\==" которые согласуются с базой данных только в том случае, когда не согласуются соответствующие им предикаты: "=" и "==" . Рассмотрим один пример. Ранее мы определяли правило для сестры: сестра(X,Y):-женщина(X), родители(X,Папа,Мама), родители(Y,Папа,Мама). При использовании этого правила, мы обнаружили, что можно оказаться сестрой самой себе. Чтобы это исключить, добавим к определению один предикат: сестра(X,Y):-женщина(X),родители(X,Папа,Мама)родители(Y,Папа,Мама), X\=Y. Добавим в базу факты: женщина(лариса). женщина(елена). родители(лариса,виктор,татьяна). родители(елена,виктор,татьяна). и зададим вопрос: ?-сестра(X,елена). X=лариса ; НЕТ без предиката X\=Y мы бы получили еще и второй ответ: X=елена . АРИФМЕТИКА В Прологе имеется ряд встроенных предикатов, для сравнения чисел и выполнения над числами арифметических действий. Рассмотрим сначала сравнение чисел. Имеются следующие предикаты для сравнения: X=Y числа X и Y равны между собой X\=Y числа X и Y не равны друг другу XY число X больше числа Y X==Y число X больше или равно числу Y Все эти встроенные предикаты являются инфиксными операторами и располагаются между своими аргументами. Аргументами каждого из них должны быть числа, в противном случае на экран будет выдано сообщение об ошибке ( типы ошибок см. в конце руководства), предикат согласуется с базой, если выполняется соответствующее условие, причем СОГЛАСОВАНИЕ ВЫОЛНЯЕТСЯ ОДИН РАЗ. ПРИ ПОВТОРНОЙ ПОПЫТКЕ СОГЛАСОВАТЬ, ВОЗНИКАЕТ НЕУДАЧА. Рассмотрим примеры: ?-3>2 . ДА ?-3<3 . НЕТ ?-3>=3 . ДА Обратите внимание, что заключительная точка должна быть отделена от числа по крайней мере одним пробелом, иначе она воспринимается как десятичная точка вещественного числа, работа с которыми не реализована в описываемой версии языка Пролог. Заполним базу данных о руководителях нашего государства. Для этого определим предикат: правил(X,Y,Z), где X - имя руководителя, а Y и Z - соответственно начальный и конечный год правления. правил(ленин,1917,1924). правил(сталин,1924,1953). правил(хрущев,1953,1964). правил(брежнев,1964,1982). Определим теперь предикат руководитель_страны(X,Y), который истинный, если лицо X руководило страной в году Y. Этот предикат определяется через предикат "правил" по правилу: X был руководителем, если X правил с года A по год B и Y находится между A и B или совпадает с A или B. На Прологе это записывается следующим образом: руководитель_страны(X,Y):-правил(X,A,B),Y>=A,Y<=B. Добавив данное правило к базе, мы можем задать ряд вопросов о руководителях нашего государства. 1) Являлся ли Сталин руководителем госудрства в 1930 году ? ?-руководитель_страны(сталин,1930). ДА 2) Кто был руководителем страны в 1924 году ? ?-руководитель_страны(Кто,1924). Кто=ленин ; Кто=сталин ; НЕТ В Прологе определены следующие предикаты для вычисления арифметических выражений. X + Y - сложение X - Y - вычитание X * Y - умножение X / Y - деление целых чисел X mod Y - остаток от деления целых чисел Следует иметь ввиду, что вычисления напрямую с помощью этих предикатов не производятся, а выполняется обычный процесс согласования. Рассмотрим пример: 3+5 . ?-3+5 . ДА ?-3+4 . НЕТ ?-Т+М. Т=3 М=5 ; НЕТ Для собственных вычислений вводится предикат is . Он как и другие арифметические предикаты является инфиксным оператором, т.е. ставится между аргументами. A is B , при выполнении этого предиката вычисляется правая часть и делается попытка согласовать полученное с левой частью. Рассмотрим примеры: ?-8 is 3+5 . ДА ?-Т is 3+6*2 . T=15 ?-L is (5+6)/3 . L=3 Рассмотрим пример использования предиката is . Имеем базу данных о населении некоторых стран и площади их территории. население(сша,203). население(индия,548). площадь(сша,8). площадь(индия,3). Для простоты взяты только две страны. Определим теперь предикат "плотность", который обозначает среднюю плотность населения данной страны. Как известно, значение плотности получается путем деления числа, представляющего население, на число, представляющее площадь. плотность(X,Y):-население(X,P),площадь(X,A),Y is P/A. Добавив правило в базу данных это правило, зададим несколько вопросов о плотности населения. 1) Какова плотность населения США ? ?-плотность(сша,P). P=25 2) У какой страны плотность населения равна 182 ? ?-плотность(C,182). C=индия ; НЕТ 3) Каковы плотности населения всех стран, сведения о которых занесены в базу данных ? ?-плотность(Страна,Плотность). Страна=сша Пплотность=25 ; Страна=индия Плотность=182 ; НЕТ Получившиеся результаты плотности несколько неточны, т.к. ввиду отсутствия в данной версии языка вещественной арифметики было произведено округление. Но не спешите разочаровываться в Прологе - этот язык не совсем подходит для вычислений, но зато позволяет сделать то, что невозможно сделать при помощи какого- либо другого языка. ПРЕДИКАТ ОТРИЦАНИЯ Предикат отрицания в Прологе имеет вид: not(X), X - целевое утверждение, для которого будет производится попытка согласования с базой данных. Если целевое утверждение X согласуется с базой данных, то весь предикат: not(X), напротив, не согласуется и наоборот, при неудаче согласования X, предикат отрицания согласуется с базой данных. Рассмотрим простые примеры использования предиката отрицания. человек(адам). человек(ева). ?-not(человек(адам)). НЕТ ?-not(человек(иисус)). ДА Теперь зададим более сложный вопрос: ?-not((человек(адам),not(человек(ева)))). ДА Целевое утверждение: "человек(адам)" согласуется с базой данных, "человек(ева)" также согласуется, поэтому его отрицание: "not(человек(ева))" не согласуется, значит не согласуется и коньюнкция этих двух выражениий, поэтому результатом первого предиката отрицания будет ответ "да". т "б Обратите внимание на двойные скобки после первого предиката not. Если задать данный вопрос в виде: ?-not(человек(адам),not(человек(ева))). то в результате будет выдано сообщение об ошибке, потому что запятая будет обозначать разделитель аргументов первого предиката not, а предикат not должен иметь только один аргумент. При использовании предиката not имеется одна особенность, на которую мы хотим обратить внимание. Зададим еще два вопроса: ?-человек(ева). ДА ?-not(not(человек(ева))). ДА В результате двойного отрицания получился такой же результат, как при отсутствии отрицаний. А теперь рассмотрим пример, в котором используются переменные. Вводим: животное(собака). растение(тюльпан). ?-животное(X),растение(X). НЕТ ?-not(not(животное(X))),растение(X). X=тюльпан ; НЕТ Итак в данном примере двойное отрицание взаимно "не уничтожается". В первом вопросе предикат "животное(X)" согласуется с базой данных и X принимает значение "собака", второй предикат при данном значении X не согласуется с базой и получается ответ "НЕТ" . Во втором вопросе, в результате двойного отрицания, предикат "not(not(животное(X)))" согласуется с базой, НО ПЕРЕМЕННАЯ X В РЕЗУЛЬТАТЕ ТАКОГО СОГЛАСОВАНИЯ ОСТАЕТСЯ НЕКОНКРЕТИЗИРОВАННОЙ. Поэтому второй предикат согласуется с базой и выводится ответ: "X=тюльпан". ДИЗЬЮНКЦИЯ ЦЕЛЕВЫХ УТВЕРЖДЕНИЙ. Дизьюнкция означает логическое "или". Дизьюнкция в Пролог обозначается ; (точка с запятой). Рассмотрим вопрос: ?-X;Y. , где X и Y - некоторые целевые утверждения. Сначала делается попытка согласовать цель X. Если согласование успешно, то успешно согласование и всей дизьюнкции, в противном случае делается попытка согласовать цель Y. При неудаче согласования Y, дизьюнкция не согласуется. Определим предикат "человек". Человеком считаем Адама и Еву или об'ект, у которого мать является человеком. человек(X):-X=адам;X=ева;мать(X,_). Добавим пару фактов: мать(каин,ева). мать(авель,ева). А теперь зададим вопрос: ?-человек(X). X=адам ; X=ева ; X=каин ; X=авель ; НЕТ Дизьюнкцию можно использовать в любом месте, где может быть использовано другое целевое утверждение. Однако увлекаться применением дизьюнкций не следует, т.к. это ведет к менее наглядным программам. В подавляющем числе случаев дизьюнкцию можно заменить использованим нескольких фактов или правил. Например, приведенный выше пример, можно записать в виде: человек(адам). человек(ева). человек(X):-мать(X,_). Лишь в некоторых случаях при использовании отсечений (см. далее)нельзя преобразовать дизьюнкцию в несколько утверждений Пролога. ОТСЕЧЕНИЕ Этот раздел посвящен специальному механизму, используемому в программах на Прологе и называемому "отсечением". Отсечение позволяет указать, какие из ранее сделанных выводов не следует пересматривать при возврате по цепочке согласованных утверждений. Синтаксически отсечение обозначается "!" - как предикат не имеющий аргументов. На предикат отсечения можно смотреть как на некий забор, разделяющий целевые утверждения. Так при обработке коньюнкции: p:-a,b,c,!,d,e,f Пролог без каких-либо ограничений может выполнять возврат и повторное согласование целей a, b, c, но как только цель c будет согласована с базой, происходит "перешагивание" через "забор" и согласованные цели a, b, c - "замораживаются". Теперь Пролог начинает доказывать цели d, e, f, выполняя между ними возвраты и повторные согласования, пока не наступит момент, когда цель d уже не может быть согласована и выполнится шаг назад к цели c. Но теперь цели a, b, c больше не согласуются ни с одним утверждением базы данных и доказательство всей коньюнкции заканчивается неудачей. Более того, неудачей заканчивается и доказательство предиката p в целевом утверждении, которое было согласовано с данным правилом. Теперь рассмотрим примеры применения отсечений. Пусть имеется база данных о читателях библиотеки. Каждому читателю доступен ряд услуг. Предположим для простоты, что услуг две: читатель может сдать книги, находящиеся у него на руках и взять новые книги. Допустим, что читатель не имеет права брать новые книги, пока не сданы старые. Определим предикат "услуги", который для каждого читателя, может сообщить, какие услуги ему доступны. услуги(Читатель,Виды_услуг):-книга_не_возвращена(Читатель,Книга), !,Виды_услуг=сдать_книги. услуги(Читатель,сдать_книги). услуги(Читатель,взять_книги). Добавим к базе информацию о читателях Иванове и Петрове. читатель(иванов). читатель(петров). книга_не_возвращена(иванов,три_мушкетера). Итак, у Иванова имеется несданая книга. А теперь зададим вопрос об услугах, доступных читателям. ?-читатель(Кто),услуги(Кто,Какие). Кто=иванов Какие=сдать_книги ; Кто=петров Какие=сдать_книги ; Кто=петров Какие=взять_книги ; НЕТ Посмотрим, почему так получилось. Сначала цель "читатель(Кто)" согласуется с базой и "Кто" становится равным "иванов". Теперь делается оытка согласовать второй предикат "услуги(иванов,Какие) " . Он согласуется с первым правилом об услугах и теперь очередной целью становится: "книга_не_возвращена(иванов,Книга) ". Она согласуется, т.к. у Иванова имеется на руках книга "три мушкетера ". Далее идет отсечение и предикат равенство дает значение переменной "Виды_услуг " "сдать_книги". Это значение выводится в качестве решения. При повторной попытке согласования начинает действовать отсечение: БОЛЬШЕ ПРЕДИКАТ УСЛУГИ НЕ МОЖЕТ БЫТЬ СОГЛАСОВАН. Для второго читателя ситуация иная. Здесь первое утверждение правой части правила для услуг не согласуется, поскольку у Петрова нет несданых книг, поэтому цель "услуги(петров,Какие) " последовательно согласуется с двумя другими утверждениями для предиката услуг. ПРЕДИКАТ FAIL Данный предикат не имеет аргументов и никогда не согласуется с базой данных. Он бывает удобен при совместном использовании с предикатом отсечения. Отсечение вместе с fail, говорит о том, что если процесс согласования дошел до данного места, то надо вернуться назад, здесь решений не будет. Пусть, например, мы хотим разработать программу вычисления налога по некоторым правилам. Сначала исключим из категории граждан, подлежащих налогообложению, иностранцев. Определение предиката "налог(X,Y)", где X - гражданин, а Y - величчина налога, может начинаться следующим образом: налог(X,Y):-иностранец(X),!,fail. налог(X,Y):- ..... Если X окажется иностранцем, то никаких дальнейших согласований предиката "налог" производиться не будет, т.к. предикат fail приведет к неудаче согласования коньюнкции правила, а отсечение прекратит дальнейший поиск решений для предикатов "иностранец" и "налог". ПРЕДИКАТЫ, РАСПОЗНАЮЩИЕ ТИП ВЫРАЖЕНИЯ. В данной версии Пролога реализованы три таких предиката. 1) Предикат var(X) согласуется с базой данных, если на момент согласования X является неконкретизированной переменной. Примеры: ?-var(X). ДА ?-var(23). НЕТ ?-X=Y,Y=23,var(X). НЕТ 2) Предикат atom(X) согласуется с базой данных, если на момент согласования X представляет собой атом. ?-atom(2). НЕТ ?-atom(яблоко). ДА ?-X=человек(адам),atom(X). НЕТ 3) Предикат integer(X) согласуется с базой данных, если на момент согласования X является целым числом. ?-T is 2+3,integer(T). T=5 Коньюнкция двух целевых утверждений согласуется, поскольку предикат аргументом integer является число. ТРАССИРОВКА И ОТЛАДКА ПРОГРАММ Трассировка позволяет проследить процесс выполнения программы по шагам. На каждом шаге трассировки печатается целевое утверждение, которое в данный момент подлежит согласованию, и тип происходящего события. Возможны четыре типа событий: 1) CALL - Данное событие фиксирует начало попытки Пролога согласовать цель с базой данных. 2) EXIT - Событие фиксирует момент, когда цель только что согласована с базой данных. 3) REDO - Событие происходит, когда Пролог возвращается к цели, пытаясь повторно согласовать ее с базой данных. 4) FAIL - Событие фиксирует момент, когда попытка согласовать цель с базой заканчивается неудачей. Средства отладки сообщают нам о моментах возникновения событий этих четырех видов в ходе выполнения программы. Для включения трассировки следует набрать: ?-trace. После появления каждого сообщения, следует нажимать любую клавишу. Для отключения трассировки следует набрать: ?-notrace. Рассмотрим пример трассировки для предиката "сестра". Дана база данных: сестра(X,Y):-женщина(X),родители(X,Папа,Мама),родители(Y,Папа,Мама). женщина(елена). женщина(ирина). родители(елена,николай,ольга). родители(ирина,николай,ольга). ?-trace. - включаем трассировку EXIT: trace ДА - трассировка включена ?-сестра(Кто,елена). - Кто является сестрой Елены ? CALL: сестра(Кто,елена) - первое согласование "сестры" EXIT: сестра(_0,елена) - выполнилось согласование с ле- вой частью правила для сестры. _0 означает связанную перемен- ную CALL: женщина(_0) - начинается попытка согласовать первый предикат правой части правила EXIT: женщина(елена) - предикат согласован с фактом CALL: родители(елена,Папа,Мама) - согласуется второй пре- дикат правила EXIT: родители(елена,николай,ольга) - предикат согласован CALL: родители(елена,николай,ольга) - третий предикат EXIT: родители(елена,николай,ольга) - согласован Кто=елена - решение ; - продолжение поиска REDO: родители(елена,николай,ольга) - повторное согласование последнего доказанного предиката FAIL: родители(елена,николай,ольга) - повторное согласование не удалось REDO: родители(елена,Папа,Мама) - повторное согласование второго предиката правила FAIL: родители(елена,Папа,Мама) - также неудача REDO: женщина(_0) - теперь снова согласуется первый предикат правила EXIT: женщина(ирина) - а для этого предиката нашлось еще одно решение CALL: родители(ирина,Папа,Мама) - поэтому второй предикат правила начал согласовы- ваться заново EXIT: родители(ирина,николай,ольга) - для него нашлось решение CALL: родители(елена,николай,ольга) - так выглядит третий пре- дикат при полученных зна- чениях переменных. Он также согласуется с начала EXIT: родители(елена,николай,ольга) - цель согласована, такой факт есть Кто=ирина - второе решение ; REDO: родители(елена,николай,ольга) - снова повторно согласует- ся последний доказанный предикат FAIL: родители(елена,николай,ольга) - второго такого факта нет REDO: родители(ирина,Папа,Мама) - второй предикат согласу- ется повторно FAIL: родители(ирина,Папа,Мама) - других родителей у Ирины нет REDO: женщина(_0) - есть ли еще женщины ? FAIL: женщина(_0) - других женщин, кроме Ири- ны и Елены в базе нет REDO: сестра(Кто,елена) - может есть другие правила или факты о сестрах ? FAIL: сестра(Кто,елена) - сведений о сестрах тоже нет НЕТ - поэтому выводится окон- чательный ответ ?-notrace. - отключаем трассировку CALL: notrace ДА - трассировка отключена ПРЕДИКАТЫ ВВОДА - ВЫВОДА Данные предикаты позволяют вводить с экрана один символ или утверджение Пролога или выводить на экран символы или утвержде- ния Пролога. 1) Предикат get0 . Целевое утверждение: get0(X) согласуется с базой данных, если X может быть сопоставлено с символом введен- ным с экрана. Можно вводить как обычные символы, так и управля- ющие ( код до 32 ). ?-get0(X). После набора этого вопроса необходимо нажать какую-нибудь клавишу. Допустим, нажата "1". Код этого символа 49 и поэ- тому на экране появится: X=49 ; НЕТ Еще два примера:( нажимается клавиша "1" ) ?-Y=49,get0(Y). ДА ?-get0(Y),Y=40 . НЕТ Кроме предиката get0 в Прологе определяется предикат get, который отличается тем, что воспринимает только коды символов ( но не управляющие,т.е. коды большие 32 ). В данной версии этот предикат не реализован, его можно легко определить через get0 (см. [1] ) 2) Противоположным по действию является предикат put(X) . Если значением X является код некоторого символа, то этот символ выводится на экран. ?-put(49). 1ДА ?-X=49,put(X). 1X=49 ; НЕТ ?-put(a). ДА По приведенным примерам видно, что предикат put всегда со- гласуется с базой, но если аргументом является число от 1 до 128, то выводится символ, код которого соответствует данному числу, в противном случае ничего не выводится. 3) Предикаты nl и tab(X) . Данные два предиката используются для удобства вывода. Предикат nl не имеет аргументов и всегда согласуется с базой данных. При выполнении данного предиката производится переход на новую строку экрана дисплея. Аргументом предиката tab(X) должно быть целое число, при выполнении преди- ката на экран выводится количество пробелов, равное значению аргумента. ?-put(49),nl,put(50),tab(3),put(51). 1 2 3ДА Кроме этих предикатов еще реализованы предикаты write и display, но о них мы поговорим в следующей главе, посвященной операторам. ОПЕРАТОРЫ Синтаксис языка Пролог разрешает записывать некоторые преди- каты как ОПЕРАТОРЫ. Это особая форма записи, облегчающая чтение. С операторами мы уже встречались, таковыми, например, являются арифметические операции. Действительно,мы записывали A+B , а не +(A,B) . В Пролог включен ряд встроенных операторов и имеется возможность определить свои операторы по определенным правилам. Следует иметь в виду, что при переводе во внутреннее представ- ление, любое утверждение Пролога преобразуется в предикатную форму. Например, если мы используем утверждение: 5+2*3 , то во внутреннем представлении ему соответствует: +(5,*(2,3)) . Подобный переход является очень удобным и позволяет изящно решить большое число задач. Далее мы рассмотрим правила работы с операторами, а пока вернемся к предикатам вывода: write(X) и display(X) . Для обоих предикатов X должен представлять собой целевое утверждение Пролога,которое и выводится на экран, но предикат write выводит утверждения в обычной форме, в какой они и вводились, а преди- кат display выводит во внутреннем представлении. Рассмотрим пример: ?-write((3+5)*2). (3+5)*2ДА ?-display((3+5)*2). *(+(3,5),2)ДА Оператором является и коньюнция. Например,выражение: a,b,c преобразуется к виду: ,(a,,(b,c)). Предикаты ":-" и "?-" также являются операторами и преобразуются соответственно: a :- b :-(a,b) ?-a ?-(a) Используя предикат display пользователь всегда может посмотреть на внутреннее представление утверждений Пролога, которое всегда бывает в предикатной форме. А теперь поговорим о правилах определения операторов. Каждый оператор характеризуется ПРИОРИТЕТОМ, ПОЗИЦИЕЙ и АССОЦИАТИВНОСТЬЮ. ПРИОРИТЕТ определяет порядок выполнения операторов в выражении. Он представляет собой число от 0 до 255. Чем меньше приоритет, тем раньше должен быть выполнен оператор. Например, встроенные предикаты умножения "*" и сложения "+" имеют соответственно приоритеты: 21 и 31 . (Список встроенных операторов см. далее ). Поэтому при записи выражения: a+b*c оно преобразуется к виду: +(a,*(b,c)) , а не к виду: *(+(a,b),c) . Второе внутреннее представление получится, если задать: (a+b)*c . ПОЗИЦИЯ определяет местоположение оператора. Мы уже знаем, что операторы раздеяются на разные групы в зависимости от их распо- ложения относитеьно аргументов. Напомним, что операторы бывают инфиксные, префиксные и постфиксные. Инфиксные операторы ста- вятся между ДВУМЯ своими аргументами, префиксные - перед ОДНИМ своим аргументом, а постфиксные - после ОДНОГО своего аргумента. Встроенным инфиксным оператором является, например, предикат больше ">" , префиксным - предикат "not". Встроенные постфикс- ные операторы отсутствуют и пусть пользователь определит свой постфиксный оператор "<-". Тогда результатами преобразования будут следующие выражения: a>b ----> >(a,b) not s ----> not(s) a<- ----> <-(a) АССОЦИАТИВНОСТЬ определяет порядок выполнения операторов одного приоритета. Пусть дано выражение a+b+b . Его можно интерпрети- ровать как (a+b)+c или a+(b+c). В зависимости от интерпретации получится различное внутреннее представление. Ассоциативность позволяет исключить одну из интерпретаций. Для определения ассоциативности каждому префиксному оператору ставится в соот- ветствие одна из двух спецфикаций: fx или fy. Для постфиксных операторов также возможны две спецификации: xf или yf, а для инфиксных возможны четыре сочетания: xfx , xfy , yfx , yfy . Что же определяет спецификация ? Символ "f" означает оператор, а символ "y" поставленный справа или слева от него означает, что справа( соответственно слева ) МОГУТ НАХОДИТЬСЯ ОПЕРАТОРЫ ЛИШЬ С МЕНЬШИМ ПРИОРИТЕТОМ. Символ "x" находящийся справа или слева означает, что на соответствующем месте МОГУТ НАХОДИТЬСЯ ОПЕРАТОРЫ С МЕНЬШИМ ИЛИ РАВНЫМ ПРИОРИТЕТОМ. Теперь вернемся к выражению: a+b+c . Оператор "+" имеет спецификацию: yfx , но тогда, если сначала выполнять второе сложение, то для первого сложения СПРАВА НАХОДИТСЯ ОПЕРАТОР ТАКОГО ЖЕ ПРИОРИТЕТА, а это запрещает спецификация yfx . При выполнении же сначала первого сложения, для второго плюса СЛЕВА НАХОДИТСЯ ОПЕРАТОР ТОГО ЖЕ ПРИОРИТЕТА. Но спецификация yfx такое допускает и поэтому выра- жение a+b+c интерпретируется как (a+b)+c и преобразуется к виду: +(+(a,b),c). Оператор "not " имеет спецификацию fx, поэтому запись без скобок not not a запрещена, т.к. при этом первый not имеет справа оператор того же приоритета. Предикаты коньюнкции и дизьюнкции ("," и ";") имеют специ- фикации xfy, поэтому, например, выражение a;b;c интерпретирует- ся в виде: a;(b;c) и преобразуется к виду: ;(a,;(b,c)). Кроме встроенных операторов,пользователь может определить свои собственные, используя встроенный предикат op. Предикат op имеет три аргумента: op(<приоритет>,<спецификация>,<имя оператора>) . Предположим, мы хотим определить оператор с именем "<-",который имеет тот же приоритет и спецификацию,что и оператор "+" . Вводим с клавиа- туры: ?-op(31,yfx,<-). и проверяем: ?-display(a+b<-c). <-(+(a,b),c)ДА Подробнее на операторах мы не имеем возможности останавли- ваться. В литературе приводится большое количество примеров использования операторов для решения задач. СООБЩЕНИЯ ОБ ОШИБКАХ Сообщения об ошибках выдаются в виде: ОШИБКА <код> Ниже приводятся коды ошибок и их комментарий. 01 - ПЕРЕПОЛНЕНИЕ ПАМЯТИ . Если возникла подобная ошибка,то это означает, что ваша программа или вышла на бесконечный цикл, или настолько велика, что не может быть выполнена. 02 - СЛИШКОМ ВЕЛИКО ИЛИ МАЛО ЦЕЛОЕ ЧИСЛО. Целое число в утверж- дении Пролога не находится в диапазоне ( -32767 ; 32767 ) 03 - НАРУШЕН БАЛАНС СКОБОК. В утверждении Пролога не совпадает число открывающихся и закрывающихся скобок ( вида "()" или "[]" ) . 04 - ИСЧЕРПАНА ТАБЛИЦА ИМЕН. В данной реализации допускается 146 различных имен, которые может вводить пользователь. Если это количество превышено, выдается данный код. Ошибка встречается крайне редко. При использовании переменных в больших программах,не добавляйте без необходимости лишних имен. Например,для правил p(X,Y):- ... и y(Z,T):- ... мож- но записать: p(X,Y):- ... и y(X,Y):- ... ,заменив Z и Т на X и Y . 05 - НЕ ПРЕДУСМОТРЕНА РАБОТА С ВЕЩЕСТВЕННЫМИ ЧИСЛАМИ. Как пра- вило,подобная ошибка возникает,когда точка ставится сразу после цифры. 06 - ОШИБКА ПРИ ПЕРЕВОДЕ ИЗ ИСХОДНОГО ФОРМАТА ВО ВНУТРЕННИЙ. Наиболее часто встречающаяся ошибка.Синтаксически введено неверное выражение. 07 - ДАННЫЙ СТАНДАРТНЫЙ ПРЕДИКАТ НЕ РЕАЛИЗОВАН. Эта ошибка вам не встретится, она зарезервирована для следующих версий программы. В данной версии реализованы только те предикаты, которые описаны в настоящем руководстве.Остальные согласу- ются с базой данных по обычным правилам. 10 - В СТАНДАРТНОМ ПРЕДИКАТЕ НЕ ЧИСЛОВОЙ АРГУМЕНТ. В некоторых предикатах( "is" , ">" и т.д. ) на месте аргументов долж- ны быть числа. Иначе будет выдан данный код. 11 - НЕПРАВИЛЬНАЯ АРИФМЕТИЧЕСКАЯ ОПЕРАЦИЯ. Такая ошибка возни- кает при делении на 0,а также при получении слишком боль- ших или малых чисел ( вне диапазона -32767 ; 32767 ). 12 - НЕВЕРНЫЙ АРГУМЕНТ У ПРЕДИКАТА op. Предикат "op" требует точного задания своих аргументов. При неверном задании выдается этот код. ЛИТЕРАТУРА В настоящее время на русском языке издано уже довольно много книг по программированию на Прологе. Мы особенно рекомен- дуем вам первые две книги из указанных. В первой приведено хорошее описание языка с иллюстрационными примерами, а во второй дано много примеров оригинальных, простых и интересных программ. 1. У.Клоксин, К.Меллиш Программирование на языке Пролог. М.,"Мир",1987 2. Л.Стерлинг, Э.Шапиро Искусство программирования на языке Пролог. М.,"Мир",1990 3. И.Братко Программирование на языке Пролог для искусственного интеллекта. М.,"Мир",1990 4. К.Кларк, Ф.Маккейб Введение в логическое программирование на микро-Прологе. М.,"Мир",1987