Сортировка фактов пролога


Содержание

Сортировка выбором

Встречал темы, где сортировка выбором осуществляется с применением предиката min.
Там элемент добавляется в начало списка путем добавления головы к телу.
У меня задача иная. Сортировка выбором но используя maх, и добавление элемента в конец списка.

По частям есть, но как слепить все это воедино?

15.03.2020, 19:10

Сортировка выбором, сортировка вставкой, сортировка заменой, сортировка обменом («пузырьковая» сортировка)
Создать класс, содержащий массив и реализующий алгоритмы сортировки и бинарного поиска в этом.

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

Сортировка выбором
Сортируем массив так:найти мин элемент,который копируем в первую ячейку другого массива,и снова.

Сортировка выбором (2 в 1)
Пишу вот сортировку. выбором Должна быть по возрастанию и убыванию.. ! имеем две функции.

16.03.2020, 09:43 2

Решение

Но это странное требование, ведь добавление в конец, а не в начало списка ОЧЕНЬ снижает эффективность..

Добавлено через 7 минут
Если обязательным условием является только использование максимума, то можно уйти от добавления в конец через накопление:

16.03.2020, 09:43

Сортировка выбором
С клавиатуры вводится последовательность целых знаковых 16-битных чисел, заканчивающихся нулем.

Сортировка выбором
Здравствуйте товарищи. Есть к вам одни вопрос. Есть задание- . Дана целочисленная квадратная.

Сортировка выбором
Добрый день, я заметил, что при сортировке массива из N элементов по алгоритму сортировки.

лабы по информатике, егэ

лабораторные работы и задачи по программированию и информатике, егэ по информатике

Prolog урок 2. Базы фактов, цели и запросы

Нормальная форма Бэкуса-Наура

Для начала вспомним нормальную форму Бэкуса-Наура (БНФ), которая была создана для формального описания синтаксиса языков программирования в 1960 году. Ее авторы — Джон Бэкус и Питер Наур.

Итак, в БНФ приняты следующие обозначения:

Символ ::= читаемый как «по определению» («это», «есть»). Слева от символа располагается объясняемое понятие, справа — разъясняющая конструкция. Например,

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

Символ | означает логическое «или» и применяется для разделения различных равнозначных альтернативных объяснений определяемого понятия.

Используя данный символ можно, например, определить десятичную цифру:

Если часть конструкции заключена в квадратные скобки [] , то это означает, что она является необязательной, т.е. может отсутствовать.

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

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

Снова определим положительное целое число, используя нотацию БНФ :

Что означает, что положительное целое число состоит из одной или нескольких цифр.

Структура программы на языке Prolog

Стандартная программа на языке Prolog состоит из следующих разделов:

    Constants

Необязательный раздел определения констант.

Domains

Раздел описания доменов (аналогичен описанию типов данных).

Раздел описания предикатов (аналогичен разделу описания процедур и функций); по сути представляет собой шаблон написания фактов в разделе Clauses.

Clauses

Утверждения (аналог: тело основной программы).

Goal

Целевое утверждение – «цель».

domains a=symbol predicates likes (a,a) clauses likes (mary,apples).

Перейдите в окно Dialog (меню Run ) и введите запрос:

В результате в окне должен появиться ответ true

Факты и правила

Часто программу, написанную на Прологе, называют базой знаний.

Предложения-правила имеют вид:

Где A — это заголовок или голова предложения, а B1. Bn – это тело.

Факт обычно утверждает, что между объектами выполнено некоторое отношение и состоит из:

  • отношения
  • объекта или объектов, заключенных в круглые скобки (аргументы)
  • завершается точкой (.)

Пример факта:

likes (bill, dogs).

где likes — факт
bill , dogs — аргументы факта, между которыми выполнено отношение ( likes )

Т.к. отношение в математической логике принято называть предикатами, то и мы иногда будем использовать понятие «предикат» вместо «факта» или «правила».

Если факт состоит только из заголовка, то можно сказать, что факт – это предложение, у которого тело пустое.

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

Отличие константы от переменной: константа получает свое значение в разделе описания констант, тогда как переменная инициализируется в процессе работы программы.

В следующем примере наводите курсор на части конструкций, и появится подсказка:

likes (bill, dogs). — Билл любит собак.
bird (vorobej). Птица – воробей.

Таким образом, в примере likes — это имя двухаргументного предиката (факта), у которого строковая константа « bill » является первым аргументом, а « dogs » — вторым аргументом.

domains a=symbol b=integer predicates age(a,b) clauses age(. ). . (. ). . (. ).

Наберите код программы в компиляторе.

Цель — это формулировка задачи, которую программа должна решить. Цель также служит «триггером» для запуска программы.

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

  1. Если цель является фактом, то Турбо-Пролог отвечает True (истина) или False (ложь):

Дословно: Мэри любит яблоки.

  1. Если цель содержит переменные, то Турбо-Пролог выдает те их значения, которые приводят к решению:

Дословно: Что любит Мэри?

Так, наш пример может быть как фактом, так и целью:

likes(mary,apples). — Мэри любит яблоки и Любит ли Мэри яблоки?

Алгоритм составления программы

Программа для компилятора TProlog состоит из разделов, рассмотренных в примере:

Описание доменов

predicates likes (a,a)

Раздел предикатов
Предикат – это логическая формула от одного или нескольких аргументов

clauses likes (mary,apples). likes(mary,oranges). color(apples,red).

goal likes(mary,X),write(«mary lyubit «, X).

Результатом примера будет: «mary lyubit apples».

В данном примере цель записана в виде раздела GOAL прямо в программе, но нужно иметь в виду, что чаще всего цели, требующие логический ответ (правда или ложь), записываются в окне Dialog (goal в программе тогда не пишется)

Бесконечный цикл

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

clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write(«mary lyubit «, X).

Результат выдает только apples . Хотя еще есть oranges.

goal likes(mary,X),write(«mary lyubit «, X),nl,fail.

nl — означает переход на следующую строку (каждое значение выводится с новой строки).
Результат:
«mary lyubit apples».
«mary lyubit oranges».

Код программы целиком:

domains a=symbol predicates likes (a,a) clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write(«mary lyubit «, X),nl,fail.

Рассмотрим еще один пример.

Код программы без запросов:

domains a=symbol predicates построил (a,a) хранится (a,a) ворует (a,a) ловит (a,a) треплет (a,a) доит (a,a) бранится (a,a) будят (a,a) clauses построил (джек,дом). хранится (пшеница, чулан_дома). ворует (птица_синица, пшеница). ловит (кот, птица_синица). треплет (кот, птица_синица). треплет (пес, кот). доит (старушка, корова). бранится (пастух, старушка). будят (два_петуха, пастух).

? — построил (Х, дом). /*Кто построил дом?*/

? – ловит (кот, Y) /*Кого ловит кот?*/

Ответ: Y= птица_синица

? – бранится (X,Y). /*Кто с кем бранится?*/

Ответ: X =пастух, Y= старушка

? – хранится (X, чулан_дома), ворует (X,Y). /*Что хранится в чулане дома и кто ворует это */

Ответ: X = пшеница, Y= птица_синица

Выполнение запросов в разделе Goal:

  1. Составить базу данных «Именины и хобби друзей».
  2. Составить запросы к базе данных, исходя из приведенных ниже:
  • чьи именины в сентябре?
  • когда именины у Ивана?
  • кто любит танцы?

  • кто любит книги и спорт?
  • что любит Петр?

domains a=symbol b=integer predicates birthday(a,b,a) likes(a,a) clauses birthday(nataly, 8, september). birthday(yana, 25, august). birthday(nina, 28, september). birthday(peter, 2, august). birthday(ivan, 12, august). likes(nataly, books). likes(nataly, sport). likes(yana, books). likes(yana, dances). likes(peter, music). likes(peter, dances). likes(ivan, sport). likes(ivan, books). Goal /* birthday(X,Y,september),write(X,» rodilas «, Y, » sentyabrya»),nl,fail.*/ … , write(…), nl, fail.

* Для удобства после выполнения очередного запроса, комментируйте его ( /* . */ ) и приступайте к написанию кода следующего запроса.

  1. Составить базу данных «Предметы и преподаватели», содержащую информацию о названии предмета, должности и фамилии преподавателя, номер семестра, отчетность.
  2. Составить запросы к базе данных, исходя из приведенных ниже:
  • по каким предметам экзамен?
  • какой предмет и когда читает доцент морозов?
  • какая отчетность по тои?
  • кто и когда читает ПРЗ?

domains a=symbol b=integer predicates teach(a,a,a,b) vedomost(a,a) clauses teach(prz, assistent,ivanova,2 ). teach(toi, docent, morozov,4). teach(mpi,docent, petrova, 5). vedomost(toi, exam). vedomost(prz, zach). vedomost(mpi, exam). Goal /* vedomost(X,exam) ,write(«exam po predmetu «, X),nl,fail. */ … , write(…), nl, fail.

* Для удобства после выполнения очередного запроса, комментируйте его ( /* . */ ) и приступайте к написанию кода следующего запроса.

Сортировка факты в Прологе

Как я могу сортировать факты о своей переменной Like

Студент (5). Студент (3). Студент (2). Студент (3). Студент (6).

Я хочу сделать функцию, чтобы сделать их

Студент (2). Студент (3). Студент (3). Студент (5). Студент (6).

Я бы сначала собрать все эти факты в список с помощью FindAll (пример: Как создать список из фактов в Прологе ), а затем отсортировать этот список (например: Сортировка списка в Прологе , или просто использовать встроенный вид / 2 предикат).

(Отправленные с телефона)

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

Затем, несколько вещей, которые вы можете сделать:

(Как это было предложено в другом ответе)

Если вы хотите , чтобы они на самом деле отсортированы в базе данных, и не боится изменить базу данных во время выполнения, вы можете удалить все student/1 из базы данных с abolish/1 и повторно вставить отсортированные факты:

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

ГЛАВА 7. ЕЩЕ НЕСКОЛЬКО ПРИМЕРОВ ПРОГРАММ

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

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

7.1. Словарь в виде упорядоченного дерева

Предположим, что мы хотим установить отношения между элементами информации с тем, чтобы использовать их, когда потребуется. Например, толковый словарь ставит в соответствие слову его определение, а словарь иностранного языка ставит в соответствие слову на одном языке слово на другом языке. Мы уже познакомились с одним способом составления словаря: с помощью задания фактов. Если нам нужно составить таблицу выигрышей на скачках, проводившихся на Британских островах в течение 1938 г., то мы можем просто определить факты вида выигрыши(Х, Y), где X — кличка лошади, a Y – количество гиней (денежных единиц), выигранных этой лошадью. Следующая база данных может рассматриваться как часть этой таблицы:

Если мы хотим узнать, какую сумму выиграла лошадь по кличке maloja, нам нужно просто правильно построить вопрос и Пролог даст нам ответ:

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

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

Упорядоченное дерево состоит из некоторого числа структур, называемых узлами, причем каждому входу словаря соответствует один узел. Каждый узел содержит четыре компоненты. Сюда входят два связанных с узлом элемента данных, как в предикате выигрыши в вышеприведенном примере. Один из этих элементов называется ключом, его имя определяет место в словаре (кличка лошади в нашем примере). Другой элемент используется для хранения какой-либо другой информации о данном объекте (сумма выигрыша в нашем примере). Кроме того, каждый узел содержит ссылку (наподобие ссылки на хвост списка) на узел со значением ключа, которое лексикографически (по алфавиту) меньше, чем имя, являющееся ключом данного узла, а также еще одну ссылку на узел со значением ключа лексикографически большим, чем имя, являющееся ключом данного узла. Будем использовать структуру, которую обозначим как в(Л,В,М, Б) (в — сокращение от «выигрыши»), где Л – кличка лошади (атом), используемая в качестве ключа, В – сумма выигрыша в гинеях (целое), М – структура, соответствующая лошади, кличка которой меньше, чем та, что хранится в Л, а Б – структура, соответствующая лошади, кличка которой больше, чем значение в Л. Когда для М и Б нет соответствующих структур, мы не будем их конкретизировать. Для небольшого множества лошадей указанная структура, будучи записанной в виде дерева, могла бы иметь вид, как представлено на рис. 7.1.

Если записать ее на Прологе в ступенчатом виде, учитывая ширину страницы, то она могла бы выглядеть так:

Теперь, располагая такой структурой, мы хотим «просмотреть» ее по кличкам лошадей, чтобы узнать их выигрыши в течение 1938 г. Как и раньше, структура должна иметь формат в(Л,В,М, Б). Условие окончания поиска состоит в том, что кличка искомой лошади должна совпасть с Л. В этом случае поиск удачен и не требуется пробовать другие варианты. В противном случае мы должны использовать предикат меньше, определенный в гл. 3, чтобы определить, какую из «ветвей» дерева, М или Б, нужно рекурсивно просмотреть. Мы используем эти принципы при определении предиката искать, причем искать(Л,Т, Г) означает, что лошадь Л, если она найдена в таблице Т (которая организована в виде структуры формата в), выиграла Г гиней:

искать Л, в(Л1,_,До,_),Г):-меньше(Л,Л1),искать(Л,До,Г).

искать(Л, в(Л1,_,_,После),Г):- not (меньше(Л,Л1)), искать(Л,После,Г).

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

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

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

привел бы к тому, что значение переменной X стало упорядоченным деревом из двух вхождений.

Понять то, каким образом искать одновременно выполняет и создание и выборку компонент, можно на основе тех знаний о Прологе, которыми вы уже располагаете; мы настоятельно рекомендуем разобраться в этом самостоятельно. Подсказка: если искать(Л,Т, Г) используется в конъюнкции целей, то «изменения» в структуре Т сохраняются только в области определения Т.

Упражнение 7.1. Поэкспериментируйте с предикатом искать, чтобы установить, какие различия будут в словаре, если элементы в него вставлять каждый раз в разном порядке. Например, как будет выглядеть дерево словаря, если вставлять его элементы в таком порядке: massinga, braemar nettleweed, panorama? А если в таком порядке: adela, braemar, nettleweed, massinga?

7.2. Поиск в лабиринте

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

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

Этот метод нуждается в некоторых уточнениях, но мы сделаем их позднее, при обсуждении проблем поиска на графе. А сначала давайте запишем по порядку наши шаги, чтобы знать, какие задачи предстоит решать:

1. Подойти к двери какой-либо комнаты. Если номер комнаты есть в нашем списке, то перейти к шагу 1.

2. Если в поле зрения нет ни одной комнаты, то «вернуться назад» через ту комнату, через которую мы прошли сюда, и посмотреть, нет ли возле нее каких-либо других комнат.

3. Иначе дописать номер комнаты к нашему списку.

4. Поискать телефон в этой комнате.

5. Если телефона нет, то перейти к шагу 1. Иначе мы останавливаемся, и наш список содержит путь, который мы прошли, чтобы попасть в нужную комнату.

Будем считать, что номера комнат являются константами (безразлично целыми числами или атомами). Сначала мы можем решить, как просматривать номера комнат, записанные на листке бумаги. Для этого можно использовать предикат принадлежит, определенный в разд. 3.3, полагая, что содержимое листка бумаги представлено в виде списка. Теперь мы можем продвинуться в решении задачи поиска в лабиринте. Рассмотрим небольшой пример, где задан план дома, комнаты которого помечены буквами (см. рис. 7.2). Заметим, что просветы в стенах обозначают двери и что комната а – это просто представление пространства вне дома. Имеются двери, ведущие из а в b, из с в d, из f в е, и так далее. Сведения о том, где имеются двери, могут быть представлены в виде фактов Пролога:

Заметим, что информация о наличии дверей не избыточна. Например, мы сказали, что имеется дверь, ведущая из комнаты g в комнату е, но не сказали, что имеется дверь, ведущая из комнаты е в комнату g, т. е. мы не зафиксировали утверждение д(e,g). Чтобы обойти эту проблему представления двухсторонних дверей, мы могли бы повторно записать д-факт для каждой двери с перестановкой аргументов. Или мы могли бы устроить программу таким образом, чтобы она понимала, что каждая дверь фактически может рассматриваться как двухсторонняя. Этот вариант мы и выбрали в нижеследующей программе.

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

• мы находимся в той комнате, которая нам нужна, или

• мы должны войти в дверь и распознать эти случаи снова (рекурсивно).

Рассмотрим целевое утверждение переход(X,Y,T), которое доказуемо (согласуется с базой данных), если можно перейти из комнаты X в комнату Y. Третий аргумент Т – это наш листок бумаги, который мы носим с собой и на котором записан перечень номеров комнат, в которых мы побывали до сего момента.

Граничное условие перехода из комнаты X в комнату Y состоит в том, что, возможно, мы уже находимся в комнате Y (т. е., возможно, X есть Y). Это условие представлено в виде утверждения:

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

переход(Х, Y,T,):- Д(Х,Z),not(принадлежит(Z,Т)), переход(Z,Y,[Z|T]).

Словами это может быть выражено так: для того чтобы «перейти» из X в Y, не проходя через комнаты из списка Т, надо найти дверь из X куда-либо (т. е. в Z), убедиться, что Z еще не занесена в список Т, и «перейти» из Z в Y, используя список Т с дописанной в него Z.

При использовании этого правила существуют три возможности возникновения ошибки: во-первых, если в X вообще нет двери. Во-вторых, если дверь, которую мы выбрали, уже есть в списке. В-третьих, если «переход» в комнату Z приведет в тупик на следующих уровнях. Если первое целевое утверждение д(X, Z) не согласуется с базой данных, то и данное целевое утверждение переход также недоказуемо. На «самом верхнем» уровне (не рекурсивный вызов) это означает, что из X в Y нет пути; на более глубоких уровнях это означает, что мы должны сделать «шаг назад» и поискать другую дверь.

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

переход(X,Y,T):- д(X,Z), not(принадлежит(Z,Т)),переход(Z,Y[Z|T]). переход(Х,Y,T):- д(Z,Х), not(принадлежит(Z,Т)),пeреход(Z,Y,[Z|T]).

Или, используя предикат ‘;’ (обозначающий дизъюнкцию), можно записать:

переход(Х,Y,T):- (д(Х,Z); д(Z,Х)), not(принадлежит (Z,T)),пepexод(Z,Y,[Z|T]).

Теперь о том, как найти телефон. Рассмотрим целевое утверждение есть_телефон(X), которое согласуется с базой данных, если в комнате X есть телефон. Если мы хотим сказать, что в комнате g есть телефон, то мы просто записываем в нашу базу данных факт есть_телефон(g). Предположим, мы начали поиск с комнаты а. Один из способов узнать дорогу к телефону – это задать вопрос:

Это – вопрос типа «создать и проверить», который находит достижимые комнаты и затем проверяет наличие в них телефона. Другой способ – это найти сопоставление сначала для предиката есть_телефон(Х), а затем попробовать перейти из комнаты а в X:

Последний метод более эффективен, однако он подразумевает что мы «знаем», где телефон, еще до того, как начали поиск.

Начальная установка третьего аргумента пустым списком означает, что мы начинаем поиск, имея чистый лист бумаги. Изменяя эту начальную установку, можно получить разные варианты поиска. Вопрос «найти телефону не заходя в комнаты d и f» можно выразить на Прологе так:

?- есть_телефон(X), переход (a,X,[d,f]).

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

Упражнение 7.2. Допишите вышеприведенную программу так, чтобы она печатала такие сообщения, как «входим в комнату X» и «телефон найден в комнате Y», подставляя в них соответствующие номера комнат.

Упражнение 7.3. Может ли эта программа находить альтернативные пути? Если да, то где нужно «отсечь», чтобы избежать нахождения более чем одного пути?

Упражнение 7.4. Чем определяется порядок, в котором просматриваются комнаты?

7.3. Ханойские башни

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

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

• Граничное условие выполняется в случае, когда на исходном (левом) штыре нет дисков.

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

• Переместить один диск с исходного штыря на итоговый штырь. В этом месте наша программа будет выдавать сообщение об этом перемещении.

• Наконец, переместить N-1 дисков с запасного на итоговый, используя исходный штырь в качестве запасного.

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

xaной(N):- переместить(N, левый,средний,правый).

переместить(N, А,В,С):-М is N-1,переместить(М,А,С,В),сообщить(А,В), переместить(М,С,В,А).

7.4. Справочник комплектующих деталей

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

Организация базы данных справочника сходна с тем, что описано в гл. 3. Сборочный узел представлен в виде списка структур вида чис(X, Y), где X – это имя некоторой детали (простой детали или узла), a Y – необходимое количество таких деталей. Ниже перечислены все предикаты измененной программы с указанием их назначения:

Деталиузла(А): выдает на печать список всех простых деталей, требующихся для сборки узла А, и количество каждой детали.

Деталиузлов(N,X,P): P — это список структур чис(Дет, Кол), где Дет — это название детали, а Кол — это количество таких деталей, требующихся для сборки каждого из экземпляров узлов X. N — целое, а X – атом, представляющий название некоторой детали.

Деталировка(N,S,Р): Р — это, как и выше, список структур чис, требующихся для сборки всех узлов, представленных элементами списка S; N задает число экземпляров списка S, N – целое; S – список структур чис.

Собрать(Р, А): Р и А – списки структур чис. А – это список, составленный из тех же элементов, что и Р, но без повторений одной и той же детали. Причем количество каждой детали, указанное в списке А, совпадает с суммой всех повторений этой детали в списке Р. Предикат собрать мы используем для того, чтобы собрать несколько описей наборов одинаковых деталей в одну опись. Например, 3 винта, 4 шайбы и 4 винта собираются вместе, давая 7 винтов и 4 шайбы.

Дособрать(Х,М, L,O,N) : L и О — это списки структур, чис, О – это список всех элементов списка L, в состав которых не входит деталь X; X – это атом, задающий название некоторой детали; N – это общее количество X в списке L, сложенное с М; М – это целое число, которое используется для суммирования количеств X в L и передается как аргумент в каждом вызове дособрать. При выходе из рекурсии, который обеспечивается выполнением граничного условия, М возвращается как N.

Вывдеталейузла(Р): Р – это список структур чис, который выдается на печать по одной структуре на строке вывода. Цель put(9) выводит литеру с кодом ASCII=9, что соответствует горизонтальной табуляции. С предикатом присоединить мы уже неоднократно встречались ранее.

Полностью Пролог-программа выглядит так:

деталиузла(Т):-деталиузлов(1,Т,Р), co6paть(P,Q), вывдеталейузла(Q).

деталиузлов(N,Х, [чис(Х,N)]):- деталь(Х).

деталировка(N, [чис(Х, Число) |L],T):-М is N * Число, деталиузлов(М,Х,Хдетали),деталировка (N, L,Остдетали,Т),присоединить(Хдетали,Остдетали,Т).

дособрать(Х,N,[чис(Х,Число)|Oст],Прочие,Nитог):-!,М is N+Число, дособрать(Х,М,Ост,Прочие,Nитог).

дособрать(Х,N,[Друг|Ост],[Друг|Прочие],Nитог):-дособрать(Х, N, Ост, Прочие, Nитог).

7.5. Обработка списков

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

Нахождение последнего элемента списка: Цель последний(X, L) согласуется с базой данных, если элемент X является последним элементом списка L. Граничное условие выполняется, когда список L содержит только один элемент. Это условие проверяется первым правилом. Второе правило задает общий рекурсивный случай:

Проверка порядка следования элементов: Цель следомза(Х, Y, L) согласуется с базой данных, если элементы X и Y являются последовательными элементами списка L. Особенности работы переменных допускают, чтобы или X, или Y, или обе переменные были неконкретизированы перед попыткой согласовать цель. В первом утверждении, которое проверяет граничное условие, должно быть также предусмотрено, что после X и Y в списке могут быть другие элементы. Этим объясняется появление анонимной переменной, в которой сохраняется хвост списка:

Объединение списков: С приводимым примером мы уже встречались ранее в разд. 3.6. Цель присоединить(X, Y, Z) согласуется с базой данных в том случае, если Z – это список, построенный путем добавления Y в конец X. Например,

Определение предиката присоединить выглядит следующим образом:

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


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

Обращение списка: Цель обр(L,M) согласуется с базой данных, если результат перестановки в обратном порядке элементов списка L есть список М. В программе используется стандартный прием, когда обращенный список получается присоединением его головы к обращенному хвосту. Лучший способ обратить хвост – это использовать сам обр. Граничное условие выполняется тогда, когда первый аргумент сократился до пустого списка, в этом случае результатом также является пустой список:

обр([Н|Т],L):- обр(T,Z), присоединить(Z,[Н],L).

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

Второй аргумент обрдоп используется для хранения «текущего результата». Каждый раз, когда выявляется новый фрагмент результата (X), передаваемый в остальную часть программы, «текущий результат» представляет из себя старый «текущий результат», дополненный новым фрагментом X. В самом конце последний «текущий результат» возвращается в качестве результата исходного целевого утверждения. Аналогичный прием используется в разд. 7.8 при определении предиката имя_целого.

Исключение одного элемента: Цель исключ1(Х, Y,Z) исключает первое вхождение элемента X из списка Y, формируя новый сокращенный список Z. Если в списке Y нет элемента X, то целевое утверждение недоказуемо. Граничное условие выполняется тогда, когда мы находим искомый элемент X, иначе осуществляется рекурсивная обработка хвоста списка Y:

Легко добавить утверждение, которое обеспечит доказательство предиката, когда второй аргумент сократится до пустого списка. Это утверждение, реализующее новое граничное условие, есть исключ1(_,[],[])-

Исключение всех вхождений некоторого элемента; Цель исключить(Х, L1, L2) создает список L2 путем удаления всех элементов X из списка L1. Граничное условие выполняется тогда, когда L1 является пустым списком. Это означает, что мы рекурсивно исчерпали весь список. Если X находится в голове списка, то результатом является хвост этого списка, из которого X тоже удаляется. Последний случай возникает, если во втором аргументе обнаружено, что-то отличное от X. Тогда мы просто входим в новую рекурсию.

Замещение: Этот предикат очень напоминает исключить, с той лишь разницей, что вместо удаления искомого элемента мы заменяем его некоторым другим элементом. Цель заменить(Х, L,A,M) строит новый список М из элементов списка L, при этом все элементы X заменяются на элементы А. Здесь возможны 3 случая. Первый, связанный с граничным условием, в точности совпадает с тем, что было в исключить. Второй случай – когда в голове второго аргумента содержится элемент X, а третий – когда там содержится нечто отличное от X:

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

подсписок[[собрание, членов, клуба],[общее, собрание, членов, клуба, будет, созвано, позже]).

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

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

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

7.6. Представление и обработка множеств

Множество — одна из наиболее важных структур данных, используемых как в математике, так и в программировании. Множество – это набор элементов, напоминающий список, но отличающийся тем, что вопрос о том, сколько раз и в каком месте что-либо входит в множество в качестве его элемента, не имеет смысла. Так, множество (1, 2, 3) – это то же самое множество, что и (1, 2, 3, 1), поскольку значение имеет только сам факт, принадлежит данный элемент множеству или нет. Элементами множеств могут также быть другие множества. Самой фундаментальной операцией над множествами является определение того, принадлежит некоторый элемент данному множеству или нет.

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

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

Принадлежность множеству: X∈Y

X принадлежит некоторому множеству Y, если X является одним из элементов Y.

Множество Y включает в себя множество X, если каждый элемент множества X является также элементом Y. Множество Y может содержать некоторые элементы, которых нет в X.

Пересечением множеств X и Y является множество, содержащее те элементы, которые одновременно принадлежат X и Y.

Объединением множеств X и Y является множество, содержащее все элементы, принадлежащие X или Y или одновременно им обоим.

Это – основные операции, которые обычно используются при работе с множествами. Теперь мы можем приступить к написанию Пролог-программ, реализующих каждую из них. Первая основная операция ‘принадлежность’ реализуется тем же самым предикатом принадлежит, с которым мы уже встречались несколько раз. Однако в нашем определении принадлежит в граничном случае нет символа «отсечения», поэтому мы можем создавать последовательные элементы списка, используя возвратный ход:

Илон Маск рекомендует:  Что такое код farrealloc

Следующая операция ‘включение’ реализуется предикатом включает, причем включает(Х, Y) завершается успешно, если X является подмножеством Y, т. е. Y включает X. Второе утверждение в его определении опирается на математическое соглашение о том, что пустое множество является подмножеством любого множества. В Прологе это соглашение дает способ проверки граничного условия для первого аргумента, поскольку запрограммирована рекурсивная обработка его хвоста:

включает([А|Х],Y):- принадлежит(А,Y), включает(Х,Y).

Следом идет самый сложный случай, реализация пересечения. Целевое утверждение пересечение(Х, Y,Z) доказуемо, если пересечением X и Y является Z. Это как раз тот случай, когда используется предположение, что данные списки не содержат повторяющихся элементов:

пересечение([X|R],Y,[X|Z]):-принадлежит(Х, Y). пересечение(R, Y,Z).

пересечение([Х|R],Y,Z):- пересечение(R, Y,Z).

Наконец, объединение. Целевое утверждение объединение (X,Y,Z) доказуемо, если объединением X и Y является Z. Заметим, что реализация предиката объединение сконструирована на основе определений предикатов пересечение и присоединить:

объединение(R,Y,Z). объединение([X |R],Y,[X|Z]):- объединение(R,Y,Z).

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

7.7. Сортировка

Иногда полезно упорядочить список элементов в соответствии с заданным порядком их следования. Если элементами списка являются целые числа, то для того чтобы определить соблюден ли порядок следования, можно использовать предикат ‘‹’. Список (1, 2, 3) упорядочен, поскольку любая пара соседних целых чисел этого списка удовлетворяет предикату ‘‹’. Если элементами списка являются атомы, то мы можем воспользоваться предикатом меньше, о чем уже говорилось в гл. 3. Список [alpha,beta,gamma] упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату меньше.

Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через ‘‹’ меньше или любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y) доказуемо, если объекты X и Y удовлетворяют требуемому порядку следования, т. е. если X в некотором смысле меньше чем Y.

Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:

перестановка(L,[H|T]):-присоединить(V,[Н|U],L), присоединить(V,U,W), перестановка(W,Т).

Используемый здесь предикат присоединить многократна определялся ранее. В этой программе предикаты имеют следующий смысл:

Наивсорт(L1, L2) означает, что L2 – это список, являющийся упорядоченной версией списка L1;

Перестановка(L1, L2) означает, что L2— это список, содержащий все элементы списка L1 в одном из многих возможных порядков их следования; в терминологии разд. 4.3 – это генератор.

Предикат отсортировано(L) означает, что числа в списке L упорядочены в порядке возрастания; это – ‘контролер’.

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

При сортировке включением каждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Этот метод используется, например, при игре в карты, когда игрок сортирует имеющиеся на руках карты, вынимая и переставляя по одной карте за раз. Целевое утверждение вклюсорт(X, Y) доказуемо тогда, когда список Y является упорядоченной версией списка X. Каждый элемент удаляется из головы списка и передается предикату вклюсорт2, который включает этот элемент в список и возвращает измененный список.

вклюсорт([Х|L],М):- вклюсорт(L,N), вклюсорт2(Х,N,М).

вклюсорт2(Х,[А|L],[А|М]):- упорядочено(А,Х). вклюсорт2(Х,L,М).

Чтобы сделать предикат сортировки включением более универсальным, удобно задавать предикат проверки порядка следования в качестве аргумента предиката вклюсорт. Используем для этого предикат ‘ =..’, который рассматривался в гл. 6:

Теперь мы можем использовать такие цели как вклюсорт(А,В,’‹’) и вклюсорт(А,В,меньше), т. е. отпадает необходимость в предикате упорядочено. Этот метод может быть распространен.и на другие алгоритмы сортировки данного раздела.

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

пусорт(L,S):-присоединить(Х,[А,В|Y],L),упорядочено(В,А),присоединить(Х, [В, А|Y],M),пусорт(M,S).

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

Быстрая сортировка — это более сложный метод сортировки, предложенный Хоором и применимый для сортировки больших списков. Для реализации быстрой сортировки на Прологе мы должны сначала разделить список, состоящий из головы Н и хвоста Т, на два списка L и М такие, что:

• все элементы L меньше или равны Н;

• все элементы М больше чем Н;

• порядок следования элементов в L и М такой же как в [Н |Т].

После того, как мы разделили список, применяем быструю сортировку к каждому из полученных списков (это рекурсивная часть), и присоединяем М к L Цель разбить(H,T,L,M) разделяет список [Н |Т] на списки L и М, как сказано выше:

paзбить(H,[A|X],[A|Y],Z):- А=‹ Н, разбить(Н,Х,Y,Z).

разбить(Н,[А|Х],Y,[А|Z]):- А › Н, разбить(Н,Х,Y,Z).

Тогда программа быстрой сортировки примет вид:

бысорт([H|T],S):-разбить(Н,Т,А,В),бысорт(А,А1),бысорт(В,В1), присоединить(А1, [H|B1],S).

Предикат присоединить можно встроить внутрь программы сортировки. Тогда получается другой предикат

бысорт2 ([H|T], S,X):-разбить(Н,T,А,В), бысорт2(А,S,[Н|Y]), бысорт2(B,Y,X).

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

Более подробные сведения о методах сортировки можно найти в книге D. Knuth, The Art of Computer Programming, v. 3 (Sort and Searching), Addison-Wesley, 1973 (Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3 (Сортировка и поиск). М.: Мир, 1978.- Перев.) Метод быстрой сортировки Хоора описан в его статье в Computer Journal n. 5 (1962), стр. 10-15.

Упражнение 7.5. Проверьте, что предикат перестановка (L1, L2) строит все перестановки заданного списка L1 (причем каждую по одному разу) и выдает их как альтернативные значения списка L2. В каком порядке строятся эти решения?

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

7.8. Использование базы данных: random, генатом, найтивсе

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

Генератор случайных чисел (random)

Цель random(R, N) конкретизирует N целым числом, случайно выбранным в диапазоне от 1 до R. Метод выбора случайного числа основан на конгруэнтном методе с использованием начального числа («затравки») инициализируемого произвольным целым числом. Каждый раз, когда требуется случайное число, ответ вычисляется на основе существующего начального значения, и при этом порождается новое начальное число, которое сохраняется до тех пор, пока вновь не потребуется вычислить случайное число. Для хранения начального числа между вызовами random мы используем базу данных. После того как начальное число использовано, мы убираем (с помощью retract) из базы данных старую информацию о начальном числе, вычисляем его новое значение, и засылаем в базу данных новую информацию (с помощью asserta). Исходное начальное значение – это просто факт в базе данных, с функтором seed имеющим одну компоненту – целое значение начального числа.

random (R,N):-seed(S),N is (S mod R) + 1,retract(seed(S)),NewSeed is (125 * S + 1) mod 4096,asserta(seed(NewSeed)).

Используя семантику retract можно упростить определение random следующим образом:

random(R,N):-retract(seed(S)),N is (S mod R)+1,NewSeed is (125 * S +1) mod 4096,asserta(seed(NewSeed)).

Для того, чтобы напечатать последовательность случайных чисел, расположенных в диапазоне между 1 и 10, которая обры-вается после того, как будет порождено значение 5, нужно задать следующий вопрос:

?- repeat, random(10,X), write(X), nl, X=5.

Генератор имен (генатом)

Предикат генатом позволяет порождать новые атомы Пролога. Если у нас есть программа, которая воспринимает информацию об окружающем мире (например, путем анализа описывающих его предложений на английском языке), то в случае появления в этом мире нового объекта возникают трудности с его обозначением. Естественно представлять объект атомом Пролога. Если объект ранее не встречался, мы должны убедиться в том, что тот атом, который мы ему сопоставляем, случайно не совпал с другим атомом, уже представляющим какой-то другой объект. Иными словами, нам необходимо иметь возможность формировать новые атомы. Мы можем также потребовать, чтобы созданный атом имел также некоторое мнемоническое значение: это облегчит понимание информации выводимой нашей программой. Если бы атомы представляли, скажем, студентов, то целесообразно было бы назвать первого студента – студент1, второго – студент2, третьего – студентЗ и т. д. Если к тому же нам нужно было бы работать с объектами представляющими еще и преподавателей, то можно было бы выбрать для их представления атомы преподаватель1, преподаватель2, преподавательЗ и т. д.

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

задан впервые, ответом будет

В следующий же раз ответом будет

Заметим, что эти различающиеся решения при возвратном ходе не порождаются (генатом(Х, Y) нельзя согласовать вновь), они порождаются последующими целями, включающими этот предикат.

В определении генатом используется вспомогательный предикат тек_номер. Контроль за тем, какой номер использовать следующим для данного корня, осуществляется программой генатом путем записи в базу данных фактов вида тек_номер и удаления фактов, которые стали ненужными. Факт тек_номер (Корень, Номер) означает, что последний номер, использованный с корнем Корень, был Номер. Иными словами, последний атом, порожденный для этого корня, состоял из литер, взятых из Корень, за которыми был приформирован номер, взятый из Номер. Когда Пролог пытается доказать согласованность цели генатом, обычно делается следующее: последний факт тек_номер для заданного корня удаляется из базы данных, к его номеру прибавляется 1, и новый факт тек_номер запоминается в базе данных, заменяя исключенный факт. С этого момента новый номер может быть использован как основа для порождения нового атома. Хранить информацию о текущем номере в базе данных очень удобно. В противном случае каждый предикат, прямо или косвенно участвующий в выполнении генатом, должен был бы пересылать информацию о текущих номерах через дополнительные аргументы.

Последние несколько утверждений этой программы определяют предикат целое_имя, который используется для преобразования целого числа в последовательность литер-цифр. Атомы, порождаемые генатом, формируются с помощью встроенного предиката name, который формирует атом из литер корня, за которыми следуют цифры номера. В некоторых реализациях Пролога используется версия предиката name, которая выполняет также функции предиката целое_имя, однако весьма поучительно посмотреть, как его можно определить на Прологе. В этом определении неявно используется тот факт, что коды ASCII для цифр 0, 1, 2 и т. д. равны соответственно 48, 49, 50 и т. д. Поэтому, чтобы преобразовать число меньшее 10 в код ASCII соответствующей цифры, достаточно прибавить к этому числу 48. Перевести в последовательность литер число, большее 9, сложнее. Последнюю цифру такого числа получить легко, поскольку это просто остаток от деления на 10 (число mod 10). Таким образом, цифры числа легче формировать в обратном порядке. Мы просто циклически повторяем следующие операции: получение последней цифры, вычисление остальной части числа (результат его целого деления на 10). Определение этого на Прологе выглядит следующим образом:

цифры_наоборот(N,[С]):- N‹10. С is N+48.

цифры_наоборот(М,[С|Сs]):-С is (N mod 10) + 48,N1 is N/10,цифры_нaoбopот(N1,Cs).

Чтобы получить цифры в правильном порядке, применим трюк: в этот предикат добавим дополнительный аргумент – список «уже сформированных» цифр, С помощью этого аргумента мы можем получать цифры по одной в обратном порядке, но в итоговый список вставлять их в прямом порядке. Это делается следующим образом. Пусть у нас есть число 123. В начале список «уже сформированных» цифр есть []. Первым получаем число 3, которое преобразуется в литеру с кодом 51. Затем мы рекурсивно вызываем целое_имя, чтобы найти цифры числа 12. Список «уже сформированных» цифр, который передается в это целевое утверждение, содержит литеру, вставленную в исходный список «уже сформированных» цифр – это список [51]. Вторая цель целое_имя выдает код 50 (для цифры 2) и снова вызывает целое_имя, на этот раз с числом 1 и со списком «уже сформированных» цифр [50, 51]. Эта последняя цель успешно выполняется и, поскольку число было меньше 10, дает ответ [49,50,51]. Этот ответ передается через аргументы разных целей целое_имя и дает ответ на исходный вопрос – какие цифры соответствуют числу 123?

Приведем теперь всю программу полностью.

/* Породить новый атом, начинающийся с заданного корня, и оканчивающийся уникальным числом. */

генатом (Корень,Атом),выдать_номер(Корень,Номер), name(Корень,Имя1), целое_имя(Номер,Имя2), присоединить(Имя1,Имя2,Имя), name(Атом,Имя).

выдать_номер(Корень, Номер):-retract(тeк_номер(Корень, Номер1)). Номер is Номер 1 + 1, asserta(тек_номер(Корень, Номер)).

/* Преобразовать целое в список цифр */

целое_имя(Цел,Итогспи):- целое_имя (Цел, [], Итогспи).

целое_имя(I,Текспи,[С|Текспи]:- I ‹10. С is I+48.

целое_имя(I,Текспи,Итогспи):-Частное is I/10, Остаток is I mod 10,С is Остаток+48.

Генератор списков структур (найтивсе)

В некоторых прикладных задачах полезно уметь определять все термы, которые делают истинным заданный предикат. Например, мы могли бы захотеть построить список всех детей Адама и Евы с помощью предиката родители из гл. 1 (и располагая базой данных с фактами родители о родительских отношениях). Для этого мы могли бы использовать предикат по имени найтивсе, который мы определим ниже. Цель найтивсе(Х,G, L) строит список L, состоящий из всех объектов X таких, что они позволяют доказать согласованность цели G. При этом предполагается, что переменная G конкретизирована произвольным термом, однако таким, что найтивсе рассматривает его как целевое утверждение Пролога. Кроме того переменная X должна появиться где-то внутри G. Таким образом G может быть конкретизирована целевым утверждением Пролога произвольной сложности. Для того, чтобы найти всех детей Адама и Евы, необходимо было бы задать следующий вопрос:

?- найтивсе(Х, родители(Х,ева,адам), L).

Переменная L была бы конкретизирована списком всех X, для которых предикату родители(Х,ева,адам) можно найти сопоставление в базе данных. Задача найтивсе заключается в том, чтобы повторять попытки согласовать его второй аргумент, и каждый раз, когда это удается, программа должна брать значение X и помещать его в базу данных. Когда попытка согласовать второй аргумент завершится неудачно, собираются все значения X, занесенные в базу данных. Получившийся при этом список возвращается как третий аргумент. Если попытка доказать согласованность второго аргумента ни разу не удастся, то третий аргумент будет конкретизирован пустым списком. При помещении элементов данных в базу данных используется встроенный предикат asserta, который вставляет термы перед теми, которые имеют тот же самый функтор. Чтобы поместить элемент X в базу данных, мы задаем его в качестве компоненты структуры по имени найдено. Программа для найтивсе выглядит следующим образом:

найтивce(X,G,_):-asserta(найденo(мapкep)), call(G), asserta(найденo(X)),fail.

найтивсе(_,_,L):- собрать_найденное([],М). L=M.

собрать_найденное(S,L):- взятьеще(Х). собрать_найденное([Х |S],L).

взятьеще(Х):- retract(найдено(Х)). Х\==маркер.

Предикат найтивсе, начинает свою работу с занесения специального маркера, который представляет из себя структуру с функтором найдено и с компонентой маркер. Этот специальный маркер отмечает место в базе данных, перед которым будут занесены (с помощью asserta) все X, согласующие G с базой данных при данном запуске найтивсе. Затем делается попытка согласовать G и каждый раз, когда это удается, X заносится в базу данных в качестве компоненты функтора найдено. Предикат fail инициирует процесс возврата и попытку повторно согласовать G (asserta согласуется не более одного раза). Когда попытка согласовать G завершается неудачей, процесс возврата приводит к неудаче первого утверждения из определения найтивсе, и делается попытка согласовать в качестве цели второе утверждение. Второе утверждение вызывает собрать_найденное для выборки из базы данных всех структур найдено и включения их компонент в список. Предикат собрать_найденное вставляет каждый элемент в переменную, где хранится список «уже собранных» элементов. Этот прием мы рассматривали выше при разборе программы ге-натом. Как только встречается компонента маркер, взятьеще завершается неудачей, после чего выбирается второе утверждение для собрать_найденное. При сопоставлении его с текущей целью второй аргумент (результат) сцепляется с первым аргументом (с набранным списком)

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

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

Упражнение 7.7. Напишите Пролог-программу случайный_выбор такую, что цель случайный_выбор(L, Е) конкретизирует Е случайно выбранным элементом списка L. Подсказка: используйте генератор случайных чисел и определите предикат, который возвращает N-й элемент списка.

Упражнение 7.8. Задана цельнайтивсе(Х,G, L). Что произойдет, если в G имеются неконкретизированные переменные не сцепленные с X?

7.9. Поиск по графу

Граф – это сеть, состоящая из узлов, соединенных дугами. Например, географическую карту можно рассматривать как граф, где узлами являются населенные пункты, а дугами, соединяющие их дороги. Если вы хотите найти кратчайший маршрут между двумя населенными пунктами, вам предстоит решить задачу нахождения кратчайшего пути между двумя узлами графа.

Проще всего описать граф в базе данных с помощью фактов, представляющих дуги между узлами графа. На рис, 7.3 приведен пример графа и его представления с помощью фактов. Чтобы пройти от узла g к узлу а, мы можем пойти по пути g, d, e, а или по одному из многих других возможных путей. Если мы представляем ориентированный граф, то предикат а следует понимать так, что а(Х, Y) означает, что существует дуга из X в Y, но из этого не следует существование дуги из Y в X. В данном разделе мы будем иметь дело только с неориентированными графами, у которых все дуги двунаправленные. Это допущение совпадает с тем, которое мы делаем в разд. 7.2 при поиске в лабиринте.

Простейшая программа поиска по графу, представленному так, как указано выше, выглядит следующим образом:

переход(Х,Y):- (a(X,Z);a(Z,X)), переход(Z,Y).

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


переход(Х,Y,T):- (a(X,Z);a(Z,X)), not (принадлежит(Z, Т)),переход(Z, Y,[Z|T]).

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

Теперь давайте рассмотрим такой поиск по графу, который мог бы быть полезен на практике. Как быть, если мы должны спланировать маршрут поездки из одного города Северной Англии в другой? Для этого потребуется база данных с информацией о дорогах между городами в Северной Англии и их протяженности:

На некоторое время мы можем забыть о расстояниях и определить новый предикат:

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

переход(Старт,Цель,Путь):- переход0(Старт,Цель,[],R),обр(R, Путь).

следузел(Х,Бывали,Y):- (a(X,Y); a(Y,X)),not (принадлежит(Y,Бывали)).

Заметим, что предикат следузел позволяет получать для узла X «правильный» узел Y, т. е. такой, к которому можно непосредственно перейти от узла X. Ниже приводится пример работы этой программы при поиске маршрута из Дарлингтона в Уэркингтон:

Это не самый лучший маршрут, однако, программа найдет другие маршруты если мы инициируем процесс возврата.

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

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

переход(Старт,Цель,Путь):- переход1([[Старт]],Цель,R),обр(R, Путь).

переход1([Первый|Ост],Цель,Первый):- Первый =[Цель|_].

переход1([[Послед|Бывали]|Прочие],Цель,Путь):-найтивсе([Z, Послед|Бывали], следузел(Послед, Бывали,Z), Список), присоединить(Список, Прочие, НовПути), переход1(НовПути,Цель,Путь).

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

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

Наш «изыскатель», переход1 ведет полный список путей, по которым, может быть, стоит двигаться. Как же он решает какой из путей следует рассмотреть первым? Он просто выбирает первый попавшийся. Затем он ищет все возможные способы продления этого пути до следующего населенного пункта (используя найтивсе для построения списка всех таких продленных путей) и помещает получившиеся пути в начало списка для рассмотрения их на следующем уровне рекурсии.

В результате, переход1 ведет себя таким образом, что он попробует все возможные способы продления первого пути прежде чем будет рассматривать альтернативные пути. Такая стратегия поиска является одним из вариантов поиска вглубь. Между прочим, переход1 рассматривает пути совершенно в том же порядке, что и переход0. Быть может вам будет интересно выяснить, почему это так.

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

переход1([[Послед|Бывали]|Прочие],Цель,Путь):-найтивсе([Z,Послед|Бывали], следузел(Послед, Бывали,Z),Список), присоединить(Прочие,Список,НовПути), переход1(НовПути,Цель, Путь).

Теперь исправленная программа находит возможные пути из Дарлингтона в Уэркингтон в следующем порядке:

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

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

а(уэркингтон, карлайл, 33).

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

переходЗ (Пути,Цель,Путь):-кратчайший (Пути,Кратчайший,ОстПути), продлить(Кратчайший,Цель,ОстПути,Путь).

продлить(г(Расст,Путь),Цель,_,Путь):- Путь = [Цель|_].

продлить(г(Расст,[Послед| Бывали]),Цель,Пути,Путь):-найтивсе(г(D1,[Z,Послед|Бывали]),следузел(Послед,Бывали,Z,Расст,D1),Список), присоединить(Список,Пути,НовПути), переходЗ(НовПути,Цель,Пути).

кратчайший(Путь|Ост],Путь,Ост). короче(г(М1,_),г(М2, _):- M1 ‹ М2.

следузел(Х,Бывали,Y,Расст,НовРасст):-(a(X,Y,Z); a(Y,X,Z)),not(принадлежит(Y,Бывали)),НовРасст is Расст+Z.

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

переход (Старт,Цель,Путь):-переход3([г(0,[Старт])],Цель,R), обр(R,Путь).

Эта новая программа успешно строит возможные пути в по-рядке возрастания их фактической протяженности. Может быть, вам захочется изменить ее так, чтобы вместе с ответами она печатала длины различных путей.

Мы лишь затронули вопрос о возможных способах организации поиска по графу. Сведения о том, как осуществлять поиск по графу с использованием более эффективных критериев, чем «первый лучший», можно найти в литературе по искусственному интеллекту. Например: Nilsson N. Principles of Artificial Intelligence, Springer-Verlag, 1982[10] и Winstone P. Artificial Intelligence, (second edition), Addison-Wesley, 1984. [11]

7.10. Просеивай Двойки, Просеивай Тройки

Просеивай Двойки,
Просеивай Тройки,
Эратосфена Решето,
Пусть все кратные им отсеем,
Простые числа получим зато.

Простое число – это целое положительное число, которое делится нацело только на 1 и на само себя. Например, число 5 – простое, а число 15 – нет, поскольку оно делится на 3. Один из методов построения простых чисел называется «решетом Эратосфена». Этот метод, «отсеивающий» простые числа, не превышающие N, работает следующим образом:

1. Поместить все числа от 2 до N в решето.

2. Выбрать и удалить из решета наименьшее число.

3. Включить это число в список простых.

4. Просеять через решето (удалить) все числа, кратные этому числу.

5. Если решето не пусто, то повторить шаги 2-5.

Чтобы перевести эти правила на Пролог, мы определим предикат целые для получения списка целых чисел, предикат отсеять для проверки каждого элемента решета и предикат удалить для создания нового содержимого решета путем удаления из старого всех чисел, кратных выбранному числу. Это новое содержимое опять передается предикату отсеять. Предикат простые — это предикат самого верхнего уровня, такой что простые(N, L) конкретизирует L списком простых чисел, заключенных в диапазоне от 1 до N включительно.

целые (Min,Max,[Min|Oct]):-Min=‹Max. М is Min+1,целые(М,Мах,Ост).

удалить (P,[I|Is],[I|Nis]):-not(0 is I mod Р). удалить(Р,Is,Nis).

удалить (P,[I|Is],Nis):-0 is I mod Р. удалить(Р,Is,Nis).

Продолжая эту арифметическую тему, рассмотрим Пролог-программу, реализующую рекурсивную формулировку алгоритма Евклида для нахождения наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) двух чисел. Целевое утверждение нод(I,J,K) доказуемо, если K является наибольшим общим делителем чисел I и J. Целевое утверждение нок(I,J,K) доказуемо, если K является наименьшим общим кратным чисел I и J:

нод(I,J,K):- R is I mod J, нод(J,R,K).

нок(I,J,K):- нод(I,J,R), K is (I*J)/R.

Заметим, что из-за особенностей способа вычисления остатка эти предикаты не являются «обратимыми». Это означает, что для того чтобы они работали, необходимо заблаговременно конкретизировать переменные I и J.

Упражнение 7.10. Если числа X, Y и Z таковы, что квадрат Z равен сумме квадратов X и Y (т. е. если Z²=X²+Y²), то про такие числа говорят, что они образуют Пифагорову тройку. Напишите программу, порождающую Пифагоровы тройки. Определите предикат pythag такой что, задав вопрос

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

7.11. Символьное дифференцирование

Символьным дифференцированием в математике называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной. Пусть U обозначает арифметическое выражение, которое может содержать переменную х. Производная от U по х записывается в виде dU/dx и определяется рекурсивно с помощью некоторых правил преобразования, применяемых к U. Вначале следуют два граничных условия. Стрелка означает «преобразуется в»; U и V обозначают выражения, а с – константу:

d(U c )/dxcU c — l (dU/dx)

Этот набор правил легко написать на Прологе, поскольку мы можем представить арифметические выражения как структуры и использовать знаки операций как функторы этих структур. Кроме того, сопоставление целевого утверждения с заголовком правила мы можем использовать как сопоставление образцов. Рассмотрим цель d(E,X, F), которая считается согласованной, когда производная выражения E по константе [12] X есть выражение F. Помимо знаков операций +, -, *, /, которые имеют встроенные определения, нам нужно определить операцию ^, такую, что X^Y означаете x y , а также одноместную операцию

Х означает «минус X». Эти определения операций введены исключительно для того, чтобы облегчить распознавание синтаксиса выражений. Например, после того как d определен, можно было бы задать следующие вопросы:

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

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

Как уже говорилось, данная программа выдает решения в неприведенной форме (т. е. без упрощений). Например, всякое вхождение х*1 может быть приведено к х, а всякое вхождение вида х*1+1*х-0 может быть приведено к 2*х. В следующем разделе рассматривается программа алгебраических преобразований, которую можно использовать для упрощения арифметических выражений. Примененный способ очень похож на тот, каким выше выводились производные.

7.12. Отображение структур и преобразование деревьев

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

Поскольку отображение имеет довольно широкое применение, мы можем определить предикат отобспис такой, что целевое утверждение отобспис(Р, L, M) согласуется с базой данных, применяя предикат Р к каждому элементу списка L и образуя в результате новый список М. При этом предполагается, что предикат Р имеет два аргумента: первый аргумент для передачи «входного» элемента, а второй аргумент – для измененного элемента, подлежащего включению в список М.

отобспис((P,[X|L],[Y|M]):- Q =..[P,X,Y],call(Q),отобспис(Р,L,М).

Об этом определении следует сказать несколько слов. Во-первых, определение содержит граничное условие (первое утверждение) и общий рекурсивный случай (второе утверждение). Во втором утверждении используется оператор ‘=..’, формирующий целевое утверждение на основе предиката (Р), входного элемента (X) и переменной (Y), которую предикат Р должен конкретизировать, чтобы образовать измененный элемент. Затем делается попытка согласовать цель Q, в результате чего Y конкретизируется, образуя голову третьего аргумента данного вызова предиката отобспис. Наконец, рекурсивный вызов отображает хвост первого аргумента в хвост второго.

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

Z = [i, [am, not], a, computer]

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

Заметим, что предикат печать_строки из гл. 5 можно было бы заменить запросом вида обрабспис(put, L), где L – это строка, которую нужно напечатать.

Отображение применимо не только к спискам; оно может быть определено для структуры любого вида. Например, рассмотрим арифметическое выражение, составленное из функторов * и +, имеющих по два аргумента. Пусть мы хотим отобразить одно выражение в другое, устраняя при этом все умножения на 1. Это алгебраическое приведение могло быть определено с помощью предиката s такого, что s(Op, L, R,Ans) означает, что выражение, состоящее из операции Ор с левым аргументом L и правым аргументом R приводится к упрощенному выражению Ans. Факты, необходимые для устранения умножений на 1, могли бы выглядеть так (из-за коммутативности умножения нужны два факта):

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

При приведении выражения Е с помощью такой таблицы упрощений, мы вначале должны привести левый аргумент Е, затем привести правый аргумент Е и, наконец, посмотреть, подходит ли этот приведенный результат под случаи, предусмотренные в нашей таблице. Если это так, то мы порождаем новое выражение в соответствии с указаниями таблицы. В качестве «листьев» дерева, представляющего выражение, фигурируют целые числа или атомы, поэтому для приведения листьев к ним самим в граничном условии мы должны использовать встроенный предикат atomic. Как и выше, мы можем использовать ‘ =..’, чтобы разложить выражение Е на функтор и компоненты;

привести(Е,Е):- atomic(E), 1.

привести(Е,F):-Е =.. [Op,L,R],привести(L,Х),привести(R, Y),s(Op,X,Y,F).

Итак, предикат привести отображает выражение Е в выражение F, используя для этого факты, имеющиеся в таблице упрощений s. А что делать, если невозможны никакие упрощения? Чтобы избежать в этом случае неудачного завершения s(Op,X, Y, F), мы должны поместить в конец каждого раздела таблицы упрощений, относящегося к определенному оператору, правило-ловушку. Приведенная ниже таблица упрощений содержит правила для сложения и умножения. Кроме того, в ней выделены правила-ловушки для каждого вида операций.

s(+,X,Y,X + Y) /* ловушка для + */

s(*,X,Y,X*Y). /* ловушка для * */

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

Другое упрощение, используемое при выполнении алгебраических преобразований с помощью ЭВМ, известно как свертка констант. В выражении 3*4+a константы 3 и 4 могут быть «свернуты», что дает в результате выражение 12+а. Правила свертки констант могут быть добавлены в соответствующие места приведенной выше таблицы упрощений. Правило для сложения констант выглядит следующим образом:

s(+,X,Y,Z):- integer(X), integer(Y), Z is X+Y.

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

В коммутативных операциях, таких как умножение и деление, указанные выше упрощения могут давать различный эффект на выражениях, которые записаны по-разному, но алгебраически эквивалентны. Например, если правило свертки констант задано для умножения, то предикат привести совершенно правильно преобразует 2*3*а в 6*а, но а*2*3 или 2*а*3 будут преобразовываться в самих себя. Чтобы понять, почему это так, подумайте над тем, как выглядят деревья, представляющие эти выражения (см. рис. 7.4).

В первом дереве самое нижнее умножение 2*3 можно свернуть, получив 6, но во втором дереве нет поддеревьев, которые было бы можно свернуть. Однако, используя коммутативность умножения, можно добавить к таблице следующее правило, которое позволит справиться с данным конкретным случаем:

Илон Маск рекомендует:  Шаблон сайта фотокамера HTML, CSS, 2 страницы

s(*,X*Y,W,X*Z):- integer(Y), integer(W), Z is Y*W.

Более общая алгебраическая система может быть построена путем простого добавления дополнительных s-утверждений вместо увеличения объема программы для привести.

7.13. Применение предикатов clause и retract

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

Мы можем определить с помощью предиката clause некоторую версию процедуры listing. Определим предикат распеч1 такой, что при согласовании цели распеч1(Х) с базой данных из последней будут выводиться на печать утверждения, заголовки которых совпадают с X. Поскольку определение распеч1 включает использование предиката clause, у которого X задан как первый аргумент, то мы вынуждены поставить условие, что переменная X конкретизирована таким образом, что главный функтор утверждения известен. Рассмотрим определение распеч1:

выв_утвержд(Х,Y):- write((X:- Y)).

При попытке согласовать с базой данных цель распеч1(Х) первое утверждение осуществляет поиск в базе данных такого утверждения, у которого заголовок совпадает с X. Если такое утверждение найдено, то оно выводится на печать и затем с помощью предиката fail инициируется механизм возврата. Возвратный ход опять приводит нас к предикату clause, который находит другое такое же утверждение, если оно имеется, и т. д. Когда таких утверждений больше нет, цель clause больше не удается согласовать с базой данных. В этом случае будет выбрано второе утверждение определения предиката распеч1, и потому цель будет согласована с базой данных. «Побочным эффектом» этих действий является печать соответствующих утверждений. Определение предиката выв_утвержд задает способ печати найденных утверждений. Выделяется специальный случай, когда тело утверждения есть true. В этом случае на печать выводится только заголовок утверждения. Иначе на печать выводится заголовок и тело утверждения, соединенные функтором ‘:-‘. Отметим, что использование «отсечения» здесь имеет целью указать, что в случае, когда тело есть true, можно применять только первое правило. Поскольку данный пример построен на использовании механизма возврата, то задание отсечения здесь существенно.

Встроенный предикат clause можно также применить при написании Пролог-интерпретатора на самом Прологе. Это означает, что мы можем определить действия, которые представляют собой выполнение Пролог-программы, причем исполнителем этих действий также является Пролог-программа. Ниже приводится определение предиката интерпрет такого, что цель интерпрет(Х) согласуется в том и только в том случае, когда X, рассматриваемая как цель, согласуется с базой данных.

Предикат интерпрет напоминает встроенный предикат call, но является более ограниченным.

интерпрет((Gl,G2)):-!, интерпрет(G1), интерпрет(G2).

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

Рассмотрим определение предиката consult. Разумеется, предикат consult предусмотрен среди встроенных предикатов большинства Пролог-систем, однако интересно посмотреть, как он может быть определен на Прологе.

обработать((?- Q)):-!, call(Q). fail.

обработать(Утвержд):- assertz(Утвержд), fail.

Это определение отличается рядом интересных особенностей. Во-первых, цель seeing(Input) и ее партнер see(Input) призваны гарантировать, что текущий файл ввода не будет «забыт» после применения предикат consult. Во-вторых, предикат маркер_конца_файла здесь использован без определения. По замыслу он должен быть истинным только в том случае, когда его аргумент конкретизирован термом, используемым для представления конца файла (который мог бы встретиться при выполнении read). В разных реализациях Пролога для представления «конца файла» используются разные термы, поэтому маркер_конца_файла в разных реализациях может быть определен по-разному. Одно из возможных определений выглядит так:

В определении предиката обработать интересна организация выполнения соответствующих действий для каждого терма, считанного из входного файла. Целевое утверждение обработать доказуемо только, когда его аргументом является маркер конца файла. Иначе после соответствующего действия имитируется неудача доказательства и инициируется механизм возврата, который возвращает программу к предикату repeat. Отметим важность «отсечения» в конце определения предиката consult. Оно фиксирует выбор, сделанный предикатом repeat[13]. И последнее замечание. Если терм, считанный из файла, представляет собой вопрос (см. второе утверждение определения предиката обработать), то делается попытка немедленно согласовать соответствующую цель с помощью предиката call (см. разд. 6.7).

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

уберивсе(Х):- retract(X), fail.

уберивсе(Х):- retract((X:- Y)), fail. уберивсе(_).

В качестве примера использования предиката убери все здесь приведено определение предиката reconsult на Прологе. Назначение предиката reconsult сходно с назначением предиката consult, с той лишь разницей, что при reconsult каждое считанное утверждение замещает существующее утверждение того же предиката, а не добавляется к нему (см. разд. 6.1).

проверить((?- Цели)):-!, call (Цели). fail.

проверить(Утверждение):-заголовок(Утверждение, Заголовок), запись_сделана(3аголовок), assertz(Утверждение), fail.

запись_сделана(3аголовок):- functor(Заголовок,Func,Arity), functor(Proc,Func,Arity), asserta(cдeлaнo(Proc)), уберивсе(Ргос).

Это определение похоже на определение consult, в котором вместо предиката обработать используется предикат проверить. Основное различие заключено в предикате запись_сделана. Когда в файле появляется первое утверждение для данного предиката, то, прежде чем к базе данных будет добавлено хотя бы одно новое утверждение, из нее должны быть удалены все старые утверждения для данного предиката. Удаление этих утверждений нельзя откладывать до момента, когда в базе данных появятся их новые версии, поскольку в этом случае мы удалили бы из базы данных те утверждения, которые только что были введены. Как же определить, что некоторое утверждение в файле является первым для соответствующего предиката? Ответ заключается в том, что мы регистрируем в базе данных предикаты, для которых уже нашлись утверждения в файле. Это делается с помощью предиката сделано. Когда из файла считывается первое утверждение например, для предиката foo с двумя переменными, то имеющиеся утверждения удаляются и новое утверждение добавляется к базе данных. Кроме того, к базе данных добавляется факт:

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

поскольку в этом случае аргумент предиката сделано не обязательно совпадает с заголовком утверждения для foo. Пара запросов

конкретизирует Ргос структурой, имеющей тот же функтор, что и заголовок Заголовок, но с переменными в качестве аргументов (см. разд. 6.5).

Примечания:

В книге термин «Пролог» употребляется в трех значениях: 1) Пролог – язык программирования с совокупностью синтаксических и семантических правил записи программ; 2) Пролог – программная система (интерпретатор), реализующая язык; эта система и осуществляет диалог с пользователем; 3) Пролог – машина, на которой Пролог-система выполняет (интерпретирует) программы, написанные на языке Пролог. Как правило, из контекста всегда ясно, какое значение используется в каждом конкретном случае. При необходимости явного указания при переводе использовались термины: «язык Пролог», «Пролог-система», «Пролог-машина». — Прим. пepeв.


Имеется перевод: Нильсон Н. Принципы искусственного интеллекта. — М.: Радио и связь, 1985. — Прим. перев.

Имеется перевод 1-го издания: Уинстон П., Искусственный интеллект. — М.: Мир, 1980. — Прим. перев.

Имеется в виду константа в смысле Пролога. — Прим. ред.

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

Лабораторная работа №1 Тема: Факты и правила на Прологе. Основные приемы работы в Visual Prolog (стр. 4 )

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4

insert (NewItem, Right, NewRight).

insert(C, Tree, TempTree),

insert(New, end, tree(New, end, end)):-!.

insert(New, tree(Element, Left, Right),tree(Element, NewLeft, Right)):-

asserta( ,databaseName) /* (i, i) */

assertz( ,databaseName) /* (i, i) */

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

Использование предиката assert имеет действие аналогичное использованию assertz.

Первый предикат следующего примера вставит факт о Suzanne, описанный предикатом person, после всех фактов person, хранящихся в текущий момент в памяти. Второй вставит факт о Michael перед всеми имеющимися фактами предиката person. Третий — вставит факт о John после всех других фактов likes в базе данных likesDatabase, а четвертый — вставит факт о Shannon в той же базе данных перед всеми другими фактами likes.

assertz(person(«Suzanne», «New Haven», 35)).

asserta(person(«Michael», «New York», 26)).

asserta(likes(«Shannon», «hard work»),likesDatabase).

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

/* Внутренняя база данных — dbasedom */

person(«Michael», «New York», 26).

/* . другие факты person. */

person(«Suzanne», «New Haven», 35).

/* Внутренняя база данных — likesDatabase */

/* . другие факты likes. */

likes(«Shannon», «hard work»)

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

retract( [, databaseName]) /* (i, i) */

Предположим в вашей программе имеются следующие секции database:

person(string, string, integer)

/* база данных — likesDatabase */

Имея такие секции facts (или database), Прологу можно задать следующие цели:

retract(person(«Fred», _, _)). /* 1 */

retract(likes( _,»broccoli»)). /* 2 */

retract(likes( _, «money»),likesDatabase). /* 3 */

retract(person(«Fred», _, _),likesDatabase). /* 4 */

Первая цель удалит первый факт person о Fred из базы данных dbasedom (имя которой задается по умолчанию). С помощью второй цели из базы данных likesDatabase будет удален первый факт, совпадающий с likes(X,»broccoli»). При этом, Пролог знает из какой базы производить удаление, поскольку имена предикатов базы данных уникальны: предикат person находится только в неименованной базе данных, а likes только в базе likesDatabase.

Третья и четвертая цель показывают, как можно использовать для проверки типа второй аргумент. Третья цель успешно реализуется, удаляя первый факт, совпадающий с likes(,»money») из likesDatabase, а четвертая цель выдаст ошибку, потому что нет (и не может быть) факта person в базе данных likesDatabase.

Сообщение об ошибке выглядит следующим образом:

506 Type Error: The functor does not belong to the domain (функтор не относится к данному домену)

Следующая цель иллюстрирует, как можно получить значения из предиката retract:

Можно также удалить все факты из заданной секции facts (или database) с помощью предиката retract. Если при вызове retract в качестве первого аргумента будет указана свободная переменная, то чтобы определить, из какой секции facts (или database) нужно произвести удаление, он будет анализировать второй аргумент. Например:

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

retractall имеет следующий формат:

Также как в случае предикатов assert и retract для проверки типа можно использовать второй аргумент. И, как в случае предиката retract, если при вызове retractall используется символ подчеркивания, то из указанной секции facts (или database) можно удалить все факты.

Следующая цель удаляет все факты о мужчинах из базы данных с фактами person:

Следующая цель удаляет все факты из базы mydatabase.

Предикат consult считывает из файла (fileName) факты, описанные в секции facts (или database), и вставляет их в вашу программу в конец соответствующей базы данных (аналогично тому, как предикат assertz включает факты.) Предикат consult имеет один или два аргумента:

consult(fileName, databaseName) /* (i, i) */

Однако, в отличии от assertz, если вы вызовите consult только с одним аргументом (без имени базы данных), то будут считаны только факты, которые были описаны в секции без имени (по умолчанию dbasedom).

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

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

Отметим, что предикат consult может считывать файлы только в том формате, который создает save (для включения фактов с максимально возможной скоростью). Файлы не должны содержать:

— пробелов за исключением тех, которые содержатся внутри

строк в двойных кавычках;

— символов без двойных кавычек.

При создании или изменении файла с фактами в редакторе нужно соблюдать аккуратность.

Предикат save сохраняет факты из указанной базы данных в файле. Этот предикат имеет один или два аргумента:

save(fileName, databaseName) /* (i, i) */

При вызове предиката save только с одним аргументом (без имени базы данных), в файле fileName будут сохранены факты из базы данных dbasedom, используемой по умолчанию.

При вызове предиката save с двумя аргументами (имя файла и имя базы данных), в указанном файле будут сохранены факты из database секции databaseName.

9. Ключевые слова, определяющие свойства фактов

Факты могут быть, объявляет с несколькими необязательными ключевыми словами:

GLOBAL — это ключевое слово определяет, что база фактов глобальная.

NOCOPY — обычно, когда предикат базы фактов вызван для связывания переменной со строковым или составным объектом, вызванные данные копируются из кучи в глобальный стек, nocopy объявляет, что данные не будут скопированы, а переменные будут ссылаться непосредственно на данные факта, хранимые в куче.

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

DETERM – это ключевое слово определяет, что база фактов может содержать не более одного факта для предиката базы фактов dbPredicates.

SINGLE – это ключевое слово определяет, что база фактов содержит один и только один факт для предиката базы фактов dbPredicates.

Факты, объявленные с ключевым словом nondeterm.

Ключевое слово nondeterm – определяет режим по умолчанию для фактов (предикатов базы данных), объявленных в разделе facts (или database). Если ни одно из ключевых слов determ или single не используется в объявлении фактов, то компилятор применяет nondeterm. Обычнопо своей природе предикаты базы данных недетерминированы. Потому что факты могут быть добавлены в любое время во время выполнения, компилятор должен всегда принимать, что во время поиска с возвратом возможно найти альтернативные решения.

Факты, объявленные с ключевым словом determ.

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

Объявление факта с determ дает возможность компилятору генерировать более эффективный код, и при вызове таких предикатов вы не будете получать предупреждений о возможном недетерминированном вызове. Особенно обратите внимание, что при удалении факта, который объявляют, как determ, обращение к недетерминированным предикатам retract/1 и retract/2, будет детерминированным. Так, если Вы знаете, что в любой момент внутренняя база данных содержит не более одного факта counter, Вы можете записать:

determ counter(integer CounterValue)

/* Здесь Пролог не будет устанавливать отметку перебора с возвратами */

Count= CurrentCount + 1,

my_retract(X): — retract(X). % deterministic predicate

/* Здесь Пролог не будет устанавливать отметку перебора с возвратами */

Count= CurrentCount + 1,

10. Примеры использования внутренней базы знаний

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

is_a(thing, thing, conds)

type_of(thing, thing, conds)

run(thing) — nondeterm (i)

ask(conds) — nondeterm (i)

is_a(X, Item, List),

write(«The «, Item,» you need is (a/an) «, Ans),nl.

write(«This program does not have enough «),

write(«data to draw any conclusions.»),

write(«Does this thing help you to «),

write(H,» (enter y/n)»),

readchar(Ans), nl, Ans=’y’,

is_a(«hammer»,»tool»,[«build a house»,»fix a fender»,»crack a nut»]).

is_a(«sewing_machine»,»tool»,[«make clothing»,»repair sails»]).

type_of(«english»,»language»,[«communicate with people»]).

type_of(«prolog»,»language»,[«communicate with a computer»]).

retractall(type_of(«prolog»,»language»,[«communicate with a computer»])),

[«communicate with a personal computer»])),

[«communicate with a mainframe computer»])).

Следующие факты могли быть занесены с помощью предикатов asserta, или assertz, или считаны из файла с помощью предиката consult. Однако, в этом примере они расположены в секции clauses.

is_a(language, tool, [«communicate»]).

is_a(hammer, tool, [«build a house», «fix a fender», «crack a nute»]).

is_a(sewing_machine, tool, [«make clothing», «repair sails»]).

is_a(plow, tool, [«prepare fields», «farm»]).

type_of(english, lahguage, [«communicate with people»]).

type_of(prolog, lahguage, [«communicate with a computer»]).

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

Теперь введите в раздел goal:

retract(type_of(prolog, language, [«communicate with a computer»])),

asserta(type_of(«turbo prolog», language, [«communicate with personal computer»])),

asserta(type_of(prolog, language, [«communicate with a mainframe computer»])),

Эта цель удалит факт


type_of(prolog, language, [«communicate with a computer»])

из внутренней базы данных и добавляет два новых факта в программу

type_of(prolog, language, [«communicate with a mainframe computer»]).

type_of(«turbo prolog», language, [«communicate with personal computer»]).

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

С помощью вызова предиката save с именем файла с качестве его аргумента можно сохранить всю базу данных в текстовом файле. Например, после вызова save(«mydata. dba») файл MYDATA. DBA будет аналогичен секции clauses обычной программы Пролога, и каждый факт будет содержаться строке. С помощью предиката consult можно считать этот файл в память:

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

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

database — dba1 /* dba1 — домен для предикатов */

Получив такие объявления, система Пролога создаст соответствующую облаcть (домен) dba1: domains

dba1 = person(name, telno) ; city(cno, cname)

Этот домен dba1 может быть использован также как любой другой предопределенный домен. Например, для создания предиката my_consult, аналогичного стандартному предикату consult,

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

2. Секциям facts (или database) можно давать имена (с помощью которых создается соответствующий внутренний домен). По умолчанию доменом для неименованной секции facts (или database) будет домен dbasedom. В программе может присутствовать несколько секций facts (или database), но каждая из них при этом должна иметь уникальное имя. Заданный предикат базы данных можно описать только в одной секции facts (или database).

3. С помощью стандартных предикатов asserta, assertz, и consult можно добавлять факты к внутренней базе данных во время работы программы. Можно также с помощью предикатов retract и retractall удалять эти факты во время работы программы.

4. Предикат save сохраняет факты из секции facts (или database) в файле (в определенном формате). С помощью редактора можно создавать или редактировать такой файл фактов, а затем можно вносить факты из файла в программу с помощью предиката consult.

5. Можно обращаться к предикатам базы данных в программе таким же образом, как и ко всем другим предикатам.

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

1. Составить ЭС диагностики. Предметную область выбрать самостоятельно (например, диагностика неисправности компьютера, некоторого заболевания, принадлежности животного или растения к некоторому виду).

Сортировка фактов в Прологе

Как я могу отсортировать факты по своей переменной

Студент (5). Студент (3). Студент (2). Студент (3). Студент (6).

Я хочу сделать функцию, чтобы они появились

Студент (2). Студент (3). Студент (3). Студент (5). Студент (6).

2 ответа

Сначала я собрал бы все эти факты в список, используя findall (пример: Как создать список из фактов в Прологе?), А затем отсортировал этот список (пример: сортировка списка в Прологе, или просто использовал встроенную сортировку /2 предиката).

(Отправлено с моего телефона)

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

Затем вы можете сделать несколько вещей:

(как предложено в другом ответе)

Если вы хотите, чтобы они действительно сортировались в базе данных, и не боитесь менять базу данных во время выполнения, вы можете удалить все student/1 из базы данных с abolish/1 и заново вставьте отсортированные факты:

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

Списки и рекурсия

Обработка списков как обработка последовательности элементов — это мощная техника, используемая в Прологе. В этом руководстве мы рассматриваем что такое списки, как их объявлять, и затем приводим несколько примеров, показывающих как использовать работу со списками в приложениях. Мы также определяем два хорошо известных предиката Пролога – member (член, элемент) и append (добавить) – рассматривая обработку списков как с рекурсивной, так и процедурной точки зрения.

Затем мы представляем предикат findall — стандартный предикат языка системы Visual Prolog, позволяющий собирать решения в единую цель. В завершение этого руководства мы обсуждаем составные списки – комбинции различных типов элементов и, кроме того, — пример разбора с помощью разностных списков.

Contents

Что такое Список?

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

Список, содержащий числа 1, 2 и 3 записывается как

Порядок элементов в этом списке значим:

  • Число «1» является первым элементом,
  • «2» — второй,
  • «3» — третий.

Список [ 1, 2, 3 ] и список [ 1, 3, 2 ] различны.

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

Один и тот же элемент может быть представлен в списке несколько раз, например:

Объявление Списков

Для объявления домена — списка целых используется декларация домена, как показано ниже:

Звездочка означает «список этого»; то есть, integer* означает «список целых».

Обратите внимание на то, что слово «list» не имеет специального значения в Visual Prolog. Вы равным образом могли бы назвать Ваш списковый домен как zanzibar. Именно звездочка, а не имя, предписывает этому домену быть списком.

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

Здесь elements должны быть приравнены к простым доменным типам (например, integer, real или symbol) или к набору возможных альтернатив, обозначенных различными функторами. Visual Prolog не допускает смешивание стандартных типов в списке. Например, следующие декларации ошибочно представляют списки, созданные из integers, reals и symbols:

Выходом для объявления списков из integer, real и symbols является объявление домена общего для всех типов, где функтор показывает какому типу принадлежит тот или иной элемент. Например:

(Подробнее об этом — в этом же руководстве в разделе «Составные списки»).

Головы и Хвосты

Список на самом деле является рекурсивным составным объетом. Он состоит из двух частей — головы списка, которым является первый элемент, и хвоста — списка, который включает все следующие элементы.

Хвост списка всегда есть список; голова списка есть элемент.

Что происходит, когда мы имеем дело со списком, содержащим один элемент? Ответом является:

Если многократно отнимать первый элемент от хвоста списка, мы получим в конечном итоге пустой список ([ ]).

Пустой список не может быть разбит на голову и хвост.

Это означает, что, концептуально говоря, списки имеют древовидную структуру подобно другим составным объектам. Древовидная структура списка [a, b, c, d] есть:

Более того, одноэлементный список, такой как [a] — это не тот же самый элемент, который этот список содержит, поскольку [a] является действительно составной структурой данных, как это видно здесь:

Представления Списков

Пролог содержит метод для явного обозначения головы и хвоста списка. Вместо разделения элементов запятыми можно отделять голову от хвоста вертикальной чертой (|). Например,

[a, b, c] эквивалентно [a|[b, c]]

и, продолжая процесс,

[a|[b,c]] эквивалентно [a|[b|[c]]],

что эквивалентно [a|[b|[c|[]]]]

Можно даже использовать оба способа разделения в одном и том же списке, рассматривая вертикальную черту как разделитель самого низкого уровня. Следовательно, можно записать [a, b, c, d] как [a, b|[c, d]]. Таблица 1 дает дополнительные примеры.

Таблица 1: Головы и Хвосты списков

Список Голова Хвост
[‘a’, ‘b’, ‘c’] ‘a’ [‘b’, ‘c’]
[ ‘a’ ] ‘a’ []
/*пустой список*/ [ ] неопределен неопределен
[[1, 2, 3], [2, 3, 4], []] [1, 2, 3] [[2, 3, 4], []]

В Таблице 2 приведены некоторые примеры унификации списков.

Таблица 2: Унификация Списков

Список 1 Список 2 Связывание Переменных
[X, Y, Z] [эгберт, ест, мороженое] X=эгберт, Y=ест, Z=мороженое
[7] [X | Y] X=7, Y=[]
[1, 2, 3, 4] [X, Y | Z] X=1, Y=2, Z=[3,4]
[1, 2] [3 | X] fail

Использование Списков

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

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

Вывод Списков на печать

Например, если Вы хотите только вывести на печать элементы списка, то вот что Вы делаете:

Здесь мы видим два клауза write_a_list, которые можно выразить но обычном языке:

  • Для вывода на печать пустого списка ничего не надо делать.
  • Иначе, для вывода на печать списка, вывести на печать его голову (она есть просто элемент), и потом вывести на печать хвост списка (он, как известно, есть список).

Первый раз, когда вызывается:

такой вызов сопоставляется со вторым клаузом, с головой H=1 и T=[2, 3]. Это приводит к выводу на печать 1, затем рекурсивно вызывается write_a_list с аргументом в виде хвоста списка:

Этот второй вызов опять сопоставляется со вторым клаузом, где, на этот раз H=2 и T=[3], поэтому выводится 2 и опять рекурсивно вызывается write_a_list:

С каким клаузом теперь такой вызов сопоставлятся? Напомним, что, хотя список [3] имеет всего один элемент, у него есть голова и хвост — голова есть 3, а хвост есть []. Таким образом, этот вызов опять сопоставляется со вторым клаузом с H=3 и T=[]. Теперь выводится 3 и вызывается рекурсивно write_a_list:

Теперь становится понятно для чего нужен первый клауз. Второй клауз не может быть сопоставлен с таким вызовом, поскольку [] не может быть разделен на голову и хвост. Если бы первого клазуа здесь не было бы, то выполнение goal оказалось бы неуспешным. Но, поскольку он есть, то первый клауз сопоставляется с вызовом и выполнение goal успешно завершается и нечего более не делается.

Подсчет элементов в Списке

Рассмотрим теперь, как подсчитать число элементов в списке, или какова длина списка? Логично определить:

  • Длина пустого списка [] есть 0.
  • Длина любого другого списка есть 1 плюс длина его хвоста.

Можно ли это запрограммировать? На Прологе это очень просто. Всего два клауза:

Посмотрите прежде всего на второй клауз. Строго говоря, [_|T] сопоставляется с любым непустым списком, связывая T с хвостом списка. Значение головы неважно, если она есть, она может быть учтена как один элемент.

сопоставляется со вторым клаузом, с T=[2, 3]. Следующим шагом является вычисление длины хвоста T. Когда это сделано (не имеет значение, как), TailLength получит значение 2, и компьютер теперь может добавить 1 к ней и связать L со значением 3. Как выполняется этот промежуточный шаг? Надо найти длину списка [2, 3], путем удовлетворения цели

Другими словами, length_of вызывает себя рекурсивно. Этот вызов сопоставляется со вторым клаузом, связывая

  • [3] и T в вызове клаузы и
  • TailLength с L в клаузе.

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

Итак, теперь задача — найти длину списка [3], которая есть 1, и мы добавляем 1 к этому значению, чтобы получить длину списка [2, 3], что будет 2. Ну и хорошо!.

Аналогично, length_of вызывает себя рекурсивно опять для получения длины списка [3]. Хвост [3] есть [], поэтому T связывается с [], и задача теперь — получение длины списка [] и добавление к ней 1, что дает длину списка [3].

Теперь все просто. Цель:

сопоставляется с первым клаузом, связывая TailLength с 0. Поэтому теперь компьютер может добавить 1 к нему, получая длину списка [3], и возвращаясь теперь в вызывавший клауз. Это, в свою очередь, опять добавляет 1, давая длину списка [2, 3], и возвращается в клауз, который его вызывал; этот первоначальный клауз добавит снова 1, давая длину списка [1, 2, 3].

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

Обратите внимание, что Вам не нужно каждый раз создавать такого рода предикаты самостоятельно, Вы можете использовать готовый предикат list::length из PFC.

Хвостовая рекурсия

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

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

  • Один из них — это список, от которого компьютер будет откусывать по одному элементу на каждом вызове до тех пор, пока этот список, как и прежде, не превратится в пустой список.
  • Второй — это свободный аргумент, который в конечном итоге вернет результат (длину).
  • Третий — это счетчик, значение которого начинается с нуля и увеличивается с каждым вызовом.

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

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

Модификация Списка

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

На обычном языке это звучит так:

  • Добавление 1 ко всем элементам пустого списка порождаем пустой список,
  • Для добавления 1 ко всем элемента любого другого списка:
    • добавить 1 к голове и сделать эту голову головой результирующего списка, а затем
    • добавить 1 к каждому элемента хвоста и этот хвост сделать хвостом результата.


Загрузим программу и выполним такую цель

Опять о хвостовой рекурсии

Является ли предикат add1 проедикатом с хвостовой рекурсией? Если у Вас есть опыт использования Lisp или Pascal, Вы могли бы подумать, что нет, поскольку Вы бы рассуждали так:

  • Делим список на Head и Tail.
  • Добавляем 1 к Head, получаем Head1.
  • Рекурсивно добавляя 1 ко всем элементам списка Tail, получаем Tail1.
  • Соединяем Head1 и Tail1, что дает результирующий список.

Это не похоже на хвостовую рекурсию, поскольку последний шаг — не рекурсивный вызов.

Однако, и это важно, – Это не то, что делает Пролог. В Visual Prolog add1 является предикатом с хвостовой рекурсией, поскольку выполняется в действительности следующим образом:

  • Связать голову и хвост исходного списка с Head и Tail, соответственно.
  • Связать голову и хвост результирующего списка с Head1 и Tail1, соответственно. (Head1 и Tail1 пока не получили значений.)
  • Добавить 1 к Head, что дает Head1.
  • Рекурсивно добавить 1 ко всем элементам списка Tail, что дает Tail1.

Когда это сделано, Head1 и Tail1 уже являются головой и списком результата и отдельной операции по их соединению нет. Поэтому рекурсивный вызов и является последним шагом.

Снова Модификация Списков

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

А вот — предикат который копирует элементы списка, добавляя для каждого элемента его дубликат:

Принадлежнось списку

Допустим, имеется список с именами John, Leonard, Eric и Frank и требуется, используя Visual Prolog, выяснить, принадлежит ли заданное имя этому списку. Другими словами, надо определить «отношение» между двумя аргументами: именем и списком имен. Это соответствует предикату

В программе e01.pro первый клауз исследует голову списка. Если голова списка совпадает с искомым именем, то можно сделать заключение, что Name принадлежит списку. Поскольку хвост списка нас не интересует, то это мы представляем анонимной переменной. Благодаря первому клаузу, цель

Если голова списка не есть Name, то надо исследовать, не содержится ли Name в хвосте списка.

На обычном языке:

Name принадлежит списку, если Name является первым элементом списка, или
Name принадлежит списку, если Name принадлежит хвосту.

Второй клауз предиката isMember относится к этому отношению. Таким образом на Visual Prolog:

Добавление списка к другому списку: декларативное и рекурсивное решения

Рассмотренный предикат member программы e01.pro работает в двух направлениях. Вернемся к его клаузам:

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

  • С декларативной точки зрения, клаузы выражают:
    • Name (Имя) принадлежит списку, если голова списка есть Name
    • иначе Name принадлежит списку, если оно (Имя) принадлежит хвосту.
  • С процедурной точки зрения, эти же два клауза могут быть интерпретированы так:
    Чтобы найти элемент списка
    • Найдите его голову
    • иначе найдите элемент хвоста списка.

Эти две точки зрения соответствуют целям

В результате первый вызов поручает Visual Prolog(у) проверить, истино ли нечто (принадлежность числа 2 списку [1,2,3,4]). Второй вызов поручает Visual Prolog(у) найти все члены списка [1,2,3,4]. Не смущайтесь этим. Предикат member является одним и тем же, но на его поведение можно смотреть под разными углами.

Рекурсия с процедуральной точки зрения

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

Этот предикат интегрирует списки List1 и List2 в форму списка List3 так, что список List2 дописывается в конце списка List1. То есть содержательно — осуществляется добавление списка List2 к списку LIst1. Опять мы используем рекурсию (на этот раз с процедуральной точки зрения).

Если список List1 пустой, результатом добавления списка List1 к списку List2 будет тот же самый List2. Запишем это на Прологе:

Если список List1 не пустой, то можно преобразовать списки List1 и List2 к форме списка List3, сделав голову списка List1 головой списка List3. В приведенном коде переменная H используется в качестве головы как списка List1, так и списка List3. хвост списка List3 есть список L3, который составлен из остатка списка List1 (а именно, L1) и всего списка List2. Опять выразим это на Прологе:

Предикат append работает следующим образом: пока список List1 не пустой, рекурсивное правило дописывает один элемент каждый раз к списку List3. Когда список List1 становится пустым, первый клауз clause обеспечивает дописывание списка List2 в конец списка List3.

Варианты использования одного предиката

Подходя к предикату append с декларативной точки зрения, мы определили его как отношение между тремя списками. Это отношение справедливо также, если списки List1 и List3 известны, а List2 — нет. Более того, это также работает, если только List3 известен. Например, для того, чтобы выяснить, какие два списка могли бы быть соединены для получения известного списка, можно использовать вызов в форме

С таким целевым вызовом, Visual Prolog найдет следующие решения:

Можно использовать предикат append для нахождения списка, который следовало бы добавить к списку [3,4] для получения списка[1,2,3,4]. Попробуем такой вызов

Visual Prolog находит решение

Предикат append определяет отношение между входным набором (input set) и выходным набором (output set) таким образом, что отношение применимо в обе стороны. При таком отношении возникает вопрос

Что является выходным набором для заданного входного? или Какой входной набор соответствует заданному выходному?

Статус аргументов данного вызова предиката известен как поток (или шаблон) ввода-вывода. Аргумент, который связан или наследуется в момент вызова является входным аргументом и обозначается как (i). Свободный аргумент является выходным аргументом и обозначается как (o).

Предикат append обладает свойством поддерживать любой шаблон ввода-вывода, какой требуется. Однако не все предикаты имеют возможность вызова с различными шаблонами ввода-вывода. Когда клауз Пролога способен поддерживать множество шаблонов ввода-вывода, он называется инверсным клаузом. Целый набор предикатов для обработки списков содержится в классе list.

Все Решения Сразу

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

Однако есть одна вещь, которую, в отличие от рекурсии, могут делать откаты, а именно – искать все альтернативные решения посредством одного вызова. Поэтому Вы можете оказаться в затруднительном положении: Вам нужно получить все решения за один вызов, и, при этом, они Вам нужны все сразу, как часть единой интегрированной структуры данных. Что делать?

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

  • Первый аргумент, VarName, определяет аргумент в вызываемом целевом предикате, значения которого будут собираться в список.
  • Второй — mypredicate — определяет предикат, который будет получать значения.
  • Выходной параметр ListParam, является переменной, которая содержит список значений, полученных в ходе отката.

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

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

Следующий код порождает список всех положительных чисел исходного списка:

Смешанные списки

Список целых объявляется просто

То же верно и для списков вещественных чисел (integer), символьных (symbol) списков или списков строк (string).

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

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

Пример объаявления списка, который может хранить целые, символы, строки или списки таких даных:

на Visual Prolog следовало бы записать так:

Следующий пример предиката append показывает как использовать такого рода декларации в стандартных программах манипулирования списками.

Разбор с использованием списков

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

Этот разборщик предназначен для примитивного формального языка. Хотя этот пример достаточно сложен с точки зрения этого руководства, мы решили поместит его здесь, поскольку разбор является одной из областей, где Visual Prolog очень эффективен. Если Вы чувствуете себя не вполне готовым для этого раздела, Вы можете этот пример пропустить и продолжить чтение руководства без потери содержательности.

Преобразование в этом примере представлено двумя шагами: сканирование и разбор. Предикат tokl — это сканер. Он принимает строку и преобразует ее в список токенов. Все предикаты с именами, начинающимися с s_ являются предикатами парсера. В этом примере входный текст представляет программу на языке, подобном языку Паскаль, и состоящей из Паскале-подобных предложений. Этот язык программирования позволяет только предложения вида: IF THEN ELSE, IF THEN, DO WHILE и присваивание (ASSIGNMENT). Предложения состоят из выражений и вложенных предложений. Выражения — сложение, вычитание, переменные и целые.

Далее, как это работает:

  • Предикат program, принимает список токенов и вызывает предикат statement_list передав ему этот список. Затем проверяется все ли токены были использованы в процессе разбора.
  • Предикат statement_list принимает список токенов и проверяет возможность деления токенов на предложения, завершающиеся точкой с запятой.
  • Предикат statement проверяет могут ли начальные токены списка (токенов) представлять собой правильное предложение. Если да, то такое предложение возвращается в виде структуры, а остаток токенов передается рекурсивно вызываемому предикату statement.
  • Четыре клауза предиката statement соответствуют четырем типам, которые парсер понимает.
  • Если первый клауз предиката statement не может преобразовать список токенов в предложение вида IF THEN ELSE, то клауз завершается неуспешно и в порядке отката переходит к следующему клаузу предиката statement.
  • Теперь делается попытка преобразовать список токенов в конструкцию вида IF THEN.
  • Если эта попытка неуспешна, то в следующем клаузе делается попытка преобразования к предложению вида DO WHILE.
  • Если первые три клауза предиката statement завершаются неуспешно, то последний клауз этого предиката провереяет представлена ли в списке токенов операция присваивания. Этот клауз проверяет «на присваивание» является ли первый терм символом, второй — знаком равно («=»), а следующие термы представляют простое математическое выражение.
  • Предикаты expression, term и termTail работают аналогично, путем проверки являются ли начальные термы выражениями и, если это так, то предикату statement возвращается остаток термов и математическое выражение в виде структуры.

Заключение

В этом руководстве раскрыта следующие важные моменты:

  • Списки могут содержать произвольное число элементов; Вы объявляете их простым добавление звездочки (*) в конце ранее определённого домена.
  • Список является рекурсивным составным объектом, состоящим из головы и хвоста. Голова есть первый элемент, а хвост — остальная часть списка (без первого элемента). Хвост списка — всегда список; голова списка — всегда элемента. Список может содержать ноль или более элементов; Пустой список обозначается [].
  • Элементами списка может быть что угодно, включая другие списки; все элементы списка должны принадлежать одному домену. В этом случае объявление домена элементов должно выглядеть так:

где elements = один из стандартных доменов (integer, real, etc.) или набор альтернатив обозначенных различными функторами (int(integer); rl(real); smb(symbol); и т.д.). Смешение типов в списках языка системы Visual Prolog допускается только включением их в составные объекты или функторы.

  • Можно использовать разделители (запятые, [ и |) для явного отделения головы списка от хвоста. Так, список

Примеры программ с использованием фактов и правил

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГАОУ ВО «Крымский федеральный университет
имени В. И. Вернадского»

Таврическая академия (структурное подразделение)

ЛОГИЧЕКОЕ ПРОГРАММИРОВАНИЕ

КОЗЛОВА М.Г.

Логическое программирование: учебно-методическое пособие / М. Г. Козлова. ФГАОУ ВО «Крымский федеральный университет имени В. И. Вернадского». Симферополь, 2020. 54 с.

Пособие содержит учебно-методический материал и задания по практической части курса «Логическое программирование».

Предназначено для студентов 3-го курса направления подготовки 01.03.02 — Прикладная математика и информатика.

©Козлова М.Г., КФУ, 2020

Лабораторная работа №1. Основы программирования на Прологе 4

Лабораторная работа №2. Использование рекурсии в Прологе. 16

Лабораторная работа №3. Представление и обработка списков .……26

Лабораторная работа №4. Сортировка списков ………………….……35

Лабораторная работа №5. Множества. ………………….……46

Лабораторная работа №6. ………………….……11

Лабораторная работа №7. ………………….……11

Лабораторная работа №8. ………………….……11

Лабораторная работа №9. ………………….……11

Лабораторная работа №10. ………………….……11

ЛАБОРАТОРНАЯ РАБОТА №1

ОСНОВЫ ПРОГРАММИРОВАНИЯ НА ПРОЛОГЕ

Цель работы

Изучение структуры программ. Разработка Пролог-программ с использованием фактов и правил. Организация запросов к программе.

Краткие сведения

Основные понятия

Пролог — язык логического программирования, основанный на логике предикатов первого порядка. Пролог-программы содержат описание логических взаимосвязей, необходимых для решения задачи. С точки зрения логики предикатов элементарные выражения имеют вид

где — имя предиката, — аргументы.

Например, предложение «Степан является дядей Ольги» на Прологе запишется в виде: Uncle(stepan,olga), где Uncle — предикат, описывающий отношение «является дядей»; stepan, olga — объекты «Степан» и «Ольга», связанные отношением Uncle.

Предложения в Прологе бывают трех типов: факты, правила и запросы.

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


Эти факты констатируют, что «igor — мужчина», «anna — женщина», «igor является родителем anna».

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

grandmother(X,Y) :- parent(X,Z), parent(Z,Y), woman(X).

Первое правило устанавливает, что «X является ребенком Y», если истинно выражение «Y является родителем X». Второе правило говорит, что «X является бабушкой Y», если выполняется, что существует такой Z, что «X является родителем Z» и «Z является родителем Y», и «X является женщиной».

Правила позволяют определять новые предикаты через уже имеющиеся. В данном случае предикат child (ребенок) определяется через предикат parent (родитель), и предикат grandmother (бабушка) через предикаты parent и woman (женщина).

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

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

woman(anna). woman(irina). woman(svetlana). предикат, описывающий женщин.
man(igor). — предикат, описывающий мужчину.
parent(anna,igor). parent(igor,irina). предикат, описывающий родителей.
grandmother (X,Y) :- parent(X,Z), parent(Z,Y), woman(X). процедура grandmother

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

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

В Прологе выделяется анонимная переменная — знак подчеркивания «_», — которая предписывает проигнорировать значение аргумента. Например, в предложении

mother(X) :- parent(X,_), woman(X).

определяется предикат mother (мама), условная часть которого содержит предикат «X является родителем Y». В связи с тем, что для предиката mother не важно, родителем кого именно является X, то второй аргумент в предикате parent — анонимная переменная.

Запрос (цель) инициализирует процедуру поиска в программе (факты + правила). Пролог просматривает факты и правила в поисках предиката, сопоставимого с запросом.

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

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

ancestor(X,Y) :- parent(Z,Y), ancestor(X,Z).

Первое правило определяет «непосредственного предка» — родителя, а второе — «отдаленного предка» (предка родителя).

Типы доменов Пролога

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

Тип данных Ключевое слово Пример
Символы char ‘б’, ‘? ‘, ‘z’
Целые числа integer 32, -120
Действительные числа real 0.12, -3.14
Строки string «baby», «157»
Символьные имена symbol p, q, r, anna, «Ivan»
Файлы file proba.txt

В Прологе можно вводить собственные имена типов доменов для придания смысла аргументу предиката. Типы доменов используются для описания предикатов в разделе predicates. Например:

title, producer = symbol

film (title, producer, year)

film (symbol, symbol, integer)

Пролог-программа может состоять из пяти разделов:

1) domains — описание доменов, которые описывают классы объектов, используемых в программе;

2) database — определение баз данных, которые являются предикатами динамической базы данных;

3) predicates — описание предикатов, используемых в программе;

4) clauses — описание фактов и правил;

5) goal — описание запроса (цели) создаваемой программы.

Арифметические операторы

Арифметические операции: + (сложение), — (вычитание), / (деление), * (умножение), div (частное от деления нацело), mod (остаток от деления нацело). Операндами операций div и mod могут быть только целые значения.

Операции отношения: >, >=, , > , > 0 — не единственное решение

write(«Two solves X1=»,X1,» X2=»,X2).

Тогда, на запрос

на экране появится Not real answer

будет решение One solve X=-1

будет выдано решение Two solves X1=10 X2=5

Варианты заданий

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

1. Определить предикат ОТЕЦ и найти всех отцов.

2. Определить предикат МАТЬ и найти всех матерей.

3. Определить предикат ДЕТИ и найти всех детей конкретного лица.

4. Определить предикат ВНУКИ и найти всех внуков конкретного лица.

5. Определить предикат СЫН и найти всех сыновей и сыновей конкретного лица.

6. Определить предикат ДОЧЬ и найти всех дочерей и дочерей конкретного лица.

7. Определить предикат ДЕДУШКА и найти всех дедушек и дедушек конкретного лица.

8. Определить предикат БАБУШКА и найти всех бабушек и бабушек конкретного лица.

9. Определить предикат ДВОЮРОДНЫЙ ДЕДУШКА и найти всех двоюродных дедушек и двоюродных дедушек конкретного лица.

10. Определить предикат ДВОЮРОДНАЯ БАБУШКА и найти всех двоюродных бабушек и двоюродных бабушек конкретного лица.

11. Определить предикат ТЕТЯ и найти всех тетей и тетей конкретного лица.

12. Определить предикат ДЯДЯ и найти всех дядей и дядей конкретного лица.

13. Определить предикат БРАТ и найти всех братьев и братьев конкретного лица.

14. Определить предикат СЕСТРА и найти всех сестер и сестер конкретного лица.

15. Определить предикат ДВОЮРОДНЫЙ БРАТ и найти всех двоюродных братьев и двоюродных братьев конкретного лица.

16. Определить предикат ДВОЮРОДНАЯ СЕСТРА и найти всех двоюродных сестер и двоюродных сестер конкретного лица.

17. Определить предикат ТРОЮРОДНЫЙ БРАТ и найти всех троюродных братьев и троюродных братьев конкретного лица.

18. Определить предикат ТРОЮРОДНАЯ СЕСТРА и найти всех троюродных сестер и троюродных сестер конкретного лица.

19. Определить предикат ПЛЕМЯННИК и найти всех племянников и племянников конкретного лица.

20. Определить предикат ПОТОМОК и найти всех потомков и потомков конкретного лица.

21. Определить предикат ПРЕДОК и найти всех предков и предков конкретного лица.

22. Определить предикат ПОТОМОК МУЖСКОГО ПОЛА и найти всех потомков мужского пола и потомков мужского пола конкретного лица.

23. Определить предикат ПОТОМОК ЖЕНСКОГО ПОЛА и найти всех потомков женского пола и потомков женского пола конкретного лица.

24. Определить предикат ПРЕДОК МУЖСКОГО ПОЛА и найти всех предков мужского пола и предков мужского пола конкретного лица.

25. Определить предикат ПРЕДОК ЖЕНСКОГО ПОЛА и найти всех предков женского пола и предков женского пола конкретного лица.

Задание 1.2. Написать программу на Прологе.

1. Заданы три числа a, b, c. Определить, сколько среди них положительных.

2. Заданы четыре числа a, b, c, d. Определить количество нулевых значений.

3. Заданы четыре числа a, b, c, d. Определить, сколько среди них отрицательных.

4. Задана прямая . Для произвольной точки определить, как расположена она относительно прямой: выше прямой; на прямой; ниже прямой.

5. Заданы три числа a, b, c. Определить, являются ли они упорядоченными: по возрастанию; равны (a=b=c); по убыванию; не упорядочены. Сколько среди них отрицательных?

6. Заданы три числа a, b, c. Найти сумму положительных чисел.

7. Заданы три числа a, b, c. Определить, сколько среди них отрицательных.

8. Заданы три числа a, b, c. Определить среди них количество максимумов.

9. Заданы три числа a, b, c. Определить среди них количество минимумов.

10. Заданы три числа a, b, c. Определить минимальное значение среди положительных.

11. Заданы три числа a, b, c. Определить максимальное значение среди отрицательных.

12. Для произвольных чисел a, b, c определить количество действительных корней уравнения .

13. Заданы три точки , , . Определить их взаимное расположение: все точки совпадают; две точки совпадают, а третья отличается; все точки отличаются.

14. Заданы три точки , , . Определить их взаимное расположение: точки лежат на одной прямой; точки образуют невырожденный треугольник.

15. Задана система координат в пространстве и произвольная точка (x,y,z). Определить, как расположена точка относительно системы координат: в начале системы координат; на одной из осей; вне осей координат.

16. Заданы прямая и две точки , . Определить их взаимное расположение: точки по одну сторону прямой; точки по разные стороны от прямой; одна точка на прямой, а другая — нет; обе точки на прямой.

17. Задана система координат на плоскости и произвольная точка (x,y). Определить, где лежит точка: на пересечении осей координат; на оси Х; на оси Y; вне осей координат.

18. Задана система координат на плоскости и произвольная точка (x,y). Определить, где лежит точка: на осях координат; в I квадранте; во II квадранте; в III квадранте; в IV квадранте.

19. Задана окружность с центром (x,y) и радиусом r. Определить взаимное расположение окружности и осей координат: окружность пересекает обе оси; окружность пересекает только ось Х; окружность пересекает только ось Y; окружность не пересекает осей координат.

20. Задан отрезок своими концами , . Определить взаимное расположение отрезка и осей координат: отрезок параллелен оси Х; отрезок параллелен оси Y; отрезок не параллелен осям координат; отрезок вырожден.

21. Задан отрезок своими концами , . Определить взаимное расположение отрезка и осей координат: отрезок лежит на какой-то оси координат; отрезок параллелен какой-то оси координат; отрезок не параллелен осям координат.

22. Задан треугольник своими сторонами a, b, c. Определить, образуют ли они: равносторонний треугольник; равнобедренный треугольник; не образуют треугольника.

23. Задан треугольник своими сторонами a, b, c. Определить, образуют ли они: прямоугольный треугольник; тупоугольный треугольник; остроугольный треугольник; не образуют треугольника.

24. Заданы прямые , . Определить их взаимное расположение: пересекаются; параллельны; совпадают.

25. Заданы два круга с центрами , и радиусами , соответственно. Определить взаимное расположение кругов: один внутри другого; пересекаются; не пересекаются.

Лекция 3: Основные понятия Пролога

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

Начнем с того, что познакомимся с так называемой нормальной формой Бэкуса-Наура (БНФ), разработанной в 1960 Джоном Бэкусом и Питером Науром и используемой для формального описания синтаксиса языков программирования. Впервые БНФ была применена Питером Науром при записи синтаксиса языка Алгол-60.

При описании синтаксиса конструкций используются следующие обозначения:

Символ ::= читается как «по определению» («это», «есть»). Слева от разделителя располагается объясняемое понятие, справа — конструкция, разъясняющая его. Например,

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

Символ | означает в нотации БНФ «или», он применяется для разделения различных альтернативных растолкований определяемого понятия.

Пример. Десятичную цифру можно определить следующим образом:

Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать);

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

Символ * обозначает, что часть синтаксической конструкции может повторяться произвольное число раз (ноль и более). Заметим, что иногда вместо символа * используют фигурные скобки (<,>).

Пример. Определить положительное целое число в нотации БНФ можно следующим образом:

То есть положительное целое число состоит из одной или нескольких цифр.

Программа на языке Пролог, ее иногда называют базой знаний, состоит из предложений (или утверждений), каждое предложение заканчивается точкой.

Предложения бывают двух видов: факты, правила.

Предложение имеет вид

A называется заголовком или головой предложения, а B1. Bn — телом.

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

Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Можно считать, что факт — это предложение, у которого тело пустое.

Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде:


Факт представляет собой безусловно истинное утверждение.

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

Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:

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

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

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

Соответственно, приведенный выше пример факта можно записать в Турбо Прологе, например, так:

Некоторые предикаты уже известны системе, они называются стандартными или встроенными.

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

В приведенном выше примере про то, что Наташа является мамой Даши, мама — это имя двухаргументного предиката, у которого строковая константа «Наташа» является первым аргументом, а строковая константа «Даша» — вторым.

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

В нотации БНФ правило будет иметь вид:

Пример. Известно, что бабушка человека — это мама его мамы или мама его папы.

Соответствующие правила будут иметь вид:

Символ «:-» означает «если», и вместо него можно писать if.

Символ «,» — это логическая связка «и» или конъюнкция, вместо него можно писать and.

Первое правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z — мамой Y. Второе правило сообщает, что X является бабушкой Y, если существует такой Z, что X является мамой Z, а Z — папой Y.

В данном примере X, Y и Z — это переменные.

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

Переменные могут быть свободными или связанными.

Свободная переменная — это переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными.

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

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания «_». Анонимная переменная применяется в случае, когда значение переменной не важно. Каждая анонимная переменная — это отдельный объект.

Третьим специфическим видом предложений Пролога можно считать вопросы.

Вопрос состоит только из тела и может быть выражен с помощью БНФ в виде:

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

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

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

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

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

Можно сказать, что утверждение — это правило, а факт или вопрос — это его частный случай.

Рассмотрим несколько примеров. Пусть в программе заданы следующие отношения:

Можно спросить у системы, является ли Наташа мамой Даши. Этот вопрос можно ввести в виде:

Найдя соответствующий факт в программе, система ответит «Yes» (то есть «Да»). Если мы спросим:

то получим ответ «No» (то есть «Нет»). Можно также попросить вывести имя мамы Даши:

Система сопоставит вопрос с первым фактом, конкретизирует переменную X значением «Наташа» и выдаст ответ:

Вопрос об имени дочери Наташи записывается в виде:

Соответствующим ответом будет:

Можно попросить систему найти имена всех известных ей мам и дочек, задав вопрос:

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

В итоге получим ответ:

Если надо получить только имена всех мам, можно воспользоваться анонимной переменной и записать вопрос:

И, наконец, если надо получить ответ на вопрос: есть ли информация о людях, находящихся в отношении «мама — дочка», то его можно сформулировать в виде:

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

Введем в нашу программу правило, определяющее отношение «бабушка — внучка», в терминах «быть мамой»:

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

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

Для того чтобы найти ответ на вопрос, система просмотрит нашу базу сверху вниз, пытаясь найти предложение, в заголовке которого стоит предикат бабушка. Найдя такое предложение (это предложение бабушка(X,Y):-мама(X,Z),мама(Z,Y)), система конкретизирует переменную из заголовка предложения X именем «Наташа», переменную Y с переменной X из вопроса, после чего попытается достигнуть цели: мама(«Наташа»,Z) и мама(Z,Y). Для этого она просматривает базу знаний в поиске предложения, заголовок которого можно сопоставить с предикатом мама(«Наташа»,Z).

Это можно сделать, конкретизировав переменную Z именем «Даша». Затем система ищет предложение, в заголовке которого стоит предикат мама с первым аргументом «Даша» и каким-то именем в качестве второго аргумента. Подходящим предложением оказывается факт мама(«Даша»,»Маша»). Система установила, что обе подцели мама(«Наташа»,Z) и мама(Z,Y) достижимы при Z=»Даша», Y=»Маша». Она выдает ответ:

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

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

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

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

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

Решение можно записать в следующем виде:

X>Y. /* если первое число больше второго,

то первое число — максимум */

X Y. /* если первое число больше второго,

то первое число — максимум */

X Y) не выполнено, будет проверяться второе условие (X Y, значит X Y. /* если первое число больше второго,

то первое число — максимум */

max2(_,Y,Y). /* в противном случае максимумом будет

В случае, если сработает отсечение, а это возможно, только если окажется истинным условие X>Y, Пролог-система не будет рассматривать альтернативное второе предложение. Второе предложение «сработает» только в случае, если условие оказалось ложным. В этой ситуации в третий аргумент попадет то же значение, которое находилось во втором аргументе. Обратите внимание, что в этом случае нам уже не важно, чему равнялся первый аргумент, и его можно заменить анонимной переменной.

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

Пример «красного» отсечения имеется в реализации предиката max2 (если убрать отсечение, предикат будет выдавать в качестве максимума второе число, даже если оно меньше первого). Пример «зеленого» отсечения можно получить, если в запись предиката max добавить отсечения (при их наличии предикат будет выдавать те же решения, что и без них).

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

будет соответствовать оператору if then P else P2, то есть если условие имеет место, то выполнить P, иначе выполнить P2. Например, в случае с максимумом, можно расшифровать нашу процедуру как «если X>Y, то M=X, иначе M=Y».

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

Подходов к решению этой задачи может быть несколько.

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

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

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

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

и третьему, то второе число является

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

и второму, то максимум — это третье число */

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

Применение отсечения позволит существенно сократить решение:

/* если первое число больше второго и третьего,

то первое число — максимум */

/* иначе, если второе число больше третьего,

то второе число является максимумом */

max3b(_,_,Z,Z). /* иначе максимум — это третье число */

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

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

max2(X,Y,XY), /* XY — максимум из X и Y */

max2(XY,Z,M). /* M — максимум из XY и Z */

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

Семантические модели Пролога

В Прологе обычно применяются две семантические модели: декларативная и процедурная. Семантические модели предназначены для объяснения смысла программы.

В декларативной модели рассматриваются отношения, определенные в программе. Для этой модели порядок следования предложений в программе и условий в правиле не важен.

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

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

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

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

Создайте предикат, находящий максимум из четырех чисел.

Создайте предикат, проверяющий, являются ли два человека

дедушкой и внуком (внучкой);

дядей и племянником (племянницей);

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

Создайте предикат, находящий абсолютное значение числа (=X, если X>=0, и =-X, если X

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9440 — | 7438 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Сортировка факты в Прологе

Как сортировать факты по своей переменной Как

Студент (5). Студент (3). Студент (2). Студент (3). Студент (6).

Я хочу сделать функцию, чтобы сделать их

Student (2). Студент (3). Студент (3). Студент (5). Студент (6).

Создан 28 дек. 13 2013-12-28 07:42:33 user3141421

2 ответа

Я бы сначала собрать все эти факты в список с помощью FindAll (пример: How to create a list from facts in Prolog?), а затем отсортировать этот список (например: Sorting a list in Prolog, или просто использовать встроенный сортировки/2 предикат).

(Отправленные с моего телефона)

Создан 28 дек. 13 2013-12-28 08:01:22 Ido.Co

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

Затем, несколько вещей, которые вы можете сделать:

(как это было предложено в другом ответе)

Если вы хотите иметь их переменный ток tually отсортированы в базе данных, и не боитесь изменить базу данных во время выполнения, вы можете удалить все student/1 из базы данных с abolish/1 и повторно вставить отсортированные факты:

Это не очень хорошая идея сделать это неоднократно! Если у вас регулярно меняется база данных студентов, вы можете не помещать их в базу данных, а вместо этого использовать, например, список ассоциаций, как в library(assoc)

Создан 28 дек. 13 2013-12-28 08:08:15 Anonymous

Ваш первый запрос вернет L = [3,5]. Как получить L = [ученик (3), ученик (5)], потому что я думаю, что OP ищет это. Также мы можем использовать setof/3? – ssBarBee 28 дек. 13 2013-12-28 08:44:59

@ssBarBee Ваше предложение вводит в заблуждение список фактов в базе данных со списком терминов. Думаю, это вопрос вкуса. Вы не можете использовать ‘setof/3’, если будете следовать точному вопросу, так как он удалит дубликаты. Или я неправильно понимаю ваш комментарий? – user1812457 28 дек. 13 2013-12-28 08:48:54

Илон Маск рекомендует:  Что такое код pdf_stroke
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL