Алгоритм приведения произвольной формулы исчисления предикатов к множеству дизъюнктов
Первый шаг. Приводим исходную формулу к предваренной нормальной форме. Для этого:
пользуясь эквивалентностью A
¬(A
переименовываем связанные переменные так, чтобы ни одна переменная не входила в нашу формулу одновременно связанно и свободно.выносим кванторы в начало формулы, используя эквивалентности:
QxA(x)
QxA(x)
Q1xA(x)
Q1xA(x)
Второй шаг. Проведем сколемизацию, т.е. элиминируем в формуле кванторы существования. Для этого для каждого квантора существования выполним следующий алгоритм.
Если устраняемый квантор существования — самый левый квантор в префиксе формулы, заменим все вхождения в формулу переменной, связанной этим квантором, на новую константу и вычеркнем квантор из префикса формулы.
Если левее этого квантора существования имеются кванторы всеобщности, заменим все вхождения в формулу переменной, связанной этим квантором, на новый функциональный символ от переменных, которые связаны левее стоящими кванторами всеобщности, и вычеркнем квантор из префикса формулы.
Проведя этот процесс для всех кванторов существования, получим формулу, находящуюся в сколемовской нормальной форме. Алгоритм устранения кванторов существования придумал Сколем в 1927 году.
Имеет место теорема о том, что формула и ее сколемизация эквивалентны в смысле выполнимости.
Третий шаг. Элиминируем кванторы всеобщности. Полученная формула будет бескванторной и эквивалентной исходной в смысле выполнимости.
Четвертый шаг. Приведем формулу к конъюнктивной нормальной форме, для чего воспользуемся эквивалентностями, выражающими дистрибутивность:
A
Пятый шаг. Элиминируем конъюнкции, представляя формулу в виде множества дизъюнктов.
Получаем множество дизъюнктов, эквивалентное исходной формуле в том смысле, который дает нам следующая теорема.
Теорема. Формула является тождественно ложной тогда и только тогда, когда множество дизъюнктов, полученных из нее, является невыполнимым.
Напомним, что множество формул называется невыполнимым, если не существует такого означивания переменных, чтобы все формулы из этого множества были бы истинными.
Пример. Превратим формулу
Первый шаг. Приведем исходную формулу к предваренной нормальной форме. Элиминировав импликацию, получим формулу
Второй шаг. Проведем сколемизацию полученной формулы. Левее квантора существования стоит квантор всеобщности, значит, нужно заменить все вхождения переменной y новым унарным функциональным символом, зависящим от x. Получим формулу, находящуюся в сколемовской нормальной форме:
Третий шаг. Элиминируем квантор всеобщности: ¬P(x)
В четвертом и пятом шагах необходимости нет, поскольку формула уже представляет собой дизъюнкт: ¬P(x)
Следующая техника, лежащая в основе Пролога, с которой мы попробуем разобраться, — это унификация. Унификация позволяет отождествлять формулы логики первого порядка путем замены свободных переменных на термы.
Подстановка — это множество вида {x1/t1,..., xn/tn}, где для всех i, xi — переменная, а ti — терм, причем xi
Символом ? будем обозначать пустую подстановку.
Подстановка, в которой все термы основные, называется основной подстановкой.
Простое выражение — это терм или атомная формула.
Если A — простое выражение, а ? — подстановка, то A? получается путем одновременной замены всех вхождений каждой переменной из A соответствующим термом. A? называется частным случаем (примером) выражения A. Содержательно подстановка заменяет каждое вхождение переменной xi на терм ti.
Пусть ? и ? — подстановки, ?={x1/t1,..., xn/tn}, ?={y1/s1,...,yn/sn}. Композиция ?? получается из множества {x1/t1?,...,xn/tn?,y1/s1,..., yn/sn} удалением пар xi/ti?, где xi
Пример. Пусть ?={x/f(y),y/z}, ?={x/a,y/b,z/y}. Построим ??. Для этого возьмем множество {x/f(b),y/y,x/a,y/b,z/y} и выбросим из него пары y/y (потому что заменяемая переменная совпадает с термом), ,x/a,y/b (потому что заменяемая переменная из подстановки ? совпадает с заменяемой переменной из подстановки ?). Получим ответ: ??={x/f(b),z/y}.
Подстановка ? называется более общей, чем подстановка ?, если существует такая подстановка ?, что ?=??.
Подстановка ? называется унификатором простых выражений A и B, если A?=B?. Про A и B в такой ситуации говорят, что они унифицируемы. Унификация используется в Прологе для композиции и декомпозиции структур данных.
Пример. A=p(f(x),z) и B=p(y,a) унифицируемы. Можно взять в качестве их унификатора подстановку {y/f(x),z/a} или подстановку {y/f(a),x/a,z/a}.
Вообще говоря, две формулы могут иметь бесконечно много унификаторов. Унификатор ? называют наиболее общим (или простейшим) унификатором простых выражений A и B, если он является более общей подстановкой, чем все другие унификаторы простых выражений A и B.
Пример. В рассмотренном выше примере наиболее общим унификатором является подстановка {y/f(a),z/a}.
Пусть S — конечное множество простых выражений. Определим множество d(S) разногласий (рассогласований). Зафиксируем самую левую позицию, на которой не во всех выражениях из S стоит один и тот же символ. Занесем в d(S) подвыражения выражений из S, начинающиеся с этой позиции.
Пример. Пусть S={p(f(x),h(y),a),p(f(x),z,a),p(f(x),h(y),b)}.Множество рассогласований для S d(S)={h(y),z}.
Алгоритм унификации
Дадим алгоритм поиска наиболее общего унификатора для конечного множества простых выражений S. В том случае, если это множество не унифицируемо, алгоритм должен обнаруживать эту ситуацию.
Шаг 1. Полагаем k=0,
Шаг 2. Если S
Шаг 3. Если в d(S
Обратите внимание, что алгоритм унификации заканчивает свою работу за конечное число шагов для любого конечного множества простых выражений, потому что на каждом проходе мы уменьшаем количество переменных. Так как множество простых выражений было конечным, то и множество различных переменных в нем конечно, и, значит, через число шагов, не превышающее количества различных переменных, алгоритм завершится.
Утверждение о том, что для любого унифицируемого конечного множества простых выражений S алгоритм унификации закончит свою работу и выдаст наиболее общий унификатор для S, называется теоремой унификации.
Теперь можно перейти к рассмотрению метода резолюций.
В чем вообще заключается задача? Мы хотим построить алгоритм, который позволял бы нам автоматически давать ответ на вопрос, может ли быть выведено некоторое заключение из множества имеющихся посылок. Известно, что в общем случае даже для логики первого порядка такой алгоритм невозможен. Как правило, формальные системы, для которых можно построить подобный разрешающий алгоритм, обладают небольшой выразительной силой. К ним, например, относится логика высказываний и логика одноместных предикатов.
Однако Робинсон решил, что правила вывода, используемые компьютером при автоматическом выводе, не обязательно должны совпадать с правилами вывода, используемыми при "человеческом" выводе. В частности, он предложил вместо правила вывода "modus ponens", которое утверждает, что из A и A
Правило резолюции для логики высказываний можно сформулировать следующим образом.
Если для двух дизъюнктов существует атомная формула, которая в один дизъюнкт входит положительно, а в другой отрицательно, то, вычеркнув соответственно из одного дизъюнкта положительное вхождение атомной формулы, а из другого — отрицательное, и объединив эти дизъюнкты, мы получим дизъюнкт, называемый резольвентой. Исходные дизъюнкты в таком случае называются родительскими или резольвируемыми, а вычеркнутые формулы — контрарными литералами. Другими словами, резольвента — это дизъюнкт, полученный из объединения родительских дизъюнктов вычеркиванием контрарных литералов.
Графически это правило можно изобразить так:
(A
Здесь A
Если родительские дизъюнкты состояли только из контрарных литералов, то резольвентой будет пустой дизъюнкт.
Пример. Правило вывода "modus ponens" получается из правила резолюции, если взять в качестве родительских дизъюнктов C1=A, C2=¬A
Сформулируем правило резолюции для логики первого порядка.
Пусть имеется два дизъюнкта C1 и C2, у которых нет общих переменных, L1 — литерал, входящий в дизъюнкт C1, L2 — литерал, входящий в дизъюнкт C2. Если литералы имеют наибольший общий унификатор ?, то дизъюнкт (C1?–L1?)
(A
Здесь P1 и P2 — контрарные литералы, (A
Метод резолюций является обобщением метода "доказательства от противного". Вместо того чтобы пытаться вывести некоторую формулу-гипотезу из имеющегося непротиворечивого множества аксиом, мы добавляем отрицание нашей формулы к множеству аксиом и пытаемся вывести из него противоречие. Если нам удается это сделать, мы приходим к выводу (пользуясь законом исключенного третьего), что исходная формула была выводима из множества аксиом. Опишем более подробно.
Добавим отрицание исходной формулы к множеству посылок, преобразуем каждую из этих формул во множество дизъюнктов, объединим получившиеся множества дизъюнктов и попытаемся вывести из этого множества дизъюнктов противоречие (пустой дизъюнкт ?). Для этого будем выбирать из нашего множества дизъюнкты, содержащие унифицируемые контрарные литералы, вычислять их резольвенту по правилу резолюции, добавлять ее к исследуемому множеству дизъюнктов. Этот процесс будем продолжать до тех пор, пока не выведем пустой дизъюнкт.
Возможны, вообще говоря, три случая:
Этот процесс никогда не завершается.Среди текущего множества дизъюнктов не окажется таких, к которым можно применить правило резолюции. Это означает, что множество дизъюнктов выполнимо, и, значит, исходная формула не выводима.На очередном шаге получена пустая резольвента. Это означает, что множество дизъюнктов невыполнимо и, следовательно, начальная формула выводима.
Имеет место теорема, утверждающая, что описанный выше процесс обязательно завершится за конечное число шагов, если множество дизъюнктов было невыполнимым.
С другой стороны, мы опираемся на результат, что формула выводима из некоторого множества формул тогда и только тогда, когда описанное множество дизъюнктов невыполнимо. А также на то, что множество дизъюнктов невыполнимо тогда и только тогда, когда из него применением правила резолюции можно вывести пустой дизъюнкт.
В сущности, метод резолюций несовершенен и приводит к "комбинаторному взрыву". Однако некоторые его разновидности (или стратегии) довольно эффективны. Одной из самых удачных стратегий является линейная или SLD-резолюция для хорновских дизъюнктов (Linear resolution with Selection function for Definition clauses), то есть дизъюнктов, содержащих не более одного положительного литерала. Их называют предложениями или клозами.
Если дизъюнкт состоит только из одного положительного литерала, он называется фактом. Дизъюнкт, состоящий только из отрицательных литералов, называется вопросом (или целью или запросом). Если дизъюнкт содержит и позитивный, и негативные литералы, он называется правилом. Правило вывода выглядит примерно следующим образом ¬A1
B:–A1,A2,...,An.
Логической программой называется конечное непустое множество хорновских дизъюнктов (фактов и правил).
При выполнении программы к множеству фактов и правил добавляется отрицание вопроса, после чего используется линейная резолюция. Ее специфика в том, что правило резолюции применяется не к произвольным дизъюнктам из программы. Берется самый левый литерал цели (подцель) и первый унифицируемый с ним дизъюнкт. К ним применяется правило резолюции. Полученная резольвента добавляется в программу в качестве нового вопроса. И так до тех пор, пока не будет получен пустой дизъюнкт, что будет означать успех, или до тех пор, пока очередную подцель будет невозможно унифицировать ни с одним дизъюнктом программы, что будет означать неудачу.
В последнем случае включается так называемый бэктрекинг — механизм возврата, который осуществляет откат программы к той точке, в которой выбирался унифицирующийся с последней подцелью дизъюнкт. Для этого точка, где выбирался один из возможных унифицируемых с подцелью дизъюнктов, запоминается в специальном стеке, для последующего возврата к ней и выбора альтернативы в случае неудачи. При откате все переменные, которые были означены в результате унификации после этой точки, опять становятся свободными.
В итоге выполнение программы может завершиться неудачей, если одну из подцелей не удалось унифицировать ни с одним дизъюнктом программы, и может завершиться успешно, если был выведен пустой дизъюнкт, а может и просто зациклиться.
Основы программирования на языке Пролог
Эта лекция будет посвящена теоретическим основам языка Пролог. В принципе, вполне можно писать хорошие программы на языке Пролог, не вдаваясь в глубины математической логики. И в этом смысле можно считать эту главу необязательной, факультативной. Однако тем, кому интересно узнать, "как она вертится", мы попробуем объяснить, как устроен Пролог, на чем он основывается.
Давайте начнем с самого начала или почти с самого начала, раз уж мы договорились, что никаких предварительных навыков от слушателей не требуется. Нам придется попытаться разобраться с понятиями логики первого порядка, которая лежит в основе Пролога; они обычно изучаются в курсе математической логики. Конечно, для того чтобы изучить даже самые начала математической логики, одной лекции недостаточно. Поэтому мы попытаемся пробежаться только по тому кусочку, который имеет отношение к языку Пролог. Часть используемых нами понятий все-таки останется "за кадром".
Говорят, что задана некая формальная система F, если определены:
алфавит системы — счетное множество символов;формулы системы — некоторое подмножество всех слов, которые можно образовать из символов, входящих в алфавит (обычно задается процедура, позволяющая составлять формулы из символов алфавита системы);аксиомы системы — выделенное множество формул системы;правила вывода системы — конечное множество отношений между формулами системы.
Зададим логику первого порядка (или логику предикатов), на которой основывается Пролог. Язык логики предикатов — один из формальных языков, наиболее приближенных к человеческому языку.
Алфавит логики первого порядка составляют следующие символы:
переменные (будем обозначать их последними буквами английского алфавита u, v, x, y, z);константы (будем обозначать их первыми буквами английского алфавита a, b, c, d);функциональные символы (используем для их обозначения ближние буквы f и g);предикатные символы (обозначим их дальними буквами p, q и r);пропозициональные константы истина и ложь (true и false);логические связки ¬ (отрицание),
Всякий предикатный и функциональный символ имеет определенное число аргументов. Если предикатный (функциональный) символ имеет n аргументов, он называется n-местным предикатным (функциональным) символом.
Термом будем называть выражение, образованное из переменных и констант, возможно, с применением функций, а точнее:
всякая переменная или константа есть терм;если t1,...,tn — термы, а f — n-местный функциональный символ,то f(t1,...,tn) — терм;других термов нет.
По сути дела, все объекты в программе на Прологе представляются именно в виде термов.
Если терм не содержит переменных, то он называется основным или константным термом.
Атомная или элементарная формула получается путем применения предиката к термам, точнее, это выражение p(t1,...,tn), где p — n-местный предикатный символ, а t1,...,tn — термы.
Формулы логики первого порядка получаются следующим образом:
всякая атомная формула есть формула;если A и B — формулы, а x — переменная, то выражения ¬A (читается "не A" или "отрицание A"), A
В случае если формула имеет вид
Чтобы не увеличивать чрезмерно объем лекции, мы не будем рассматривать полный список аксиом и правил вывода логики первого порядка.Те из них, которые пригодятся нам в дальнейшем, будут приведены в соответствующих местах.
Литералом будем называть атомную формулу или отрицание атомной формулы. Атом называется положительным литералом, а его отрицание — отрицательным литералом.
Дизъюнкт — это дизъюнкция конечного числа литералов. Если дизъюнкт не содержит литералов, его называют пустым дизъюнктом и обозначают посредством символа ?.
Давайте посмотрим, как можно привести любую формулу к множеству дизъюнктов, с которым работает метод резолюций. Для этого нам понадобятся некоторые определения нормальных форм.
Говорят, что формула находится в конъюнктивной нормальной форме,если это конъюнкция конечного числа дизъюнктов. Имеет место теорема о том, что для любой бескванторной формулы существует формула, логически эквивалентная исходной и находящаяся в конъюнктивной нормальной форме.
Формула находится в предваренной (или префиксной) нормальной форме, если она представлена в виде Q1x1,...,QnxnA, где Qi — это квантор
Формула находится в сколемовской нормальной форме, если она находится в предваренной нормальной форме и не содержит кванторов существования.
Основные понятия Пролога
Данная лекция посвящена базовым понятиям языка Пролог. В этой и следующей лекциях, мы будем изучать основы написания программ на Прологе.
Начнем с того, что познакомимся с так называемой нормальной формой Бэкуса-Наура (БНФ), разработанной в 1960 Джоном Бэкусом и Питером Науром и используемой для формального описания синтаксиса языков программирования. Впервые БНФ была применена Питером Науром при записи синтаксиса языка Алгол-60.
При описании синтаксиса конструкций используются следующие обозначения:
Символ ::= читается как "по определению" ("это", "есть"). Слева от разделителя располагается объясняемое понятие, справа - конструкция, разъясняющая его. Например,
<Имя> ::= <Идентификатор>
В угловые скобки заключается часть выражения, которая используется для обозначения синтаксической конструкции языка, в частности объясняемое понятие. В приведенном выше примере это <Имя> и <Идентификатор>.
Символ | означает в нотации БНФ "или", он применяется для разделения различных альтернативных растолкований определяемого понятия.
Пример. Десятичную цифру можно определить следующим образом:
<цифра> ::= 0|1|2|3|4|5|6|7|8|9
Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать);
Пример. Запись
<Целое число> ::= [-]<Положительное целое число>
означает, что целое число можно определить через положительное целое число, перед которым может стоять знак минус.
Символ * обозначает, что часть синтаксической конструкции может повторяться произвольное число раз (ноль и более). Заметим, что иногда вместо символа * используют фигурные скобки ({,}).
Пример. Определить положительное целое число в нотации БНФ можно следующим образом:
<Положительное целое число> ::= <цифра>[<цифра>]*.
То есть положительное целое число состоит из одной или нескольких цифр.
Программа на языке Пролог, ее иногда называют базой знаний, состоит из предложений (или утверждений), каждое предложение заканчивается точкой.
Предложения бывают двух видов: факты, правила.
Предложение имеет вид
A:- B1,... , Bn.
A называется заголовком или головой предложения, а B1,..., Bn - телом.
В принципе об этом уже говорилось в предыдущей лекции. Но там мы рассматривали эти понятия в основном с теоретической точки зрения, заходя со стороны математической логики, а сейчас наш подход будет больше практическим, со стороны программирования.
Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Можно считать, что факт - это предложение, у которого тело пустое.
Например, известный нам факт, что Наташа является мамой Даши, может быть записан в виде:
мама(Наташа, Даша).
Факт представляет собой безусловно истинное утверждение.
Напомню, что в математической логике, с которой мы познакомились в предыдущей лекции, отношения принято называть предикатами.
Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:
<Предикат>::=<Имя> | <Имя>(<аргумент>[,<аргумент>]*),
т.е. предикат состоит либо только из имени, либо из имени и следующей за ним последовательности аргументов, заключенной в скобки.
Аргументом или параметром предиката может быть константа, переменная или составной объект. Число аргументов предиката называется его арностью или местностью. Про переменные мы поговорим чуть-чуть позже, а подробное рассмотрение констант отложим до пятой лекции. Пока отметим, что константа получает свое значение в разделе описания констант, а переменная означивается в процессе работы программы.
В Турбо Прологе имя предиката должно состоять из последовательности латинских букв, цифр, знаков подчеркивания и начинаться с буквы или знака подчеркивания. В других версиях Пролога имя предиката может содержать символы не только из английского алфавита, но и из национального, например, из русского.
Соответственно, приведенный выше пример факта можно записать в Турбо Прологе, например, так:
mother("Наташа", "Даша").
Некоторые предикаты уже известны системе, они называются стандартными или встроенными.
В Турбо Прологе предложения с одним и тем же предикатом в заголовке должны идти одно за другим. Такая совокупность предложений называется процедурой.
В приведенном выше примере про то, что Наташа является мамой Даши, мама - это имя двухаргументного предиката, у которого строковая константа "Наташа" является первым аргументом, а строковая константа "Даша" - вторым.
Правило - это предложение, истинность которого зависит от истинности одного или нескольких предложений. Обычно правило содержит несколько хвостовых целей, которые должны быть истинными для того, чтобы правило было истинным.
В нотации БНФ правило будет иметь вид:
<Правило>::=<предикат>:-<предикат>[,<предикат>]*.
Пример. Известно, что бабушка человека - это мама его мамы или мама его папы.
Соответствующие правила будут иметь вид:
бабушка(X,Y):- мама(X,Z),мама(Z,Y). бабушка(X,Y):- мама(X,Z),папа(Z,Y).
Символ ":-" означает "если", и вместо него можно писать 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 значением "Наташа" и выдаст ответ:
X=Наташа 1 Solution
Вопрос об имени дочери Наташи записывается в виде:
мама(Наташа,X).
Соответствующим ответом будет:
X=Даша 1 Solution
Можно попросить систему найти имена всех известных ей мам и дочек, задав вопрос:
мама(X,Y).
Система последовательно будет пытаться согласовывать вопрос с имеющимися в программе предложениями от первого до последнего. В случае успешной унификации соответствующих термов переменная X будет означена именем матери, а переменная Y - именем ее дочери.
В итоге получим ответ:
X=Наташа Y=Даша X=Даша Y=Маша 2 solutions
Если надо получить только имена всех мам, можно воспользоваться анонимной переменной и записать вопрос:
мама(X,_).
Получим ответ:
X=Наташа X=Даша 2 solutions
И, наконец, если надо получить ответ на вопрос: есть ли информация о людях, находящихся в отношении "мама - дочка", то его можно сформулировать в виде:
мама(_,_),
В данном случае нам не важны конкретные имена, а интересует, есть ли в нашей базе знаний хотя бы один соответствующий факт. Ответом в данном случае будет просто "Yes". Система сообщит о том, что у нее есть информация об объектах, связанных отношением "мама".
Введем в нашу программу правило, определяющее отношение "бабушка - внучка", в терминах "быть мамой":
бабушка(X,Y):- мама(X,Z), мама(Z,Y).
По сути дела здесь записано, что один человек является бабушкой другого, если это он является мамой его мамы. Конечно, для полноты картины не помешает записать еще и второе правило, которое говорит, что бабушка - это мама папы, если в программу добавить факты еще и про пап.
Заметим, что в нашей программе нет ни одного факта, связанного с отношением бабушка. Тем ни менее, система оказывается способна найти ответы на вопросы о бабушках, пользуясь введенными фактами и правилом. Например, если нас интересует, чьей бабушкой является Наташа, то мы можем записать этот вопрос следующим образом:
бабушка("Наташа",X).
Для того чтобы найти ответ на вопрос, система просмотрит нашу базу сверху вниз, пытаясь найти предложение, в заголовке которого стоит предикат бабушка. Найдя такое предложение (это предложение бабушка(X,Y):-мама(X,Z),мама(Z,Y)), система конкретизирует переменную из заголовка предложения X именем "Наташа", переменную Y с переменной X из вопроса, после чего попытается достигнуть цели: мама("Наташа",Z) и мама(Z,Y). Для этого она просматривает базу знаний в поиске предложения, заголовок которого можно сопоставить с предикатом мама("Наташа",Z).
Это можно сделать, конкретизировав переменную Z именем "Даша". Затем система ищет предложение, в заголовке которого стоит предикат мама с первым аргументом "Даша" и каким-то именем в качестве второго аргумента. Подходящим предложением оказывается факт мама("Даша","Маша"). Система установила, что обе подцели мама("Наташа",Z) и мама(Z,Y) достижимы при Z="Даша", Y="Маша".
Она выдает ответ:
X=Маша
Напомним, что наша переменная X из вопроса была связана с переменной Y из правила. После этого, если есть такая возможность, система пытается найти другие решения, удовлетворяющие вопросу. Однако в данном случае других решений нет.
Вообще говоря, цель может быть согласована, если она сопоставляется с заголовком какого-либо предложения. Если сопоставление происходит с фактом, то цель согласуется немедленно. Если же сопоставление происходит с заголовком правила, то цель согласуется только тогда, когда будет согласована каждая подцель в теле этого правила, после вызова ее в качестве цели. Подцели вызываются слева направо. Поиск подходящего для сопоставления предложения ведется с самого начала базы. Если подцель не допускает сопоставления, то система совершает возврат для попытки повторного согласования подцели. При попытке повторного согласования система возобновляет просмотр базы с предложения, непосредственно следующего за тем, которое обеспечивало согласование цели ранее.
В программе на Прологе важен порядок предложений внутри процедуры, а также порядок хвостовых целей в теле предложений. От порядка предложений зависит порядок поиска решений и порядок, в котором будут находиться ответы на вопросы. Порядок целей влияет на количество проверок, выполняемых программой при решении.
Пример. Давайте создадим предикат, который будет находить максимум из двух чисел. У предиката будет три аргумента. Первые два аргумента - входные для исходных чисел, в третий выходной аргумент будет помещен максимум из первых двух аргументов.
Предикат будет довольно простым. Мы запишем, что в случае, если первое число больше второго, максимальным будет первое число, в случае, если первое число меньше, максимумом будет второе число. Надо также не забыть про ситуацию, когда числа равны, в этом случае максимумом будет любое из них.
Решение можно записать в следующем виде:
max(X,Y,X):- X>Y. /* если первое число больше второго, то первое число - максимум */ max(X,Y,Y):- X<Y. /* если первое число меньше второго, то второе число - максимум */ max(X,Y,Y):- X=Y. /* если первое число равно второму, возьмем в качестве максимума второе число */
Последнее предложение можно объединить со вторым или третьим в одно предложение. Тогда процедура будет состоять не из трех предложений, а всего из двух:
max(X,Y,X):- X>Y. /* если первое число больше второго, то первое число - максимум */ max(X,Y,Y):- X<=Y./* если первое число меньше или равно второму, возьмем в качестве максимума второе число */
Однако полученная процедура еще далека от совершенства. С одной стороны, в случае, когда первое проверяемое условие (X>Y) не выполнено, будет проверяться второе условие (X<=Y), хотя понятно, что если не выполнено X>Y, значит X<=Y. С другой стороны, в случае, если первое условие имело место и первое число оказалось больше второго, Пролог-система свяжет третий аргумент предиката max с первым аргументом, после чего попытается сопоставить второе предложение. Хотя нам очевидно, что после того, как максимум определен, не нужно больше ничего делать. Других вариантов в данной ситуации просто не может быть. И, значит, проверка второго условия избыточна.
В данной ситуации нам пригодится встроенный предикат, который по-английски называется cut, по-русски - отсечение, а в программе на Прологе он обозначается восклицательным знаком "!". Этот предикат предназначен для ограничения пространства поиска, с целью повышения эффективности работы программ. Он всегда завершается успешно. После того, как до него дошла очередь, он устанавливает "забор", который не дает "откатиться назад", чтобы выбрать альтернативные решения для уже "сработавших" подцелей. То есть для тех, которые расположены левее отсечения. На цели, расположенные правее, отсечение не влияет. Кроме того, отсечение отбрасывает все предложения процедуры, расположенные после предложения, в котором находится отсечение.
С использованием отсечения наше решение будет еще короче:
max2(X,Y,X):- X>Y,!./* если первое число больше второго, то первое число - максимум */ max2(_,Y,Y). /* в противном случае максимумом будет второе число */
В случае, если сработает отсечение, а это возможно, только если окажется истинным условие X>Y, Пролог-система не будет рассматривать альтернативное второе предложение. Второе предложение "сработает" только в случае, если условие оказалось ложным. В этой ситуации в третий аргумент попадет то же значение, которое находилось во втором аргументе. Обратите внимание, что в этом случае нам уже не важно, чему равнялся первый аргумент, и его можно заменить анонимной переменной.
Все случаи применения отсечения принято разделять на "зеленые" и "красные". Зелеными называются те из них, при отбрасывании которых программа продолжает выдавать те же решения, что и при наличии отсечения. Если же при устранении отсечений программа начинает выдавать неправильные решения, то такие отсечения называются красными.
Пример "красного" отсечения имеется в реализации предиката max2 (если убрать отсечение, предикат будет выдавать в качестве максимума второе число, даже если оно меньше первого). Пример "зеленого" отсечения можно получить, если в запись предиката max добавить отсечения (при их наличии предикат будет выдавать те же решения, что и без них).
В принципе, с помощью отсечения в Прологе можно смоделировать такую конструкцию императивных языков, как ветвление.
Процедура
S:- <условие>,!,P. S :- P2.
будет соответствовать оператору if <условие> then P else P2, то есть если условие имеет место, то выполнить P, иначе выполнить P2. Например, в случае с максимумом, можно расшифровать нашу процедуру как "если X>Y, то M=X, иначе M=Y".
Пример. Теперь напишем предикат, который будет находить максимум не из двух чисел, а из трех. У него будет уже четыре параметра. Первые три - входные для сравниваемых чисел, а четвертый - выходной параметр для их максимума.
Подходов к решению этой задачи может быть несколько.
Первое, что приходит в голову, это решить задачу по аналогии с нахождением максимума из двух чисел. Вариант без отсечения будет выглядеть так:
max3a(X,Y,Z,X):- X>=Y,X>=Z. /* если первое число больше или равно второму и третьему, то первое число - максимум */ max3a(X,Y,Z,Y):- Y>=X,Y>=Z. /* если второе число больше или равно первому и третьему, то второе число является максимумом */ max3a(X,Y,Z,Z):- Z>=X,Z>=Y. /* если третье число больше или равно первому и второму, то максимум - это третье число */
Недостаток этой программы, кроме ее длины, еще и в том, что если какие-то из исходных чисел окажутся равными, мы получим несколько одинаковых решений. Например, если все три числа совпадают, то каждое из трех правил будет истинным и, соответственно, мы получим три одинаковых, хотя и правильных ответа.
Применение отсечения позволит существенно сократить решение:
max3b(X,Y,Z,X):- X>Y,X>Z,!. /* если первое число больше второго и третьего, то первое число - максимум */ max3b(_,Y,Z,Y):- Y>=Z,!. /* иначе, если второе число больше третьего, то второе число является максимумом */ max3b(_,_,Z,Z). /* иначе максимум - это третье число */
Число сравнений значительно сократилось за счет того, что отсечение в первом правиле гарантирует нам, что на второе правило мы попадем только в том случае, если первое число не больше второго и третьего. В этой ситуации максимум следует искать среди второго и третьего чисел. Если ни первое, ни второе число не оказались больше третьего, значит, в качестве максимума можно взять как раз третье число, уже ничего не проверяя. Обратите внимание на то, что во втором правиле нам было не важно, чему равно первое число, а в третьем предложении участвовало только третье число. Не участвующие параметры заменены анонимными переменными.
И, наконец, самое короткое решение можно получить, если воспользоваться уже имеющимся предикатом max2. Решение будет состоять всего из одного предложения.
max3(X,Y,Z,M):- max2(X,Y,XY), /* XY - максимум из X и Y */ max2(XY,Z,M). /* M - максимум из XY и Z */
Мы записали, что для того, чтобы найти максимум из трех чисел, нужно найти максимум из первых двух чисел, после чего сравнить его с третьим числом.
Самостоятельные задания
Создайте предикат, находящий максимум из четырех чисел.Создайте предикат, проверяющий, являются ли два человека сестрами;братьями;дедушкой и внуком (внучкой);дядей и племянником (племянницей);супругами;родственниками.Создайте предикат, имеющий пять аргументов, и проверяющий, попадает ли точка, чьи координаты заданы первыми двумя параметрами, в круг, центр которого определяют третий и четвертый параметр, а радиус - пятый.Создайте предикат, находящий абсолютное значение числа (=X, если X>=0, и =-X, если X<0).Создайте предикат, находящий длину гипотенузы прямоугольного треугольника по длинам катетов.
Семантические модели Пролога
В Прологе обычно применяются две семантические модели: декларативная и процедурная. Семантические модели предназначены для объяснения смысла программы.
В декларативной модели рассматриваются отношения, определенные в программе. Для этой модели порядок следования предложений в программе и условий в правиле не важен.
Процедурная модель рассматривает правила как последовательность шагов, которые необходимо успешно выполнить для того, чтобы соблюдалось отношение, приведенное в заголовке правила.
Множество предложений, имеющих в заголовке предикат с одним и тем же именем и одинаковым количеством аргументов, трактуются как процедура. Для процедурной модели важен порядок, в котором записаны предложения и условия в предложениях.
При написании программы на Прологе кажется логичным в первую очередь рассматривать декларативную семантику, однако и о процедурной не стоит забывать, особенно в том случае, когда программа не работает или работает не совсем так, как предполагалось.
Следует заметить, что в некоторых случаях использование отсечения может привести к изменению декларативного смысла.
Рекурсия
В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в Прологе для этого используются процедура поиска с возвратом (откат) и рекурсия. Откат дает возможность получить много решений в одном вопросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого. При изучении рекурсии частенько вспоминается случай с бароном Мюнхгаузеном, который сам себя за волосы вытаскивал из болота. Про откат мы подробнее поговорим в шестой лекции, а в этой займемся изучением рекурсии. Заметим, что рекурсию используют не только в Прологе, но и в обычных императивных языках программирования. Но для Пролога, в отличие от императивных языков, рекурсия является основным приемом программирования. Более того, Пролог позволяет определять рекурсивные структуры данных. Работе с ними будет посвящено несколько лекций нашего курса.
Начнем изучение рекурсии в Прологе с классического примера. Предположим, что в базе знаний есть набор фактов, описывающий родственные связи людей через отношение "быть родителем". Предикат родитель имеет два аргумента. В качестве его первого аргумента указывается имя родителя, в качестве второго - имя ребенка. Мы хотим создать отношение "быть предком", используя предикат родитель.
Для того чтобы один человек был предком другого человека, нужно, чтобы он либо был его родителем, либо являлся родителем другого его предка.
Запишем эту идею:
предок(Предок,Потомок):- родитель(Предок,Потомок). /* предком является родитель */ предок(Предок,Потомок):- родитель(Предок,Человек), предок(Человек,Потомок). /* предком является родитель предка */
Отношение предок является транзитивным замыканием отношения родитель, то есть это наименьшее отношение, включающее отношение родитель и обладающее свойством транзитивности. Напомним, что отношение называется транзитивным, если для любых пар (А,В) и (В,С), находящихся в этом отношении, пара (А,С) также находится в этом отношении.
Очевидно, что отношение предок содержит отношение родитель. Это следует из первого предложения, в котором записано, что всякий родитель является предком. Второе предложение дает транзитивность.
По аналогии с математической индукцией, на которую рекурсия немного похожа, любая рекурсивная процедура должна включать в себя базис и шаг рекурсии.
Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. Так, в приведенной выше процедуре, описывающей предикат предок, базисом рекурсии является первое правило, в котором определено, что ближайшими предками человека являются его родители. Это предложение часто содержит условие, при выполнении которого происходит выход из рекурсии или отсечение.
Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле. В общем виде правило, реализующее шаг рекурсии, будет выглядеть так:
<имя определяемого предиката>:- [<подцели>], [<условие выхода из рекурсии>], [<подцели>], <имя определяемого предиката>, [<подцели>].
В некоторых ситуациях предложений, реализующих базис рекурсии, и предложений, описывающих шаг рекурсии, может быть несколько. Как правило, это бывает в сложных случаях, например, когда выполняемые в процессе реализации шага рекурсии действия зависят от выполнения или невыполнения какого-либо условия. Такие задачи встретятся нам в последующих лекциях, когда речь пойдет об обработке рекурсивных структур данных. В этой же лекции мы будем иметь дело в основном с простыми случаями рекурсии, когда рекурсивная процедура имеет один базис и один шаг рекурсии.
Пример. Создадим предикат, который будет вычислять по натуральному числу его факториал. Эта задача допускает рекурсивное решение на многих языках программирования, а также имеет рекурсивное математическое описание:
1!=1 /* факториал единицы равен единице */ N!=(N-1)!*N /* для того, чтобы вычислить факториал некоторого числа, нужно вычислить факториал числа на единицу меньшего и умножить его на исходное число */
Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:
fact(1,1). /* факториал единицы равен единице */ fact(N,F):- N1=N-1, fact(N1,F1), /* F1 равен факториалу числа на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */
К сожалению, при попытке вычислить факториал произвольного натурального числа с помощью описанного выше предиката fact произойдет переполнение стека ("Stack overflow"). Попробуем разобраться, в чем причина. Рассмотрим, например, что будет происходить, если мы попытаемся вычислить факториал трех.
Соответствующий вопрос можно записать следующим образом:
fact(3,X).
Пролог-система попытается унифицировать цель с заголовком первого предложения (fact(1,1)). Ей это не удастся, поскольку число три не равно единице. При унификации цели с заголовком второго предложения (fact(N,F)) переменная N конкретизируется числом три, а переменная X связывается с переменной F. После этого происходит попытка выполнить подцели, расположенные в теле правила слева направо. Сначала переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть двойкой. Срабатывание следующей подцели (fact(N1,F1)) приводит к рекурсивному вызову предиката, вычисляющего факториал, со значением переменной N1, равным двум.
Так же, как и в случае, когда первый аргумент был равен трем, унификации с головой первого предложения не происходит (единица не равна двум). Сопоставление с головой второго правила происходит успешно. Дальше все происходит почти так же, как для значения переменной N, равного трем.
Вычисляется новое значение N1, равное двум без единицы, то есть единице. Пролог снова пытается вычислить подцель fact(N1,F1) (правда, со значением переменной N1, равным единице).
На этот раз происходит сопоставление цели (fact(1,F1)) с заголовком первого предложения, при этом переменная F1 конкретизируется единицей. Пролог-системе наконец-то удалось вычислить вторую подцель второго правила, и она переходит к вычислению третьей подцели (F=F1*N). Переменная N была равна двум, переменная F1 - единице, произведение двух и единицы равно двум и, значит, переменная F конкретизируется двойкой.
Начинается обратный ход рекурсии. После того, как был вычислен факториал двойки, Пролог-система готова вычислить факториал тройки. Для этого нужно умножить факториал двух на три. Переменная F будет конкретизирована числом шесть. Мы получили ответ на вопрос о факториале трех.
Однако вычисления на этом не заканчиваются. Пролог-система обнаруживает, что цель fact(1,F1) может быть сопоставлена не только с заголовком первого предложения, но и с заголовком правила (fact(N,F)). Переменная N конкретизируется единицей, а переменная F1 связывается с переменной F. После этого переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть нулем. Пролог-система пытается вычислить цель fact(0,F1). С заголовком первого предложения (fact(1,1)) сопоставить эту цель не удается, поскольку ноль не равен единице. Зато с заголовком второго предложения (fact(N,F)) цель успешно унифицируется. Переменная N1 становится равна минус единице. После этого делается попытка вычислить цель fact(-1,F1).... Потом fact(-2,F1), fact(-3,F1), fact(-4,F1), fact(-5,F1)... .
Этот процесс будет продолжаться до тех пор, пока не будет исчерпана часть оперативной памяти, отведенная под стек. После этого выполнение программы остановится с сообщением о том, что стек переполнен.
Почему так получилось? Что мы сделали неправильно? Причина в том, что в исходном определении факториала, которое мы использовали, предполагалось, что правило работает только для натуральных чисел, то есть для положительных целых чисел.
У нас же в программе произошел выход в отрицательную часть целых чисел, что не было предусмотрено формулой, на которой была основана наша процедура.
Как можно исправить ошибку? У нас есть два варианта корректировки процедуры.
Можно проверить, что число, для которого применяется правило, больше единицы. Для единицы останется факт, утверждающий, что факториалом единицы будет единица. Выглядеть этот вариант будет следующим образом:
fact(1,1). /* факториал единицы равен единице */ fact(N,F):- N>1, /* убедимся, что число больше единицы */ N1=N-1, fact(N1,F1), /* F1 равен факториалу числа, на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */
В этом случае, хотя и произойдет повторное согласование цели fact(1,F1) с заголовком правила, и переменная N будет конкретизирована единицей, а переменная F связана с переменной F1, первая подцель правила (N>1) будет ложной. На этом процесс оборвется. Попытки вычислять факториал на неположительных числах не произойдет, процедура будет работать именно так, как нам хотелось.
Второй вариант решения проблемы - добавить в первое предложение процедуры отсечение. Напомним, что вызов отсечения приводит к тому, что предложения процедуры, расположенные ниже той, из которой оно было вызвано, не рассматриваются. И, соответственно, после того, как какая-то цель будет согласована с заголовком первого предложения, сработает отсечение, и попытка унифицировать цель с заголовком второго предложения не будет предпринята. Процедура в этом случае будет выглядеть так:
fact(1,1):-!. /* условие останова рекурсии */ fact(N,F):- N1=N-1, fact(N1,F1), /* F1 равен факториалу числа, на единицу меньшего исходного числа */ F=F1*N. /* факториал исходного числа равен произведению F1 на само число */
Конечно, с одной стороны, метод рекурсии имеет свои преимущества перед методом итерации, который используется в императивных языках программирования намного чаще. Рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные.
Некоторые алгоритмы удобно записывать именно рекурсивно.
С другой стороны, рекурсия имеет большой недостаток: ей, вообще говоря, может не хватать для работы стека. При каждом рекурсивном вызове предиката в специальном стековом фрейме запоминаются все промежуточные переменные, которые могут понадобиться. Максимальный размер стека при работе под управлением операционной системы MS DOS всего 64 Кб. Этого достаточно для размещения около трех-четырех тысяч стековых фреймов (в зависимости от количества и размера промежуточных переменных). При больших входных значениях стека может не хватить.
Есть, правда, один вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила. Турбо Пролог, на который мы ориентируемся в нашем курсе, распознает хвостовую рекурсию и устраняет связанные с ней дополнительные расходы. Этот процесс называется оптимизацией хвостовой рекурсии или оптимизацией последнего вызова.
Пример. Попробуем реализовать вычисление факториала с использованием хвостовой рекурсии. Для этого понадобится добавить два дополнительных параметра, которые будут использоваться нами для хранения промежуточных результатов. Третий параметр нужен для хранения текущего натурального числа, для которого вычисляется факториал, четвертый параметр - для факториала числа, хранящегося в третьем параметре.
Запускать вычисление факториала мы будем при первом параметре равном числу, для которого нужно вычислить факториал. Третий и четвертый аргументы будут равны единице.
Во второй аргумент по завершении рекурсивных вычислений должен быть помещен факториал числа, находящегося в первом параметре. На каждом шаге будем увеличивать третий аргумент на единицу, а второй аргумент умножать на новое значение третьего аргумента. Рекурсию нужно будет остановить, когда третий аргумент сравняется с первым, при этом в четвертом аргументе будет накоплен искомый факториал, который можно поместить в качестве ответа во второй аргумент.
Вся процедура будет выглядеть следующим образом:
fact2(N,F,N,F):-!. /* останавливаем рекурсию, когда третий аргумент равен первому*/ fact2(N,F,N1,F1):- N2=N1+1, /* N2 - следующее натуральное число после числа N1 */ F2=F1*N2, /* F2 - факториал N2 */ fact2(N,F,N2,F2). /* рекурсивный вызов с новым натуральным числом N2 и соответствующим ему посчитанным факториалом F2 */
Остановить рекурсию можно, воспользовавшись отсечением в базисе рекурсии, как это было сделано выше, или добавив в начало второго предложения сравнение N1 с N.
Если мы решим, что вызывать предикат с четырьмя аргументами неудобно, можно ввести дополнительный двухаргументный предикат, который будет запускать исходный предикат:
factM(N,F):- fact2(N,F,1,1). /* вызываем предикат с уже заданными начальными значениями */
Пример. В предыдущей лекции мы записали аналог императивного ветвления, воспользовавшись отсечением. Теперь напишем, используя рекурсию и отсечение, реализацию цикла с предусловием. Обычно этот цикл выглядит примерно так: while <условие> do P. Это соответствует текстовому описанию "пока имеет место <условие>, выполнять P". На Прологе подобную конструкцию можно записать следующим образом:
w:- <условие>,p,w. w:-!.
Пример. Еще одна классическая задача, имеющая рекурсивное решение, связна с вычислением так называемых чисел Фибоначчи. Числа Фибоначчи можно определить так: первое и второе числа равны единице, а каждое последующее число является суммой двух предыдущих. Соответственно, третье число Фибоначчи будет равно двум, четвертое равно трем (сумма второго числа (один) и третьего числа (два)), пятое - пяти (сумма третьего и четвертого чисел, то есть двух и трех), шестое - восьми (сумма четвертого и пятого, трех и пяти) и т.д.
Базисов рекурсии в данном случае два. Первый будет утверждать, что первое число Фибоначчи равно единице. Второй базис - аналогичное утверждение про второе число Фибоначчи. Шаг рекурсии также будет необычным, поскольку будет опираться при вычислении следующего числа Фибоначчи не только на предшествующее ему число, но и на предшествующее предыдущему числу. В нем будет сформулировано, что для вычисления числа Фибоначчи с номером N сначала нужно вычислить и сложить числа Фибоначчи с номерами N-1 и N-2.
Записать эти рассуждения можно так:
fib(1,1):-!. /* первое число Фибоначчи равно единице */ fib(2,1):-!. /* второе число Фибоначчи равно единице */ fib(N,F) :- N1=N-1, fib(N1,F1), /* F1 это N-1-е число Фибоначчи */ N2=N-2, fib(N2,F2), /* F2 это N-2-е число Фибоначчи */ F=F1+F2. /* N-е число Фибоначчи равно сумме N-1-го и N-2-го чисел Фибоначчи */
Обратите внимание на отсечение в первых двух предложениях. Оно служит для остановки рекурсии, чтобы при прямом ходе рекурсии не произошло выхода из области натуральных чисел (номеров чисел Фибоначчи) в область отрицательных чисел, как это происходило у нас в первой версии предиката, вычисляющего факториал.
Вместо этих двух отсечений от зацикливания можно избавиться путем добавления в начало правила, реализующего шаг рекурсии, проверки значения, находящегося в первом параметре предиката (N>2). Это условие в явном виде указывает, что рекурсивное правило применяется для вычисления чисел Фибоначчи, начиная с третьего.
Но надо сказать, что хотя наше решение получилось ясным и прозрачным, довольно точно соответствующим определению чисел Фибоначчи, оно, тем не менее, весьма неэффективное. При вычислении N-1-го числа Фибоначчи F1 вычисляются все предыдущие числа Фибоначчи, в частности, N-2-е число Фибоначчи F2. После этого заново начинает вычисляться N-2-е число Фибоначчи, которое уже было вычислено. Мало того, опять вычисляются все предыдущие числа Фибоначчи. Получается, что для вычисления числа Фибоначчи используется количество рекурсивных вызовов предиката fib, равное искомому числу Фиббоначи.
Давайте попробуем повысить эффективность вычисления чисел Фибоначчи. Будем искать сразу два числа Фибоначчи: то, которое нам нужно найти, и следующее за ним. Соответственно, предикат будет иметь третий дополнительный аргумент, в который и будет помещено следующее число. Базис рекурсии из двух предложений сожмется в одно, утверждающее, что первые два числа Фибоначчи равны единице.
Вот как будет выглядеть этот предикат:
fib_fast(1,1,1):-!. /* первые два числа Фибоначчи равны единице */ fib_fast(N,FN,FN1):- N1=N-1,fib_fast(N1,FN_1,FN), /* FN_1 это N-1-е число Фибоначчи, FN это N-е число Фибоначчи */ FN1=FN+FN_1. /* FN1 это N+1-е число Фибоначчи */
Несмотря на то, что предикат fib_fast находит, в отличие от предиката fib, не одно число Фибоначчи, а сразу два, он использует намного меньше стекового пространства и работает во много раз быстрее. Для вычисления числа Фибоначчи с номером N (а заодно и N+1-го числа Фибоначчи) необходимо всего лишь N рекурсивных вызовов предиката fib_fast.
Если нам не нужно следующее число Фибоначчи, можно сделать последним аргументом анонимную переменную или добавить описанный ниже двухаргументный предикат:
fib_fast(N,FN):- fib_fast(N,FN,_).
Обратите внимание, что если во втором правиле процедуры, описывающей предикат предок, с которого мы начали знакомство с рекурсией, изменить порядок подцелей, с декларативной точки зрения смысл останется прежним:
предок2(Предок,Потомок):- родитель(Предок,Потомок). /* предком является родитель */ предок2(Предок,Потомок):- предок2(Человек,Потомок), /* предком является родитель предка */ родитель(Предок,Человек).
Однако работать модифицированная процедура будет совсем не так. В случае, если вызвать предикат предок2, указав в качестве аргументов имена людей, один из которых является предком другого, он успешно подтвердит, что первый человек - предок второго. Во всех остальных ситуациях (один из аргументов свободен; человек, имя которого указано в качестве первого аргумента, не является предком человека, чье имя указано в качестве второго аргумента) все произойдет не так, как следовало бы.
После того, как этот предикат выдаст те же ответы, что и исходный предикат предок, он зациклится и в итоге выдаст сообщение о том, что стек переполнен.
С оригинальным предикатом предок этого не происходило, потому что в его втором правиле первой подцелью стоял вызов подцели родитель. В результате выполнения этой подцели переменная Человек получала в качестве значения имя какого-то человека. Поэтому в момент вызова второй подцели предок(Человек,Потомок) переменная Человек была уже связанной. В новой же версии предиката второе правило начинается с вызова подцели предок2(Человек,Потомок), причем переменная Человек в ней свободна. После того, как будут исчерпаны все альтернативы для означивания свободных переменных через первое предложение процедуры, подцель будет унифицироваться с заголовком второго предложения. Свободная переменная Человек будет связана с переменной Предок, а переменная Потомок подцели - с переменной Потомок заголовка правила. При попытке выполнить первую подцель правила все повторится. Этот процесс будет продолжаться до тех пор, пока не будет исчерпано все свободное пространство стека.
Такой вид рекурсии, когда тело правила начинается с рекурсивного вызова определяемого предиката, называется левосторонней рекурсией. С левосторонней рекурсией очень часто возникают описанные проблемы. Поэтому нужно стараться, если возможно, избегать использования левосторонней рекурсии, в отличие от правосторонней или хвостовой рекурсии.
Самостоятельные задания
Создайте предикат, вычисляющий неотрицательную степень целого числа.Создайте предикат, вычисляющий по натуральному числу N сумму чисел от 1 до N.Создайте предикат, вычисляющий по натуральному числу N сумму нечетных чисел, не превосходящих N.Создайте предикат, вычисляющий наибольший общий делитель двух натуральных чисел.Создайте предикат, вычисляющий наименьшее общее кратное двух натуральных чисел.Реализуйте, используя рекурсию и отсечение, цикл с постусловием (типа repeat <оператор> until <условие>).Реализуйте, используя рекурсию и отсечение, цикл со счетчиком (типа for i:=1 to N do <оператор>)Реализуйте, используя рекурсию и отсечение, цикл со счетчиком (типа for i:=1 downto N do <оператор>)
Директивы компилятора
В самом начале программы можно расположить одну или несколько директив компилятора, которые дают компилятору дополнительные инструкции по обработке программы.
Давайте для примера рассмотрим несколько наиболее широко используемых директив компилятора.
Директива trace применяется при отладке программы для трассирования. Этот процесс немного похож на пошаговое выполнение императивной программы с отслеживанием значений переменных. Трассировка позволяет пользователю наблюдать за ходом выполнения программы. Если после ключевого слова trace указаны имена предикатов через запятую, то трассировка идет только по этим предикатам. В противном случае - по всем предикатам программы. После завершения отладки трассировку нужно выключить, чтобы компилятор мог осуществить оптимизацию хвостовой рекурсии, о которой рассказывалось в предыдущей лекции.
Во время исполнения программы при включенной трассировке в специальном окне трассировки будет отображаться следующая информация:
после слова "CALL" будет указано имя выполняемого предиката (текущая подцель) и его параметры; * после слова "FAIL" будет выводиться имя текущей подцели, которая не была достигнута; после слова "RETURN" будет выводиться результат вычисления текущей подцели, в случае успеха. При этом если у подцели есть еще альтернативы, к которым возможен возврат, то перед именем предиката высвечивается звездочка ("*");слово "REDO" перед именем предиката указывает на то, что произошел возврат и происходит вычисление альтернативного решения.
Переход от подцели к подцели вызывается нажатием функциональной клавиши F10. При этом в окне редактирования выполняющуюся подцель указывает курсор, она также отображается в окне трассировки с параметрами и дополнительной информацией.
Директива nowarnings используется для подавления предупреждения системы о том, что какая-то переменная встречается в предложении только один раз. Эту директиву стоит использовать только в хорошо отлаженных программах. Как правило, для подавления такого предупреждения ("WARNING: The variable is only used once") достаточно заменить переменную, которая встретилась только один раз, на анонимную переменную.
С помощью директивы include при компиляции в исходный текст можно вставить содержимое некоторого файла.
Заметим, что многие директивы компилятора могут быть не только расположены в тексте программы, но и установлены в меню среды разработки Турбо Пролога (Options
Основы Турбо Пролога. Структура программы на Турбо Прологе
В этой лекции мы изучим специфику среды Турбо Пролог, отличия этой разновидности языка Пролог от других версий. Во-первых, Турбо Пролог - это компилируемый язык, а не интерпретируемый, как некоторые другие версии Пролога. Во-вторых, в Турбо Прологе принята строгая типизация данных (для повышения скорости трансляции и выполнения программ). В начале программы на Турбо Прологе обычно располагаются разделы описаний объектов программы. В-третьих, в Турбо Прологе отсутствует возможность рассматривать правила как данные, т.е. добавлять и удалять их во время работы. В процессе выполнения программы в нее можно добавлять и из нее можно удалять только факты. В-четвертых, в нем нельзя определять операции. Многое из перечисленного можно считать недостатками, однако в целом все это приводит к тому, что Турбо Пролог отличается высокой скоростью компиляции и выполнения.
Предикаты ввода-вывода
Турбо Пролог имеет отдельные предикаты для чтения с клавиатуры или из файла данных целого, вещественного, символьного и строкового типа. Работе с файлами будет посвящена лекция 12, а сейчас мы рассмотрим чтение из стандартного устройства ввода информации (клавиатуры) и, соответственно, запись на стандартное устройство вывода информации (монитор).
Предикат readln считывает строку с текущего устройства ввода и связывает ее со своим единственным выходным параметром.
Предикат readint читает с текущего устройства целое число и связывает его со своим единственным выходным параметром.
Предикат readreal отличается от предиката readint тем, что он считывает не целое, а вещественное число.
Для чтения символа с текущего устройства ввода используется предикат readchar. Есть еще предикат inkey, который так же, как и readchar, читает символ со стандартного устройства ввода. Разница между ними в том, что предикат readchar приостанавливает работу программы до тех пор, пока не будет введен символ, а предикат inkey не прерывает выполнение программы. Если нужно просто проверить, нажата ли клавиша, можно воспользоваться предикатом keypressed, не имеющим аргументов.
Предикат readterm предназначен для чтения сложных термов. У него два параметра: первый входной указывает имя домена, второй параметр конкретизируется термом домена, записанного в первом параметре. Если считанная этим предикатом строка не соответствует домену, указанному в его первом параметре, предикат выдаст сообщение об ошибке.
Для записи данных в текущее устройство записи служит предикат write. Он может иметь произвольное количество параметров. Кроме того, в Турбо Прологе есть еще и предикат writef, который служит для форматного вывода данных.
Для осуществления перехода на следующую строку (возврат каретки и перевод строки) применяется предикат nl, не имеющий параметров.
Описанная ниже группа предикатов служит для преобразования типов.
Предикат upper_lower имеет два аргумента и три варианта использования. Если в качестве первого аргумента указана строка (или символ), а второй аргумент свободен, то второй аргумент будет означен строкой (символом), полученной из первого аргумента преобразованием к нижнему регистру.
Если в исходной строке были прописные английские буквы, то они будут заменены строчными. Если же, наоборот, первый аргумент свободен, а второй аргумент - это строка (или символ), то первый аргумент получит значение, равное строке (символу), полученной из второго аргумента преобразованием к верхнему регистру. Если в строке, находящейся во втором аргументе, были строчные английские буквы, то они будут заменены прописными. И, наконец, имеется третий вариант использования. Если и первый, и второй аргументы связаны, то предикат будет истинным только в том случае, если во втором аргументе находится строка (символ), которая получается из строки, находящейся в первом аргументе, путем замены всех прописных английских букв на строчные. В противном случае предикат будет ложным.
Также имеют два параметра и три варианта использования предикаты str_int, str_real. Первый преобразует строку в целое число и наоборот. Второй служит для превращения строки в вещественное число или вещественного числа в строку.
Предикат str_char имеет те же параметры использования и применяется для преобразования односимвольной строки в один символ и наоборот.
Немного по-другому работает предикат char_int. Он позволяет переходить от символа к его ASCII-коду и обратно.
Хотя Пролог - не самый лучший инструмент для выполнения большого объема вычислений, в нем имеются стандартные средства для реализации обычных вычислений. При этом можно использовать четыре арифметических операции (сложение (+), вычитание (-), умножение (*) и деление (/)), а также целочисленное деление (div) и взятие остатка от деления одного целого числа на другое (mod). Для сравнения чисел можно воспользоваться операциями равно (=), не равно (<>), больше (>), больше или равно (>=), меньше (<), меньше или равно (<=).
Кроме того, можно использовать обычные математические функции, такие как: логарифмы натуральный (ln) и десятичный (log), квадратный корень (sqrt), модуль (abs), экспонента (exp). Тригонометрические функции: синус (sin), косинус (cos), тангенс (tan), арктангенс (arctan).
Величины углов указываются в радианах.
Функция trunc отбрасывает дробную часть своего параметра, а функция round округляет вещественное число до ближайшего целого.
Для вычисления псевдослучайных чисел имеется два варианта предиката random. Первый вариант имеет один выходной параметр, в который помещается сгенерированное вещественное число, лежащее в промежутке межу нулем и единицей. Второй вариант этого предиката - двухаргументный. В качестве первого входного аргумента указывается целое число. Второй аргумент означивается целым числом, лежащим между нулем и первым аргументом.
Нуль-местный предикат true всегда истинен, а нуль-местный предикат fail всегда ложен. Предикат fail часто используется для организации поиска с возвратом. Причем размещение какой-либо подцели в теле правила после предиката fail бессмысленно, поскольку в связи с тем, что этот предикат всегда терпит неудачу, цель никогда не будет достигнута.
Одноместный предикат free истинен, если его аргументом является свободная переменная, и ложен в противном случае. Предикат bound, наоборот, истинен, если его аргумент - это связанная переменная, и ложен, если его аргумент свободен.
В Турбо Прологе любой текст, находящийся между символами /* и */, рассматривается как комментарий. Кроме того, любой текст между символом % и концом строки также воспринимается как комментарий. Комментарий отличается от остального текста тем, что он игнорируется компилятором Турбо Пролога. Соответственно, комментарии пишутся не для компилятора, а для человека; для того, чтобы сделать программу более легкой для понимания.
Раздел описания доменов
Раздел описания доменов является аналогом раздела описания типов в обычных императивных языках программирования и начинается с ключевого слова DOMAINS.
В Турбо Прологе имеются стандартные домены, которые не нужно указывать в разделе описания доменов. Основные стандартные домены - это:
integer - целое число (из промежутка -32768...32767);
real - действительное число (лежащее между ±1e-307...±1e308);
char - символ, заключенный в одиночные апострофы;
string - последовательность символов, заключенная в двойные кавычки;
symbol - символическая константа (начинающаяся со строчной буквы последовательность букв латинского алфавита, цифр и знаков подчеркивания или последовательность любых символов, заключенная в кавычки). Этот домен соответствует понятию атома, с которым мы познакомились во второй лекции;
file - файл (подробному изучению файлов будет посвящена лекция 12).
В разделе описания доменов объявляются любые нестандартные домены, используемые в качестве аргументов предикатов.
Объявление домена имеет следующий вид:
<имя домена>=<определение домена>
или
file=<имя файлового домена1>;...;<имя файлового доменаN>
Удобно использовать описание доменов для сокращения имен стандартных доменов. Например, чтобы не писать каждый раз integer, можно написать следующее:
DOMAINS i=integer
и далее использовать вместо ключевого слова integer односимвольное обозначение i.
Из доменов можно конструировать составные или структурные домены (структуры). Структура описывается следующим образом:
<имя структуры>=<имя функтора>(<имя домена первой компоненты>,...,<имя домена последней компоненты>) [;<имя функтора>(...)]*
Каждая компонента структуры в свою очередь может быть структурой. Например, структура, описывающая точку на плоскости и имеющая две компоненты (координаты точки)
point = p(integer, integer)
может входить в качестве компоненты в более сложную структуру, описывающую треугольник:
triangle = tr(point, point, point)
В описание структуры могут входить альтернативы, разделенные символом ";" или ключевым словом "or".
Так, структуру, описывающую точку и на плоскости, и в пространстве, можно задать следующим образом:
point = p(integer, integer);p(integer, integer, integer).
Описание файлового домена имеет вид:
file = <символическое имя файла 1>;...; <символическое имя файла N>
Для представления данных в Турбо Прологе, в отличие от стандартных алгоритмических языков программирования, используются не массивы, а списки. Подробнее списки будут рассмотрены в следующей лекции, а пока заметим, что списковый домен задается следующим образом:
<имя спискового домена>=<имя домена элементов списка>*
Например, список целых чисел описывается так:
list_of_integer=integer*
Раздел описания констант
Раздел, озаглавленный зарезервированным словом CONSTANTS, предназначен для описания констант. Объявление константы имеет вид:
<имя константы>=<значение>
Имя константы должно быть идентификатором, то есть оно может состоять из английских букв, цифр и знака подчеркивания, причем не может начинаться с цифры.
Каждое определение константы должно размещаться в отдельной строке.
Например:
CONSTANTS pi=3.14 bgi_path="c:\\prolog\\bgi"
В разделе описания констант можно использовать в качестве первого символа имени константы прописные символы, потому что в этом разделе прописные и строчные символы не различаются. Однако при использовании констант в разделе описания предложений нужно задействовать в качестве первого символа имени константы только строчные символы, чтобы Пролог-система не восприняла константу как переменную.
Разделов описания констант может быть несколько, но каждая константа должна быть определена до ее первого использования.
Раздел описания предикатов
В разделе, озаглавленном зарезервированным словом PREDICATES, содержатся описания определяемых пользователем предикатов. В традиционных языках программирования подобными разделами являются разделы описания заголовков процедур и функций. Описание n-местного предиката имеет следующий вид:
<имя предиката>(<имя домена первого аргумента>,..., <имя домена n-го аргумента>).
Домены аргументов должны быть либо стандартными, либо объявленными в разделе описания доменов. Обратите внимание на то, что имя предиката в Турбо Прологе должно быть идентификатором, т.е. оно должно состоять только из английских букв, цифр и символа подчеркивания, причем не может начинаться с цифры.
Например, предикат, описывающий отношение "мама", которым мы пользовались в третьей лекции, может быть описан следующим образом:
PREDICATES mother(string,string)
Это описание означает, что у предиката два аргумента, причем оба строкового типа.
Один предикат может иметь несколько описаний. Это используется, когда нам нужно, чтобы предикат работал с аргументами различной природы. Например, в следующей лекции мы запишем предикат, который будет проверять принадлежность элемента списку. Описать его можно, например, так:
PREDICATES member(integer,integer*) member(real,real*) member(char,char*) member(string,string*)
Такие описания означают, что у предиката два аргумента. При этом возможны четыре варианта использования этого предиката. Первый аргумент может быть целым или вещественным числом, символом или строкой, второй аргумент, соответственно, списком целых или вещественных чисел, или списком, элементами которого являются символы, или списком, состоящим из строк. При этом процедура, реализующая этот предикат в разделе описания предложений, будет единственной.
Кроме того, при описании предиката можно указать, будет он детерминированным или недетерминированным. Детерминированный предикат возвращает только одно решение, а недетерминированный предикат при помощи поиска с возвратом может давать много решений. Детерминированные предикаты менее требовательны к оперативной памяти и выполняются быстрее. Отсечение, с которым мы познакомились в третьей лекции, позволяет превращать недетерминированные предикаты в детерминированные.
Для того чтобы указать, что предикат является детерминированным (недетерминированным), нужно перед его именем поместить зарезервированное слово determ (nondeterm). Если ни determ, ни nondeterm при описании предиката не использовались, то, по умолчанию, предикат считается детерминированным.
В Турбо Прологе имеется директива компилятора check_determ, которая принудительно включает проверку предикатов на детерминированность.
В Турбо Прологе есть так называемые стандартные (встроенные) предикаты, которые не нужно описывать в разделе описания предикатов PREDICATES. Наиболее употребляемые из них мы рассмотрим чуть позже. Все встроенные предикаты являются детерминированными.
Раздел описания предикатов внутренней базы данных
Работа с внутренними (динамическими) базами данных в Прологе будет рассмотрена в лекции 13. Начинается раздел описания предикатов внутренней базы данных с зарезервированного слова DATABASE и описываются в нем те предикаты, которые можно в процессе выполнения программы добавлять во внутреннюю базу данных или удалять оттуда. Описываются предикаты базы данных аналогично предикатам в разделе описания предикатов PREDICATES, который мы сейчас рассмотрим.
Раздел описания предложений
Этот раздел можно считать основным разделом программы, потому что именно в нем содержатся факты и правила, реализующие пользовательские предикаты. Все предикаты, которые применяются в этом разделе и не являются стандартными предикатами, должны быть описаны в разделе описания предикатов или в разделе описания предикатов базы данных. Начинается этот раздел со служебного слова CLAUSES.
Напомним, что предложения, у которых в заголовке указан один и тот же предикат, должны идти друг за другом. Такой набор предложений называется процедурой. Предложения довольно подробно обсуждались в третьей лекции, поэтому сейчас мы не будем подробно останавливаться на этом. Заметим только, что программу на Прологе принято оформлять по следующим правилам:
между процедурами пропускается пустая строка;тело правила записывается со следующей строки, после строки, в которой был заголовок, с отступом;каждую подцель записывают на отдельной строке, одну под другой.
Эти правила не являются обязательными, но они делают программу более "читабельной".
Раздел описания внутренней цели
С зарезервированного слова GOAL начинается раздел описания внутренней цели программы. Если этот раздел отсутствует, то после запуска программы Пролог-система выдает приглашение вводить вопросы в диалоговом режиме (внешняя цель). При выполнении внешней цели Пролог-система ищет все решения, выводя все возможные значения для переменных, участвующих в вопросе. Если же выполняется внутренняя цель, то осуществляется поиск только первого решения, а для получения всех решений нужно предпринимать дополнительные действия.
Программа, компилируемая в исполняемый файл, который можно запускать независимо от среды разработки, обязательно должна иметь внутреннюю цель. Внешнюю цель обычно применяют на этапе отладки программы.
Внешние и внутренние цели уже обсуждались в третьей лекции, они еще будут рассматриваться в следующей лекции, поэтому сейчас мы не будем останавливаться на этом вопросе более подробно.
Пример. Запишем полностью реализацию на Турбо Прологе той базы знаний про мам и бабушек, которую мы рассматривали в качестве примера в третьей лекции. Нажимаем комбинацию клавиш Alt+E (от Editor), попадаем в редактор. Набираем код, приведенный ниже.
DOMAINS /* раздел описания доменов */ s=string /* вводим синоним для строкового типа данных */ PREDICATES /* раздел описания предикатов */ mother(s,s) /* предикат мама будет иметь два аргумента строкового типа */ grandmother(s,s) /* то же имеет место и для предиката бабушка */ CLAUSES /* раздел описания предложений */ mother("Наташа","Даша"). /* "Наташа" и "Даша" связаны отношением мама */ mother("Даша","Маша"). /* "Даша" и "Маша" также принадлежат отношению мама */ grandmother(X,Y):- /* X является бабушкой Y, если найдется такой Z, что */ mother(X,Z), /* X является мамой Z, а */ mother(Z,Y). /* Z является мамой Y */
Для запуска программы нажимаем Alt+R (Run). Так как раздела описания внутренней цели в нашей программе не было, Пролог система выведет приглашение на ввод внешней цели ("GOAL:"). Вводим вопросы, наблюдаем результаты. Повтор предыдущей цели F8.
Теперь давайте рассмотрим некоторые наиболее употребляемые стандартные предикаты. Начнем с предикатов, предназначенных для вывода и ввода.
Самостоятельные задания
Создайте программу, решающую квадратное уравнение.Создайте программу, реализующую игру "Угадай число" (компьютер загадывает число, человек пытается его отгадать, ориентируясь на реплики "Больше", "Меньше").Создайте предикат, вычисляющий сумму цифр натурального числа.Создайте предикат, вычисляющий произведение цифр натурального числа.Создайте предикат, переводящий число из десятичной системы счисления в двоичную.Создайте предикат, переводящий число из одной системы счисления в другую.
Структура программы на Турбо Прологе
Программа на Турбо Прологе состоит из следующих семи разделов:
директивы компилятора;CONSTANTS - раздел описания констант;DOMAINS - раздел описания доменов;DATABASE - раздел описания предикатов внутренней базы данных;PREDICATES - раздел описания предикатов;CLAUSES - раздел описания предложений;GOAL - раздел описания внутренней цели.
В программе не обязательно должны быть все эти разделы. Так, например, она может состоять из одного описания цели:
GOAL write("hello"),readchar(_).
Эта программа, вполне в императивном духе, выведет сообщение (с помощью стандартного предиката write) и будет ожидать нажатия пользователем любой клавиши (стандартный предикат readchar читает символ).
Однако, как правило, программа содержит, по меньшей мере, разделы PREDICATES и CLAUSES.
Если программа запускается в среде разработки Турбо Пролога, то раздел GOAL необязателен. При написании же программы, не зависящей от среды разработки, в ней необходимо указать внутреннюю цель.
В программе может быть несколько разделов описаний DOMAINS, PREDICATES, DATABASE и CLAUSES. Однако разделов GOAL не может быть в программе более одного.
Порядок разделов может быть произвольным, но при этом константы, домены и предикаты должны быть определены до их использования. Однако в разделе DOMAINS можно ссылаться на домены, которые будут объявлены позже.
Рассмотрим разделы немного подробнее.
Управление выполнением программы на Прологе
Эта лекция посвящена способам организации управления программой при программировании на Прологе. Конечно, какую-то часть способов организации в явном или неявном виде мы уже рассмотрели в предыдущих лекциях. Здесь будет сформулировано явно то, что до сих пор использовалось в неявном виде. Мы разберем, в каких случаях применяются эти методы, как они работают и как ими пользоваться. Также мы рассмотрим некоторые новые методы, которых до сих пор не касались.
Начнем c того, что еще раз обсудим бэктрекинг, (или откат, или поиск с возвратом, или механизм поиска в глубину). Откат уже упоминался в предыдущих лекциях. Суть этого механизма такова: в том месте программы, где возможен выбор нескольких вариантов, Пролог сохраняет в специальный стек точку возврата для последующего возвращения в эту позицию. Точка возврата содержит информацию, необходимую для возобновления процедуры при откате. Выбирается один из возможных вариантов, после чего продолжается выполнение программы.
Во всех точках программы, где существуют альтернативы, в стек заносятся указатели. Если впоследствии окажется, что выбранный вариант не приводит к успеху, то осуществляется откат к последней из имеющихся в стеке точек программы, где был выбран один из альтернативных вариантов. Выбирается очередной вариант, программа продолжает свою работу. Если все варианты в точке уже были использованы, то регистрируется неудачное завершение и осуществляется переход на предыдущую точку возврата, если такая есть. При откате все связанные переменные, которые были означены после этой точки, опять освобождаются.
При объяснении сущности бэктрекинга часто приводят пример с поиском пути в лабиринте. Один из возможных способов найти выход из лабиринта — это на каждой развилке поворачивать в одну и ту же сторону, до тех пор, пока не попадешь в тупик. После попадания в тупик нужно вернуться до ближайшей развилки. На ней нужно выбрать другое направление. После этого нужно опять на всех развилках выбирать поворот в том же направлении, что и в самом начале. Продолжаем этот алгоритм до тех пор, пока не выберемся из лабиринта.
Пример. Рассмотрим работу механизма отката на примере слегка модифицированной программы, описывающей родственные отношения. Разделы описания доменов и предикатов оставим без изменения, а порядок фактов в разделе предложений изменим, для того чтобы он лучше соответствовал нашим целям. Получим следующую программу.
DOMAINS /* раздел описания доменов */ s=string /* вводим синоним для строкового типа данных */ PREDICATES /* раздел описания предикатов */ mother(s,s) /* предикат мама будет иметь два аргумента строкового типа */ grandmother(s,s) /* то же имеет место и для предиката бабушка */ CLAUSES /* раздел описания предложений */ mother("Даша","Маша"). /* "Даша" и "Маша" связаны отношением мама */ mother("Наташа","Даша"). /* "Наташа" является мамой "Даши" */ mother("Наташа","Глаша"). /* "Наташа" и "Глаша" связаны отношением мама */ mother("Даша","Саша"). /* "Даша" является мамой "Саши" */ grandmother(X,Y):– /* X является бабушкой Y, если найдется такой Z, что */ mother(X,Z), /* X является мамой Z, а */ mother(Z,Y). /* Z является мамой Y */
В качестве внешней цели, после запуска программы зададим вопрос об именах всех бабушек и внучек (grandmother(B,V)).
Чтобы проследить процесс работы Пролог-системы при поиске ответа на наш вопрос, можно включить трассировку, записав в начале программы директиву компилятору trace. В окне редактирования курсор указывает подцель, которая выполняется на данном шаге. В окне трассировки отображается дополнительная информация. Напомним, что переход от подцели к подцели осуществляется с помощью функциональной клавиши F10.
Для выполнения цели grandmother(B,V) должны быть удовлетворены две подцели: mother(B,Z) и mother(Z,V). Первая подцель унифицируется с первым предложением, описывающим отношение "быть мамой". При этом переменная B конкретизируется именем "Даша", а переменная Z — "Маша". В окне трассировки в этот момент результат вычисления текущей подцели (mother("Даша","Маша")), выводящийся после слова RETURN, сопровождается звездочкой (*), которая показывает, что у подцели есть альтернативные решения. Это то самое место, указатель на которое Пролог заносит в стек точек возврата для возможного последующего возвращения.
Затем делается попытка удовлетворить вторую подцель mother(Z,V), причем переменная Z означена именем "Маша". Попытка унифицировать эту подцель с одним из фактов, имеющих отношение к предикату mother, оказывается неудачной. Это происходит потому, что в нашей базе знаний нет никакой информации о детях Маши. О неуспехе говорит слово FAIL в окне трассировки. Происходит откат до места, сохраненного в стеке точек возврата. При этом переменные B и Z, означенные к моменту отката, вновь становятся свободными.
Выбирается вторая альтернатива. Переменная B при этом становится равной имени "Наташа", а переменная Z получает значение "Даша". Звездочка в окне трассировки, как и при первом проходе этой точки, показывает нам, что исчерпаны еще не все из имеющихся альтернатив, удовлетворяющих нашей подцели.
Делается попытка найти решение для второй подцели mother(Z,V) (при Z = "Даша"). Первое же предложение в процедуре, реализующей предикат mother, унифицируется с текущей подцелью, переменная V получает значение "Маша". Очередная звездочка в окне трассировки отмечает, что указатель на это место помещен в стек точек возврата, для того чтобы вернуться сюда, и что возможны другие означивания для переменной V, приводящие текущую подцель к успеху.
Получаем, что ответ на наш вопрос возможен при следующих значениях переменных: B=Наташа, V=Маша. Этот ответ отображается в окне диалога, после чего осуществляется откат к последнему месту, записанному в стек точек возврата. При этом освобождается переменная V, которая уже была означена именем "Маша". Подцель mother(Даша,V) унифицируется с заголовком последнего предложения процедуры, определяющей предикат mother. Переменная V означивается именем "Саша". В диалоговом окне выводится второй возможный ответ на заданный нами в качестве внешней цели вопрос: B=Наташа, V=Саша.
Альтернативных решений для подцели mother(Даша,V) больше нет. Соответственно, в окне трассировки отсутствует звездочка, а в стеке точек возврата нет больше указателя на то место, куда можно было возвращаться для того, чтобы выбирать новые значения для второй подцели правила, определяющего отношение grandmother.
Однако в стеке точек возврата еще остается указатель на тот участок программы, где находились означивания переменных для первой подцели в теле правила, определяющего отношение "быть бабушкой". Пролог-система осуществляет откат, попутно освобождая переменные.
Первая подцель сопоставляется с третьим фактом mother("Наташа","Глаша"). В окне трассировки видим уже знакомый символ звездочки, который свидетельствует о том, что испробованы еще не все возможные варианты для текущей подцели mother(B,Z). Делаются последовательные попытки сопоставить подцель mother("Глаша",V) с одним из фактов, имеющихся в базе знаний. Однако эти попытки заканчиваются неудачей, поскольку наша программа не содержит информации о детях Глаши. В окне трассировки отображается слово FAIL, информирующее нас об этой неудаче.
Процесс выполнения программы в очередной, последний, раз откатывается к тому месту, где можно выбрать решение для первой подцели. Подцель унифицируется с последним предложением в процедуре, описывающей знания, касающиеся мам. Переменная B конкретизируется именем "Даша", а переменная Z — "Cаша". Других вариантов для сопоставления первой подцели не остается. Стек точек возврата пуст. В окне трассировки нет индикатора, сообщающего об альтернативных решениях, к которым возможно возвращение. Пролог-система пытается сопоставить с чем-нибудь вторую подцель mother("Саша",V), однако ей не удается этого сделать. Ни один из фактов не содержит в качестве первого аргумента имя "Саша". Очередная неудача в попытке найти внуков для Даши.
Программа завершается. В диалоговом окне — два найденных в процессе работы решения:
B=Наташа, V=Маша B= Наташа, V=Саша 2 Solutions
Теперь посмотрим, какие имеются у программиста возможности по управлению откатом.
Рассмотрим модификацию механизма поиска в глубину, которая позволяет получать дополнительные решения и называется метод отката после неудачи. Этот метод используется в ситуации, когда нужно получить не один ответ, а все возможные в данной ситуации ответы. Например, если вопрос является внутренней целью, то Турбо Пролог останавливает поиск после первого же успешного вычисления цели. При этом выявляется только первое решение.
Пример. Давайте зададим тот же вопрос, что и в предыдущем примере, но уже не как внешнюю цель, а укажем ее в разделе описания внутренней цели:
GOAL grandmother(B,V)
Если запустить эту программу, она завершит свою работу, так ничего и не выдав в окне диалога. Дело в том, что при наличии в программе внутренней цели Турбо Пролог не отображает в диалоговом окне значений переменных, тогда как при выполнении внешней цели Турбо Пролог выводит в окне значения всех содержащихся в вопросе переменных. Это первое существенное отличие внешней и внутренней цели.
Однако мы можем сами организовать отображение результатов вычисления внутренней цели, добавив к ней в качестве подцелей вывод значений переменных B и V на экран, используя встроенный предикат write. Раздел описания внутренней цели при этом может выглядеть, например, так:
GOAL grandmother(B,V),write("Имя бабушки — ",B), write(", имя внучки — ",V),nl
В этом случае мы увидим на экране имена бабушки и внучки, но в окне диалога отобразится не два решения, а всего одно:
Имя бабушки — Наташа, имя внучки — Маша
Дело в том, что при наличии в программе внутренней цели Турбо Пролог находит только одно возможное означивание переменных, а не все возможные, как в случае внешней цели. Это второе отличие внешней и внутренней цели. Если нам необходимо получить все решения, нужно организовать это специально, например, с помощью метода отката после неудачи. Обычно внешние цели используются на этапе отладки новых предикатов. Если же нам нужна программа, которая может запускаться вне среды разработки, в ней обязательно должна быть внутренняя цель.
В методе отката после неудачи обычно используется всегда ложный предикат fail, о котором говорилось в прошлой лекции. Хотя, по большому счету, вместо этого предиката можно воспользоваться каким-нибудь заведомо ложным выражением. Например, 1=2 или чем-то в этом роде.
Если добавить к нашей внутренней цели предикат fail, то получим в окне диалога оба решения, которые мы могли наблюдать, когда задавали этот вопрос, используя внешнюю цель:
Имя бабушки — Наташа, имя внучки — Маша Имя бабушки — Наташа, имя внучки — Саша
Пример. Теперь давайте напишем предикат, который будет выводить на экран с помощью стандартного предиката write имена всех дочек.
show_names:– mother(_,Name), /* означивает переменную Name именем дочки */ write(" ", Name), nl, /* выводит значение переменной Name на экран */ fail. /* вызывает откат на место, сохраненное в стеке точек возврата */
Допишем этот предикат к нашей программе про мам и бабушек, не забыв добавить его описание в раздел PREDICATES.
В качестве внутренней цели укажем вывод сообщения "Имена дочек:" (с помощью встроенного предиката write), переведем курсор на следующую строку стандартным предикатом nl. В качестве третьей подцели запишем предикат show_names, выводящий имена всех дочек.
GOAL write("Имена дочек:"),nl, show_names.
Как будет работать эта программа? Сначала будет выведена строка "Имена дочек:", произойдет переход на следующую строку. После этого выполняется подцель show_names.
Во время попытки вычисления этой подцели механизм унификации означивает переменную именем дочери, указанном в качестве второго аргумента в первом предложении процедуры, описывающей предикат mother. Переменная Name получает значение "Маша". При этом в окне трассировки можно видеть звездочку, которая говорит о том, что в стек точек возврата помещен указатель на место, в которое возможен откат для получения других решений подцели mother(_,Name). Имя "Маша" выводится на экран встроенным предикатом write.
После этого предикат fail вызывает неуспешное завершение правила, затем осуществляется откат в точку, помещенную в стек последней. Процесс повторяется до тех пор, пока не будут исчерпаны все варианты достижения подцели mother(_,Name). В окне диалога будут выведены имена всех дочек в том порядке, в котором они упоминались в нашей программе:
Имена дочек: Маша Даша Глаша Саша
Пример. Давайте изменим наш предикат, чтобы он выводил имена не всех дочек, а только дочек одной мамы. Для этого нужно добавить предикату аргумент, в качестве которого будет указываться имя мамы. Кроме того, в первой подцели требуется заменить анонимную переменную некоторой обычной переменной, которую затем нужно сравнить с именем мамы, указанной в качестве аргумента предиката.
show_names2(Mother):– mother(M,Name), /* означивает переменную Name именем дочки мамы Mother */ M=Mother, /* проверяет совпадение имен мам M и Mother */ write(" ", Name), nl, /* выводит значение переменной Name на экран */ fail. /* вызывает откат к месту, сохраненному в стеке точек возврата */
Вместо первых двух подцелей mother(M,Name), M=Mother можно записать альтернативный вариант: mother(Mother,Name). Результат будет тем же, но процесс вычисления будет отличаться.
Выведем с помощью модифицированного предиката имена дочек Даши. Для этого изменим внутреннюю цель следующим образом:
GOAL write("Имена дочек Даши:"),nl, show_names2("Даша").
Отличие в работе этого предиката от предиката, который выводил имена всех дочек, заключаются в следующем. После того, как переменная M будет означена именем очередной мамы, будет проверяться совпадение ее значения с именем "Даша". В случае совпадения будет выведено имя дочери Даши и осуществится откат. Если же имя окажется отличным от "Даша" , откат произойдет немедленно. Выполнение программы в этом случае не доберется до вывода имени дочери на экран. Предикат fail не потребуется, так как подцель M=Mother будет неуспешной сама по себе. Тем не менее, наличие стандартного предиката fail в качестве последней подцели правила необходимо для того, чтобы вызвать откат, если подцель M=Mother окажется успешной.
По завершении работы этой программы можно будет увидеть в диалоговом окне результаты:
Имена дочек Даши: Маша Саша
Рассмотрим теперь так называемый метод отсечения и отката. В основе этого метода лежит использование комбинации предикатов fail (для имитации неудачи и искусственной организации отката) и "!" (отсечение или cut), который позволяет прервать этот процесс в случае выполнения какого-то условия. Об отсечении мы уже говорили в третьей лекции. Разберем этот метод на примере.
Пример. Модифицируем еще раз предикат, выводящий имена всех дочек, так чтобы он выводил их не все, а только до определенного имени. У предиката будет один входной аргумент, где указывается имя дочери, на котором должен оборваться вывод на экран имен дочек. В тело правила нужно добавить подцель, в которой текущее имя дочки будет сравниваться с именем дочки, указанным в качестве аргумента предиката. После этой подцели
show_names3(Daughter):– mother(_,Name), /* означивает переменную Name именем дочки */ write(" ", Name), nl, /* выводит значение переменной Name */ Name=Daughter, /* проверяет совпадение имен дочек Name и Daughter. В случае несовпадения вызывает откат на место, указатель на которое хранится в стеке точек возврата. В случае совпадения, за счет наличия отсечения, завершает поиск и вывод имен дочек */ write("Искомый человек найден!"),!.
Этот предикат будет конкретизировать переменную Name именем чьей-то дочери, выводить на экран значение этой переменной. После этого будет сравниваться значение переменной Name со значением переменной Daughter. В случае несовпадения эта подцель терпит неудачу, вызывая откат на первую подцель правила. В случае совпадения имен подцель успешна, управление получает предикат отсечение. Он всегда истинен и запрещает откат для подцелей, расположенных левее. На этом работа предиката show_names3 завершается. То есть откаты в этом правиле будут продолжаться до тех пор, пока текущее значение переменной Name не совпадет со значением переменной Daughter.
Еще один способ организации повторяющихся действий — так называемый метод повтора, определяемый пользователем. Он также использует откат, однако, в отличие от метода отката после неудачи, в котором откат осуществляется только после специально созданной неудачи, в этом методе откат возможен всегда за счет использования специального предиката, обычно кодируемого в виде следующего предложения:
repeat. repeat:– repeat.
Этот предикат всегда успешен. После выполнения первого предложения процедуры в стек точек возврата запоминается указатель, поскольку имеется еще один альтернативный вариант для него. В теле второго предложения опять вызывается предикат repeat.
Предикат repeat не является встроенным предикатом, а имя "repeat" — зарезервированным словом. Соответственно, вместо этого имени можно использовать какое-нибудь другое.
С помощью этого предиката можно организовывать циклы, подобные циклам в императивных языках программирования. Нужно не забыть добавить в правило, организующее цикл, кроме предиката repeat, условие завершения цикла и отсечение, чтобы не получилось зацикливания.
Пример. Создадим предикат, который будет дублировать символ, введенный пользователем с клавиатуры. Завершиться этот процесс должен, когда пользователь введет некий ключевой символ, о котором мы заранее договоримся, что его появление означает окончание процесса дублирования символов. Давайте, для определенности, возьмем в качестве такого символа точку (.).
double_char:– repeat, readchar(C), /* читаем символ с клавиатуры в переменную C */ write(C,C), nl,/* выводим на экран значение переменной C */ C=’.’,!, /* сравниваем значение переменной C с символом ‘.’*/ nl,write("Была введена точка. Закончили.").
Первой подцелью нашего правила записан вызов предиката repeat. Он обеспечивает нам повторное выполнение следующих за ним подцелей. Можно эксперимента ради закомментировать предикат repeat, дабы убедиться, что в этом случае цикла не получится. Последующие подцели выполнятся всего один раз.
Далее, используя стандартный предикат readchar, осуществляем чтение символа с клавиатуры в переменную C. Посредством встроенного предиката write выводим два экземпляра введенного пользователем символа на экран; стандартным предикатом nl переводим курсор на следующую строку. Затем значение переменной C сравнивается с символом точка (‘.’). Это условие, которое, с одной стороны, обеспечивает откат на первую подцель (предикат repeat), а с другой обеспечивает выход из цикла. Если поступивший с клавиатуры символ отличен от точки, подцель C=’.’ терпит неуспех. Пролог-система осуществляет откат на последнее место, указатель на которое записан в стеке точек возврата. Из подцелей, расположенных левее, альтернативы имелись только у первой подцели (предиката repeat). Все повторяется еще раз. Пользователь вводит символ, он дважды отображается на экране, сравнивается с точкой. Процесс повторяется до тех пор, пока введенный символ не окажется точкой. В этом случае подцель C=’.’ окажется успешной, управление перейдет на подцели, расположенные правее. Предикат nl сдвинет курсор на начало следующей строки, стандартный предикат write выводит на экран сообщение: "Была введена точка. Закончили." — и процесс дублирования символов на этом завершается.
Напишем внутреннюю цель, которая проинформирует пользователя о правилах работы нашей программы, после чего запустит предикат double_char.
GOAL write("Вводите символы, которые нужно повторить (точка — завершение)"),nl, double_char.
Самостоятельные задания
Создайте предикат, заменяющий в исходном списке первое вхождение заданного значения другим.Создайте предикат, заменяющий в исходном списке все вхождения заданного значения другим.Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из натуральных чисел от 1 до N (по возрастанию).Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из натуральных чисел от N до 1 (по убыванию).Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из N случайных натуральных чисел из промежутка от 1 до 100.Создайте предикат, порождающий по заданным числам N, M, K список, состоящий из N случайных натуральных чисел из промежутка от M до K.Создайте предикат, порождающий по заданным числам M, K список, состоящий из случайного количества случайных чисел из промежутка от M до K.Создайте предикат, порождающий список, состоящий из случайного количества случайных чисел.Создайте предикат, который увеличивает элементы исходного списка на единицу.Создайте предикат, переводящий список цифр от 0 до 9 в список соответствующих им названий (строк).Создайте предикат, переводящий список чисел в список соответствующих им названий.Создайте предикат, переводящий список цифр от 0 до 9 в список соответствующих им римских чисел.Создайте предикат, переводящий список арабских чисел в список соответствующих им римских чисел.Создайте предикат, переводящий список римских чисел в список соответствующих им арабских чисел.Создайте предикат, удваивающий значения элементов списка.Создайте предикат, преобразующий список, элементами которого являются числа, в список, элементы которого неотрицательны.Создайте предикат, преобразующий исходный список в список позиций отрицательных элементов.Создайте предикат, удаляющий из исходного списка элементы с четными номерами.Создайте предикат, который разделит исходный список из целых чисел на два списка: список положительных чисел и список отрицательных чисел.Создайте предикат, разделяющий исходный список на два подсписка. В первый из них должны попасть элементы с нечетными номерами, во второй - элементы с четными номерами.Создайте предикат, вычисляющий по списку и числу, подсписок исходного списка, начинающийся с элемента с указанным номером.Создайте предикат, осуществляющий удаление указанного количества последних элементов исходного списка.Создайте предикат, осуществляющий разделение исходного списка на два подсписка. В первый из них должно попасть указанное количество элементов из начала списка, во второй - оставшиеся элементы.Создайте предикат, осуществляющий разделение исходного списка на два подсписка. В первый из них должно попасть указанное количество элементов с конца списка, во второй - оставшиеся элементы.Создайте предикат, находящий предпоследний элемент списка.Создайте предикат, удаляющий предпоследний элемент списка.Создайте предикат, заменяющий в исходном списке два подряд идущих одинаковых элемента одним.Создайте предикат, удаляющий в исходном списке все повторные вхождения элементов.Создайте предикат, осуществляющий перестановку двух элементов списка с заданными номерами.Создайте предикат, генерирующий все перестановки элементов списка, указанного в качестве первого аргумента предиката.Создайте предикат, осуществляющий циклический сдвиг элементов списка на один влево (вправо).Создайте предикат, осуществляющий циклический сдвиг элементов списка на заданное количество шагов влево (вправо).Создайте предикат, осуществляющий поэлементное перемножение соответствующих элементов двух исходных списков.Создайте предикат, вычисляющий скалярное произведение векторов, заданных списками целых чисел.Создайте предикат, осуществляющий подсчет числа вхождений каждого элемента исходного списка. Ответом должен быть список пар, в которых первая компонента - элемент исходного списка, вторая - число его вхождений в первоначальный список.Создайте предикат, определяющий первую позицию подсписка в списке.Создайте предикат, добавляющий элементы одного списка во второй список, начиная с заданной позиции.Создайте предикат, возвращающий по списку и двум числам M и N подсписок исходного списка, состоящий из элементов с номерами от M до N.Создайте предикат, формирующий список простых чисел, не превосходящих данного числа.Создайте предикат, транспонирующий матрицу, заданную списком списков.
Списки
В императивных языках, как правило, основной структурой данных являются массивы. В Прологе так же, как и в Лиспе, основным составным типом данных является список. В этой лекции мы займемся изучением именно списков.
Дадим сначала неформальное определение списка.
Будем называть списком упорядоченную последовательность элементов произвольной длины.
Список задается перечислением элементов списка через запятую в квадратных скобках, так, как показано в приведенных ниже примерах.
[monday, tuesday, wednesday, thursday, friday, saturday, sunday] — список, элементами которого являются английские названия дней недели;
["понедельник", "вторник", "среда", "четверг", "пятница", "суббота", "воскресенье"] — список, элементами которого являются русские названия дней недели;
[1, 2, 3, 4, 5, 6, 7] — список, элементами которого являются номера дней недели;
['п', 'в', 'с', 'ч', 'п', 'с', 'в'] — список, элементами которого являются первые символы русских названий дней недели;
[] — пустой список, т.е. список, не содержащий элементов (в языке функционального программирования Лисп он обозначается nil).
Элементы списка могут быть любыми, в том числе и составными объектами. В частности, элементы списка сами могут быть списками.
В разделе описания доменов списки описываются следующим образом:
DOMAINS <имя спискового домена>=<имя домена элементов списка>*
Звездочка после имени домена указывает на то, что мы описываем список, состоящий из объектов соответствующего типа.
Например:
listI = integer* /* список, элементы которого — целые числа */ listR = real* /* список, состоящий из вещественных чисел */ listC = char* /* список символов */ lists = string* /* список, состоящий из строк */ listL = listI* /* список, элементами которого являются списки целых чисел */
Последнему примеру будут соответствовать списки вида:
[[1,3,7],[],[5,2,94],[–5,13]]
В классическом Прологе элементы списка могут принадлежать разным доменам, например: [monday, 1, "понедельник"]
В Турбо Прологе, в связи со строгой типизацией, все элементы списка должны принадлежать одному домену. Однако можно разместить в одном списке объекты разной природы, используя домен с соответствующими альтернативами.
Например, следующее описание:
DOMAINS element = i(integer); c(char); s(string) listE = element*
позволит иметь дело со списками вида
[i(–15), s("Мама"),c('A'),s("мыла"),c('+'),s("раму"), i(48),c('!')]
Дадим рекурсивное определение списка.
список — это структура данных, определяемая следующим образом:
пустой список ([ ]) является списком;структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.
Принято называть H головой списка, а T — хвостом списка. Заметим, что выбор переменных для обозначения головы и хвоста не случаен. По-английски голова — Head, а хвост — Tail.
Фактически операция "|" позволяет разделить список на хвост и голову (в Лиспе есть подобные операции car и cdr) или, наоборот, приписать объект (объекты) к началу списка (cons в Лиспе).
Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост. Хвост, в свою очередь, также является списком, содержащим меньшее количество элементов, чем исходный список. Если хвост не пуст, его также можно разбить на голову и хвост. И так до тех пор, пока мы не доберемся до пустого списка, у которого нет головы.
Например, в списке [1, 2, 3] элемент 1 является головой, а список [2, 3] — хвостом, т.е. [1, 2, 3] = [1|[2, 3]].
Заметим, что хвост этого списка [2, 3], в свою очередь, может быть представлен в виде головы 2 и хвоста [3], а список [3] можно рассматривать в виде головы 3 и хвоста []. Пустой список далее не разделяется.
В итоге получаем, что список [1, 2, 3] эквивалентен списку [1|[2, 3]], который, в свою очередь, эквивалентен списку [1|[2|[3]]]. Последний сопоставим со списком [1|[2|[3|[ ]]]].
В этом же списке можно выделить два первых элемента и хвост из третьего элемента [1,2|[3]]. И, наконец, возможен вариант разбиения на голову из трех первых элементов и пустой хвост: [1, 2, 3|[]].
Чтобы организовать обработку списка, в соответствии с приведенным выше рекурсивным определением, нам достаточно задать предложение (правило или факт, определяющее, что нужно делать с пустым списком), которое будет базисом рекурсии, а также рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста. Иногда базис рекурсии записывается не для пустого, а для одно- или двухэлементного списка.
В качестве резюме к нашим рассуждениям запишем еще раз определение списка в нотации Бэкуса–Науэра:
Список ::= [ ]|[Элемент <,Элемент>*]|[Голова|Хвост] Голова ::= Элемент <,Элемент>* Хвост ::= Список
Словесно это можно записать так: список или пустой, или представим в виде перечисления элементов, записанных через запятую, или состоит из головы и хвоста, который, в свою очередь, также является списком.
Рассмотрим обработку списков.
Пример. Создадим предикат, позволяющий вычислить длину списка, т.е. количество элементов в списке.
Для решения этой задачи воспользуемся очевидным фактом, что в пустом списке элементов нет, а количество элементов непустого списка, представленного в виде объединения первого элемента и хвоста, равно количеству элементов хвоста, увеличенному на единицу. Запишем эту идею:
length([], 0). /* в пустом списке элементов нет */ length([_|T], L) :– length(T, L_T), /* L_T — количество элементов в хвосте */ L = L_T + 1. /* L — количество элементов исходного списка */
Обратите внимание, что при переходе от всего списка к его хвосту нам неважно, чему равен первый элемент списка, поэтому мы используем анонимную переменную.
Разберем на примере, как это будет работать. Пусть нас интересует количество элементов в списке [1,2,3]. Запишем соответствующий вопрос Пролог-системе:
length([1,2,3],X).
Система попытается вначале сопоставить нашу цель с первым предложением length([], 0), однако ей это не удается сделать, потому что первый аргумент цели является непустым списком.
Система переходит ко второму предложению процедуры. Сопоставление с заголовком правила проходит успешно, переменная X связывается с переменной L, список [1,2,3] будет сопоставлен со списком [_|T], переменная T будет конкретизирована значением [2,3]. Теперь система переходит к попытке достижения подцели length(T,L_T). Как и в предыдущем случае, первое предложение с подцелью не сопоставляется, так как список T не пустой. При сопоставлении заголовка правила с подцелью хвост T конкретизируется одноэлементным списком [3]. На следующем шаге рекурсии переменная T означена пустым списком (хвост одноэлементного списка). И, значит, наша подцель выглядит следующим образом: length([], L_T). Эта цель сопоставляется с фактом, переменная L_T становится равной нулю. Раскручивается обратный ход рекурсии: переменная L_T увеличивается на единицу, результат попадает в переменную L. Получаем, что длина списка [3] равна единице. На следующем обратном шаге происходит еще одно добавление единицы, после чего длина списка [2,3] конкретизируется двойкой. И, наконец, на последнем возвратном шаге получаем означивание переменной L числом 3 (количеством элементов в списке [1,2,3]).
Пример. Создадим предикат, позволяющий проверить принадлежность элемента списку. Предикат будет иметь два аргумента: первый — искомое значение, второй — список, в котором производится поиск.
Построим данный предикат, опираясь на тот факт, что объект принадлежит списку, если он либо является первым элементом списка, либо элементом хвоста. Это может быть записано в виде двух предложений:
member(X,[X|_]). /* X — первый элемент списка */ member(X,[_|T]) :– member(X,T). /* X принадлежит хвосту T*/
Заметим, что в первом случае (когда первый элемент списка совпадает с исходным элементом), нам неважно, какой у списка хвост, и можно в качестве хвоста указать анонимную переменную. Аналогично, во втором случае, если X принадлежит хвосту, нам не важно, какой элемент первый.
Отметим, что описанный предикат можно использовать двояко: во-первых, конечно, для того, для чего мы его и создавали, т.е.
для проверки, имеется ли в списке конкретное значение. Мы можем, например, поинтересоваться, принадлежит ли двойка списку [1, 2, 3]:
member(2, [1, 2, 3]).
Получим, естественно, ответ: "Yes".
Подобным образом можно спросить, является ли число 4 элементом списка [1, 2, 3]:
member(4, [1, 2, 3]).
Ответом, конечно, будет "No".
Второй способ использования данного предиката — это получение по списку его элементов. Для этого нужно в качестве первого аргумента предиката указать свободную переменную. Например:
member(X, [1, 2, 3]).
В качестве результата получим список всех элементов списка:
X=1 X=2 X=3
Третий способ позволит получить по элементу варианты списков, которые могут его содержать. Теперь свободную переменную запишем вторым аргументом предиката, а первым — конкретное значение. Например,
member(1, X).
Вначале Пролог-система выдаст предупреждение о том, что переменная X не связана в первом предложении ("708 WARNING: The variable is not bound in this clause. (F10=ok, Esc=abort)").
У нас есть два способа отреагировать на это предупреждение: нажать кнопку Esc, чтобы отказаться от генерации списков, содержащих единицу в качестве элемента; нажать F10 для того, чтобы продолжить выполнение цели. Во втором случае Пролог-система начнет выдавать варианты списков, содержащих единицу:
X=[1|_] /* единица — первый элемент списка */ X=[_,1|_] /* единица — второй элемент списка */ X=[_,_,1|_] /* единица — третий элемент списка */ и т.д.
Этот процесс будет продолжаться до тех пор, пока не будет нажата комбинация клавиш Ctrl+Break.
Если данный предикат планируется использовать только первым способом, то можно ускорить его работу, устранив поиск элемента в хвосте списка, если он уже найден в качестве первого элемента списка. Это можно сделать двумя способами.
Первый способ. Добавим в правило проверку на несовпадение первого элемента списка с искомым элементом, чтобы поиск элемента в хвосте списка производился только тогда, когда первый элемент списка не является искомым.
Модифицированный предикат будет выглядеть следующим образом:
member2(X,[X|_]). member2(X,[Y|T]):– X<>Y, member2(X,T).
Заметим, что эту модификацию предиката member нельзя использовать для получения всех элементов списка. Если подставить в качестве первого аргумента несвязанную переменную, то при попытке согласования подцели правила неозначенная переменная X будет сравниваться с неозначенной переменной Y. Получим сообщение об ошибке "Free variable in expression".
Второй способ. Добавим в факт отсечение, чтобы в ситуации, когда искомый элемент оказался первым элементом списка, не производился лишний поиск в хвосте исходного списка. Получим:
member3(X,[X|_]):–!. member3(X,[_|T]):– member3(X,T).
Заметим, что хотя эта модификация предиката member более эффективна, чем исходная, за счет того, что она не выполняет поиск в хвосте после того, как искомый элемент найден, ее можно использовать только для того, чтобы проверить, имеется ли в списке конкретное значение. Если мы попытаемся применить ее для получения всех элементов списка, подставив в качестве первого аргумента несвязанную переменную, то результатом будет только первый элемент списка. Отсечение не позволит нам получить оставшиеся элементы.
Пример. Создадим предикат, позволяющий соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий — результат соединения.
В качестве основы для решения этой задачи возьмем рекурсию по первому списку. Базисом рекурсии будет факт, устанавливающий, что если присоединить к списку пустой список, в результате получим исходный список. Шаг рекурсии позволит создать правило, определяющее, что для того, чтобы приписать элементы списка, состоящего из головы и хвоста, ко второму списку, нужно соединить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка. Запишем решение:
conc([ ], L, L). /* при присоединении пустого списка к списку L получим список L */ conc([H|T], L, [H|T1]) :– conc(T,L,T1). /* соединяем хвост и список L, получаем хвост результата */
Заметим, что этот предикат также можно применять для решения нескольких задач.
Во-первых, для соединения списков. Например, если задать вопрос
conc([1, 2, 3], [4, 5], X)
то получим в результате
X= [1, 2, 3, 4, 5]
Во-вторых, для того, чтобы проверить, получится ли при объединении двух списков третий. Например, на вопрос:
conc([1, 2, 3], [4, 5], [1, 2, 5]).
ответом будет, конечно, No.
В-третьих, можно использовать этот предикат для разбиения списка на подсписки. Например, если задать следующий вопрос:
conc([1, 2], Y, [1, 2, 3]).
то ответом будет Y=[3].
Аналогично, на вопрос
conc(X, [3], [1, 2, 3]).
получим ответ X=[1, 2].
И, наконец, можно спросить
conc(X, Y, [1, 2, 3]).
Получим четыре решения:
X=[], Y=[1, 2, 3] X=[1], Y=[2, 3] X=[1, 2], Y=[3] X=[1, 2, 3], Y=[]
В-четвертых, можно использовать этот предикат для поиска элементов, находящихся левее и правее заданного элемента. Например, если нас интересует, какие элементы находятся левее и, соответственно, правее числа 2, можно задать следующий вопрос:
conc(L, [2|R], [1, 2, 3, 2, 4]).
Получим два решения:
L=[1], R=[3, 2, 4]. L=[1, 2, 3], R=[4]
В-пятых, на основе нашего предиката conc можно создать предикат, находящий последний элемент списка:
last(L,X):– conc(_,[X],L).
Справедливости ради стоит заметить, что этот предикат можно реализовать и "напрямую", без использования предиката conc:
last2([X],X). /* последний элемент одноэлементного списка — этот элемент */ last2([_|L],X):– last2(L,X). /* последний элемент списка совпадает с последним элементом хвоста */
В-шестых, можно определить, используя conc, предикат, позволяющий проверить принадлежность элемента списку. При этом воспользуемся тем, что если элемент принадлежит списку, то список может быть разбит на два подсписка так, что искомый элемент является головой второго подсписка:
member4(X,L):– conc(_,[X|_],L).
В-седьмых, используя предикат, позволяющий объединить списки, можно создать предикат, проверяющий по двум значениям и списку, являются ли эти значения соседними элементами списка.
Предикат будет иметь три параметра: первые два — значения, третий — список.
Идея решения заключается в следующем. Если два элемента оказались соседними в списке, значит, этот список можно разложить на два подсписка, причем голова второго подсписка содержит два наших элемента в нужном порядке. Выглядеть это будет следующим образом:
neighbors(X,Y,L):– conc(_,[X,Y|_],L). /* список L получается путем объединения некоторого списка со списком, голову которого составляют элементы X и Y */
Обратите внимание, что этот предикат проверяет только наличие нужных значений в указанном порядке. Если нам неважен порядок, в котором два данных значения встречаются в некотором списке, то следует записать модификацию описанного выше предиката, которая будет проверять оба варианта размещения искомых элементов. Для этого достаточно, чтобы список раскладывался на два подсписка, причем голова второго подсписка содержала два наших элемента либо в прямом, либо в обратном порядке. Соответствующий программный код будет следующим:
neighbors2(X,Y,L):– conc(_,[X,Y|_],L); conc(_,[Y,X|_],L). /* список L получается путем объединения некоторого списка со списком, голову которого составляют элементы X и Y или элементы Y и X */
Есть подозрение, что многообразие использований предиката conc приведенными выше примерами не исчерпывается.
Пример. Разработаем предикат, позволяющий "обратить" список (записать его элементы в обратном порядке). Предикат будет иметь два аргумента: первый — исходный список, второй — список, получающийся в результате записи элементов первого аргумента в обратном порядке.
Для решения этой задачи воспользуемся рекурсией. Базис: если записать элементы пустого списка (которых нет) в обратном порядке — опять получим пустой список. Шаг рекурсии: для того чтобы получить "перевернутый" список, можно "перевернуть" его хвост и "приклеить" к нему первый элемент исходного списка. Запишем эти размышления.
reverse([ ],[ ]). /* обращение пустого списка дает пустой список*/ reverse([X|T],Z):– reverse(T,S), conc(S,[X],Z). /* обращаем хвост и приписываем к нему справа первый элемент исходного списка*/
Обратите внимание, что вторым аргументом в предикате conc должен стоять именно одноэлементный список [X], а не элемент X. Это связано с тем, что аргументами предиката conc должны быть списки.
Можно написать данный предикат без использования предиката conc. Правда, тогда нам придется добавить дополнительный аргумент, в котором мы будем "накапливать" результат. Мы будем "отщипывать" от исходного списка по элементу и дописывать его к вспомогательному списку. Когда исходный список будет исчерпан, мы передадим "накопленный" список в третий аргумент в качестве ответа. До этого момента третий аргумент передается от шага к шагу неконкретизированным. Реализация будет выглядеть следующим образом:
rev([H|T],L1,L2):– rev(T,[H|L1],L2). /* голову первого аргумента дописываем ко второму аргументу*/ rev([ ],L,L). /* если исходный список закончился, то второй аргумент — передаем в третий аргумент в качестве результата*/
Для того чтобы использовать этот предикат обычным "двухаргументным" образом, добавим еще один предикат, который будет запускать наш "основной" предикат rev, имеющий "лишний" аргумент, используемый для накопления элементов обращенного списка. В начале работы второй аргумент должен быть пустым списком.
reverse2(L1,L2):– rev (L1,[ ],L2).
Пример. Создадим предикат, который позволит проверить, является ли список палиндромом. Палиндромом называется список, который совпадает со своим обращением. Соответственно, у данного предиката будет всего один аргумент (список, который проверяем на "палиндромность").
Первое, что приходит в голову: воспользоваться только что написанным предикатом reverse (или reverse2). Перевернуть список и проверить, совпадает ли результат с исходным списком. Выглядеть этот предикат будет следующим образом:
palindrom(L):– reverse (L,L).
Можно решить эту задачу "напрямую", без использования предиката reverse.
Пример. Напишем предикат, позволяющий получать элемент списка по его номеру так же, как по номеру можно получать элемент массива в императивных языках программирования.
Предикат будет трехаргументный: первый аргумент — исходный список, второй аргумент — номер элемента и третий — элемент списка, указанного в качестве первого аргумента предиката, имеющий номер, указанный в качестве второго аргумента.
Решение проведем рекурсией по номеру элемента. В качестве базиса возьмем очевидный факт, что первым элементом списка является его голова. Шаг рекурсии позволит нам сделать предположение, что N-й элементом списка является (N–1)-м элементом хвоста. Данному определению будет соответствовать следующее предложение:
n_element([X|_],1,X). n_element([_|L],N,Y):– N1=N–1, n_element(L,N1,Y).
Пример. В большинстве практических задач не обойтись без предиката, удаляющего все вхождения заданного значения из списка. Предикат будет зависеть от трех параметров. Первый параметр будет соответствовать удаляемому списку, второй — исходному значению, а третий — результату удаления из первого параметра всех вхождений второго параметра. Создадим его.
Без рекурсии не обойдется и на этот раз. Если первый элемент окажется удаляемым, то нужно перейти к удалению заданного значения из хвоста списка. Результатом в данном случае должен стать список, полученный путем удаления всех вхождений искомого значения из хвоста первоначального списка. Это даст нам базис рекурсии. Шаг рекурсии будет основан на том, что если первый элемент списка не совпадает с тем, который нужно удалять, то он должен остаться первым элементом результата, и нужно переходить к удалению заданного значения из хвоста исходного списка. Полученный в результате этих удалений список должен войти в ответ в качестве хвоста.
delete_all(_,[],[]). delete_all(X,[X|L],L1):– delete_all (X,L,L1). delete_all (X,[Y|L],[Y|L1]):– X<>Y, delete_all (X,L,L1).
Если нам нужно удалить не все вхождения определенного значения в список, а только первое, то следует немного изменить вышеописанную процедуру. Это можно сделать несколькими способами. Рассмотрим один из них.
Заменим в первом правиле рекурсивный вызов предиката отсечением.В этом случае, пока первый элемент списка не окажется удаляемым, мы будем переходить к рассмотрению хвоста.
delete_one(_,[],[]). delete_one(X,[X|L],L):–!. delete_one(X,[Y|L],[Y|L1]):– delete_one(X,L,L1).
В заключение лекции рассмотрим предикат findall, предназначенный для нахождения всех решений некоторой цели. У него три параметра: имя переменной, предикат и список, в который будут помещены найденные решения.
Пример. Посмотрим, как с помощью предиката findall можно решать задачи, подобные тем, которые мы решали в предыдущей лекции.
Найдем имена всех дочек: findall(N,mother(_,N),L). В список L попадут имена всех дочек.
Найдем имена всех дочек Даши: findall(N,mother("Даша",N),L). В список L попадут имена всех дочек Даши.
