Successful evaluation for an undefined network about reactive-banana HOT 5 OPEN

Question: is the Graph data structure meant to be a DAG?

Yes, it's meant to be a DAG.

If so, perhaps insertEdge should just call error instead of making a cycle?

That would be nice — but we would have to detect that there is a cycle. 😅 This can be done with a depth first search, but that is an expensive operation in that it needs to visit all the vertices on the putative cycle. I'm currently not aware of an algorithm that keeps track of the transitive closure and can do incremental updates that are faster than this. 🤔

That said, it may be possible to detect the cycle while the Event is turned into a Pulse, as this process does involve a depth first search of sorts anyway.

from reactive-banana.

Hm. Let's digest the call to doStep. If onStart does not have an occurrence, then the state change for onStateChange should be

(Nothing, ["Hello"]) → (Just "Hello", [])

but this invalidates the assumption that onStart does not occur. On the other hand, if both onStart and onState have an occurrence, then the state change for onStateChange should be

(Nothing, ["Hello"]) → (Nothing, ["Won't see me!"])

and this invalidates the condition for onStart to occur.

This looks like a classic let x = not x paradox and I agree that it should be outlawed. It's probably possible to shrink this example to use only Bool, that would make for a useful unit test.

How does the model implementation behave for this example?

Internally, it seems that the Reactive.Banana.Prim.Plumbing.dependOn function does not notice when a cycle of event dependencies is being created.

from reactive-banana.

Question: is the Graph data structure meant to be a DAG? Its docs only mention being directed, but seems to have an API that relies on it being acyclic, too (e.g. walkSuccessors claims to visit a vertex only after all of its predecessors are visited).

If so, perhaps insertEdge should just call error instead of making a cycle? (And would that fix this issue?)

from reactive-banana.

That said, it may be possible to detect the cycle while the Event is turned into a Pulse, as this process does involve a depth first search of sorts anyway.

@HeinrichApfelmus could you provide some guidance on where in the code one might find an Event turning into a Pulse, with this depth-first-search-of-sorts nearby? I'm interested in tackling this issue, to the extent that it can be tackled, but (as usual) the code is all a little over my head 😃

from reactive-banana.

@HeinrichApfelmus could you provide some guidance on where in the code one might find an Event turning into a Pulse, with this depth-first-search-of-sorts nearby?

That's a tough one. 🤔 The best I can do in a pinch is to point you to the documentation of observable sharing in the design document: https://github.com/HeinrichApfelmus/reactive-banana/blob/master/reactive-banana/doc/design/design.md .

The issue is that the Cache type supports arbitrary recursion and cannot distinguish between Event → Behavior → Event (allowed) and Event → Event (disallowed).

If you look at the implementation of Reactive.Banana.Prim.High.Combinators.mapE and friends, you will find the function liftCached1 which eventually results in a call to Reactive.Banana.Prim.High.Cached.cache. This functions pretends that the monadic action that creates the Pulse will succeed, and caches its value for recursive use. This is necessary to handle the case of a Event → Behavior → Event recursion, but unfortunately, it also yields a result when recursing Event → Event; the problem is that this result is now semantically unsound.

The only viable solution is to reify the issue in the structure of the code somehow. In other words, one would probably need two distinct Cache types — one for Event, one for Behavior — in such a way that mutual recursion between them is allowed, but recursion within a type is forbidden.

from reactive-banana.