#269 Allow self-referential Assignment Rules


From Chris, on https://sourceforge.net/p/sbml/sbml-specifications/260/ :

We have a similar problem, we would like to be able to create an assignment rule like this:

TetR = piecewise(1, (IPTG==1) or (not (aTc==1) and (TetR==1)), 0)

This models the genetic toggle switch in a Binary fashion. Namely, if you add IPTG, you set TetR high, but when you remove IPTG, you continue to get TetR high due to the feedback in the assignment rule. Only once you set aTc high, does TetR go away.

This is currently illegal because it appears to be a recursive assignment rule. However, this does converge, but you only know this because you execute it and find that it does so. If you have this instead,

TetR = piecewise(1, (TetR==0), 0)

You get an oscillation. So, is this a modeling error or a validation error. You can cause the same problem when simulating events,

Event E0
Trigger TetR == 0
Delay 0
Assignment TetR = 1

Event E1
Trigger TetR == 1
Delay 0
Assignment TetR = 0

This will also bring simulation to its knees, but this is not illegal SBML.

So, I guess what I'm saying is that if we allow recursive function definitions, and they can only be proven to terminate by simulation, this is not any different than what we are already allowed to do with 0 delay events and what we perhaps SHOULD be allowed to do with assignment rules that can reference themselves.


  • Lucian Smith

    Lucian Smith - 2014-06-27

    Even though (I think) you are not claiming that we should allow recursive functions that converge, like

    x := x/2

    (which converges to zero), but only allow it in the boolean test sections of the 'piecewise' function, I think, on balance, that we should not allow this. The reason is that even though, as you say, we already allow infinite recursion for events, the way people implement support for events is to have an event queue that you add things to and take things away from. As such, it is relatively simple to have an arbitrary cutoff of a large number of events, on the queue at once, and say 'I think we've reached infinite recursion; stopping.' Similarly, if we allow recursive function definitions, those function definitions can be treated like programming functions, and you can check how many recursions you've had so far, and cut that off after an arbitrary number.

    In contrast, assignment rules are, as currently defined, 'fire and forget'. While an assignment rule update might cause an event to fire or a fast reaction to have to adjust, those are different systems that have their own support structures. Having to suddenly include assignment rules themselves into a category of 'things that might update themselves' would be, IMO, a major structural change in how people implement SBML support.

    Finally, at least for the specific use-case you posted, there are other structures in SBML that could model the exact same system just as well (and, IMO, more cleanly):

    E0: at(IPTG==1), t0=false: TetR = 1;
    E1: at(aTc==1 && IPTG==0): TetR = 0;

    Or you could go whole-hog and do it with reactions and reaction rates.

    I think the problem of not knowing if you converge or not is actually fairly significant, and one we should avoid if at all possible.

    • Chris Myers

      Chris Myers - 2014-06-27

      I disagree. Allowing recursive functions is going to cause at least as much if not more headaches than self-referential assignment rules.

      Assignment rules are not fire and forget. You have to actually order assignment rules based on the acyclic graph they imply OR you must iterate the updates up to the number of assignment rules you have. For example:

      Z = 2Y
      Y = 2
      X = 2*W

      If you fire the assignments in this order, you may need to iterate three times until it converges. However, you could reorder them and fire it once:

      X = 2W
      Y = 2
      Z = 2*Y

      In this case, one pass is sufficient. Therefore, you either loop #assignmentRules times OR you sort. In the first case, if you don't have convergence, you would report, in the second case, you would detect the cycle and realize you must check convergence. This is not any more of a burden than making me check the depth of a function call recursion.


      Last edit: Lucian Smith 2014-06-27
  • Michael Hucka

    Michael Hucka - 2014-06-27

    I think Chris does not mean to limit nonrecursion it to when 'piecewise' is used in the math. That would be a pretty specific special case.

  • Michael Hucka

    Michael Hucka - 2014-06-27

    Let's step back for a moment and reflect on what the SBML spec is trying to do with the restrictions on circular dependencies.

    A model that contains infinite recursion seems invalid as a model, in a manner similar to how an overconstrained model is invalid: it can't be simulated properly. However, unlike the case of overconstrained models, detecting infinite recursion is difficult. The explicit statements in SBML about avoiding referential loops are there precisely because you can't, in the unrestricted case, detect infinite recursion via static software analysis. (This is the Turing halting problem.) So, what we did in SBML originally is restrict the permissible constructs so that it would be possible to detect infinite recursion syntactically. This originally did not seem to be a significant limitation on the models that people could express -- one could presumably rewrite the assignments in a model to make it work out.

    I'm surprised we didn't catch the loophole involving events that Chris points out; maybe it was something that got changed at some point. More interesting, however, is that Chris's example involving TetR points out the following: the way someone might want to write their model in a natural way is currently prevented by these restrictions in SBML.

    So, at this juncture, I think we have the following options:

    1. Express the prohibition against infinite recursion by resorting to behavioral rules: the syntactic restrictions could be lifted, and instead, the validation rules could say something general about how the model should not contain infinite recursion when taken as a whole. This means that a syntactic analysis of a model won't be able to catch infinite recursion. (But, in reality, because of events, it can't do that now anyway.)

    2. Go the other way and tighten up the restrictions further, to ensure that syntactic analysis can be used to detect infinite recursion. This might mean adding a validation rule involving events.

    • Chris Myers

      Chris Myers - 2014-06-28

      I cannot think of a good argument as to why we allow recursive functions, but then not allow self-referential assignment rules. To me, they are essentially the same thing with the same simulation challenges. As for events, I don't think we can limit them in any way that would prevent "zeno" (time convergent) behavior. With events, you can I believe build Turing machines which takes us to "undecidability" land.

      As for the concern about simulation being "tool dependent", the fact of the matter is that a simulation of anything but the simplest model is always going to be somewhat "tool dependent". When you are running a program and it becomes non-responsive, and you then quit, you will never know if it would have eventually halted. The same is true here. The behavior is simply the tool will get stuck in simulation. A good tool developer will detect this situation and exit gracefully. A bad one will have a tool that crashes on the model.

      Therefore, I'm inclined towards option 1 below, but I'm not strongly against leaving things as they are. However, I would be against recursive functions but not allowing self-referential assignment rules as that seems completely contradictory.


      Last edit: Lucian Smith 2014-06-28
  • Frank Bergmann

    Frank Bergmann - 2014-06-28

    I accept this issue as valid, but would opt not to allow self-referential assignment rules.

    Chris is right though, that if one were to allowing recursive function definitions is just as bad (and I'm against allowing that in an unrestricted fashion as well). I also see no way of writing the events to prevent something like outlined above.

  • Nicolas Le Novère

    I vote for lifting the restriction. It is part of a "how to model" and not "how to encode the model" and therefore should not be part of our mission. If all sofware fail in the recursion, this is reproducible ...

  • Dagmar Waltemath

    I accept this issue as valid. I vote for option one, as suggested by Mike:

    1. Express the prohibition against infinite recursion by resorting to behavioral rules: the syntactic restrictions could be lifted, and instead, the validation rules could say something general about how the model should not contain infinite recursion when taken as a whole.
  • Lucian Smith

    Lucian Smith - 2014-07-09

    If we take Brett's comments on FunctionDefinition recursion (issue 260) as indicative of his feeling on this issue as well, we would again have a 2:2 split on this issue, making Sven's vote the deciding one (or Mike's, if Sven decides to abstain).

    As a single point of clarification: it was not the case that infinite event recursion slipped into the spec without being considered; there is explicit text that states:

    "A cascade of events can be potentially infinite (never terminate); when this occurs a simulator should indicate this has occurred—it is incorrect for a simulator to break a cascade arbitrarily and continue the simulation without at least indicating that the infinite cascade occurred."

    It doesn't actually say, "Also, don't write your models that way, you jerks," so there's no validation rule about it. In fact, if I recall correctly, there's a model either in the test suite or on biomodels.net with events that converge but do not terminate (Zeno-like), and simulators have to break out of the recursion at some point before they can finish the simulation (it has to do with taking increasingly tiny time steps, as two values converge while another oscillates between them).

  • Michael Hucka

    Michael Hucka - 2014-07-11

    I'm not terribly happy about the additional complexity this implies, but I am swayed by Nicolas and Chris' arguments in this case, and would vote to allow this construct. (So, my option #1, or some semblance thereof.)

  • Sven Sahle

    Sven Sahle - 2014-08-06

    I`m hesitant to even accept this issue, but do so (otherwise there would be nothing to discuss).

    I do not consider the fact that endless recursion can occur with events as a newly discovered loophole. It was always clear that one event can immediately trigger another event (with no delay in between but with a well defined order), and I thought it was always implied that this could lead to an infinite number of events.

    I also do not think that an assignment rule should mean "assign repeatedly until convergence". Rather I understand it as "make sure that the target variable always has the value specified by the expression". I realize that this is little ambiguous in that the name "assignment rule" seems to imply that it is equivalent to an assignment in a programing language, but I think it is not. I think of an assigmnet rule as a sort of special case of an algebraic rule.

    So my vote is for not allowing recursive assignmet rules, and not to do anything about not terminating event evaluations.

  • Brett Olivier

    Brett Olivier - 2014-08-06

    Just to confirm, my vote is not to allow recursive assignment rules.

  • Lucian Smith

    Lucian Smith - 2014-08-06
    • status: open --> closed
    • Group: Reported-Proposed --> Rejected-No_action
  • Lucian Smith

    Lucian Smith - 2014-08-06

    OK, that's a majority of editors who have indeed voted against making this change. Marking this 'closed' and 'rejected/no action'. Thanks, everyone! As a note, we still have yet to close the other recursion item, about recursive function definitions: https://sourceforge.net/p/sbml/sbml-specifications/260/; Sven, can you vote on that as well? Thanks!


Log in to post a comment.