Open HeinrichApfelmus opened 9 years ago
I'm confused with this difference, why is this necessary? What is the difference in the model? Is this due implementation details?
The two combinators are indistinguishable in the model implementation. Unfortunately, I have found it necessary to distinguish them in the efficient implementation. This is because the IO
type constructor is not a good MonadFix instance.
The following code demonstrates the issue. If we want to use the result for IO right away, then valueB
is the right choice (testA1
vs testA2
). If we want to use the result with value recursion, then valueBLater
is the right choice (testB1
vs testB2
). I have not been able to find an implementation that works in both cases.
{-# LANGUAGE RecursiveDo #-}
module TestValueB where
import Reactive.Banana
import Reactive.Banana.Frameworks
testMoment :: MomentIO a -> IO a
testMoment m = fmap from $
interpretFrameworks (\e -> m >>= \x -> return (x <$ e)) [Just ()]
where from [Just x] = x
testA1, testA2, testB1, testB2 :: MomentIO Int
-- works
testA1 = do
b <- stepper 0 never
x <- valueB b
liftIO $ print x
return x
-- fails, throws exception
testA2 = do
b <- stepper 0 never
x <- valueBLater b
liftIO $ print x
return x
-- fails, does not terminate
testB1 = mdo
x <- valueB b
b <- stepper 0 never
return x
-- works
testB2 = mdo
x <- valueBLater b
b <- stepper 0 never
return x
I see. Is there any documentation how your implementation works? On Jan 1, 2016 5:30 PM, "Heinrich Apfelmus" notifications@github.com wrote:
The two combinators are indistinguishable in the model implementation. Unfortunately, I have found it necessary to distinguish them in the efficient implementation. This is because the IO type constructor is not a good MonadFix instance.
The following code demonstrates the issue. If we want to use the result for IO right away, then valueB is the right choice (testA1 vs testA2). If we want to use the result with value recursion, then valueBLater is the right choice (testB1 vs testB2). I have not been able to find an implementation that works in both cases.
{-# LANGUAGE RecursiveDo #-} module TestValueB where import Reactive.Banana import Reactive.Banana.Frameworks testMoment :: MomentIO a -> IO a testMoment m = fmap from $ interpretFrameworks (\e -> m >>= \x -> return (x <$ e)) [Just ()] where from [Just x] = x testA1, testA2, testB1, testB2 :: MomentIO Int -- works testA1 = do b <- stepper 0 never x <- valueB b liftIO $ print x return x -- fails, throws exception testA2 = do b <- stepper 0 never x <- valueBLater b liftIO $ print x return x -- fails, does not terminate testB1 = mdo x <- valueB b b <- stepper 0 never return x -- works testB2 = mdo x <- valueBLater b b <- stepper 0 never return x
— Reply to this email directly or view it on GitHub https://github.com/HeinrichApfelmus/reactive-banana/issues/108#issuecomment-168315014 .
I presume that valueBLater does not immediately get the value, but creates a mutable cell which is filled in at the end of the moment with the correct value, and that forcing the value before the end of the moment is an error.
Would it work if you take this behavior, but add that forcing the value (before the end of the moment) also causes it to observe the value?
I.e. the observation is done at most at the end of the moment, but earlier if the value is forced?
I presume that valueBLater does not immediately get the value, but creates a mutable cell which is filled in at the end of the moment with the correct value, and that forcing the value before the end of the moment is an error.
Yes, pretty much. In order to return an actual value, some IO actions have to happen. In particular, the argument Behavior has to be "built" and inserted into the graph. In the case of valueBLater
, these IO actions are deferred to until the end of the current Moment, as you presumed correctly.
Would it work if you take this behavior, but add that forcing the value (before the end of the moment) also causes it to observe the value?
In principle, that should be possible, but I found it hard to write code that does this. The main difficulty is that in order to get the actual values, some IO actions have to be performed. But the value is pure, so something along the lines of unsafeInterleaveIO
needs to be used. Unfortunately, these IO actions may trigger "building" the argument Behavior, which in turn may trigger other calls to valueB
. When using unsafeInterleaveIO
, all of this happens outside the normal ordering of IO actions, and I have no idea how to ensure correctness / atomicity in this case, where we have nested, interleaving, and potentially recursive actions.
That's why I've implemented a solution that is "good enough" and opened an issue. :smile:
I'm a bit confused. Would this work (in pseudocode)?
valueB b = scheduleForceAtEndOfMoment m >> return m where
m = unsafePerformIO $ readValueOf b
This gives bottom if value is forced before the behavior is defined, but this is consistent with the semantics, I think.
Yes, in principle, this would work. However, executing readValueOf b
may in turn make calls to scheduleForceAtEndOfMoment
, perhaps even recursively, depending on how the Behavior b
came to be in the first place.
Essentially, I would have to write a thing that can
unsafePerformIO
.I have not attempted to tackle the fourth point, because it seems very difficult to me, with little benefit.
I don't understand why readValueOf b might make calls to scheduleForceAtEndOfMoment. I assumed readValueOf b is just reading some mutable cell (which might change in the start of the next moment, but not before that).
Can you give an example where readValueOf b causes calls scheduleForceAtEndOfMoment (or something else)?
Also what do you mean with this?
... This is because the IO type constructor is not a good MonadFix instance.
Can you give an example where
readValueOf b
causes callsscheduleForceAtEndOfMoment
(or something else)?
Essentially, the trouble is that the Behavior b
is not simply a cell, rather it is itself an action, which happens in a special monad Reactive.Banana.Internal.Combinators.Moment
, which is a transformer stack on top of IO
. For instance, the definition of applyB
looks like this (e.g. in commit 429ae4cd29262ab24eea69346e5a486725ee55e7):
type Moment = ReaderT EventNetwork Prim.Build
type Behavior a = Cached Moment (Latch a, Pulse ())
applyB = liftCached2 $ \(~(l1,p1)) (~(l2,p2)) -> liftBuild $ do
p3 <- Prim.unionWithP const p1 p2
let l3 = Prim.applyL l1 l2
return (l3,p3)
Essentially, it says that Behavior
is built from a pair of primitive types Latch
and Pulse
. The Pulse
keeps track of when the Behavior changes, so that we can offer an efficient changes
function for binding to external UI libraries.
Latch and Pulse can only be "created" from within the Build
monad. For instance, "creation" for a Latch means that we call newIORef
to create the cell that holds the value of the latch, but also other things, like dependency information.
Now, what applyB
does is it caches the creation, so that we get observable sharing. In pseudocode, it looks something like this:
applyB bf bx = unsafePerformIO $ do
sharingDetector <- newIORef
return $ do
maybeCreatedAlready <- liftIO $ readIORef sharingDetector
case maybeCreatedAlready of
Just (latch, pulse) -> return (latch, pulse)
Nothing -> do
(l1,p1) <- bf
(l2,p2) <- bx
-- the following lines call
-- scheduleForceAtEndOfMoment
p3 <- Prim.unionWithP const p1 p2
let l3 = Prim.applyL l1 l2
liftIO $ writeIORef maybeCreatedAlready $ Just (l3,p3)
return (l3,p3)
The point is that new pulses and latches can only be created at the end of the Moment, so the lines indicated by a comment call scheduleForceAtEndOfMoment
.
Now, I'm not saying that unifying these two is wholly impossible. I think it is possible. But with my current setup, it's far from easy. Ultimately, the problem is that a Behavior is more than just an IORef that contains the current value, but also other things.
... This is because the IO type constructor is not a good MonadFix instance.
What I was referring to is that the class instance MonadFix IO
does not satisfy all the laws I want, though I have to admit that I'm not entirely clear on which laws these are. In any case, here is one recursive example in several different monads. For some monads, it terminates, but for some it doesn't, and this is bad for the issue at hand.
{-# LANGUAGE RecursiveDo #-}
import Control.Monad.Trans.State.Lazy
import Data.Functor.Identity
-- does not terminate
testIO :: IO ()
testIO = mdo
Just _ <- return b
b <- return (Just 'a')
return ()
-- terminates
testRecState :: ()
testRecState = runIdentity . fmap fst . flip runStateT (0::Int) $ mdo
Just _ <- return b
b <- return (Just 'a')
return ()
-- does not terminate
testRecStateTIO :: IO ()
testRecStateTIO = fmap fst . flip runStateT (0::Int) $ mdo
Just _ <- return b
b <- return (Just 'a')
return ()
(Just for reference, the articles that introduce MonadFix
, in particular "Recursive Monadic Bindings", can be found on Levent Erkök's website.)
Thanks, I see now why it's hard in this setup. On Jan 4, 2016 1:00 AM, "Heinrich Apfelmus" notifications@github.com wrote:
Can you give an example where readValueOf b causes calls scheduleForceAtEndOfMoment (or something else)?
Essentially, the trouble is that the Behavior b is not simply a cell, rather it is itself an action, which happens in a special monad Reactive.Banana.Internal.Combinators.Moment, which is a transformer stack on top of IO. For instance, the definition of applyB looks like this (e.g. in commit 429ae4c https://github.com/HeinrichApfelmus/reactive-banana/commit/429ae4cd29262ab24eea69346e5a486725ee55e7 ):
type Moment = ReaderT EventNetwork Prim.Buildtype Behavior a = Cached Moment (Latch a, Pulse ())
applyB = liftCached2 $ (~(l1,p1)) (~(l2,p2)) -> liftBuild $ do p3 <- Prim.unionWithP const p1 p2 let l3 = Prim.applyL l1 l2 return (l3,p3)
Essentially, it says that Behavior is built from a pair of primitive types Latch and Pulse. The Pulse keeps track of when the Behavior changes, so that we can offer an efficient changes function for binding to external UI libraries.
Latch and Pulse can only be "created" from within the Build monad. For instance, "creation" for a Latch means that we call newIORef to create the cell that holds the value of the latch.
Now, what applyB does is it caches the creation, so that we get observable sharing. In pseudocode, it looks something like this:
applyB bf bx = unsafePerformIO $ do sharingDetector <- newIORef return $ do maybeCreatedAlready <- liftIO $ readIORef sharingDetector case maybeCreatedAlready of Just (latch, pulse) -> return (latch, pulse) Nothing -> do (l1,p1) <- bf (l2,p2) <- bx -- the following lines call -- scheduleForceAtEndOfMoment p3 <- Prim.unionWithP const p1 p2 let l3 = Prim.applyL l1 l2 liftIO $ writeIORef maybeCreatedAlready $ Just (l3,p3) return (l3,p3)
The point is that new pulses and latches can only be created at the end of the Moment, so the lines indicated by a comment call scheduleForceAtEndOfMoment.
Now, I'm not saying that unifying these two is wholly impossible. I think it is possible. But with my current setup, it's far from easy. Ultimately, the problem is that a Behavior is more than just an IORef that contains the current value, but also other things.
... This is because the IO type constructor is not a good MonadFix instance.
What I was referring to is that the class instance MonadFix IO does not satisfy all the laws I want, though I have to admit that I'm not entirely clear on which laws these are. In any case, here is one recursive example in several different monads. For some monads, it terminates, but for some it doesn't, and this is bad for the issue at hand.
{-# LANGUAGE RecursiveDo #-}import Control.Monad.Trans.State.Lazyimport Data.Functor.Identity -- does not terminatetestIO :: IO () testIO = mdo Just <- return b b <- return (Just 'a') return () -- terminatestestRecState :: () testRecState = runIdentity . fmap fst . flip runStateT (0::Int) $ mdo Just <- return b b <- return (Just 'a') return () -- does not terminatetestRecStateTIO :: IO () testRecStateTIO = fmap fst . flip runStateT (0::Int) $ mdo Just _ <- return b b <- return (Just 'a') return ()
(Just for reference, the articles that introduce MonadFix, in particular "Recursive Monadic Bindings", can be found on Levent Erkök's website https://sites.google.com/site/leventerkok/.)
— Reply to this email directly or view it on GitHub https://github.com/HeinrichApfelmus/reactive-banana/issues/108#issuecomment-168556525 .
Note that
main :: IO ()
main = mdo
~(Just _) <- return b
b <- return (Just 'a')
return ()
does terminate, so it seems to be related to the strictness of IO
. Doesn't really change anything though, but gets us a bit more of an insight into what's going on!
The functions
are somewhat redundant. Unfortunately, the distinction seems necessary, because the two variants differ when it comes to recursion: The result value of
valueB
is available immediately, while the result value ofvalueBLater
is | until the end of the Moment.Maybe there is a way to unify them again?