Рекурсивное мышление на Прологе

Декларативное выражение рекурсии…

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

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

Основы рекурсии

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

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

sum(n)
  if n is less than 0, then return 0
  if n is 0 or 1, then return n
  return n + sum(n-1)

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

move_tower(n, source, destination, spare)
  if n is less than 1, then output “error”
  if n is 1, output “move top disk on {source} to {destination}”
  else
    move_tower(n-1, source, spare, destination)
    output “move top disk on {source} to {destination}”
    move_toweri(n-1, spare, destination, source)

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

Введение в Пролог

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

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

bear(b).
elephant(e).
frog(f).
ostrich(o).
salmon(s).

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

warm_blooded(A) :- mammal(A) ; bird(A).
cold_blooded(A) :- fish(A) ; amphibian(A).
mammal(A) :- bear(A) ; elephant(A).
bird(A) :- ostrich(A).
fish(A) :- salmon(A).
amphibian(A) :- frog(A).

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

?- warm_blooded(A).
A = b ;
A = e ;
A = o ;
false
?- mammal(o).
false
?- cold_blooded(s).
true

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

Рекурсия в Прологе

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

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

sum(1,1).
sum(N,0) :- N =< 0, !.

Рекурсивные правила используются для определения того, как использовать решение рекурсивного предиката для получения общего решения. В случае задачи суммирования правило должно выполнять некоторые арифметические действия: во-первых, установить переменную M на единицу меньше входной N, а во-вторых, вычислить сумму N и рекурсивного решения R, которое становится общим решением, S. (Сокращение в последнем предложении предотвращает дублирование решения, когда Prolog запрашивает альтернативное решение.)

sum(N,S) :- M is N-1, sum(M,R), S is N+R, !.

Запуск запроса дает ответ для определенного значения N или для того, является ли конкретная сумма правильным ответом для конкретного N:

?- sum(10,Answer).
Answer = 55 ;
false
?- sum(10,56).
false

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

Обычное первое упражнение на Прологе

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

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

В следующем простом примере есть шесть известных людей, представленных символами от a до f, которые появляются в факте person. Есть также три факта, указывающие на то, что родителями элементов c и d являются a и b и родителями элемента f являются c и e. Обратите внимание, что база данных не включает информацию о родителях a, b и e.

%% The Facts %%

person(a). 
person(b). 
person(c). 
person(d).
person(e).
person(f).

parents(a,b,c).
parents(a,b,d).
parents(c,e,f).

%% Convenience Predicate %%

parentOf(Child,Parent) :- parents(Parent,_,Child) ; parents(_,Parent,Child).

%% Reasoning about Multi-Generational Relationships %%

ancestorOf(Descendant,Ancestor) :- parentOf(Descendant,Ancestor).

ancestorOf(Descendant,Ancestor) :- parentOf(Descendant,Middle), 
                                   ancestorOf(Middle,Ancestor).

%% Another Convenience Predicate %%

descendantOf(Ancestor,Descendant) :- ancestorOf(Descendant,Ancestor).

?- ancestorOf(f,Ancestor).
Ancestor = c ;
Ancestor = e ;
Ancestor = a ; 
Ancestor = b ;
false

?- ancestorOf(e,Ancestor).
false

?- descendantOf(d, Descendant).
false

?- descendantOf(c, Descendant).
Descendant = f ;
false

?- descendantOf(b, Descendant).
Descendant = c ;
Descendant = d ;
Descendant = f ;
false

%% Tower Helper and Base Cases %%

report_move(Source, Destination) :- write('move top disk on '), 
                                    write(Source), write(' to '), 
                                    write(Destination), nl.

move_tower(N,_,_,_) :- N < 1, write(‘ERROR’), nl, !.
move_tower(1,S,D,_) :- report_move(S,D).

%% Tower Recursive Case %%

move_tower(N,S,D,X) :- M is N-1,
                       move_tower(M,S,X,D), 
                       report_move(S,D),
                       move_tower(M,X,D,S).

?- move_tower(3, starting, ending, spare).
move top disk on starting to ending
move top disk on starting to spare
move top disk on ending to spare
move top disk on starting to ending
move top disk on spare to starting
move top disk on spare to ending
move top disk on starting to ending