Violations where Resource Undefined

[pranav-super]

This turns out not to be as simple as our discussion on Slack might have implied.

For context, the ticket that this pertains to is one that resolves AERIE-1825. This ticket involves doing constraints checking on external datasets (which I will also refer to as external resources or external profiles, as that is the language we adopted when working on this ticket). Currently, it is possible to upload external profiles, and this ticket takes the profiles that have been uploaded, integrates them with the constraints DSL, and makes it so that violations are checked on these resources. That is, if I have an external profile “/ext1” uploaded, the constraint export default () => Constraint: {Real.Resource(“/ext1”).greaterThan(20)} becomes valid.

Generally, this is a pretty straightforward ticket, except for the fact that it is totally possible that these external resources have sparse profile segments. That is, they may not be defined everywhere. If we call + a space where the resource is defined and - a space where it isn’t, then it is totally possible that we could have the following profile:

/plant: --333--22--
(undefined from t=[1,2],[6,7],[10,11])

That part isn’t the problem – implementing that hasn’t been much of an issue, and it can address some useful test cases where a resource is based on something like telemetry data, or pertains to a component that isn’t used or attached to the mission for the entirety of a mission, like an alternative power source.

The problem is constraints checking itself. That is, should we flag a constraint as being violated when the resource the constraint operates on isn’t defined? So should the constraint Real.Resource(“/plant”).equal(3.0) yield a violation everywhere except t=[3,5], or only in t=[8,9]?

After some deliberation on Slack, where the two conflicting opinions were:

• if it isn’t defined, then the constraint can’t be true, so return a violation
• if it isn’t defined, telling the user their constraint was violated is misleading and shouldn’t be done

the latter of the two was chosen. That is, when a resource was undefined do not to return a violation. That’s about where slack leaves off. There was discussion of ways to implement this – we want to do this in a way where we don’t really mess with existing implementations of methods like evaluate() because the scheduling DSL uses the exact same Java tree nodes, and we don’t want a change in constraints checking to mess with scheduling. This is because currently, the default is a comparison with undefined returns false, but what we imply here is a comparison with undefined should return true. The solution was to isolate all constraint-specific changes the the one constraint-specific class, ViolationsOf.java, and then do any windowing restrictions using a special method that we add to the Expression.java class, getWhereDefined(), which returns an intersection (this will be qualified shortly, it’s not always an intersection) of where the leaf nodes’ resources are defined, and then takes the windows that were found from normal constraints checking and intersects it with the result of that call to getWhereDefined(). This was a cool solution, except for the fact that it isn’t really well defined for nodes like ForEachActivity, and there are two cases where it really just doesn’t make a ton of sense, and this has to do with composite constraints:

1. Let’s say we have an Any constraint, where one of the subconstraints is defined but false in a given window, and the other subconstraint’s resource is undefined in that same window. In that case, constraints checking evaluates that composite constraint as false, as undefined is treated as false. But should it return a violation? On one hand, none of them are true, so it’s clearly not satisfied, but on the other hand is a constraint isn’t satisfied is the composite constraint completely defined? We leaned heavily towards the latter, but the second case was what really broke this solution.
2. Let’s say we have an All constraint, with one subconstraint true in a given window, and the other undefined in the same window. This would evaluate to false, as undefined equals false, and if one is false, all will be. But should we really return a violation? On one hand, technically not every constraint is satisfied, so that’s grounds for violation. But that’s not totally consistent with the idea that an undefined constraint should cause a violation – the constraints that are defined are true, so this shouldn’t be a violation. This is definitely up for debate, but the vagueness here led to Joel proposing another solution, which we also want comment on.

The solution was to revert to the initial behavior, i.e. undefined = violation, unless explicitly stated otherwise. That is, we add a new node to the DSL, called undefined(), as a method on Real.Resource(), and it returns the windows for which the resource isn’t defined. Then, by doing the following:

Real.Resource("hello").whenDefined().lessThan(3);
(apologies, I can't get multiline code to work here)

you’ve said this is true when the resource is undefined, or where it is defined and it is less than 3, in other words, only evaluate this constraint when this resource is defined.

But, imaginably, users would need to type this often. There could be cases where they might want constraints checking to fail when a resource is undefined (we think?), so this verbosity in some form is important as we would then want users to have the option to not type this (this could be up for debate), but maybe there’s a more concise way. The solution was to add a method to Real.Resource() called .whenDefined(), that translates as follows:

• user types: Real.Resource("hello").whenDefined().lessThan(3);
• .whenDefined() returns NullableReal.Resource("hello"), where NullableReal.Resource is the same as Real.Resource except every time you call something like .lessThan() or .equals(), it returns the expanded form above, i.e. it returns:
• the final result, or Real.Resource("hello").whenDefined().lessThan(3);

But there might be a cleaner easier way to do this, so comment on that too would be appreciated as well.

After we figure these details out, though, we can finish off AERIE-1825!

[Twisol]

if it isn’t defined, then the constraint can’t be true,

If we're missing a span of telemetry, it doesn't mean the resource didn't take on a desired value; it means we don't know what value it took on. It very well may have taken on the desired value, but we can't observe that.

if it isn’t defined, telling the user their constraint was violated is misleading and shouldn’t be done

This is my opinion, too. If data is missing, we can say neither that a condition is met nor that it is not met -- we simply don't have the data to make such a determination.

Classically, this kind of use-case is what the NULL value in databases is for: missing data. NULL compares weirdly with itself: almost any operation involving NULL produces NULL.

Example psql session

Because of this, almost any computation involving a NULL produces NULL itself.

postgres=# \pset null '<null>'
Null display is "<null>".

postgres=# \pset format csv
Output format is csv.

postgres=# select null + 1 as result;
result
<null>

postgres=# select null + 1 as result;
result
<null>

postgres=# select null > 1 as result;
result
<null>

postgres=# select null = null as result;
result
<null>

This is because currently, the default is a comparison with undefined returns false, but what we imply here is a comparison with undefined should return true.

I would argue that a comparison with undefined should return undefined, assuming undefined plays the same role as NULL above.

It kind of seems to me that a condition needs to not only produce windows on which it is true, but also windows on which it is undefined (or windows on which it is false; pick any two, they imply the third). This works pointwise, just like anything else with conditions: a condition operator evaluated at time t is defined if its operands are also defined at time t (or whatever other time it consults, like with translating or scaling operators).

Let’s say we have an Any constraint

As long as one of Any's subconditions is true at a time, the Any should be true at that time, regardless of the value of the other subconditions. This is because, regardless of whether the other subconditions resolve to true or false, it doesn't change the answer that the Any would be true either way.

Conversely, for Any to be false at a time, all of its subconditions must be false. A single null amongst otherwise all-falses will cause the Any to be undefined at that time.

Let’s say we have an All constraint

As long as one of All's subconditions is false at a time, the All should be false at that time, regardless of the value of the other subconditions. Conversely, for All to be true at a time, all of its subconditions must be true.

[Twisol]

Think I spotted another bug, an off-by-one error this time. Fixed.

I'm still poking at the alternate representation -- I'm writing map2 for it now, so I'm still reviewing my earlier map2 and adapting it to the setting.

[Twisol]

I've just "finished" my alternate representation for IntervalMap. Again, I haven't tested this at all -- it compiles, and that's all I know for sure. https://gist.github.com/Twisol/88a8b2bf9e71681e74c1b4160ee9a03e

The IntervalMap API still works with intervals, but this implementation only stores the individual transitions between profile states. There's an iterator for running over all defined intervals, and an append-only builder for creating new instances. I ended up making IntervalMap itself immutable for simplicity, I think we generally want fast forward traversal and whole-timeline transformations, not random read-write access.

I also included three general-purpose methods that use map2, namely mask (implementing the generalized form of @JoelCourtney's applyWhen), select (pare the timeline down to only intervals intersecting a given window), and zip (generically pair values between two maps). These demonstrate how map2 abstracts over all the mess of traversing two maps, only asking you to specify what value the result should have based on the values (or absence thereof) on each input map.

(The hull() method gives the bounding interval containing all segments; this would support the minTimePoint and maxTimePoint methods on Windows.)

[pranav-super]

...I did not see this.

I also have an implementation of IntervalMap that I just finished yesterday - I also found an issue in map2 that had to do with when both input maps in map2 were null between intervals, but I fixed that and implemented a new version of Windows on top of it.

This was based off of the first implementation of map2 you sent, by the way.

But I think it's definitely important that we factor in your IntervalMap implementation, I just missed this update :(

[Twisol]

It would be good to test the behavior of one against the other, to see if we understood the problem constraints the same way 😄

[pranav-super]

Fortunately I wrote some pretty extensive map2 tests, but then again it was based on how I was approaching the problem

[JoelCourtney]

Hi, I'm the annoying guy who keeps changing the conversation to talk about Spans.

So what happens when a user converts a Windows that has gaps into Spans? My first instinct is that null makes negative sense in the context of Spans, because Spans is just "a set of intervals", nothing more. But then converting Windows to Spans becomes a lossy operation, because null will be lost when it becomes "not an interval".

So the question is, does it make any sense to include the concept of a null span, so that the conversion is lossless? If so, how would it behave under operations like split, shorterThan, or starts? My vote is to officially define them as follows:

• Windows: a boolean profile, which can be null because profiles can be null
• Spans: a set of intervals, which can't be null because what even the heck

Any objections?

[Twisol]

This interpretation fits with my mental model of the topic, so I'm 100% on board 😄