Unintended Dependency Cycles

[MattEWeber]

I'm not sure if this is a bug or a feature, but it struck me as counterintuitive. This reactor

target TypeScript;
reactor A {
    input x:number;
    output y:number;
    logical action a:number;
    reaction (startup) -> a {=
        actions.a.schedule(0, 1);
    =}
    reaction (x) -> a {=
        actions.a.schedule(0, x as number);
    =}
    reaction (a) -> y {=
        y = a as number;
    =}
}
main reactor Example {
    r = new A();
    r.y -> r.x;
}

has a cycle in its dependency graph. This very similar reactor

target TypeScript;
reactor A {
    input x:number;
    output y:number;
    logical action a:number;
    reaction (startup) -> a {=
        actions.a.schedule(0, 1);
    =}
    reaction (a) -> y {=
        y = a as number;
    =}
    reaction (x) -> a {=
        actions.a.schedule(0, x as number);
    =}
}
main reactor Example {
    r = new A();
    r.y -> r.x;
}

does not.

The cycle in the first example comes from the obvious dependency of reaction 2 on reaction 3, and the not-so-obvious dependency of reaction 3 on reaction 2 (because reaction 3 occurs later in the list of A's reactions than reaction 2). Swapping the order of the reactions in the second example removes the cycle.

But even with the dependency graph cycle, the first example should execute just fine because reaction 2 will never be on the reaction queue at the same time as reaction 3 due to the microstep delay on the action. Perhaps we shouldn't immediately discard all reactors with cyclic dependencies?

[lhstrh]

Neither example has a cycle in it. Also, the compiler isn't reporting any. The logical action always breaks the cycle, because it inserts (at a minimum) a microstep delay. Perhaps it is the runtime that is reporting a cycle? If so, we have a bug in the runtime.

[MattEWeber]

Yes this is being detected by the updatePriorities function in util.ts, not by the compiler.

But I brought this up here because the logical action doesn't break the cycle. In the first example reaction 2 depends on reaction 3 because of the connection between ports y and x. But reaction 3 depends on reaction 2 because reaction 2 comes earlier in the list of reactions than reaction 3.

[lhstrh]

OK. We should nonetheless move the issue to reactor-ts because the dependency graph is constructed at run-time for the TypeScript target.

[MattEWeber]

I believe this is the right place for this issue because it's about the spec. TypeScript appears to be constructing the dependency graph and analyzing it correctly to the spec. In fact this same issue of reaction ordering inside a reactor leading to an unintended cycle is discussed with respect to Figure 2 of the CyPhy paper. The paper goes on to say all cyclic precedence graphs must be rejected.

The question is whether automatically rejecting all cyclic precedence graphs is actually a good idea. My first thought is no, because the first example I gave above is both 1) very easy to write by mistake and 2) perfectly safe to execute. Should we consider altering the spec to allow such models?

The compiler doesn't report cycles for this because it's currently checking for a different kind of cycle. Right now it's only checking for cyclic reactor hierarchies to fix the issue Marten identified in #110.

[lhstrh]

I had overlooked the cycle you pointed out in the first example. You mean the cycle 2<-3<-2. Not detecting it in the compiler strikes me as problematic. Currently, only the C code generator builds a complete graph of the program and detects cycles (not just the ones discussed in #100). We may want to consider doing this for the other targets as well (even though they perform this analysis at run time), but I'm not sure that we do.

As to whether we should reject all cyclic dependency graphs, the answer should absolutely be yes. The dependency graph has to determine the schedule, and when it's cyclic we cannot decide which reaction has to go first. This example constitutes a proper causality loop.

There being a way to break the causality loop by shuffling the order of reactions to achieve a program that implements the behavior you want doesn't mean the compiler can do it for you. Reactions have side effects, so switching the order of reactions may change the meaning of the program, just like swapping assignments in an imperative program would.

That said, we are being overly conservative by arranging the reactions within a reactor in a total order. We've been considering relaxing this constraint, but we can only do this safely if state variables become part of the causality interface of reactions. Reactions that share no state variables can, as you suggest with your example, execute in any order with respect to one another. There is some cost associated with this, however, because it slightly increases the cognitive load for the programmer, but I personally think the pros may outweigh the cons on this one.

[edwardalee]

I think the cognitive load needs to be assessed not as the dealt increment, but more holistically. When reaction signatures start to look like this, we have a problem:

reaction (trigger) [state] uses -> effects {= ... =}

Each piece Is a small addition, but whole is overwhelming.

If reactions are not sharing state, shouldn’t they be in separate reactors? The above example is actually using the action a as a state variable, so it actually makes sense that the second reactor would work but not the first. The principle is that any reactor that breaks a feedback loop must produce outputs before it reads inputs. The first reactor above does not do that.

[lhstrh]

As for state declarations, I would just treat state the same way we treat ports; if the state is read, put it before the -> and if it is written to, put it after the arrow. In other words, the syntax would remain the same, we'd just require more things to be declared. This does imply that in C we'd have to use the set macro...

[lhstrh]

There is one other reason to be apprehensive about abandoning the total ordering of reactions within a reactor: physical side effects that are not necessarily accounted for by access to state variables.

[MattEWeber]

Rather than adding additional labeling for state, how about a new keyword that signifies a reaction's order in its reactor's list of reactions can be safely ignored? Such a reaction would get no edges in the dependency graph resulting from reaction precedence. We could name the keyword something like unordered, nopriority, priorityfree, free, or anytime. As in:

free reaction (x) -> a {= =}

We're already trusting the programmer to correctly label other dependencies, so why not trust them here to label a lack of dependency?

Whatever we decide, my primary concern about the examples above is how easy it is to accidentally introduce a dependency cycle and not see the problem. This issue is likely to come up in any reactor with feedback. If I missed it and Marten missed it and we're developing the language, what hope does a layperson have? Whatever we decide to do about it, I think we need to write explicit documentation for this issue and how to fix it.

[edwardalee]

Another possible solution is in the graphical rendition. Right now, the order of reactors is indicated by number. Suppose that the layout were constrained to order them top-to-bottom and display a downward arrow between them. Then in the graphical rendition, the cycle would have been obvious.

[lhstrh]

We're already trusting the programmer to correctly label other dependencies, so why not trust them here to label a lack of dependency?

This is not true. We don't trust the programmer; if a dependency is omitted a compile error results. Adding a keyword to denote unordered reactions is prone to abuse. People will start to always use unordered reactions because the ordered ones "don't work" for reasons they don't care to understand.

Making dependencies on state explicit also has other advantages. It enables optimizations in memory management, for instance. I think we should seriously consider this solution. I also realized that the issue about physical side-effects not being indicated by dependencies on state can be addressed with the realtime modifier, which could force the ordering of reactions to be total.

Rendering the graphical representation the way you suggest, Edward, is very difficult to achieve with the rendering engine we use. Also, this only addresses the issue for those who work in the dedicated IDE and have enabled diagram plugin. It won't do anything for those who didn't enabled it or use the command line tools exclusively.

[MattEWeber]

I like the idea of graphically depicting arrows to signify reaction precedence. Sure, it wouldn't do anything for people who don't use the IDE, but it would help the people who do. Would it be difficult to just draw the arrows without changing the layout?

Regarding programmer trust: missing dependencies may be caught by the compiler but I don't believe extraneous dependencies are. Our hypothetical lazy programmer could make every reaction depend on every input, and capable of writing to every output. My point isn't that everyone's going to actually do that, but there's a certain level of trust we have to give the programmer to write a program that actually does what they want.

If our job is to help programmers avoid mistakes, I think forcing every reaction to be ordered even if the programmer doesn't want it to be ordered is going to cause more mistakes than it will prevent. I don't believe we have a single example in our (admittedly simplistic) test suite where reaction order affects correctness. Reaction order is something that doesn't matter at all 90% of the time until you're trying to fine-tune a sequence of reactions with modifications to state. That's why it's surprising to find these accidental cycles when you've been ignoring priorities for so long.

[lhstrh]

I like the idea of graphically depicting arrows to signify reaction precedence. Sure, it wouldn't do anything for people who don't use the IDE, but it would help the people who do. Would it be difficult to just draw the arrows without changing the layout?

It would be difficult to enforce a vertical ordering. We could add dotted arrows between reactions but that would likely result in clutter...

Regarding programmer trust: missing dependencies may be caught by the compiler but I don't believe extraneous dependencies are.

That is correct. This is a conservative approach. Spurious dependencies are generally not a problem (aside from them potentially introducing unintended cycles).

Our hypothetical lazy programmer could make every reaction depend on every input, and capable of writing to every output.

That strikes me as the opposite of lazy, but it wouldn't hurt correctness. It may hurt performance. This is the way causality interfaces are used in Ptolemy II, actually: all outputs are assumed to depend on all inputs, unless specified otherwise. There is not check on the soundness of these relaxations, however.

If our job is to help programmers avoid mistakes, I think forcing every reaction to be ordered even if the programmer doesn't want it to be ordered is going to cause more mistakes than it will prevent.

I disagree. Not ordering them makes the model nondeterministic. Getting a compile-time error (or run-time error at startup) that is resolvable is not nearly as problematic. If anything, I'd suggest we focus on improving the error message.

Reaction order is something that doesn't matter at all 90% of the time until you're trying to fine-tune a sequence of reactions with modifications to state.

I disagree. It is needed to guarantee determinism.

[lhstrh]

There may be a way to visualize this better without creating a spaghetti of dependencies. If we indicate order-imposed dependencies with dotted lines that connect from the mid bottom of one reaction to the mid top of the next, this may give the automatic layout engine enough hints for it to produce an aesthetic rending. We'll have to experiment with it...

[edwardalee]

I agree that reaction order is essential. When it doesn’t matter, the programmer should create separate reactors.

[cmnrd]

I also stumbled across this issue recently while using the C++ backend. I had some more complex reactors and it took me a while to figure out what the issue is and where the cycle comes from.

I agree that reaction order is essential. When it doesn’t matter, the programmer should create separate reactors.

Does this mean that there should be a keyword on the reactor declaration? Maybe stateless that the reactor is not allowed to have state?

I think it might still be worthy to be able to declare for individual reactions whether they use state or not. While it certainly works to move stateless reactions to dedicated reactors, it might break the conceptual dependencies between reactions. It often makes sense to group related functionionality (reactions) within the same entity.

Regardless of whether it is possible to change the order of stateless reactions, the issue outlined above remains. If reaction (x) -> a and (a) -> y both use state, the compiler cannot simply reorder them. As Marten pointed out, this should be at least reflected in a better error message. Maybe suggesting to reorder the affected reactions.

That said, I am wondering how important the order of reactions actually is. Of course it is crucial for the model, but is it a common use-case that the programmer cares about the order? So far, I didn't consider the order of reactions at all when writing reactor programs. Would it be an option to sort the reactions automatically by the compiler (in a way that avoids cycles) and give the programmer the option to specify the order if it is relevant?

[edwardalee]

A compiler that changes the logic of a program makes me nervous. If you reverse the order of two updates of a state variable, you get different results.

Maybe part of the problem here is that reactors are being used as modules. Maybe a better solution would be to have a module system in Lingua Franca so that a group of related reactors can be collected in a module, rather than a group of related functions being collected into a reactor.

[cmnrd]

I don't really see how placing the reactions in multiple reactors would solve the issue. For the reactor given in the first post, I don't see a way of achieving this. But maybe I am missing something.

Maybe it was a bit radical to propose automatic reordering of reactions in the compiler. I think a better place to do this would be the Eclipse IDE. If the validator detects a cycle, the IDE could propose a reordering that solves the issue. This way the programmer still has full control (she could simply reject the proposal). I think in many cases such a reordering would be very helpful and ther could even be a button to trigger it. At least for me, it is very difficult to reason about the order of reactions and the implications this might have. Having a tool that assists the programmer could be invaluable.

[edwardalee]

I agree that we need better feedback to the programmer. But I really don't see any way to automate the transformation. To know whether a reordering of reactions is correct, you have to know that the reactions do not interact with any shared objects, either state variables of the reactor or side effects in the environment (e.g. printf, actuators, writing to files, etc.). This happens to be true of the original example, but how could a tool know that it is true? It will have to analyze the target code and all procedures that the target code calls. Suppose the target code invokes OS libraries to append to a file? Suppose it invokes code in a random Node module? Suppose that Node module invokes native C code? I just don't see any safe way to do this.

[lhstrh]

It should be easy to detect cycles that involve two or more reactions within the same reactor. The question is whether we want to do this analysis/reporting in the compiler or in the runtime for targets like TS or Cpp.

On Tue, Mar 10, 2020 at 9:33 AM Edward A. Lee notifications@github.com wrote:

I agree that we need better feedback to the programmer. But I really don't see any way to automate the transformation. To know whether a reordering of reactions is correct, you have to know that the reactions do not interact with any shared objects, either state variables of the reactor or side effects in the environment (e.g. printf, actuators, writing to files, etc.). This happens to be true of the original example, but how could a tool know that it is true? It will have to analyze the target code and all procedures that the target code calls. Suppose the target code invokes OS libraries to append to a file? Suppose it invokes code in a random Node module? Suppose that Node module invokes native C code? I just don't see any safe way to do this.

— You are receiving this because you modified the open/close state.

Reply to this email directly, view it on GitHub https://github.com/icyphy/lingua-franca/issues/114?email_source=notifications&email_token=AEYD47CWNZA72T4ANASTUM3RGZTU5A5CNFSM4LDLUFV2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEOME7YQ#issuecomment-597184482, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEYD47EWDFGF4F5FBC6JSXLRGZTU5ANCNFSM4LDLUFVQ .

--

-- Marten Lohstroh, MSc. | Ph.D. Candidate University of California | 545Q Cory Hall Berkeley, CA 94720 | +1 510 282 9135

[MattEWeber]

@edwardalee You could know it's safe to reorder reactions if they were labeled with the unordered keyword I suggested above. Here's a concrete proposal for how unordered reactions could be implemented as syntactic sugar to be handled in the code generator without changing anything about how priorities work.

Starting with the original example with a dependency cycle:

If the programmer were to label reaction 3 above as unordered, the code generator could make the following transformation:

The key point is we've wrapped the reaction we want to be unordered inside a container where it 1) doesn't have any priority relationships with A's other reactions and 2) doesn't have access to any of A's state. It doesn't have access to any of A's actions or ports either, but we can fix that with the following steps:

1. Create input and output ports on the contained reactor and wire them to A's ports of the same name
2. Translate A's actions into messages sent and received on the container's ports. This can be accomplished by creating an "action helper" reaction (this is reaction 1 in the transformed diagram) which is triggered by actions needed by the unordered reaction. The action helper writes the value on that action into the contained reactor's input port. For example where a is an action:

reaction (a) -> container.x {=
    container.x = a;
=}

If the unordered reaction needs to schedule an action (which is not shown in this example), it produces scheduling information for those actions which is sent through contained reactor outputs to another action helper reaction in A where the action is scheduled. Note, that these "action helper" reactions have to be highest priority within A or else they could just introduce a new dependency cycle.

I think it would be a lot easier to just not give an unordered reaction edges ordering dependencies to other reactions and prevent the unordered reaction from using state, but I wanted to show how this outcome is isomorphic to a transformation resulting in a standard reactor, and just as deterministic.

[MattEWeber]

Since we're all now aware of these concerns, I propose tabling the discussion of reaction ordering until we have larger practical reactor programs. Then we can better evaluate what's actually a problem. Maybe better error reporting will fix all the practical problems.

[lhstrh]

Error handling has been improved. Error messages now clearly indicate where the cycles are, and even make suggestions to reorder reactions where appropriate. Comments and feedback are welcome.

I've also been working with @a-sr to improve the error reporting in the diagram synthesis. We're getting close to a solution but are not quite ready to take in feedback on that particular error reporting mechanism.

[lhstrh]

Support for cycle highlighting in the synthesized diagrams has also been implemented.