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

Я изучаю Пролог в моей Лаборатории искусственного интеллекта, из источника Learn Prolog Now!,

В 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 ответа

Решение

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

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

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).

Источник

TL; DR: да, они есть.

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

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

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

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

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

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

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

смотрите также:

Вы спросите, каковы практические последствия всего этого? Представьте, что наш друг, математик- маг, должен варить яйца. У него есть горшок; кран; горячая тарелка; и немного яиц. Что ему делать?

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

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

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

Источник

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

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

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

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

Используя аккумулятор:

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

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

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

Алгоритмы поиска, которым необходимо знать "путь до сих пор" (или любой алгоритм, который должен иметь состояние), используют более общую форму той же техники, предоставляя "промежуточный результат" для рекурсивного вызова. Например, кодер длины прогона может быть определен как:

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)
    ).

Надеюсь, это поможет.

Источник
Другие вопросы по тегам