Министерство образования и науки Российской Федерации Омский государственный университет им. Ф.М. Достоевского
УДК 519 ББК 32.973 – 018я73 Ч 188 Рекомендовано к изданию в качестве учебного пособия редакционно-издательским советом ОмГУ 5 октября 2004 г., протокол № 4 Рецензенты: д-р физ.-мат. наук, проф., зав. кафедрой геометрии ОмГПУ А.Н. Зубков; д-р техн. наук, проф. В.А. Филимонов
Чанышев О.Г. Ч 188 ПРОграммирование в ЛОГике: Учеб. пособие. – Омск: Изд-во ОмГУ, 2004. – 64 с. ISBN 5-7779-0510-3
О.Г. Чанышев
Учебное пособие обобщает опыт автора по проведению лекций по теме "Введение в искусственный интеллект" и "Автоматический анализ текста" на математическом факультете Омского государственного университета в 2000–2004 гг. в части, касающейся программирования на языке PDC Prolog. Представлены история языка, разделы программы, основные структуры данных и методы программирования. Изложение сопровождается большим количеством примеров. Полностью приведен исходный текст, разработанной автором в учебных целях «игрушечной» экспертной системы, позволяющей пользователю формулировать вопросы на естественном русском языке. Пособие написано с учетом Государственных образовательных стандартов высшего профессионального образования 431 ен/бак по направлению 511800 «Математика. Компьютерные науки» и 199 ен/сп по специальности «Прикладная математика и информатика». Для студентов математического факультета.
ПРОграммирование в ЛОГике Учебное пособие
УДК 519 ББК 32.973 – 018я73
Изд-во ОмГУ
Омск 2004
© Чанышев О.Г., 2004 © Омский госуниверситет, 2004
ISBN 5-7779-0510-3 2
ОГЛАВЛЕНИЕ Введение ......................................................................................................... 4 1. История Пролога .................................................................................... 10 2. Синтаксис и семантика Пролог-программ........................................ 13 2.1. Объекты данных............................................................................... 13 2.2. Декларативный смысл Пролог-программ...................................... 14 2.3. Основные определения.................................................................... 15 3. Практическое программирование на Прологе ................................. 17 3.1. Структура Пролог-программы........................................................ 18 3.2. Свободные и связанные переменные ............................................. 20 3.3. Внутренняя БД Пролога .................................................................. 21 3.4. Обработка условий и организация циклов в Прологе .................. 23 3.4.1. Обработка условия................................................................. 23 3.4.2. Использование предиката типа repeat .................................. 24 3.5. Списки в Прологе ............................................................................ 26 3.5.1. Примеры списков ................................................................... 26 3.5.2. Разделение списков на "голову" и "хвост"........................... 26 3.5.3. Некоторые полезные программы для работы со списками ................................................................................................... 28 3.6. Ввод и вывод .................................................................................... 30 3.6.1. Файловая система................................................................... 30 3.6.2. Операции с именами файлов................................................. 32 3.6.3. Чтение и запись ...................................................................... 33 3.7. Строки и функции работы со строками ......................................... 34 4. Простенькая экспертная система........................................................ 40 5. Базовые понятия и термины Пролога................................................ 51 5.1. Объекты ............................................................................................ 51 5.2. Внутренние дела Пролога ............................................................... 55 5.3. Что такое шаблоны? ........................................................................ 55 5.4. Управление поиском........................................................................ 56 Заключение.................................................................................................. 58 Контрольные вопросы и задания ............................................................ 59 Список используемой литературы.......................................................... 63
3
Введение В средние века знание латинского и греческого языков являлось существенной частью образования любого ученого. Ученый, владеющий только одним языком, неизбежно чувствовал себя неполноценным, поскольку он был лишен той полноты восприятия, которая возникает благодаря возможности посмотреть на мир сразу с двух точек зрения. Таким же неполноценным ощущает себя сегодняшний исследователь в области искусственного интеллекта, если он не обладает основательным знакомством как с Лиспом, так и с Прологом – этими двумя основополагающими языками искусственного интеллекта, без знания которых невозможен более широкий взгляд на предмет исследования. Иван Братко Логическое программирование базируется на убеждении, что не человека надо обучать мышлению в терминах операций компьютера… а компьютер должен выполнять инструкции, свойственные человеку. Леон Стерлинг, Эхуд Шапиро
Эволюция языков программирования – это движение от языков императивных (как делать) к языкам декларативным (что делать). Или иначе – от программирования в инструкциях компьютера к ПРОграммированию в ЛОГике. Отсюда происходит название языка – ПроЛог, к изучению которого мы и приступаем. Для иллюстрации важнейших черт Пролога воспользуемся примером Братко [1], в котором задается вопрос базе знаний: «Кто у нас темный и большой?» (Номера перед фактами не кодируются.) Программа: 1. большой(медведь). 2. большой(слон). 3. маленький(кот). 4. коричневый(медведь). 5. черный(кот). 6. серый(слон). 4
7. темный(Z):-черный(Z). 8. темный(Z):-коричневый(Z). Вопрос: темный(X),большой(X). Шаги вычисления:
Забегая немного вперед, представляю запись этой же программы на Turbo Prolog'е. (Если используете VP v.5.2, можете писать по-русски все, за исключением типов встроенных переменных, наименований встроенных предикатов, наименований разделов программы). /* Раздел объявления предикатов*/ predicates большой(string) черный(string) коричневый(string) серый(string) темный(string) маленький(string) /*Главная цель-вопрос*/ goal темный(X), большой(X), write(X). /*Правила*/ clauses большой(медведь). большой(слон). маленький(кот). коричневый(медведь). черный(кот). серый(слон). темный(Z):-черный(Z). темный(Z):-коричневый(Z).
1) Исходный список целевых утверждений: темный(X), большой(X). 2) Просмотр всей программы от начала к концу и поиск предложения, у которого голова сопоставима с первым целевым утверждением: темный(X). Найдено предложение 7: темный(Z):-черный(Z). Замена первого целевого утверждения конкретизированным телом предложения 7 – порождение нового списка целевых утверждений: черный(X), большой(X). 3) Просмотр программы для нахождения предложения, сопоставимого с черный(X). Найдено предложение 5: черный(кот). У этого предложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до большой(кот). 4) Просмотр программы в поисках этой цели завершается неуспехом, и происходит возврат к шагу 3 и отмены конкретизации X=кот. Список целей вновь: черный(X), большой(X). Продолжение просмотра ниже предложения 5. Ни одно предложение не найдено. Возврат к шагу 2 и продолжение просмотра ниже предложения 7. Найдено предложение 8: темный(Z):коричневый(Z). Замена первой цели в списке на коричневый(X) дает: коричневый(X), большой(X). 5) Просмотр программы для обнаружения предложения, сопоставимого с коричневый(X) дает коричневый(медведь). У этого предложения нет тела, поэтому список целей уменьшается до большой(медведь). 6) Просмотр программы и обнаружение предложения большой(медведь). У него нет тела, поэтому список целей становится пустым. Это указывает на успешное завершение, а соответствующая конкретизация переменных: X=медведь.
Можно изменить программу: записать факты в специальный файл (с любым именем), а затем загрузить их в раздел фактов: facts – f1 большой(string) маленький(string) коричневый(string) черный(string) темный(string) серый(string)
5
6
goal % Читаем файл bear4.dbs в раздел facts при помощи % встроенного предиката consult consult("bear4.dbs",f1), большой(X), темный(X),!, % Если во внутренней БД существует существует объект X % со свойствами "большой" и "темный", то печатаем % имя этого объекта % знак "!" – откат – есть указание Прологу прекратить про-
Понимание того, что алгоритм – это аксиоматическое задание функции, а его выполнение – частный случай логического вывода, и привело к возникновению логического программирования и языка Пролог. Почти 30 лет прошло с момента его появления. На мой взгляд, сегодня, с появлением Visual Prolog’a пятой версии (компания PDC), Пролог – это самый технологичный язык программирования. Интерес к Прологу вообще на Западе несколько спал после неудачи проекта пятого поколения ЭВМ, однако кризис доверия быстро миновал, и сегодня он более популярен, чем прежде. В России же, если судить по программистской литературе последних лет, Пролог никому не нужен. И этому есть свое объяснение. В Советском Союзе существовало множество высокопрофессиональных коллективов, занимающихся разработкой программного обеспечения для различных отраслей народного хозяйства. Технология предполагала четкое разделение труда, при котором собственно программирование (кодирование) отдельных небольших модулей производилось кодировщиками на основании подробной "гостированной" технической документации, разрабо-
танной постановщиками задач под руководством главного конструктора проекта. В таком случае рабочим языком мог быть ассемблер. Итоговый программный продукт, пройдя комплексную отладку, получался и надежным, и быстрым. Пролог же был еще во многом языком экзотическим и не позволял создавать программы, столь же оптимальные по затратам памяти и быстродействию. К тому же автоматизировались задачи хорошо формализованные, при решении которых главное достоинство Пролога – логический вывод из системы аксиом – как бы затушевывалось вычислительной мощностью вечно молодого дедушки – Фортрана. Подавляющее большинство кодировщиков не имело никакого опыта в проектировании программных систем, и, фигурально выражаясь, их любимым занятием было изобретение наибыстрейших алгоритмов извлечения квадратного корня, которыми, как писал Дж. Мартин, "у меня заполнена вся корзина для ненужных бумаг" [3]. После распада Союза большинство организаций типа ПКБ АСУ прекратило свое существование; сильные в единстве коллективы конструкторов, постановщиков и кодировщиков распались. Наука потеряла в общественном сознании статус интеллектуального эталона, и в программистском сообществе стали задавать тон кодировщики, вооруженные философией наибыстрейшего извлечения квадратного корня. Пролог как язык концептульного программирования – незаменимое средство индивидуальной разработки программного продукта, но для этого нужно концептуально мыслить. Какой смысл я вкладываю в термин язык концептуального программирования? Прежде всего это средство решения при помощи компьютера широкого класса задач таким образом, чтобы максимально большая часть нейронов мозга была занята самой задачей и следствиями, которые могут быть получены в результате ее правильного решения, а не способом описания решения для компьютера. (В конце концов, это одна из причин возникновения научного направления «искусственный интеллект».) Пролог прост, поскольку использует небольшой набор базовых механизмов, включающих сопоставление c образом и "бэктрекинг" (автоматический возврат
7
8
верки % перейти на альтернативный вариант запроса write(X); % Иначе переформулируем вопрос большой(X), коричневый(X),!, write(X); !.
при поиске решения). Пролог заставляет Вас сконцентрироваться на осознании задачи и описании предметной области, а не на деталях программной реализации. Языки же типа Си представляют все возможности, чтобы забыть о цели и заставить думать о себе. Признаюсь, когда в 1992 г. я начал программировать на Turbo Prolog’е v.2.0., то писал во вполне "императивном" стиле. Но простота конструкций экономила массу времени. И только после полутора лет работы с Прологом я как-то вдруг осознал возможности решения плохо формализованных задач, задач распознавания образов, кластеризации и т. п., скрывающиеся за термином "бэктрекинг". По критерию минимума количества деталей реализации, которые нужно держать в голове при программировании "с листа", Пролог не знает себе равных. (Отмечу, правда, что в последнее время мне понравился Icon по той же причине. Но Visual Prolog v.5.2 существенно технологичнее.) Пролог – язык быстрого прототипирования. Это означает, в частности, что вы можете в течение какого-нибудь часа написать и отладить программу для экспериментальной проверки положений вашей концепции. Это означает, что вы можете подойти к решению задачи, как физик-экспериментатор: быстро разработать программный продукт для исследовательских целей, проанализировать экспериментально исследуемое явление, внести в модель поправки и перейти к следующей серии опытов. В теории экспертных систем это называется инкрементальным методом. "Поскольку для достижения высокого качества работы необходимо экспериментирование, то экспертная система развивается постепенно. Такой эволюционный или инкрементальный метод создания стал доминирующим в области экспертных систем" [4].
9
1. История Пролога С точки зрения математических оснований языка историю Пролога можно начать с 1930 г., когда Эрбран "предложил оригинальный метод доказательства теорем в формальных системах первого порядка" [5]. Идея заключается в том, что для того, чтобы доказать теорему H1 ∧ H2 ∧ … ∧ Hn ⊃ C, проще доказать противоречивость формулы F H1 ∧ H2 ∧ … ∧ Hn ∧ ¬ C. Доказательство базируется на теореме о резулюциях [5, с. 163]. В 1973 г. исследователи из Марсельского университета под руководством Алана Колмероэ (Colmerauer), опираясь на работы Джона Робинсона, посвященные методу резолюций, создали программу на Фортране для доказательства теорем. Программа получила название Пролог (Programmation en Logique). Существенный вклад в развитие теории логического программирования внесла работа Р. Ковальского "Логика предикатов как язык программирования". В 1976 г. Ковальский и М. ван Эмден предложили два подхода к прочтению текстов логических программ – процедурный и декларативный. В 1977 г. Д. Уоррен и Ф. Перейра создают в университете Эдинбурга интерпретатор/компилятор языка Пролог для ЭВМ DEC-10, тем самым переведя методы логического программирования в практичекую плоскость. В 1980 г. К. Кларк и Ф. Маккейб в Великобритании разработали версию Пролога для персональных ЭВМ. В основу методологии разработки программных средств японского проекта создания ЭВМ пятого поколения (1981 г.) было положено логическое программирование. Целью проекта декларировалось создание систем обработки информации, базирующихся на знаниях, а главным средством реализации должен был стать язык Пролог. В это же время появляется множество коммерческих реализаций Пролога практически для всех типов компьютеров. К наиболее известным можно отнести CProlog, Quintus Prolog,
10
Silogic Knowledge Workbench, Prolog-2, Arity Prolog, Prolog-86, Тurbo Prolog и др. [6]. Наиболее известна в России система программирования Turbo Prolog – коммерческая реализация языка для IBM-совместимых ПК. Ее первая версия разработана датской компанией Prolog Development Center (PDC) в содружестве с фирмой Borland International в 1986 г. Cамым существенным отступлением от неофициального стандарта было введение строгой типизации данных, что это позволило значительно ускорить трансляцию и выполнение программ. В 1996 г. Prolog Development Center выпускает на рынок систему Visual Prolog 4.0. В этой работе участвовали российские программисты под руководством Виктора Юхтенко, который позже стал техническим директором компании "Пролог-Софт", представляющей интересы PDC в России. В Visual Prolog входят: интерактивная среда визуальной разработки (VDE – Visual Develop Environment), которая включает текстовый и различные графические редакторы, инструментальные средства генерации кода, конструирующие управляющую логику (Experts), а также интерфейс визуального программирования VPI (Visual Programming Interface), Пролог-компилятор, набор различных подключаемых файлов и библиотек, редактор связей, файлы, содержащие примеры и помощь. Visual Prolog – многоплатформенная среда программирования, позволяющая разрабатывать приложения, работающие под управлением различных операционных систем – MS-DOS, PharLap-Extended DOS, всеми версиями Windows, 16- и 32-битовыми платформами OS/2, UNIX. Ресурсы и инструментальные средства (окна, меню, диалоги, органы управления, перья, кисти, курсоры мыши, графические курсоры, рисунки и т. п.), представляются в виде несложных Пролог-структур. В декабре 1997 г. фирма PDC выпустила Visual Prolog 5.0, с января 1999 г. приступила к распространению версии 5.1. В настоящее время все желающие могут бесплатно скопировать через Internet последнюю версию системы Visual Prolog 5.2 Personal Edition, функционирующую в средах Windows 3.1/95/98, NT, OS/2,
SCO UNIX и Linux. Ее загрузочный файл объемом 20 Мбайт можно найти по адресам: http://www.visual-prolog.com/vip/vipinfo/freeware_version.htm, http://www.pdc.dk/vip/vipinfo/freeware_version.htm1. В 2003 г. издательство "БХВ-Петербург" тиражом 3000 экз. издало книгу "Логическое программирование и Visual Prolog" объемом 990 стр. [8]. Она содержит CD с Personal Version Visual Prolog v. 5.2. Вариант Personal Edition предназначен для некоммерческого использования, и сообщения об этом постоянно имеются во всех приложениях, созданных с его помощью. Все продукты PDC, включая Visual Prolog, – это системы, порождающие исполняемый код (EXE или DLL), что еще раз подтверждает высокую эффективность Пролога.
11
12
1
Судя по последним данным, PDC Prolog v.5.2. Rersonal Edition более официально свободно не распространяется. Думаю, ее можно найти на других сайтах Интернета.
2. Синтаксис и семантика Пролог-программ 2.1. Объекты данных2 Объекты данных в Прологе могут быть простыми данными и структурами. Простые данные могут быть константами и переменными. Константы могут быть атомами, числами и строками. Пролог-система распознает тип объекта по его синтаксической форме в тексте программы. Атомы Атом – комбинация букв, цифр и знака подчеркивания, начинающаяся со строчной буквы. Примеры: a, "это_атом", "this_is_atom". Переменные Переменная – комбинация букв, цифр и знака подчеркивания, начинающаяся с прописной буквы. Примеры: V, Это_переменная25. Структуры Структурные объекты (или просто структуры) – это объекты, состоящие из нескольких компонент. Компоненты, в свою очередь, могут быть структурами. Для объединения компонент в структуру используется функтор: date(17,июнь,1999) % date – функтор. date(День,июнь,1999), здесь – День – переменная, которая может получить значение (стать связанной переменной) на ком-то этапе вычислений. Синтаксически все объекты данных в Прологе есть термы. Сопоставление. Наиболее важная операция над термами – сопоставление. Два терма сопоставимы: – если они идентичны,
2
Излагается по [2, 8]
13
– если переменным в обоих термах можно присвоить в качестве значений объекты таким образом, что после подстановки они станут идентичными. Например, date(Day,июнь,1999) и date(Day1,июнь,1999) сопоставимы, поскольку переменным Day и Day1 можно присвоить одинаковые значения от 1 до 31. Сопоставление – процесс проверки сопоставимости термов. 2.2. Декларативный смысл Пролог-программ Дано предложение: P:-Q,R. Q и R имеют синтаксис термов. Возможные способы декларативной интерпретации этого предложения: P истинно, если Q и R истинны. Из Q и R следует P. Два варианта процедурного прочтения: Чтобы решить задачу P нужно сначала решить подзадачу Q, а затем – подзадачу R. Чтобы достичь P, сначала достигни Q, затем достигни R. Таким образом, различие между декларативным и процедурным прочтениями заключается в том, что последнее не только определяет логические связи между левой и правой (цели) частями предложения, но еще и порядок, в котором эти цели обрабатываются. Декларативный смысл программы определяет, является ли данная цель истинной, и, если да, то при каких значениях переменных это достигается. Конкретизацией предложения называется результат подстановки в него на место каждой переменной некоторого терма. Вариантом предложения C называется такая конкретизация C, при которой каждая переменная заменена на другую переменную. Например: читатель(X):- иметь_книгу(X,Y) 14
Два варианта: читатель(X1):- иметь_книгу(X1,Y2) читатель(Beta):- иметь_книгу(Beta,Alpha) Конкретизации: читатель(Колмогоров):- иметь_книгу(Колмогоров,Z) читатель(Васильев):- иметь_книгу(Васильев, Овод) В общем случае, вопрос к Пролог-системе есть список целей, разделенных запятыми. Список целей будет истиннным, если все цели в списке истинны при одинаковых конкретизациях переменных. Запятая между целями обозначает конъюнкцию целей. В Прологе возможна и дизъюнкция целей: должна быть истинной, по крайней мере, одна из целей. Дизъюнкция обозначается точкой с запятой (;): P:-Q;R. %P истинно, если истинно Q или P. То же самое можно написать в виде двух правил Пролога: P:-Q. P:-R. Запятая связывает цели сильнее (имеет более высокий приоритет), чем точка с запятой. Предложение P:-Q,R;S,T,U. понимается как P:-(Q,R);(S,T,U). Процедурная семантика определяет, как Пролог-система отвечает на вопросы. Ответить на вопрос – это значит удовлетворить список целей. Процедурная семантика Пролога – процедура вычисления списка целей. 2.3. Основные определения
• Примеры: синий(шар), красный(платок,флаг,яблоко), любит(Cаша,Некто). • Предикат – символическое имя отношения, за которым следуют аргументы в скобках (через запятую) • Факт – отношение, в котором все объекты известны; факты всегда истинны. Факты можно рассматривать как аксиомы. • Предложение – запись на Прологе отдельных отношений. • Правило – предложение с логической связкой если (if,:-). Пример: предложение естественного языка "Гена пойдет на пляж, если день будет солнечным" на Прологе может быть записано так: ходить(Гена,пляж):-день(солнечный) ходить(Гена,пляж) if день(солнечный) Левая часть правила называется заголовком, правая – телом. • Процедура – последовательность предложений, описывающих предикат. Переменные позволяют формулировать отношения и правила общего вида и, таким образом, формулировать вопросы. Переменные должны получить значения в результате операций сопоставления и конкретизации. До этого переменная называется свободной, после – связанной. Имя переменной должно начинаться с прописной буквы или знака подчеркивания (_). Далее может следовать любое число букв (в любом регистре), цифр или знаков подчеркивания. Анонимная переменная обозначается знаком подчеркивания и используется вместо любой другой, когда ее значение не интересует программиста. • Цель – более общее наименование запроса. Пролог пытается разрешить цель, просматривая все факты. Разрешение цели эквивалентно доказательству теоремы на основе аксиом – фактов.
• Пролог – «декларативный язык, программы на котором содержат объявления логических взаимосвязей, необходимых для решения задачи» [6]. • Отношение между объектами задается в форме предиката: "имя_отношения(<имена_объектов>)". 15
16
6. После того как вы написали текст программы, откомпилируйте ваш основной файл ("<имя_проекта>.pro"). Для этого воспользуйтесь либо Ctrl-F9, либо соответствующей позицией в меню Projec. Если есть ошибки, появится соответствующее окно с сообщениями. Установите курсор на сообщение и нажмите Enter (либо двойное нажатие левой клавишей мышки), и вы окажетесь в исходном модуле в позиции ошибки. 7. Устранив ошибки, выберите позицию Rebuild All или нажмите сочетание клавиш Ctrl-Alt-F9 для получения исполняемого файла.
3. Практическое программирование на Прологе Лучший известный мне учебник по программированию на Turbo Prologe, переведенный на русский язык, – это уже цитированная книга "Использование Турбо-Пролога" [7]. В ней есть все, за исключением использования системы управления внешней "бинарной" БД. Наиболее полное руководство на русском языке по логическому программированию и Visual Prolog'у вышло в 2003 г. [8]. Исходные модули, написанные на Turbo Prolog’е, могут быть включены и в состав приложений Visual Prolog’а. Полный комплект документации на английском языке можно получить в составе Visual Prolog v. 5.2 Personal Edition. Она содержит также удобную и полную Help-систему. Изучение версии 5.2. визуального пролога рекомендую начать с написания программ, работающих в режиме (точнее, в пользовательской стратегии) EASYWIN, – вы будете иметь простой, но вполне достаточный для начала интерфейс с вашими программами. Для этого стартуйте систему: 1. В общем меню выбираете Projec. Затем New Project. Появляется меню Эксперта приложения (Application Axpert). В этом меню в подменю GENERAL (оно уже выбрано) печатаете наименование проекта и имя файла-проекта (VPRфайла). Печатаете или выбираете директорию проекта. 2. Выбираете подменю TARGET. В позиции UI Strategy заменяете VPI на EASYWIN. 3. Нажимаете кнопку Create. Создаются все необходимые файлы. В настоящий момент вас интересуют только два из них – файлы с расширениями .pro и pre. Последний содержит секции GLOBAL DOMAINS и GLOBAL DATABASE. 4. Напишите в этих секциях необходимые определения, не убирая уже имеющийся текст. Файл с расширением .pro содержит секции predicates, goal, clauses. 5. Пишите необходимый код. Можно редактировать вообще вне системы. Для вызова системы установите курсор на файл с раширением .vpr и нажмите Enter. 17
В следующем разделе приведены самые необходимые сведения и примеры, для того чтобы понять специфику Пролога и начать писать программы. Тема работы с внешней ("бинарной") базой данных Пролога не затрагивается. 3.1. Структура Пролог-программы В общем случае программа на Прологе состоит из следующих секций (или разделов): CONSTANTS /* раздел определения констант */ const1 = definition const2 = definition %Пример: str_main = "Это строка" [GLOBAL] DOMAINS /*раздел определения структур данных*/ dom[,dom] = [reference]declaration1;declaration2 Примеры: listdom = dom* /*определение списка целых чисел*/ dom, nb_jbject = integer compaund_dom = cmpd(dom,string,symbol,name) name = string file = inputfile;outputfile 18
[GLOBAL]DATABASE[-
]/*раздел определения данных, хранящихся в оперативной памяти*/ [determ] pred1(....) pred2(.....) %Пример: term(integer,string,real,name) GLOBAL PREDICATES /* раздел объявления глобальных "процедур"*/ [determ|nondeterm] pred1(.........) -(i,i,o,..)(i,o,i,..)[language c|pascal|fortran] [ as "name" ] pred2(........) %Пример: main_calc(integer,real,real,string) – (i,i,i,o) my_predict make_NewString(string,string,string) – (i,i,o) PREDICATES /* раздел объявления локальных "процедур"*/ [determ|nondeterm] pred1(.........) pred2(........) %Пример: calc2(integer,real,real,string) nondeterm calc3(integer,real,real,string) Goal /*аналог процедуры main в языке C*. Вся программа может состоять только из раздела Goal / %Пример: Goal InpStr = "Отредактировать эту строку", edit(InpStr,OutStr), file_str("primer.txt",InpStr2), concat(OutStr,InpStr2,S3), edit(S3,_). CLAUSES /*раздел правил или определения "процедур"*/ p(....):-p1(...), p2(.....), ... . 19
%Пример1: Только конъюнкция edit_3(InpStr1,InpStr2,OutStr):concat(InpStr1,InpStr2,InpStr), edit(InpStr,OutStr). %Пример2: Конъюнкция и дизъюнкция edit_3(InpStr1,InpStr2,OutStr):InpStr2<>"Не присоединять",!, concat(InpStr1,InpStr2,InpStr), edit(InpStr,OutStr); !,edit(InpStr1,OutStr); include "filename" % включение файла во время компиляции Пример: include "modul1.pro" Отметим, что Turbo Prolog располагает достаточной для решения большинства задач библиотекой математических функций. 3.2. Свободные и связанные переменные Вызывая некоторый предикат с N переменными, части из них вы можете задать значения, другим – нет. Первые – это параметры, или связанные переменные, последние – свободные переменные, которые в процессе вычисления должны получить значения. Пример: .. деление(17,Rezult), .. деление(D,Rezult):-Rezult = (27-10)/D. Или: .. delenie_plus(17,Rezult), .. delenie_plus(D,Rezult):P1=27-10, 20
delenie2(P1,D,Rezult). delenie2(P1,D,Rezult):-Rezult = P1/D. Когда какие-то значения вас не интересуют, вместо них следует ставить знак подчеркивания (указание анонимной переменной): database – b1 некий_факт(string,integer,symbol,integer) clauses .., некий_факт(A,_,_,_), write(A), .. 3.3. Внутренняя БД Пролога Используя аналогию с языком C, внутреннюю БД Пролога (раздел facts, устаревшее имя раздела – database) можно рассматривать как множество массивов структур. Например, анализируя построчно входной текст, информацию о строках вы можете хранить в структурах типа: domains .. number_str,type_str, length_str = integer .. database – ab_strings .. input_string(number_str,type_str,length_str) .. Для размещения фактов используются встроенные предикаты assert, asserta, assertz (assert эквивалентно assertz). Извлекается факт по его имени (функтору). Удаляются факты при помощи встроеннных предикатов retract или retractall. Рассмотрим подробнее процессы размещения и извлечения фактов. Asserta всякий новый факт помещает в начало однименных фактов, assertz – в конец, т. е. для работы с множеством фактов как со стеком фактов следует использовать asserta, а для рабо21
ты с очередью фактов – assertz. Например, если во входном файле было 1000 строк и факты размещались при помощи assertz(input_string(NbS,TS,LS)), то используя рекурсивную процедуру get_all_DefStrings:input_string(NbS,TS,LS),!, retractall(inp_strings(NbS,_,_)), write(NbS,’,’), get_all_DefStrings,!; !. или же более корректный с точки зрения программирования на Прологе вариант, в котором используется бэктрекинг (да и факты не приходится удалять): get_all_DefStrings:input_string(NbS,TS,LS), write(NbS,’,’),fail. get_all_DefStrings. Вы получите на выходе последовательность 1,2,3,..,1000. Если использовался при загрузке предикат asserta(input_string(NbS,TS,LS)), то те же процедуры выдатут: 1000,999,998,..,1.
чисел
Если факты были загружены в БД в произвольном порядке, а нужно извлечь их в определенной последовательности, то для индексированного массива, каким является input_string, можно поступить так: get_all_DefStrings(I):input_string(I,TS,LS),!, write(I,’,’TS,’,’,LS),nl, Inew = I+1, get_all_DefStrings(Inew),!;!. Встроенный предикат save сохраняет БД во внешнем файле (не путать с внешней БД!). save(DosFileName) (string) – (i) 22
save(DosFileName,InternalDatabaseName) (string,DatabaseName) – (i,i) Встроенный предикат consult загружает БД, сохраненную предикатом save, из файла в память. consult(DosFileName) (string) – (i) consult(DosFileName,InternalDatabaseName) (string,InternalDatabaseName) – (i,i) Примеры: save("stringDB.dba",ab_strings) consult("stringDB.dba",ab_strings) Только одна БД в программе может быть неименованной. Все остальные должны иметь имя. Вы можете сформировать факты БД в программе, написанной на любом другом языке, и записать их в файл или сформировать "вручную" при помощи текстового редактора, затем загрузить в память в программе на Прологе при помощи consult. 3.4. Обработка условий и организация циклов в Прологе Два встроенных предиката, очень полезных для обработки условий и организации циклов: 1. Предикат fail искусственно порождает неуспех. 2. Предикат cut (или !) предотвращает бэктрекинг: p:-p1,p2,!,p3,.. – если достигнуты цели p1 и p2, бэктрениг не осуществляется. 3.4.1. Обработка условия
Пример: p(A,C,Dplus):-A>=C,!,Dplus=A-C;Dplus=C-A. Или: p(A,C,Dplus):-A>=C,!,Dplus=A-C. p(A,C,Dplus):-Dplus=C-A. Конечно, наиболее простое решение: p(A,C,Dplus):-Z:=A-C, Dplus=abs(Z), где abs – встроенная функция. Если в нашем примере со строками требуется получить все номера строк с длиной не более 45, тогда процедура, решающая эту задачу, будет такой: get_all_DefStrings:input_string(NbS,TS,LS), LS< = 45, write(NbS,’,’), fail. get_all_DefStrings. % или get_all_DefStrings:-!. 3.4.2. Использование предиката типа repeat Пусть требуется в рамках одного правила предиката pravilo выполнить некоторое множество заведомо успешных предикатов, после чего выполнять некоторое другое множество предикатов, до тех пор, пока справедливо некоторое условие. Первую и вторую группы предикатов можно, очевидно, обозначить одним предикатом, p1 и p2 соответственно. Пусть p_control – предикат, проверяющий условие, а предикат repeat (который может, очевидно, иметь любое другое имя) записывается в виде следующих двух правил: repeat. repeat:-repeat. Тогда: pravilo:-p1,repeat,p2,p_control.
Пусть a – предикат, который может быть либо успешным, либо нет. В случае успеха мы хотим выполнить предикат u, в обратном случае – предикат f. p:-a,!,u;f. Можно и так (в случае неуспеха выполняется второе правило для p): p:-a,!,u. p:-f.
Предикат p1 выполнится один раз, предикат же p2 будет выполняться до тех пор, пока p_control неуспешен.
23
24
Разберемся, как это происходит: p1 всегда успешен, затем выполняется всегда успешное первое правило предиката repeat и Пролог устанавливает указатель отката на второе правило. Выполняется p2. После неуспеха p_control выполняется второе правило repeat:-repeat, после чего первое правило, указатель отката устанавливается на второе правило, далее p2, p_control и т. д. Приведем простой пример использования repeat. Требуется загрузить факты БД со значениями, вводимыми с клавиатуры. Предикат check_cont запрашивает пользователя о разрешении ввода группы значений факта fact, предикат vvod принимает значения. database fact(string,string,string) predicates repeat check_cont vvod goal vvod,exit. clauses repeat. repeat:-repeat. vvod:retractall(fact(_,_,_)), write("Начинаем процесс ввода значений"),nl, repeat, clearwindow, write("A?"),readln(A),nl, write("B?"),readln(B),nl, write("C?"),readln(C),nl, assert(fact(A,B,C)), check_cont. check_cont:write("ВВОДИТЬ ДАЛЕЕ? (Y|N)"), readchar(Ans),Ans='N',!, write("Процесс завершен"),readchar(_). 25
3.5. Списки в Прологе 3.5.1. Примеры списков domains list_integer=integer* list_struct=el2* el=e(list_integer) el2=l(integer,symbol) predicates p1(list_integer) p2(list_struct) goal L1=[1,2,3,4] %Списки списков L2=[e([10,40,50]),e([30,20])] .................................... %Списки структур L3=[l(1,"Fortran"),l(2,"Algol"),l(3,"PL/1")], write("Языки программирования"),nl, p2(L3), search(3,L1), .................................... 3.5.2. Разделение списков на "голову" и "хвост" Основным приемом работы со списками является представление списков в виде "Головы" (Head) и "Хвоста" (Tail). Для иллюстрации напишем правило для предиката p2 из предыдущего раздела: clauses p2([]). p2([l(I,S)|T]):write(I," ",S),nl, p2(T). Поиск элемента в списке: search(H,[H,_]). search(H,[_,T]):-search(H,T). 26
Получить сумму числовых элементов списка можно очевидным способом: sumList([],S). sumList([H|T],S):-S1=S+H,sumList(T,S1). А для иллюстрации работы со стеком применим "неочевидный" прием: predicates sumlist(integer*,integer) goal L = [1,2,3,4], sumlist(L,S), write(S) . clauses sumlist([],0). sumlist([H|T],X):-sumlist(T,S),X = S+H. До тех пор пока не удовлетворено первое правило, Пролог будет очищать список, сбрасывая "головы" в стек. Затем он присвоит 0 свободной переменной, а далее будет суммировать элементы стека, присваивая значения промежуточной суммы переменной X, и возвращать элементы стека в список. (По моему мнению, если уж вы выбрали Пролог, не стоит жертвовать логической ясностью ради "оптимизации".) Встроенный предикат findall findall собирает компоненты факта в список. domains фам_им_от = ф(symbol,symbol,symbol) лист_фам_им_от = фам_им_от* facts – f1 гриб(symbol) язык_программирования(integer,symbol) фио(фам_им_от)
27
predicates собрать_фио(лист_фам_им_от) ................ goal consult(famio.txt,f1) %файл "famio.txt" содержит: %фио("Фадеев","Фиктор","Петрович") %фио("Иванов","Иван","Иванович") ............... %фио("Гимазов","Артур","Олегович") findall(Гриб,гриб(Гриб),Грибы), findall(Имя_Языка,язык_программирования(_,Имя_Языка),С писок), собрать_фио(СписокФИО). clauses собрать_фио(Список):-findall(ФИО,фио(ФИО),Список). % Список будет состоять из [ф("Фадеев","Фиктор","Петрович"),ф("Иванов","Иван","Ива нович"),...] 3.5.3. Некоторые полезные программы для работы со списками • Слияние списков Полагаем, что в базе данных facts содержаться два списка (список1, список2), элементами которых являются целые числа. Требуется список1 присоединить к списку2. Пусть список1 есть [5,6,7], а список2 есть [8,9]. domains список = integer* facts – f1 список1(список) список2(список) predicates объединить_списки(список,список,список) 28
goal список1(Список1), список2(Список2),!, % А вдруг БД пуста?! объединить_списки(Список1,Список2,Список3);!. clauses объединить_списки([],L,L). объединить_списки([H|L1],L2,[H|L3]):объединить_списки(L1,L2,L3). Что будет происходить? Поскольку вначале первый список не пуст, Пролог будет пытаться удовлетворить второе правило, очищая первый список. Элементы первого списка пересылаются в стек в оперативной памяти. Когда первый список окажется пустым, становится возможным третьему списку присвоить второй список, и первое правило окажется истинным: объединить_списки([],[8,9],[8,9]). Пролог берется за второе правило, сворачивая рекурсию. Начиная с вершины стека, он присваивает элементы "головам" первого и третьего списков. При этом на каждом шаге левая часть второго правила истинна, происходит рекурсивный вызов и так до тех пор, пока стек не опустеет. • Сортировка списков goal sortL([5,4,7,6,11,9],LS) clauses sortL([],[]). sortL([X|T],Sorted_list):sortL(T,Sorted_tail), insert(X,Sorted_tail,Sorted_list). insert(X,[Y|Sorted_list],[Y|Sorted_list1]):ask_order(X,Y),!, insert(X,Sorted_list,Sorted_list1). insert(X,Sorted_list,[X|Sorted_list]). ask_order(X,Y):-X>Y.
29
3.6. Ввод и вывод PDC Visual prolog обладает гибкой системой ввода-вывода и манипулирования файлами. 3.6.1. Файловая система Доступ к файлу может осуществляться в двух "модах" – бинарной и текстовой. Для определения вида доступа используется специальный предикат filemode(SymbolicFileName,Mode). Параметр Mode принимает одно из двух значений: 0 – Binary Mode, 1 – Text Mode. Дальнейшее изложение имеет отношение только к работе с файлами в текстовой "моде". Для того, чтобы работать с файлом на внешнем носителе, его нужно открыть или создать. Открыть файл можно для чтения, записи, модификации. Прежде чем это сделать, в файле <имя_проекта>.inc в разделе global domains следует задать символические имена файлов, разделяя их точкой с запятой. (В том месте, где написано %To be edited.). Например, уже написано: global domains DB_SELECTOR = browselist_db % For treebrowser tool FILE = fileselector1; fileselector2 % To be edited Вы должны добавить Ваши имена: global domains DB_SELECTOR = browselist_db % For treebrowser tool FILE = fileselector1; fileselector2; filein; filein2; fileout % To be edited Открыть можно практически неограниченное количество файлов, столько, сколько позволяют установки операционной системы (но стоит ли это делать?). Для перехода от одного открытого файла к другому (перенаправление потоков ввода-вывода) служат предикаты readdevice и writedevice. Например: .................... openread(filein,"text.txt") openread(filein2,"text2.txt") openwrite(fileout,"forwrite.txt") 30
readdevice(filein), readln(Str1), write(Str1) .................... readdevice(filein2), readln(Str), write(Str), ................. closefile(filein), closefile(filein2), closefile(fileout), ................. Следует помнить, что при открытии файла предикатом openwrite(SimbolicFileName,OSFileName) существующий файл очищается, несуществующий – создается. Для дозаписи существующий файл открывается предикатом openappend(SimbolicFileName,OSFileName). Открыть файл для чтения и записи можно предикатом openmodify(SimbolicFileName,OSFileName). Когда вы работаете с файлом в режиме чтения – записи, следует после каждой записи использовать предикат flush(SimbolicFileName), который вызывает принудительную очистку буфера. Он полезен также во время отладки программы, когда вы пишите некоторую информацию для трассировки. (Flush существенно замедляет выполнение программы.) Для реализации нелинейного ("гипертекстового") доступа к файлу используется предикат filepos(SymbolicFileName,FilePosition,Mode), перемещающий (шаблон (i,i,i)) и берущий (i,o,i) текущую позицию в файле. Параметр Mode определяет "точку отсчета" позиции: 0 – от начала файла, 1 – относительно текущей позиции, 2 – относительно конца файла. 31
Предикат eof(SymbolicFileName) предназначен для контроля конца файла. domains nondeterm repeat читать_и_обработать_строки обработать_строку(symbol) .................... clauses repeat. repeat:-repeat. читать_и_обработать_строки:repeat, readln(f,S), обработать_строку(S), eof(f),!,closefile(f);!. ...................... Файлы можно копировать, переименовывать, удалять, искать. copyfile(FromName, ToName) renamefile(OldOSFileName, NewOSFileName) deletefile(OSFileName) searchfile(SearchPath, FileName, FoundName) existfile(OSFileName) 3.6.2. Операции с именами файлов Для работы с именами файлов используются предикаты: filenameext(FullName,Name,Mask)-(i,o,o),(o,i,i) filenamepath(FullName,Path,Name)- (i,o,o),(o,i,i) Примеры: filenameext с шаблоном (i,o,o): filenameext("myprog.vpr",Name,Ext), write("Name=",Name, "Ext=",Ext),nl, Выход: Name=myprog Ext=.vpr
32
filenameext с шаблоном (o,i,i): filenameext(FullName,"prolog",".err"), write(FullName),nl, filenameext(FullName1,"prolog.err",".exe"), write(FullName1),nl. Выход: prolog.err prolog.exe filenamepath с шаблоном (i,o,o) filenamepath("C:\\mycatalog\\myfile.txt",Path,Name), write("Path=",Path, "Name=",Name),nl, Выход: Path=C:\mycatalog\ Name=myfile.txt
Универсальный оператор записи – write. Пример: write("Это значения переменных. V=",V,",C=",C),nl, Переменные могут иметь любой тип. Предикат nl служит для перевода строки. 3.7. Строки и функции работы со строками Строка – любая последовательность символов, заключенная в кавычки. Предикат concat – объединение строк. Шаблоны (patterns) (i, i, o), (o, i, i), (i, o, i), (i, i, i). Примеры с разными шаблонами. % Шаблон (i, i, o) Строка1="Это строка ", Строка2="И это строка", concat(Строка1,Строка2,ИтоговаяСтрока). write(ИтоговаяСтрока), %Выход: Это строка И это строка
filenamepath с шаблоном (o,i,i) filenamepath(FullName,"C:\\mycatalog\\","anfile.txt"), write(FullName),nl, Выход: C:\mycatalog\anfile.txt
% Шаблон (o, i, i) concat(X,"И это строка","Это строка И это строка") write(X) %Выход: Это строка
3.6.3. Чтение и запись Основные предикаты для чтения: file_str(OSFileName,StringVariable) – читает файл целиком. readchar(CharVariable) – читает один символ с устройства ввода (файл или клавиатура). readint(IntegerVariable) – читает целое число в пределах (от -2147483648 до >2147483647 для 32 bit платформы). Ошибка возникает, если ввод не может быть преобразован в целое. readln(StringVariable) – читает строку. readreal(RealVariable) – читает реальное число. Примеры правильного задания: 127 -127.457E-5 0.72 .99 33
% Шаблон (i, o, i) concat("Это строка",X,"Это строка И это строка") %Выход: И это строка % Шаблон (i, i, i) concat("Это строка"," И это строка","Это строка И это строка") % Нет выхода. Утверждение истинно. concat("Это строка"," А это строка не строка","Это строка И это строка") % Утверждение ложно. "А это строка не строка" не является % подстрокой "Это строка И это строка" 34
Предикат frontchar frontchar (String, StartChar, EndString) Шаблоны (i, o, o), (i, i, o), (i, o, i), (i, i, i), (o, i, i) Примеры: %Шаблон (i, o, o) frontchar("Я Вас люблю!",Fc,ES), write(Fc,"##",Es), %Выход: Я## Вас люблю! %Шаблон (i, i, o) S="Я Вас люблю!", frontchar(S,'О',ES), %Предикат не успешен. %Шаблон (i, o, i) S="Ненавижу", frontchar(S,X,"енавижу"), write(X), %Выход: Н. %Шаблон (i, i, i) S="У-р-р-я-я-я!" frontchar(S,'У',"-р-р-я-я-я!"), %Предикат успешен. %Шаблон (o, i, i) -добавление символа в начало строки frontchar(S,'Н',"енавижу"), write(S), %Выход: Ненавижу.
St="МАМА", frontstr(5,St,StartS,EndS), Предикат не успешен. Предикат fronttoken token – это правильное (integer|real), символ (но не пробел).
"имя",
беззнаковое
Можно проверить, является ли ваша строка правильным именем, используя встроенный предикат isname. Например: isname("75Слонов") – No (не имя), isname("Windows_95") – Yes, isname("Windows-95") – No. Ниже приводится исходный текст полной программы на Visual Prolog'е /********************************************** Copyright (c) My Company Project: TOKEN FileName: TOKEN.PRO Purpose: No description Written by: Visual Prolog Comments: ************************************************/ include "token.inc" predicates token() clauses
Предикат frontstr – выбор лидирующей подстроки %шаблон – (i,i,o,o) frontstr(5,"ААААААА",StartS,EndS), write(SrartS,"###",EndS), Выход: ААААА###AA.
35
число
token():fronttoken("all kids do fine",TOK,REST), write("TOK = ",TOK," REST = ",REST),nl, fronttoken("all+kids do fine",TOK1,REST1), write("TOK = ",TOK1," REST = ",REST1),nl, 36
fronttoken("22all kids do fine",TOK2,REST2), write("TOK = ",TOK2," REST = ",REST2),nl, fronttoken("22.66all kids do fine",TOK3,REST3), write("TOK = ",TOK3," REST = ",REST3),nl, fronttoken("-22.66all kids do fine",TOK4,REST4), write("TOK = ",TOK4," REST = ",REST4),nl, fronttoken(".66all kids do fine",TOK5,REST5), write("TOK = ",TOK5," REST = ",REST5),nl, fronttoken("Иди ко мне!",TOK7,REST7), write("Исходная строка >>> ","Иди ко мне!"),nl, write("TOK = ",TOK7," REST = ",REST7). goal token(). % Выход: TOK = all REST = kids do fine TOK = all REST = +kids do fine TOK = 22 REST = all kids do fine TOK = 22.66 REST = all kids do fine TOK = – REST = 22.66all kids do fine TOK = . REST = 66all kids do fine Исходная строка >>> Иди ко мне! TOK = Иди REST = ко мне! Последнее использование fronttoken демонстрирует, что вы можете использовать этот предикат для парсирования текстов на русском языке, что не позволял TurboProlog v.2.0. Давайте, мы это и сделаем. domains слово=symbol часть_речи=symbol facts -f1 лексема(слово,часть_речи) знак(symbol,symbol) predicates парсировать_предложение(symbol) 37
определить_нечто(symbol) goal assert(лексема("я","местоимение")), assert(лексема("бы","частица")), assert(лексема("на","предлог")), assert(лексема("но","союз")), assert(лексема("выходить","глагол")), assert(лексема("вышел","глагол")), assert(лексема("идет","глагол")), assert(лексема("улица","существительное")), assert(лексема("улицу","существительное")), assert(лексема("дождь","существительное")), assert(знак(",","запятая")), assert(знак(".","точка")), Предл="Я бы вышел на улицу, но идет сильный дождь.", парсировать_предложение(Предл). clauses парсировать_предложение(Предл):fronttoken(Предл,Нечто,Остаток),!, upper_lower(Нечто,Нечто1), % преобразование регистра определить_нечто(Нечто1), парсировать_предложение(Остаток);!. определить_нечто(X):лексема(X,Часть_речи),!, write("Слово = ",X," Часть_речи = ",Часть_речи),nl; знак(X,Наименование),!, write("Знак препинания = ",X," Наименование ",Наименование),nl; write("Элемент ",X," не определен"),nl. Выход: Слово = я Часть_речи = местоимение Слово = бы Часть_речи = частица Слово = вышел Часть_речи = глагол Слово = на Часть_речи = предлог Слово = улицу Часть_речи = существительное Знак препинания = , Наименование = запятая Слово = но Часть_речи = союз 38
=
Слово = идет Часть_речи = глагол Элемент сильный не определен Слово = дождь Часть_речи = существительное Знак препинания = . Наименование = точка Для поиска подстрок и отдельных символов используются предикаты searchstring(SourceStr,SearchStr,Position) и seachchar(SourceString,Char,FoundPos) соответственно. Они возвращают позиции начала подстроки и символа. Для выбора подстроки используется предикат substring(STRING,Pos,Len,SubStr), для выбора символа – предикат subchar(String,Position,RetChar). Длина строки определяется предикатом str_len.
39
4. Простенькая экспертная система Задача этого раздела заключается в том, чтобы проиллюстрировать использование Пролога для создания игрушечной экспертной системы (ЭС). Игрушечная ЭС «Кто чем увлекается?» Мы хотим создать систему, которая отвечала бы на вопросы, сформулированные на русском языке, на тему увлечений (hobby) действующих лиц. Начнем с простейшего варианта. В простейшем варианте нам следует создать элементарную базу фактов типа увлечение (Кто,Что). Все вербальные варианты запросов система проинтерпретирует так: 1) если в тексте вопроса присутствует значение "Кто" (Петров, Сидоров, ...), следует выдать все значения "Что"; 2) если в тексте вопроса присутствует значение "Что", следует выдать все значения "Кто"; 3) если в тексте запроса присутствуют "Что" и "Кто", то система интерпретирует запрос, как "Увлекается ли Кто Что?". Ответ: "Да" или "Нет" в зависимости от содержания элементарной базы знаний. В таком простейшем варианте ЭС (с единственным видом отношения между субъектом и объектом) можно не утруждать пользователя формулированием запроса в полном виде, играя в понимание, а предоставить ему возможность выбрать тип запроса и заполнить соответствующие поля. Алгоритм обработки запросов очень прост. В самом сложном случае, когда их типы заранее не определены (через меню выбора типа), каждое слово запроса проверяется на принадлежность типам "Кто" или "Что", и, в зависимости от результата, формулируется ответ. "Закодируем" алгоритм обработки строки-запроса Запрос, полагая, что база знаний содержится в файле "hobbyNew.dbs". Программа завершает работу, если в ответ на ее вопрос write("Есть вопросы? (Д|Н|д|н)") пользователь ответит 'Н' или 'н'. 40
Предикат repeat используется в разделе goal для организации цикла по обработке вопросов. domains кто=symbol что=symbol facts – f1 увлечение(кто,что) кто(кто) что(что) predicates nondeterm repeat nondeterm ответить(symbol) ответить_что(кто) ответить_кто(что) анализ_КтоЧто(symbol) спросить goal consult("hobbyNew.dbs",f1), repeat, спросить, retractall(кто(_)), retractall(что(_)), write("Есть вопросы? (Д|Н)"), readchar(ДаНет), ДаНет='Н',exit(). clauses repeat. repeat:-repeat. ответить(""):кто(Кто), что(Что), увлечение(Кто,Что),!, write("Да"); кто(Кто), что(Что), not(увлечение(Кто,Что)),!, 41
write("Нет"); кто(Кто), not(что(_)),!, write(Кто,".Хобби:"),nl, ответить_что(Кто); что(Что), not(кто(_)),!, write(Что," является увлечением для:"),nl, ответить_кто(Что); !,write("Не понял"),nl. ответить(Запрос):fronttoken(Запрос,Лексема,Остаток),!, анализ_КтоЧто(Лексема), ответить(Остаток). анализ_КтоЧто(Лексема):увлечение(Лексема,_),!, assert(кто(Лексема)); увлечение(_,Лексема),!, assert(что(Лексема)); !. ответить_кто(Что):увлечение(Кто,Что), write(Кто),nl, fail. ответить_кто(_). ответить_что(Кто):увлечение(Кто,Что), write(Что),nl, fail. ответить_что(_). спросить:write("Введите Ваш вопрос:"),nl, readln(Вопрос), ответить(Вопрос),!; !. 42
Теперь усложним задачу с целью дать возможность пользователю формулировать вопрос грамматически правильно, а также для того, чтобы вводить любые виды отношений. Факты мы приведем к универсальному виду f(объект1,отношение,объект2), а также введем синонимы для имен объектов и отношений. В данном случае под термином синоним будем понимать как грамматическое видоизменение слова, так и другое слово, которое мы считаем семантически эквивалентным исходному. При данной организации БЗ и приведенном ниже алгоритме обработки запроса имена объектов и отношений, множества синонимов различных отношений и множество синонимов различных объектов не должны пересекаться. Например, если есть факты ф("кирилл","хобби","шахматы")}, ф("кирилл","любить","татьяна")}, соб("татьяна",["татьяну",...]) сот("хобби",["нравится","увлекается","любит","любить"]) сот("любить",["любит"]), то на вопрос: "кирилл любит татьяну" вы получите ответ "Нет!", поскольку в качестве имени отношения будет выбрано "хобби". Состав базы знаний. ф("кирилл","хобби","хоккей") ф("петров","хобби","лыжи") ф("ирина","хобби","кино") ф("татьяна","хобби","гимнастика") ф("кирилл","хобби","гимнастика") ф("петров","любить","ирина") ф("ирина","любить","кирилл") ф("кирилл","любить","татьяна") соб("кирилл",["кириллу","кириллом","кирилла","кирилле"]) соб("петров",["петрову","петровым","петрова","петрове"]) соб("ирина",["ирине","ириной","ирины","ирину"]) соб("гимнастика",["гимнастикой","гимнастики","гимнастикой", "гимнастике","гимнастику"]) соб("татьяна",["татьяне","татьяной","татьяны","татьяну"]) сот("хобби",["нравится","увлекается"]) сот("любить",["любит"]) 43
Текст программы. domains список=symbol* facts – f1 ф(symbol,symbol,symbol) соб(symbol,список) сот(symbol,список) кто(symbol) что(symbol) отн(symbol) временно(symbol) predicates nondeterm repeat nondeterm ответить(symbol) ответ1(symbol,symbol,symbol) ответ2(symbol,symbol) ответ3(symbol,symbol) ответ4(symbol) ответ5(symbol,symbol) ответ6(symbol) ответ7(symbol) анализ_КтоОтношениеЧто(symbol) nondeterm поиск_кто(symbol) nondeterm поиск_что(symbol) nondeterm поиск_отношения(symbol) искать_синоним_кто(symbol) искать_синоним_отношения(symbol) искать_синоним_что(symbol) загрузить_список(список) спросить goal consult("hobbyNew2.dbs",f1), repeat, спросить, retractall(кто(_)), retractall(что(_)), retractall(отн(_)), 44
write("Есть вопросы? (Д|Н)"), readchar(ДаНет), ДаНет='Н',!,exit(). clauses repeat. repeat:-repeat.
not(кто(_)), not(отн(_)), что(Что),!, ответ7(Что); !,write("Не понял"),nl.
ответить(""):кто(Кто), что(Что), отн(Отношение),!, ответ1(Кто,Отношение,Что); кто(Кто), что(Что), not(отн(_)),ф(Кто,_,Что),!, ответ2(Кто,Что);
ответить(Запрос):fronttoken(Запрос,Лексема,Остаток), анализ_КтоОтношениеЧто(Лексема), ответить(Остаток). анализ_КтоОтношениеЧто(Лексема):поиск_кто(Лексема),!; поиск_отношения(Лексема),!; поиск_что(Лексема),!; !. поиск_кто(Лексема):not(кто(_)), ф(Лексема,_,_),!,assert(кто(Лексема)); not(кто(_)),искать_синоним_кто(Лексема),!;!,fail.
кто(Кто), отн(Отношение), not(что(_)),!, ответ3(Кто,Отношение);
поиск_отношения(Лексема):not(отн(_)), ф(_,Лексема,_),!,assert(отн(Лексема)); not(отн(_)),искать_синоним_отношения(Лексема),!;!,fail.
кто(Кто), not(отн(_)), not(что(_)),!, ответ4(Кто);
поиск_что(Лексема):not(что(_)), ф(_,_,Лексема),!,assert(что(Лексема)); not(что(_)),искать_синоним_что(Лексема),!;!,fail. искать_синоним_кто(Лексема):соб(Кто,СписокКто), загрузить_список(СписокКто), временно(Лексема),!, retractall(временно(_)),assert(кто(Кто));
not(кто(_)), отн(Отношение), что(Что),!, ответ5(Отношение,Что); not(кто(_)), отн(Отношение), not(что(_)),!, ответ6(Отношение); 45
46
fail. искать_синоним_кто(_):-retractall(временно(_)),!,fail. искать_синоним_отношения(Лексема):сот(Отн,СписокОтн), загрузить_список(СписокОтн), временно(Лексема),!, retractall(временно(_)),assert(отн(Отн)); fail. искать_синоним_отношения(_):-retractall(временно(_)),!,fail. искать_синоним_что(Лексема):соб(Что,СписокЧто), загрузить_список(СписокЧто), временно(Лексема),!, retractall(временно(_)),assert(что(Что)); fail. искать_синоним_что(_):-retractall(временно(_)),!,fail. загрузить_список([]). загрузить_список([H|T]):assert(временно(H)),загрузить_список(T). ответ1(Кто,Отношение,Что):ф(Кто,Отношение,Что),!, write("otvet1"),nl, write("Да."),nl;!,write("Нет."),nl. ответ2(Кто,Что):ф(Кто,Отношение,Что), write("otvet2"),nl, write(Кто," ",Отношение," ",Что),nl, fail. ответ2(_,_). ответ3(Кто,Отношение):ф(Кто,Отношение,Что), 47
write("otvet3"),nl, write(Кто," ",Отношение," ",Что),nl, fail. ответ3(_,_). ответ4(Кто):ф(Кто,Отношение,Что), write("otvet4"),nl, write(Кто," ",Отношение," ",Что),nl, fail. ответ4(_). ответ5(Отношение,Что):ф(Кто,Отношение,Что), write("otvet5"),nl, write(Кто," ",Отношение," ",Что),nl, fail. ответ5(_,_). ответ6(Отношение):ф(Кто,Отношение,Что), write("otvet6"),nl, write(Кто," ",Отношение," ",Что),nl, fail. ответ6(_). ответ7(Что):ф(Кто,Отношение,Что), write("otvet7"),nl, write(Кто," ",Отношение," ",Что),nl, fail. ответ7(_). спросить:write("Введите Ваш вопрос:"),nl, readln(Вопрос), upper_lower(Вопрос,Q), ответить(Q),!; !. 48
Протокол сеанса с системой (знак '?' опущен, а также опущены вопросы системы в отношении продолжения диалога): Любит ли Кирилл Татьяну otvet1 Да. Любит ли Татьяна Кирилла Нет.
otvet6 петров хобби лыжи otvet6 ирина хобби кино otvet6 татьяна хобби гимнастика otvet6 кирилл хобби гимнастика
В каких отношениях находятся Петров и Ирина otvet2 петров любить Ирина
Кто занимается гимнастикой Есть вопросы? (Д|Н)Введите Ваш вопрос: (Комментарий: в синонимах нет слова гимнастикой)
Кого любит Ирина otvet3 ирина любить кирилл Как относится Татьяна к гимнастике otvet2 татьяна хобби гимнастика Все о Петрове otvet4 петров хобби лыжи otvet4 петров любить ирина Кто любит кино Есть вопросы? (Д|Н)Введите Ваш вопрос: Чьим хобби является кино otvet5 ирина хобби кино Кто чем увлекается otvet6 кирилл хобби хоккей 49
50
5. Базовые понятия и термины Пролога Следуя известному "алгоритму пастора", который начинал каждую проповедь так: "Сейчас я расскажу вам о том, о чем я буду говорить, затем я расскажу это, а затем я расскажу о том, о чем я говорил", изложение материала подошло к точке, где я должен сказать о том, о чем я рассказывал. 5.1. Объекты "Пролог – это язык программирования, предназначенный для обработки символьной нечисловой информации. Особенно хорошо он приспособлен для решения задач, в которых фигурируют объекты и отношения между ними" [1]. Теперь вспомним, из каких "кирпичиков" строятся объекты. Любой класс объектов определяется набором составляющих его подъобъектов и структурой. Элементарные классы объектов не имеют структуры и описываются одним из встроенных типов данных, которые называются еще встроенными доменами. Домен – имя простого или составного терма (не функтор!), которое, в свою очередь, может замещать этот терм в определении другого сложного терма. domains ............................... dom1=functor1(integer,string) dom2=functor2(symbol,real,dom1) ............................... Конкретный экземпляр элементарного класса называется атомом. Это – числовые, символьные и строчные константы. Термы Все типы данных в Прологе называются термами. Имя терма называется доменом. Терм может быть простым. Простой терм – это любой класс объектов, определяемый прямо (object = integer) или косвенно доменом стандартного типа: object2=object;object2=object*. 51
Терм может быть сложным, т. е. состоять из функтора и списка термов, разделенных запятыми, который заключен в круглые скобки: любить(миша,шоколад). Структура – это другой термин для обозначения сложного терма. Основной характеристикой структуры является ее размерность (или арность) – число термов в списке. Любая структура определяет некоторое отношение между составляющими ее термами (объектами). В таком случае функтор – это имя отношения. Например, терм (факт) мяч(форма(сфера),материал(резина),размер(25), цвет([синий,красный])) определяет конкретный объект класса "мяч". Функтор "мяч" есть имя одноместного отношения "быть объектом". В рамках программы дается процедурная интерпретация всех отношений. Программисту рекомендуется составлять осмысленные имена всех объектов и функторов, помогающих читателю разобраться в интерпретации и самому программисту не забывать о ней. Стандартные типы данных являются "аксиоматическими" и не нуждаются в объявлении. Поскольку PDC Prolog является строго типизированным языком, домены необходимы для определения предикатов ("процедур" с процедурной точки зрения на Пролог). Простые домены следует рассматривать как характеристики объектов, выраженные (в конечном итоге) в терминах встроенных типов. Сложные домены определяют иерархию по вхождению менее сложных объектов в более сложные. Множество доменов, с помощью которых описываются все объекты отношения, называется системой типов. Задавая системы типов, мы подготовливаем поле для задания аксиом, которые в Прологе выражаются либо фактами внутренней БД или безусловно верными предикатами (которые также называются фактами, пример: черный(X):-темный(X). Таким образом, сами логические процедуры могут служить в качестве описаний структур данных.
52
Пролог-программа Пролог-программу следует рассматривать как доказательство теоремы, сформулированной в разделе GOAL. Доказательство использует аксиомы, сформулированные как факты Пролога, а также вспомогательные теоремы, сформулированые в виде предложений. Часто используемый термин цель – это и есть теорема, или целевое утверждение. Предложения и отдельные его утверждения рассматриваются как подцели. Вопрос – это та же теорема, или цель. Использование этого термина связано со взглядом на пролог-программу как систему управления Базой Знаний, сами знания в которой представлены фактами. В случае "Кто у нас большой и темный?" вторая интерпретация конъюнкции большой(X),темный(X) – это теорема о существовании большого и темного объекта X. Для формулирования целей и подцелей используются переменные. Переменная – символическое имя, которому может быть сопоставлен определенный домен (определенный в разделе domains или стандартный). Если сравнивать с русским языком, то переменная – это местоимение, которое должно получить конкретное значение. Переменная должна начинаться с буквы в верхнем регистре (или символа подчеркивания) и может содержать только буквы, цифры и знаки подчеркивания. Переменные могут быть связными (имеющими значение), несвязными (свободными, не имеющими значения) и анонимными. Переменная анонимная – переменная "_", используемая вместо обычной переменной в том случае, когда не важно значение соответствующей ей обычной переменной. Из переменных, отношений, конкректных экземпляров объектов, используя очень простой синтаксис, конструируются утверждения и предложения Пролога. Утверждение – одно или несколько отношений, связанных конъюнктивно (отношения, перечисляемые через запятую). Предложение – утверждение, заканчивающееся точкой, которое может быть фактом и правилом.
Правило – утверждение, истинность которого зависит от выполнения ряда условий. Заметим, что любое математическое выражение можно назвать отношением, поскольку его можно представить в префиксной записи, и тогда у нас получится обращение к предикату (вызов процедуры). Правила состоят из двух частей – головы правила и тела правила, соединенных логической связкой "если": (if|:-)." И синтаксически, и семантически левая часть правила представляет собой отношение, это то же самое, что и утверждение, т. е. правило в целом читается как "отношение имеет место быть, если верны утверждения в правой части" или "утверждение в левой части верно, если верны утверждения в правой части правила". Левая часть правила или предложение, состоящее из одного утверждения, называется предикатом. В этом смысле раздел clauses содержит определения предикатов. Предикаты должны быть объявлены в разделе predicates. Предикат может содержать одно или несколько утверждений: женщина(умная). женщина(красивая). женщина(нежная). женщина(страстная). женщина(сварливая). ................. Предикату могут соотвествовать несколько правил. В таком случае говорят о "множественном определении предиката". Число объектов определяет арность предиката. Предикат женщина имеет арность, равную 1. Пример предиката нулевой арности: люблю_женщину:женщина(умная), женщина(красивая), женщина(нежная), женщина(страстная).
53
54
5.2. Внутренние дела Пролога Работу пролог-программы можно сравнить с поиском пути на разветвленной дороге (коей является последовательность и семантика утверждений), когда известны все или часть характеристик искомого объекта, но не неизвестно, где следует свернуть. Если у нескольких объектов совпадают характеристики, то будет найден первый объект на этой дороге. Пролог ищет "первую истину". Бэктрекинг. Основной механизм доказательства теоремы – это бэктрекинг, или перебор с возвратами. Возвраты (или откаты) происходят в случае неистинности рассматриваемого утверждения (цели, подцели, вспомогательной теоремы) с целью нахождения иного пути (способа доказательства). Как Пролог убеждается, что цель достигнута? Основной механизм проверки истинности утверждений заключается в подстановке. Подстановкой, или конкретизацией, Θ называется всякое множество присваиваний вида x = t, где x – переменная, а t – терм. Каждой переменной присваевается только одно значение. Результат подстановки иногда называют подстановочным примером. Если применение подстановки Θ к утверждениям (выражениям) E1, E2 дает один и тот же подстановочный пример, такая подстановка называется унификатором, сам подстановочный процесс – унификацией, а утверждения (предикаты) – унифицируемыми. 5.3. Что такое шаблоны? Шаблон на поток параметров – шаблон, формирующийся в зависимости от того, используются ли параметры в предикатном вызове для ввода данных (т. е. данные известны), либо для вывода данных (т. е. данные неизвестны). Поточный вариант: если предикат ассоциируется с несколькими различными шаблонами, то для каждого шаблона будет реализована самостоятельная внутренняя программа, относящаяся к 55
данному предикату. Эти различные действия получили название поточных вариантов предиката. Множественные описания предиката: отдельно взятый предикат может иметь несколько описаний, каждое из которых содержит различные доменовые спецификации для аргумента (аргументов) релевантного отношения. 5.4. Управление поиском Для того чтобы найти все возможные решения, а также для управления поиском, существует ограниченный, но мощный набор явных средств: 1. Операторы сравнения и альтернатива (или: or|;). 2. Множественность правил для одного предиката. 3. Встроенные предикаты fail, (cut | !), которые порождают искусственный откат и отсечение возможных переборов соответственно. 4. Рекурсия, или самовызов, предиката. 5. Комбинация отсечения и искусственного отката. 6. Использование предиката типа repeat. repeat:-repeat Пример predicates search2 search search3 f1(integer,string) f2(integer,string) goal % Если search3 успешен, то write и выполнить search, % search2, иначе выполнить search, search2. % используется метод ОО – отсечение и откат. search3,!,write("Два первых факта удовлетворяют условию"),fail; search, search2; !. clauses 56
f1(1,"String1"). f1(2,"String2"). f1(3,"String3"). f1(4,"String4"). f2(1,"String1"). f2(0,"String2"). f2(-5,"String3"). f2(4,"String4"). % Найти первую комбинацию различных фактов, % удовлетворяющих условию. % Используется "естественный откат – бэктрегинг" % для поиска единственного успешного решения. search:f1(X1,S1), f2(X2,S2), X2<X1,write(X1," ",S1," ",X2," ",S2),nl. % Найти все комбинации разных фактов, % удовлетворяющих условию % Используется ОПН – откат после неудачи.
Заключение Со времени первой реализации (1973) Пролог проделал огромный путь и к настоящему времени в ипостаси PDC Visual Prolog v.5.2 стал одним из наиболее технологичных средств разработки программного обеспечения для различных областей человеческой деятельности. Тем не менее (многое зависит от мощности конкретного компьютера), на нем не стоит писать ПО для систем, принципиально требующих особого быстродействия, а также не стоит решать задачи сугубо вычислительного характера (для этой цели обратитесь к вечно молодому прадедушке – Фортрану – или пакету MathLab). Достаточно сосредоточиться на логической стороне задачи, и тут же станет очевидной истинная сила Пролога, заключающаяся в наглядности, красоте и простоте программ. Основываясь на естественных для человеческого мышления логических принципах, он будет неутомимо искать истинное решение, перебирая все возможные комбинации правил. Начните писать программы в среде PDC Visual Prolog v.5.2 и вряд ли вы захотите сменить это средство на какое-либо другое.
search2:f1(X1,S1), f2(X2,S2), X2<X1,write(X1," ",S1," ",X2," ",S2),nl, fail. search2:-!. % Удовлетворяют ли условию 1-е 2 разных факта? % Здесь важно, в каком месте использован откат. Если он % был бы поставлен после сравнения, то было бы найдено % единственное решение, как в предикате search. search3:f1(X1,S1), f2(X2,S2),!, X2<X1,write(X1," ",S1," ",X2," ",S2),nl.
57
58
Контрольные вопросы и задания 1. 32_DATA есть атом? 2. Что является переменной в структуре summer_time(июнь, июль,август)? 3. Сопоставимы ли термы date(D,M,Y) и date2(D1,M1,Y1)? 4. Какая из последовательностей строк является правильным фрагментом Пролог-программы: а) facts f1(string,integer,integer) f2(list1):-f3(list3) б) clauses p(X,Y,Z,S):-S1=X+Y,S2=S1+Z,S=S1+S2. q(вася). 5. Является ли приведенный ниже фрагмент законченной программой? goal comline(Koef), %Чтение параметра из командной строки Z=Koef*sin(17), write(Z). 6. Пусть zi1,…,ziN – некоторые конкретные значения и начальное значение B равно 0. Внутренняя БД задана в виде facts f(z11,…,z1N) f(z21,…,z2N) ………….. Верно ли определены правила суммирования первых элементов фактов f? P(B,S):-f(A,_,…,_),B1=B+A,P(B1,S). P(B,S):-S=B. Соберите значения ziN в список, используя встроенный предикат findall. Отсортируйте элементы полученного списка в порядке возрастания значений. 7. Создайте в программе некоторое множество фактов и сохраните их в файле.
59
8. При помощи единственного невстроенного предиката (но использующего предикат типа repeat) откройте файл и читайте строки до появления некоторой определенной строки. Запомните смещение до этой строки. 9. Найдите ошибку в программе перезаписи файла f1.txt в файл f2.txt: domains file=fIn;fOut predicates rewrite_file goal openread(fIn,"f1.txt"), openwrite(fOut,"f2.txt"), rewrite_file, closefile(fIn),closefile(fOut). clauses rewrite_file:-readln(fIn,S),!,write(fOut,S), rewrite_file;!. 10. Пусть "modul.exe text.txt -1 pars" – командная строка. Используя встроенный предикат fronttoken напишите фрагмент программы, берущий командную строку и выделяющий ее отдельные компоненты. 11. Как известно, продукционная модель представления знаний есть набор продукций,каждая из которой представляется пятеркой P(A,B,C,D,E), где A – идентификатор продукции (любого типа: число, лексема, выражение); B – область действия продукции; C – условия выполнения ("запуска") продукции; D – собственно продукция, в данном случае понимаемая как некоторое множество операций, выполняемых над объектами, принадлежащими множеству B; E – множество операций, завершающих выполнение продукции (в простейшем случае, приводящих систему в исходное состояние). Задание: напишите программу, которая • моделирует предметную область при помощи множества фактов типа объект(имя_объекта,список_свойств), 60
• генерирует события, относящиеся, к некоторому подмножеству объектов, • обрабатывает эти события при помощи соответствующих продукций. Например, игровой вариант: имеется командный пункт, подходы к которому на фиксированных направлениях перекрыты дистанционно управляемыми минами, на других направлениях подходы контролирует артиллерия, в резерве находятся мобильные группы истребителей танков. Опишите различные варианты отражения танковой атаки противника. 12. Предположим, в некотором текстовом файле строки оглавления рубрик имеют следующую структуру: <4_пробела><римское_число>.<пробел><слово_с_большой _буквы>[<пробел><слово>] Преобразуйте текстовый файл в HTML-формат с лидирующим оглавлением. Каждый элемент оглавления оформите как гипертекстовую ссылку. Пояснение: простенькая структура HTML-файла. <TITLE>Пример html-файла Оглавление
%Элементы оглавления Здесь строка оглавления 1 Здесь строка оглавления 2 ………………………………………………. %Возможно, некотрый текст Строка оглавления 1 %Текст рубрики Строка оглавления 2 ………………………………………….. 13. Некоторый файл содержит текст на русском языке. Кроме слов русского языка (лексем), в нем содержатся целые и десятичные числа, а также лексемы, набранные латиницей (например, Windows XP, HTML, TM75 и т. п.).
Напишите программу, которая: • выделяет лексемы, • подсчитывает частоту их повторения в тексте, • классифицирует по признакам: лексема кириллическая, лексема в латинице, лексема буквенно-цифровая, • для каждой лексемы определяет их позиции в тексте в координатах "строка, позиция в строке". Словарь представьте в виде фактов следующей структуры: лексема(сама_лексема,призак_лексемы,частота_повторения, список_ позиций). Подберите тексты различных объемов (200 Кб, 500 Кб, 1 Мб, 2 Мб) и постройте таблицу зависимости времени анализа от объема текста.
61
62
Список используемой литературы 1. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. М.: Мир, 1990. 2. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер. с англ. М.: Мир, 1990. 3. Мартин Дж. Надежность программного обеспечения: Пер. с англ. М.: Мир, 1986. 4. Построение экспертных систем. М.: Мир, 1987. 5. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с фр. М.: Мир, 1991. 6. Швыркин И. Пролог. Генезис // Мир ПК. 2000. № 5. 7. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ. М.: Мир, 1993. 8. Логическое программирование и Visual Prolog. СПб.: БХВПетербург, 2003.
Учебное издание
Олег Георгиевич Чанышев ПРОграммирование в ЛОГике Учебное пособие
Технический редактор Н.В. Москвичёва Редактор Е.В. Коськина Подписано в печать 11.11.04. Формат бумаги 60х84 1/16. Печ. л. 4,0. Уч.-изд. л. 4,0. Тираж 100 экз. Заказ 582. Издательство Омского государственного университета 644077, г. Омск-77, пр. Мира, 55а, госуниверситет
63
64
