Статья 'Анализ способов завершения рекурсии в рекурсивных правилах на языке логического программирования Пролог' - журнал 'Программные системы и вычислительные методы' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > Требования к статьям > Политика издания > Редакция > Порядок рецензирования статей > Редакционный совет > Ретракция статей > Этические принципы > О журнале > Политика открытого доступа > Оплата за публикации в открытом доступе > Online First Pre-Publication > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала
ГЛАВНАЯ > Вернуться к содержанию
Программные системы и вычислительные методы
Правильная ссылка на статью:

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

Здор Дмитрий Валерьевич

кандидат педагогических наук

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

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

DOI:

10.7256/2454-0714.2021.4.35383

Дата направления статьи в редакцию:

31-03-2021


Дата публикации:

31-12-2021


Аннотация: В настоящее время одним из развивающихся направлений в области программирования является логическое программирование, связанное с реализацией инструментальных средств создания искусственного интеллекта. Одним из таких языков программирования является непроцедурный декларативный язык логического программирования Пролог. Статья посвящена использованию рекурсивных правил в программе на Прологе. Цель работы: проанализировать способы завершения рекурсивных вызовов в рекурсивных правилах, а также продемонстрировать использование выявленных способов на примерах программ с рекурсией. Был проведен анализ специальной литературы по теме исследования, обобщены и систематизированы данные, проведено тестирование программы и анализ хода выполнения программы. Рекурсивное правило в программе на Прологе задает бесконечный цикл повторения предикатов. Чтобы закончить рекурсивный цикл, в программу нужно поместить условие, заканчивающее цикл. В статье рассмотрены варианты организации рекурсии с завершением бесконечного цикла различными способами. На рассмотренных примерах были продемонстрированы способы организации и использования рекурсии в программах на Прологе. Приведенные примеры позволяют использовать их в качестве технологической основы в процессе программирования на языке Пролог при решении сходных задач. Полученные результаты могут быть использованы в дальнейшей разработке вопросов использования рекурсивных предикатов в логических языках программирования.


Ключевые слова:

логическое программирование, рекурсия, рекурсивное правило, условие окончания рекурсии, Prolog, механизм выполнения, процессах сопоставления, поиск с возвратом, предикаты, логические утверждения

Abstract: One of the developing trends in programming is the logic programming associated with the implementation of tools for creating artificial intelligence. One of such programming languages is the nonprocedural declarative logic programming language Prolog. This article is dedicated to the use of recursive rules in Prolog software. The goal of this work lies in analysis of the methods for completing recursive calls in recursive rules, as well as in explication of the use of such methods on the examples of programs with recursion. The author explores the specialized literature on the topic, generalized and systematizes the data, as well as tested the programs and the progress of their implementation. Recursive rule in the Prolog software sets an infinite cycle of repetition of predicates. For completing the recursive cycle, it is necessary to set a condition within the program that would end the cycle. The article examines the variants of organizing recursions with the completion of infinite cycle. The examples used in the article allows using them as the basis for programming in language Prolog for solving similar tasks. The acquired results are valuable for further development of the use of recursive predicates in logic programming languages.


Keywords:

logic programming, recursion, recursive rule, recursion end condition, Prolog, execution mechanism, mapping processes, search with a refund, predicates, logical statements

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

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

Основы логического программирования и особенности языка Пролог, такие как, основные конструкции языка, виды предложений, механизм выполнения программы, методика проектирования логических программ, рассмотрены в работах У. Клоксина [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 формируется при обратном ходе рекурсии.

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

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

Библиография
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

Результаты процедуры рецензирования статьи

В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.

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


Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.