Infinite recursion (stack blown) with mutual recursion in event streams

[ocharles]

Here is a minimal example program:

{-# LANGUAGE RecursiveDo #-}

import Control.FRPNow
import Control.Monad
import System.IO

main :: IO ()
main =
  do hSetBuffering stdin NoBuffering
     hSetBuffering stdout NoBuffering
     runNowMaster
       (mdo (keyPressed,keyPress) <- callbackStream
            -- State begins in state "1", and when a key is pressed it switches to state 2
            state <-
              sample (fromChanges
                        1
                        (2 <$ (keyPressed `during` (fmap (1 ==) state))))
            -- Whenever the state changes, print it
            callIOStream (print :: Int -> IO ())
                         (toChanges state)
            async (forever (getChar >>= keyPress)))

When ran, if you press any key the process begins using all the memory it can, until it blows the stack.

If I change fmap (1 ==) state to pure True it works fine, but obviously is a different program :) Perhaps a missing call to futuristic somewhere?

[ocharles]

Another example using snapshots:

{-# LANGUAGE RecursiveDo #-}

import Control.FRPNow
import Control.Monad
import System.IO

main :: IO ()
main =
  do hSetBuffering stdin NoBuffering
     hSetBuffering stdout NoBuffering
     runNowMaster
       (mdo (keyPressed,keyPress) <- callbackStream
            let toggles =
                  fmap not (snapshots checked (void keyPressed))
            checked <-
              sample (fromChanges False toggles)
            -- Whenever the state changes, print it
            callIOStream print
                         (toChanges checked)
            async (forever (getChar >>= keyPress)))

[ocharles]

I've continued to shrink the example down to try and see if I can solve the problem:

{-# LANGUAGE RecursiveDo #-}

import Control.FRPNow
import Control.Monad

main :: IO ()
main =
  runNowMaster
    (mdo run <- async (return ())
         let checked =
               pure False `switch` (fmap not checked <$ run)
         sample (whenJust (fmap guard checked)))

This might not make sense, because that might be basically saying

checked = not checked 

Using prev doesn't solve the problem though:

{-# LANGUAGE RecursiveDo #-}

import Control.FRPNow
import Control.Monad

main :: IO ()
main =
  runNowMaster
    (mdo run <- async (return ())
         let checked =
               pure False `switch` (fmap not lastChecked <$ run)
         lastChecked <-
           sample (prev False checked)
         sampleNow (whenJust (fmap guard checked)))

[atzeus]

Thanks, for the bugs. Which version of GHC are you using? I'm on holiday now, so it might take a while before I have time to fix this.

[ocharles]

This is 7.10.1. Out of interest, how long are you on holiday for? Not intended to be pushy, just curious when I should internally reschedule more frpnow experiments :)

[atzeus]

Ok 7.10.1 is also what I'm using. Till the 12 th of August I'm afraid. I'll contact you when I have more info. Cheers!

[ocharles]

No worries, have a great holiday! I'll carry on getting my hands dirty, it's good fun :)

[atzeus]

Great to hear that your enjoying messing around with this :)

Looking closer at your examples, I think all, except the last which uses prev, are expected to give bottom (i.e. infinite loop).

The confusion is understandable, since this is not yet described anywhere.

In FRPNow, a fixpoint is only defined if the value of a behavior at a time t does not depend on the value of that behavior itself at time t.

In your first example, the behavior state when the key is pressed at time t, is 2 if state is 1 at time t (the value of the behavior at time t depends on its own value at time t). In your second example, the same thing is happening: the value of checked when a key is pressed (at time t) is not the checked at time t.
In your third example, it is as you say:

checked = not <$> checked

Using prev should help however, there must be a bug in it's implementation, which I will try to fix now.

[atzeus]

In the meantime, try using delay from Control.FRPNow.Time, which delays the given behavior by one tick of the "clock" . Delay will always give you the value of the behavior at the previous event.

[atzeus]

I think your prev example can be simplified to:

mdo let i = not <$> j
    j <- prev False i
    ....

The expected behavior, I think is that i = pure True and j = pure False.
The difference with your example is that you get to this situation only after an event.

The problem is now that the event that i changes is the event that j changes is the event that i changes. Tricky!

[ocharles]

I think it's a shame if we do end up in this situation where it's possible to write infinite loops - we deal with this in reactive-banana by having events change instantaneously after behaviors. Eventually this all works out, and I haven't managed to build a looping program in r-b just by composing primitives (e.g., the above does work out as expected).

I'll have a play with Control.FRPNow.Time, I haven't looked at that yet.

[atzeus]

You have a point there, might be worth rethinking this behavior.

[ocharles]

https://stackoverflow.com/questions/26980819/why-does-changes-return-event-t-future-a/26996387#26996387 is the relevant Stack Overflow answer I was thinking of too, which shows that observing the changes to a behavior happens at a different time. There's also this documentation comment:

https://hackage.haskell.org/package/reactive-banana-0.4.2.0/docs/Reactive-Banana-Model.html#v%3astepper

Which goes with this longer SO answer: https://stackoverflow.com/questions/7850389/can-reactive-banana-handle-cycles-in-the-network/7852344#7852344

That might provide some food for thought!

[ocharles]

Paging @HeinrichApfelmus in case he wants to chime in :)

[HeinrichApfelmus]

The StackOverflow answers sum up my take on this pretty well. 😄

But actually, the idea of letting a Behavior have the old value for t <= t0 and take on the new value for t > t0 goes way back to Conal Elliott's original design. The consequence is that recursion is always possible as long as it is a mutual recursion between Behavior and Event.

In addition, I have found that this approach also solves a lot of problems when trying to do a push-driven implementation.