Аккумуляторы Пролога. Действительно ли это "другая" концепция?

Я изучаю пролог в своей лаборатории искусственного интеллекта, из источника изучайте Пролог сейчас!.

В 5-й главе мы познакомимся с аккумуляторами . И в качестве примера приведены эти два фрагмента кода. Чтобы найти длину списка

без аккумуляторов : 

len([],0).
len([_|T],N) :- len(T,X), N is X+1.

с аккумуляторами : 

accLen([_|T],A,L) :- Anew is A+1, accLen(T,Anew,L).
accLen([],A,A).

Я не могу понять, как эти два фрагмента концептуально различаются? Что именно Ан аккумулятор делает по-другому? И в чем же выгода?

Аккумуляторы звучат какпромежуточные переменные . (Поправьте меня, если я ошибаюсь.) И я уже использовал их в своих программах до сих пор, так что это действительно такая большая концепция?

3 9
recursion tail-recursion prolog

3 ответа:

Аккумуляторыявляются промежуточными переменными, аявляются важной (читайосновной ) темой в прологе, поскольку позволяют реверсировать информационный поток некоторого фундаментального алгоритма, с важными последствиями дляэффективности программы.

Возьмем в качестве примера реверсирование списка 

nrev([],[]).
nrev([H|T], R) :- nrev(T, S), append(S, [H], R).

rev(L, R) :- rev(L, [], R).
rev([], R, R).
rev([H|T], C, R) :- rev(T, [H|C], R).

Nrev/2 (наивный реверс) - Это O(N^2), где N-длина списка, а rev/2-O(N).

7

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

На практике, проходя через список без аккумулятора: 

foo([]).
foo([H|T]) :-
    foo(T).

Глава списка остается позади и не может быть доступна с помощью рекурсивного вызова. На каждом уровне рекурсии вы видите только то, что осталось от списка.

Использование аккумулятора: 

bar([], _Acc).
bar([H|T], Acc) :-
    bar(T, [H|Acc]).

На каждом рекурсивном шаге у вас есть оставшийся список и всех элементов, которые вы прошли. В вашем примере len/3 Вы сохраняете только количество, а не фактические элементы, так как это все, что вам нужно.

Некоторые предикаты (например, len/3) можно сделать хвостовыми рекурсивными с накопителями: вам не нужно ждать окончания ввода (исчерпать все элементы списка), чтобы выполнить фактическую работу, вместо этого делайте это постепенно, по мере получения входных данных. Prolog не должен оставлять значения в стеке и может выполнить оптимизацию хвостового вызова для вас.

Алгоритмы поиска, которые должны знать " путь до сих пор "(или любой алгоритм, который должен иметь состояние), используют более общую форму того же метода, предоставляя" промежуточный результат " рекурсивному вызову. Кодер длины выполнения, например, может быть определен следующим образом: 
rle([], []).
rle([First|Rest],Encoded):- 
    rle_1(Rest, First, 1, Encoded).               

rle_1([], Last, N, [Last-N]).
rle_1([H|T], Prev, N, Encoded) :-
    (   dif(H, Prev) 
    ->  Encoded = [Prev-N|Rest],
        rle_1(T, H, 1, Rest)
    ;   succ(N, N1),
        rle_1(T, H, N1, Encoded)
    ).
Надеюсь, это поможет.
11

TL; DR: Да, это так.

Представьте, что вы идете из города A слева в город B справа, и вы хотите заранее знать расстояние между ними. Как вы этого достигнете?

A математик в такой позиции используется магия известная как структурная рекурсия. Он говорит себе: а что, если я пошлю свою копию еще на шаг ближе к городу Б , и спросите его Оего расстоянии до города? Затем я добавлю 1 к его результату, после того, как получив его из моего экземпляра, так как я послал его на один Шаг ближе к городу, и вы узнаете мой ответ, не сдвинувшись ни на дюйм! Конечно, если я уже у городских ворот, я не буду посылать свои копии никуда, так как я буду знать, что расстояние равно 0 - не сдвинувшись ни на дюйм!

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

И вот теперь, узнав заранее свой ответ, наш осторожный маг-математик готов взяться за свой сейф (сейчас!) путешествие.

Но это, конечно, не было магией вообще - это все было грязным трюком! Он не нашел ответа заранее из воздуха - он разослал всю стопку других, чтобы найти его для него. В конце концов, эту изнурительную работу надо было сделать, он просто делал вид, что не замечает ее. Расстояние было путешествовал. Кроме того, расстояние назад также должно было быть пройдено, чтобы каждая копия сообщала свой результат своему хозяину, причем результат фактически создавался по пути назад из пункта назначения. И все это еще до того, как наш фальшивый волшебник начал ходить сам. Как это , что для командной работы. Для него это может показаться сладкой сделкой. Но в целом...

Так вот как думает математик-маг . Но его двойной отважный путешественник просто отправляется в путешествие и считает свои шаги по пути, добавляя 1 к текущему счетчику шагов на каждом шаге, раньше остальная часть его настоящего путешествия. Больше нет никакого притворства. Путешествие может быть конечным, А может быть и бесконечным - он не может знать заранее. Но в каждой точке своего маршрута, а следовательно, когда он прибудет в город B ворот тоже, он будет знать свое расстояние, пройденное до сих пор. И ему, конечно, не придется возвращаться к началу пути, чтобы сказать себе результат.

И в этом разница между структурной рекурсией первой и хвостовая рекурсия с накопителем ⁄ хвостовая рекурсия по модулю минусы ⁄ corecursion нанятый вторым. Познание первого строится на обратном пути от цели; второго - на пути вперед с самого начала, к цели.

См. также:

Каковы практические последствия всего этого, спросите вы? Почему, представьте себе, наш друг маг математику необходимо отварить несколько яиц. У него есть кастрюля, кран, плита и несколько яиц. Что же ему делать?

Ну, это просто - он просто ... положите яйца в кастрюлю, добавьте в нее немного воды из крана и поставьте на горячую плиту.

А что, если ему уже дали горшок с яйцами и водой? Да ведь ему даже легче - он просто вынет яйца, выльет воду и окажется перед проблемой, которую уже знает, как решить! Чистая магия , не так ли?

Прежде чем мы смеемся над беднягой, мы не должны забывать Сказка о сороконожке. Иногда невежество - это блаженство. Но когда требуемое знание просто и "одномерно", как расстояние здесь, было бы преступлением притворяться, что у него вообще нет памяти.

10