implement an 'implies' logical operator

[martin-east]

Would it be possible to implement a short circuit logical boolean 'implies' operator (as in Eiffel and some other languages):

true imp false evaluates to false
true imp true evaluates to true
false imp false short circuits to true

I realise that Dart doesn't have alphabetic operators (I wish!) and that most non-alphanumeric character combinations are already assigned to operators, but maybe '!|' is available? It has two characters like the other logical short-circuit operators && and ||, and is strongly redolent of the equivalent operation which is !a || b. I hope this would not lead to ambiguities, but if so perhaps some other combination such as '|!', '^|', or '~|' might be possible.

Various work-arounds are:

1. code using the equivalent operations: !a || b;
   // arguably more cryptic
2. code using the ternary operator: !a?true:b;
   // wordier and surely more cryptic
3. call function with two boolean parameters: imp(bool a, bool b) => !a || b;
   // doesn't short circuit, doesn't mimic an operator, not inlined (?) by the compiler
4. call function with boolean and predicate parameters: bool imp(bool a, bool Function evalB()) =>!a || evalB();
   // expensive, unintuitive to call: imp(a, ()=>b), doesn't mimic an operator, unlikely to be optimised by the compiler
5. call method in bool extension: imp(bool other) => !this||other;
   // mimics operator better: a.imp(b), otherwise same disadvantages as item 3)
6. call method in bool extension: imp(bool Function evalOther()) =>!this||evalOther();
   // mimics operator better: a.imp(()=>b), otherwise same disadvantages as 4)

I believe the main reason why programmers aren't aware of the implies operator is because most languages don't have it. However, given the chance to use it - especially for contracts and assertions - you wouldn't want to do without.

For as discussion, see

https://softwareengineering.stackexchange.com/questions/184089/why-dont-languages-include-implication-as-a-logical-operator

Thanks for your comments/feedback

[lrhn]

The linked discussion gives good answers for why implication isn't usually in programming languages.

Two of the reasons is that the operator is hard to reason about, and that it's less often what you need.

It's hard to reason about because it doesn't read like a test, but more like a general open predicate. I can read isRaining & !hasUmbrella and understand it (gets wet). Same for its negation !isRaining || hasUmbrella (won't get wet).

What is isRaining => hasUmbrella saying? (I can't tell without either translating to one of the forms above, or mentally building the truth table.)
That may just be habit. Reading it as "only if it's raining, then you must have umbrella" might help. Maybe.

Since the alternative !expr1 || expr2 works today, and new syntax, especially operator syntax, is something to reserve for important changes, I don't see an implication operator as a very likely feature to spend implementation resources or syntax real estate on.

I expect user defined short-circuit operators to happen before a single implication operator (and I don't think we've ever thought about user defined short-circuit operators before).

[hydro63]

@martin-east There is no need to add a new operator, since you can just do add extension on bool overriding >> operator, and you get what you want, with more readibility than your proposed operators. You also get ability to shortcurcuit as a bonus (though the operator precedence is a problem)

extension ImpliesBool on bool {
  bool operator >>(bool right) => !this || right;
}

void main() {
  // all cases
  print(true >> true);     // true
  print(true >> false);    // false
  print(false >> true);    // true
  print(false >> false);   // true
  print(true >> 150);      // comptime error - you can't use implication on non-bool type
  print(150 >> false);     // comptime error
}

IMPORTANT - DO NOT use implication when you are collaborating with someone, since implication is very difficult for people to wrap their head around. I literally had to look up the truth table for implication in order to make this extension

[lrhn]

An operator >> would not be short-circuiting, that is the one feature that the request asks for that you can't get without rewriting to !left || right directly in the code. If you try to abstract using a function, then the call by value parameter passing makes it non-short-circuiting.

A language feature like "lazy arguments" could change that. Say a feature like:

extension ImpliesBool on bool {
  bool operator >>(late bool right) => !this || right;
}

where late means the argument expression isn't evaluated until the parameter variable is read (with some consquences for how that variable can be used, and how function subtyping works).

I don't think such a feature is very likely, but it's also not impossible. I think it's more likely than adding an impliction short-circuit operator by itself.

[martin-east]

first of all I would like to thank both of you for your very prompt, thoughtful and helpful responses. Lasse's answers in particular don't just address the immediate question but give a glimpse into what might come in the future. Respect!

Most of content of the link comes down to the following 'anti' arguments:

1. languages that use symbols for operators have limited scope for new operators.

• This is perfectly valid in the case of Dart and I fully accept Lasse's reasoning that such scope should be limited to potentially more needed operators, especially as the work-around !expr1 || expr2 is also an operator expression and relatively concise.

2. you can replace an implies operator with !expr1 || expr2.

• you can replace other operators with compound expressions or if statements too, that doesn't mean you should have to.

3. an implies operator is not intuitive.

• I would argue that && and || are only intuitive to programmers because they learnt the corresponding truth tables when starting out programming. And just because an operator isn't intuitive, that's no reason to exclude it: in my view the ?. operator isn't intuitive but is very useful and I for one am delighted that Dart has it, unlike many other languages

4. even if it were intuitive, there isn't much need for it

• I agree to some extent with this: && and || will be used far more often. Ergo point 1)

5. misunderstandings arising from the assumption that we were talking about a strict operator, not a short-circuit operator

• no comment

Lasse has already pointed out the problem of (lack of) short-circuiting in Peter's otherwise very helpful suggestion.

I am glad if I have triggered some thoughts through my post, and personally would be very pleased to see user-defined short-circuit operators and/or lazy arguments appear in Dart. Some ideas of mine:

• short-circuit bitwise operators: 0 & a is always 0, -1 | a is always a; similarly for multiplication. Maybe the compiler does this already?
• provide both short-circuit and strict versions as a choice. Short-circuit is always safer and sometimes faster. But in some cases strict can be safe and faster - especially if expr2 is a variable or constant
• let the compiler decide whether strict or short-circuit is more appropriate, unless overruled by the programmer
• take short-circuiting into account when evaluating const expressions - this could reduce the number of expressions rejected by the compiler because they call methods or functions
• provide an instruction to the compiler that a strict binary user-defined operator (or a function with two arguments of the same type, or a method with one argument that is the same type as this) is commutative, allowing the compiler to decide the evaluation order.

Many thanks again for your input

Martin

[lrhn]

I would argue that && and || are only intuitive to programmers because they learnt the corresponding truth tables when starting out programming

I'd argue the opposite. Those operators are in the programming languages because they are the ones that are intuitive to most people, including the people making the first programming languages.

They correspond to traditional natural language phrases "this and also that" and "either this or else that".
You use those naturally like "I'll get wet when it rains and I (also) don't have an umbrella",
or "I'll stay dry when it either doesn't rain, or (else) if I have an umbrella". Natural language being what it is, we leave our some words if they aren't needed to disambiguate.

The biggest difference from natural language is that || is inclusive or, not exclusive or, and natural language often uses an exclusive or. But that's also why most programming languages have both.

The ?/: conditional operator is understandable, even intutive, because it reduces to clear "if this then that" logic:
"I am suitably dressed if this is a formal occasion and I'm wearing formal clothes, or it's not a formal occastion and I'm wearing clean and decent clothes."
The "condition and this, or not condition and that" is how I read conditional expressions.
(Which could be reduced to (condition && then) || (!condition && else), but we don't like to repeat expressions.)

About short-circuit bitwise operators on integers: I'm fairly sure the compiler doesn't do this. In the vast majority of cases, doing a conditional branch is more expensive than just evaluating the second expression and doing a bitwise and/or (one machine op). Unless there is reason to believe that the first operand will be zero often, not just the base 1/2^64 of the time, doing a test and still not skipping the second expression is more work. (Arguably a predictable branch then.)

Dart does provide short-circuit and non-short-circuit operations for booleans (|| and && vs | and &).
Again for numbers, where the short-circuiting value is not 50% of the possible values, it's so unlikely to be needed, that it's OK for the author to write var res = switch (e1) { 0 => 0, var x => x & e2}; or similar, if they think the check is worth doing. There is no chance the compiler can know that, and adding short-circuiting operators for bitwise operations (numberExpr || expr2) which short-circuits expr2 if numberExpr evaluats to precisely -1, seems like a trap for users. They may use it, and think they can get better performance, when actually they'll get worse performance in all but 1/2^64 of the cases.

It's non-trivial to see if an expression has side-effects, like throwing or updating global state. Allowing the compiler to choose between short-circuit and not, is a fragile approach. It's better to have the author choose, because they know what they want.
If I do x != null && x.length > 0, I definitely don't want the second expression evaluated first. The "and also" of the && meaning is important.

Same for evaluation order. If there is one thing I want from my compiler, it's predictability. Allowing the compiler to choose evaluation can mean that tests are run in one order and production in another. That makes testing fail its one job: Avoid g bugs in production by exercising the same code and control flows in a controlled environment. If it's not testing the same control flows, it's not actually saying whether the code will run in production.
Non-determinism is something you need to opt in to, otherwise it just makes your job of predicting behavior harder.

(I'm not opposed to short-circuit user operators, or call-by-name parameters, but they're not trivial, and it's also not clear that they're worth the significant complexity they may entail. Not expecting anything any time soon.)

[martin-east]

The biggest difference from natural language is that || is inclusive or, not exclusive or, and natural language often uses an exclusive or. But that's also why most programming languages have both.

inclusive vs. exclusive or was exactly what I was thinking of when I said that && and || aren't intuitive to non-programmers. Also, many non-programmers think that and denotes addition, thus:
1 and 1 = 2, not 1 (I have one umbrella at home and one umbrella in my office)
1 and 0 = 1, not 0 (I have one umbrella at home and no umbrella in the office)

About short-circuit bitwise operators on integers: I'm fairly sure the compiler doesn't do this. In the vast majority of cases, doing a conditional branch is more expensive than just evaluating the second expression and doing a bitwise and/or (one machine op). Unless there is reason to believe that the first operand will be zero often, not just the base 1/2^64 of the time, doing a test and still not skipping the second expression is more work. (Arguably a predictable branch then.)

I reckon that 0 and -1 arise far more frequently than any other numbers in bitwise operator arguments. My idea was that the programmer can decide which version (strict or short-circuit) is likely to give the better or safer performance, without having to completely rewrite the code. And might it make sense for the compiler to omit the test of expr1 and the evaluation of expr2 if the compiler knows expr1 is always 0 or -1 (e.g. for a named constant or where the programmer has consciously included the call to keep source code formatting orthogonal and consistent)? This is what I meant when asking if the compiler does this already.

Dart does provide short-circuit and non-short-circuit operations for booleans (|| and && vs | and &).

Yes, you are correct. Since (I think) only && and || short-circuit, both options are covered. My idea was for any future short-circuit operators to always offer a strict alternative. As a side point, accidentally omitting one of the two & or | symbols can lead to some very subtle and hard-to-discover bugs. We can't change these operator symbols, but may I suggest a linter warning when using the strict versions? Short-circuit operators are always safer except for the (frankly) bizarre case that expr2 has desired side-effects that must be executed regardless of expr1, for which there really should be other linter warnings!

In vscode, I get this popup when rolling over the & operator:

bool &(bool other)
dart:core

The logical conjunction ("and") of this and [other].

Returns true if both this and [other] are true, and false otherwise.

If I roll over a && operator, a tiny window saying only 'type bool' pops up.

The same applies with | and ||.

And https://dart.dev/language/operators doesn't even mention that the logical operators short-circuit! That's pretty fundamental.

It's non-trivial to see if an expression has side-effects, like throwing or updating global state. Allowing the compiler to choose between short-circuit and not, is a fragile approach. It's better to have the author choose...

That's why I proposed that the compiler chooses "... unless overridden by the programmer". Perhaps better: the author must explicitly say 'you choose' to the compiler.

Non-determinism is something you need to opt in to, otherwise it just makes your job of predicting behavior harder.

That's why I proposed that the programmer actively says to the compiler: you choose. Standard C leaves the order of evaluation to the compiler in all cases: that's forced non-determinism, and I'm very glad that Dart has the opposite. It means that different Dart compilers in different environments should produce exactly the same result. I'm just suggesting that there may be cases where the programmer, by explicitly allowing the compiler to decide, could produce better performing code.

Many thanks again for your time and thoughts. I'm happy to continue discussing these and related points, but fully understand if you want to focus on much more important things on your plate.

NB: It would be nice to see the linter and documentation points regarding && and || addressed!

Best
Martin

[hydro63]

I have returned, and i am sorry for misunderstanding what you wanted. You are right, the proposed solution does not short-curcuit. With that in mind:

A language feature like "lazy arguments" could change that

IMO lazy arguments is a really bad proposal. What i think lazy arguments are gonna be used for is to avoid computing complex functions when possible, right? The problem is that the said function can also reference global variable, or perhaps you pass them mutable List<T> by reference. That means that it's possible that the developer will change said global variable before the lazy expression is evaluated, and thus changing the result of the evaluation.

bool mutable = false;
bool calculation() => mutable;
 
void lazyEval(late bool value){
  mutable = true;
  print(value ? "IT'S FALSE" : "IT'S TRUE");  // should be false, prints true;
}

/*
// debug version
void lazyEval(late bool value){
  print(value);
  mutable = true;
  print(value ? "IT'S FALSE" : "IT'S TRUE");  // prints false; -> which is correct
}
*/

void main(){
  lazyEval(calculation());
}

These kinds of bugs would be practically impossible to debug, since you think you know what is passed to function, you can also print the value at the start, and the problem would go away, since it was computed before the change happened. If you then removed the print, the bug would reappear, leaving everybody confused why is print the solution. The same would also happen with real debuggers, since when you would put the breakpoint, the value would be calculated before the change would happend, thus fixing the bug (which is like ????). The lazy evaluation of expression is a sort of async code, while looking exactly like sync code.

About the userdefined short-curcuit operators, i'm not entirely sure i'm sold on it. There are not many uses for them, and most of the time, there isn't a lot of time lost. The most useful shortcurtuits have already been done, and for the others developer can implement them himself without much difficulty. For example, the collection types have functions that shortcurtuit.

I just don't see a compelling enough of a reason to add a userdefined shortcurcuit operators. Also, how would you even write that?? I can't imagine any single syntax, that i'd be comfortable to read. Please provide some prototype syntax, so that we can have at least a concrete example to fall back on.

[martin-east]

Hi Peter,

lazy evaluation is exactly what the logical operators && and || do! They only evaluate expr2 when it's needed, and in many cases, it's not needed.

The classic usage is to avoid throwing exceptions in the unneeded evaluation of expr2, such as x <= array.length && array[x] == y. But they are also useful for a) avoiding a potentially expensive calculation of expr2 b) avoiding any unwanted side-effects in expr2.

Of course if the programmer definitely wants the side-effects in expr2 to occur irrespective of expr1, I would submit that the code is in need of a review. Failing that, the programmer should use the strict version (& or |) and clearly document why strict evaluation is necessary.

Your example of a void function with a single lazy argument isn't what Lasse suggested: the first argument (or this for the example member function given) is always evaluated, the subsequent arguments might or might not be, depending on the first one.

Lasse's suggestion:

extension ImpliesBool on bool {
  bool operator >>(late bool right) => !this || right;
}

illustrates perfectly how you could define such an operator. The syntax on usage is very simple:

a >> b

FWIW I have a strong bias towards coding non-void functions and methods with absolutely no side-effects. It makes reasoning about programs, debugging, and the job of an automated verification easier. And if you follow these principles, there are no side-effects to worry about with short-circuit operators or lazy arguments. See for example: command-query . As we are drifting off-topic into software engineering philosophy we should probably continue in a different thread or agree to differ :)

[hydro63]

I disagree. In practice, believing that a developer will adhere to some arbitrary rules never works, and there will always be someone who tries to do a bit too much with what they are given. They will try to be clever, thinking if i put everything as lazy, then i execute only what i need to execute, nothing else and then fumble it, because they don't realise that what they are given is NOT IMMUTABLE, but can change at any given point. Basically, don't trust developers to not abuse the feature.

You have to think about the whole language, not just a part. I know that the && and || are lazily evaluated, but they work because they are binary operators and don't run other code. If you introduce lazy evaluation, you introduce it not only to the operators, but also to the functions (since operators are just functions). In that case, the example i provided is more or less realistic, since you never know how a given function is implemented, and so it's always possible to unknowingly change the return value of a function.

PS: I know what lazy evaluation is ( || is immensly useful in JS). My argument is don't trust the developer all that much, he will always try to do something he shouldn't. I'm saying this because i'm a developer, and i know that with this i would use it practically everywhere, since there are only benefits and no apparent detriments. With that much use (basically every function), that would basically guarantee that some sideeffect would be hidden somewhere