Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Содержание
1. Введение в функциональное и логическое программирование…………5
1.1. Основные классы вычислительных моделей…………………………… 5
1.1.1 .Процедурная вычислительная модель……………………………… 6
1.1.2 Функциональная вычислительная модель………………………… .7
1.1.3.Логическая вычислительная модель…………………………………8
1.1.4 Объектно-ориентированная модель…………………………………8
1.2 . Методы оценки…………………………………………………………..9
1.3 . Обмен информацией в процессе оценки…………………………… …9
1.4.Понятие искусственного интеллекта……………………………………11
1.5. Символьные языки программирования и исчисление предикатов первого порядка…………………………………………………………………..11
1.6. Основные направления в искусственном интеллекте…………………14
1.7 . Подходы к построению искусственного интеллекта………………….15
2. Основы логического программирования………………………………….19
2.1. Основные понятия……………………………………………………. 19
2.2. Определение отношений на основе фактов и правил…………… ...20
2.3.Пример программы на языке Пролог………………………………...21
2.4. Использование рекурсии……………………………………………….25
2.5 Декларативная и процедурная трактовка программы………………..28
2.6. Структура программы…………………………………………………30
2.7 . Особенности логического программирования……………………...33.
2.8. Использование предиката not и квантификация переменных в
подцели с предикатом not...................................................................34.
3. Синтаксис Пролога…………………………………………………………..38
3.1. Объекты данных………………………………………………………38
3.2. Составные объекты и альтернативные домены………………………39
3.2.1. Составная структура……………………………………………...40
3.2.2. Доменная структурная диаграмма……………………………..41
3.2.3. Предикатная структурная диаграмма………………………….42
3.2.4. Альтернативные домены………………………………………....42
3.3. Сопоставление структур……………………………………………..44
3.4. Унификация и подстановки. Откат…………………………………45
3.5 Основные правила поиска с возвратом и пример на унификацию ...50
4. Принцип резолюции………………………………………...............................52
4.1. Логическое следствие …………………………………………………54
4.2 Логический вывод……………………………………………………....55
4.3. Преимущества и недостатки метода резолюции……………………57
4..4. Пример применения метода резолюции……………………………..59
5.. Управление поиском решения……………………………………………...61
5.1. Метод отката после неудачи………………………………………….62
5.2.Метод отсечения и отката……………………………………………..64
5.2.1. Влияние предиката cut на составную цель……………………64
5.2.2. Влияние предиката cut на процедуру………………………….65
5.2.3. Использование зеленых и красных отсечений………………..68
5.2.4. Использование предиката not как средства управления. ……..71.
5.3. Метод повтора, определяемый пользователем………………………71
5.4. Методы организации рекурсии………………………………………. 76
6. Работа со списками………………………………………………………....84
6.1. Операции над структурами типа список………………………………87
6.2 .Предикат findall и его использование…………………………………97
6.3 . Операции со структурами данных…………………………………….98
Литература………………………………………………………………………..101
1.Введение в функциональное и логическое программирование
“ Программирование - это
одно из наиболее сложных
направлений математики”
Дейкстра
“Границы моего языка –
границы моего мира”
Людвиг Виттгенштейн
1.1. основные классы вычислительных моделей
Курс посвящен изучению логического и функционального программирования.
Современным программистам предлагаются различные стили программирования (парадигмы).
Внутри каждого из этих стилей имеются свои наборы различных языков.
В программировании термин парадигма используется для определения модели вычислений, то есть способа структурирования информации, организации вычислений и данных.
Для описания процесса вычислений используются четыре основных типа таких моделей: процедурная, функциональная, логическая и объектно-ориентированная.
Поставленная перед разработчиком задача обычно имеет некоторый набор исходных данных и цель. Это отражается в постановке задачи. Если поставленная задача решается на компьютере, то возникает проблема формализации этой задачи, так как вычислительный процесс может быть выполнен на компьютере только в том случае, если он формализован. В основу вычислительного процесса могут быть положены разные математические формализмы (вычислительные модели). Четыре основных парадигмы программирования представлены на рис.1.1.
Рис. 1.1. Различные стили программирования
1.1.1 Процедурная вычислительная модель
В этой модели алгоритм (программа) в явном виде (с помощью выполняемых операторов присваивания) определяет как сами действия, так и последовательность их выполнения ( С, С++, Pascal, Ada и другие языки программирования) Концепция памяти – преобразование исходного состояния памяти (значения переменных) в заключительное состояние. Фон-неймановские машины состоят из ячеек памяти и процессора, имеющего локальную память в виде регистров. Компьютер работает на ограниченном множестве операций, и программист вынужден мыслить в терминах этого ограниченного множества операций.
1.1.2 Функциональная вычислительная модель
В этой модели программа рассматривается как множество определений функций. Отличительной чертой этих моделей является то, что в основу их положена математическая модель, называемая “лямбда-исчислением” Черча. Для представления обычной функции используется выражение f(x).При этом неясно: то ли оно означает функцию f,то ли ее значение при заданном параметре x. Для четкого описания функции было введено выражение xf(x).То есть, когда хотят рассматривать выражение P как функцию от x, следует использовать запись xP (лямбда-абстракция). Таким образом, выражение x(x+y) является функцией от x, а не от у. При этом x называют связанной переменной, а y- свободной переменной.
Таким образом, главным в парадигме функционального программирования является понятие функции (отсюда и название – функциональное программирование). Математики придумали множество теоретических и практических аппаратов для оперирования функциями (дифференцирование, интегрирование, функциональный анализ, теория нечетких множеств и т.д.) Теперь появился раздел, который напрямую связал математическую теорию функций и технологию создания программного обеспечения (ПО) для компьютеров. Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. То есть, функцию можно рассматривать как некоторый черный ящик, входные значения которого порождают значения на выходе (выражают связь между входом и выходом некоторого процесса). Так как вычисление – это тоже процесс, имеющий вход и выход, то функция является вполне адекватным средством описания вычислений. Именно этот простой принцип и положен в основу функциональной парадигмы и функционального программирования. Функции определяются через другие функции или рекурсивно – через самих себя. В процессе выполнения программы функции получают параметры, вычисляют и возвращают результат, в случае необходимости вычисляя значения других функций. Все, что необходимо сделать программе для получения желаемого результата при решении задачи, должно быть представлено в виде системы взаимосвязанных функций.
1.1.3. Логическая вычислительная модель
В этих моделях вычисления представляются с помощью логики предикатов, а языки программирования, используемые для описания вычислений, называются логическими. Компьютер используется для получения выводов из декларативного описания предметной области. В качестве основы используется раздел математической логики, называемый автоматизация доказательства теорем. Для самого описания предметной области используются хорновские дизъюнкты как часть исчисления предикатов первого порядка. В логическом программировании основными являются понятия объектов и отношений между ними. Первая часть пособия посвящена именно логическому программированию и языку Пролог, поэтому сразу после введения перейдем к более подробному изложению этого стиля программирования.
1.1.4. Объектно-ориентированная вычислительная модель (ООП)
Основным элементом программы в этом стиле является объект, объединяющий в себе данные и операции над ними, называемые методами. Это отличает ООП от процедурного программирования, где операции отделены от данных.
Внутренняя структура данных и реализация методов объекта скрыта от остальной программы (инкапсуляция). Программе доступен только интерфейс объекта.
Основной механизм повторного использования программного обеспечения – это класс (по сути шаблон, описывающий все объекты, для которых характерны одинаковые операции и элементы данных).Разработка шаблонов позволяет создавать проекты сложных систем прямо “на лету”. Платить за это, правда, приходится выразительностью.
Для существующего класса можно создать подклассы путем использования наследования. Способность подклассов одного класса отвечать на одно и то же входящее сообщение по-разному называется полиморфизмом.
Такова краткая характеристика различных парадигм программирования.
Следовать какой-либо парадигме можно практически на любом языке программирования, но каждый язык программирования предназначен в первую очередь для работы внутри своей парадигмы.( Можно например, следовать функциональной парадигме программирования на языках С или С++, когда в теле каждой функции будет только одна инструкция – return.)
Необходимо решить, какой математический формализм должен быть положен в основу вычислительного процесса, который будет выполнять компьютер для решения задачи, то есть выбрать парадигму программирования.
1.2.Метод оценки (способ получения результатов)
Для каждой вычислительной модели существует свой метод оценки. Эти методы разделяются на 3 основных типа:
1.3. Обмен информацией в процессе оценки
В процессе оценки необходимо осуществить обмен информацией. Для этого используют различные способы:
При программировании применяются различные вычислительные модели (стили), соответственно различные методы оценки и различные способы передачи информации.
Алгоритмы, используемые в этих стилях (моделях), реализуются с помощью языков программирования 4 типов – процедурного, функционального, логического и объектно-ориентированного.
Каждый язык программирования приспособлен к определенному типу вычислений, и использование того или иного языка вынуждает применять именно те типы вычислений, к которым данный язык программирования приспособлен. Это значит, что язык программирования навязывает определенный взгляд на мир и вынуждает мыслить в терминах того языка, на котором предполагается работать. Выбор стиля должен проходить оценку на соответствие стиля и цели программирования. Когда выбор языка сделан, то используются конструкции выбранного языка, а, следовательно, приходится мыслить в терминах семантики этих конструкций. Именно смысловая (семантическая) часть конструкций языка и определяет процесс мышления программиста. Конечно, факторы, которые влияют на выбор стиля, часто противоречивы. Например, эффективность программы с точки зрения архитектуры машины и ясность программы с точки зрения человека могут требовать различных способов изображения. Часто можно написать короткую программу, но понять ее будет очень трудно. Именно в таких ситуациях удачный выбор способа представления данных и метода решения позволяет найти приемлемый компромисс.
1.4.Понятие искусственного интеллекта
Искусственный интеллект- это одна из новейших областей информатики, предметом которой является разработка компьютерных систем, обладающих возможностями, связанными со способностями естественного интеллекта. Задачи, для которых неизвестны алгоритмы решения, априорно относятся к сфере искусственного интеллекта.
Особенность задач, относящихся к сфере ИИ, заключается в том, что их почти невозможно формализовать, то есть для их описания не подходят обычные (примитивные) структуры данных, используемые в традиционных языках программирования для обработки данных, и методы работы с ними. Такие задачи не предусматривают обработки данных с фиксированной структурой(т.е. с такой структурой, в которую входят отдельные численные значения или матрицы численных значений). Один из фундаментальных вопросов программирования – это вопрос о представлении сложных объектов (например, множеств) и вопрос об эффективной реализации операций над подобными объектами. Наиболее часто используются структуры данных, принадлежащие к трем большим семействам (списки, деревья, графы).
1.5.Символьные языки программирования
Понятия отношения и предиката
В сфере ИИ используются символьные языки представления знаний и формализмы, стоящие на более высоком понятийном уровне. Здесь важное значение имеет обработка отношений между данными. При этом эти отношения могут претерпевать существенные изменения в ходе выполнении программы. Отношение – это обобщение функций, то есть более общее понятие, чем функция (отношение определяется как подмножество прямого произведения множеств). Функция, рассматриваемая как отношение – это подмножество декартова произведения. (декартовым произведением двух множеств M1 и M2 называется множество всевозможных упорядоченных пар <x,y>, где х берется из М1, а y –из М2.)
Любую функцию можно представить в виде отношения с помощью следующего преобразования:
(f x x …x)=y (f x x …x y)
функция отношение
Функция- это частный случай отношения, не содержащего двух элементов (x x….x y) и
(x x… x y) таких, что y y ,так как значение функции определяется однозначно.
У функции, представленной в форме отношения, аргументы и результат находятся в равнозначных позициях аргументов отношения.
Определение понятия отношение
Пусть дано множество М. Рассмотрим декартово произведение множеств M =M*M*…*M – множество всех упорядоченных последовательностей из n элементов(x1 ,x2 ,…xn) таких, что xi M; n-местным отношением на М называется его подмножество: RMn.
Например, сложение двух целых положительных чисел можно представить в виде отношения между множествами целых чисел (N1,N2,N3)
R N1*N2*N3,
где n1+n2=n3 и ni принадлежит множеству Ni.
Отношение можно явно представить как множество троек:
R= {(1 1 2),(1 2 3),(1 3 4),. . .}
Это отношение имеет три численных аргумента, т.е. оно является 3-х местным. 0-местное отношение реализует константу, 1-местное отношение – реализует свойство, 2-х и более местное отношение можно графически представить в виде сети. На основе отношений могут быть реализованы декларативные языки (Лисп за основу программирования берет функцию и лямбда-исчисление, а Пролог основан на более общем понятии отношения и хорновской логике.)
Иногда может рассматриваться множество М1*М2*…*Mn, где Mi- множества различной природы, и подмножества этого множества рассматриваются в качестве отношений. Например, прямая и плоскость – объекты принадлежащие разным множествам, но они могут находиться в отношении параллельности, компьютер может быть инструментом для человека, на нем работающего (М1-множество компьютеров, М2-множество людей) и т.д.
Определение понятия предикат
n-местным предикатом P(x1,x2,..,xn) называется функция P: MnB, где M –произвольное множество, а B={1,0}.
М называется предметной областью, xi – предметными переменными.
Для любых M и n существует взаимно однозначное соответствие между n-местными отношениями и n-местными предикатами. Каждому n-местному отношению R соответствует предикат P такой, что P(x1,x2,….,xn)=1 тогда и только тогда, когда (x1,x2,….,xn)R,и любому предикату P(x1,x2,..,xn) соответствует отношение R такое, что (x1,x2,..,xn)R тогда и только тогда, когда P(x1,x2,..,xn)=1.Это значит, что областью истинности предиката P является множество R.
Отсюда видно, что предикат – это индикатор отношения. Он принимает значение true или false в зависимости от того, имеет место данное отношение или нет.
ИИ изучает методы решения компьютерных задач, не имеющих явного алгоритмического решения, используя в качестве инструмента символьные языки программирования, в том числе и язык исчисления предикатов первого порядка.
1.6. Основные направления в искусственном интеллекте
В рамках ИИ различают три основных направления:
Сверхзадачей ИИ является построение компьютерных интеллектуальных систем, которые обладают уровнем эффективности решений неформализованных задач, сопоставимым с человеческим или превосходящим его.
В качестве критерия интеллектуальности предложен так называемый тест Тьюринга.
Алан Тьюринг предложил его для проверки того, является ли компьютер разумным в человеческом смысле слова. Тест заключается в том, что человек-судья переписывается с двумя собеседниками на естественном языке. Один из собеседников- человек, другой – компьютер. Каждый из собеседников старается, чтобы человеком признали его. Общение сводится к обмену текстовыми сообщениями. Промежутки времени передачи сообщений контролируются, чтобы судья не мог делать заключения исходя из скорости ответов. Если судья не может надежно определить, кто есть кто, тогда считается, что компьютер прошел тест.
К настоящему времени ни одна аппаратно-программная система не достигла такого уровня развития, чтобы успешно пройти тест Тьюринга.
Поэтому в последнее время в рамках идеологии ИИ рассматривается третий подход к построению систем а именно, создание смешанных человекомашинных, или, интерактивных интеллектуальных систем, осуществляющих симбиоз возможностей естественного и искусственного интеллекта. Важнейшими проблемами в этих исследованиях являются оптимальное распределение функций между естественным и искусственным интеллектом и организация диалога между человеком и машиной.
С ИИ тесно связаны математика, логика, теория информатики, филология, философия, психология и много других смежных областей знаний.
1.7. Подходы к построению ИИ.
1) логический – основанный на правилах логического вывода;
2) структурный – моделирование структуры человеческого мозга. Основой моделирования является нервная клетка – нейрон. (например, модель зрительного восприятия и распознавания –перцептрон). Отсюда направление –нейронные сети ( строим отдельный нейрон, разрабатываем топологию связей между нейронами, разрабатываем алгоритм обучения) Нейронные сети успешно применяются в задачах распознавания образов, в робототехнике, для обслуживания АЭС, ТЭС, в медицине, автономные летающие устройства для сбора разведывательной информации(беспилотные самолеты).Наиболее известны нейросети с обратным распространением ошибки, сети Хопфилда и стохастические (вероятностные) нейронные сети.
Легкое распараллеливание алгоритма и высокая производительность нейронных сетей даже в условиях неполноты информации является их неоспоримым примуществом.
3) эволюционный подход – построение начальной модели и разработка правил, по которым она может изменяться (эволюционировать).При этом начальная модель может быть любой (и логической, и структурной). Разрабатывается эволюционный алгоритм, проверка на оптимальность - то есть выбор наилучшей модели по определенному критерию, а дальше моделируются новые модели и т.д.
4) имитационный – кибернетический подход Объект, поведение которого имитируется, представляется черным ящиком. Главное, чтобы модель в аналогичной ситуации вела себя также как и моделируемый объект. Используется теория адаптивных систем и эволюционного развития.
5) смешанные системы
Замечания
Большой интерес представляют голографические системы обработки информации. Они обещают решение тех задач ИИ, с которыми не справляются даже самые мощные компьютеры. Это связано с тем, что некоторые ключевые механизмы работы нашего мозга похожи на механизмы работы оптической голограммы.
В рамках парадигм ФЛП предлагаются различные методики и инструменты для решения задач ИИ.
1) Языки ИИ, обеспечивающие простоту модификации
программ и данных;
(Lisp-List Processing –обработка списков; Haskell ,Caml, Curry, Hope и др.)
Prolog –Programming in Logic-программирова-
ние в терминах логики)
2) Системы программирования для поддержки
составления, разработки и сопровождения программного обеспечения ПО (создание удобной среды разработки ПО)
3) Важна и структура самой машины, позволяющая с
большей эффективностью использовать эти
языки.
В настоящее время мы работаем с машинами чет-
вертого поколения, т.н. фон-неймановскими машинами. Процедурные языки программирования созданы именно под эту архитектуру. Другие языки программирования могут входить с этой архитектурой в противоречие. Правда, современные технологии обеспечивают высокие скорости работы процессоров и большие объемы достаточно дешевой памяти, так что вопрос согласования языков программирования и архитектуры компьютера не стоит сегодня так остро.
Что относится к области ИИ?
доказательства теорем;
базы данных и базы знаний;
(интересно сравнить системы БД SQL и прологовские: для выполнения тех же задач вы получаете возможность работать с развитой логикой. При этом система Visual Prolog,например, обеспечивает высокую скорость работы и имеет большую эффективность и более дружественный интерфейс.)
Самоорганизующиеся СУБД, способные подстраиваться под профиль конкретной задачи без администрирования.
задачи символьной математики;
эврестические задачи, моделирующие поведение человека в проблемной ситуации;
экспертные системы;
нейронные сети (используются в робототехнике, информационных технологиях)
логико-лингвистические модели в системах управления;
печать с голоса;
интеллектуальные игры;
мутационные исчисления ( набор правил для моделирования процесса эволюции по созданию Homo Sapiens).
Операционные системы (ОС) реального времени (для принятия решений в рамках дефицита времени)
Web- приложения и административные системы.
2.Основы логического программирования и язык Пролог.
2.1.Основные понятия
Процедурный стиль программирования зависит в большой степени от внутренних механизмов компьютера, так как процедурные языки ориентированы в основном на последовательное исполнение инструкций, оперирующих с памятью (операции присваивания). Однако, подавляющее большинство задач, которые решаются на компьютере, напрямую с архитектурой машины не связаны.
Логический стиль программирования строится на основе абстрактной модели, поэтому тоже никак не связан с архитектурой ЭВМ. Поскольку вычисление есть частный случай логического вывода, а алгоритм – это аксиоматическое задание функции, то весьма актуальным является возможность применения идей логического программирования для решения достаточно широкого круга задач (касающихся объектов и отношений между объектами).
Суть идеи логического программирования(ЛП): компьютеру в качестве программы можно представить не алгоритм решения задачи, а формальное ее описание в виде аксиоматической системы, тогда построение решения задачи в виде вывода можно поручить компьютеру. Это значит, что программа на Прологе не отображает последовательность действий, как это принято в процедурных языках, а представляет собой определенный набор фактов и правил, которые позволяют на их основе выполнить логический вывод. Это возможно, потому что имеются методы автоматического поиска доказательства (то есть существуют некоторые универсальные алгоритмы, которые могут быть запрограммированы). Именно поэтому эффективность ЛП зависит не только от аксиоматизации задачи, но и от качества компилятора, который реализует поиск доказательства.
Язык Пролог(Prolog-PROgramming in LOGic) –декларативный язык, так как знания в виде фактов и правил их использования представлены в декларативной форме.
2.2.Определение отношений на основе фактов и правил
Центральное понятие- отношение между объектами, представленное в терминах ограничения условий и целей. Программист мыслит в терминах структуры отношений, не заботясь о точности их реализации.
Отношение – это обобщение функции, которое определяется как подмножество прямого произведения множеств.
Итак, сама программа – это множество фактов и правил, задающих отношения между объектами в конкретной прикладной области. Отношение в Прологе называется предикатом. Объекты, связанные этим отношением, называются аргументами. Аргументы могут быть константами (атомами) или переменными.
Предикат определяет, является ли данное отношение истинным или ложным, поэтому предикат можно рассматривать как “индикатор отношения”.
Для записи отношений между объектами можно использовать различные формализмы. В ЛП используется исчисление предикатов первого порядка (ИП1П).Вернее, ограниченная форма ИП1П в виде логики так называемых хорновских предложений(факты, правила и цели).
По сути хорновские дизъюнкты - это логические импликации(правила типа если - то) .В общем виде импликации имеют вид:
A;A;….;A:-B,B,…,B (n>=0;m>=0)
В – это посылки импликации, А – это заключение импликации.
Чтобы увеличить эффективность метода резолюций, используемого в качестве метода автоматизации доказательства теорем, берутся лишь формулы при n=1 и m>=0:
Формула Хорна-> A:-B,B,….,B
(n=1; m>0)- это правило
A:-
(m=0;n=1) - это факт
?:-B,B,…..,B
(m>0;n=0) –это цель
Рис.2.1. Схема, демонстрирующая два уровня значения программы – декларативное и процедурное
2.3 Пример программы на языке Пролог
Рассмотрим классическую программу родственных отношений на языке Пролог
Дано дерево родственных отношений вида:
Рис.2.2.Дерево родственных отношений
Предположим, надо определить, кто является сестрой Ann?
Тот факт, что Tom является родителем Bob (стрелки на рисунке) можно записать следующим образом:
parent(tom,bob).
parent- имя отношения –предикат
tom,bob –параметры (аргументы) отношения.
Имена собственные являются константами и в Прологе пишутся со строчной буквы.
Программа на Прологе для ответа на вопрос, кто является сестрой Ann имеет следующий вид:
Листинг 2.1.Программа о семейных отношениях
domains
person=symbol
predicates
parent(person,person)
female(person)
sister(person,person)
clauses
parent(pam,bob). %определение отношений
parent(tom,bob). % на основе фактов
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).
parent(tom,liz).
female(ann).
female(pat).
female(liz).
female(pam).
sister(X,Y):- %определение отношений
parent(Z,X), % на основе правил
parent(Z,Y),
female(X),
X<>Y.
goal (внешняя цель)
sister(X,ann).
Представленное на рис.1.1.дерево семейных отношений определено в программе на основе 6 предложений, каждое из которых объявляет о наличии одного факта, выраженного отношением parent.Это отношение определяет связь между двумя объектами.
Чуть ниже представлены 4 предложения, каждое из которых объявляет о наличии факта, выраженного унарным отношением female.Это отношение определяет такое свойство объекта как принадлежность к женскому полу.
Последовательность предложений, описывающих один и тот же предикат, называется процедурой.
Все предложения, относящиеся к одной и той же процедуре, имеют одинаковое имя предиката и одну и ту же размерность(арность). Эти предложения должны следовать друг за другом.
Следующее предложение программы определяет отношение sister(X,Y) на основе правил. Правила определяют условия, при которых отношения между объектами становятся истинными. Чем правило отличается от факта? Факт всегда является истинным. Правило становится истинным при выполнении определенных условий. Правило имеет голову и тело. Правило (его заголовок) принимает значение истина только в том случае, если приняли значение истинности все предложения, составляющие его тело.
голова:- тело.
Правило применимо к любым объектам, поэтому в правиле используются переменные, которые по ходу решения задачи могут конкретизироваться.
Для описания объектов и отношений между ними используются идентификаторы. Идентификаторы объекта и отношения начинаются со строчной буквы, за которой может следовать любое число символов – буквы верхнего и нижнего регистров, цифры, знаки подчеркивания.
Нельзя использовать пробелы, знак минус и слеш.
Построим графы, определяющие абстрактные отношения, такие как сестра и тетя :
Рис.2.3 Определение отношений сестра и тетя
2.4.Использование рекурсии
Рекурсия – способ описания функций или процессов через самих себя. Рекурсия используется как основа для записи рекурсивных конструкций.
Введем в рассмотрение еще одно отношение –ancestor (предок). Определим его в терминах уже известного отношения parent. Отношение ancestor может быть представлено с помощью двух правил:
Рис.2.4.Отношение ancestor для прямого(правило 1) и отдаленного предков(правило2)
Для всех X и Z,
1) X - предок Z, если
X – родитель Z.
Второе правило (б) формулируется так:
Для всех X и Z,
2) если имеется такой Y, что
а) X -родитель Y(прямые предки) и
б) Y –предок Z. (отдаленные предки)
Эти утверждения можно перевести на Пролог таким образом:
1) ancestor(X,Z):-
parent(X,Z).
2) ancestor(X,Z):-
parent(X,Y),
ancestor(Y,Z).
Отсюда видно (2), что было использовано утверждение ancestor, которое само еще не было полностью определено. Такие определения называются рекурсивными. Отношение, представленное в заголовке правила (2) зависит от более простой версии самого себя- от подцели ancestor(Y,Z).
Предложенная задача содержит в себе подзадачу такого же типа. При работе с такими задачами должно существовать обязательное условие выхода из рекурсии, иначе рекурсия может оказаться бесконечной, а правила бесполезными. Окончательное решение задачи откладывается до тех пор, пока не сработает утверждение, которое и определяет условие выхода из рекурсии. Ответственность за выход из рекурсии лежит на программисте.
Состав рекурсивной процедуры :
2.5.Декларативная и процедурная трактовка программы
Декларативное значение определяет то, каким должен быть результат работы программы. Процедурное значение определяет способ получения этого результата, то есть показывает, как на самом деле Пролог-система проводит обработку представленных в программе отношений. Процедура выводит сведения об истинности или ложности целей и в случае истинности целей показывает при каких значениях переменных это достигается.
Так как результаты в принципе определяются их декларативным значением, то для написания программы этого должно быть достаточно. Процедурные аспекты надо оставлять для самой системы.
Однако декларативный подход не всегда позволяет решить все задачи. Поэтому процедурные аспекты полностью игнорироваться программистом не могут,в частности, из-за необходимости обеспечения вычислительной эффективности.
Прогресс в технологии программирования достигается за счет все более глубокого ухода к декларативным аспектам (они легче понимаются и легче поддаются формальному описанию). Желательно все процедурные детали переложить на саму систему.
Но система Пролог не всегда, к сожалению, способна проработать все процедурные детали. Часто это бывает связано с тем, что стратегия решения задачи в компиляторе – другая и не совпадает с порядком написания предложений в программе (например, рекурсивный вызов стоит раньше других подцелей предложения, из-за этого не происходит надежной обработки). В этой ситуации необходимо сначала сосредоточиться на декларативных аспектах программы, затем оттестировать программу, и в случае ее отказа, попытаться переупорядочить предложения и цели.
Пример. Вернемся к задаче о родственных отношениях. Предположим, что мы определили отношение – предок так (см рис.2.5. 2)):
Рис.2.5. Влияние переупорядочения предложений в программе с использованием рекурсии
На рис 2) с декларативной точки зрения все в порядке.
Но при процедурной трактовке смысл становится совершенно другим. Переменная Z здесь не конкретизируется в момент обработки рекурсивной подцели ancestor(X,Y). У нас первым стояло предложение parent(Y,Z). Оно вырабатывало новое значение переменной Y, а уже потом использовало это новое значение в рекурсивной подцели ancestor(X,Y). Теперь этого нет. К чему это приведет? Это приведет к тому, что когда компилятор будет пытаться выполнить запрос к процедуре ancestor, то вначале он отыщет правильные ответы, а затем будет выполнять рекурсивные действия вплоть до исчерпания доступного объема памяти. Это происходит потому, что рекурсивный вызов не является последним в предложении, а стоит раньше других подцелей. Cтратегия же решения задачи в компиляторе – другая, поэтому не будет надежной обработки.
Попробуйте самостоятельно сформулировать правило, отображенное на рис 1). А теперь попытайтесь объяснить, что произойдет с программой, в которой процедура ancestor представлена так как на рис 3).
Когда мы пишем программу, то используем процедурное понимание. Когда мы определяем значение программы, рассматривая это значение с точки зрения истинности, то применяем декларативное понимание.
В “чистом прологе” декларативное значение программ не зависит от порядка предложений и порядка целей в предложениях.
Процедурное значение зависит от порядка целей и предложений. Поэтому порядок может повлиять на эффективность программы, приводя ее иногда к бесконечным рекурсивным выводам.
Для обеспечения процедурной надежности программ разработаны общие методы предотвращения бесконечных циклов. При решении более сложных задач будем их применять.
2.6. Cтруктура программы
Итак, на основе первой показательной программы видно, что структура программы в общем случае имеет вид:
domains
/*объявление доменов*/
predicates
/*объявление предикатов*/
clauses
/*предложения-факты и правила*/
goal
/*цель программы*/
Раздел доменов (domain)
В этом разделе объявляются домены всех аргументов, используемых в предикатах. Домены позволяют задать разные имена различным видам данных. По сути в этом разделе задается область интерпретации предметных переменных.
domains
title, author=symbol
year=integer
predicates
book(title, author, year)
Объявление собственных доменов позволяет отследить ошибки. Несмотря на то, что author и title интерпретируются типом symbol ,они не эквивалентны друг другу.
Если вы перепутали местами объекты, то это будет сразу обнаружено.
Интерпретация (задание типов аргументов) при декларации предикатов может происходить напрямую (без их описания в разделе domains),но только в случае, если эти домены – стандартные (смотри таблицу стандартных доменов).
Раздел предикатов ( predicates)
Если в разделе clauses вы описали собственные не cтандартные предикаты, то их необходимо объявить в разделе predicates(иначе Пролог вас не поймет).
В результате объявления предиката вы сообщаете, к каким доменам принадлежат аргументы этого предиката. Только стандартные предикаты объявлять не обязательно.
Все пользовательские предикаты c указанием доменов(типов) их аргументов в этом разделе просто перечисляются.
predicates
summa(integer, integer, integer)
Декларация предиката не завершается точкой.
Имя предиката начинается с буквы, за которой может следовать буква, цифра или знак подчеркивания.
Раздел предложений (сlauses)
Раздел состоит из фактов и правил.
Факты(facts) устанавливают отношения между объектами или описывают свойства объекта:
student(petrov, sp-81,2010).
cup(red).
parent(bob, tom).
Правила(rules)- определяют, когда эти отношения истинны. Правила позволяют выводить одни факты из других.
Голова правила истинна тогда и только тогда, когда являются истинными все утверждения, составляющие тело.
If тело then голова ( голова if тело)
Раздел целей (goal)
запускает программу в работу.
Выводы:
Дедуктивной системой(ДС) называется способ задания множества путем указания исходных элементов (аксиом исчисления) и правил вывода, каждое из которых описывает, как строить новые элементы из исходных.
ДС называют также исчислением (то есть правилами вычисления и оперирования объектами) или формальной системой.
Когда говорят о языках программирования, предложения которых построены на основе строгих правил таким образом, чтобы для любой последовательности символов можно было сказать, является она правильно построенной конструкцией этого языка или нет, то о языке говорят тоже как о формальной системе.
Множество фактов, правил и целей задают логическую программу.
Факты задают отношения между объектами.
Правила определяют одни отношения через другие.
Цель требует доказательства, исходя из множества фактов и правил программы. Процесс доказательства – само выполнение программы.
Логика возложена на программиста, управление – на компьютер. Компьютер строит необходимый для решения логический вывод в соответствии с процессом упрощения (внутренние подпрограммы унификации и поиск с возвратом) и механизмом вывода (принцип резолюции – раздел логики – автоматическое доказательство теорем)
Программист должен быть квалифицирован и в представлении знаний, и в понимании того, как они обрабатываются на компьютере.
2.7.Особенности ЛП:
- Декларативный характер описания программы приводит к высокой степени независимости отдельных частей программы, каждая из которых реализует отдельную часть решения.
- Возможность работать в обоих направлениях, так как последовательность и способ выполнения программы не фиксируется. На основе исходных данных можно вычислить результат, но также без дополнительного программирования на основе результата можно получить исходные данные.
- Возможность рассмотрения альтернативных решений и поиск всех возможных решений.
2.8 Использование предиката not и
квантификация переменных в подцели с предикатом not
Информация о фактах, которые не являются истинными и об отношениях, которые не соблюдаются, называется отрицательной информацией. Такая информация в явной форме в программе не хранится. Просто считается, что вся информация, которая отсутствует в программе, ложна.
Встроенный предикат not имеет один аргумент. Этим аргументом является подцель, значение истинности которой (после выполнения подцели) заменяется на противоположное.
Предикат not будет успешным, если не может быть доказана истинность данной подцели. Это приводит к предотвращению связывания внутри not несвязанных переменных.
Свободные переменные в предикате not не разрешены, потому что для связывания свободных переменных в подцели подцель должна унифицироваться с каким-либо предложением и выполниться, то есть, если вы используете внутри not переменную, то она должна быть означена до своего использования.
Квантификация переменных в подцели с предикатом not
? not(sister(ann,X)) если Ann не является сестрой X, то предикат sister –неуспешен, а not(sister…)- истина.
В подцели sister(ann,X) переменная X квантифицирована экзистенциально (существует ли некоторый X, для которого Ann является сестрой?)
Переменная X в подцели с отрицанием not(sister(…)) квантифицирована универсально (является ли Ann не сестрой X?То есть для любого X является ли Ann не сестрой X? Для проверки этого положения требуется отыскать только одно значение X, при котором подцель с отрицанием потерпит неудачу.
Квантификация переменных всегда изменяется на противоположную, если фраза подвергается отрицанию.
Рассмотрим задачу, в которой заданы пары европейских государств, часть из которых имеет общие границы. Необходимо определить названия пар государств, не имеющих общих границ.
Предположим, программа для решения этой задачи имеет вид:
Листинг 2.2.Использование предиката not
domains
country=symbol
predicates
euro_pair(country,country)
border(country,country)
find_non_border_pair
goal
find_non_border_pair.
clauses
euro_pair("France","Germany").
euro_pair("France","Spain").
euro_pair("France","Italy").
euro_pair("Germany","Spain").
euro_pair("Germany","Italy").
euro_pair("Spain","Italy").
euro_pair("Russia","Finland").
euro_pair("Russia","Poland").
border("France","Germany").
border("France","Spain").
border("France","Italy").
border("Russia","Finland").
border("Russia","Poland").
border("Spain","Germany").
find_non_border_pair:-
* euro_pair(X,Y),
not(border(X,Y)),
not(border(Y,X)),
write("X=",X," Y=",Y),nl,
fail.
1. Как видно из программы наша цель find_non_border_pair означает, что мы хотим найти пары стран, не имеющих общей границы. В программе же представлены только сами пары стран и пары стран, имеющие общие границы.
Вместо того, чтобы выдавать на экран все пары стран с общими границами, а потом визуально искать все пары, не попавшие в этот список, лучше воспользоваться более простым и эффективным средством- предикатом not (отрицанием, то есть недостижением цели). Его пишут в программе как not, чтобы отличить его от логического оператора “”.
Если мы хотим вызывать цель многократно, то лучше использовать цель в форме правила, не содержащего в себе данных (нулевой арности) А само правило определить в разделе clauses.
Это полезно, когда для достижения цели надо доказать много разных подцелей, включающих в себе достаточно сложные операции. Это поможет упростить процедуру запросов. При этом такие правила можно создавать “в запас”, а потом их использовать в работе программы.
2.В случае цели без аргументов вне зависимости оттого будете вы использовать внутреннюю или внешнюю цель ответ вы получите только один:
X=Germany Y=Italy
1 Solution
Это объясняется тем, что к предикату find_non_border_pair не могут быть поставлены точки возврата, так как такое утверждение в программе только одно, других просто нет.
Чтобы получить все возможные ответы, надо в теле правила
find_non_border_pair поставить предикат fail,который заставит поставить точки отката у подцели правила euro_pair(X,Y) (cимвол *):
find_non-border_pair:-
*euro_pair(X,Y),
not(border(X,Y)),
not(border(Y,X)),
write(“X=”,X,” Y=”,Y),nl,
fail.
Предикат fail вызывает откат, ибо он всегда неуспешен.
3.Для внешней цели можно обойтись без предиката fail, но тогда в правило надо добавить аргументы find_non_border_pair(X,Y)и не забыть произвести изменения в разделе предикатов –find_non_border_pair(country,country)
4.Предикат not не допускает свободной переменной в подцели, так как для связывания свободной переменной подцель должна быть унифицирована с каким-то предложением и выполнена, то есть переменная должна быть означена до своего использования. Как видите, предикат not позволяет ввести в программу элементы логики.
Например,
Goal: not(border(“France”,”Germany”))
Ответ: False (France и Germany –соседи)
3.Синтаксис Пролога
3.1. Объекты данных
Рис.3.1. Классификация объектов данных
Атомы, переменные и числа в Прологе относятся к простым объектам.
Для представления объектов, имеющих несколько компонент (арность которых >0) используются структурированные объекты, которые представляются в виде деревьев.
Тип объекта распознается по его синтаксической форме.
АТОМ может быть символом (symbol) или строкой(string).
Символы:
1) цепочка букв, цифр и символа подчеркивания, начинающаяся со строчной буквы
(например,nil | x23 | x_y | ann)
2) специальные символы, кроме тех специальных символов, которые имеют в Прологе заранее определенный смысл(например, :-если - то )
::=, <--->, ... и т.д.
3) цепочки символов, заключенные в одинарные кавычки
‘Tom’ ‘Ann’ ‘X’.
Строка:
Выделяется двойными кавычками и может содержать любую комбинацию литер:
“New York”, ”We study Prolog”.
Так как symbol/string взаимозаменяемы, то их отличия несущественны.
ЧИСЛО - как обычно
ПЕРЕМЕННАЯ- цепочка, состоящая из букв, цифр, символов подчеркивания. Начинается с прописной буквы или символа подчеркивания
X Result List_student _x23
Лексической областью определения переменных является одно предложение, поэтому под переменными с одним и тем же именем в двух предложениях подразумеваются две различные переменные.
Если переменная используется в предложении только один раз, то для нее не обязательно использовать имя. В этом случае используют так называемую анонимную переменную, которая записывается как один символ подчеркивания. Каждый символ подчеркивания представляет новую анонимную переменную.
Если анонимная переменная появляется в цели, то ее значение не выводится при выдаче результата.
СТРУКТУРА-это объект, который состоит из несколькиx компонентов. Эти компоненты тоже могут быть структурами. Все структурированные объекты могут быть изображены в виде деревьев. Корнем дерева является функтор.
student(fio(“orlov”,”dmitriy”),address(“pskov”,”mira”,53))
Составной объект student имеет две части: объект fio(“orlov”,”dvitriy”) и объект address(“pskov”,”mira”,53). Функторы у этих объектов – fio и address.
С точки зрения синтаксиса все объекты данных представляют собой термы.
Простой объект представляет сам себя, а структура, состоящая из простых объектов, называется простой структурой.
Аргументы составного объекта данных могут быть сами составными объектами.
student
/ \
name address
/ \ / | \
first last city street housenumb
3.2.1. Составная структура
На Прологе это выглядит так:
student(name(“liz”,”petrova”),address(“moscow”,”lefortov”,23))
student – главный функтор;
name, address- функторы
Функтор – это имя (не функция), которое идентифицирует сложную структуру объекта данных и связывает его аргументы вместе. Аргументы в свою очередь могут быть составными. Функтор помогает распознавать различия в объектах (один объект - это имя, другой объект- это адрес). Пролог позволяет объявлять составные объекты в разделе domains:
domains
stud_name=name(symbol,symbol)
stud_addr=address(symbol,symbol,integer)
predicates
student(stud_name,stud_addr)
clauses
student(name(“liz”,”petrov”),address(“Moscow”,”lefortov”,23)).
Имена доменов stud_name и stud_addr – это имена составных объектов, образованных при помощи функторов name и address.Таким образом, составной объект является определенной структурой доменов. Каждая структура предполагает особое представление фактов в базе данных (БД).
Структура обеспечивает средство сортировки объектов по категориям. Ссылки на доменную структуру осуществляются по имени функтора.
Пролог позволяет конструировать составные объекты с несколькими уровнями.
domains
personal_library = book(title, author, publisher, year)
collector, title, author, publisher=symbol
year=integer
predicates
collection(collector, personal_library)
clauses
collection(ivanov,book(“Artificial intelligence”,”Patrick Winston”,”Addison-Wesley Publishing company”,2005)).
сollection(petrov, book(“Artificial intelligence”, ”Stuart Rassel”, ”Pretice Hall”,2007)).
.................................................
и т.д.
3.2.2.Доменная структурная диаграмма программы “Библиотека” (ДСД)
personal_lilrary домен
|
book функтор структуры 0-уровень
__________|_______________ |
| | | |
title author publisher year уровень1
3.2.3.Предикатная структурная диаграмма программы “Библиотека” (ПСД)
collecton -предикат 0-уровень
____|________
| |
collector book -функтор уровень1
____________|_________________
| | | |
title author publisher year -уровень2
ДСД является компонентой ПСД.
Диаграммы показывают, как организованы домены и предикаты.
Все компоненты структуры и их уровни здесь видны очень ясно. Верхние уровни определяют общие черты структуры, нижние уровни отображают детали. Используются при разработке и документировании программ и проектов наряду с диаграммами потоков данных и структурными схемами.
Важная особенность составных объектов состоит в том, что они позволяют передавать группы величин как один аргумент. Мы можем иметь одну переменную для хранения целой группы величин. И это достигается благодаря использованию составного объекта.
3.2.4. Альтернативные домены
Представление данных часто требует наличия большого числа структур, эти структуры должны быть описаны. Поэтому предлагается альтернативное описание доменов. Для разделения доменов используют знак “;”.
Листинг 3.2. Использование альтернативных доменов
domains
row,column,step=integer
movement=up(step);
down(step);
left(step);
right(step)
predicates
move_cursor(row,column,movement)
clauses
move_cursor(R,C,up(Step)):-
cursor(R,C),
R1=R-Step,
cursor(R1,C),
write("movement_up\n").
move_cursor(R,C,down(Step)):-
cursor(R,C),
R1=R+Step,
cursor(R1,C),
write("movement_down\n").
move_cursor(R,C,left(Step)):-
cursor(R,C),
C1=C-Step,
cursor(R,C1),
write("movement_feft\n").
move_cursor(R,C,right(Step)):-
cursor(R,C),
C1=C+Step,
cursor(R,C1),
write("movement_right\n").
Альтернативный домен позволяет использовать предикат movevent применительно к различным классам движения курсора. Термы up, down, left, right являются именами структур. Однако,при появлении в предикатном выражении одновременно играют роль имен функторов, то есть Пролог не делает различий между функторами структур и доменными структурами. Если бы конструкция домена movement отсутствовала, то пришлось бы ввести 4 предиката.
Здесь использован стандартный предикат
cursor(Row,Column) (integer,integer) (вх, вх) ,(вых, вых):
- помещает курсор в позицию с координатами (Row,Column) (вх, вх);
- присваивает переменной Row и Column значения текущих координат курсора(вых, вых).
- Типы объектов данных могут быть простыми и составными. Простой объект – это константа или переменная.
- Составной объект данных позволяет рассматривать несколько частей информации как единое целое. В этом случае функтор используется для различения объектов. Функтор – это имя, а не функция. Функтор определяет вид составных объектов данных и объединяет вместе их аргументы.
- Домен можно определить как несколько альтернативных функторов (альтернативный домен).
- использование составных объектов позволяет упростить написание предикатов.
-использование альтернативных доменов позволяет сократить количество используемых предикатов.
Начнем с рассмотрения алгоритма унификации, который составляет основу вычислительной модели логических программ (реализует механизм упрощения).
Можно рассматривать каждое утверждение программы как структуру того или иного вида:
parent(bob,tom) – это структура, и тогда
parent- функтор структуры; bob, tom-компоненты структуры.
Компоненты структуры заключаются в круглые скобки;
разделяются между собой запятыми;
между функтором и левой скобкой нет пробела;
количество компонент структуры определяет ее размерность(арность –arity)
Факты, правила, заголовки правил, цели – все они по синтаксису языка являются просто структурами:
они имеют один и тот же главный функтор;
одинаковую размерность;
компоненты на одинаковых позициях обеих структур сопоставимы
обе являются константами и представляют собой одинаковый объект;
одна из них переменная;
обе являются структурами, и эти структуры сопоставимы.
СОПОСТАВЛЕНИЕ- это процесс, на вход которого подаются два терма, и идет проверка соответствия этих термов друг другу. Если термы не сопоставимы, то процесс заканчивается неудачей. Если термы сопоставимы, то процесс заканчивается успешно и в обоих термах происходит конкретизация переменных такими значениями, что оба терма становятся тождественными. Например,
dата(D, C, 2012)
| | |
data(D1, october, Y1)
Одна из конкретизаций, которая делает эти термы идентичными:
D=D1 C=october Y1=2012
Нашли конкретизацию переменных, делающих эти
термы тождественными, и процесс завершился успешно.
3.4.Унификация и ПОДСТАНОВКИ (Unify).
ОТКАТ (ПОИСК С ВОЗВРАТОМ)( BACKTRACKING)
На программу можно взглянуть с логической точки зрения или с процедурной точки зрения.
Цель используется для запуска процесса выполнения программы. Можно рассматривать цель как вызов процедуры. Чтобы цель была доказана, надо, чтобы вызываемая ею процедура была успешно выполнена. Обычно аргументы вызова процедуры – выражения, которые подставляются вместо формальных параметров, являющихся именами переменных. Но Пролог позволяет формальным параметрам самим быть термами. Поэтому процесс вызова “логической” процедуры включает совмещение термов, являющихся аргументами вызова, с термами из заголовков процедур. Этот процесс называется унификацией. Унификация является ключевым компонентом любых алгоритмов вывода в логике первого порядка.
Унификацией называется процесс нахождения наиболее общей подстановки, делающей два терма одинаковыми.
Если унификация оканчивается неудачно из-за того, что никакая подстановка не смогла совместить аргументы вызова и термы заголовков, то вызова не произойдет, но будет сделана попытка совмещения с другим определением процедуры, если оно есть. (Это называется “вызов с поиском по образцу”, или поиск с возвратом).
Можно сказать, что унификация – это взаимное приведение двух структур к общему виду. В результате унификации возникают связи переменных, делающих сравниваемые структуры идентичными. Унификация двух предикатов не обязана быть единственно возможной. В этом случае выбирается наиболее общая подстановка. Она то и называется унификацией. Применяя принцип резолюции для доказательства цели, мы неизменно используем алгоритм, который всегда приводит к наиболее общему унификатору(Most General Unifier –MGU-НОУ), или сообщает о невозможности это сделать, если множество – не унифицируемо, то есть если предикаты унифицируемы, то НОУ всегда существует и при этом только один! Если унификатора нет, то вывод невозможен. В процессе работы внутренних унификационных подпрограмм происходит означивание (связывание) переменных.
Замечания:
если оба значения в момент конкретизации известны, то знак равенства используется как оператор сравнения map=map, и в результате получаем успех, или неуспех, если map=lamp,например;
Если одно из значений является переменной,то знак равенства может быть как оператором присваивания, так и оператором сравнения.
Например, X=map.Если X была свободная переменная, то присваивание. Если X – означенная переменная, то знак равенства означает сравнение.
В процессе унификации мы находим нужную подстановку.
Подстановкой Q называется множество присваиваний вида X=t, где X-переменная, t-терм. Каждой переменной присваивается не более одного значения. Подстановка, которая привела к тому, что два предиката стали идентичными, называется унификатором.
Например, Unify(P1,P2)=Q, где P1 и P2-предикаты.
Если P1Q=P2Q, тогда Q – унификатор, а P1 и P2- стали идентичными.
Определим, какая подстановка приведет к тому, что предложенные ниже предикаты станут идентичными?
1 Р(1) и Р(1) ?
Q={}- ?
Q={}-пустое множество, так как нет замены переменных.
Общий пример Р(1)
2 Р(х) и Р(1) ?
Q={x:=1}
Общий пример Р(x)Q=P(1)Q=P(1)
3 P(x) и P(y)
Q={x:=y}
Общий пример P(y)
4 P(x,x) P(1,y)
x:=1 y:=x:=1
Q={x:=1,y:=1}
Общий пример P(1,1)
Алгоритм унификации основан на решении системы равенств. На вход подают два терма Т1 и Т2 Результат работы алгоритма – так называемый наиболее общий унификатор двух термов, если термы унифицируемы, или отказ, если они не унифицируемы.
Замечание1:
1) Унификация составных объектов:
с простой переменной - для передачи целого набора значений как единого объекта. Например:
name(“liz”,”petrova”) сопоставляется с X.
X=name(“liz”,”petrova”).
с составным объектом, который может содержать переменные в качестве частей внутренней структуры. В этом случае применение унификации используется для разделения составного объекта на части.
name(“liz”,”petrova”) сопоставляется с name(X,Y)
X=liz
Y=petrova
2) использование знака равенства для унификации составных объектов (а не только при сопоставлении цели с заголовком предложения) Фактически Пролог выполняет операции присваивания для унификации объектов по разные стороны знака равенства. Это свойство полезно для нахождения значений аргументов составного объекта.
Листинг 3.3.Использование знака равенства для унификации составных объектов
domains
person=person(name, address)
name=name(first, last)
address=addr(city,street))
street=street(number, street_name)
city, state, street_name=string
first, last=string
number=integer
goal
P1=person(name(jim,black),addr(pskov,street(25,mira)),
P1=person(name(_,black),Address),
P2=person(name(jane,black),Address),
write(“P1=”,P1,nl,
write(“P2=”,P2), nl.
Программа проверяет, совпадают ли фамилии у двух людей, и затем дает второму человеку тот же адрес, что и у первого. Знак равенства является инфиксным предикатом.
Замечание2:
Алгоритм унификации очень прост: он рекурсивно исследует два выражения одновременно, и в ходе этого исследования формирует унификатор, но может закончиться и неудачей, если структуры окажутся несопоставимыми. Но при этом есть один маленький нюанс: если переменная согласуется со сложным термом, необходимо произвести проверку того, встречается ли сама эта переменная внутри терма; если встречается, то согласование окончится неудачей, потому что будет невозможно сформировать какой-либо совместный унификатор. Эта операция носит название “проверка вхождения”(occur check). Но к сожалению именно из-за этой проверки сложность всего алгоритма становится квадратично зависимой от размера унифицируемых выражений. Все системы логического программирования просто исключают проверку вхождения и поэтому иногда могут сформироваться противоречивые логические выводы. Это случается крайне редко, но это означит, что унификация, проводимая в логическом программировании не является строго унификацией.
Как проходит процесс унификации?
- Пролог начинает поиск с начала программы.
- Если вызов завершился успешно, то делается попытка доказать следующую подцель.
- Если переменная была связана в предложении, то единственный способ сделать ее снова свободной - это откат.
ОТКАТ -автоматически исполняемый процесс. Это механизм, который используется для нахождения дополнительных фактов и правил, необходимых при вычислении цели, если текущая попытка вычислить цель оказалась неудачной. Пролог должен рассмотреть все возможные варианты нахождения решения и поэтому должен запомнить точки, в которых он может продолжить альтернативные попытки найти решение.
Это специальные указатели, определяющие точки, в которые может быть выполнен откат, если текущая попытка будет неудачной. Если некоторая подцель оказывается неуспешной, то Пролог откатывается влево и останавливается у ближайшего указателя отката. С этой точки Пролог начнет попытку найти другое решение для неуспешной цели.
3.5.Основные правила поиска с возвратом:
подцели проверяются по порядку – сверху вниз
предложения проверяются в том порядке, в котором они появляются в программе
если подцель сопоставляется с заголовком правила, то тело правила поставляет новые подцели, которые должны быть доказаны
цель доказана, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.
Вызов, который дает множество решений –недетерминированный
Вызов, дающий одно и только одно решение –детерминированный.
predicates
likes(symbol, symbol)
tastes(symbol, symbol)
food(symbol)
clauses
likes(bill, X):-
food(X),
tastes(X, good).
tastes(pizza, good).
tastes(Brussels_sprouts, bad).
food(Brussels_sprouts).
food(pizza).
Поставим цель goal:likes(bill, What).
Таблица 3.1. Ручная трассировка программы
|
Стек активных целей |
Предложения программы |
Означивания переменных |
|
? likes(bill,What) |
likes(bill,X):- food(X), tastes(X,good). likes(bill,What):- food(What), tastes(What,good) |
X=What X и What становятся одной и той же неконкре-тизированной переменной |
|
? food(What) |
*food(brussels_sprouts). food(pizza). |
What= brussels_ sprouts |
|
? tastes(brussel_sprouts,good) |
tastes(pizza,good). tastes(brus_sp,bad). |
Отказ. Запускаем механизм возврата и ищем другое ре- шение W –освобождается, |
|
? food(What) |
food(pizza). |
What=pizza |
|
? tastes(pizza,good) |
tastes(pizza,good). |
Это факт. Согласование получено.Успех What=pizza 1Solution |
Рис.3.2 .Иллюстрация прохождения процесса унификации и конкретизации переменных
4.ПРИНЦИП РЕЗОЛЮЦИИ
В ЛП все решаемые задачи могут быть представлены в виде теорем, которые должны быть доказаны в рамках исчисления предикатов первого порядка. Робинсон предложил удачный метод работы с предложениями. Этот метод легко реализуется на ЭВМ. В основе предложения Робинсона лежит принцип резолюции и основанные на нем методы доказательства теорем. Принцип резолюции – это метод вывода, который является непротиворечивым и полным. Это значит, что этим методом можно доказать лишь справедливые теоремы, причем если теорема справедлива, то она доказывается за конечное число шагов. Мы считаем множество S (наши утверждения) – внутренне непротиворечивыми. Непротиворечивость множества S будет гарантирована всякий раз, когда это множество содержит только правила и/или факты – а именно так обстоит дело в стандартном логическом программировании.
Основная стратегия доказательства заключается в том, чтобы показать несправедливость (противоречие) противоположной теоремы, а не пытаться непосредственно вывести исходную теорему (доказательство от противного - reductio absurdum)
У нас есть программа:
S1={F,…..,Fn} – множество формул в разделе утверждений (clauses).
F - цель (goal)
Формула F логически следует из S1 ,если при каждой интерпретации, когда все F -истинны (то есть истинна их конъюнкция) истинной является и F. Иначе, каждая интерпретация, удовлетворяющая S1, удовлетворяет и F.
С точки зрения Пролога это означает, что формула, которую нужно доказать в прикладном исчислении предикатов первого порядка, должна логически следовать из множества формул, составляющих программу. Иначе программа будет работать неправильно, или приведет к неправильному результату.
Для того чтобы доказать, что Fn+1 логически следует из S1, можно доказать, что множество
S2=S1{F} является противоречивым, то есть
не существует интерпретации, в которой оно бы удовлетворялось.
В логике есть два классических правила вывода, открытых очень давно. Это – модус поненс и цепное заключение.
1.Modus Ponens -правило сокращения посылки путем применения импликации (отношение если….то) Если истинно А и истинно А--à(влечет)В, то можно вывести В(но не наоборот). То есть из двух данных предложений можно вывести третье(B).Корректность правила очевидна. Она получается из определения операции ВЛЕЧЕТ. Правило применимо к любой формуле.
( A
A-àB
B)
(“А влечет В” или “если А ,то В”) Рассуждения уместны только в одном направлении: зная А можно получить В, но не наоборот).Утверждение “если А, то В” будет правильным независимо от того, истинно В или ложно.
2.Цепное правило – позволяет вывести новую импликацию из двух данных импликаций.
Если истинно А-àВ и истинно В-àС, то можно вывести А-àС.Корректность очевидна: если истинность А влечет истинность В, и истинность В влечет истинность С, то истинность А влечет истинность С.
Из А àВ
В àС
Получаем АàС
Проблема доказательства в логике состоит в нахождении доказательства заключения на основании посылок.
Это можно сделать либо табличным способом с помощью построения таблиц истинности (алгебра логики), либо с помощью применения правил вывода.
вило вывода новой логической формулы из двух посылок (похоже на решение системы уравнений. Предполагается, что уравнение истинно при некоторых значениях неизвестных, и делаются подстановки, сохраняющие эту истинность и дающие новые уравнения).
Метод резолюции является более общим по отношению к модус поненс и цепному правилу. Модус поненс является частным случаем правила резолюции для случая ложного А. Правило резолюции можно рассматривать как аналог цепного правила в применении к формулам, находящимся в конъюнктивной нормальной форме. (Любое выражение в ИП1П можно привести к КНФ - по сути похоже на упрощение алгебраических выражений).
Резолюция – это метод доказательства того, что ложное высказывание – ложно, а не того, что истинное высказывание - истинно. Необходимо понимать, что такое логическое следствие и логический вывод.
Предложения программы сами по себе не являются true или false .Значения true или false для предложения определяются их конкретной интерпретацией. Решая задачу мы всегда выбираем определенную область интерпретации (предметную область), которая представляет собой произвольное множество объектов (D).{На основе теоретико-множественной модели}. Эти объекты сопоставляются именам, входящим в наши предложения (S1).
Наши предложения (S1) Область интерпретации(D)
сonst -------------------------------объект
функтор -------------------------------функция
предикат -------------------------------отношение
{true,false}
Используем интерпретацию множества предложений S1 для оценки каждого предложения из S1 с помощью истинностных значений true и false.
Каждое предложение из S1 будет принимать в данной интерпретации true или false. Сказать, что некоторое предложение из S1 истинно или ложно относительно выбранной интерпретации, значит сказать, что истинно или ложно соответствующее высказывание о D.
Таким образом, посредством установления связи с внешним миром объектов предложения S1 приобретают истинностно - функциональное значение.
4.1.ЛОГИЧЕСКОЕ СЛЕДСТВИЕ
Множество предложений S1 логически влечет некоторое предложение F тогда и только тогда, когда в каждой интерпретации над произвольной областью из выполнения в ней множества предложений S1 следует выполнение в ней предложения F (или F является логическим следствием множества предложений S1).
S1 |-- F -(логически следует)
Смысл отношения |-- заключается в том, что если
S1 |-- F (S влечет за собой F ) имеет место, то это происходит благодаря внутреннему устройству самих предложений, независимо от того, что могут означать составляющие их части в соответствии с той или иной интерпретацией. Использование интерпретации приписывающей значения – это всего лишь один из способов образования понятия логического следствия, которое в конечном счете от этих интерпретаций не зависит.
На практике не требуется исследовать различные области интерпретации для установления отношения S1|-- Fn+1 ,так как существуют более простые методы, основанные на логическом выводе. Наиболее простой метод для установления отношения логического следствия S1|--F основан на логическом выводе.
4.2. Логический вывод
- это процесс получения некоторого предложения Fn+1 ,исходя из множества предложений S1 путем применения одного или нескольких правил вывода.
Логический вывод -> Если A,то B.
Если известно, что A- истинно, то можно заключить, что B- истинно. Однако, если A-не истинно, то нельзя сделать никакого вывода о B.Утверждение “Если A,то B” будет правильно независимо от того, истинно В или ложно.
Единственный способ показать, что само утверждение о выводимости – ложно- это предъявить ситуацию, в которой известно, что В – ложно, хотя A –истинно.
Цель вывода: показать справедливость отношения
S1|-- Fn+1. В ЛП используется метод резолюции( одно правило вывода)Каждое применение правила называется шагом вывода. Будем применять метод резолюции (правило вывода) только к предложениям трех типов:
Отрицание : (A1,….,An)
Факт: А
Правило: A:- B1,….,Bm
(импликация)
где A1,….,An и B1,…..,Bm -произвольные предикаты.
Каждое предложение в логике предикатов первого порядка преобразуется в множество дизъюнктов (то есть объединение множеств). Предложения, являющиеся отрицаниями, фактами и правилами, образуют подкласс класса всех дизъюнктов и называются хорновскими дизъюнктами.
Введем наиболее простую форму резолюции
Пусть имеем:
1случай отрицание S1: A
импликация S2:A:-B
Здесь предикат А из S1 совпадает с заголовком A из S2
В результате первого шага резолютивного вывода получаем из S1 и S2 (родительские предложения) новое предложение s:
s:- B -резольвента, которая получилась в результате применения резолюции к S1 и S2.
Допуская, что не А и А, если В, выводим не В{modus tollens}.
2cлучай: отрицание S1: A
факт S2:A
Применяя к этим родительским предложениям правило резолюции, выводим в качестве резольвенты пустое отрицание (противоречие):
S: противоречие
Допуская, что не А и А , выводим противоречие
В ЛП вопрос, задаваемый системе, представляется в виде отрицания, и система должна опровергнуть это отрицание при помощи других предложений. Опровержение отрицания происходит путем демонстрации того, что его допущение ведет к противоречию (в математике – доказательство от противного). Резолюция, порождающая последовательность отрицаний, называется резолюцией сверху вниз.
1 шаг – формулировка задачи
2 шаг – запрос (цель)
3 шаг – выполняет ПК, который пытается решить поставленную задачу, строя доказательство от противного.
В теории резолюции есть важный результат:
Из S1 логически следует Fn+1 тогда и только тогда, когда из S1 и F можно вывести противоречие.
Вывод: построение логического вывода пустого отрицания при помощи правила резолюции означает, что из множества допущений S1 логически следует заключение F.Это заключение прямо отвечает на запрос, поставленный исходным отрицанием F и поэтому всегда является утверждением о решении задачи: так как исходное отрицание цели было опровергнуто, то цель – успешна.
Используя метод резолюции совместно с методом унификации можно выводить из имеющихся дизъюнктов все новые дизъюнкты – следствия.
Комбинация методов называется приведением к противоречию. Резолюция позволяет объединить две формулы, удалив из одной А, а из другой А.
4.3 Преимущества и недостатки метода резолюции
1. Надо знать и помнить всего одно правило.
2. Применение этого правила можно автоматизировать(запрограммировать на ПК).
3.Ответы можно извлекать из унификаторов.
Недостатки:
Не гарантируется конец работы (бесконечный цикл при попытке найти доказательство). Но это бывает очень редко, так как большинство реальных задач не содержат “неразрешимых ” формул.
Общий вывод:
1. Предложения Пролога можно интерпретировать как предложения исчисления предикатов первого порядка.
(фразы Хорна)
2. Компилятор Пролога можно рассматривать как резолюционную процедуру доказательства, использующую поиск в глубину (сверху - вниз и слева – направо)
3. Все вычислительные задачи можно сформулировать, пользуясь только отрицанием, правилами и фактами, а те из задач, которые являются разрешимыми, можно решить с помощью общей резолюции сверху вниз.
(неразрешимыми считаем те задачи, которые не имеют опровержения)
Дополнительная информация:
Резолюция обладает важными свойствами корректности и полноты.
Резолюция корректна в том смысле, что если с ее помощью из множества допущений S1 и отрицания F выводится противоречие, то обязательно справедливо отношение S1 |-- F.
Резолюция полна в том смысле, что если справедливо S1|-F,то противоречие непременно выводится из S1 и F.
Проблема общезначимости
Логика первого порядка только частично разрешима. Но есть алгоритмы, которые всегда устанавливают справедливость отношения S1|- F,если оно действительно имеет место. Это значит, что если составили неразрешимую логическую программу, то есть не имеющую опровержения и подали ее на вход частично разрешимой процедуры, основанной на резолюции и реализовали на ЭВМ ,то может произойти зацикливание.
Исследования подтвердили, что логика хорновских дизъюнктов является универсальным вычислительным формализмом. Ее проверили на множестве натуральных чисел, на частично рекурсивных функциях, на классе алгоритмов Маркова и тому подобное.
4.4. Пример применения метода резолюций.
Листинг 4.1. программа, иллюстрирующая применение метода резолюции
predicates
likes(symbol,symbol)
food(symbol,symbol)
clauses
S2 likes(bill,pizza):-
food(pizza,italiano).
S3 food(pizza,italiano).
S2 и S3 –родительские предложения
В качестве S1 будет выступать цель goal: likes(bill,pizza), которая поступит на компилятор в виде отрицания.
Опровержение отрицания демонстрируется так: допущение отрицания цели ведет к противоречию.
likes(bill,pizza) подаем на вход системы резолютивного вывода. Система должна опровергнуть это отрицание при помощи других предложений программы.
Рис. 4.1. Применение принципа резолюции
Для верхнего случая : S1:A.
S2:A:-B.
S:B
Для нижнего случая : S1:A
S2:A
S: противоречие
В данном примере оказалось достаточно двух шагов вывода. Если предположить, что мы не отказываемся от предложений S2 и S3, и сами они не являются противоречивыми, то отсюда следует, что они совместно противоречат S1, то есть подтверждают отрицание S1, а следовательно, ответ –ДА.
В общем виде:
S1:(A1,..,An)
S2: Aк:-B1,..,Bm где 1<=к<=n
Некий предикат Ak из отрицания S1 совпадает с головой правила S2.В этой ситуации шаг вывода заменяет Ak в S1 на подцель из S2, и в качестве резольвенты получаем s:(A1,..,Ak-1,B1,..,Bm,Ak+1,..,An).
Если на запрос можно получить ответ на основе знаний, закодированных во входных допущениях, то система обязательно его получит. Ответственность за построение вывода, за управление протоколом связываний и извлечения ответа может быть полностью возложено на систему.
Каждое вычисленное решение обладает требуемым свойством – оно логически следует из данных допущений. Очень немногие из формальных систем программирования обладают этими качествами.
5. Управление поиском решений
Управление выполнением программы – это отход от декларативности в сторону процедурных свойств, что может возникнуть, например, при необходимости выполнения циклов. Пролог одинаково хорошо выполняет повторы и в процедурах, и в структурах данных.
Было показано, что можно управлять выполнением программы, изменяя порядок следования предложений и целей. Это изменение могло повлиять на эффективность программы и в некоторых ситуациях могло привести к бесконечным рекурсивным вызовам. Это было показано и в программе о нахождении отдаленных предков, и в программе о нахождении стран, не имеющих общих границ.
Кроме переупорядочивания предложений существуют другие методы управления программой.
Система Пролог использует поиск с возвратом (откат), который выполняется автоматически для поиска решения программы, но это может привести к поиску заведомо ненужных решений, то есть снизить эффективность работы программы.
Иногда наоборот необходимо найти не одно решение, а много (несколько) решений.
Управление поиском решения можно рассматривать с процедурной точки зрения.
Тогда можно сказать, что циклические части программы записываются на Прологе либо в виде правил, которые используют откат, либо в виде правил, которые используют рекурсию.
Используя откат или рекурсию при решении задачи, можно получить один и тот же результат, хотя алгоритмы их выполнения различны. Конкретная ситуация диктует тот или иной выбор реализации циклических частей программы. Рисунок 5.1. демонстрирует оба способа реализации циклических частей программы и средства, которые используются в случае отката для управления логическим поиском.
Рис. 5.1.Два способа управления поиском решения
Есть несколько способов реализации повторов в Прологе. Наиболее удобными считаются два способа - откат после неудачи и отсечение и откат.
5.1.Метод отката после неудачи – ОПН
Использование предиката fail
Листинг 5.1.Программа, использующая ОПН
domains
name=symbol
predicates
country(name)
print_countries
clauses
country(england).
country(france).
country(germany).
country(denmark).
print_countries:-
country(X),
write(X),
nl,
fail.
print_countries.
Пояснения к программе:
Поставим перед программой две разные цели:
1)country(X);
2)print_countries.
Как поведет себя каждая из этих целей, если мы сделаем ее сначала внешней, а потом внутренней?
Внешняя цель
Для country(X) c fail и без fail внешняя цель даст одинаковый ответ – все 4 решения. Fail для внешней цели в этом случае просто избыточна, потому что внешняя цель заставит ее получить все ответы и без fail.
Для print_countries внешняя цель без fail даст одно решение- england- , потому что откат для получения других решений просто некуда выполнить. В разделе clauses нет больше предиката с таким именем (print_countries). Без fail у нас нет повода обратиться к country , даже если цель внешняя.
Для print_countries внешняя цель с fail даст все 4 решения. Print_countries использует поиск с возвратом с тем, чтобы получить все решения для country, заставляя Пролог выполнять поиск с возвратом через правило print_countries. При этом Пролог возвратится к той подцели в правиле, которая может дать множественные решения, то есть к недетерминированной подцели. Предикаты nl и write не могут быть согласованы повторно, так как они не в состоянии дать нам новые решения, поэтому Пролог вынужден откатиться к предыдущей подцели, то есть к country.
Внутренняя цель
Для цели country(X) с fail и без fail результат одинаков – ответ будет один. Это происходит потому, что fail стоит в правиле print_countries,а в country fail не задействован.
Для цели print_countries c fail мы получим все 4 ответа, а без fail –один ответ.
Замечание :
Помещать подцель после fail в теле правила бесполезно, так как fail – всегда неудача, а значит, нет возможности для достижения подцели, расположенной после fail.
Вывод
Метод ОПН - откат после неудачи –позволяет управлять вычислением цели при поиске всех возможных ее решений. Для этого используется встроенный предикат fail.
5.2 Метод отсечения и отката – ОО
Использование предиката cut
В случае, когда надо иметь доступ только к определенной части данных, Пролог использует встроенный предикат cut (!)-отсечение.
Его вычисление всегда успешно. Этот предикат заставляет внутренние унификационные подпрограммы убрать все указатели отката, установленные во время попытки вычислить текущую подцель – то есть он прерывает поиск с возвратом. Через cut невозможно вернуться (совершить откат). Отсечение обычно помещается в теле правила.
Однажды выполнив отсечение, невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением и невозможно возвратиться к другим предложениям в предикате, содержащим отсечение, то есть к предложениям, стоящим после предложения с отсечением.
Пусть cut является одной из подцелей составной цели.
После того как компилятор пройдет предикат cut, он больше не сможет вернуться назад к подцелям, стоящим перед этим предикатом. И все значения переменных, расположенных слева от предиката cut, которые они получили в процессе унификации будут заморожены.
Пример:
При выполнении этой цели компилятор пройдет через предикат cut только в том случае, если и подцель a(X), и подцель b(Y) окажутся уже успешными.
После того как предикат cut окажется обработан, компилятор не сможет вернуться назад для повторного рассмотрения подцелей “a” и “b”, если подцель”c” потерпит неудачу при текущем значении переменных X и Y.
Эта составная цель не обладает декларативным смыслом. Но с процедурной точки зрения ее можно прочесть так:
взять значение переменной X из подцели “a” и значение переменной Y из подцели “b” а затем выполнить подцель c(X,Y,Z).
5.2.2.Влияние предиката cut на процедуру
predicates
a(symbol)
d(symbol)
clauses
a(“1”):-
write(“один”).
a(X):-
d(X),
write(“два”).
a(“3”):-
write(“три”).
d(“2a”).
d(“2b”).
Возьмем цель goal: a(N).
В соответствии с представленной схемой получаем все четыре решения:
1) один, N=1;
2) два, N=2a;
3) два, N=2b;
4) три,N=3.
Изменим программу, вставим предикат cut между двумя подцелями правила a(X) и проанализируем, что произойдет в результате выполнения программы, которая будет запущена той же самой целью goal:a{N).
Листинг 5.3.Программа с предикатом cut
predicates
a(symbol)
d(symbol)
clauses
a(“1”):-
write(“один”).
a(X):-
d(X),
!,
write(“два”).
a(“3”):-
write(“три”).
d(“2a”).
d(“2b”).
В результате получим только два ответа:
1) один, N=1;
2) два, N=2.
3) система ‘заморозила’ все альтернативы, стоящие до cut,и лишила тем самым возможности вернуться к подцели d(X),чтобы воспользоваться веткой d(“2b”).
4) отбросила все утверждения процедуры a , стоящие после утверждения с предикатом cut.(то есть перейти к утверждению a(“3”) –невозможно)
Использование предиката cut позволило отбросить части пространства поиска.
Рассмотрим еще один пример.
Листинг 5.4.Программа, использующая cut для того, чтобы сделать процедуру детерминированной
predicates
x(integer)
clauses
x(1):-
!,
write(“a, b, c”),nl.
x(2):-
!,
write(“c”),nl.
x(_):-
Write(“ изучаем предикат cut.”).
Предикат сut позволяет сделать процедуру детерминированной.
Предикат cut предотвращает поиск с возвратом к следующим предложениям. Это отменяет точки отката, увеличивая эффективность выполнения программы. Конструкция очень похожа на switch(case).Для каждой цели существует своя веточка, которая единственная и будет работать при совпадении цели с головой именно этой веточки.
Обратите внимание: условие проверки записывается в заголовке правила(x(1), x(2) и так далее, а не в теле: x(Y):- Y=1,!,a, b, c.)- это увеличивает эффективность работы программы и упрощает чтение.
5.2.3. Использование зеленых и красных отсечений
Отсечения бывают зеленые и красные.
Листинг 5.5. Использования зеленого отсечения в
задаче нахождения минимума двух чисел
predicates
minimum(real,real,real)
clauses
minimum(X,Y,X):-
X<=Y, !.
minimum(X,Y,Y):-
X >Y,!.
goal: minimum(3,5,Min)
Min=3
goal: minimum(6,5,Min)
Min=5
-При выполнении одной арифметической проверки оказывается невозможным выполнение другой проверки. Отсечение, содержащееся в этой программе, отображает детерминированный характер ее. Это значит, что для каждой доказуемой цели к ее доказательству ведет применение лишь одного правила программы. Отсечение фиксирует выбор такого правила.
-Отбрасывает часть пространства поиска. Сведения, зафиксированные при отсечении, используются для сокращения дерева поиска, что уменьшает выполняемый путь обхода дерева и экономит время выполнения программы а также уменьшает объем используемой памяти.
Здесь имели место зеленые отсечения, то есть такие, добавление которых в программу не влияло на декларативный ее характер (Можно найти все решения, убирая заведомо лишние части дерева, которые все равно бы не привели к новым решениям. Удаление зеленого отсечения также не влияет на решения программы)
Замечание: программы с отсечением менее гибкие, чем без отсечения. Но если предполагается использовать программу только одним способом, то это не существенно.
Листинг 5.6. Использования красного отсечения
predicates
minimum(real,real,real)
clauses
minimum(X,Y,X):- X<=Y,!.
minimum(X,Y,Y).
Если X<=Y, то минимум X. В противном случае минимум равен Y.Вроде бы сравнения X и Y – излишни. Однако в приведенной ранее программе такое сравнение выполняется, и это – правильно. Здесь мы это сравнение из программы убрали. Поставим цель minimum(3,7,7) Ответ:yes, что неверно. То есть программа получилась логически ложной. Можно попытаться избавиться от ложных целей, сделав неявную унификацию явной:
minimum(X,Y,Z):- X<=Y,!,Z=X.
Но снова получаем логическую программу, которая может быть неверной как раз с точки зрения логики. Если аргументам X и Y –сопоставили значения, а Z-осталась свободной, то программа будет работать правильно. Если Z – связана, то может быть ошибка. Например, goal: minimum(8,9,7) –no.
Если применяем зеленые отсечения, то отбрасываем заведомо бесполезные ветви в дереве поиска.
Красные отсечения используются для устранения явных условий (заведомо выполнимых). Это иногда
полезно, но опасно. Использование красных отсечений для устранения явных условий позволяет задавать отрицания неявно. Требуют от программиста максимального внимания.
Отсечение cut –мощный, но опасный оператор Пролога. Он многое позволяет, но за это приходится платить - программа становится трудной для понимания и легко сделать ошибку.
Выводы
Определение: После унификации порождающей цели с заголовком предложения, содержащего отсечение, цель выполняется и фиксируется для всех выборов предложений.
Следствия: -
- отсечение отбрасывает все расположенные после него предложения. Если цель Р унифицирована с предложением, содержащим отсечение, и отсечение выполнено, то эта цель не может быть использована для построения решений с помощью предложений, расположенных ниже данного;
- отсечение отбрасывает все альтернативные решения конъюнкции целей, расположенных в предложении левее отсечений, то есть конъюнкция целей, стоящих перед отсечением, приводит не более чем к одному решению;
- отсечение не влияет на цели ,расположенные правее его. В случае возврата они могут порождать более одного решения. Однако если эта конъюнкция не выполнится, то поиск переходит к последнему выбору, сделанному перед выбором предложения, содержащего отсечение.
5.2.4.Использование предиката not как средства управления
Предикат not использовался ранее, добавим несколько замечаний.
Умея теперь использовать предикаты fail и cut
можно написать:
not(P):-
P,
!,
fail;
true.
Иначе это можно записать так:
not(P):-P, !, fail.
not(P).
Здесь требуется именно такой порядок правил. Процедуры, в которых порядок правил может изменить значение программы, следует рассматривать как единый объект, а не как набор отдельных предложений. Отношение not здесь отличается от строгого логического отрицания. Оно трактуется как отсутствие. В дереве поиска должны отсутствовать успешные вершины, но не должно существовать бесконечных ветвей.
Предполагается, что not –встроенная процедура.
Информация о фактах, которые не являются истинными и об отношениях, которые не соблюдаются, называется отрицательной информацией. В явной форме такая информация в программе не хранится. Просто считается, что вся информация, отсутствующая в программе, ложна.
Правило повтора имеет вид:
repeat.
repeat:-repeat.
Правило, которое использует само себя как компоненту (третий repeat). Второй repeat вызывает третий repeat, и этот вызов всегда успешен, так как первый repeat удовлетворяет подцели repeat, следовательно, правило repeat также всегда успешно.
Предикат repeat будет вычисляться успешно при каждой новой попытке его вызвать после отката.Repeat используется в качестве компоненты других правил.
Листинг 5.7. Использование repeat для ввода и вывода на экран символов до тех пор пока не будет нажата клавиша ‘Enter’.(ASCII-код =13)
predicates
repeat
typewriter
clauses
repeat.
repeat:-
repeat.
typewriter:-
repeat,
write(“ input char”),nl,
readchar(Ch),
write(Ch),nl,
char_int(Ch,13),
write(“end”).
goal:typewriter,nl.
Встроенный предикат readсhar(Ch) читает новое значение, вводимое с клавиатуры только при первом вызове предиката и не делает этого при возврате (то есть если использовать здесь предикат fail, то повтора чтения не произойдет):
typewriter:-
readchar(Ch),
write(Ch),
fail.
Встроенный предикат repeat позволяет преодолеть эту трудность. Однако даже repeat при наличии fail не приведет к завершению программы, потому что комбинация repeat…..fail приводит к бесконечному циклу:
typewriter:-
repeat,
readchar(Ch),
write(ch),
fail.
Как выйти из комбинации repeat…fail? Очевидно, необходимо ввести индикатор завершения программы и заменить им предикат fail. Таким индикатором в нашей ситуации является нажатие на клавишу ‘Enter’.Для этого можно использовать стандартный предикат char_int(CharParam,IntParam), который успешен, если код символа CharParam совпадает со значением IntParam.
Листинг 5.8.Использование метода повтора для ввода двух новых чисел и получения их суммы.
predicates
sum(integer,integer,integer)
repeat
summa
check(integer,integer)
write_message
goal
clearwindow,
write_message,
summa.
clauses
repeat.
repeat:-
repeat.
write_message:-
nl,write(”input 2 integer number”),nl,
write(“for stop input 0 for X or Y”),nl,nl.
summa:-
repeat,
write(“input X=”),
readint(X),nl,
write(“input Y=”),
readint(Y),nl,
write(“X=”,X,” Y=”,Y),nl,
check(X,Y),!.
check(X,0):-
nl,write(“OK”).
check(Y,0):-
nl,write(“OK”).
check(X,Y):-
sum(X,Y,Z),
write(“ Z=”,Z),nl,
write(“input new integer”),nl,
write(“ numbers for X and for Y”),nl,
fail.
sum(X,Y,Z:-
Z=X+Y.
В данной программе для останова процесса сложения вместо одного из двух чисел(или вместо и того и другого) вводится 0.
Следует помнить, что:
-предикаты read и write читают и печатают свои значения только при первом вызове, поэтому fail здесь не поможет, а repeat будет на месте;
- правило repeat дает бесконечные циклы, поэтому нужен признак конца;
- все переменные теряют свои значения при откате обработки в позицию, предшествующую тем вызовам предиката, который эти значения устанавливал.
Замечания.
Если необходимо бесконечное выполнение, и окончание наступает только при возникновении каких- то исключительных ситуаций, то в не интерактивных программах можно использовать предикат exit, прекращающий выполнение программы. В интерактивных программах можно нажать клавишу <Break>.
Так как ни write(), ни readchar() не являются альтернативными, то возврат происходит к repeat,который всегда имеет альтернативные решения.
Обратите внимание на то, что Ch теряет свое значение после отката в позицию перед вызовом предиката readchar(Ch), который связывает переменную Ch.Такой тип освобождения переменной важен, когда поиск с возвратом применяется для определения альтернативных решений, но он не эффективен при использовании поиска с возвратом в других целях. Суть в том, что хотя поиск с возвратом и может повторять операции сколько угодно раз, но он не способен “запомнить” что-либо из одного повторения для другого. Поэтому write() надо сделать перед повтором, так как вы теряете при откате значение переменной.
Правило repeat позволяет получить бесконечные откаты. В МП откат может быть выполнен всегда в отличии от метода ОО, где откат выполняется только после искусственно созданного неуспешного результата. Но не следует забывать о необходимости введения признака завершения повторов.
Выводы
Предикат fail вызывает неуспшное завершение правила, заставляя внутренние унификационные программы выполнять откат, а процесс повторяться до тех пор, пока не будет обработано последнее утверждение.
Оператор отсечения cut предотвращает перебор с возвратами, не давая проверять альтернативные цели, если заранее известно, что они все равно окончатся неудачей.
Оператор отсечения позволяет сформулировать взаимоисключающие утверждения с помощью правил вида: если Условие, то Заключение 1,иначе Заключение 2.
Оператор отсечения позволяет сделать процедуру детерминированной.
Оператор отсечения может нарушить соответствие между декларативным и процедурным значениями программы, поэтому надо быть предельно осторожным при его использовании.
Оператор not как недостижение цели не полностью соответствует понятию отрицания в математике, поэтому и при работе с ним также требуется определенная осторожность.
Правило повтора repeat успешно при каждой новой попытке вызвать его после отката.
Эффективен при реализации доступа к данным в базе данных и файлах на диске. Используется для формирования меню и выдачи его на экран.
5.4.Методы организации рекурсии
Другим способом реализации циклических частей программы является использование рекурсии(смотри рис.5.1.)Понятие рекурсии введено в разделе “Основы логического программирования” и использовалось в решении задачи о родственных отношениях. Ее особенность заключается в том, что вычисленные с помощью рекурсии значения передаются из одного вызова в другой как аргументы рекурсивно вызываемого предиката.
Там же были даны определения рекурсии и рекурсивности.
Когда и где применяется рекурсия?
Рекурсия применяется:
-Для решения задач, содержащих в себе подзадачи такого же типа (поиск в дереве, рекурсивная обработка (например, сортировка списков);
-работа с базами данных (БД);
-обработка файлов;
-встречаются задачи, не имеющие нерекурсивного алгоритма решения;
- в математических вычислениях.
Рекурсивные программы дают компактное и элегантное описание интересующих нас отношений, но есть один минус - во время счета образуется все увеличивающийся в размерах стек вызовов, для хранения которых может потребоваться слишком большой объем памяти.
Однако, существует класс рекурсивных программ, которые выполняются с использованием постоянного объема памяти. Это такие рекурсивные программы, которые могут быть преобразованы непосредственно в итерационные программы. Метод реализации таких программ называется оптимизацией хвостовой рекурсии (tail recursion optimization) (оптимизацией последнего обращения). Основная идея метода: рекурсивная программа выполняется так, как если бы она была итерационной. Когда процедура может вызвать себя без сохранения информации о своем состоянии? Это возможно в том случае, если процедура не генерирует указателей отката и последней подцелью ее является рекурсивный вызов самой себя. В этом случае информация о состоянии процедуры больше не понадобится. Получается, что когда процедура на последнем шаге вызывает саму себя, то стек для вызывающей процедуры должен быть заменен на стек для вызванной процедуры. То есть происходит при замене стека очень простая операция – аргументам процедуры присваиваются новые значения, после чего выполнение процесса возвращается на начало процедуры. Поэтому с процедурной точки зрения происходящее очень похоже на итерацию (обновление управляющих переменных в цикле).
На Прологе можно задать хвостовую рекурсию следующим образом:
- рекурсивный вызов является самой последней подцелью последнего предложения в процедуре.
- ранее в предложении не было точек возврата (если они есть, то от них можно избавиться с помощью отсечения, которое ставится непосредственно перед рекурсивным вызовом и помогает убрать все лишние альтернативы)
Замечание: В общем случае невозможно определить, является ли подобное отсечение зеленым или красным, поэтому надо предварительно тщательно исследовать этот вопрос.
Пролог автоматически отслеживает хвостовую рекурсию и устраняет дополнительные расходы, которые вызывает рекурсия. Этот процесс называется устранением хвостовой рекурсии.
Замечание:
-рекурсия логически проще метода итерации;
-при работе с рекурсивными правилами обязательны условия выхода из рекурсии, иначе рекурсия будет бесконечной и правила бесполезными. Ответственность за выход из рекурсии лежит на программисте. Это рассмотрено в задаче о дереве родственных отношений.
predicates
count(real)
clauses
count(N):-
write(N),nl,
NewN=N+1,
count(NewN).
Эта процедура count(N) –является хвостовой рекурсией, которая вызывает себя без резервирования нового стекового фрейма, и потому не истощает запас памяти, в конечном итоге произойдет целочисленное переполнение, но остановки из-за нехватки памяти не будет.
Введение условия, ограничивающего бесконечную рекурсию:
Листинг 5.10.Ограничение бесконечной рекурсии
predicates
count(integer)
check(integerl)
clauses
count(N):-
write(N),nl,
NewN=N+1,
сheck(NewN),
count(NewN).
check(Z):-Z<5.
goal
clearwindow,
write(“result:”),nl,
count(1).
Замечание:
В Прологе мы не можем изменить значение переменной, поэтому создаем новую переменную NewN.
Добавим еще одно предложение после рекурсивного вызова
Листинг 5.11.Пример не хвостовой рекурсии из-за того, что вызов процедуры – не последний шаг
predicates
count(integer)
check(integerl)
clauses
count(N):-
write(N),
NewN=N+1,
сheck(NewN),
count(NewN),
nl.
check(Z):-
Z<5.
Из-за наличия nl вызов процедуры count() перестал быть последним шагом, стек придется сохранить, чтобы обработку можно было вернуть к вызывающей процедуре.
Еще один случай не хвостовой рекурсии:
Листинг 5.12.Пример не хвостовой рекурсии за счет использования недетерминированного предиката
check_determ
predicates
count(integer)
check(integer)
clauses
count(N):-
write(N),nl,
NewN=N+1,
сheck(NewN),
count(NewN).
count(N).
check(Z):-Z<5.
Добавили второй count(N). Получили недетерминированный предикат. Этот предикат еще не проверен к моменту выполнения рекурсивного вызова, поэтому стек должен быть сохранен, так как в случае неуспеха рекурсивного вызова процедура может откатиться и начать проверку этой альтернативы.
Замечания:
- Если проверку chеck(NewN) не поставить, то предыдущие программы будут работать до истощения памяти.
- Непроверенные альтернативы не обязательно должны быть отдельными предложениями рекурсивной процедуры. Они могут находиться в любом вызываемом предикате. Например,
. . . . . .
check(NewN),
. . . . . . . .
check(Z):-Z>=0.
check(Z):-Z<0.
Eсли Z>0,то первое check(Z) достигло цели, а второе в этот момент еще не проверено, поэтому предикат count() должен сохранить свои стековые копии, чтобы иметь возможность вернуться и начать проверку второго предложения, если рекурсивный вызов будет неудачен.
Для поиска недетерминированных предложений используйте директиву check_determ.
Для удаления альтернативных вызовов используйте cut, достигнув которого можно больше не обращать внимание на альтернативные предложения, а раз так, то и стек хранить не надо, и рекурсивный вызов может свободно идти дальше. Если отсечение выполнено, то компьютер считает, что непроверенных альтернатив больше нет, и не создает стекового фрейма.
Листинг 5.13. Использование рекурсии для циклического считывания символов
domains
char_data=char
predicates
write_prompt
read_a_character
goal
clearwindow,
write_prompt,
read_a_character.
clauses
write_prompt:-
write(“введи символ”),nl,
write(“окончание по #”),nl,nl.
read_a_character:-
readchar(Char_data),
Char_data<>’#’,
write(Char_data),
read_a_character.
domains
number=integer
predicates
write_number(number)
goal
clearwindow,
write(“ вот числа”),nl,nl,
write_number(1),nl,nl,
write(“all done,bye”).
clauses
write_number(8).
write_number(Number):-
Number<8,
write(“ “,Number),nl,
write_number(Next_number).
Подумайте, что надо изменить в программе для выдачи на экран чисел в обратном порядке.
Листинг 5.15. Рекурсивная программа вычисления факториала
trace
predicates
factorial(integer,real)
clauses
factorial(1,1):-!.
factorial(X,FactX):-
Y=X-1,
factorial(Y,FactY),
FactX=X*FactY.
goal
clearwindow,
write("input X-integer\n"),
readint(X),
factorial(X,FactX),
write("X=",X," FactX=",FactX).
Измените программу таким образом, чтобы рекурсия стала хвостовой.
Замечание: ПК создает новую копию предиката factorial таким образом, что factorial становится способным вызывать сам себя как полностью самостоятельную процедуру. При этом код выполнения не будет, конечно, копироваться, но все аргументы и промежуточные переменные копируются.
Информация хранится в стеке, который создается каждый раз при вызове правила. Когда выполнение правила завершится, стек освободится (если это не недетерминированный откат), и выполнение продолжается в стеке правила-родителя.
Выводы
Prolog имеет два способа повторения циклических участков программы – поиск с возвратом и рекурсию.
Поиск с возвратом – это мощное средство с точки зрения использования памяти, но после каждой итерации переменные обновляют свои значения, при этом их старые значения теряются.
Рекурсия позволяет сохранять значения переменных, но она не эффективна с точки зрения требуемого объема памяти. Однако, есть хвостовая рекурсия, и Prolog способен ее оптимизировать, то есть снять требования к объему памяти. Для этого рекурсивный вызов должен быть последней подцелью в теле предложения, а тело предложения и рекурсивный предикат должны быть детерминированными.
В Prolog’е рекурсивным может быть не только предложение, но и структуры данных.Prolog в отличие от большинства других языков позволяет определять типы рекурсивных данных, в которых указатели создаются и обрабатываются автоматически. Тип данных является рекурсивным, если он допускает структуры, содержащие такие же структуры, как и они сами. Такими структурами являются, например, список, дерево и др. Каждая ветвь дерева сама является деревом, поэтому структура рекурсивна. В Prolog’е мы имеем собственно рекурсивную структуру дерева, а не представление дерева в памяти, как это было в С и С++.
6. С П И С К И И Р Е К У Р С И Я
В Прологе рекурсивными могут быть не только предложения, но и структуры данных. Наиболее важный рекурсивный тип данных – это список.
Список- это бинарная структура данных, представляющая собой логически связанную последовательность записей - элементов списка.
Эта структура либо пуста, либо состоит из двух частей – головы и хвоста.
Хвост в свою очередь является списком.
Голова – обычная переменная. Выделив из списка голову, можно ее обрабатывать как и любую другую переменную. Все элементы списка обладают общим свойством: в Прологе это свойство трактуется как отношение, определяющее связь между элементами списка или между списком в целом и элементом, внешним по отношению к списку. Все элементы списка заключаются в [] и отделяются друг от друга запятыми:
[ann, peter, jim, tom] , [2,5.7.8]
В Прологе список – это последовательность, состоящая из любого количества элементов. Известно, что все структурированные объекты Пролога – это деревья. Списки не являются исключением из этого правила:
[3,7,10]
/ \
3 [7,10]
/ \
7 [10]
/ \
10 []
Рис.6.1.Двоичное дерево списка
Замечание
Конечно, объединить объекты в один можно различными способами. Если число объектов заранее известно,
то можно сделать эти объекты аргументами одной составной структуры данных. Если число объектов не определено, то можно использовать рекурсивную составную структуру данных, такую, как дерево, но наиболее легко и удобно работать со списками.
ной и легко управляемой. Списки широко используются в программах искусственного интеллекта, при разработке трансляторов программных языков, в реализации методов управления памятью.
Это базовые структуры функциональных языков. С помощью списков можно представить практически любые сложные структуры.
Порядок расположения элементов является отличительной чертой списка: те же элементы, упорядоченные иным способом, представляют собой уже совсем другой список. Порядок важен в процессе сопоставления. Объекты cписка называются элементами списка. Единственное ограничение на их число – объем оперативной памяти.
Все элементы списка принадлежат одному и тому же типу доменов. (Исключением являются списки структур. Структура может принадлежать альтернативному домену, и тогда элементы списка могут иметь разный тип).
Как представить список в виде стандартного объекта Пролога?
мы рассматриваем два случая – пустой список и непустой список.
Непустой список следует рассматривать как структуру, состоящую из двух частей - головы и хвоста, при этом хвост тоже список, который либо пуст, либо имеет свою голову и хвост.
Одноэлементный список [a]- не то же самое, что элемент, который в него входит, так как [a] –на самом деле – это составная структура данных:
/ \
a []
Список в Прологе рассматривается как частный случай двоичного дерева.
При построении списков необходимо наличие константного символа, чтобы рекурсия не была бесконечной. Таким символом является символ [], обозначающий пустой список.
Требуется также функтор арности два [X|Y],где X и Y-компоненты терма, имеющие специальные названия: X – голова(car),а Y-хвост (cdr) списка.
Определение списка
list([]).
list([Head|Tail]):-
list(Tail).
Например, список [a,b,c] – это терм [H|T] при подстановке H=a и T=[b,c].
list([a,b,c])
|
list([b,c])
|
list([c])
|
list([])
Рис 6.2.Дерево вывода при проверке списка
Таблица 6.1. Примеры разделения списка на голову и хвост
|
список |
голова |
хвост |
|
[[1,2],[2,3,4],[]] |
[1,2] |
[[2,3,4],[]] |
|
[] |
Не определен |
Не определен |
|
[3] |
3 |
[] |
Таблица 6.2.Примеры сопоставления двух списков:
|
Список 1 |
Список 2 |
Присвоение переменным |
|
[X,Y,Z] |
[2,3,4] |
X=2,Y=3,Z=4 |
|
[5] |
[X|Y] |
X=5,Y=[] |
|
[1,2,3,4] |
[X,Y|Z] |
X=1,Y=2,Z=[3,4] |
|
[1,2] |
[3|X] |
fail |
Использование списков отразится в программе на трех ее разделах:
1 domains
<описание домена списка>
2 predicates
<описание работающего со списком предиката>
3 clauses
<задание самого списка>
6.1.Операции над структурами данных типа список.
1 Принадлежность списку
2 Определение длины списка.
3 Вывод списка на печать
4 Модификация списка
5 Деление списка(X,L,L1,L2)
6 Удаление элемента из списка (X,L1,L2)
7 Объединение списков(L1,L2,L3)
8 Cортировка списков
Листинг6.1.1. Поиск нужного элемента(принадлежность списку)
domains
list=integer*
predicates
member(integer,list)
clauses
(1) member(Head,[Head|_]).
(2) member(Head,[_|Tail]):-
member(Head,Tail).
Алгоритм: (декларативная точка зрения)
Элемент принадлежит списку, если
(1) первый элемент списка и есть искомый элемент
(2) искомый элемент входит в состав хвоста списка
С процедурной точки зрения предложения программы 1 и 2 можно трактовать так: чтобы найти принадлежность элемента списку, надо проверить, не совпадает ли элемент с головой списка и если нет, то попытаться найти этот элемент в хвосте списка.
Цели
? member(3,[5,6,3,8,9]) –просим Пролог выяснить верно ли это утверждение.
(ответ: Yes или No в зависимости от того, входит или нет элемент с состав списка)
? member(X,[6,8,9])- вывод всего списка
И процедурная и декларативная точки зрения соотносятся с целями 1 и 2.
(ответ:
X=6
X=8
X=9
)
Модифицируем первое предложение member(Head,[Head|__]):-!.
Как изменится ответ, если поставим цель ?member(X,[6,8,9])
(ответ: X=6- только одно решение) Отсечение не позволит нам получить оставшиеся элементы списка, следовательно, это можно использовать только для получения одного конкретного значения –первого элемента списка.
Проверим, имеет ли значение порядок написания двух предложений для предиката member()? Поменяем местами эти предложения. Поставим цель member(X,[6,8,9]).Ответ будет напечатан в обратном порядке:
(ответ:
X=9
X=8
X=6
)
Убедились, что с процедурной точки зрения порядок предложений в программе важен. Изменение порядка правил в процедуре приведет к перестановке ветвей в дереве поиска цели, использующей данную процедуру. Само дерево поиска не изменится, но обход дерева будет производиться в ином порядке, а значит и процесс унификации пойдет иначе.
Замечание: Порядок целей более существенен, чем порядок предложений. Порядок целей имеет решающее значение при определении последовательности действий в программе. Изменение порядка целей приведет к изменению дерева поиска.
Листинг6.1.2. Определение длины списка
domains
list=integer*
predicates
length_of(list,integer)
clauses
length_of([],0).
length_of([_|T],L):-
length_of(T,TailLength),
L=TailLength+1.
Терминальный случай- длина пустого списка =0.
Нетерминальный случай-правило рекурсии – длина любого
другого списка равна 1+длина его хвоста.
Goal: clearwindow, length_of([5,7,1,4],L).
При нисходящем построении рекурсии решение откладывается до тех пор, пока не станет известен последний член списка
Length_of([5,7,1,4]) L1=L2+1=4
length_of([7,1,4],L2) L2=L3+1=3
length_of([1,4],L3) L3=L4+1=2
length_of([4],L4) L4=0+1=1
length_of([],0) 0
Ответ: L=4 1 Solution
Замечание
Отличия от процедурных языков:
1. Вместо изменения значения переменной с помощью присваивания, повторно вызываем функцию с измененными значениями ее параметров
2. Вместо использования безусловного перехода и итерации применяем условное выражение и рекурсию.
3.Плохо то, что для организации рекурсии требуется большой стек, а механизм связывания, используемый для адресации позиции текущей переменной в этом стеке, может замедлить исполнение для фон-неймановских машин (сейчас, правда, это не так важно).
Листинг 6.1.3.Модификация списка (программа работает со списком и добавляет 1 к каждому элементу списка)
domains
list=integer*
predicates
add1(list,list)
clauses
add1([],[]).
add1([Head|Tail],[Head1|Tail1]):-
Head1=Head+1,
add1(Tail,Tail1).
goal
add1([10,21,3,74],NewList),
write(NewList).
(ответ-[11,22,4,75])
стек: 75 из стека идет обратная раскрутка
74 [74],[75]
4 [3,74],[4,75]
3 [21,3,75],[22,4,75]
22 [10,21,3,74],[11,22,4,75] и печать
21
11
10
Ответ: NewList=[11,22,4,75]
Объединение списов (конкатенация)
Особенность Пролога заключается в том, что задавая утверждения для предиката с логической точки зрения, эти утверждения могут быть выполнены с процедурной точки зрения.
То есть здесь присутствует двойственность, и эту двойственность надо увидеть и учесть. Воспользуемся рекурсией с процедурной точки зрения для объединения списков.
Определим предикат append с тремя аргументами
append(List1,List2,List3)
List1, List2 – исходные списки,
List3- список, получающийся при их объединении.
Например, append([1,2],[3,4],[1,2,3,4])-true
append([1,2],[3,4],[1,2,1,3,4])-false
Определим отношение append,как содержащее два случая в зависимости от вида List1:
1. Если List1-пуст, то второй и третий аргументы представляют собой один и тот же список (назовем его List2):
append([],List2,List2).
2. Если List1 –не пуст, то он имеет голову и хвост [H|L1], и можно объединить List1 и List2 для формирования List3,сделав голову List1 головой List3.
Хвост List3 состоит из объединения остатка List1 и всего List2:
append(H|L1],List2,[H|L3]:-
append(L1,List2,L3).
Листинг 6.1.4. Программа объединения списков
domains
list=integer*
predicates
append(list,list,list)
clauses
append([],List,List).
append([H|L1],List2,[H|L3]):-
append(L1,List2,L3).
Поставьте цели:
1.?append([1,2],[3,4,5],L).
Ответ:L=[1,2,3,4,5] 1Solution
2.?append([1,2],[3],L),append(L,L,LL).
Ответ: L=[1,2,3]
LL=[1,2,3,1,2,3] 1Solution
3.?append([1,2],L,[1,2,5,6]) –разность между списками
Ответ:L=[5,6] 1Solution
4.? append(L,[5,6],[1,2,5,6] –разность между списками
Ответ L=[1,2] 1Solution
Замечание для 3 и 4:
Первые два аргумента отношения append не симметричны, поэтому имеется два различных варианта нахождения разности между двумя списками.
Рассматривая append с декларативной точки зрения мы определяем отношение между тремя списками. Это отношение сохранится даже если List1 и List3 известны, а List2 –нет. Оно также справедливо, если известен только List3.
Таким образом, предикат append определяет отношение между входным набором и выходным набором таким образом, что отношение применимо в обоих направлениях Задавая отношения вы можете спросить систему
–Какой выход соответствует данному входу?
-Какой вход соответствует данному выходу?
Состояние аргументов при вызове предиката называется потоком параметров. Аргумент, который присваивается или назначается в момент вызова, называется входным аргументом и обозначается буквой”i”; а свободный аргумент – это выходной аргумент, и он обозначается буквой “o”.
У предиката append есть возможность работать с разными потоками параметров в зависимости от того, какие исходные данные ему зададут. Если утверждение Пролога может быть использовано с различными потоками параметров, оно называется обратимым утверждением. Обратимые утверждения имеют дополнительные преимущества, и их создание добавляет “мощности” предикатам.
Использование программы append в обратном направлении:
Goal: (L1,L2,[1,2,3,6]).
Ответ:
L1=[] L2=[1,2,3,6]
L1=[1] L2=[2,3,6]
L1=[1,2] L2=[3,6]
L1=[1,2,3] L2=[6]
L1=[1,2,3,6] L2=[] 5 Solutions
Если бы объекты были не числа, а дни недели,то:
domains
list=string*
Goal: append(Before,[friday|After],[monday,tuesday,wednesday,thursday,friday,saturday,sunday]).
Ответ:
Before=(“monday”,”tuesday”,’wednesday’,”thursday”]
After=[“saturday”,”sunday”]
1 solution
goal: append(L1,[b|_],[a,b,c])
ответ
L1=[“a”] 1Solution
goal: L1=[a,b,c,d,f,f,m],append(L2,[f|_],L1)
ответ:
L1=[a,b,c,d,f,f,m] L2=[a,b,c,d]
L1=[a,b,c,d,f,f,m] L2=[a,b,c,d,f]
2 solutions
(удаление всего, что стоит следом за f)
Замечание: логические программы не содержат алгоритма, для решения логической задачи достаточно точного логического описания. Так как в логической программе последовательность и способ выполнения программы не фиксируется, как при описании алгоритма, программы в принципе могут работать в обоих направлениях. Прологовская программа может на основе исходных данных вычислить результат, но с тем же успехом без дополнительного программирования на основе результата –вычислить исходные данные.
(В традиционных языках программирования данные обрабатываются в порядке, задаваемом описанием алгоритма. Это определяет несимметричность функции, то есть вычислить значения аргументов, исходя из значения функции нельзя!)
Ранее мы ввели предикат member.Такие предикаты как member, sublist, prefix могут быть определены в терминах предиката append, если последний использовать не для объединения, а для разделения(расщепления) списков.
Попробуем определить отношение принадлежности, используя конкатенацию.
member(X,L):-
append(L1,[X|L2],L).
X принадлежит L, если список L можно разбить на два списка L1 и L2 так, чтобы элемент X являлся головой списка L2. Поставим цель ? member(2,[1,3,2,5,7]). Предикат member будет просматривать список L элемент за элементом до тех пор, пока не встретит 2, или пока не кончится список. Ответ: yes –no
Листинг 6.1.5.Определение принадлежности через объединение
domains
list=integer*
predicates
member(integer,list)
append(list,list,list)
clauses
member(X,L):-
append(L1,[X|L2],L).
append([],L,L).
append([X|L1],L2,[X|L3]):-
append(L1,L2,L3).
Попытайтесь самостоятельно использовать предикат append для нахождения префиксов, суффиксов, подсписков.
Листинг 6.1.6.Деление списка
domains
middle=integer
list=integer*
predicates
split(middle,list,list,list)
clauses
split(_,[],[],[]).
Split(Middle,[Head|Tail],[Head|L1],L2):-
Head<=Middle,
Split(Middle,Tail,L1,L2).
Split(Middle,[Head|Tail],L1,[Head|L2]):-
Head>Middle,
Split(Middle,Tail,L1,L2).
Middle-компаратор-элемент данных
L-исходный список
L1,L2 – подсписки, получающиеся в результате деления
списка L.
Алгоритм
Очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом голова сравнивается с компаратором Middle.Если значение этого элемента <= Middle,то элемент помещается в список L1,иначе - в список L2. Элементы и компаратор должны быть одного типа.
Goal: split(12,[96,2,8],L1,L2)
Ответ:L1=[2,8]
L2=[96]
Листинг 6.1.7. Удаление элемента из списка
domains
list=integer*
predicates
delete(integer,list,list)
clauses
(1) delete(X,[X|Tail],Tail).
(2) delete(X,[Y|Tail],[Y|Tail1]):-
delete(X,Tail,Tail1).
(1) Если X – голова списка, то результат –хвост этого списка.
(2) Если X – в хвосте, то его надо удалить оттуда.
Отношение delete по своей природе – недетерминировано и обратимо.
Цели:
? delete(5,[1,8,5,7,5],L)
Ответ L=[1,8,7,5] -удаление первой 5
L=[1,8,5,7] –удаление последней 5
Если в списке содержится несколько вхождений элемента X, то delete может исключить их все при помощи возврата и дать нам различные варианты удалений, каждый раз удаляя лишь одно вхождение X.Остальные вхождения остаются в неприкосновенности (недетерминированность). При попытке исключить элемент, отсутствующий в списке, отношение delete потерпит неудачу
? delete(5,L,[1,8,7]) – используем для вставки элемента (обратимость)
Ответ L=[5,1,8,7]
L=[1,5,8,7]
L=[1,8,5,7]
L=[1,8,7,5] 4Solution
Отношение delete – обратимое, его можно использовать в обратном направлении для того, чтобы добавить элементы в список, вставляя их в произвольные места списка. Для этого зададим вопрос:”Каким должен быть список L,чтобы после удаления из него элемента “5” получить список [1,8,7] ”?
Отношение delete можно использовать для проверки на принадлежность списку.
Идея:X принадлежит списку, если этот X можно из списка удалить:
member(X,List):-
delete(X,List,_).
Delete можно использовать для построения всех возможных перестановок списка .Для этого надо включить отношение change с двумя аргументами
Листинг 6.1.8 Перестанова элементов списка с помощью удаления
domains
list=integer*
predicates
delete(integer,list,list)
change(list,list)
clauses
delete(X,[X|Tail],Tail).
delete(X,[Y|Tail],[Y|Tail1]):-
delete(X,Tail,Tail1).
change([],[]).
change(L,[X|P]):-
delete(X,L,L1),
change(L1,P).
? (change([3,5,6],L)---L=[3,5,6] L=[3,6,5] L=[5,3,6] L=[5,6,3]
L=[6,3,5] L=6,5,3] 6 Solutions
Но надо быть осторожным ( при change(L,[3,5,6])—произойдет зацикливание)
6.2.Предикат findall
findall(Variable,<предикат>,ListVariable) - записывает значение объекта Variable в список ListVariable. Variable должен являться одним из аргументов указанного предиката.
Рекурсивная процедура хранит память о промежуточных результатах по мере выполнения программы, так как она передает информацию через параметры от одного рекурсивного вызова к другому. Но рекурсия не может осуществить поиск всех альтернативных решений в цели, который обычно выполняет поиск с возвратом. Поэтому, когда вам нужны все решения для целевого утверждения, и они необходимы все сразу, как часть единой составной структуры, то вы будете использовать встроенный предикат findall. Этот предикат использует целевое утверждение в качестве одного из своих аргументов и собирает все решения для этого целевого утверждения в единый список методом поиска с возвратом.
Листинг 6.2.1. использование предиката findall
/*Пусть есть БД – группа студентов, есть отметки, полученные студентом на экзамене по ФЛП Найти средний балл по указанной группе*/
domains
name=string
mark=integer
list=mark* % список оценок
predicates
student(name,mark) % предикат БД
sum_list(list,mark,integer) % сумма всех оценок в списке по ФЛП
report_average_student_mark %средний балл
goal
report_average_student_mark.
clauses
student(“Орлов”,4).
student(“Абрамов”,3).
student(“Смирнов”,5).
report_average_student_mark:-
findall(Mark,student(_,Mark),Mark_list),
sum_list(Mark_list,Sum,Number),
Average=Sum/Number,
write(“Группа студентов по дисциплине имеет:”),nl,
write(“Средний балл=”,Average).
sum_list([],0,0).
sum_list([H|T],Sum,Number):-
sum_list(T,Sum1,Number1),
Sum=H+Sum1,
Number=Number1+1.
6.3. Операции со структурами данных.
Сортировка списков
Список может быть упорядочен (отсортирован), если между его элементами определено отношение порядка.
Отношение порядка – больше(x,y)
ask_order(X,Y):-
X>Y (для чисел)
Если элементы списка – атомы, то отношение “больше”
соответствует алфавитному порядку.
В качестве примера приведем программу, реализующую быструю сортировку.
Метод быстрой сортировки (quick_sort)
Идея: 1 Удалить из списка L какой-либо элемент X и разбить оставшуюся часть на два списка- Smaller и Larger
2 разбиение(деление) списка производить следующим образом: все элементы>X принадлежат списку Larger,остальные- списку Smaller
3 Отсортировать список Smaller и результат – список Sort_Smaller
4 Отсортировать список Larger и результат – список Sort_larger
5 Получить результирующий упорядоченный список как конкатенацию списков Sort_Smaller и [X|Sort_Larger].
[5,2,4,8,9,3,7] --исходный список
/ --удаляем X=5( обычно голова списка)
[2,4,8,9,3,7]
/ \ --деление списка по признаку-<=5 >5
[2,4,3] [8,9,7]
/ \ ---сортировка
[2,3,4] [7,8,9]
\ / ---конкатенация с добавлением X
[2,3,4,5,7,8,9] ---отсортированный список
Время выполнения сортировки зависит от того, насколько повезет при разбиении сортируемого списка. Если оба разбиваемых списка примерно одинаковой длины, то время выполнения порядка n*log n,где n-длина исходного списка
Если один из списков значительно длиннее другого, то время выполнения порядка n2 (как и при сортировке со вставками- с ростом n время растет пропорционально n2.)
Анализ показывает, что чаще произведенная сортировка оказывается ближе к лучшему случаю.
Листинг 6.3.3. быстрая сортировка
trace
domains
number=integer
list=number*+
predicates
quick_sort(list,list)
split(list,number,list,list)
append(list,list,list)
clauses
quick_sort([],[]).
quick_sort([X|Tail],Sort_list):-
split(Tail,X,Little_list,Large_list),
quick_sort(Little_list,Sort_little_list),
quick_sort(Large_list,Sort_large_list),
append(Sort_little_list,[X|Sort_large_list],Sort_list).
split([],_,[],[]).
split([X|Tail],Y,[X|Sort_little_list],Sort_large_list):-
X<=Y,
split(Tail,Y,Sort_little_list,Sort_large_list).
split([X|Tail],Y,Sort_little_list,[X|Sort_large_list]):-
X>Y,
split(Tail,Y,Sort_little_list,Sort_large_list).
append([],L,L).
append([X|L1],L2,[X|L3]):-
append(L1,L2,L3).
Список литературы
1. Адаменко А, Кучумов А. Логическое программирование и Visual prolog: руководство в подлиннике – СПб.: БХВ-Петербург,2003 -993с.
2.Стерлинг Л.,Шапиро Э. Искусство программирования на языке Пролог:Пер с анг.-М.:Мир,1990. -235с.
3.Братко И. Алгоритмы искусственного интеллекта на языке Prolog,3-е издание.:пер. с англ. – М.:Издательский дом “Вильямс”, 2004. – 640с.
4.Хювёнен Э.,Сеппянен Й. Мир Лиспа.В 2-х т. Т1:Введение в язык Лисп и функциональное программирование. Пер. с финск. – М.: Мир, 1990. -447c.
5.Душкин Р.В.Функциональное программирование на языке Haskell.-М.:ДМК Пресс,2007. -608с.
Объекты данных( термы)
Простые объекты
оставные объекты
(размерность>0)
Структуры
константы const
переменные
атомы
число
числа
Система резолютивного вывода
Система резолютивного вывода
S1
S2
EMBED Equation.3 likes(bill,pizza).
Likes(bill,pizza):-food(pizza,italiano).
S: EMBED Equation.3 food(pizza,italiano)
S
S3
EMBED Equation.3 food(pizza,italiano).
food(pizza,italiano)
S ’ : противоречие