Блог

Этот код используется в Learn You A Haskell, чтобы объяснить, как ( ) может быть неэффективным, если он используется для построения списка справа, а не слева:

 import Control.Monad.Writer  

gcdReverse :: Int -> Int -> Writer [String] Int  
gcdReverse a b  
    | b == 0 = do  
        tell ["Finished with "    show a]  
        return a  
    | otherwise = do  
        result <- gcdReverse b (a `mod` b)  
        tell [show a    " mod "    show b    " = "    show (a `mod` b)]  
        return result  
  

Поскольку мы здесь не выполняем хвостовую рекурсию, правильно ли предположить, что GHC преобразует эту функцию в функцию в стиле CPS во время компиляции? Если это преобразование действительно происходит, могу ли я ожидать его от всех компиляторов Haskell, или это просто GHC.

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

Нет, GHC не выполняет преобразование CPS. Хотя существуют варианты преобразования CPS для ленивых языков, я не знаю ни одного компилятора для ленивого языка, который фактически выполняет преобразование CPS.

Вы правы в том, что преобразование CPS может обменивать пространство стека на пространство кучи, но некоторые компиляторы, использующие преобразование CPS, обрабатывают продолжения специально, чтобы они эффективно получали выделенный стек кучи, и поэтому вы все равно получите переполнение стека. Я думаю, что это хорошо, потому что это помогает отладке. И, что касается стеков, выделенных в куче, GHC делает это тоже без преобразования CPS. Вот как он справляется со своей реализацией облегченных потоков.