MaxDestroyerEvents

[maxitg]

The problem

In project Yellowstone, the format for Multihistory generators will be

Generator[System[rules_], generatorArgs] @ init

Some possible choices for Generator would be GenerateSingleHistory and GenerateFullMultihistory (or GenerateAllHistories). These allow one to select between generating a single or a multihistory.

However, we need a generator that can interpolate between them such as

GenerateMultihistory[system_, selectionCondition_, ordering_, stoppingCondition_]

In order to switch between single and multihistories, we will need to specify "MaxDestroyerEvents". If "MaxDestroyerEvents" -> 1, it's a single history, and if "MaxDestroyerEvents" -> Infinity, it's a multihistory.

So, to implement GenerateMultihistory completely, we need "MaxDestroyerEvents" stopping condition which we don't currently have.

Possible solution

Before GenerateMultihistory is implemented, we can add "MaxDestroyerEvents" as a WolframModel stopping condition, e.g.,

WolframModel[{{1, 2}, {2, 3}} -> {{2, 3}, {2, 4}, {3, 4}, {2, 1}},
             {{1, 1}, {1, 1}},
             <|"MaxEvents" -> 5, "MaxDestroyerEvents" -> 2|>,
             "EventSelectionFunction" -> "MultiwaySpacelike"]

To implement this, one will need to roughly do the following:

In C++,

1. Get rid of SystemType and pass maxDestroyerEvents instead to the Set initialization.
2. Add an instance variable to CausalGraph to track the number of destroyer events per expression.
3. In Set::replaceOnce, modify the following code to perform matcher_.removeMatchesInvolvingExpressions and related operations once the limit from step (2) is reached: https://github.com/maxitg/SetReplace/blob/9d3d7fb3f1d405a25c208c7a1b03a69223b95ae2/libSetReplace/Set.cpp#L102-L111

In Wolfram Language:

1. Add another step spec to setSubstitutionSystem.m (and, as a result, to WolframModel).
2. Pass it as an extra parameter to the second argument of $cpp$setReplace in setSubstitutionSystem$cpp.m.

Additional context

Implementing GenerateMultihistory itself is a big refactoring and is separate from this feature (although requires it). There will be another issue for that.

[daneelsan]

@maxitg What would be the difference between passing maxDestroyerEvents to setInitialize instead of just passing it to setReplace as the other stepSpec?

Also, is "EventSelectionFunction" -> "MultiwaySpacelike" necessary if I specify "MaxDestroyerEvents"?

[maxitg]

@daneelsan,

If you pass something to setInitialize, you can assume that it is constant and won't change during the evolution. If you pass it to setReplace, you will have to expect that it can change in subsequent calls to setReplace. There is nothing wrong with that, however, it's more difficult to implement (and we don't use that functionality from WL yet).

For example, let's say someone starts by running a single-way system, for which it's not necessary to keep track of expression separations. Then, one would continue evolving it as a multiway system. At this point, the C++ implementation will have to go back and compute all the separations before it can continue with the evolution. We will need to be able to do that once we allow multihistories to work as inits, but it's out of scope for this PR because it will require being able to change the rules, the ordering function, etc. as well.

And yes, for now, "EventSelectionFunction" -> "MultiwaySpacelike" will be necessary, but it won't be in GenerateMultihistory, so I don't think we should worry about it too much.

[daneelsan]

I understand now. What feels weird is to have "MaxDestroyerEvents" being inside stepSpec instead of being at the option level. As I understand, it eventually will replace "EventSelectionFunction" -> "MultiwaySpacelike", so it makes sense to have it there.

Also, the value must be a positive integer or Infinity. I see that Infinity is sometimes considered converted to max int 64. Seems to me that is the way to go (?)

[maxitg]

Yes, you are right. It's really a selection function, so in the old design it should actually be something like "EventSelectionFunction" -> {"MultiwaySpacelike", "MaxDestroyerEvents" -> 2} or some variation of that.

And yes, Infinity needs to be passed to C++, and max int 64 is just a special value to do that.

[daneelsan]

Instead of:

"EventSelectionFunction" -> {"MultiwaySpacelike", "MaxDestroyerEvents" -> 3}

what about:

"EventSelectionFunction" -> "MultiwaySpacelike", "MaxDestroyerEvents" -> 3

The default value of "MaxDestroyerEvents" would be Automatic:

• If "EventSelectionFunction" is "GlobalSpacelike", then "MaxDestroyerEvents" -> 1,
• if None or "MultiwaySpacelike", then "MaxDestroyerEvents" -> Infinity.

"MaxDestroyerEvents" is independent of the event selection function (even though "MaxDestroyerEvents" does depend on the value of "MaxDestroyerEvents" for performance improvements).

And I guess

"EventSelectionFunction" -> "GlobalSpacelike", "MaxDestroyerEvents" -> 3

should return an error.

[maxitg]

If we are going to do that, we should then add it as a step spec.

[maxitg]

Out of the old design things, it's most similar to "MaxGenerations" because that works as a selection function as well.

[daneelsan]

Yes, it does look similar:

Note also that "MaxGenerations" works differently from the other limiters, as the matching algorithm would not even attempt to match edges with generations over the limit. Therefore unlike, i.e., "MaxVertices", which would terminate the evolution immediately once the limit-violating event is attempted, "MaxGenerations" would keep "filling in" events for as long as possible until no further matches within allowed generations are possible.

Does this imply there should also be some sort of "TerminationReason:MaxDestroyerEvents"?

Also, "MaxDestroyerEvents" really is "MaxDestroyerEventsPerExpression". This confused me initially as I thought the limiter was the total number of destroyer events of the causal graph.

[maxitg]

What's the difference between the total number of destroyer events and the total number of events?

I suppose there could be another termination reason indicating that there are additional matches possible but only if "MaxDestroyerEvents" is increased. But the problem here is again that the old design conflates stopping conditions with selection conditions. In the new design, I don't think we should even have a termination reason for "MaxGenerations".

Instead, "MaxGenerations" is information about uninstantiated matches, and we need a whole other way of dealing with that.

So, in short, I think we should leave termination reasons as they are for now.