#260 Allow recursion in Function Definitions

[Lucian Smith]

From an email from Andy Somogyi:

I have some users who have a multi-compartment synapse model, and diffusion is treated as a Green's function -- its cylindrical geometry so its defined by Bessel functions. Bessel functions are obtained through recursion.

They have a very definite need to allow recursive functions.

It does not break the standard in any way. Maybe we can add an optional attribute of recursive to function definitions? This way, macro expanding systems can safely avoid such functions?

---

This recursion is used in e.g. piecewise functions; it is not infinite recursion.

[Michael Hucka]

There is one more possible L3v2 change that came during Harmony but was not discussed, and that's the idea of allowing recursion in user-defined functions. (See below.)

The original requirement to avoid recursiveness in function definitions was to make it possible for simple systems to treat function definitions as macros. It's not clear whether this is still an important consideration for software tools today. Does anyone have a sense for that?

The request here suggests adding an attribute to indicate whether a function is recursive. That's one option. Altogether, I think there are 3 alternative answers to this proposal:

1. don't do it; leave SBML function definitions as they are.
2. allow SBML function definitions to be recursive in L3v2.
3. add a flag that indicates whether a given function is recursive.

What are people's opinions on this?

[Nicolas Le Novère]

I would vote for 3 (and therefore 2), to help a software to decide if it can use or not the functions.

[Michael Hucka]

I suppose we should add a 4th option, based on Sven's suggestion that there could be a completely different type of object (e.g., RecursiveFunction). However, for the reasons that I outlined in the editor list email to that suggestion, it does not appear to be materially different from option #3 here.

I personally prefer #3.

[Lucian Smith]

With a clear use case, a single vote in favor, and a second non-binding-but-influential argument in favor, I have taken the liberty of incorporating option 3 into SVN for the L3v2 specification. If officially accepted, it will be released with that specification, and if not, the changes will be reverted.

[Chris Myers]

How do we ensure that there is not infinite recursion? What would such a function look like? It needs to be clear somehow that the function will not recurse forever? I'm guessing there must be some sort of piecewise involved.

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.

Chris

[Lucian Smith]

I could be wrong, but I believe that "figuring out if a recursive function loops infinitely or not" is one of those unsolved CS problems, if not one of those known-to-be-unsolvable CS problems. In our case, we could at least check to see if the recursion happened inside a 'piecewise' function, which I believe is the only if/else kind of statement we have in our MathML subset. If I'm right, it would be necessary, but not sufficient, for the recursion to happen inside a piecewise function for it to not be infinitely recursive.

This doesn't really answer your question, of course. My own inclination is to just say 'don't do infinite recursion' in the spec, and then validate that as best we can in our software support tools (libsbml, jsbml) with checks for piecewise, etc.

However, I could see a case for doing something similar to what we do for events, which is (as you know, Bob):

"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."

Or we could do both, and say, "Don't write infinite recursion in your models, and if you're a simulator and think you're in that situation, bail and tell the user you've done so."

[Chris Myers]

I think it is fine to leave this to the simulator to detect. We cannot prevent all bad models syntactically.

If we agree on this, I think we should also allow recursive assignment rules.

Chris

[Lucian Smith]

OK, I'm going to open a new issue about recursive assignment rules. There are some issues surrounding that, that are different from the issues about recursive function definitions.

[Lucian Smith]

Done: https://sourceforge.net/p/sbml/sbml-specifications/269/

[Lucian Smith]

As per Chris's comments, added language about what a simulator should do if it encounters infinite recursion:

"Recursive functions must terminate, as through the use of a 'piecewise' function. However, it is not always possible to determine this through a validation analysis. A simulator may therefore need to break a cascade of recursive functions arbitrarily in the middle of a simulation. If this happens, the simulator should indicate that this has occurred, and may proceed, or not, as seems fit. It is incorrect for a simulator to break recusion arbitrarily and continue without at least indicating that the infinite recursion occurred."

[Chris Myers]

Text looks good.

Chris

[Brett Olivier]

So the value of returned by this function is then tool dependent (resource availability, precision, programming language)? Maybe adding a "maximum recursion depth" attribute could get around some of the uncertainty.

[Frank Bergmann]

While I see the issue as valid, it is highly problematic. I am against adding this by simply adding a boolean attribute 'isRecursive'.

I still would prefer not to add recursive functions at this point. If we do, i would use a new element RecursiveFunctionDefinition, maybe adding the 'maximum recursion depth' attribute that brett suggest. That would go on a new element.

[Brett Olivier]

I am not in favour of allowing functions to become recursive based on a single use case. Something like Frank describes above might work.

[Lucian Smith]

OK, the current voting stands at Nicolas voting to allow recursive function definitions with a boolean attribute indicating this, and Frank and Brett voting against this, though with tentative approval of some sort of separate scheme for functions. Sven and Dagmar, this means we need your input.

Personally, I believe that a completely new construct ('RecursiveFunctionDefinition') would not be the way to go, as it would require completely new machinery to connect it to the mathML.

However, a package or custom annotation could do the job instead relatively straightforwardly, replacing the existing $child\; of\; FunctionDefinition\; with\; something\; new--perhaps\; \text{'}relaxedMath\text{'},\; that\; would\; allow\; both\; recursion\; and\; reference\; to\; global\; variables.\; This\; would\; be\; particularly\; clear\; in\; L3v2,\; where\; FunctionDefinitions\; no\; longer\; need\; a\; child\; \text{'}math\text{'}\; object\; at\; all.\; Something\; like:$

<functionDefinition id="foo">
  <relax:relaxedMath>
    <math xmlns="http://www.w3.org/1998/Math/MathML">
      <lambda>
        <bvar>
          <ci> y </ci>
        </bvar>
        <apply>
          <plus/>
          <ci> y </ci>
          <apply>
            <ci> foo </ci>
            <ci> x </ci>
          </apply>
        </apply>
      </lambda>
    </math>
  </relax:relaxedMath>
</functionDefinition>

(that particular function wouldn't resolve, but you get the idea).

[Dagmar Waltemath]

I am undecided and feel I am not experienced enough to make a decision here (especially as the vote is so close), sorry.

I would tend towards allowing recursive functions (as there is apparently a user's need). I would not introduce an additional attribute, but prefer an annotation to store that information, so my (vague) tendency is towards option (2) allow SBML function definitions to be recursive in L3v2.

However, I will feel more comfy if Sven steps in and helpa making the decision.

[Michael Hucka]

It's true that adding a boolean flag to FunctionDefinition would mean every function definition would need a value for it, making FunctionDefinition objects no longer forward-compatible between L3v1 and L3v2 (because L3v1 FunctionDefinitions would never have the flag yet L3v2 ones would be invalid without it, so converting an L3v1 model to L3v2 would entail more than simply changing the version number on an L3v1 file).

Although it seems crazy-redundant to have an entirely different object for recursive functions, I can understand the appeal for this reason, and so I would accept the introduction of a RecursiveFunctionDefinition.

Perhaps the RecursiveFunctionDefinition could have a mechanism to also allow local variables, per tracker issue #277 (https://sourceforge.net/p/sbml/sbml-specifications/277/)? If we're going to introduce a whole new object type, then may as well knock two birds out of a tree with one stone.

[Lucian Smith]

By common consent at the 2015 SBML Editors' meeting, we decided that it was not clear what the best conclusion was, nor what the extent of the need might be for this type of construct. We also need to know the extent of implementor willingness to implement such a scheme. We will poll the community to see what the majority opinion there is. We will also poll about the recursive assignment rules.

[Lucian Smith]

After further discussion, it was decided to go ahead and close this issue, but still poll the community and mention that anyone could define new lightweight custom extensions (annotation or package-like) that let SBML behave as they want, including this issue of recursive function definitions (or recursive assignment rules, etc.)

[Lucian Smith]

It was agreed to not incorporate this into l3v2, which is now released. It can be re-suggested if desired for a later SBML level/version.