Haskell рекурсия и использование памяти
Мне становится комфортно с идеей замены циклов рекурсией. Я возился с любимым проектом и хотел протестировать некоторые функции ввода текста, поэтому я написал небольшой интерфейс командной строки, который постоянно запрашивает ввод, пока не получит конкретную команду выхода.
Это выглядит примерно так:
getCommandsFromUser = do
putStrLn "Enter command: "
keyboardInput <- getLine
let command = map toLower keyboardInput
if command == "quit"
then
putStrLn "Good-bye!"
else do
-- stuff
-- more stuff
putStrLn ("Sending command: " ++ commandURI)
simpleHTTP $ getRequest commandURI
getCommandsFromUser
main = do
getCommandsFromUser
Это работает точно так, как и ожидалось, но, исходя из опыта C/Java, оно все еще щекочет глубокие, темные, бессознательные части моего мозга и заставляет меня хотеть вырваться в ульи, потому что я не могу избавиться от мысли, что каждый рекурсивный вызов getCommandsFromUser Быть созданным создает новый фрейм стека.
Теперь я еще ничего не знаю о IO, монадах, состоянии, стрелах и т. Д. Я все еще прохожу свой путь через Real World на Haskell, я еще не дошел до этой части, и часть этого кода соответствует шаблонам, которые я нашел в Google.
Кроме того, я знаю, что весь смысл GHC в том, что это сводящий с ума оптимизирующий компилятор, который предназначен для выполнения невероятных вещей, таких как красивая развертка хвостовых рекурсивных функций и тому подобное.
Так может кто-нибудь объяснить, является ли эта реализация "правильной", и если да, объясните мне, что происходит за кулисами, что предотвратит взрыв этой программы, если она будет передана в руки бесконечного числа обезьян?
Я знаю, что такое оптимизация хвостовых вызовов. Меня больше беспокоит то, как это работает в этом случае, что происходит с действиями и общей функциональной примесью.
Этот вопрос основывался не столько на идее, что меня смутило то, как Хаскелл использовал стек, и что я ожидал, что он будет работать как императивный язык; это было основано на том факте, что я понятия не имел, как Haskell обращается со стеком, и хотел знать, что он делает по-другому, чем традиционные C-подобные языки.
4 ответа
Не беспокойтесь о стеке. Нет ничего фундаментального в том, что вызовы функций должны быть реализованы с использованием стековых фреймов; это всего лишь один из возможных методов их реализации.
Даже когда у вас есть "стек", нет ничего, что говорит о том, что стек должен быть ограничен небольшой долей доступной памяти. Это по сути эвристика, настроенная на императивное программирование; там, где вы не используете рекурсию в качестве метода решения проблем, очень глубокие стеки вызовов, как правило, возникают из-за ошибок бесконечной рекурсии, а ограничение размера стека до чего-то весьма небольшого означает, что такие программы быстро умирают вместо того, чтобы потреблять всю доступную память и выполнять обмен, а затем умирает.
Функциональному программисту наличие нелегкого изъяна в конструкции языка, когда программа завершает "нехватку" памяти для выполнения большего количества вызовов функций, когда на компьютере еще есть гигабайты оперативной памяти. Это было бы похоже на ограничивающие циклы C для некоторого произвольного числа итераций. Таким образом, даже если функциональный язык реализует вызовы функций с использованием стека, будет сильная мотивация избегать использования стандартного крошечного стека, который мы знаем из C, если это возможно.
На самом деле, у Haskell есть стек, который может переполняться, но это не тот стек вызовов, с которым вы знакомы из C. Можно написать нерекурсивные функции, которые бесконечно рекурсивно и будут использовать всю доступную память, не затрагивая ограничение по глубине звонка. Стек, который есть у Haskell, используется для отслеживания "ожидающих" значений, которые нужно оценить немного больше, чтобы принять решение (я расскажу об этом чуть позже). Вы можете прочитать более подробно об этом виде переполнения стека здесь.
Давайте рассмотрим пример, чтобы увидеть, как ваш код может быть оценен. 1 Я приведу еще более простой пример, чем ваш:
main = do
input <- getLine
if input == "quit"
then
putStrLn "Good-bye!"
else do
putStrLn $ "You typed: " ++ input
main
Оценка Хаскелла ленива 2. Проще говоря, это означает, что он будет оценивать термин только тогда, когда ему необходимо значение этого термина для принятия решения. Например, если я вычислю 1 + 1 а затем добавить результат этого в начало списка, его можно оставить как "ожидающий" 1 + 1 в списке 3. Но если я использую if чтобы проверить, был ли результат равен 3, тогда Haskell нужно будет на самом деле сделать поворот 1 + 1 в 2,
Но если бы это все, что было, ничего бы не случилось. Вся программа будет просто оставлена как "ожидающая" стоимость. Но есть внешний драйвер, который должен знать, какое действие ввода-вывода main оценивает, чтобы выполнить это.
Вернуться к примеру. main равно этому do блок. За IO, do блок делает большой IO действие из ряда меньших, которые должны быть выполнены по порядку. Таким образом, среда выполнения Haskell видит main оценивая input <- getLine сопровождаемый некоторыми неоцененными вещами, в которых это еще не нуждается. Достаточно знать, чтобы прочитать с клавиатуры и вызвать полученную Stringinput, Скажи, что я набрал "фу". Это оставляет Haskell с чем-то вроде следующего как его "next" 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" на самом деле $, Избавившись от синтаксиса инфиксного оператора, чтобы вы могли видеть его так же, как это делает 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
И я уверен, что вы можете видеть, куда идут остальные.
Обратите внимание, что я ничего не сказал о каком-либо стеке. Все это просто построение структуры данных, описывающей IO действие, которое main Таким образом, внешний драйвер может выполнить его. Это даже не особая структура данных; с точки зрения системы оценки, она, как и любая другая структура данных, не имеет произвольных ограничений по размеру.
В этом случае ленивая оценка означает, что генерация этой структуры данных чередуется с ее потреблением (и генерация более поздних ее частей может зависеть от того, что произошло в результате использования более ранних ее частей!), И поэтому эта программа может работать в постоянное количество места. Но, как отмечается в комментарии Шахафа к этому вопросу, это не совсем оптимизация для удаления ненужных кадров стека; это просто то, что происходит автоматически с ленивой оценкой.
Поэтому я надеюсь, что это было достаточно полезно для вас, чтобы увидеть, что происходит. По сути, к тому времени, когда Хаскелл оценивает рекурсивный вызов getCommandsFromUser, это уже сделано со всеми данными, сгенерированными в предыдущей итерации, и поэтому он собирает мусор. Таким образом, вы можете продолжать запускать эту программу бесконечно, не занимая больше фиксированного объема памяти. Это просто прямое следствие ленивой оценки, и существенно не отличается, когда IO вовлечен.
Я собираюсь заранее заявить, что я не знаю очень подробно о фактической текущей реализации Haskell. Однако я знаю общие методы реализации ленивых чистых языков, таких как Haskell. Я также постараюсь не вдаваться в подробности и просто объяснить, как все работает интуитивно. Так что эта учетная запись может быть неверной в некоторых мелких деталях того, что на самом деле происходит внутри вашего компьютера, но она должна показать вам, как эти вещи могут работать.
2 Технически спецификация языка просто говорит, что оценка должна быть "нестрогой". Оценка, которую я собираюсь описать, которая неофициально называется "ленивая", на самом деле является лишь одной из возможных "нестрогих" стратегий оценки, но это то, что вы получаете на практике.
3 И новый список фактически можно оставить как "ожидающий" результат (1 + 1) : originalList пока кто-то не должен знать, пусто оно или нет.
Эта реализация верна.
Я не думаю, что оптимизация хвостового вызова - это та часть, которая делает эту работу эффективной. Вместо этого, что позволяет ему работать эффективно, так это, верите или нет, неизменность действий ввода-вывода. Вы удивлены, что действия IO неизменны? Я был сначала! Что это значит, это: getCommandsFromUser это рецепт для "вещей, чтобы сделать"; и каждый раз, когда вы оцениваете getCommandsFromUser, он оценивает по тому же рецепту. (Хотя, конечно, не каждый раз, когда вы следуете рецепту, вы получаете один и тот же результат! Но это совсем другая фаза выполнения.)
Результатом этого является то, что все оценки getCommandsFromUser можно поделиться - GHC просто хранит одну копию рецепта в памяти, и часть этого рецепта включает указатель на начало рецепта.
Насколько я понимаю, вы должны забыть о TCO: вместо того, чтобы спрашивать, находится ли рекурсивный вызов в хвостовой позиции, думайте с точки зрения защищенной рекурсии. Этот ответ, я думаю, имеет право. Вы также можете ознакомиться с постом " Данные и кодаты" из всегда интересного и интересного блога "Соседство бесконечности". Наконец проверьте Зоопарк Космической утечки.
РЕДАКТИРОВАТЬ: я сожалею, что выше не касается вашего вопроса о монадических действиях напрямую; Мне интересно увидеть другие ответы, такие как DanielWagner, которые конкретно касаются монады IO.
Неважно, что IO участвует. Вы можете прочитать об этом в вики Haskell:
Или, для более глубокого опыта с IO Haskell: