управление памятью хвостовых вызовов в haskell - PullRequest
Новая
       27

управление памятью хвостовых вызовов в haskell

1 голос
/ 28 ноября 2010

Я использую следующую управляющую структуру (которую я считаю хвостовой рекурсивной) 

untilSuccessOrBigError :: (Eq e) => (Integer -> (Either e a)) -> Integer -> e -> (Either e a)
untilSuccessOrBigError f count bigError
  = case f count of
         Right x -> Right x
         Left e -> (if e==bigError then Left e else untilSuccessOrBigError f (count - 1) e)

сделать итеративное углубление 

iterativeDeepening :: (a -> [a]) -> (a -> Bool) -> (a -> Bool) -> a -> Either String a
iterativeDeepening stepFunc isAValidSolution isGraphBottom x
  = untilSuccessOrBigError
        (\count -> dfsWithMaxDepth stepFunc isAValidSolution isGraphBottom count x)
        (-1)
        "Reached graph bottom"

Будет ли эта свободная память (поскольку технически она больше не сможет ее достичь) после каждого итеративного углубления, если нет, то как мне переписать управляющую структуру?

P.S. Во-вторых, хотя это выглядит так, как будто это потерпит неудачу, поскольку хвостовые рекурсивные структуры часто могут получить доступ к вещам в стеке, например, к добавлению к предыдущему значению, даже если в этом случае это не так. - Роман А. Тайчер 28 ноября в 12:33 P.P.S. В-третьих, это заставляет меня думать, что он может отбросить значения внутри dfsWithMaxDepth, как только вернется dfsWithMaxDepth, и куча ответов не займет много памяти. - Роман А. Тайчер, ноябрь 2

1 Ответ

2 голосов
/ 28 ноября 2010

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

В общем, о tco и сборке мусора следует думать по-другому.в Хаскеле - много связанных вопросов, перечисленных здесь на SO, кажутся полезными.По сути, вы хотите представить операционную семантику GHC Haskell как ленивое сокращение графов.

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

Выше приведено небрежно и волнисто, но может помочь придать интуицию.

...