Ответ 1
Не беспокойтесь о стеке. Нет ничего фундаментального, говорящего, что вызовы функций должны выполняться с использованием фреймов стека; это всего лишь один из возможных способов их реализации.
Даже когда у вас есть "стек", нет ничего, что говорит о том, что стек должен быть ограничен небольшой долей доступной памяти. Это по сути эвристика, настроенная на императивное программирование; где вы не используете рекурсию как метод решения проблем, очень глубокие стеки вызовов, как правило, возникают из-за ошибок с бесконечной рекурсией, и ограничение размера стека на что-то довольно маленькое означает, что такие программы быстрее умирают, а не потребляют всю доступную память и свопируют, а затем умираю.
Для функционального программиста, когда программа завершает "выбег" из памяти, чтобы сделать больше вызовов функций, когда компьютер по-прежнему имеет гигабайты ОЗУ, является смехотворным недостатком в разработке языка. Это было бы как 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.
Но если бы все было в этом, ничего бы не случилось. Вся программа будет оставлена как "ожидающее" значение. Но есть внешний драйвер, который должен знать, что оценивает действие IO main, чтобы выполнить его.
Вернемся к примеру. main равен этому блоку do. Для IO блок do делает большое действие IO из серии меньших, которые должны выполняться по порядку. Таким образом, время выполнения Haskell оценивает main на input <- getLine, за которым следуют некоторые неоцененные вещи, которые пока не нужны. Это достаточно, чтобы знать, чтобы читать с клавиатуры и называть полученный String input. Скажем, я набрал "foo". Это оставляет Haskell с чем-то вроде следующего в качестве своего следующего действия IO:
if "foo" == "quit"
then
putStrLn "Good-bye!"
else do
putStrLn $ "You typed: " ++ "foo"
main
Haskell только смотрит на самую внешнюю вещь, так что это в значительной степени похоже на ", если бла-бла-бла-бла...". 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" на самом деле $. Избавьтесь от синтаксиса оператора infix, чтобы вы могли увидеть его так же, как это делает Haskell runtiem, он будет выглядеть так:
($) 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
И я уверен, что вы можете увидеть, где все остальное.
Обратите внимание, что я ничего не говорил о любом стеке. Все это просто создает структуру данных, описывающую действие IO, которое main, поэтому внешний драйвер может его выполнить. Это даже не особенно особая структура данных; с точки зрения системы оценки он точно так же, как и любая другая структура данных, и поэтому нет никаких произвольных ограничений на его размер.
В этом случае ленивая оценка означает, что генерация этой структуры данных чередуется с ее потреблением (а генерация последующих ее частей может зависеть от того, что произошло в результате потребления более ранних ее частей!), и поэтому эта программа может работать в постоянном пространстве. Но, как отметил комментарий shachaf по этому вопросу, на самом деле это не оптимизация для удаления ненужных фреймов стека; это просто то, что происходит автоматически с ленивой оценкой.
Поэтому я надеюсь, что это было бы достаточно полезно для вас, чтобы посмотреть, что происходит. В принципе, к тому времени, когда Haskell получает оценку рекурсивного вызова getCommandsFromUser, он уже выполняется со всеми данными, созданными в предыдущей итерации, и поэтому он получает сбор мусора. Таким образом, вы можете продолжать эту программу неограниченно, не требуя больше фиксированного объема памяти. Это просто очевидное следствие ленивой оценки и не существенно отличается при использовании IO.
1 Я собираюсь отказаться от фронта, о котором я не очень подробно расскажу о фактической текущей реализации Haskell. Однако я знаю общие методы для реализации ленивых чистых языков, таких как Haskell. Я также попытаюсь избежать слишком много погружений в детали и просто объяснить, как все работает интуитивно. Таким образом, эта учетная запись может быть неправильной в некоторых тонких деталях того, что происходит на вашем компьютере, но должно показать вам, как эти вещи могут работать.
2 Спецификация языка технически просто говорит, что оценка должна быть "нестрогой". Оценка, которую я собираюсь описать, которая известна как "ленивый" неофициально, на самом деле является единственной возможной "нестрогой" стратегией оценки, но это то, что вы получаете на практике.
3 И новый список фактически может быть оставлен как "ожидающий" результат (1 + 1) : originalList, пока кто-то не узнает, пусты или нет.