Перевод в DCG Semicontext не работает
Поскольку этот вопрос использует список, я хотел решить его с помощью DCG. В процессе я понял, что можно использовать полуконтекст. ( DCG Primer)
Первоначальная проблема состоит в том, чтобы вернуть количество элементов в списке, но если два идентичных элемента расположены рядом друг с другом, не увеличивайте количество.
Хотя мой код работает для некоторых тестовых случаев, он не работает для других. Это всего лишь один пункт, который терпит неудачу. При просмотре кода с помощью отладчика выясняется, что вторая переменная состояния, возвращаемый список, связана с вызовом предложения, когда я думаю, что она должна быть не связана. РЕДАКТИРОВАТЬ Решена эта часть проблемы ниже.
Я использую SWI-Prolog 8.0.
Пункт, вызывающий проблему:
count_dcg(N0,N),[C2] -->
[C1,C2],
{ N is N0 + 1 }.
Примечание: C1 помечен как Singleton variables: [C1]
Обычно я бы поменял C1 в _ но в этом случае мне нужно указать, что первый и второй элементы, обрабатываемые в данный момент, различны. Другими словами, он использует провал объединения в качестве охранника.
Глядя на DCG с помощью листинга / 1 показывает использование _ что может быть проблемой, но не уверен.
count_dcg(C, B, A, E) :-
A=[_, F|D],
B is C+1,
G=D,
E=[F|G].
Как правильно решить проблему с помощью DCG?
Смотрите следующий вопрос.
Текущий исходный код
% empty list
% No semicontext (push back) needed because last item in list.
count_dcg(N,N) --> [].
% single item in list
% No semicontext (push back) needed because only one item removed from list.
count_dcg(N0,N) -->
[_],
\+ [_],
{ N is N0 + 1 }.
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N,N),[C] -->
[C,C].
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C2] -->
[C1,C2],
{ N is N0 + 1 }.
count(L,N) :-
DCG = count_dcg(0,N),
phrase(DCG,L).
Контрольные примеры
:- begin_tests(count).
test(1,[nondet]) :-
count([],N),
assertion( N == 0 ).
test(2,[nondet]) :-
count([a],N),
assertion( N == 1 ).
test(3,[nondet]) :-
count([a,a],N),
assertion( N == 1 ).
test(4,[nondet]) :-
count([a,b],N),
assertion( N == 2 ).
test(5,[nondet]) :-
count([b,a],N),
assertion( N == 2 ).
test(6,[nondet]) :-
count([a,a,b],N),
assertion( N == 2 ).
test(7,[nondet]) :-
count([a,b,a],N),
assertion( N == 3 ).
test(8,[nondet]) :-
count([b,a,a],N),
assertion( N == 2 ).
:- end_tests(count).
Выполнение теста
?- run_tests.
% PL-Unit: count ..
ERROR: c:/question_110.pl:80:
test 3: failed
ERROR: c:/question_110.pl:84:
test 4: failed
ERROR: c:/question_110.pl:88:
test 5: failed
ERROR: c:/question_110.pl:92:
test 6: failed
ERROR: c:/question_110.pl:96:
test 7: failed
ERROR: c:/question_110.pl:100:
test 8: failed
done
% 6 tests failed
% 2 tests passed
false.
РЕДАКТИРОВАТЬ 1
Понял, что нужен хвостовой вызов для двух предикатов
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C] -->
[C,C],
count_dcg(N0,N).
% Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C2] -->
[C1,C2],
{
C1 \== C2,
N1 is N0 + 1
},
count_dcg(N1,N).
Код все еще не работает, но это объясняет, почему переменная состояния была связана, когда я ожидал, что она не будет связана.
РЕДАКТИРОВАТЬ 2
Хотя я и не использовал полуконтекст DCG, как я надеялся, используя вариант полуконтекста в качестве заглядывания, код работает. Не публиковать это как ответ, потому что я хотел бы, чтобы ответ либо показывал код DCG, работающий с полуконтекстом в заголовке предложения, либо объяснял, почему это неправильно.
lookahead(C),[C] -->
[C].
% empty list
% No lookahead needed because last item in list.
count_3_dcg(N,N) --> [].
% single item in list
% No lookahead needed because only one in list.
count_3_dcg(N0,N) -->
[_],
\+ [_],
{ N is N0 + 1 }.
% Lookahead needed because two items in list and
% only want to remove first item.
count_3_dcg(N0,N) -->
[C1],
lookahead(C2),
{ C1 == C2 },
count_3_dcg(N0,N).
% Lookahead needed because two items in list and
% only want to remove first item.
count_3_dcg(N0,N) -->
[C1],
lookahead(C2),
{
C1 \== C2,
N1 is N0 + 1
},
count_3_dcg(N1,N).
count(L,N) :-
DCG = count_3_dcg(0,N),
phrase(DCG,L).
Выполнение теста
?- run_tests.
% PL-Unit: count ........ done
% All 8 tests passed
true.
2 ответа
Альтернативное решение, которое не требует откатов назад или упреждения:
count_dcg(N0,N) -->
[C], {N1 is N0 + 1}, count_dcg(N1,N,C).
count_dcg(N,N) -->
[].
count_dcg(N0,N,C) -->
[C],
count_dcg(N0,N,C).
count_dcg(N0,N,C) -->
[C1],
{C \== C1, N1 is N0 + 1},
count_dcg(N1,N,C1).
count_dcg(N,N,_) -->
[].
count(L,N) :-
phrase(count_dcg(0,N),L).
Я считаю, что проблема в вашем коде здесь:
> % Semicontext (push back) needed because two items removed from list.
% Need second item to stay on list.
count_dcg(N0,N),[C] -->
[C,C],
count_dcg(N0,N).
заключается в том, что возврат происходит после завершения тела, поэтому рекурсивныйcount_dcgникогда не видит[C]отпор, потому что этого еще не произошло.
Чтобы обойти эту проблему, дедуплицируйте заголовок списка, используя полуконтекстную обратную отправку. Поскольку тело должно завершиться до того, как произойдет возврат, мы не можем иметь рекурсивный вызов self и должны иметь переход между двумя правилами с разными именами:
% dedupe squashes head repeatedly, then stops.
dedupe --> ((squash, dedupe) | stop), !.
% removes duplicate from list head.
squash, [A] --> [A, A].
% stop when head is not a duplicate, or one item remains.
stop, [A, B] --> [A, B], { dif(A, B) }.
stop, [A] --> [A].
% e.g. (NB. this uses phrase/3 and pushback leaves
% the list-to-be-counted in Rest)
?- phrase(dedupe, [1,1,1,1,2,3], Rest).
Rest = [1, 2, 3]
Затем простой рекурсивный счетчик DCG, который удаляет один элемент из списка и увеличивает его, считая от 0 в пустом списке:
count(C) --> [_], count(B), { succ(B, C) }, !.
count(0) --> [].
% e.g.
?- phrase(count(C), [a,b,c,d])
C = 4
Затем объедините их, изменив первое правило подсчета на дедупликацию головы, посчитайте один и повторите:
count(C) --> dedupe, [_], count(B), { succ(B, C) }, !.
например, подсчитать уникальные числа:
?- phrase(count(C), [1,1,1,2,3,3]).
C = 3