Подтвердить что ты не робот

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

Я новичок в Haskell, и мне нравится идея замены циклов рекурсией. Я возился с проектом для домашних животных, и я хотел протестировать некоторые функции ввода текста, поэтому я написал небольшой интерфейс командной строки, который неоднократно запрашивает ввод, пока не получит определенную команду quit. Это выглядит примерно так:

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 заключается в том, что он безумно оптимизирующий компилятор, который предназначен для совершения невероятных вещей, таких как прекрасное разворачивание хвостовых рекурсивных функций и тому подобное. Так может кто-нибудь объяснить, является ли эта реализация "правильной", и если это так объясняет мне, что происходит за кулисами, которые помешали бы этой программе взорваться, если бы она была поставлена ​​в руки бесконечного числа обезьян?

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

Double Edit: Большое спасибо за все потрясающие ответы. Оглядываясь назад, я не думаю, что я правильно сформулировал вопрос, но у меня все еще есть то, что я искал. Этот вопрос был не столько основан на идее, что я был смущен тем, как Хаскелл использовал стек, и я ожидал, что он будет работать как императивный язык; это было основано на том, что я понятия не имел, как Haskell обрабатывал стек и хотел знать, что он делает иначе, чем традиционные C-подобные языки. Я просыпаюсь с умным человеком благодаря вам.

4b9b3361

ОТВЕТЫ

Ответ 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, пока кто-то не узнает, пусты или нет.

Ответ 2

Эта реализация верна.

Я не думаю, что оптимизация хвостового вызова - это действительно бит, который делает эту работу эффективной. Вместо этого, что позволяет ему эффективно работать, верьте или нет, неизменность действий IO. Вы удивлены тем, что действия IO неизменны? Я был первым! Что это значит: getCommandsFromUser - это рецепт для "вещей, которые нужно сделать"; и каждый раз, когда вы оцениваете getCommandsFromUser, он оценивает один и тот же рецепт. (Хотя, конечно, не каждый раз, когда вы следуете рецепту, вы получаете тот же результат! Но это другая фаза исполнения целиком.)

В результате этого все оценки getCommandsFromUser могут быть разделены - GHC просто хранит одну копию рецепта в памяти, а часть этого рецепта включает указатель назад к началу рецепта.

Ответ 3

Как я понимаю, вы должны забыть о TCO: вместо того, чтобы спросить, находится ли рекурсивный вызов в хвостовом положении, подумайте с точки зрения охраняемой рекурсии. Этот ответ Я думаю, это правильно. Вы также можете проверить сообщение на Data and Codata из всегда интересного и сложного блога "Neighborhood of Infinity". Наконец, проверьте Space Leak Zoo.

РЕДАКТИРОВАТЬ: Мне жаль, что это не касается вашего вопроса о монадических действиях напрямую; Мне интересно видеть другие ответы, такие как DanielWagner, которые конкретно касаются монады IO.