Ошибка «Out of stack» в простом предикате Prolog

Question

Я занимаюсь прологом. Функция, которую я пытаюсь написать - это compose (L1, L2, L3). Он состоит из элементов L1 и L2, чередующихся по порядку, пока один из них не станет равным nil, а затем добавляет этот ненулевой список в конце. Функция отлично работает, когда ей задаются L1 и L2 в качестве входных данных (то есть она выводит правильный L3), но я сталкиваюсь с ошибкой «out of stack», когда я вводю L3 и пытаюсь получить все логически возможные входы L1 и L2,Например, для следующего кода функции,

compose([],[],[]).
compose(L1,[],L3):-
    append(L1,[],L3).
compose([],L2,L3):-
    append([],L2,L3).
compose([H1|T1],[H2|T2],L3):-
    compose(T1,T2,Tail),
    append([H1],[H2],Head), 
    append(Head,Tail,L3).

?-compose(L1,L2,[a,b,c]).

даст мне ошибку вне стека. Как мне решить эту проблему?

Answer 1

Как мне решить эту проблему?

Сначала попытайтесь понять, почему ваш запрос не заканчивается. Вы можете попытаться представить, как протекает Пролог, но имейте в виду, это может быть довольно сложно. В конце концов, Prolog объединяет два потока управления (AND- и OR-control), плюс имеет частично неизвестные данные, которых нет в более традиционных языках (OO и FP). По этой причине я предпочитаю не подражать Прологу, вместо этого я позволю Прологу помочь мне локализовать ошибку. С этой целью я добавляю в вашу программу как можно больше целей false, чтобы запрос по-прежнему не завершался. Вот максимум, называемый fault-slice :

<s>compose([],[],[]) :- <b>false</b></s>.
<s>compose(L1,[],L3):- <b>false</b></s>,
    <s>append(L1,[],L3)</s>.
<s>compose([],L2,L3):- <b>false</b></s>,
    <s>append([],L2,L3)</s>.
compose([H1|T1],[H2|T2],L3):-
    compose(T1,T2,Tail), <b>false</b>,
    <s>append([H1],[H2],Head)</s>,
    <s>append(Head,Tail,L3)</s>.

?- compose(L1, L2, [a,b,c]), <b>false</b>.

Мы можем пропустить ваши первые пункты. Интересна только первая цель последнего правила! Так что не более чем:

compose([H1|T1],[H2|T2],L3):-
    compose(T1,T2,Tail), <b>false</b>,
    ... .

?- compose(L1, L2, [a,b,c]), <b>false</b>.

В этой крошечной маленькой программе третий аргумент compose/3 полностью игнорируется. Никто не хочет L3. И, таким образом, L3 не влияет на завершение. Чтобы это закончилось, нам нужно как-то ограничить L3 до цели. другой ответ показывает, как это сделать.

(Этот метод работает для любой проблемы без прерывания в чистой программе Prolog, подробнее см. fail-slice .)

Answer 2

Сначала перепишите его как более простой, но полностью эквивалентный

compose([],[],[]).                       % some redundancy here
compose(L1,[],L1).
compose([],L2,L2). /*
compose([H1|T1],[H2|T2],L3):-            % whole solution
    compose(T1,T2,Tail),
    Head = [H1,H2],
    L3 = [Head|Tail]. */

, который теперь проясняет проблему с рекурсией, first , вычисляющий остальную часть результата (Tail), и только затем завершая его (как L3).

Вместо этого поверните его,

compose([H1|T1],[H2|T2],[H1,H2|Tail]):-   % single step
    compose(T1,T2,Tail).

, чтобы теперь у нас была co -рекурсия, и при этом продуктивная. Сначала он создает (гарантированно конечную) начальную часть результата, а затем заполняет недостающие фрагменты.

(В приведенном выше примере «создает» можно взаимозаменять с «потребляет», как и в случае двунаправленности). Пролог. Будучи одностадийным , ему все равно, какие аргументы используются, а какие приводятся).

Answer 3

Ошибка «Out of global stack» обычно означает, что ваша рекурсия застряла в бесконечном цикле и, таким образом, продолжает вызывать предикат до тех пор, пока стек не будет исчерпан. Цикл вызван тем, что он сначала выдаст результаты:

?- compose(L1,L2,[a,b,c]).
L1 = [a, b, c],
L2 = [] ;
L1 = [],
L2 = [a, b, c] ;
L1 = [a, c],
L2 = [b] ;

Но тогда он будет искать другие решения. Он делает это, основываясь на вашей программе, каждый раз объединяя первый элемент с [H1|T1], а второй с [H2|T2]. Затем вы немедленно делаете рекурсивный вызов, поэтому Пролог не может проверить, действительно ли H1 и H2 являются первыми двумя элементами в третьем параметре.

Однако нам не нужны все эти append/3звонки и т. д. в первую очередь. Мы можем выполнить простую унификацию параметров:

compose([],L2,L2).
compose(L1,[],L1).
compose([H1|T1],[H2|T2],[H1, H2|T3]) :-
    compose(T1,T2,T3).

Для данного запроса это закончится после предложенного решения:

?- compose(L1,L2,[a,b,c]).
L1 = [],
L2 = [a, b, c] ;
L1 = [a, b, c],
L2 = [] ;
L1 = [a],
L2 = [b, c] ;
L1 = [a, c],
L2 = [b] ;
false.

Действительно, так как из-за рекурсии, в конце концов, третийПараметр будет пустым списком и, следовательно, не сможет объединиться со списком [H1, H2|T3].