Julia: short-circuiting and `missing` (3-value logic)

[goretkin]

As mentioned here the short-circuiting operators || and && don't tolerate a missing value in the first position.

But I would like an operator that is the marriage of these two: produces the result of | and & respectively, and avoids evaluating the second value when result is knowable from the first value.

I wrote a macro and a test jig. It's certainly something that could live in a package, but I wanted to open this issue for discussion, because it might benefit from a non-macro spelling.

The tables show the two operands/arguments, the number of times they were evaluated, and the result.

case = :both
andor = :and
┌─────────┬─────────┬────┬────┬─────────┐
│       p │       q │ ep │ eq │       r │
├─────────┼─────────┼────┼────┼─────────┤
│    true │    true │  1 │  1 │    true │
│   false │    true │  1 │  0 │   false │
│ missing │    true │  1 │  1 │ missing │
│    true │   false │  1 │  1 │   false │
│   false │   false │  1 │  0 │   false │
│ missing │   false │  1 │  1 │   false │
│    true │ missing │  1 │  1 │ missing │
│   false │ missing │  1 │  0 │   false │
│ missing │ missing │  1 │  1 │ missing │
└─────────┴─────────┴────┴────┴─────────┘
---------

case = :both
andor = :or
┌─────────┬─────────┬────┬────┬─────────┐
│       p │       q │ ep │ eq │       r │
├─────────┼─────────┼────┼────┼─────────┤
│    true │    true │  1 │  0 │    true │
│   false │    true │  1 │  1 │    true │
│ missing │    true │  1 │  1 │    true │
│    true │   false │  1 │  0 │    true │
│   false │   false │  1 │  1 │   false │
│ missing │   false │  1 │  1 │ missing │
│    true │ missing │  1 │  0 │    true │
│   false │ missing │  1 │  1 │ missing │
│ missing │ missing │  1 │  1 │ missing │
└─────────┴─────────┴────┴────┴─────────┘

compared to && and ||

case = :sc
andor = :and
┌─────────┬─────────┬────┬────┬───────────────────────────────────┐
│       p │       q │ ep │ eq │                                 r │
├─────────┼─────────┼────┼────┼───────────────────────────────────┤
│    true │    true │  1 │  1 │                              true │
│   false │    true │  1 │  0 │                             false │
│ missing │    true │  1 │  0 │ TypeError(:if, "", Bool, missing) │
│    true │   false │  1 │  1 │                             false │
│   false │   false │  1 │  0 │                             false │
│ missing │   false │  1 │  0 │ TypeError(:if, "", Bool, missing) │
│    true │ missing │  1 │  1 │                           missing │
│   false │ missing │  1 │  0 │                             false │
│ missing │ missing │  1 │  0 │ TypeError(:if, "", Bool, missing) │
└─────────┴─────────┴────┴────┴───────────────────────────────────┘
---------

case = :sc
andor = :or
┌─────────┬─────────┬────┬────┬───────────────────────────────────┐
│       p │       q │ ep │ eq │                                 r │
├─────────┼─────────┼────┼────┼───────────────────────────────────┤
│    true │    true │  1 │  0 │                              true │
│   false │    true │  1 │  1 │                              true │
│ missing │    true │  1 │  0 │ TypeError(:if, "", Bool, missing) │
│    true │   false │  1 │  0 │                              true │
│   false │   false │  1 │  1 │                             false │
│ missing │   false │  1 │  0 │ TypeError(:if, "", Bool, missing) │
│    true │ missing │  1 │  0 │                              true │
│   false │ missing │  1 │  1 │                           missing │
│ missing │ missing │  1 │  0 │ TypeError(:if, "", Bool, missing) │
└─────────┴─────────┴────┴────┴───────────────────────────────────┘
---------

[kimikage]

If you know the rhs expression of &&/|| is a Bool or missing, that looks reasonable. However, if you know that, I don't think we need to support your proposal, i.e. you can use &/| in such situations.

In general, the result is unknown from the lhs missing. An rhs expression can have side effects. Therefore, the lhs expression must be "deterministic".

[goretkin]

I don't understand. Using &/| does not produce the short-circuiting behaviors. the ep/qp columns will be all 1s, which is not what I desire.

[kimikage]

Paradoxically I meant you "cannot" do the short-circuit evaluation.
@and and @or may be useful in some cases, but they are not consistent with &&/||.
It is generally difficult to know what the rhs expression is, without evaluating it. The return type may be inferred, but it is not clear the expression has no side effects.

Edit:
Of course, if there are no side effects, it is reasonable to proceed the steps with the 3-valued logic. However, it is not intuitive that the behavior differs depending on whether or not there are side effects.
If we have a mechanism to determine that the short-circuit evaluation is available, it should be done by the compiler and we (users) should use &/|.

[StefanKarpinski]

Would it seem reasonable for

if x
    # do something
else
    # do something else
end

to take both branches if x happens to be the value missing? That seems like it would really be asking for horrible trouble when reasoning about code. That's effectively the equivalent of what this issue is asking for since && and || are control flow.

[goretkin]

Perhaps I should clarify. I'm not proposing changing the behavior of && and ||.

[kimikage]

I wanted to open this issue for discussion, because it might benefit from a non-macro spelling.

I'm sorry for the misunderstanding. Then, what should we discuss? Are they the names of new operators (functions)?

Edit:
Since missing should not be implicitly converted to Bool, in the tandem form (e.g. a && b || c) all &&/|| keywords need to be replaced with the new operators. So if we don't change the syntax of Julia, I think macros are a good choice.(Basically a function evaluates all its arguments.) Perhaps the new macros will not be backported to Julia v1.1-v1.3, so it's better to define them in a package.

[goretkin]

It's a marriage of the behavior that &/| and &&/||, so my first instinct is &&&/|||. :-X But before reserving syntax for this operator, perhaps it's worth understanding that the need for this behavior arose from requiring the behavior of &/| and desiring the efficiency of &&/||, by which I mean it's control flow to affect the performance and not the result of a computation.

It came up in PaddedViews.jl (xref above), but it might not come up often enough. So I too also lean toward just packaging the macros. The macros as I wrote have a totally different spelling for something that is closely related to &/| and &&/||. Instead, it seems preferable that the macro be applied to an expression written in terms of &/|, and the macro would substitute those functions for the short-circuiting-3-value behavior. For "pure" functions, the program behavior would be unchanged, but just more efficient, which is in the spirit of other macros like @inbounds, and @fastmath.

[kimikage]

For "pure" functions, the program behavior would be unchanged, but just more efficient,

That's right. You showed the advantages of the new operators and I showed their dangerous behavior. You must use them at your own risk.

BTW, I prefer to hide the new operators, for example:

@trinary isinteger(a) || isconcretetype(a) || show("foo")

However, I much prefer to write tedious if blocks for safety. (Note that isconcretetype(missing) returns false, not missing)

[goretkin]

However, I much prefer to write tedious if blocks for safety. (Note that isconcretetype(missing) returns false, not missing)

Sorry I didn't understand why that's relevant. ismissing(missing)==true, too. Not all functions propagate missing?

[kimikage]

ismissing is a special, clear and well-documented case.:confused:

In the first place, it's not clear whether each function supports missing. However, when I find a function used with the new 3-valued operators and without any comments, I will infer from the context that the function supports missing and returns one of true/false/missing. Of course, this inference is not always true.

It's nonsense to write long comments due to the short notation.

This is why "I" don't want to use the new operators widely, not why they should not be used.

[kimikage]

The weirdness I've felt since the beginning is that you want the short-circuiting behavior for efficiency, but are trying to evaluate missing. The &/| with missing is known as Kleene's logic. But many other missing operations are similar to Bochvar's logic. And we now assume that there are no side effects (except the trivial last step). (As mentioned above, the new operators are troublesome when the functions have side effects).
That implies there is a bias in the number of "logical" combinations of input patterns for each true/false/missing, and a bias in the "experimental" probability of occurrence of those patterns, too. In other words, you seem to miss the opportunity for optimization, trying to treat true/false/missing equally.

Based on the current implementations, in the cases of PaddedView, the new operators should be useful. However, you overlook the condition of no padding. In the case with the additional conditional branch, I doubt the new operators are much smarter.

[goretkin]

@kimikage I would be happy if you include feedback about the PaddedViewPR on that PR. I don't understand your point, but would appreciate a clarification over there.

Thanks for bringing up that true/ false/ missing can have two different logics. I think that the poison/propagation/Bochvar logic is not relevant here, because that's not what &/| or &&/|| do. I'll note that +/* applied on 0/!=(0)/missing is an encoding of the Bochvar 3-value logic. Better yet min/max works as and/or on true/false/missing.

I fully do not understand what you mean by "bias" and "experimental probability" and what opportunity for optimization I've missed, and what it means to treat true/false/missing equally. Sorry if I should be following better.

[kimikage]

I am sorry but I am not good at explaining.

I think that the poison/propagation/Bochvar logic is not relevant here, because that's not what &/| or &&/|| do.

WRT the "operators", that's right. I also meant the "operands" (callees). Of course, I don't know what properties the expressions of the operands have. However, if it is a simple expression, there is little merit of the short-circuit evaluation. Therefore, I implicitly assume the expressions take time to evaluate.

"bias"

The 1/3 of all input patterns result in missing. This property stands out as the logical expression becomes longer. On the other hand, in practical applications, it is unlikely that 1/3 of what we get is missing. In many cases, the probability of missing is biased as a prior probability, and the posterior probability should fluctuate significantly as the expression is interpreted from the left to right.

Although not mentioned above, there should be some bias in execution time. The callees can also do short-circuit evaluations.

what opportunity for optimization I've missed

Your proposed operators cannot shortcut when the intermediate result is missing.

[StefanKarpinski]

Seems like you can get what you'd like from coalesce and && and ||:

• coalesce(a(), true) && b()
• coalesce(a(), false) || b()

[goretkin]

Seems like you can get what you'd like from coalesce and && and ||:

* `coalesce(a(), true) && b()`

* `coalesce(a(), false) || b()`

julia> missing & true
missing

julia> missing | false
missing

So that rules out a strategy which discards the missing.

[goretkin]

xref: https://github.com/johnmyleswhite/julia_tutorials/blob/master/From%20Macros%20to%20DSLs%20in%20Julia%20-%20Part%201%20-%20Macros.ipynb has a related exercise