Анализ способов завершения рекурсии в рекурсивных правилах на языке логического программирования Пролог

Здор Дмитрий Валерьевич кандидат педагогических наук доцент, Кафедра проектирования и механизации технологических процессов, Инженерно-технологический институт, Федеральное государственное бюджетное образовательное учреждение высшего образования «Приморская государственная сельскохозяйственная академия», 692503, Россия, Приморский край, г. Уссурийск, ул. Комсомольская, 64, кв. 10 Zdor Dmitrii Valer'evich PhD in Pedagogy Docent, the department of Design and Mechanization of Technological Processes, Primorye State Agricultural Academy 692503, Russia, Primorskii krai, g. Ussuriisk, ul. Komsomol'skaya, 64, kv. 10 zdor_d@inbox.ru

Горностаева Татьяна Николаевна кандидат физико-математических наук доцент, кафедры математики, физики, информатики и методики преподавания, Филиал федерального государственного автономного образовательного учреждения высшего образования «Дальневосточный федеральный университет» в г. Уссурийске 692519, Россия, Приморский край, г. Уссурийск, ул. Некрасова, 35 Gornostaeva Tat'yana Nikolaevna PhD in Physics and Mathematics Docent, the department of Mathematics, Physics, Informatics and Teaching Technique, Ussuriysk branch of Far Eastern Federal University 692519, Russia, Primorskii krai, g. Ussuriisk, ul. Nekrasova, 35 gorno-tatyana@yandex.ru

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

Различным аспектам программирования на языке Пролог посвящены многие работы.

Основы логического программирования и особенности языка Пролог, такие как, основные конструкции языка, виды предложений, механизм выполнения программы, методика проектирования логических программ, рассмотрены в работах У. Клоксина ^[3], Г. Метакидеса, А. Нероуд ^[6].

В работах И. Братко ^[2] показано применение языка Пролог в различных областях искусственного интеллекта.

Рекурсия как объект специального изучения представлен в работах А.Н. Адаменко, Л. Стерлинга, E. Costa. Так, А.Н. Адаменко рассматривает рекурсию как способ организации повтора предикатов в программе на Прологе ^{[1, c. 319]}. Л. Стерлинг прибегает к рекурсивному программированию в контексте обработки особого типа данных – списков ^{[7, c. 82]}. Е. Costa приводит примеры рекуррентных соотношений ^{[10, с. 119-120]}.

Правила записи рекурсивных определений средствами языка Пролог, варианты организации рекурсии по нисходящей и восходящей схемам, примеры программ с использованием рекурсивных правил представлены в работе Н.И. Цукановой, Т.А. Дмитриевой ^{[9, с. 108]}.

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

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

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

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

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

Чтобы доказать цель программы, указанной в разделе Goal, например,

Goal А, В, С.

система Пролог должна проверить на истинность все предикаты цели А, В, С, причем, проверяются они в порядке следования их в цели слева – направо.

Это делается путем сопоставления предикатов А, В, С с фактами и правилами программы из базы знаний программы, т.е. разделаclouses, причем, факты и правила просматриваются в порядке их следования в БЗ сверху – вниз.

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

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

Одним из таких средств выступает рекурсия.

Для организации в программе повтора действий, в Прологе используют стандартный предикат repeat, который используется совместно с рекурсивным правилом в конструкции следующего вида:

repeat.

repeat:- repeat.

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

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

Вместе с тем заметим, что в указанной конструкции для организации повторений используется рекурсивное правило repeat:- repeat, Таким образом, данное стандартное средство организации повторения предикатов реализовано через рекурсию.

Правило, которое обращается само к себе, называется рекурсивным.

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

Пример 1.

predicates

write_string /* Нульместный предикат – записать строку */

clauses

write_string :- write («Вывод произвольной строки»), nl, write_string.

goal

write_string.

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

Пример 2.

predicates

write_string (integer) /* Одноместный предикат – записать строку */

clauses

write_string (N):- N < 11, write («Вывод произвольной строки»), nl, N1 = N + 1,

write_string (N1).

goal

write_string (1).

В этой программе пришлось снабдить предикат аргументом, чтобы работало условие N < 11, поэтому программа выведет строку 10 раз. Рассмотрим поэтапно процесс выполнения.

Предикат цели write_string (1) сопоставим с головой правила write_string (N), если N конкретизируется значением 1.

Чтобы доказать истинность головного предиката write_string (1), нужно доказать истинность предикатов в теле: первые 4 предиката тела правила: 1< 11, write, nl, N1 =2 –истинны; 5-ый предикат write_string (2) сопоставим с головой правила write_string (N), если N конкретизируется значением 2.

Чтобы доказать истинность головного предиката write_string (2) (второй виток рекурсии), нужно доказать истинность предикатов в теле: первые 4 предиката тела правила: 2< 11, write, nl, N1 =3 –истинны; 5-ый предикат write_string (3) сопоставим с головой правила write_string (N), если N конкретизируется значением 3.

Чтобы доказать истинность головного предиката write_string (3), (третий виток рекурсии), нужно доказать истинность предикатов в теле: первые 4 предиката тела правила: 3< 11, write, nl, N1 =4 –истинны; 5-ый предикат write_string (4) сопоставим с головой правила write_string (N), если N конкретизируется значением 4. Витки рекурсии 4-10 будут аналогичными.

Чтобы доказать истинность головного предиката write_string (11) (11-тый виток рекурсии), нужно доказать истинность предикатов в теле. Первый предикат в нем 11< 11 будет ложным, Пролог возвратиться до головы write_string (11), но альтернативы для него нет. Следовательно, головной предикат 11-го витка рекурсии write_string (11) ложен; значит, ложен сопоставимый с ним предикат write_string (11) из тела 10-го витка; значит, головной предикат 10-го витка рекурсии write_string (10) ложен; значит, ложен сопоставимый с ним предикат write_string (10) из тела 9-го витка и т.д.

В конечном счете, головной предикат 1-го витка рекурсии write_string (1) ложен; следовательно, ложен сопоставимый с ним предикат цели write_string (1) и цель программы тем самым не доказана. Но решена практическая задача программиста – на экран 10 раз выведена нужная строка.

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

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

Пример 3.

predicates

write_string (integer) /* Нульместный предикат – записать строку */

clauses

write_string (11). /* Факт */

write_string (N) :- write («Вывод произвольной строки»), nl, N1 = N + 1,

write_string (N1).

goal

write_string (1).

Эта программа тоже выведет 10 раз на экран заданную строку, но доказательство цели будет отличаться от примера 2. Предикат в теле правила write_string (N1) на каждом витке рекурсии сначалабудет сопоставляться с фактом write_string (11), пока N1

В конечном счете, головной предикат 1-го витка рекурсии write_string (1) истинен, следовательно, истинен сопоставимый с ним предикат цели write_string (1) и цель программы тем самым доказана.

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

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

Пример 4. Вычисление n!

Известно, что n! можно определить следующим образом:

n! = 1∙2∙3∙4∙…∙n или n! =

Второе определение уже является рекурсивным, так как n! определяется через (n-1)!. Составим программу, вычисляющую n!. Для описания отношений между n и n! введем предикат fact (N,M), где 1-ый аргумент – заданное число, а 2-ой – его факториал.

predicates

fact(integer, integer)

clauses

fact (0,1). /* Факт, утверждающий, что 0! = 1 */

fact (N,M) :- N1 = N -1, fact (N1,M1), M = M1*N.

goal

write («Введите целое число »), readint (K), fact (K,X), nl, write («Факториал », K, « равен », Х).

Эта программа в базе знаний содержит процедуру fact, состоящую из факта и рекурсивного правила, в котором предикат fact содержится не в конце, а в середине тела правила. Рассмотрим, как программа будет находить решение, если ввести, например K=3.

1. Так как в цели write и readint - истинные предикаты, Пролог должен доказать только истинность fact (3,X), где Х – свободная переменная. Ее значение и должен найти Пролог в результате доказательства цели.

2. Предикат fact (3,X) сначала сопоставляется с фактом fact (0,1), так как он 1-ый в БЗ, но сопоставление терпит неуспех, т.к. первые аргументы различны.

3.Тогда предикат fact (3,X) сопоставляется с головным предикатом правила fact (N(1),M(1)), они сопоставимы, если N(1) конкретизируется значением 3; М(1) сцепляется с Х, обе они пока свободны. Теперь Прологу нужно доказать истинность головного предиката fact (3,М(1)).

4. Чтобы доказать истинность головного предиката fact (3,М(1)) (1-ый виток рекурсии), Прологу нужно доказать истинность предикатов в его теле: 1-ый предикат N1(1) = 2 –истинен, т.к. N1(1) просто получает значение 2; 2-ой предикат тела fact(2,М1(1)) не сопоставим с фактом, но сопоставим с головой правила fact (N(2),М(2)), если: N(2) конкретизируется значением 2; М(2) сцепляется с М1(1), обе они пока свободны. Теперь Прологу нужно доказать истинность предиката fact (2,М(2)).

5. Чтобы доказать истинность головного предиката fact (2,М(2)) (2-ой виток рекурсии), Прологу нужно доказать истинность предикатов в его теле: 1-ый предикат N1(2) = 1 – истинен, N1(2) получает значение 1; 2-ой предикат тела fact(1,М1(2)) не сопоставим с фактом, но сопоставим с головой правила fact (N(3),М(3)), если: N(3) конкретизируется значением 1; М(3) сцепляется с М1(2), обе они пока свободны. Теперь Прологу нужно доказать истинность предиката fact (1,М(3)).

6. Чтобы доказать истинность головного предиката fact (1,М(3)) (3-ий виток рекурсии), Прологу нужно доказать истинность предикатов в теле: 1-ый предикат N1(3) = 0 – истинен, N1(3) получает значение 0; 2-ой предикат тела fact (0,М1(3)) сопоставим уже с фактом fact (0,1), если М1(3) конкретизируется значением 1. Так как факт истинен, то истинен и предикат тела fact (0,1); 3-ий предикат тела М(3) = М1(3)* 1 = 1*1 =1 тоже истинен, т.к. свободная переменная М(3) получает значение равное 1.

7. Итак, на 3-ем витке рекурсии все 3 предиката тела, а значит головной предикат 3-го витка рекурсии fact(1, М(3) = 1))- истинен, следовательно, 3-ий предикат тела М(2) = М1(2)*2 =1*2=2-тоже истинен, т.к. свободная переменная М(2) получает значение 2, головной предиката 2-го витка рекурсии fact (2,М(2) = 2) истинен, 3-й предикат тела М(1) = М1(1)*3=2*3=6-тоже истинен, свободная переменная М(1) получает значение 6, головной предиката 1-го витка рекурсии fact (3,М(1))=6)-истинен, целевой предикат fact (3,Х = 6) – истинен. Переменная X получит значение 6, это значение будет выведено на экран.

Как следует из этих рассуждений факт fact (0,1) нужен для того, чтобы закончить рекурсию. Значение переменной X формируется при обратном ходе рекурсии.

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

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