Здравствуйте, valexey, Вы писали:
V>Читаю вот статью "мягкое введение в Haskell", решил попробовать один из примеров, а именно -- подсчет длины списка.
V>
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, deniok, Вы писали:
D>>Правильно делает. Для thunk'а 1+1+1+...+1 (10000000 раз) никакой памяти не хватит.
Б>Непонятно, почему не сделана простейшая оптимизация.
В чем должна заключаться оптимизация — можно точно сформулировать?
D>>Рекурсию — в хвостовую, а затем форсировать. Например, так
Б>Можно и не форсировать.
Можно, но если хочется избавиться от stack overflow, то придется
Здравствуйте, deniok, Вы писали:
Б>>Непонятно, почему не сделана простейшая оптимизация.
D>В чем должна заключаться оптимизация — можно точно сформулировать?
Нельзя Поспешил я. Показалось, что здесь можно было бы догадаться ввести аккумулятор.
Но, получается, что в общем случае это сделать проблематично. Я подумаю над этим
Б>>Можно и не форсировать.
D>Можно, но если хочется избавиться от stack overflow, то придется
Ну, с ключами -O3 и -O2 stack overflow не вылезает. Я проверил
Здравствуйте, Буравчик, Вы писали:
Б>Ну, с ключами -O3 и -O2 stack overflow не вылезает. Я проверил
Ну, мы конечно верим в GHC team и в их strictness analyzer, но всё же -On на мой вкус недостаточно документированы. Чего бы не подсказать компилятору, где можно/нужно форсировать.
Здравствуйте, deniok, Вы писали:
D>Рекурсию — в хвостовую, а затем форсировать. Например, так ...
А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...
Здравствуйте, geniepro, Вы писали:
D>>Рекурсию — в хвостовую, а затем форсировать. Например, так ...
G>А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...
в gcc есть strictness analyzer?
вообще-то причина ровно одна — ghc комипилирует более высокоуровневый язык. и утверждать, что gcc умеет это оптимизировать — всё равно что говорить, что это умеет делать gas
Здравствуйте, geniepro, Вы писали: G>А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...
Gcc умеет превращать рекурсивный процесс в итеративный (т.е. убирать рост control context)?
Или ты про необходимость форсить в хаскеле даже в случае хвостовой рекурсии.
Здравствуйте, geniepro, Вы писали:
G>Здравствуйте, deniok, Вы писали:
D>>Рекурсию — в хвостовую, а затем форсировать. Например, так ...
G>А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...
Ну, попробуем. Понятно, что оптимизировать надо не эту конкретную функцию (это, кстати, сделано для библиотечной length), а некоторый паттерн рекурсии. Выделим его:
genieproMorphism _ ini _ [] = ini
genieproMorphism f ini step (_:xs) = f step (genieproMorphism f ini step xs)
-- при этом, кстати
length' = genieproMorphism (+) 0 1
foldr f ini [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` ini)...)
заключаем, что наш морфизм — частный случай катаморфизма; слегка подумав, выражаем его через foldr.
genieproMorphism f step = foldr (f . const step)
-- или так
genieproMorphism f step = foldr (\_ acc -> f step acc)
Ну foldr к foldl' свести, мягко говоря, не очень просто, здесь даже анализатора строгости не хватит, ещё для f нужен будет анализатор ассоциативности.
Может не стоило обобщать всё до полного катаморфизма? Вычисления в исходном примере могут начаться, только когда мы, пробежав весь список, дойдем до ini (увязанного в данном примере с концом списка). А то, что (step `f` ini) можно выполнить над началом списка, а дальше применять (step `f`) к результату над каждым следующим элементом и получить то же самое — это некоторый тонкий факт, связанный с тем, что мы в действительности игнорируем сами элементы списка. Пожалуй подобную оптимизацию действительно можно было бы сделать, поскольку здесь мы имеем дело с истинным полиморфизмом: в типе
genieproMorphism :: (a -> b -> b) -> a -> b -> [t] -> b
тип t стоит под квантором общности. Итак: допустима замена
\f step -> foldr (\_ acc -> f step acc)
-- на
\f step -> foldl (\acc _ -> f step acc)
которая, конечно, имеет смысл, если в дальнейшем анализатор строгости решит заменить foldl на foldl'.
[cut] D>Ну foldr к foldl' свести, мягко говоря, не очень просто, здесь даже анализатора строгости не хватит, ещё для f нужен будет анализатор ассоциативности.
А вывести, что у нас тут Sum a, который моноид, в общем случае не получится? Хотя, блин, это и будет уже анализатор ассоциативности (если явно нигде ничего не указывать )
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, deniok, Вы писали:
D>>Можно, но если хочется избавиться от stack overflow, то придется
Б>Здесь же явная хвостовая рекурсия. Почему GHC ее не превратил в цикл?
По-моему GHCi по умолчанию не оптимизирует, а чтобы превратить хвостовую рекурсию в цикл в ленивом языке надо еще провести strictness analysis. Иначе семантика может поменяться; да и эффективность упасть.
Здравствуйте, geniepro, Вы писали: G>Ну вот, на другом форуме на эту тему сообщили: G>GCC 4.4
Занятно. Интересно, насколько сложные случаи он может оптимизировать.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, deniok, Вы писали:
D>>Можно, но если хочется избавиться от stack overflow, то придется
Б>Здесь же явная хвостовая рекурсия. Почему GHC ее не превратил в цикл?
Это может быть превращено в цикл. За исключением, что вместо значения ты получишь вычисление этого значения, которое и упадёт на FORCE, что нужно для вывода.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)