Есть ли в Haskell хвостовая рекурсивная оптимизация?

90

Сегодня я обнаружил команду time в unix и подумал, что буду использовать ее, чтобы проверить разницу во времени выполнения между хвостовой рекурсивной и нормальной рекурсивной функцией в Haskell.

Я написал следующие функции:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

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

Однако после написания основного метода для каждого из них, их компиляции и запуска с помощью команды «time» оба они имели одинаковое время выполнения с нормальной рекурсивной функцией, вытесняющей хвостовую рекурсивную. Это противоречит тому, что я слышал относительно хвостовой рекурсивной оптимизации в lisp. В чем причина этого?

мошенник Haskell
источник
8
Я считаю, что совокупная стоимость владения - это оптимизация для экономии стека вызовов, это не означает, что вы сэкономите время процессора. Поправьте меня, если не прав.
Джером
3
Я не тестировал его с помощью lisp, но в учебнике, который я прочитал, подразумевается, что настройка стека сама по себе требует больших затрат процессора, тогда как решение, скомпилированное в итеративную хвостовую рекурсию, не затрачивает на это энергии (времени) и, следовательно, был более эффективным.
haskell rascal
1
@Jerome: Ну, это зависит от многих вещей, но обычно в игру вступают и кеши, так что TCO обычно производит и более быструю программу ..
Кристофер Мичински
В чем причина этого? Одним словом: лень.
Дэн Бертон,
Интересно, что вы facболее или менее знакомы product [n,n-1..1]с тем, как ghc вычисляет с помощью вспомогательной функции prod, но, конечно, это product [1..n]было бы проще. Я могу только предположить, что они не сделали его строгим во втором аргументе на том основании, что ghc очень уверен в том, что это именно то, что может скомпилировать до простого аккумулятора.
AndrewC

Ответы:

171

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

Давайте посмотрим, как мы оцениваем facSlow 5в качестве примера:

facSlow 5
5 * facSlow 4            -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3)       -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2))  -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Итак, как вы и беспокоились, у нас есть накопление чисел до того, как произойдут какие-либо вычисления, но, в отличие от вас, нет стека facSlowвызовов функций, которые ждут завершения - каждое сокращение применяется и исчезает, оставляя фрейм стека в своем wake (это потому, что (*)является строгим и поэтому запускает оценку его второго аргумента).

Рекурсивные функции Haskell не вычисляются очень рекурсивно! Единственная куча вызовов - это сами умножения. Если (*)рассматриваются как строго конструктора данных, это то , что известно как охраняемая рекурсия (хотя обычно называют такие с не конструкторами данных -strict, где то , что осталось на своем пути являются конструкторы данных - при вынужденном пути дальнейшего доступа).

Теперь посмотрим на хвостовую рекурсию fac 5:

fac 5
fac' 5 1
fac' 4 {5*1}       -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}}    -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}}        -- the thunk "{...}" 
(2*{3*{4*{5*1}}})        -- is retraced 
(2*(3*{4*{5*1}}))        -- to create
(2*(3*(4*{5*1})))        -- the computation
(2*(3*(4*(5*1))))        -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120

Итак, вы можете видеть, что хвостовая рекурсия сама по себе не сэкономила вам ни времени, ни места. Он не только выполняет больше шагов в целом facSlow 5, но и создает вложенный преобразователь (показан здесь как {...}) - для которого требуется дополнительное пространство, - который описывает будущие вычисления и выполняемые вложенные умножения.

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

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

facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
    facS' 1 y = y
    facS' x y = facS' (x-1) $! (x*y) 

Это заставляет facS'быть строгим во втором аргументе. (Он уже строг в своем первом аргументе, потому что его нужно оценить, чтобы решить, какое определение facS'применить.)

Иногда строгость может очень помочь, иногда это большая ошибка, потому что лень эффективнее. Вот это хорошая идея:

facSlim 5
facS' 5 1
facS' 4 5 
facS' 3 20
facS' 2 60
facS' 1 120
120

Думаю, именно этого вы и хотели достичь.

Резюме

  • Если вы хотите оптимизировать свой код, первый шаг - скомпилировать с -O2
  • Хвостовая рекурсия хороша только тогда, когда нет наращивания преобразований, и добавление строгости обычно помогает предотвратить это, если и где это необходимо. Это происходит, когда вы сразу добиваетесь результата, который понадобится вам позже.
  • Иногда хвостовая рекурсия - плохой план, и защищенная рекурсия лучше подходит, то есть когда результат, который вы создаете, будет нужен постепенно, по частям. Посмотрите этот вопрос о foldrи, foldlнапример, и сравните их друг с другом.

Попробуйте эти два:

length $ foldl1 (++) $ replicate 1000 
    "The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000 
    "The number of reductions performed is more important than tail recursion!!!"

foldl1является хвостовой foldr1рекурсией , тогда как выполняет защищенную рекурсию, так что первый элемент немедленно предоставляется для дальнейшей обработки / доступа. (Первый «помещается в скобки» сразу влево, (...((s+s)+s)+...)+sзаставляя свой входной список полностью до конца и создавая большой кусок будущих вычислений намного раньше, чем потребуются его полные результаты; второй заключен в круглые скобки вправо постепенно s+(s+(...+(s+s)...)), потребляя ввод list по крупицам, так что все это может работать в постоянном пространстве с оптимизацией).

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

AndrewC
источник
1
@WillNess Отлично, спасибо. нет необходимости убирать. Думаю, теперь это лучший ответ для потомков.
AndrewC
4
Это здорово, но могу ли я предложить намек на анализ строгости ? Я думаю, что это почти наверняка сработает для хвостового рекурсивного факториала в любой достаточно свежей версии GHC.
dfeuer 03
16

Следует отметить, что facфункция не подходит для защищенной рекурсии. Хвостовая рекурсия - это то, что вам нужно. Из-за лени вы не получаете эффекта TCO в своей fac'функции, потому что аргументы-накопители продолжают создавать большие переходы, которые при оценке потребуют огромного стека. Чтобы предотвратить это и получить желаемый эффект от совокупной стоимости владения, вам необходимо сделать эти аргументы аккумулятора строгими.

{-# LANGUAGE BangPatterns #-}

fac :: (Integral a) => a -> a
fac x = fac' x 1 where
  fac' 1  y = y
  fac' x !y = fac' (x-1) (x*y)

Если вы компилируете с использованием -O2(или просто -O) GHC, вероятно, он сделает это самостоятельно на этапе анализа строгости .

is7s
источник
4
Думаю, с $!чем понятнее, чем с BangPatterns, но это хороший ответ. Особенно упоминание об анализе строгости.
singpolyma
7

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

(И в изучении Haskell остальные вики-страницы тоже великолепны!)

Кристофер Мицински
источник
0

Если я правильно помню, GHC автоматически оптимизирует простые рекурсивные функции в оптимизированные с хвостовой рекурсией.

Ncat
источник