Пролог - что вызывает ошибку локального стека в этом случае?

Question

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

Код не идеален, так как я просто сначала пытаюсь познакомиться с языком, поэтому он неэффективен, но мой вопрос в том, где находится бесконечный l oop или что-то подобное, скрывающееся.

Только последнее правило вызывает эту проблему, я проверял предыдущие, и они работали нормально.

:- use_module(library(clpfd)).

% Stuff

max(X,Y,X):- X#>=Y.
max(X,Y,Y):- Y#>X.

sub(X,Y,Z):- Z is X-Y.

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).

% Checking "tree-ness" of a term
% is_tree(Tree)

is_tree(tree(_,Left,Right)) :-
   Left=nil, Right=nil;
   Left=nil, is_tree(Right);
   Right=nil, is_tree(Left);
   is_tree(Left), is_tree(Right).

% Computing tree height
% tree_height(Tree, Height)

tree_height(nil,0).
tree_height(tree(_,L,R),H) :-
   tree_height(L,H1),
   tree_height(R,H2),
   H1#>=H2,
   H is H1+1.
tree_height(tree(_,L,R),H) :-
   tree_height(L,H1),
   tree_height(R,H2),
   H2#>H1,
   H is H2+1.

% Checking "AVL tree-ness" of a term
% is_avl_tree(Tree, Height)

is_avl_tree_help(nil,0).
is_avl_tree_help(tree(_,L,R),H) :-
    is_avl_tree_help(L,H1),
    is_avl_tree_help(R,H2),
    sub(H1,H2,D),
    D in -1 .. 1,
    max(H1,H2,H3),
    H is H3+1.    

is_avl_tree(Tree,H) :-
    is_tree(Tree),
    is_avl_tree_help(Tree,H).

% Define relation between a Tree and a List

tree_elements_help(nil,[]).
tree_elements_help(tree(X,Le,Ri),L) :-
    tree_elements_help(Le,L1),
    tree_elements_help(Ri,L2),
    append(L1,[X|L2],L).

tree_elements(Tree,L) :- 
    is_tree(Tree),
    tree_elements_help(Tree,L).

avl_tree_planter(Tree,L) :-
    is_avl_tree(Tree,H),
    tree_elements(Tree,L2),
    permutation(L2,L).

Answer 1

Проблема в том, что такие предикаты, как tree_elements/2 и avl_tree_planter/2, необратимы. Я предполагаю, что вы заметили проблему после вызова avl_tree_planter/2 с первым необоснованным аргументом. Например, следующие запросы не завершаются:

?- tree_elements(Tree,[]).
?- avl_tree_planter(Tree,[]).

Я остановлюсь на более простом случае написания обратимого предиката inorder/2, который генерирует каждое двоичное дерево, имеющее заданный обход обхода. Следующая реализация не завершается, когда ее первый аргумент необоснован:

inorder(leaf,[]).
inorder(node(X,L,R),L3) :-
    inorder(L,L1),
    inorder(R,L2),
    append(L1,[X|L2],L3).

Если вы проследите запрос ?- inorder(Tree,[]), вы обнаружите, что первый рекурсивный вызов inorder/2 вызывает проблему. Чтобы доказать inorder(Tree,[]), необходимо доказать бесконечно много целей вида inorder(X,[]). Как правило, первый рекурсивный вызов inorder/2 предотвращает создание левого поддерева. Это аналогично проблеме левой рекурсии при разборе.

Вот одно из решений. Введем два аргумента, которые отслеживают состояние обхода. Первый аргумент представляет состояние ввода и отслеживает необработанные элементы. Второй представляет состояние вывода и отслеживает остальные элементы. Их разница соответствует элементам, обработанным во время рекурсивного вызова. Отсюда следует, что inorder(Tree,List) должен быть успешным с состоянием ввода List и состоянием вывода []. Вот одна из возможных реализаций:

inorder(Tree,List) :-
    inorder(Tree,List,List,[]).

inorder(leaf,[],State,State).
inorder(node(X,L,R),List,[_|State1],State3) :-
    inorder(L,Left,State1,State2),
    inorder(R,Right,State2,State3),
    append(Left,[X|Right],List).

Например:

?- inorder(leaf,List).
List = [].

?- inorder(node(1,leaf,leaf),List).
List = [1].

?- inorder(node(1,node(2,leaf,leaf),leaf),List).
List = [2, 1].

?- findall(Tree,inorder(Tree,[]),Trees).
Trees = [leaf].

?- findall(Tree,inorder(Tree,[1]),Trees).
Trees = [node(1, leaf, leaf)].

?- findall(Tree,inorder(Tree,[1,2]),Trees).
Trees = [node(1, leaf, node(2, leaf, leaf)), node(2, node(1, leaf, leaf), leaf)].

Если эта реализация напоминает вам о разборе, то это потому, что она реализует примерно те же функции, что и следующая определенная пункт грамматики (DCG). Следующий код и обсуждение взаимосвязи между недерминированием и левой рекурсией можно найти в учебнике Маркуса Триски DCG , который я предлагаю прочитать. Использование DCG для обработки списка считается идиоматическим c Пролог.

:- use_module(library(dcg/basics)).

inorder(Tree,List) :-
    phrase(inorder(Tree,List,_),List).

inorder(leaf,S,S) -->
    [].
inorder(node(X,L,R),[_|S1],S3) -->
    inorder(L,S1,S2),
    [X],
    inorder(R,S2,S3).

Как решить вашу исходную проблему? Чтобы адаптировать эти методы к настройке деревьев AVL, необходимо наложить дополнительные ограничения на генерируемые деревья (т. Е. Выполнить только двоичные деревья поиска, удовлетворяющие свойству AVL). Это не должно быть сложно. Я надеюсь, что вы нашли это объяснение полезным.