Как работает рекурсивное отслеживание назад в Прологе

Question

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

Например, приведенные ниже строки кода, удаляет все вхождения элемента из списка:

remove_all(_, [], []).
remove_all(El, [El|Tail], Tail2):- 
    remove_all(El, Tail, Tail2).
remove_all(El, [Head|Tail], [Head|Tail2]):-
    not(El = Head),
    remove_all(El, Tail, Tail2).

Теперь я запрашиваю следующее? - remove_all( 2, [1,4,2,3,5,2,7,2], X). Я использовал онлайновый пролог SWISH, чтобы выполнить его с трассировкой, и я получил следующее дерево

 Call:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], _4896)
 Call:not(2=1)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=1))
 Call:remove_all(2, [4, 2, 3, 5, 2, 7, 2], _5128)
 Call:not(2=4)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=4))
 Call:remove_all(2, [2, 3, 5, 2, 7, 2], _5146)
 Call:remove_all(2, [3, 5, 2, 7, 2], _5146)
 Call:not(2=3)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=3))
 Call:remove_all(2, [5, 2, 7, 2], _5164)
 Call:not(2=5)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=5))
 Call:remove_all(2, [2, 7, 2], _5182)
 Call:remove_all(2, [7, 2], _5182)
 Call:not(2=7)
 Exit:not('10758ac0-dc91-4335-a0d8-48b7b11776c0' : (2=7))
 Call:remove_all(2, [2], _5200)
 Call:remove_all(2, [], _5200)
 Exit:remove_all(2, [], [])
 Exit:remove_all(2, [2], [])
 Exit:remove_all(2, [7, 2], [7])
 Exit:remove_all(2, [2, 7, 2], [7])
 Exit:remove_all(2, [5, 2, 7, 2], [5, 7])
 Exit:remove_all(2, [3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [2, 3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [4, 2, 3, 5, 2, 7, 2], [4, 3, 5, 7])
 Exit:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], [1, 4, 3, 5, 7])
X = [1, 4, 3, 5, 7]

Что я не могу понять, так этокак происходит откат в этих строках кода

 Exit:remove_all(2, [], [])
 Exit:remove_all(2, [2], [])
 Exit:remove_all(2, [7, 2], [7])
 Exit:remove_all(2, [2, 7, 2], [7])
 Exit:remove_all(2, [5, 2, 7, 2], [5, 7])
 Exit:remove_all(2, [3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [2, 3, 5, 2, 7, 2], [3, 5, 7])
 Exit:remove_all(2, [4, 2, 3, 5, 2, 7, 2], [4, 3, 5, 7])
 Exit:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], [1, 4, 3, 5, 7])

Как интерпретатор Prolog выполняет рекурсию по этому вопросу? Могут ли некоторые объяснить, пожалуйста.

Answer 1

Проблема обратного отслеживания не относится к этому примеру.

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

Когда вызывается функция 'a', а 'a', в свою очередь, вызывает функцию 'b': пока внутри'b' и 'b' и 'a' находятся в стеке;когда 'b' завершается, только' a 'находится в стеке;когда 'a' ничего не завершает, в стеке ничего нет.

Когда вызывается функция 'a', а 'a', в свою очередь, вызывает функцию 'b' и 'b' inturn вызывает функцию 'c': пока в 'a' находится только 'a' в стеке: в то время как в 'b' оба 'b' и 'a' находятся в стеке: покавнутри 'c' allof 'c' и 'b' и 'a' находятся в стеке;когда 'c' завершается, оба' b и 'a' находятся в стеке;когда 'b' завершает только' a 'в стеке;когда 'a' ничего не завершает, в стеке ничего нет.

То же самое происходит, если 'a' вместо вызова 'b' вызывает себя рекурсивно.

Когда функция' a(1)'вызывается, и' a(1) ', в свою очередь, вызывает функцию' a(2) ', а 'a(2)', в свою очередь, вызывает функцию 'a(3)': в то время как внутри' a(1) 'в стеке находится только' a(1) ':в то время как в 'a(2)' в стеке находятся и 'a(2)', и 'a(1)', а в 'a(3)' allof 'a(3)' и 'a(2)' и 'a(1)'в стеке;когда 'a(3)' завершается, оба' a(2) и 'a(1)' находятся в стеке;когда 'a(3)' завершает только' a(1) 'в стеке;когда 'a (1) `' ничего не завершает, стека нет.

Функция в этом примере вызывает себя рекурсивно, таким образом, она создает стек. Каждый раз, когда он называет себя, глубина стека увеличивается. Так как каждый раз, когда он вызывает себя, в списке появляется на один элемент меньше, и он перестает вызывать себя, когда в списке 0 элементов, из этого следует, что функция установит глубину стека вызовов функции, равную по размеру размеру исходного списка. Когда функция наконец вызывается со списком размера 0, она больше не вызывает себя рекурсивно;поэтому он возвращает, таким образом, стек уменьшается на 1, теперь возвращается вызов функции, у которого был список размера 1, таким образом, стек уменьшается на 1, теперь вызов функции, у которого был список размера 2, возвращает, таким образом, стек уменьшается на 1, теперь вызов функцииу которого был список возвратов размера 3, таким образом, стек уменьшается на 1, ... и т. д.

С этим объяснением, возможно, будет полезно следующее форматирование выходных данных отладки.

        Call:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], _4896)
            Call:remove_all(2, [4, 2, 3, 5, 2, 7, 2], _5128)
                Call:remove_all(2, [2, 3, 5, 2, 7, 2], _5146)
                    Call:remove_all(2, [3, 5, 2, 7, 2], _5146)
                        Call:remove_all(2, [5, 2, 7, 2], _5164)
                            Call:remove_all(2, [2, 7, 2], _5182)
                                Call:remove_all(2, [7, 2], _5182)
                                    Call:remove_all(2, [2], _5200)
                                        Call:remove_all(2, [], _5200)
                                        Exit:remove_all(2, [], [])
                                    Exit:remove_all(2, [2], [])
                                Exit:remove_all(2, [7, 2], [7])
                            Exit:remove_all(2, [2, 7, 2], [7])
                        Exit:remove_all(2, [5, 2, 7, 2], [5, 7])
                    Exit:remove_all(2, [3, 5, 2, 7, 2], [3, 5, 7])
                Exit:remove_all(2, [2, 3, 5, 2, 7, 2], [3, 5, 7])
            Exit:remove_all(2, [4, 2, 3, 5, 2, 7, 2], [4, 3, 5, 7])
        Exit:remove_all(2, [1, 4, 2, 3, 5, 2, 7, 2], [1, 4, 3, 5, 7])

* 1068 пятьдесят шестой *