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]

ContT! ContT!

import Control.Monad.Cont
import Control.Monad.State

abort :: Monad m => r -> ContT r m a
abort x = ContT $ \_ -> return x

interrupt :: Monad m => ContT () m ()
interrupt = abort ()

runInterruptible m = runState (runContT m return)
------------------------------

loop = do
    modify (+1)
    check
    loop


check :: ContT () (State Int) ()
check = do
    s <- get
    if s == 42
        then interrupt
        else return ()

[permea-kra.livejournal.com]

Опередил -((.

[palm-mute.livejournal.com]

Continuations - моя любимая тема, это был практически рефлекс :)

[permea-kra.livejournal.com]

Я с ними вторую неделю ковыряюсь -))). Правда с трансформерами совершенно незнаком.

[lomeo.livejournal.com]

тваюзаногу
Спасибо!

[palm-mute.livejournal.com]

не надо маюзаногу!

[lomeo.livejournal.com]

уговорил :-)

[antilamer.livejournal.com]

Чорт, и меня опередил!

[lomeo.livejournal.com]

Обыдна, да! Все знают - я нет!

[antilamer.livejournal.com]

Ну, вообще-то, я с ContT обращаться не умею, я собирался сказать "Use the continuation, Luke!" :)

[lomeo.livejournal.com]

Успокоил ;-)
Спасибо! Пойду учиться :-)

[swizard.livejournal.com]

Видимо, это первая реакция у всех людей, хорошо знакомых с scheme :)

[lomeo.livejournal.com]

Я неплохо знаком со схемой, но ведь не сообразил.

И ещё - в scheme есть state monad? ;)

[swizard.livejournal.com]

Как это не удивительно, но в схеме есть все: http://okmij.org/ftp/Scheme/monad-in-Scheme.html =)

Другое дело, что с подобными вещами (монады, pattern matching) все-таки не так приятно работать в языке c динамической типизацией.

[lomeo.livejournal.com]

Ага, там свои вкусности.

[potan.livejournal.com]

Если в программе использовать только одну монаду - проблем особых нет.
Но как две задействовать с удобством я пока не придумал.

[palm-mute.livejournal.com]

>Я неплохо знаком со схемой, но ведь не сообразил.
Просто наиболее широко используемый оператор call/cc не слишком удобен. Тебе бы пришлось на верхнем уровне захватить продолжение и везде передавать как аргумент.

>И ещё - в scheme есть state monad? ;)
Банальность, но все равно скажу - монады есть везде, где есть first-class функции. А вот do-нотация делается или макросами, или через shift/reset.

[lomeo.livejournal.com]

Насчёт state-monad в схеме. Я тут давал линк, где реализовал её на схеме, чтобы посмотреть будет ли она хвостаторекурсивной. Это к тому, есть ли монады везде ;-)

Я же имел в виду - на фига козе баян? Что с этой монадой делать в схеме, где и так есть состояние?

[palm-mute.livejournal.com]

Линк не открывал, но я понимаю, что Америку не открываю.

>Что с этой монадой делать в схеме, где и так есть состояние?
Чисто теоретически, можно сделать какое-то особенное состояние. Например, мне недавно подумалось, что на shift/reset элементарно реализуется STM, но идею не проверял.

[lomeo.livejournal.com]

Проверишь - расскажешь?

[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]

Ясно.

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

[potan.livejournal.com]

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

[lomeo.livejournal.com]

На чём пишешь?

[potan.livejournal.com]

Как раз на Scheme. :-)
На работе это основной язык, решил не разрываться.

[lomeo.livejournal.com]

Где вы такие работы находите? :)

А почему монада показалась лучше, чем переменные? Вроде записи то у клиента схожие.

[potan.livejournal.com]

Я могу описать каждую команду ввиде комбинации монад, а потом уже их них все комбинировать не боясь неожиданного побочного эффекта.

[lomeo.livejournal.com]

В общем-то ясно, но надо будет посмотреть поближе, у меня до сих пор ощущение, что в схеме стейт-монада ну никак не нужна. Спасибо!

[palm-mute.livejournal.com]

Вот так родился гиковский вариант игры "первый, нах"

[permea-kra.livejournal.com]

state + continuation не поможет?

[lomeo.livejournal.com]

И тебе спасибо :-)

[mibori.livejournal.com]

кстати, возможно, боянистый вопрос ...
loop -- он таки хвостато-рекурсивен или нет?

[lomeo.livejournal.com]

Зависит от. Для State/StateT хвостато, я где то разбирал даже.

[lomeo.livejournal.com]

http://lomeo.livejournal.com/33004.html

[mibori.livejournal.com]

спасибо.

[migmit.vox.com (from livejournal.com)]

Твой InterruptState - не что иное, как MaybeT State. От перестановки мест трансформеров результат временами меняется. Functor, Monad и MonadState ты получаешь автомагически (см. hackage, как обычно). Cont тут сугубо лишний (хоть я его и люблю нежно).

[lomeo.livejournal.com]

Я пробовал его, что то у меня там не срослось.

[lomeo.livejournal.com]

Слушай, ты прав, как то криво я его проверял.

[palm-mute.livejournal.com]

Лишний Cont или не лишний - дело вкуса, т.к. Cont можно использовать вместо любой монады. Теоретически Cont должен быть дешевле, чем Maybe или Error, - меньше сравнений с образцом.

[migmit.vox.com (from livejournal.com)]

Можно. Это и называется "overkill". Это и значит "лишний".

> Теоретически Cont должен быть дешевле, чем Maybe или Error, - меньше сравнений с образцом.

М-м-м... не факт. Зато дофига cons-ов, от которых производительность может просесть очень прилично.

[palm-mute.livejournal.com]

>Можно. Это и называется "overkill". Это и значит "лишний".
Слишком категорично. Выпрыгивать из вложенных циклов - вполне естественное применение продолжений.

>М-м-м... не факт. Зато дофига cons-ов, от которых производительность может просесть очень прилично.
Вот тут ты, похоже, прав.