Шпаргалка - Функционально-логическое программирование Prolog, Lisp - файл n1.doc

приобрести
Шпаргалка - Функционально-логическое программирование Prolog, Lisp
скачать (91.3 kb.)
Доступные файлы (1):
n1.doc381kb.30.05.2008 22:26скачать

n1.doc

  1   2
1. Понятия предиката.

2. Алгоритмы унификации

3. Структура пролог-программы

4. Организация повторов

5. Ветвление-выбор

6. Стандартные математические предикаты

7. Списки и операции над ними

8. Сортировка списков

9. Выборка элементов из списков

10. Слияние списков

11. Множества в Прологе

12. Реализация деревьев в Прологе
13. Функциональный подход программирования

14. Методы обработки списков (ЛИСП)

15. Определение универсальной функции

16. Предикаты и истинность в ЛИСПе

17. Отображения и функционалы

18. Имена, определения и контексты в ЛИСП 180

19. Prog выражения и циклы в ЛИСП

20. Списки свойств атомов и структура списков

21. Числа и мультиоперации

22. Функционалы - общее понятие

23. Безымянные функции

24. Экспертные системы. Реализация в Пролог и Лисп

1. ПОНЯТИЯ ПРЕДИКАТА.

2. АЛГОРИТМЫ УНИФИКАЦИИ

Унификация позволяет отождествлять формулы логики первого порядка путем замены свободных переменных на термы.

Подстановка Y называется унификатором простых выражений A и B, если AY=BY. Про A и B в такой ситуации говорят, что они унифицируемы. Унификация используется в Прологе для композиции и декомпозиции структур данных. Унификатор называют наиболее общим (или простейшим) унификатором простых выражений A и B, если он является более общей подстановкой, чем все другие унификаторы простых выражений A и B.
АЛГОРИТМ ПОИСКА наиболее общего унификатора.:

Шаг 1. Полагаем k=0,  .

Шаг 2. Если  - одноэлементное множество, останавливаем алгоритм,  - наиболее общий унификатор для S. В противном случае строим множество рассогласований  и переходим к третьему шагу.

Шаг 3. Если в  существуют переменная x и терм t такие, что x не входит в t, то полагаем что . Увеличиваем на единицу k, переходим ко второму шагу. Иначе останавливаем алгоритм, множество S не унифицируемо.
Утверждение о том, что для любого унифицируемого конечного множества простых выражений S алгоритм унификации закончит свою работу и выдаст наиболее общий унификатор для S, называется теоремой унификации.
МЕТОД РЕЗОЛЮЦИЙ.

Алгоритм, дающий ответ на вопрос, может ли быть выведено некоторое заключение из множества имеющихся посылок. Известно, что в общем случае даже для логики первого порядка такой алгоритм невозможен. Однако Робинсон решил, что правила вывода, используемые компьютером при автоматическом выводе, не обязательно должны совпадать с правилами вывода, используемыми при "человеческом" выводе. В частности, он предложил вместо правила вывода "modus ponens", которое утверждает, что из A и A B выводится B, использовать его обобщение, правило резолюции, которое сложнее понимается человеком, но эффективно реализуется на компьютере. Давайте попробуем разобраться с этим правилом.

ПРАВИЛО РЕЗОЛЮЦИИ для логики высказываний можно сформулировать следующим образом.

Если для двух дизъюнктов существует атомная формула, которая в один дизъюнкт входит положительно, а в другой отрицательно, то, вычеркнув соответственно из одного дизъюнкта положительное вхождение атомной формулы, а из другого — отрицательное, и объединив эти дизъюнкты, мы получим дизъюнкт, называемый резольвентой. Исходные дизъюнкты в таком случае называются родительскими или резольвируемыми, а вычеркнутые формулы — контрарными литералами. Другими словами, резольвента — это дизъюнкт, полученный из объединения родительских дизъюнктов вычеркиванием контрарных литералов.

Графически это правило можно изобразить так:



Здесь A P и B ¬P — родительские дизъюнкты, P и ¬P — контрарные литералы, A B — резольвента.

Если родительские дизъюнкты состояли только из контрарных литералов, то резольвентой будет пустой дизъюнкт.

Пример. Правило вывода "modus ponens" получается из правила резолюции, если взять в качестве родительских дизъюнктов C1=A, C2=¬A B( A B). Контрарными литералами в применении этого правила будут A и ¬A, резольвентой — формула B.

Сформулируем правило резолюции для логики первого порядка.

Пусть имеется два дизъюнкта C1 и C2, у которых нет общих переменных, L1 — литерал, входящий в дизъюнкт C1, L2 — литерал, входящий в дизъюнкт C2. Если литералы имеют наибольший общий унификатор ?, то дизъюнкт (C1?–L1?)(C2?–L2?) называется резольвентой дизъюнктов C1 и C2. Литералы L1 и L2 называются контрарными литералами. То же правило записывается в графическом виде как

(A P2, B ¬P2)/(A B)?

Здесь P1 и P2 — контрарные литералы, (A B)? — резольвента, полученная из дизъюнкта (A B) применением унификатора ?, A P1 и B P2 — родительские дизъюнкты, а ? — наибольший общий унификатор P1 и P2.

Метод резолюций является обобщением метода "доказательства от противного". Вместо того чтобы пытаться вывести некоторую формулу-гипотезу из имеющегося непротиворечивого множества аксиом, мы добавляем отрицание нашей формулы к множеству аксиом и пытаемся вывести из него противоречие. Если нам удается это сделать, мы приходим к выводу (пользуясь законом исключенного третьего), что исходная формула была выводима из множества аксиом. Опишем более подробно.

Добавим отрицание исходной формулы к множеству посылок, преобразуем каждую из этих формул во множество дизъюнктов, объединим получившиеся множества дизъюнктов и попытаемся вывести из этого множества дизъюнктов противоречие (пустой дизъюнкт ?). Для этого будем выбирать из нашего множества дизъюнкты, содержащие унифицируемые контрарные литералы, вычислять их резольвенту по правилу резолюции, добавлять ее к исследуемому множеству дизъюнктов. Этот процесс будем продолжать до тех пор, пока не выведем пустой дизъюнкт.

Возможны, вообще говоря, три случая:

  1. Этот процесс никогда не завершается.

  2. Среди текущего множества дизъюнктов не окажется таких, к которым можно применить правило резолюции. Это означает, что множество дизъюнктов выполнимо, и, значит, исходная формула не выводима.

  3. На очередном шаге получена пустая резольвента. Это означает, что множество дизъюнктов невыполнимо и, следовательно, начальная формула выводима.

Имеет место теорема, утверждающая, что описанный выше процесс обязательно завершится за конечное число шагов, если множество дизъюнктов было невыполнимым.

С другой стороны, мы опираемся на результат, что формула выводима из некоторого множества формул тогда и только тогда, когда описанное множество дизъюнктов невыполнимо. А также на то, что множество дизъюнктов невыполнимо тогда и только тогда, когда из него применением правила резолюции можно вывести пустой дизъюнкт.

В сущности, метод резолюций несовершенен и приводит к "комбинаторному взрыву". Однако некоторые его разновидности (или стратегии) довольно эффективны. Одной из самых удачных стратегий является линейная или SLD-резолюция для хорновских дизъюнктов (Linear resolution with Selection function for Definition clauses), то есть дизъюнктов, содержащих не более одного положительного литерала. Их называют предложениями или клозами.

Если дизъюнкт состоит только из одного положительного литерала, он называется фактом. Дизъюнкт, состоящий только из отрицательных литералов, называется вопросом (или целью или запросом). Если дизъюнкт содержит и позитивный, и негативные литералы, он называется правилом. Правило вывода выглядит примерно следующим образом ¬A1 ¬A2...¬An B. Это эквивалентно формуле A1 A2... An B, которая на Прологе записывается в виде

B:–A1,A2,...,An.

Логической программой называется конечное непустое множество хорновских дизъюнктов (фактов и правил).

При выполнении программы к множеству фактов и правил добавляется отрицание вопроса, после чего используется линейная резолюция. Ее специфика в том, что правило резолюции применяется не к произвольным дизъюнктам из программы. Берется самый левый литерал цели (подцель) и первый унифицируемый с ним дизъюнкт. К ним применяется правило резолюции. Полученная резольвента добавляется в программу в качестве нового вопроса. И так до тех пор, пока не будет получен пустой дизъюнкт, что будет означать успех, или до тех пор, пока очередную подцель будет невозможно унифицировать ни с одним дизъюнктом программы, что будет означать неудачу.

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

В итоге выполнение программы может завершиться неудачей, если одну из подцелей не удалось унифицировать ни с одним дизъюнктом программы, и может завершиться успешно, если был выведен пустой дизъюнкт, а может и просто зациклиться.

.

.

3. СТРУКТУРА ПРОЛОГ-ПРОГРАММЫ

Программа на Турбо Прологе состоит из следующих семи разделов:

директивы компилятора;

CONSTANTS - раздел описания констант;

DOMAINS - раздел описания доменов;

DATABASE - раздел описания предикатов внутренней базы данных;

PREDICATES - раздел описания предикатов;

CLAUSES - раздел описания предложений;

GOAL - раздел описания внутренней цели.
В программе может быть несколько разделов описаний DOMAINS, PREDICATES, DATABASE и CLAUSES.

Порядок разделов может быть произвольным, но при этом константы, домены и предикаты должны быть определены до их использования. Однако в разделе DOMAINS можно ссылаться на домены, которые будут объявлены позже.

Рассмотрим разделы немного подробнее.
ДИРЕКТИВЫ КОМПИЛЯТОРА (Options -Compiler Directives).

TRACE применяется при отладке программы для трассирования. Если после слова trace указаны имена предикатов через запятую, то трассировка идет только по этим предикатам.

NOWARNINGS используется для подавления предупреждения системы о том, что какая-то переменная встречается в предложении только один раз.

INCLUDE при компиляции в исходный текст можно вставить содержимое некоторого файла.
РАЗДЕЛ ОПИСАНИЯ КОНСТАНТ (<имя константы>=<значение>).

Каждое определение константы должно размещаться в отдельной строке.

Имя константы должно быть идентификатором (состоять из английских букв, цифр и знака подчеркивания, причем не может начинаться с цифры).

Можно использовать в качестве первого символа прописные символы. Однако при использовании констант нужно задействовать в качестве первого символа только строчные символы, чтобы Пролог-система не восприняла константу как переменную.
РАЗДЕЛ ОПИСАНИЯ ДОМЕНОВ (ТИПОВ).

<имя домена>=<определение домена>.

Integer, real, char, string, symbol, file.

В разделе описания доменов объявляются любые нестандартные домены.
Из доменов можно конструировать структуры:

point = p(integer, integer)

Каждая компонента структуры в свою очередь может быть структурой:

triangle = tr(point, point, point).

В описание структуры могут входить альтернативы, разделенные символом ";" или ключевым словом "or". Структура, описывающую точку и на плоскости, и в пространстве:

point = p(integer, integer);p(integer, integer, integer).

Список целых чисел описывается так:

list_of_integer=integer*

РАЗДЕЛ ОПИСАНИЯ ПРЕДИКАТОВ ВНУТРЕННЕЙ БАЗЫ ДАННЫХ

DATABASE [ — <имя базы данных>]

<имя предиката>(<имя домена первого аргумента>,...,

< имя домена n-го аргумента>)

РАЗДЕЛ ОПИСАНИЯ ПРЕДИКАТОВ

В традиционных языках программирования подобными разделами являются разделы описания заголовков процедур и функций. Описание n-местного предиката имеет следующий вид:

Домены аргументов должны быть либо стандартными, либо объявленными в разделе описания доменов.

mother(string,string)

Один предикат может иметь несколько описаний. При этом возможны несколько вариантов использования этого предиката, а процедура, реализующая этот предикат будет единственной.

Кроме того, при описании предиката можно указать, будет он детерминированным или недетерминированным. Детерминированный предикат возвращает только одно решение, а недетерминированный предикат при помощи поиска с возвратом может давать много решений. Детерминированные предикаты менее требовательны к оперативной памяти и выполняются быстрее.

РАЗДЕЛ ОПИСАНИЯ ПРЕДЛОЖЕНИЙ

Этот раздел можно считать основным разделом программы, потому что именно в нем содержатся факты и правила, реализующие пользовательские предикаты. Все предикаты, которые применяются в этом разделе и не являются стандартными предикатами, должны быть описаны в разделе описания предикатов или в разделе описания предикатов базы данных.

Предложения, у которых в заголовке указан один и тот же предикат, должны идти друг за другом. Такой набор предложений называется ПРОЦЕДУРОЙ.

РАЗДЕЛ ОПИСАНИЯ ВНУТРЕННЕЙ ЦЕЛИ

Если этот раздел отсутствует, то после запуска программы Пролог-система выдает приглашение вводить вопросы в диалоговом режиме (внешняя цель). При выполнении внешней цели Пролог-система ищет все решения, выводя все возможные значения для переменных, участвующих в вопросе. Если же выполняется внутренняя цель, то осуществляется поиск только первого решения, а для получения всех решений нужно предпринимать дополнительные действия.

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

.

4. ОРГАНИЗАЦИЯ ПОВТОРОВ

В Прологе для этого используются процедура поиска с возвратом (откат) и рекурсия. Откат дает возможность получить много решений в одном запросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого.
БАЗИС РЕКУРСИИ - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии.

ШАГ РЕКУРСИИ - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле.
Рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные. Некоторые алгоритмы удобно записывать именно рекурсивно.

НЕДОСТАТОК: может не хватать для работы стека. При каждом рекурсивном вызове предиката в специальном стековом фрейме запоминаются все промежуточные переменные, которые могут понадобиться. Максимальный размер стека при работе под управлением операционной системы MS DOS всего 64 Кб. Этого достаточно для размещения около трех-четырех тысяч стековых фреймов (в зависимости от количества и размера промежуточных переменных). При больших входных значениях стека может не хватить.
Есть, правда, один вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила.

5. Ветвление-выбор

6. Стандартные математические предикаты
.

.

7. СПИСКИ И ОПЕРАЦИИ НАД НИМИ (list = integer*)

Рекурсивное определение списка.

Список — это структура данных, определяемая следующим образом:

1. пустой список ([ ]) является списком;

2. структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.

В императивных языках основной структурой данных являются массивы. В Прологе так же, как и в Лиспе, основным составным типом данных является список.

[] — пустой список, т.е. список, не содержащий элементов (в Лисп - nil).

Элементы списка могут быть любыми, в том числе и списками.

В классическом Прологе элементы списка могут принадлежать разным доменам, В Турбо Прологе, в связи со строгой типизацией, все элементы списка должны принадлежать одному домену. Однако можно разместить в одном списке объекты разной природы, используя домен с соответствующими альтернативами.

Операция "|" позволяет разделить список на хвост и голову (в Лиспе - car и cdr) или приписать объект (объекты) к началу списка (cons в Лиспе). Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост.

Чтобы организовать обработку списка достаточно задать базис рекурсии (правило или факт, определяющее, что нужно делать с пустым списком), а также рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста.


8. СОРТИРОВКА СПИСКОВ

9. ВЫБОРКА ЭЛЕМЕНТОВ ИЗ СПИСКОВ

10. СЛИЯНИЕ СПИСКОВ

Создадим предикат, позволяющий соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий — результат соединения.

В качестве основы для решения этой задачи возьмем рекурсию по первому списку. Базисом рекурсии будет факт, устанавливающий, что если присоединить к списку пустой список, в результате получим исходный список. Шаг рекурсии - правило, определяющее, что для того, чтобы приписать элементы списка, состоящего из головы и хвоста, ко второму списку, нужно соединить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка.

conc([ ], L, L).

conc([H|T], L, [H|T1]) :– conc(T, L, T1).
Заметим, что этот предикат также можно применять для решения нескольких задач.

Во-первых, для соединения списков.

Во-вторых, для того, чтобы проверить, получится ли при объединении двух списков третий.

В-третьих, можно использовать этот предикат для разбиения списка на подсписки.

В-четвертых, можно использовать этот предикат для поиска элементов, находящихся левее и правее заданного элемента.

В-пятых, на основе нашего предиката conc можно создать предикат, находящий последний элемент списка:

last(L,X):– conc(_,[X],L).
В-шестых, можно определить, используя conc, предикат, позволяющий проверить принадлежность элемента списку. При этом воспользуемся тем, что если элемент принадлежит списку, то список может быть разбит на два подсписка так, что искомый элемент является головой второго подсписка:

member4(X,L):–

conc(_,[X|_],L).

В-седьмых, используя предикат, позволяющий объединить списки, можно создать предикат, проверяющий по двум значениям и списку, являются ли эти значения соседними элементами списка. Предикат будет иметь три параметра: первые два — значения, третий — список.

Идея решения заключается в следующем. Если два элемента оказались соседними в списке, значит, этот список можно разложить на два подсписка, причем голова второго подсписка содержит два наших элемента в нужном порядке. Выглядеть это будет следующим образом:

neighbors(X,Y,L):–

conc(_,[X,Y|_],L). /* список L получается путем

объединения некоторого списка

со списком, голову которого

составляют элементы X и Y */

Обратите внимание, что этот предикат проверяет только наличие нужных значений в указанном порядке. Если нам неважен порядок, в котором два данных значения встречаются в некотором списке, то следует записать модификацию описанного выше предиката, которая будет проверять оба варианта размещения искомых элементов. Для этого достаточно, чтобы список раскладывался на два подсписка, причем голова второго подсписка содержала два наших элемента либо в прямом, либо в обратном порядке. Соответствующий программный код будет следующим:

neighbors2(X,Y,L):–

conc(_,[X,Y|_],L);

conc(_,[Y,X|_],L). /* список L получается

путем объединения некоторого

списка со списком, голову

которого составляют элементы X

и Y или элементы Y и X */

.

.

11. МНОЖЕСТВА В ПРОЛОГЕ
Список, который не содержит повторных вхождений элементов.
Нам предстоит разработать предикаты, которые реализуют основные теоретико-множественные операции.

Начнем с написания предиката, превращающего произвольный список во множество, в том смысле, в котором мы договорились понимать этот термин. Для этого нужно удалить все повторные вхождения элементов. При этом мы воспользуемся предикатом delete_all, который был создан нами ранее, в седьмой лекции. Предикат будет иметь два аргумента: первый — исходный список (возможно, содержащий повторные вхождения элементов), второй — выходной (то, что остается от первого аргумента после удаления повторных вхождений элементов).

Предикат будет реализован посредством рекурсии. Базисом рекурсии является очевидный факт: в пустом списке никакой элемент не встречается более одного раза. По правде говоря, в пустом списке нет ни одного элемента, который встречался бы в нем хотя бы один раз, то есть в нем вообще нет элементов. Шаг рекурсии позволит выполнить правило: чтобы сделать из непустого списка множество (в нашем понимании этого понятия), нужно удалить из хвоста списка все вхождения первого элемента списка, если таковые вдруг обнаружатся. После выполнения этой операции первый элемент гарантированно будет встречаться в списке ровно один раз. Для того чтобы превратить во множество весь список, остается превратить во множество хвост исходного списка. Для этого нужно только рекурсивно применить к хвосту исходного списка наш предикат, удаляющий повторные вхождения элементов. Полученный в результате из хвоста список с приписанным в качестве головы первым элементом и будет требуемым результатом (множеством, т.е. списком, образованным элементами исходного списка и не содержащим повторных вхождений элементов).

Закодируем наши рассуждения.

list_set([],[]). /* пустой список является списком

в нашем понимании */

list_set ([H|T],[H|T1]) :–

delete_all(H,T,T2),

/* T2 — результат удаления

вхождений первого элемента

исходного списка H из хвоста T */

list_set (T2,T1).

/* T1 — результат удаления

повторных вхождений элементов

из списка T2 */

Например, если применить этот предикат к списку [1,2,1,2,3, 2,1], то результатом будет список [1,2,3].

Заметим, что в предикате, обратном только что записанному предикату list_set и переводящем множество в список, нет никакой необходимости по той причине, что наше множество уже является списком.

Теперь займемся реализацией теоретико-множественных операций, таких как принадлежность элемента множеству, объединение, пересечение, разность множеств и т.д.

При реализации этих предикатов можно было бы воспользоваться предикатами, предназначенными для работы с обыкновенными списками, но в результате их применения могут получаться списки, содержащие некоторые элементы несколько раз, даже если исходные списки были множествами, в нашем понимании этого слова.

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

Итак, приступим.

В качестве реализации операции принадлежности элемента множеству вполне можно использовать предикат member3, который мы разработали в седьмой лекции, когда только начинали знакомиться со списками. Напомним, что факт принадлежности элемента x множеству A в математике принято обозначать следующим образом: xA.

Для того чтобы найти мощность множества, вполне подойдет предикат length, рассмотренный нами в седьмой лекции. Напомним, что для конечного множества мощность — это количество элементов во множестве.

Пример. Реализуем операцию объединения двух множеств. На всякий случай напомним, что под объединением двух множеств понимают множество, элементы которого принадлежат или первому, или второму множеству. Обозначается объединение множеств A и B через AB. В математической записи это выглядит следующим образом: AB={x | xA или xB}. На рисунке объединение множеств A и B обозначено штриховкой.


Рис. 9.1.  Объединение множеств A и B

У соответствующего этой операции предиката должно быть три параметра: первые два — множества, которые нужно объединить, третий параметр — результат объединения двух первых аргументов. В третий аргумент должны попасть все элементы, которые входили в первое или второе множество. При этом нам нужно проследить, чтобы ни одно значение не входило в итоговое множество несколько раз. Такое могло бы произойти, если бы мы попытались, например, воспользоваться предикатом conc (который мы рассмотрели в седьмой лекции), предназначенным для объединения списков. Если бы какое-то значение встречалось и в первом, и во втором списках, то в результирующий список оно бы попало, по крайней мере, в двойном количестве. Значит, вместо использования предиката conc нужно написать новый предикат, применение которого не приведет к ситуации, в которой итоговый список уже не будет множеством за счет того, что некоторые значения будут встречаться в нем более одного раза.

Без рекурсии мы не обойдемся и здесь. Будем вести рекурсию по первому из объединяемых множеств. Базис индукции: объединяем пустое множество с некоторым множеством. Результатом объединения будет второе множество. Шаг рекурсии будет реализован посредством двух правил. Правил получается два, потому что возможны две ситуации: первая — голова первого множества является элементом второго множества, вторая — первый элемент первого множества не входит во второе множество. В первом случае мы не будем добавлять голову первого множества в результирующее множество, она попадет туда из второго множества. Во втором случае ничто не мешает нам добавить первый элемент первого списка. Так как этого значения во втором множестве нет, и в хвосте первого множества оно также не может встречаться (иначе это было бы не множество), то и в результирующем множестве оно также будет встречаться только один раз.

Давайте запишем эти рассуждения:

union([ ],S2,S2). /* результатом объединения

пустого множества со множеством S2

будет множество S2 */

union([H|T],S2,S):–

member3(H,S2),

/* если голова первого

множества H принадлежит второму

множеству S2, */

!,

union(T,S2,S).

/* то результатом S будет

объединение хвоста первого

множества T и второго

множества S2 */

union([H |T],S2,[H|S]):–

union(T,S2,S).

/* в противном случае результатом

будет множество, образованное

головой первого множества H

и хвостом, полученным объединением

хвоста первого множества T

и второго множества S2 */

Если объединить множество [1,2,3,4] со множеством [3,4,5], то в результате получится множество [1,2,3,4,5].

Пример. Теперь можно приступить к реализации операции пересечения двух множеств. Напомним, что пересечение двух множеств — это множество, образованное элементами, которые одновременно принадлежат и первому, и второму множествам. Обозначается пересечение множеств A и B через AB. В математических обозначениях это выглядит следующим образом: AB={x|xA и xB}. На рисунке пересечение множеств A и B обозначено штриховкой.


Рис. 9.2.  Пересечение множеств A и B

У предиката, реализующего эту операцию, как и у предиката, осуществляющего объединение двух множеств, есть три параметра: первые два — исходные множества, третий — результат пересечения двух первых аргументов. В итоговом множестве должны оказаться те элементы, которые входят и в первое, и во второе множество одновременно.

Этот предикат, наверное, будет немного проще объединения. Его мы также проведем рекурсией по первому множеству. Базис рекурсии: пересечение пустого множества с любым множеством будет пустым множеством. Шаг рекурсии так же, как и в случае объединения, разбивается на два случая в зависимости от того, принадлежит ли первый элемент первого множества второму. В ситуации, когда голова первого множества является элементом второго множества, пересечение множеств получается приписыванием головы первого множества к пересечению хвоста первого множества со вторым множеством. В случае, когда первый элемент первого множества не встречается во втором множестве, результирующее множество получается пересечением хвоста первого множества со вторым множеством.

Запишем это.

intersection([],_,[]). /* в результате пересечения

пустого множества с любым

множеством получается пустое

множество */

intersection([H|T1],S2,[H|T]):–

member3(H,S2),

/* если голова первого множества H

принадлежит второму множеству S2 */

!,

intersection(T1,S2,T).

/* то результатом будет множество,

образованное головой первого

множества H и хвостом, полученным

пресечением хвоста первого

множества T1 со вторым

множеством S2 */

intersection([_|T],S2,S):–

intersection(T,S2,S).

/* в противном случае результатом

будет множество S, полученное

объединением хвоста первого

множества T со вторым

множеством S2 */

Если пересечь множество [1,2,3,4] со множеством [3,4,5], то в результате получится множество [3,4].

Пример. Следующая операция, которую стоит реализовать, — это разность двух множеств. Напомним, что разность двух множеств — это множество, образованное элементами первого множества, не принадлежащими второму множеству. Обозначается разность множеств A и B через A–B или A\B. В математических обозначениях это выглядит следующим образом: A\B={x|xA и хB}.

На рисунках разность множеств A и B (B и A) обозначена штриховкой.


Рис. 9.3.  Разность множеств A и B


Рис. 9.4.  Разность множеств В и А

В этой операции, в отличие от двух предыдущих, важен порядок множеств. Если в объединении или пересечении множеств поменять первый и второй аргументы местами, результат останется прежним. В то время как при A={1,2,3,4}, B={3,4,5}, A\B={1,2}, но B\A={5}.

У предиката, реализующего разность, как и у объединения и пересечения, будет три аргумента: первый — множество, из которого нужно вычесть, второй — множество, которое нужно отнять, третий — результат вычитания из первого аргумента второго. В третий параметр должны попасть те элементы первого множества, которые не принадлежат второму множеству.

Рекурсия по первому множеству поможет нам реализовать вычитание. В качестве базиса рекурсии возьмем очевидный факт: при вычитании произвольного множества из пустого множества ничего кроме пустого множества получиться не может, так как в пустом множестве элементов нет. Шаг рекурсии, как и в случае объединения и пересечения, зависит от того, принадлежит ли первый элемент множества, из которого вычитают, множеству, которое вычитают. В случае, когда голова первого множества является элементом второго множества, разность множеств получается путем вычитания второго множества из хвоста первого. Когда первый элемент множества, из которого производится вычитание, не встречается в вычитаемом множестве, ответом будет множество, образованное приписыванием головы первого множества к результату вычитания второго множества из хвоста первого множества.

Запишем эти рассуждения.

minus([],_,[]). /* при вычитании любого множества

из пустого множества получится пустое

множество */

minus([H|T],S2,S):–

member3(H,S2),

/* если первый элемент первого

множества H принадлежит второму

множеству S2*/

!,

minus(T,S2,S).

/* то результатом S будет разность

хвоста первого множества T

и второго множества S2 */

minus([H|T],S2,[H|S]):–

minus(T,S2,S).

/* в противном случае, результатом

будет множество, образованное

первым элементом первого

множества H и хвостом, полученным

вычитанием из хвоста первого

множества T второго множества S2 */

Можно попробовать реализовать пересечение через разность. Из математики нам известно тождество AB=A\(A\B). Попробуем проверить это тождество, записав соответствующий предикат, реализующий пересечение множеств, через взятие разности.

intersection2(A,B,S):–

minus(A,B,A_B), /*A_B=A\B */

minus(A,A_B,S). /* S = A\A_B = A\(A\B) */

Проверка на примерах показывает, что этот предикат, так же, как, впрочем, и ранее созданный предикат intersection, возвращает именно те результаты, которые ожидаются.

Пример. Не помешает иметь предикат, позволяющий проверить, является ли одно множество подмножеством другого. В каком случае одно множество содержится в другом? В случае, если каждый элемент первого множества принадлежит второму множеству. Тот факт, что множество A является подмножеством множества B, обозначается через AB. В математической записи это выглядит следующим образом: ABx(xA xB).

Предикат, реализующий данное отношение, будет иметь два параметра, оба входные. В качестве первого параметра будем указывать множество, включение которого мы хотим проверить. То множество, включение в которое первого аргумента нужно проверить, указывается в качестве второго параметра.

Решение, как обычно, будет рекурсивным. Базис рекурсии будет представлен фактом, утверждающим, что пустое множество является подмножеством любого множества. Шаг рекурсии: чтобы одно множество было подмножеством другого, нужно, чтобы его первый элемент принадлежал второму множеству (проверить это нам позволит предикат

member3, рассмотренный нами ранее в седьмой лекции), а его хвост, в свою очередь, должен быть подмножеством второго множества. Этих рассуждений достаточно, чтобы записать предикат, реализующий операцию включения.

subset([],_). /* пустое множество является

подмножеством любого множества */

subset([H|T],S):– /* множество [H|T] является

подмножеством множества S */

member3(H,S), /* если его первый элемент H

принадлежит S */

subset(T,S). /* и его хвост T является

подмножеством множества S */

Можно также определить это отношение, воспользовавшись уже определенными предикатами union и intersection.

Из математики известно, что ABAB=B. То есть одно множество является подмножеством другого тогда и только тогда, когда их объединение совпадает со вторым множеством. Или, аналогично, ABAB=A. То есть одно множество является подмножеством другого тогда и только тогда, когда их пересечение совпадает с первым множеством.

Запишем эти математические соотношения на Прологе.

subsetU(A,B):–

union(A,B,B). /* объединение множеств

совпадает со вторым множеством */

subsetI(A,B):–

intersection(A,B,A).

/* пересечение множеств

совпадает с первым множеством*/

Проверка на примерах показывает, что оба предиката, как и ранее созданный предикат subset, возвращают именно те результаты, какие и должны возвращать.

Используя только что написанный предикат, реализующий отношение включения множеств, можно создать предикат, осуществляющий проверку совпадения двух множеств. Напомним, что два множества A и B называются равными, если одновременно выполнено AB и BA, т.е. множество A содержится во множестве B и множество B содержится во множестве A. Другими словами, два множества равны, если все элементы первого множества содержатся во втором множестве, и наоборот. Отсюда следует, что эти множества состоят из одних и тех же элементов.

Напишем предикат, реализующий отношение равенства двух множеств.

equal(A,B):– /* множество A совпадает

со множеством B, */

subset(A,B), /* если множество A содержится

во множестве B */

subset(B,A). /* и множество B является

подмножеством множества A*/

Убедимся, что множество [1,2,3] и множество [3,4,5] не равны, а множества [1,2,3] и [2,1,3] совпадают.

Если множество A содержится во множестве B, причем во множестве В имеются элементы, не принадлежащие множеству А, то говорят, что А — собственное подмножество множества В. Обозначается этот факт как AB.

Закодируем это отношение:

Prop_subset(A,B):–

subset(A,B),

/* множество A содержится

во множестве B */

not(equal(A,B)).

/* множества A и B не совпадают*/

Проверим, что множество [1,3] является собственным подмножеством множества [1,2,3], в отличие от множеств [1,4] и [2,1,3].

Пример. Рассмотрим еще одну операцию на множествах. Она называется симметрическая разность и, как видно из ее названия, в отличие от обычной разности, не зависит от порядка ее аргументов. Симметрической разностью двух множеств называется множество, чьи элементы либо принадлежат первому и не принадлежат второму множеству, либо принадлежат второму и не принадлежат первому множеству. Она не столь известна, как предыдущие рассмотренные нами операции, однако тоже имеет право на существование. Обозначается симметрическая разность множеств A и B через A?B. В математических обозначениях это выглядит следующим образом: A?B={x|(xA и xB) или (xB и xA)}. В отличие от обычной разности, в симметрической разности, если поменять аргументы местами, результат останется неизменным (A?B=B?A).


Рис. 9.5.  Симметрическая разность множеств А и В

Например, при A={1,2,3,4}, B={3,4,5}, A?B=B?A={1,2,5}.

Воспользуемся тем, что симметрическую разность можно выразить через уже реализованные нами операции. А именно, A?B=(A\B)(B\A). Словесно эта формула читается так: симметрическая разность двух множеств есть разность первого и второго множеств, объединенная с разностью второго и первого множеств.

Запишем это на Прологе:

Sim_minus(A,B,SM):–

minus(A,B,A_B), /* A_B — это разность

множеств A и B */

minus(B,A,B_A), /* B_A — это разность

множеств B и A */

union(A_B,B_A,SM). /* SM — это объединение

множеств A_B и B_A */

Убедимся, что симметрическая разность множеств [1,2,3,4] и [3,4,5] равна множеству [1,2,5], а симметрическая разность множеств [3,4,5] и [1,2,3,4] равна множеству [5,1,2]. Множество [1,2,5] с точностью до порядка элементов совпадает с множеством [5,1,2]. Таким образом, мы выяснили, что результат не зависит от порядка аргументов.

Пример. Еще одна операция, которую обычно используют при работе со множествами, это дополнение. Дополнением множества обычно называется множество, чьи элементы не принадлежат исходному множеству. Обозначается дополнение множества A через A. В математических обозначениях это выглядит следующим образом: A={x|xA}. Обычно имеет смысл говорить о дополнении только в ситуации, когда имеется некоторое универсальное множество, т.е. множество, которому принадлежат все рассматриваемые элементы. Оно может зависеть от решаемой задачи. Например, в качестве такого множества может выступать множество натуральных чисел, множество русских букв, множество символов, обозначающих арифметические действия и т.д.

Давайте, для определенности, возьмем в качестве универсального множества множество цифр ({0,1,2,3,4,5,6,7,8,9}). Напишем дополнение над этим универсальным множеством.

Воспользуемся при этом очередным тождеством, которое известно в математике. А именно, тем, что A=U\A, где символ U обозначает универсальное множество. Операция разности двух множеств у нас уже реализована.

Закодируем вышеприведенную формулу на Прологе.

supp(A,D):–

U=[0,1,2,3,4,5,6,7,8,9],

minus(U,A,D). /* D — это разность

универсального множества U

и множества A */

Проверяем, что дополнение множества [1,2,3,4] равно множеству [0,5,6,7,8,9].

Имея дополнение, можно выразить операцию объединения через пересечение и дополнение, или, наоборот, операцию пересечения через объединение и дополнение, используя законы де Моргана (AB=AB и AB=AB).

Запишем эти соотношения на Прологе.

unionI(A,B,AB):–

supp(A,A_), /* A_ — это дополнение

множества A */

supp(B,B_), /* B_ — это дополнение

множества B */

intersection(A_,B_,A_B),

/* A_B — это пересечение

множеств A_ и B_ */

supp(A_B,AB). /* AB — это дополнение

множества A_B */

intersectionU(A,B,AB):–

supp(A,A_), /* A_ — это дополнение

множества A */

supp(B,B_), /* B_ — это дополнение

множества B */

union(A_,B_,A_B), /* A_B — это объединение

множеств A_ и B_ */

supp(A_B,AB). /* AB — это дополнение

множества A_B */

Проверка на примерах показывает, что оба предиката работают на множествах, являющихся подмножествами универсального множества (в нашем примере это множество {0,1,2,3,4,5,6,7,8,9}), как и ранее созданные предикаты union и intersection.
.

.

12. РЕАЛИЗАЦИЯ ДЕРЕВЬЕВ В ПРОЛОГЕ
ГРАФ - пара множеств: множество вершин и множество дуг. Различают ориентированные и неориентированные графы. В ориентированном графе каждая дуга имеет направление. Путем называется последовательность вершин, соединенных дугами. Для ориентированного графа направление пути должно совпадать с направлением каждой дуги, принадлежащей пути.

Если из одной вершины достижима другая, то первая называется предком, вторая - потомком.
ДЕРЕВОМ называется граф, у которого одна вершина корневая, остальные вершины имеют только одного отца и все вершины являются потомками корневой вершины.

ЛИСТ - вершина, не имеющая сыновей.

ВЫСОТА - наибольшая длина пути от корня к листу.
Рекурсивное определение бинарного дерева: дерево либо пусто, либо состоит из корня, а также левого и правого поддеревьев, которые в свою очередь также являются деревьями.

В вершинах дерева может храниться информация любого типа.

tree=empty;tr(i,tree,tree)

.

.


13. ФУНКЦИОНАЛЬНЫЙ ПОДХОД ПРОГРАММИРОВАНИЯ.
Функциональным называется программирование при помощи функций в математическом их понимании. Функциональное программирование основано на следующей идее: в результате каждого действия возникает значение, которое может быть аргументом следующего действия. Программы строятся из логически расчлененных определений функций.

Язык LISP (LISt Processing) – язык программирования высокого уровня, разработан в 1961 году Дж. Маккарти. В основе Лиспа лежит функциональная модель вычислений, ориентированная прежде всего на решение задач нечислового характера.
ОСОБЕННОСТИ функционального программирования.

1. Вызов функций является единственной разновидностью действий, выполняемых в функциональной программе.

2. В алгоритмических языках программа является последовательностью операторов, вызовов процедур в соответствии с алгоритмом. В функциональном программировании программа состоит

из вызовов функций и описывает то, что нужно делать и что собой представляет результат решения, а не как нужно действовать для получения результата.

3. Основными методами программирования являются суперпозиция функций и рекурсия.

4. Функциональное программирование есть программирование, управляемое данными. В строго функциональном языке однажды созданные (введенные) данные не могут быть изменены!

5. В алгоритмических языках с именем переменной связана некоторая область памяти, соответствие строго сохраняется в течение всего времени выполнения программы. В функциональном программировании переменная обозначает только имя некоторой структуры, имена символов, переменных, списков, функций и других объектов не закреплены предварительно за какими-либо типами данных. В ФП одна и та же переменная в различные моменты времени может представлять различные объекты.

6. В языках функционального программирования программа и обрабатываемые ею данные имеют единую списочную форму представления.

7. Функциональное программирование предполагает наличие функционалов – функций, аргументы и результаты которых могут быть функциями.
ПРЕИМУЩЕСТВА языков ФП.

- Краткость программы.

- Функциональные программы поддаются формальному анализу легче своих аналогов на алгоритмических языках за счет использования математической функции в качестве основной конструкции.

- Возможность реализации на ЭВМ с параллельной архитектурой.

.

.

14. МЕТОДЫ ОБРАБОТКИ СПИСКОВ (ЛИСП).

Списком в Лиспе называется упорядоченная последовательность S-выражений, заключенная в круглые скобки. Элементы списка отделяются друг от друга пробелами.

Одной из отличительных особенностей Лиспа является единая форма представления данных и программного кода (функций). Для обозначения списка, используемого как данные, и блокировки вычислений в Лиспе определена функция QUOTE (‘).
БАЗОВЫЕ ФУНКЦИИ ОБРАБОТКИ СПИСКОВ.

В Лиспе для построения, разбора и анализа списков существуют простые базовые функции:

1) Функции-селекторы CAR и CDR.

2) Функцию-конструктор CONS.

3) Предикаты ATOM, EQ, EQUAL.
СЕЛЕКТОРОМ называется функция, осуществляющая выборку элемента объекта данных.

Функция CAR возвращает голову списка, CDR - хвост списка. Функции CAR и CDR являются обратными для конструктора CONS.

Путем комбинации селекторов CAR и CDR можно выделять произвольный элемент списка.

КОНСТРУКТОРОМ называется функция, осуществляющая построение объекта данных. Функция CONS строит новый список из переданных ей в качестве аргументов выражения и списка. При этом первый аргумент включается в список-результат в качестве головы, второй – в качестве хвоста.

Функция LIST создает список из произвольных элементов. Вызов list эквивалентен суперпозиции вызовов CONS, причем вторым аргументом последнего вызова является nil, который служит основой для наращивания списка. (list ‘a ‘b ‘c) эквивалентно (cons ‘a (cons ‘b (cons ‘c nil))).

Для выборки элементов списков в Лиспе существуют функции выделения заданного элемента : FIRST, SECOND, THIRD, FOURTH, ... last и более общая функция NTH, выделяющая n-й элемент списка (nth n список).
ПРЕДИКАТАМИ в функциональном программировании называются функции, которые проверяют выполнение некоторого условия и возвращают логическое значение T или NIL.

ATOM, EQ и EQUAL являются базовыми предикатами Лиспа. С их помощью и используя другие базовые функции, можно задавать более сложные предикаты, которые будут проверять наличие более сложных свойств.

Предикат ATOM проверяет, является ли аргумент атомом.

Предикат EQ проверяет тождественность двух атомарных выражений.

Предикат EQUAL проверяет тождественность произвольных выражений.

.

.

15. ОПРЕДЕЛЕНИЕ УНИВЕРСАЛЬНОЙ ФУНКЦИИ.


.

.

16. ПРЕДИКАТЫ И ИСТИННОСТЬ В ЛИСПЕ.

Хотя формальное правило записи программ вычислений в виде S-выражения предписывает, что константа Т — это (QUOTE T), было оговорено, что в системе всегда пишется Т. Кроме того, Nil оказался удобнее, чем атом F, встречавшийся в начальных предложениях по Лиспу аналог значения FALSE. Программист может либо принять это правило на веру, либо изучить следующие уточнения.

В Лисп есть два атомных символа, которые представляют истину и ложь, соответственно. Эти два атома — T и NIL. Данные символы — действительные значения всех предикатов в системе. Главная причина в удобстве кодирования. Во многих случаях достаточно отличать произвольное значение от пустого списка.

Формального различия между функцией и предикатом в Лиспе не существует. Предикат может быть определен как функция со значениями либо T либо NIL. Это верно для всех предикатов системы. Можно использовать форму, не являющуюся предикатом там, где требуется предикат: предикатная позиция условного выражения или аргумент логической операции. Семантически любое S-выражение, отличного от NIL, будет рассматриваться в таком случае как истинное. Первое следствие из этого — предикат Null и логическое отрицание Not идентичны. Второе — то, что (QUOTE T) или (QUOTE Х) практически эквивалентны Т как константные предикаты.

Предикат EQ ведет себя следующим образом:

1. Если его аргументы различны, значением EQ является NIL.

2. Если оба его аргументы являются одним и тем же атомом, то значение — Т.

3. Если значения одинаковы, но не атомы, то его значение T или NIL в зависимости от того, идентично ли представление аргументов в памяти.

4. Значение EQ всегда T или NIL. Оно никогда не бывает не определено, даже если аргументы неправильные.

.

.

17. ОТОБРАЖЕНИЯ И ФУНКЦИОНАЛЫ
Аргумент, значением которого является функция, называют в функциональном программировании ФУНКЦИОНАЛЬНЫМ АРГУМЕНТОМ, а функцию, имеющую функциональный аргумент - ФУНКЦИОНАЛОМ.

Одним из основных типов функционалов являются функции, которые позволяют вызывать другие функции, иными словами, применять функциональный аргумент к его параметрам. Такие функционалы называют аппликативными (применяющими) функционалами.
Программирование отображений и использование функционалов демонстрируется как метод резкого повышения производительности программирования и эффективности отладки программ.

Отображения структур данных и функционалы


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

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

Говорят, что отображение существует, если задана пара множеств и отображающая функция, для которой первое множество - область определения, а второе - область значения. При определении отображений, прежде всего, должны быть ясны следующие вопросы:

Это позволяет задать порядок перебора множества и метод передачи аргументов для вычисления отображающей функции. При обходе структуры, представляющей множество, отображающая функция будет применена к каждому элементу множества.

Проще всего выработать структуру множества результатов, подобную исходной структуре. Но возможно не все полученные результаты нужны или требуется собрать их в иную структуру, поэтому целесообразно прояснить заранее еще ряд вопросов:

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


18. ИМЕНА, ОПРЕДЕЛЕНИЯ И КОНТЕКСТЫ В ЛИСП

19. PROG ВЫРАЖЕНИЯ И ЦИКЛЫ В ЛИСП
  1   2


2. Алгоритмы унификации
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации