Boolean Operator Short Circuiting

[edwardpeters]

Elm supports boolean operator circuiting - i.e., in True || <expr> or False && <expr>, <expr> will not be evaluated. This is significant in cases where <expr> would not return.

As far as I can tell, the current elm-based interpreter does not support this. From the following code, shortCircuitTest will hang on either True or False, while shortCircuitTestFinite will not. In native elm, shortCircuitTest will only hang on False, as expected.

I structured these tests to isolate the question - is the second expression being evaluated or not - as cleanly as possible (the only difference between the two shortCircutTest functions is that one of them triggers an infinite loop if it does not short circuit.)

infinite : Int -> Bool -> Bool
infinite i u = 
 if i == 0 then u else infinite (i - 0) u

finite : Int -> Bool -> Bool
finite i u = 
 if i == 0 then u else finite (i - 1) u

shortCircuitTest : Bool -> Bool
shortCircuitTest b = 
    b || infinite 3 b

shortCircuitTestFinite : Bool -> Bool
shortCircuitTestFinite b = 
    b || finite 3 b

Additionally, I think it may be difficult to implement short circuiting in the current IR structure, with curried function application. If you imagine the IR as:

Apply(
  Apply(
    Reference("Or"),
    True),
  <expr>
)

Then the outer apply function needs some way to know that it should not evaluate its second argument. There are ways to work around this, but I wonder if it wouldn't be better to have boolean operators present directly as members of Value?

[DamianReeves]

I haven't thought of it very, very deeply, but I find it intriguing, the concept of adding perhaps BinaryOp and UnaryOp as both Type and Value nodes in the IR.

Doing such would allow us to encode the concept of infix ops to natively support math and boolean operators. We could also potentially add associativity as well.

I think the concepts of infix, postfix, prefix for Ops and associativity make this worth at least discussing. It would also allow us to encode consistent semantics in the IR.

cc/ @AttilaMihaly, @stephengoldbaum

[AttilaMihaly]

What would be the benefit of doing that? The assumption we had while designing the IR was that fixity and associativity are concepts tied to syntax so we intentionally left it out of the IR. Do they have any relevance beyond parsing?

[AttilaMihaly]

Way back when this was originally implemented it did do short circuiting:
https://github.com/finos/morphir-elm/blob/56e0816c6542274cefde664e2b341fa10cca8093/src/Morphir/IR/SDK/Basics.elm#L140-L157

Since then we decided that it doesn't worth the additional complexity to do that since it has minimal performance impact. You are right that there is a behavior difference when one of the arguments contains infinite recursion, but we consider those to be invalid and we don't concern ourselves with the behavior around that.

Generally we take the approach of assuming that an IR is valid if the computations don't fail and complete in bounded time. We may not be able to reject all invalid IRs at compile time right now, but assuming that the IR is valid allows us (and all tool developers) to avoid a lot of complexity. So your IR may still be invalid if it goes through make and the behavior is undefined in that case. That's never going to happen with real, properly tested business logic though.

[edwardpeters]

So there's a few things that seem viable to me:

If you want to be super minimal about it, I think technically you don't have to add any? I believe that with short circuiting, a || b is equivalent to if a then true else b and a && b is equivalent to if a then b else false. It's probably an unbearable hack, but if you really want to keep the IR frozen, you could just transpile those boolean operators to if statements.

I don't entirely follow @DamianReeves's ideas about infix, postfix, etc, which would be the advantage of adding BinaryOp in general. I don't have any objections, though, and it could make the IR itself more readable.

Finally, I don't think it's the worst idea to just add && and || as IR nodes. It might look a little weird to have them as first-class constructs, but they do have their own unique semantics, so I think it's justified.

Personally I would go with #2 if we care more about readable IR, and #3 if we just want a small change that matches the semantics without any strange hacks.

[AttilaMihaly]

One of the design principles we followed when designing the IR was to try to have only one way of doing a certain thing (we borrowed that from Elm). Since we already have a consistent way to call any functions, adding dedicate And and Or or BinaryOp nodes would violate that principle. And my bigger worry is that we wouldn't stop there.

There is a whole alternative way of designing an IR where the SDK is encoded in the IR itself. It has benefits and drawback. We tried it in the past and found that it makes the IR data structure too big and awkward to handle.

Specifically, if you think about what adding those two nodes mean for tool developers: every backend now has to handle those two nodes as separate branches now when they already have handling for every other SDK function.

[AttilaMihaly]

Thinking about this a bit more. How would adding And resolve the issue you are describing? It's all a matter of how the node is interpreted, right? Does it matter whether you see And arg1 arg2 in the IR or Apply (Apply "And" arg1) arg2?

Isn't this simply a matter of documenting the evaluation semantics of each function in the SDK?

[edwardpeters]

So thinking about it, that could mean one of two different things - neither is strictly wrong, but I think both have some issues.

The first is that we're matching on the IR, and looking for directly nested cases. That's viable, but does put some impositions on encodings and transformations - any level that transforms the IR (including some that @damian has written before) will need to be aware of the short-circuiting behavior and handle that case separately. It means that short circuiting won't happen in any non-directly nested case such as:

test : () -> Bool
test _ = 
    let f = (&&) in
    f False (foo())

But I think that's appropriate, and it matches the elm semantics. My bigger issue is just instinctive leeriness against any sort of AST matching that relies on patterns of nodes rather than individual nodes... I think those immediately become more brittle, and if you get any number of them they start to collide.

The other approach is to match on the evaluation of the inner apply, rather than its IR. That would allow the logic to be specified in encodings where the IR isn't directly nested (previously we had a model where after encoding you would see a monad for the nested IR which obfuscated its original form), but comes with a host of ambiguous cases. (For instance, users can create functions whose arguments may be either lazily or eagerly evaluated based on runtime logic... That strikes me as problematically messy.)

[AttilaMihaly]

Sorry to bring this back to a more abstract level again but I think it's important to clarify that Morphir is not trying to be a programming language in the traditional sense. In fact, the motivation for creating Morphir was to stop the constant debate about what is the one right way of doing this or that and focus more on what we can achieve through the subset of a language that everyone already agrees on.

More specifically, certain languages do lazy evaluation, others do strict and many do a mix. The business problems we are targeting to solve though are unaffected by the evaluation semantics. If we decided to chose a particular evaluation strategy we run the risk of making integrations more difficult since every tool would have to reproduce those exact semantics. So we would impose a cost with no gain to balance it out when it comes to solving business problems.

I think it's fine to execute the same business logic with short circuiting or without it and from a business perspective it should not matter. This is infrastructure details that Morphir was designed to abstract away.