Interruptable state

[lomeo]

Понадобилось мне состояние, вычисление которого можно прервать в любой момент. Комбинатор guard не подходит тем, что его просто нет для State. if/then/else не устравает, потому что иногда прерывать необходимо в любом месте, например, в одной из вызываемой функции рекурсивной функции:

loop = do
    modify (+1)
    check
    loop

check = do
    s <- get
    if s == 42
        then interrupt
        else return ()

Вот как тут описать комбинатор interrupt?

По моему, как не опишешь, зацикливания не избежать. State на этом коде зацикливается. Можно попробовать StateT s Maybe, он оно не вернёт мне состояния на момент прерывания, когда я позову execStateT. Может быть можно всё таки воспользоваться готовым кодом, и просто параметризовать его нужным образом?

Пока обхожусь самодельной монадой

newtype InterruptState s a = IntState { runIntState :: s -> (Maybe a, s) }

Значение монады заворачивается каждый раз в Maybe, Nothing сигнализирует нам о том, что состояние было прервано. Для пользователя работа со значением должна быть прозрачна. Он ничего не обязан знать о том, что наше состояние реализовано через Maybe.

instance Functor (InterruptState s) where
    fmap f (IntState fs) = IntState $ \s -> let (a, s') = fs s
        in maybe (Nothing, s') (\v -> (Just (f v), s')) a

instance Monad (InterruptState s) where
    return x = IntState $ \s -> (Just x, s)
    m >>= f  = IntState $ \s -> let (a, s') = runIntState m s
        -- Вот здесь прерываем обработку, если состояние прервано.
        in maybe (Nothing, s') (\v -> runIntState (f v) s') a

Использование функции maybe позволяет разделить дальнейшее вычисление состояния и прерывание вычисления с возвратом текущего состояния. В качестве бонуса - мы используем чистое значение из под Just-конструктора в дальнейшей обработке.

Реализуем функции работы с состоянием a la State:

instance MonadState s (InterruptState s) where
   get   = IntState $ \s -> (Just s,s)
   put s = IntState $ \_ -> (Just (),s)

execIntState m s = snd (runIntState m s)
evalIntState m s = fst (runIntState m s)

Всяческие withState, mapState реализуются схожим образом. Не забываем только учитывать Nothing.

Прерывание, как уже говорилось, возвращает Nothing в значении.

interrupt = IntState $ \s -> (Nothing, s)

Пример сверху теперь сработает корректно

*Main> execIntState loop 0
42

Обидно, что трансформер, схожий с StateT из этого не сделаешь, чтобы Maybe заменить на Monad m => m. Или сделаешь?

Comments

[palm-mute.livejournal.com]

Проверил. Оказалось, что продолжения для STM не очень-то нужны. Мне казалось, что они будут удобны для возможности проигрывать транзацию повторно в случае неудачи.

В моем понимании STM = StateT TransactionLog IO. Поэтому при переводе на Схему продолжения (или монада State) нам могут понадобиться только в том случае, если мы захотим протаскивать лог транзакции неявно, в противном случае достаточно мутабельных переменных и first-class функций.

Если бы моя гипотеза подтвердилась, я бы написал развернутый пост, а так, если интересно
вот наивная реализация (http://sites.google.com/site/iampalmmute/Home/myintstm.hs?attredirects=0). Не исключено, что с ошибками.

[lomeo.livejournal.com]

Спасибо! А я что-то не понял - где там продолжения?

Я бегло посмотрел - там дедлок не будет в случае

-- thread 1
atomically $ modifyTVar var1 f1 >> modifyTVar var2 f2
-- thread 1
atomically $ modifyTVar var2 g1 >> modifyTVar var1 g2

Во время validateAndCommit в первом треде залочится var1 мьютекс, а во-втором var2 и будут ждать друг друга? Возможно, лучше tryTakeMVar и если Nothing, то освобождаем все и на петлю. А так - прикольно, интересное решение. Я, когда разбирался, делал похожее, но с одним глобальным мьютексом.

[lomeo.livejournal.com]

Копипаст :-)) Конечно, во втором случае --thread 2

[palm-mute.livejournal.com]

>А я что-то не понял - где там продолжения?
Продолжений там нет. План проверки идеи был такой - нарисовать на Хаскеле монаду, реализующую абстракцию STM штатными средствами. В зависимости от заковыристости монады решаем, нужны ли нам продолжения при переводе на Схему. Для StateT s IO можно обойтись без продолжений.

>Во время validateAndCommit в первом треде залочится var1 мьютекс, а во-втором var2 и будут ждать друг друга?
Дедлоков быть не должно - все переменные пронумерованы, Map.keys возвращает ключи отсортированными - мюьтексы захыватываются в одном порядке.

>Я, когда разбирался, делал похожее, но с одним глобальным мьютексом.
Ну, с глобальным мьютексом можно вообще сердито поступить - STM = IO, atomically m = do { lock gmtx; a <- m; release gmtx; return a } :) (я так понимаю, мьютекс захватывался только во время коммита?)

[lomeo.livejournal.com]

Ясно.

Да, во время коммита.