Стоит ли избегать хвостовой рекурсии в Прологе и вообще?

Question

Я работаю над онлайн-книгой "Learn Prolog now" для удовольствия.

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

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

Но я читал, что этот тип рекурсии лучше избегать по соображениям производительности. Это правда? Считается ли "хорошей практикой" всегда использовать хвостовую рекурсию? Будет ли стоить усилий использовать аккумуляторы, чтобы получить хорошую привычку?

Я попытался изменить этот пример на использование аккумуляторов, но он переворачивает список. Как я могу избежать этого?

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).

Answer 1

Короткий ответ: рекурсия хвоста желательна, но не переоценивайте ее.

Ваша оригинальная программа настолько хвостовая рекурсивная, насколько вы можете получить в Прологе. Но есть более важные вопросы: правильность и прекращение.

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

Но у вашей попытки оптимизации есть какой-то смысл. По крайней мере, с исторической точки зрения.

Еще в 1970-х годах основным языком искусственного интеллекта был LISP. И соответствующее определение было бы

(Определить аддон (хз)
  (cond ((ноль хз) ноль)
    (т (минусы (+ 1 (автомобиль хз))
         (addone (cdr xs))))))

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

В Prolog, однако, вы можете создать минусы до знания фактических значений, благодаря логическим переменным. Так много программ, которые не были хвостово-рекурсивными в LISP, переведены в хвост-рекурсивные программы в Прологе.

Последствия этого все еще можно найти во многих учебниках Пролога.

Answer 2

Ваша процедура addOne уже является хвостовой рекурсивной.

Не существует точек выбора между головой и последним рекурсивным вызовом, потому что is/2 является детерминированным.

Аккумуляторы иногда добавляются, чтобы разрешить хвостовую рекурсию, более простой пример, который я могу придумать, это reverse/2. Вот наивный реверс (nreverse/2), не хвостовой рекурсив

nreverse([], []).
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R).

если мы добавим аккумулятор

reverse(L, R) :- reverse(L, [], R).
reverse([], R, R).
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R).

теперь reverse/3 является хвостовой рекурсией: рекурсивный вызов является последним, и точка выбора не остается.

Answer 3

ОП сказал:

Но я читал, что лучше избегать [хвостовой] рекурсии по соображениям производительности. Это правда? Считается ли "хорошей практикой" всегда использовать хвостовую рекурсию? Будет ли стоить усилий использовать аккумуляторы, чтобы получить хорошую привычку?

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

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

Возможные недостатки?

• потеря полезной трассировки стека. Не проблема, если TRO применяется только в выпуске / оптимизированной сборке, а не в отладочной сборке, но...
• разработчики напишут код, который зависит от TRO, а это означает, что код будет работать нормально с применением TRO, не будет работать без применения TRO. Это означает, что в вышеприведенном случае (TRO только в выпусках / оптимизированных сборках) существует функциональное изменение между выпусками сборки и отладки, по сути это означает, что выбор параметров компилятора генерирует две разные программы из идентичного исходного кода.

Это, конечно, не проблема, когда языковой стандарт требует оптимизации хвостовой рекурсии.

Цитировать Википедию:

Хвостовые вызовы важны, потому что они могут быть реализованы без добавления нового фрейма стека в стек вызовов. Большая часть кадра текущей процедуры больше не нужна, и ее можно заменить на кадр хвостового вызова, измененный соответствующим образом (аналогично наложению для процессов, но для вызовов функций). Затем программа может перейти к вызываемой подпрограмме. Создание такого кода вместо стандартной последовательности вызовов называется устранением хвостовых вызовов или оптимизацией хвостовых вызовов.

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

• Что такое оптимизация вызовов?
• Портлендский репозиторий по этому вопросу
• и даже MSDN от Microsoft

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

Answer 4

Я не думаю, что первая версия addone должно привести к менее эффективному коду. Это также намного более читабельно, поэтому я не вижу причин, по которым следует избегать этого.

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

Итак, как вы можете реализовать работающую хвостовую рекурсивную версию addone? Это может быть обманом, но при условии, что reverse реализуется с помощью хвостовой рекурсии (например, см. здесь), затем ее можно использовать для решения вашей проблемы:

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],Acc,Result) :- reverse(Acc, Result).
addone(List,Result) :- accAddOne(List,[],Result).

Это очень неуклюжий, хотя.:-)

Кстати, я не могу найти более простое решение. Может по той же причине, что и foldr в Haskell обычно не определяется с хвостовой рекурсией.

Answer 5

В отличие от некоторых других языков программирования, некоторые реализации Prolog хорошо подходят для хвостовых рекурсивных программ. Рекурсию хвоста можно рассматривать как частный случай оптимизации последнего вызова (LCO). Например, здесь в Java не работает:

public static boolean count(int n) {
    if (n == 0) {
        return true;
    } else {
        return count(n-1);
    }
}

public static void main(String[] args) {
    System.out.println("count(1000)="+count(1000));
    System.out.println("count(1000000)="+count(1000000));
}

Результат будет:

count(1000)=true
Exception in thread "main" java.lang.StackruError
    at protect.Count.count(Count.java:9)
    at protect.Count.count(Count.java:9)

С другой стороны, у основных реализаций Prolog с этим нет проблем:

 ?- [user].
 count(0) :- !.
 count(N) :- M is N-1, count(M).
 ^D

Результат будет:

?- count(1000).
true.
?- count(1000000).
true.

Причина, по которой системы Prolog могут это делать, заключается в том, что их выполнение в любом случае чаще всего выполняется в стиле трамплина, и тогда оптимизация последнего вызова является вопросом исключения точки выбора и обрезки среды. Обрезка среды уже была задокументирована в ранних версиях WAM.

Но да, отладка может быть проблемой.