Логические языки программирования: особенности, примеры
Как часто вы сталкивались с непонятным термином «логическое программирование» и не могли понять, что это? Сегодня мы окончательно определимся с тем, что такое языки программирования логического типа, и рассмотрим примеры таких языков.
Прежде чем начинать обзор языков, необходимо сначала узнать, что это такое и зачем оно нужно.
Что такое логическое программирование?
Это подход к программированию, основанный на доказательстве теорем и выводе информации на основе фактов. Вывод результата является побочным продуктом работы программы. Логическое программирование основано на теории математической логики, включает в себя раздел дискретной математики и некоторые другие.
В чем различия?
Многие объединяют логические языки программирования с функциональными, однако они обладают некоторыми различиями, о которых мы далее поговорим.
В отличие от функциональных, логические очень хорошо подходят для создания искусственного интеллекта. Также иногда очень удобно, когда в языке переменные не делятся на входные и выходные. Именно в таких языках это и происходит, что иногда упрощает работу с кодом. Опять же программы являются более быстрыми и выполняют свои задачи иногда эффективнее. Основная особенность логических языков программирования заключается в том, что программа представляет определенные отношения между элементами.
Однако существуют и минусы. Не все можно описать с помощью логики, поэтому в таких программах функции будут работать не всегда так, как нужно, или вообще не будут работать.
Кому полезно учить языки программирования логического типа?
Стоит сразу ответить на вопрос: учить данные языки полезно всем – от школьника до человека в возрасте. Ведь логические языки программирования способны буквально заставить наш мозг думать логически. Также такие языки будут очень полезны в создании искусственного интеллекта или при работе с данными.
Логические языки программирования
Таких языков не так много, и они отличаются между собой. Мы поговорим только о двух, а начнем с того, с которого началась эра логических языков, и имя ему Prolog.
Данный язык был разработан в 1972 году Аленом Колмероэ и является актуальным и свежим и на сегодняшний день. Хоть это и не самый простой язык в плане синтаксиса, но зато весьма полезен в понимании логики компьютера. Посмотрите, как выглядит код, описывающий книгу:
Такое описание довольно просто понять и разобрать что к чему. Именно поэтому обучение подобному языку дальше не составит огромных трудностей и не потребует танцев с бубном.
Давайте дальше разберем его плюсы и минусы.
1. Код легко понять и запомнить.
Как уже упоминалось выше, код в языке Prolog пишется не так уж и сложно. Он довольно прост, в понимании обычного пользователя.
2. Выражения и факты.
Данный язык можно использовать без каких-либо вычислений, опираясь только на выражения и факты.
Какой бы путь к реализации вашей задумки вы ни выбрали, он практически никогда не влияет на результат выполнения программы.
1. Слабые инвестиции.
Из-за того, что этот язык мало поддерживают в материальном плане – он развивается довольно медленно, маленькими шажками.
2. Невозможность создания комплексных программ.
Данный язык будет невозможно использовать без связки с другим, если вы хотите создавать более сложные программы с большим функционалом.
3. Вычислительные операции.
Для вычислительных операций опять же придется использовать другие языки.
Пошедший от языка Prolog, Mercury создан, чтобы решить две проблемы, связанные с популярным языком программирования.
Логические языки программирования довольно сильно уступают в производительности императивному типу.
В языках такого типа уходит довольно много времени на отладку программы, а также производится меньше проверок на ошибки в программе, из-за чего порой происходят неприятности.
Пример кода на Mercury:
Синтаксис и понимание данного языка, как можно заметить, весьма отличаются от «Пролога», что немного усложняет обучение, однако некоторые его плюсы, помогающие решить проблемы «Пролога», весьма полезны.
Заключение
Языком логического программирования является язык, который обрабатывает выражения и факты, а побочным эффектом выдает результат работы данной программы. Такие языки весьма полезны в создании искусственного интеллекта и работы с данными, однако редко применяются без сторонних языков программирования.
и декларативно читаются как логические следствия:
В ASP и Datalog логические программы имеют только декларативное чтение, и их выполнение выполняется с помощью процедуры проверки или генератора моделей, поведение которых не предназначено для управления программистом. Однако в семействе языков Prolog логические программы также имеют процедурную интерпретацию как процедуры приведения к цели:
Рассмотрим в качестве примера следующий пункт:
Содержание
История
Ассоциация логического программирования была создана для содействия логического программирования в 1986 году.
Концепции
Логика и контроль
Логическое программирование можно рассматривать как управляемую дедукцию. Важным понятием в логическом программировании является разделение программ на их логический компонент и компонент управления. В языках программирования чистой логики только логический компонент определяет производимые решения. Компонент управления может быть изменен для предоставления альтернативных способов выполнения логической программы. Это понятие выражено слоганом
Алгоритм = Логика + Управление
где «Логика» представляет собой логическую программу, а «Управление» представляет различные стратегии доказательства теорем.
Решение проблем
Для поиска в этом пространстве можно использовать любую стратегию поиска. Prolog использует последовательную стратегию отслеживания с возвратом, в соответствии с которой одновременно рассматриваются только одна альтернатива и одна подцель. Также возможны другие стратегии поиска, такие как параллельный поиск, интеллектуальный поиск с возвратом или поиск по первому наилучшему для поиска оптимального решения.
Отрицание как неудача
Для большинства практических приложений, а также для приложений, которые требуют немонотонных рассуждений в искусственном интеллекте, логические программы с предложением Хорна необходимо расширить до обычных логических программ с отрицательными условиями. Положение в нормальной логической программе имеет вид:
и декларативно читается как логическое следствие:
H if A1 and … and An and not B1 and … and not Bn.
где H и все и являются атомарными формулами. Отрицание в отрицательных литералах обычно упоминается как « отрицание как сбой », потому что в большинстве реализаций отрицательное условие выполняется, показывая, что положительное условие не выполняется. Например: Ai Bi not Bi not Bi Bi
Учитывая цель найти что-то, что умеет летать:
Логический статус отрицания как неудачи не был решен до тех пор, пока Кейт Кларк [1978] не показал, что при определенных естественных условиях это правильная (а иногда и полная) реализация классического отрицания в отношении завершения программы. Сумма завершения примерно равна набору всех предложений программы с одним и тем же предикатом в левой части, скажем
как определение предиката
где «если и только если» означает «тогда и только тогда». Написание завершения также требует явного использования предиката равенства и включения набора соответствующих аксиом равенства. Однако для реализации отрицания путем отказа нужны только if-половины определений без аксиом равенства.
Например, выполнение приведенной выше программы:
canfly(X) iff bird(X), not abnormal(X). abnormal(X) iff wounded(X). bird(X) iff X = john or X = mary. X = X. not john = mary. not mary = john.
Представление знаний
Варианты и расширения
Пролог
Следующим летом 1972 года Ковальский, снова работая с Колмерауэром, разработал процедурную интерпретацию импликаций. Эта двойная декларативная / процедурная интерпретация позже была формализована в нотации Пролога.
Абдуктивное логическое программирование
где предикат normal приводим.
Программирование с абдуктивной логикой используется для диагностики неисправностей, планирования, обработки естественного языка и машинного обучения. Он также использовался для интерпретации отрицания как неудачи как формы абдуктивного рассуждения.
Металогическое программирование
Программирование логики ограничений
Однако, в то время как предикаты в заголовках предложений определяются программой логики ограничений, предикаты в ограничениях предопределены некоторой теоретико-модельной структурой или теорией, зависящей от предметной области.
С процедурной точки зрения подцели, предикаты которых определены программой, решаются путем редукции целей, как в обычном логическом программировании, но ограничения проверяются на выполнение с помощью решателя ограничений, зависящего от предметной области, который реализует семантику предикатов ограничений. Первоначальная проблема решается путем сведения ее к выполнимой комбинации ограничений.
Следующая программа логики ограничений представляет собой игрушечную временную базу данных john’s истории как учителя:
Здесь ≤ и представлены предикаты ограничений с их обычной предполагаемой семантикой. Следующее целевое предложение запрашивает базу данных, чтобы узнать, когда john и учили, logic и когда были professor :
:- teaches(john, logic, T), rank(john, professor, T).
Параллельное логическое программирование
Возможно, параллельное логическое программирование основано на передаче сообщений, поэтому оно подвержено той же неопределенности, что и другие параллельные системы передачи сообщений, такие как субъекты (см. Неопределенность в параллельных вычислениях ). Карл Хьюитт утверждал, что параллельное логическое программирование не основано на логике в его понимании, что вычислительные шаги не могут быть логически выведены. Однако в параллельном логическом программировании любой результат завершения вычисления является логическим следствием программы, а любой частичный результат частичного вычисления является логическим следствием программы и остаточной цели (технологической сети). Таким образом, неопределенность вычислений означает, что не все логические следствия программы могут быть выведены.
Программирование логики параллельных ограничений
Индуктивное логическое программирование
Логическое программирование высшего порядка
Программирование линейной логики
Основание логического программирования в линейной логике привело к созданию языков логического программирования, которые значительно более выразительны, чем языки, основанные на классической логике. Программы с предложениями Horn могут представлять изменение состояния только путем изменения аргументов предикатов. В линейном логическом программировании можно использовать внешнюю линейную логику для поддержки изменения состояния. Некоторые ранние разработки языков логического программирования, основанные на линейной логике, включают LO [Andreoli & Pareschi, 1991], Lolli, ACL и Forum [Miller, 1996]. Форум дает целенаправленную интерпретацию всей линейной логики.
Объектно-ориентированное логическое программирование
F-logic расширяет логическое программирование за счет объектов и синтаксиса фреймов.
Logtalk расширяет язык программирования Prolog за счет поддержки объектов, протоколов и других концепций ООП. Он поддерживает большинство совместимых со стандартами систем Prolog в качестве внутренних компиляторов.
Программирование логики транзакций
Языком логического программирования является
10.1. Классификация языков программирования
Языки программирования в зависимости от базовых конструкций языка, заложенных в структуру программы можно разбить на четыре категории [9]:
Программа, написанная на функциональном языке, выражает алгоритм решения задачи в терминах значений, которые возвращают функции. Таким образом, программа представляет набор функций, каждая из которых возвращает только одно значение определенного типа. Работа программы (алгоритм решения задачи) представляет собой последовательный вызов функций. К функциональным языкам относится С.
Программа, написанная на объектно-ориентированном языке, представляет собой набор объектов, взаимодействующих между собой посредством посылки сообщений. Каждый объект характеризуется информационной составляющей (набором атрибутов) и поведенческой (набор событий и методов). Работа программы представляет собой последовательный обмен сообщениями (вызов методов) между объектами. К объектно-ориентированным языкам относятся Object Pascal, Visual Basic, С++, Java и т.д. Следует отметить, что в любом объектно-ориентрованном языке имеется возможность процедурного программирования.
Общим для всех перечисленных категорий языков является то, что в программе описывается, что и как необходимо сделать для решения задачи, т.е. описывается последовательность решения задачи.
Программа, написанная на декларативном языке, представляет собой описание предметной области через набор отношений (англ. relation) между объектами (сущностями) и формулировку цели (задачи), которую требуется решить. В отличие от перечисленных выше языков, в такой программе нет явного описания последовательности действий, необходимых для решения задачи. Как правило, процедура поиска решения выполняется автоматически с использованием соответствующего математического или логического аппарата, лежащего в основе языка и реализованная в его конкретном интерпретаторе 1 (компиляторе 2 ). К декларативным языкам относятся Prolog, SQL и т.д. Таким образом, несомненным достоинством декларативных языков является концентрация внимания разработчика на том, что надо сделать, а не как.
Другая классификация языков программирования основана на стиле программирования [30]:
— императивные – программа представляет собой последовательность операторов (команд, выполняемых компьютером), с помощью которых программист должен объяснить компьютеру, как нужно решать задачу (функциональные, процедурные и объектно-ориентированные языки программирования);
— декларативные – программа представляет собой совокупность утверждений, описывающих предметную область или сложившуюся ситуацию, с помощью которых программист должен описать, что нужно решать (найти) – поиском решения будет заниматься императивная система программирования.
Известна классификация языков программирования по их близости либо к машинному, либо к естественному человеческому языку. Те, что ближе к компьютеру, относят к языкам низкого уровня (Ассемблер), а те, что ближе к человеку, называют языками высокого уровня (Basic, Pascal, Java и т.д.). В этом смысле декларативные языки можно назвать языками сверхвысокого или наивысшего уровня, поскольку они очень близки к человеческому языку и человеческому мышлению.
10.2. Основные вехи развития языка Пролог
Идеи использования логики в качестве языка программирования зародилась в начале 1970-х годов. Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы, статьи 1971 и 1974 г.), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация, 1973 г.). В 1973 году «группа искусственного интеллекта» во главе с Аленом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (фр. PROgrammation en LOGique) и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алена Колмероэ. Программа была написана на Фортране и работала довольно медленно.
Популяризации Пролога во многом способствовали:
— эффективная реализация (интерпретатор/компилятор) этого языка для ЭВМ DEC-10 Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга в 1977 г. Послужила прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как «эдинбургская версия», фактически стала первым и единственным стандартом языка;
— разработка Кларком и Маккейбом (Великобритания) в 1980 году версии для персональных ЭВМ;
На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic iis Workbench, Strawberry Prolog, SWI-Prolog, Turbo Prolog (PDC Prolog, Visual Prolog), UNSW Prolog и т. д. В нашей стране были разработаны такие версии Пролога как Пролог-Д (С. Григорьев), Акторный Пролог (А. Морозов), а также Флэнг (А. Манцивода, В. Петухин).
5 ISO – International Organization of Standardization (Международная организация по стандартизации).
6 IEC – International Electrotechnical Commission (Международная комиссия по электротехнике).
10.3. Основные понятия Пролога
При формальном описании синтаксиса конструкций алгоритмических языков часто используется так называемая «нормальная форма Бэкуса-Наура» (БНФ), разработанная в 1960 Джоном Бэкусом и Питером Науром. Впервые БНФ была применена Питером Науром при записи синтаксиса языка Алгол-60 [30]. Основными конструкциями БНФ являются следующие.
Символ «|» означает в нотации БНФ «или». Он применяется для разделения альтернативных толкований определяемого понятия. Например, десятичную цифру можно определить следующим образом:
Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной (может присутствовать или отсутствовать), например
означает, что целое число можно определить через положительное целое число, перед которым может стоять знак минус.
Символ «*» обозначает, что часть синтаксической конструкции может повторяться произвольное число раз (ноль и более). Заметим, что иногда вместо символа «*» используют фигурные скобки « ». Например, положительное целое число в нотации БНФ можно следующим образом:
Т.е. положительное целое число состоит из одной или нескольких цифр.
Программа на Прологе состоит из предложений (утверждений). Каждое предложение заканчивается точкой.
Предложение имеет вид
При необходимости применения дизъюнкции (логическое ИЛИ, ∨) используется символ «;», действующий до следующей дизъюнкции, окончания правила или закрывающей круглой скобки. Например,
Предложения бывают трех видов: факты, правила, вопросы.
А) Факт – это предложение, у которого нет тела. В терминах логики предикатов, факт – это и есть предикат. Он фиксирует (определяет) некоторое отношение между объектами. Например, факт, что Наташа является мамой Даши, может быть записан в виде (в SWI-Prolog строки-константы записываются в одинарных кавычках):
Факт представляет собой безусловно истинное утверждение. Если воспользоваться нормальной формой Бэкуса-Науэра, то предикат можно определить следующим образом:
т.е. предикат состоит либо только из имени, либо из имени и следующей за ним последовательности аргументов (термов), заключенной в скобки.
Аргументом (термом) предиката может быть константа, переменная или составной объект (список или функция). Число аргументов предиката называется арностью.
Б) Правило – предложение, истинность заголовка которого в виде предиката зависит от истинности одной или нескольких формул, указанных в теле. Обычно правило содержит несколько хвостовых целей, которые должны быть истинными для того, чтобы само правило было истинным. В нотации БНФ правило будет иметь вид:
| grandmama(X, Y):- mama(X, Z), mama(Z, Y). grandmama(X, Y):- mama(X, Z), papa(Z, Y). |
или
grandmama(X, Y):-
mama(X, Z), mama(Z, Y);
mama(X, Z), papa(Z, Y).
или
grandmama(X, Y):-
mama(X, Z), (mama(Z, Y); papa(Z, Y)).
В) Вопрос (запрос, цель) – предложение, состоящее только из тела. В нотации БНФ вопрос имеет вид:
Вопросы используют для выяснения выполнимости некоторого отношения между описанными в программе объектами. Автоматическая система логического вывода Пролога рассматривает вопрос как цель, к которой надо стремиться. Ответ на вопрос может оказаться положительным (true) или отрицательным (false), в зависимости от того, может ли быть достигнута соответствующая цель.
Программа может содержать вопрос в теле (внутренняя цель). Если программа содержит внутреннюю цель, то после запуска программы на выполнение система сразу проверяет достижимость заданной цели. Если внутренней цели в программе нет, то после запуска программы система выдает приглашение вводить вопросы в диалоговом режиме (внешняя цель). Программа, компилируемая в исполняемый файл, обязательно должна иметь внутреннюю цель.
Если цель достигнута, система отвечает «yes» («true»), в противном случае «no» («false»). Следует отметить, что ответ «no» на вопрос не всегда означает, что он отрицательный. Система может дать такой ответ и в том случае, когда у нее просто недостаточно информации, позволяющей положительно ответить на вопрос. Т.е. Пролог основан на т.н. «модели закрытого мира», в которой все, что можно получить на основе описания модели является истиной, а остальное – ложью.
Во всех предложениях можно использовать переменные. Считается, что переменные в теле одного правила неявно связаны квантором всеобщности. Имя переменной в Прологе может состоять из букв латинского алфавита, цифр, знаков подчеркивания и должно начинаться с прописной буквы или знака подчеркивания. При этом переменные в теле правила неявно связаны квантором всеобщности и эквивалентны объектам предметной области. Переменные могут быть свободными или связанными.
Свободная переменная – переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными.
Переменная, которая получила какое-то значение, называется связанной. Такой переменной не может быть присвоено новое значение, т. е., по сути, переменная становится константой.
Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно и то же имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания «_». Анонимная переменная предписывает интерпретатору (компилятору) проигнорировать значение аргумента (терма). Если в правиле несколько анонимных переменных, то все они отличаются друг от друга, несмотря на то, что записаны с использованием одного и того же символа («_»). Анонимные переменные могут записываться только в качестве терма предиката. Использовать их в выражениях (например, арифметических) нельзя. Пример использования анонимной переменной в вопросе «Есть ли у Даши мама?»:
Разновидности предложений Пролога, записанные в виде фраз Хорна (B ← A), можно интерпретировать следующим образом:
Рассмотрим несколько примеров. Пусть в программе заданы следующие факты (предикаты) и правила:
| mama(‘Наташа’, ‘Даша’). mama(‘Даша’, ‘Маша’). mama(‘Наташа’, ‘Вася’). |
grandmama(X, Y):-
mama(X, Z), (mama(Z, Y); papa(Z, Y)).
grandpapa(X, Y):-
papa(X, Z), (mama(Z, Y); papa(Z, Y)).
Вопрос 1 – является ли Наташа мамой Даши:
Вопрос 2 – кто является мамой Даши:
Первая строка сообщения означает, что ответ найдет и мамой Даши является Наташа; вторая – что в базе знаний для оставшихся предложений не обнаружены другие мамы Даши.
Вопрос 3 – есть ли у Даши мама:
Вопрос 4 – найти всех мам и детей:
В данном случае после третьего ответа не выдается «false», т.к. в базе знаний были перебраны все предложения и они все истинны.
Вопрос 5 – для кого Наташа является бабушкой:
10.4. Краткие сведения об операциях и встроенных предикатах SWI-Prolog
В табл. 10.1 приведены некоторые операции и предикаты SWI-Prolog, которые в дальнейшем будут использоваться для иллюстрации примеров.
Некоторые операции и предикаты SWI-Prolog
10.5. Процедура вывода в Прологе
При поиске решения (доказательства цели) в Прологе используется метод перебора с возвратами (поиск в глубину). Пролог при доказательстве утверждения поочередно пытается установить истинность, входящих в него предикатов (утверждений). Если первый предикат истинен, то Пролог переходит ко второму. Если и он истинен, то переходит к третьему. Если второй предикат ложен, то Пролог пытается установить его истинность при других значениях, входящих в него переменных. Если этого не удается сделать, то он возвращается к первому предикату и пытается установить его истинность для новых значений переменных, а затем снова возвращается к доказательству второго предиката. Такая процедура повторяется до тех пор, пока не будет достигнута истинность последнего предиката. После доказательства истинности последнего предиката цели Пролог завершает работу. Процесс возврата в Прологе называется backtracking.
Например, пусть имеется запрос на определения внучек и внуков «Наташи»:
| ?- mama(‘Наташа’, Y), (mama(Y, Z); papa(Y, Z)), write(Z); write(‘Всё’). |
Ответ:
Маша ;
Маша ;
Всё ;
Примечание. Выделенная жирным часть соответствует правилу определения бабушки (grandmama).
Процедура доказательства (перебора с возвратами) приведена в табл. 10.2.
Некоторые операции и предикаты SWI-Prolog
| № п/п | Предикат запроса | Проверяемый предикат базы знаний | Результат |
| 1 | mama(‘Наташа’, Y) | mama(‘Наташа’, ‘Даша’) | Y = ‘Даша’ |
| 2 | mama(Y, Z) ≡ mama(‘Даша’, Z) | mama(‘Наташа’, ‘Даша’) | backtracking |
| 3 | mama(Y, Z) ≡ mama(‘Даша’, Z) | mama(‘Даша’, ‘Маша’) | Z = ‘Маша’ |
| 4 | write(Z) ≡ write(‘Маша’) | ‘Маша’ | |
| 5 | mama(Y, Z) ≡ mama(‘Даша’, Z) | mama(‘Наташа’, ‘Вася’) | backtracking |
| 6 | papa(Y, Z) ≡ papa(‘Даша’, Z) | papa(‘Вася’, ‘Маша’) | backtracking |
| 7 | mama(‘Наташа’, Y) | mama(‘Даша’, ‘Маша’) | backtracking |
| 8 | mama(‘Наташа’, Y) | mama(‘Наташа’, ‘Вася’) | Y = ‘Вася’ |
| 9 | mama(Y, Z) ≡ mama(‘Вася’, Z) | mama(‘Наташа’, ‘Даша’) | backtracking |
| 10 | mama(Y, Z) ≡ mama(‘Вася’, Z) | mama(‘Даша’, ‘Маша’) | backtracking |
| 11 | mama(Y, Z) ≡ mama(‘Вася’, Z) | mama(‘Наташа’, ‘Вася’) | backtracking |
| 12 | papa(Y, Z) ≡ papa(‘Вася’, Z) | papa(‘Вася’, ‘Маша’) | Z = ‘Маша’ |
| 13 | write(Z) ≡ write(‘Маша’) | ‘Маша’ | |
| 14 | write(‘Всё’) | ‘Всё’ |
1) Указанная последовательность имеет место, если в SWI-Prolog после вывода на консоль имени внучки (внука) нажимать клавишу «;» (поиск альтернативного доказательства).
2) Жирным выделены строки, для которых выполнение предиката истинно.
Рекурсия – процесс повторения элементов самоподобным образом. Рекурсия (в программировании) – алгоритмический метод, заключающийся в возможности обращения правила (функции, процедуры) к самому себе один или более раз.
На вопрос predok(‘Вася’, ‘Миша’) ответ будет положительным.
Второй пример использования рекурсии – расчет факториала.
На вопрос fact(6, F) ответ будет «F = 720».
Любая рекурсивная процедура в Прологе должна включать, как минимум два правила:
1) нерекурсивное правило, определяющее его вид в момент прекращения рекурсии;
10.7. Управление процессом вывода
В Прологе имеется два стандартных предиката, которые позволяют управлять процедурой перебора с возвратами:
— fail (false) – предикат, который всегда возвращает ложь;
Первый из них используется для организации циклов, а второй для ускорения процедуры перебора.
Если мы желаем узнать всех предков «Миши» и при этом, чтобы выдача предков на консоль была выполнена автоматически, а не в диалоговом режиме (путем нажатия «;» после каждого ответа), тогда запрос должен выглядеть следующим образом:
| ?- writeln(‘Предки Миши:’), predok(A, ‘Миша’), writeln(A), fail; true. |
Ответ:
Предки Миши:
Юля
Вася
Коля
Таким образом, предикат fail выполняет принудительный откат и заставляет Пролог заново передоказывать все предыдущие подцели с новыми значениями переменных. Передоказательству в приведенном примере будет подвержен только предикат predok(A, ‘Миша’), т.к. предикаты write и writeln не генерируют новые значения переменных. Если после предиката fail находятся другие предикаты правила, указываемые через «,» (логическое И), то они никогда не будут выполнены.
Рассмотрим более сложный пример: выяснить всех правнуков «Коли».
| ?- roditel(‘Коля’, A), write(‘Правнуки (‘), write(A), writeln(‘):’), roditel(A, B), writeln(B), fail; true. |
Ответ:
Правнуки (Юля):
Миша
Маша
Правнуки (Света):
Рома
Леша
10.8. Способы организации циклов
В Прологе отсутствуют конструкции циклов с параметром, пред- и постусловием, но с помощью соответствующих механизмов можно организовать разные типы циклов.
1 способ. Используя рекурсию.
2 способ. Используя предикат, который можно передоказать, и предикат fail.
| ?- predok(A, B), write(A), write(‘ является предком ‘), writeln(B), B == ‘Миша’; true. |
Ответ:
Вика является предком Коля
Вася является предком Коля
Коля является предком Юля
Юля является предком Миша
Такая конструкция соответствует циклу с постусловием.
4 способ. Организация цикла со счетчиком, используя предикат repeat и динамическое добавление фактов в базу знаний (программу).
Следует отметить, что в некоторых реализациях языка Пролог отсутствует встроенный предикат repeat. Тогда данный предикат надо определить в программе следующим образом
Приведенная программа будет циклически выдавать на экран квадраты чисел от 1 до 10. В качестве счетчика используется предикат (факт) count, который динамически добавляется и удаляется из базы знаний.
Существуют также другие способы организации циклов.
В Прологе нет такой распространенной и часто используемой структуры хранения данных как массивы, но зато есть развитые возможности работы со списками. Список – упорядоченный набор элементов одного типа. В отличие от массивов, количество элементов которых строго фиксировано (в большинстве языков программирования), списки позволяют модифицировать, добавлять или удалять из него элементы.
Списки в Прологе заключаются в квадратные скобки, например [1, 2, 8, 123] или [‘Пн’, ‘Вт’, ‘Четверг’]. Список, не содержащий ни одного элемента «[]», называется пустым. Каждый непустой список состоит из двух частей: головы и хвоста. Головой является первый элемент списка, хвостом – все остальное.
Списки и его составные части
| Список | Голова | Хвост |
| [1, 2, 8, 123] | 1 | [2, 8, 123] |
| [‘Пн’, ‘Вт’, ‘Четверг’] | ‘Пн’ | [‘Вт’, ‘Четверг’] |
| [1.25] | 1.25 | [] |
| [] | не определена | не определен |
В программе голова отделяется от хвоста символом «|».
Часто используемыми операциями при работе со списками являются:
1. Проверка наличия элемента в списке.
?- member(2, [1, 3, 45, 2, 74]),
write(‘Да’);
write(‘Нет’).
2. Добавление элемента в список. Для данной операции не требуется отдельного правила, если элемент X добавляется в начало списка List
3. Конкатенция двух списков.
| % 1 параметр – первый список % 2 параметр – второй список % 3 параметр – результат объединения двух списков concat([], L2, L2). concat([X|L1], L2, [X|L3]):- concat(L1, L2, L3). |
?- concat([1, 2], [3, 45], L),
write(L).
4. Удаление элемента из списка и задание обратного порядка следования элементов списка.
| % 1 параметр – удаляемый элемент % 2 параметр – исходный список % 3 параметр – рабочий список % 4 параметр – перевернутый список без элемента delete(_, [], L, L). delete(X, [X|L], L1, L2):- delete(X, L, L1, L2). delete(X, [Y|L], L1, L2):- X \== Y, delete(X, L, [Y|L1], L2). |
% 1 параметр – исходный список
% 2 параметр – рабочий список
% 3 параметр – перевернутый список
reverse([], Lr, Lr).
reverse([X|L], L1, Lr):- reverse(L, [X|L1], Lr).
?- delete(1, [1, 3, 1, 45, 1], [], L),
reverse(L, Lr),
write(Lr).
5. Разделение списка на два.
| % 1 параметр – элемент, задающий разбиение % 2 параметр – исходный список % 3 параметр – элементы, меньшие или равные 1 параметру % 4 параметр – элементы, большие 1 параметра split(_, [], [], []). split(Y, [X|L], [X|L1], L2):- X =@ Y, split(Y, L, L1, L2). |
?- split(7, [1, 3, 1, 45, 1, 33], L1, L2),
writeln(L1),
writeln(L2).