WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |
УДК 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 ISBN 5-7779-0510-3 © Омский госуниверситет, 2004 2 ОГЛАВЛЕНИЕ Введение В средние века знание латинского и гречеВведение......................................................................................................... 4 ского языков являлось существенной частью об1. История Пролога.................................................................................... разования любого ученого. Ученый, владеющий 2. Синтаксис и семантика Пролог-программ........................................ только одним языком, неизбежно чувствовал се2.1. Объекты данных............................................................................... бя неполноценным, поскольку он был лишен той 2.2. Декларативный смысл Пролог-программ...................................... полноты восприятия, которая возникает благо2.3. Основные определения.................................................................... даря возможности посмотреть на мир сразу с 3. Практическое программирование на Прологе................................. 17 двух точек зрения. Таким же неполноценным ощущает себя сегодняшний исследователь в об3.1. Структура Пролог-программы........................................................ ласти искусственного интеллекта, если он не об3.2. Свободные и связанные переменные............................................. ладает основательным знакомством как с Лис3.3. Внутренняя БД Пролога.................................................................. пом, так и с Прологом – этими двумя основопо3.4. Обработка условий и организация циклов в Прологе.................. лагающими языками искусственного интеллекта, 3.4.1. Обработка условия................................................................. без знания которых невозможен более широкий 3.4.2. Использование предиката типа repeat.................................. взгляд на предмет исследования.

3.5. Списки в Прологе............................................................................ Иван Братко 3.5.1. Примеры списков................................................................... 3.5.2. Разделение списков на "голову" и "хвост"........................... Логическое программирование базируется 3.5.3. Некоторые полезные программы для работы на убеждении, что не человека надо обучать со списками................................................................................................... 28 мышлению в терминах операций компьютера… а компьютер должен выполнять инструкции, 3.6. Ввод и вывод.................................................................................... свойственные человеку.

3.6.1. Файловая система................................................................... Леон Стерлинг, Эхуд Шапиро 3.6.2. Операции с именами файлов................................................. 3.6.3. Чтение и запись...................................................................... Эволюция языков программирования – это движение от 3.7. Строки и функции работы со строками......................................... 4. Простенькая экспертная система........................................................ 40 языков императивных (как делать) к языкам декларативным (что 5. Базовые понятия и термины Пролога................................................ делать). Или иначе – от программирования в инструкциях компь5.1. Объекты............................................................................................ ютера к ПРОграммированию в ЛОГике. Отсюда происходит на5.2. Внутренние дела Пролога............................................................... звание языка – ПроЛог, к изучению которого мы и приступаем.

5.3. Что такое шаблоны........................................................................ Для иллюстрации важнейших черт Пролога воспользуемся 5.4. Управление поиском........................................................................ примером Братко [1], в котором задается вопрос базе знаний: «Кто Заключение.................................................................................................. у нас темный и большой» (Номера перед фактами не кодируются.) Контрольные вопросы и задания............................................................ Программа:



Список используемой литературы.......................................................... 1. большой(медведь).

2. большой(слон).

3. маленький(кот).

4. коричневый(медведь).

5. черный(кот).

6. серый(слон).

3 7. темный(Z):-черный(Z). Забегая немного вперед, представляю запись этой же про8. темный(Z):-коричневый(Z). граммы на Turbo Prolog'е. (Если используете VP v.5.2, можете писать по-русски все, за исключением типов встроенных переменВопрос:

ных, наименований встроенных предикатов, наименований раздетемный(X),большой(X).

лов программы).

Шаги вычисления: /* Раздел объявления предикатов*/ predicates 1) Исходный список целевых утверждений: темный(X), большой(string) большой(X).

черный(string) 2) Просмотр всей программы от начала к концу и поиск коричневый(string) предложения, у которого голова сопоставима с первым целевым серый(string) утверждением: темный(X).

темный(string) Найдено предложение 7: темный(Z):-черный(Z).

маленький(string) Замена первого целевого утверждения конкретизированным /*Главная цель-вопрос*/ телом предложения 7 – порождение нового списка целевых утgoal верждений: черный(X), большой(X).

темный(X), большой(X), 3) Просмотр программы для нахождения предложения, соwrite(X).

поставимого с черный(X). Найдено предложение 5: черный(кот).

/*Правила*/ У этого предложения нет тела, поэтому список целей при соответclauses ствующей конкретизации сокращается до большой(кот).

большой(медведь).

4) Просмотр программы в поисках этой цели завершается большой(слон).

неуспехом, и происходит возврат к шагу 3 и отмены конкретизамаленький(кот).

ции X=кот. Список целей вновь: черный(X), большой(X).

коричневый(медведь).

Продолжение просмотра ниже предложения 5. Ни одно черный(кот).

предложение не найдено. Возврат к шагу 2 и продолжение просерый(слон).

смотра ниже предложения 7. Найдено предложение 8: темный(Z):темный(Z):-черный(Z).

коричневый(Z). Замена первой цели в списке на коричневый(X) темный(Z):-коричневый(Z).

дает: коричневый(X), большой(X).

5) Просмотр программы для обнаружения предложения, соМожно изменить программу: записать факты в специальный поставимого с коричневый(X) дает коричневый(медведь). У этого файл (с любым именем), а затем загрузить их в раздел фактов:

предложения нет тела, поэтому список целей уменьшается до facts – fбольшой(медведь).

большой(string) 6) Просмотр программы и обнаружение предложения больмаленький(string) шой(медведь).

коричневый(string) У него нет тела, поэтому список целей становится пустым.

черный(string) Это указывает на успешное завершение, а соответствующая контемный(string) кретизация переменных: X=медведь.

серый(string) 5 goal танной постановщиками задач под руководством главного конст% Читаем файл bear4.dbs в раздел facts при помощи руктора проекта. В таком случае рабочим языком мог быть ас% встроенного предиката consult семблер. Итоговый программный продукт, пройдя комплексную consult("bear4.dbs",f1), отладку, получался и надежным, и быстрым. Пролог же был еще большой(X), темный(X),!, во многом языком экзотическим и не позволял создавать про% Если во внутренней БД существует существует объект X граммы, столь же оптимальные по затратам памяти и быстродей% со свойствами "большой" и "темный", то печатаем ствию. К тому же автоматизировались задачи хорошо формализо% имя этого объекта ванные, при решении которых главное достоинство Пролога – ло% знак "!" – откат – есть указание Прологу прекратить про- гический вывод из системы аксиом – как бы затушевывалось выверки числительной мощностью вечно молодого дедушки – Фортрана.

% перейти на альтернативный вариант запроса Подавляющее большинство кодировщиков не имело ника кого опыта в проектировании программных систем, и, фигурально write(X); выражаясь, их любимым занятием было изобретение наибыст% Иначе переформулируем вопрос рейших алгоритмов извлечения квадратного корня, которыми, как большой(X), коричневый(X),!, писал Дж. Мартин, "у меня заполнена вся корзина для ненужных write(X); бумаг" [3].

!. После распада Союза большинство организаций типа ПКБ АСУ прекратило свое существование; сильные в единстве коллекПонимание того, что алгоритм – это аксиоматическое зада- тивы конструкторов, постановщиков и кодировщиков распались.

ние функции, а его выполнение – частный случай логического вы- Наука потеряла в общественном сознании статус интеллектуальвода, и привело к возникновению логического программирования ного эталона, и в программистском сообществе стали задавать тон и языка Пролог. Почти 30 лет прошло с момента его появления. кодировщики, вооруженные философией наибыстрейшего извлеНа мой взгляд, сегодня, с появлением Visual Prolog’a пятой версии чения квадратного корня.

(компания PDC), Пролог – это самый технологичный язык про- Пролог как язык концептульного программирования – незаграммирования. Интерес к Прологу вообще на Западе несколько менимое средство индивидуальной разработки программного проспал после неудачи проекта пятого поколения ЭВМ, однако кри- дукта, но для этого нужно концептуально мыслить.





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

Технология предполагала четкое разделение труда, при ко- (В конце концов, это одна из причин возникновения научного натором собственно программирование (кодирование) отдельных правления «искусственный интеллект».) Пролог прост, поскольку небольших модулей производилось кодировщиками на основании использует небольшой набор базовых механизмов, включающих подробной "гостированной" технической документации, разрабо- сопоставление c образом и "бэктрекинг" (автоматический возврат 7 при поиске решения). Пролог заставляет Вас сконцентрироваться 1. История Пролога на осознании задачи и описании предметной области, а не на деталях программной реализации. Языки же типа Си представляют С точки зрения математических оснований языка историю все возможности, чтобы забыть о цели и заставить думать о себе.

Пролога можно начать с 1930 г., когда Эрбран "предложил оригиПризнаюсь, когда в 1992 г. я начал программировать на нальный метод доказательства теорем в формальных системах Turbo Prolog’е v.2.0., то писал во вполне "императивном" стиле.

первого порядка" [5]. Идея заключается в том, что для того, чтобы Но простота конструкций экономила массу времени. И только подоказать теорему сле полутора лет работы с Прологом я как-то вдруг осознал возH1 H2 … Hn C, можности решения плохо формализованных задач, задач распопроще доказать противоречивость формулы F знавания образов, кластеризации и т. п., скрывающиеся за термиH1 H2 … Hn ¬ C.

ном "бэктрекинг". По критерию минимума количества деталей Доказательство базируется на теореме о резулюциях [5, реализации, которые нужно держать в голове при программировас. 163].

нии "с листа", Пролог не знает себе равных. (Отмечу, правда, что в В 1973 г. исследователи из Марсельского университета под последнее время мне понравился Icon по той же причине. Но руководством Алана Колмероэ (Colmerauer), опираясь на работы Visual Prolog v.5.2 существенно технологичнее.) Джона Робинсона, посвященные методу резолюций, создали проПролог – язык быстрого прототипирования. Это означает, в грамму на Фортране для доказательства теорем. Программа получастности, что вы можете в течение какого-нибудь часа написать и чила название Пролог (Programmation en Logique).

отладить программу для экспериментальной проверки положений Существенный вклад в развитие теории логического провашей концепции. Это означает, что вы можете подойти к решеграммирования внесла работа Р. Ковальского "Логика предикатов нию задачи, как физик-экспериментатор: быстро разработать прокак язык программирования". В 1976 г. Ковальский и М. ван Эмграммный продукт для исследовательских целей, проанализироден предложили два подхода к прочтению текстов логических вать экспериментально исследуемое явление, внести в модель попрограмм – процедурный и декларативный.

правки и перейти к следующей серии опытов. В теории экспертВ 1977 г. Д. Уоррен и Ф. Перейра создают в университете ных систем это называется инкрементальным методом.

Эдинбурга интерпретатор/компилятор языка Пролог для ЭВМ "Поскольку для достижения высокого качества работы неDEC-10, тем самым переведя методы логического программирообходимо экспериментирование, то экспертная система развиваетвания в практичекую плоскость. В 1980 г. К. Кларк и Ф. Маккейб ся постепенно. Такой эволюционный или инкрементальный метод в Великобритании разработали версию Пролога для персональных создания стал доминирующим в области экспертных систем" [4].

ЭВМ.

В основу методологии разработки программных средств японского проекта создания ЭВМ пятого поколения (1981 г.) было положено логическое программирование. Целью проекта декларировалось создание систем обработки информации, базирующихся на знаниях, а главным средством реализации должен был стать язык Пролог. В это же время появляется множество коммерческих реализаций Пролога практически для всех типов компьютеров. К наиболее известным можно отнести CProlog, Quintus Prolog, 9 Silogic Knowledge Workbench, Prolog-2, Arity Prolog, Prolog-86, SCO UNIX и Linux. Ее загрузочный файл объемом 20 Мбайт можТurbo Prolog и др. [6]. но найти по адресам:

Наиболее известна в России система программирования http://www.visual-prolog.com/vip/vipinfo/freeware_version.htm, Turbo Prolog – коммерческая реализация языка для IBM-совмести- http://www.pdc.dk/vip/vipinfo/freeware_version.htm1.

мых ПК. Ее первая версия разработана датской компанией Prolog В 2003 г. издательство "БХВ-Петербург" тиражом 3000 экз.

Development Center (PDC) в содружестве с фирмой Borland издало книгу "Логическое программирование и Visual Prolog" International в 1986 г. Cамым существенным отступлением от не- объемом 990 стр. [8]. Она содержит CD с Personal Version Visual официального стандарта было введение строгой типизации дан- Prolog v. 5.2.

Pages:     || 2 | 3 | 4 | 5 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.