Восстановление после переполнения стека или исчерпания кучи в программе на Haskell - PullRequest
Новая
       17

Восстановление после переполнения стека или исчерпания кучи в программе на Haskell

5 голосов
/ 19 апреля 2011

В настоящее время я пишу генетический алгоритм на Хаскеле, в котором мои хромосомы представляют собой довольно сложные структуры, представляющие исполняемые системы.

Чтобы оценить пригодность моих хромосом, я должен запустить функцию evolution, которая выполняет один вычислительный цикл данной системы. Пригодность тогда вычисляется, просто посчитав, сколько раз evolution может быть применено, прежде чем не произойдет изменений в системе (в этом случае система завершается).

Проблема теперь заключается в следующем: некоторые системы могут работать бесконечно долго и никогда не прекратят работу - я хочу наказать их (давая им мало очков). Я мог бы просто установить определенное ограничение на количество шагов, но это не решает другую проблему.

Некоторые из моих систем выполняют экспоненциальные вычисления (т. Е. Даже для небольших значений шагов эволюции они достигают гигантских размеров), и они вызывают ERROR - Control stack overflow. Для наблюдателя-человека очевидно, что они никогда не завершатся, но алгоритм не может знать, поэтому он работает и разрушается.

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

Мне кажется, что лучшим решением было бы сказать программе: «Эй, попробуй, но если не получится, не волнуйся. Я знаю, как с этим справиться». Однако я даже не уверен, возможно ли это. Если нет - есть ли альтернативы?

Ответы [ 4 ]

5 голосов
/ 19 апреля 2011

Это будет трудно сделать надежно изнутри Haskell - хотя при некоторых условиях GHC будет выдвигать исключения для этих условий .(Вам понадобится GHC 7). 

import Control.Exception

Если вы действительно просто хотите перехватить переполнение стека, это возможно, как показано в следующем примере: 

> handle (\StackOverflow -> return Nothing) $
              return . Just $! foldr (+) 0 (replicate (2^25) 1) 
Nothing

Или перехват любого асинхронного исключения(включая исчерпание кучи): 

> handle (\(e :: AsyncException) -> print e >> return Nothing) $
              return . Just $! foldr (+) 0 (replicate (2^25) 1) 
stack overflow
Nothing

Однако, это хрупко.

Альтернативно, с помощью флажков GHC вы можете принудительно установить максимальный размер стека (или кучи) в процессе, скомпилированном GHC, что приведет к его уничтожению, если он превысит эти пределы (GHC, похоже, немаксимальное ограничение стека в эти дни).

Если вы компилируете свою программу на Haskell с помощью GHC (как рекомендуется), запустите ее следующим образом: 

$ ghc -O --make A.hs -rtsopts

применяется нижний предел кучи ниже: 

$ ./A +RTS -M1M -K1M
Heap exhausted;

Для этого требуется GHC.(Опять же, вы не должны использовать объятия для такой работы).Наконец, вы должны убедиться, что ваши программы не используют чрезмерный стек во-первых, через профилирование в GHC .

2 голосов
/ 19 апреля 2011

Я думаю, что общее решение здесь - предоставить способ измерения времени вычислений и убить его, если это занимает слишком много времени. Вы можете просто добавить счетчик к своей функции оценки, если она рекурсивная и если она падает до нуля, вы возвращаете значение ошибки - например, Nothing, в противном случае это Just result.

Этот подход может быть реализован другими способами, кроме явного параметра count, например, путем помещения этого счетчика в монаду, используемую для оценки (если ваш код является монадическим), или, что нечисто, путем запуска вычислений в отдельном потоке, который будет уничтожен по истечении ,

Я бы предпочел использовать любое чистое решение, так как оно было бы более надежным.

1 голос
/ 20 апреля 2011

Мысль о вашем генетическом алгоритме. Часть пригодности ваших хромосом заключается в том, что они не потребляют слишком много вычислительных ресурсов. Заданный вами вопрос определяет «слишком много ресурсов» как сбой системы во время выполнения. Это довольно произвольная и несколько случайная мера.

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

1 голос
/ 19 апреля 2011 
It seems to me like the best solution would be to tell the program: 
"Hey, try doing this, but if you fail don't worry. I know how to handle it"

В большинстве языков это будет блок try/catch.Я не уверен, что эквивалент в haskell, или даже если какой-то эквивалент существует.Кроме того, я сомневаюсь, что конструкция try/catch могла бы эффективно перехватывать / обрабатывать состояние переполнения стека.

Но возможно ли применить некоторые разумные ограничения для предотвращения переполнения?Например, возможно, вы могли бы установить некоторую верхнюю границу размера системы и следить за тем, как каждая система приближается к границе от одной итерации к следующей.Тогда вы могли бы применить правило типа «если в одном evolution система либо превысила свою верхнюю границу, либо использовала более 50% пространства, оставшегося между ее предыдущим выделением и ее верхней границей, эта система завершается и подвергаетсяпенальти ".

...