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

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

Даже когда у вас есть «стек», нет ничего, что говорит о том, что стек должен быть ограничен небольшой долей доступной памяти. Это по сути эвристика, настроенная на императивное программирование; там, где вы не используете рекурсию в качестве метода решения проблем, очень глубокие стеки вызовов, как правило, возникают из-за ошибок бесконечной рекурсии, а ограничение размера стека до чего-то весьма небольшого означает, что такие программы быстро умирают вместо того, чтобы использовать всю доступную память и перестановку, а затем умирающих.

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

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

Давайте рассмотрим пример, чтобы увидеть, как можно оценить ваш код. ^{1 Я приведу еще более простой пример, чем ваш:}

main = do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

Оценка Haskell ленива ^{2 . Проще говоря, это означает, что он будет оценивать термин только тогда, когда ему нужно значение этого термина для принятия решения. Например, если я вычисляю 1 + 1 и затем добавляю результат этого в начало списка, его можно оставить как «ожидающий» 1 + 1 в списке 3 . Но если я использую if, чтобы проверить, был ли результат равен 3, , то Haskell должен будет фактически сделать работу по превращению 1 + 1 в 2.}

1165 Но если бы это все, что было, ничего бы не случилось. Вся программа будет оставлена ​​как «ожидающая» стоимость. Но есть внешний драйвер, который должен знать, что оценивает действие IO main, чтобы выполнить его.

Вернемся к примеру. main равен этому блоку do. Для IO блок do выполняет большое действие IO из серии меньших, которые должны выполняться по порядку. Таким образом, во время выполнения Haskell main оценивается как input <- getLine, за которым следуют некоторые неоцененные вещи, которые ему пока не нужны. Этого достаточно, чтобы знать, читать с клавиатуры и вызывать получившийся String input. Скажи, что я набрал "фу". Это оставляет Haskell с чем-то вроде следующего как его «следующее» IO действие:

if "foo" == "quit"
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

Haskell смотрит только на самую внешнюю вещь, так что это очень похоже на « if бла бла бла бла ... ". if IO-исполнитель - не то, с чем он может что-либо делать, поэтому его нужно оценить, чтобы увидеть, что он возвращает. if просто оценивает либо ветку then, либо else, но чтобы узнать, какое решение сделать Haskell требуется для оценки условия. Таким образом, мы получаем:

if False
    then
        putStrLn "Good-bye!"
    else do
        putStrLn $ "You typed: " ++ "foo"
        main

, который позволяет сократить все if до:

do
    putStrLn $ "You typed: " ++ "foo"
    main

И снова, do дает нам действие IO, которое состоит из упорядоченная последовательность вложенных действий. Итак, следующая вещь, которую должен выполнить IO-исполнитель - putStrLn $ "You typed: " ++ "foo". Но это также не действие IO (это неоцененное вычисление, которое должно привести к одному). Так что нам нужно это оценить.

«Самая внешняя» часть putStrLn $ "You typed: " ++ "foo" на самом деле $. Избавившись от синтаксиса инфиксного оператора, чтобы вы могли видеть его так же, как это делает runtiem Haskell, это выглядело бы так:

($) putStrLn ((++) "You typed: " "foo")

Но оператор $ только что определен как ($) f x = f x, подставляя правая часть сразу дает нам:

putStrLn ((++) "You typed: " "foo")`

Теперь обычно мы оцениваем это, подставляя в определение putStrLn, но это «волшебная» примитивная функция, которая не может быть прямо выражена в Haskell. код. Так что на самом деле это не оценивается так; внешний IO-исполнитель просто знает, что с ним делать. Но это требует, чтобы аргумент из putStrLn был полностью оценен, поэтому мы не можем оставить его как (++) "You typed: " "foo".

На самом деле существует целый ряд шагов для полной оценки этого выражения, проходящих через определение ++ в терминах операций со списками, но давайте просто пропустим это и скажем, что оно оценивается как "You typed: foo". Таким образом, IO-исполнитель может выполнить putStrLn (запись текста на консоль) и перейти ко второй части блока do, а именно:

`main`

не то, что может быть немедленно выполнено как действие IO (оно не встроено в Haskell, как putStrLn и getLine), поэтому мы оцениваем его, используя правую часть определения main, чтобы получить :

do
    input <- getLine
    if input == "quit"
        then
            putStrLn "Good-bye!"
        else do
            putStrLn $ "You typed: " ++ input
            main

И я уверен, что вы можете видеть, куда идут остальные.

1176 Обратите внимание, что я ничего не сказал ни о каком стеке. Все это просто построение структуры данных, описывающей действие IO, которое является main, так что внешний драйвер может его выполнить. Это даже не особая структура данных; с точки зрения системы оценки, она, как и любая другая структура данных, не имеет произвольных ограничений по размеру.

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

---

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

---

^{1 Я сразу откажусь от того, что я не очень подробно знаю о текущей текущей реализации Haskell. Однако я знаю общие методы реализации ленивых чистых языков, таких как Haskell. Я также постараюсь не вдаваться в подробности и просто объяснить, как все работает интуитивно. Так что эта учетная запись может быть неверной в некоторых тонких деталях того, что на самом деле происходит внутри вашего компьютера, но она должна показать вам, как эти вещи могут работать.}

^{2 Спецификация языка технически просто говорит, что оценка должна быть "нестрогой". Оценка, которую я собираюсь описать, которая неофициально называется «ленивая», на самом деле является лишь одной из возможных «нестрогих» стратегий оценки, но это то, что вы получаете на практике.}

^{3 И новый список на самом деле можно оставить как «ожидающий» результат (1 + 1) : originalList, пока кто-то не узнает, пуст он или нет.}