bool::implies and bool::implied_by

[GoldsteinE]

Proposal

Problem statement

There’s no clean way to express boolean implication: you need to resort to something like !a || b.

Motivation, use-cases

Happens kind of a lot, but it may be unclear whether a.implies(b) or !a || b is more clear in each concrete use case.

Some examples from rustc:

https://github.com/rust-lang/rust/blob/f63ccaf25f74151a5d8ce057904cd944074b01d2/compiler/rustc_hir_typeck/src/fn_ctxt/suggestions.rs#L451

if !expected.is_box() || found.is_box()

https://github.com/rust-lang/rust/blob/f63ccaf25f74151a5d8ce057904cd944074b01d2/compiler/rustc_expand/src/config.rs#L444

attrs.iter().all(|attr| !is_cfg(attr) || self.cfg_true(attr))

https://github.com/rust-lang/rust/blob/f63ccaf25f74151a5d8ce057904cd944074b01d2/src/tools/clippy/clippy_lints/src/methods/unnecessary_filter_map.rs#L44

!clone_or_copy_needed || is_copy(cx, in_ty)

Solution sketches

impl bool {
    fn implies(self, other: Self) -> Self {
        !self || other
    }

    fn implied_by(self, other: Self) -> Self {
        self || !other
    }

    // Or maybe (to preserve laziness)
    fn implies(self, other: impl FnOnce() -> Self) -> Self {
        !self || other()
    }

    fn implied_by(self, other: impl FnOnce() -> Self) -> Self {
        self || !other()
    }
}

Links and related work

Some languages have implication function or operator, e.g. Racket.

Rust has <=, which works like boolean implication but looks like implication backwards, which is kinda confusing.

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[scottmcm]

My big question is why this set it worth having specifically.

After all, there's no specific method for x && !y either. Should that get a method? It's the dual of implies...

[GoldsteinE]

I think this operation is worth having because it has a well-known name, so writing !a || b as a.implies(b) may simplify reading in some cases. I can’t think of a name for x && !y that’s better than x.and_not(y), and I don’t think it would be easier to read that.

[the8472]

I'm not sure if this is a good addition to the standard library. Someone might end up using implies because it has the correct truth table but the conditions they use don't form a general implication between a and b except in that particular context, perhaps due to some additional checks earlier in the code.
If someone later then reads the code they might be mislead about the relation between the conditions.

[GoldsteinE]

The same argument also applies to having Ord on booleans: <= has the right truth table, but is semantically weird.

I look at it this way: either a programmer may (for some reason) write .implies() where they really meant !a || b , or they’re forced to write !a || b where they really meant .implies(). Given that the name is pretty self-describing, I think it’s better to have ways to semantically express both “it’s just !a || b” and “it’s actually logical implication”.

[the8472]

The same argument also applies to having Ord on booleans: <= has the right truth table, but is semantically weird.

I don't think Ord on booleans is a good precedent. I have run into cases where it felt quite arbitrary.

I think it’s better to have ways to semantically express both “it’s just !a || b” and “it’s actually logical implication”.

For the former we could chose a more neutral name that just describes what it does rather than ascribing meaning. if_not_or_else, negate_or or something along those lines.

[GoldsteinE]

The former is already expressible by just doing !a || b. The latter is not expressible at all in current Rust.

[cuviper]

I understand the truth table of implication, but stuff like if a.implies(b) feels very awkward as a reader -- and I think that's related to this section on Wikipedia:
https://en.wikipedia.org/wiki/Material_conditional#Discrepancies_with_natural_language

[the8472]

The former is already expressible by just doing !a || b. The latter is not expressible at all in current Rust.

The latter is less general and can be expressed via an extension trait. So the question is whether it's appropriate for the standard library.

[GoldsteinE]

It can be expressed via an extension trait, but it probably won’t be expressed that way, since writing an extension trait for a couple of single-line methods is kind of cumbersome.

[the8472]

I'm skeptical of "it has to be in the standard library or else nobody will ever write it" arguments, that's more a sign that its utility is quite low, rather than an argument in favor.

At the very least if someone thinks it makes their code more readable they could write a free function or a macro inside their own crate. Is their prior art of crate authors trying to improve readability this way?

[CryZe]

It seems like people are writing such a trait / free function in their code: https://github.com/search?q=lang%3ARust+symbol%3Aimplies&type=code

[the8472]

That doesn't show any hits that resemble what we're discussing here.

[CryZe]

It seems like you are still on the old Github code search then that can't handle symbols, languages and co. yet.

[the8472]

Ah yeah, enabling the preview worked. Interesting, I get pre-1.0 hits for rust, which means it was removed at some point.

https://github.com/pcwalton/rust/blame/2c3420175cd83a4ec0c3e89816a17b1a6a3bff3c/src/libstd/bool.rs#L137

One library chose implies_materially, perhaps to avoid confusion with the common meaning.

[cuviper]

Interesting, I get pre-1.0 hits for rust, which means it was removed at some point.

That instance was moved to an extension trait in rust-lang/rust#10007, and then removed in rust-lang/rust#12473.

[m-ou-se]

a well-known name

I don't think this is a very well known name. Most programmers will be able to read !a || b and know what it means, but many programmers will not immediately know what a.implies(b) means.

[BurntSushi]

so writing !a || b as a.implies(b) may simplify reading in some cases

I agree with this, but I also think (as mentioned above) that an extension trait is a suitable answer to this. I don't think we should be lifting this terminology to std. Its negative effects are likely to eclipse its positive effects IMO.

[CryZe]

After all, there's no specific method for x && !y either. Should that get a method? It's the dual of implies...

This really made me think. If the main argument against implies (well there's also the name) is that it seems uncommon and there's no reason to have it when other operators don't have a method... then what if we simply add all of them?

Truth Table	Expression
FFFF	false
FFFT	p.nor(q)
FFTF	p.converse_non_implication(q)
FFTT	!p
FTFF	p.material_non_implication(q)
FTFT	!q
FTTF	p ^ q
FTTT	p.nand(q)
TFFF	p & q
TFFT	p.xnor(q)
TFTF	q
TFTT	p.material_implication(q)
TTFF	p
TTFT	p.converse_implication(q)
TTTF	p | q
TTTT	true

Then it's not arbitrary and I'm sure people would appreciate the others (NAND, NOR and co.) as well. Integers, floats and co. have lots of methods nowadays, so I don't see why we couldn't simply add the whole truth table to booleans (it's only 7 methods).

That unfortunately doesn't solve the naming problem (but maybe if we add them all we could just go with the official names for the operators?).

[programmerjake]

we could use method names that describe what operation they do in terms of [n]and/[n]or/x[n]or/not:

Truth Table	Expression	Equivalent Expression
FFFF	false	false
FFFT	p.nor(q)	!(p | q)
FFTF	p.reverse_and_not(q)	q & !p
FFTT	!p	!p
FTFF	p.and_not(q)	p & !q
FTFT	!q	!q
FTTF	p ^ q	p ^ q
FTTT	p.nand(q)	!(p & q)
TFFF	p & q	p & q
TFFT	p.xnor(q)	!(p ^ q)
TFTF	q	q
TFTT	p.reverse_or_not(q)	q | !p
TTFF	p	p
TTFT	p.or_not(q)	p | !q
TTTF	p | q	p | q
TTTT	true	true

[BurntSushi]

I am personally even less in favor of adding the full complement of methods here than I am of just adding something like implies.

[Amanieu]

We discussed this in the libs-api meeting. Overall we believe that this makes code less readable than if the condition was explicitly written out using basic boolean operations (#188 (comment)). If this was added to the standard library then it may encourage people to use it because it matches the truth table they are looking for, at the cost of readability.