Recently, I came across a problem that required me to define the logical "OR" operator programmatically, but without using the operator itself.
What I came up with is this:
OR(arg1, arg2)
if arg1 = True and arg2 = True
return True
else if arg1 = True and arg2 = False
return True
else if arg1 = False and arg2 = True
return True
else:
return False
Is this logic correct, or did I miss something?
Here is a solution without or, and, not, comparisons and boolean literals:
or(arg1, arg2)
if arg1
return arg1
else
return arg2
It probably doesn't get much more fundamental than that ;)
One line of code:
return not (not arg1 and not arg2)
No branching, no OR.
In a C-based language, it would be:
return !(!arg1 && !arg2);
This is simply an application of De Morgan's laws: (A || B) == !(!A && !B)
I'd say that's correct, but could you not condense it down to something such as this?
or(arg1, arg2)
if arg1 == true
return true
if arg2 == true
return true
return false
Since you're doing an or comparison, I don't think you really need to check the combination. It just matters if one of them is true to return true. Otherwise we want to return false.
If you're looking for a shorter version that is less verbose, this will also work:
or(arg1, arg2)
if arg1
return arg1
return arg2
If you only have and and not, you can use DeMorgan's law to flip around and:
if not (arg1 = False and arg2 = False)
return True
else
return False
... or (even more simply)
if arg1 = False and arg2 = False
return false
else
return true
...
And since we've all apparently become fixated on optimizing something that is almost always available as a machine instruction anyway, that boils down to:
return not(not arg1 and not arg2)
return arg1 ? true : arg2
etc. etc. etc. etc.
Since most languages provide a conditional-and, odds are the "and" operator implies a branch anyway.
...
If all you have is nand (see wikipedia):
return nand(nand(arg1, arg1), nand(arg2, arg2))
All you need are function definitions and function calls. You don't need any branching, conditionals, operators or builtin functions. I will demonstrate an implementation using ECMAScript.
First, let's define two functions called true and false. We could define them any way we want, they are completely arbitrary, but we will define them in a very special way which has some advantages as we will see later:
const tru = (thn, _ ) => thn,
fls = (_ , els) => els;
tru is a function with two parameters which simply ignores its second argument and returns the first. fls is also a function with two parameters which simply ignores its first argument and returns the second.
Why did we encode tru and fls this way? Well, this way, the two functions not only represent the two concepts of true and false, no, at the same time, they also represent the concept of "choice", in other words, they are also an if/then/else expression! We evaluate the if condition and pass it the then block and the else block as arguments. If the condition evaluates to tru, it will return the then block, if it evaluates to fls, it will return the else block. Here's an example:
tru(23, 42);
// => 23
This returns 23, and this:
fls(23, 42);
// => 42
returns 42, just as you would expect.
There is a wrinkle, however:
tru(console.log("then branch"), console.log("else branch"));
// then branch
// else branch
This prints both then branch and else branch! Why?
Well, it returns the return value of the first argument, but it evaluates both arguments, since ECMAScript is strict and always evaluates all arguments to a function before calling the function. IOW: it evaluates the first argument which is console.log("then branch"), which simply returns undefined and has the side-effect of printing then branch to the console, and it evaluates the second argument, which also returns undefined and prints to the console as a side-effect. Then, it returns the first undefined.
In λ-calculus, where this encoding was invented, that's not a problem: λ-calculus is pure, which means it doesn't have any side-effects; therefore you would never notice that the second argument also gets evaluated. Plus, λ-calculus is lazy (or at least, it is often evaluated under normal order), meaning, it doesn't actually evaluate arguments which aren't needed. So, IOW: in λ-calculus the second argument would never be evaluated, and if it were, we wouldn't notice.
ECMAScript, however, is strict, i.e. it always evaluates all arguments. Well, actually, not always: the if/then/else, for example, only evaluates the then branch if the condition is true and only evaluates the else branch if the condition is false. And we want to replicate this behavior with our iff. Thankfully, even though ECMAScript isn't lazy, it has a way to delay the evaluation of a piece of code, the same way almost every other language does: wrap it in a function, and if you never call that function, the code will never get executed.
So, we wrap both blocks in a function, and at the end call the function that is returned:
tru(() => console.log("then branch"), () => console.log("else branch"))();
// then branch
prints then branch and
fls(() => console.log("then branch"), () => console.log("else branch"))();
// else branch
prints else branch.
We could implement the traditional if/then/else this way:
const iff = (cnd, thn, els) => cnd(thn, els);
iff(tru, 23, 42);
// => 23
iff(fls, 23, 42);
// => 42
Again, we need some extra function wrapping when calling the iff function and the extra function call parentheses in the definition of iff, for the same reason as above:
const iff = (cnd, thn, els) => cnd(thn, els)();
iff(tru, () => console.log("then branch"), () => console.log("else branch"));
// then branch
iff(fls, () => console.log("then branch"), () => console.log("else branch"));
// else branch
Now that we have those two definitions, we can implement or. First, we look at the truth table for or: if the first operand is truthy, then the result of the expression is the same as the first operand. Otherwise, the result of the expression is the result of the second operand. In short: if the first operand is true, we return the first operand, otherwise we return the second operand:
const orr = (a, b) => iff(a, () => a, () => b);
Let's check out that it works:
orr(tru,tru);
// => tru(thn, _) {}
orr(tru,fls);
// => tru(thn, _) {}
orr(fls,tru);
// => tru(thn, _) {}
orr(fls,fls);
// => fls(_, els) {}
Great! However, that definition looks a little ugly. Remember, tru and fls already act like a conditional all by themselves, so really there is no need for iff, and thus all of that function wrapping at all:
const orr = (a, b) => a(a, b);
There you have it: or (plus other boolean operators) defined with nothing but function definitions and function calls in just a handful of lines:
const tru = (thn, _ ) => thn,
fls = (_ , els) => els,
orr = (a , b ) => a(a, b),
nnd = (a , b ) => a(b, a),
ntt = a => a(fls, tru),
xor = (a , b ) => a(ntt(b), b),
iff = (cnd, thn, els) => cnd(thn, els)();
Unfortunately, this implementation is rather useless: there are no functions or operators in ECMAScript which return tru or fls, they all return true or false, so we can't use them with our functions. But there's still a lot we can do. For example, this is an implementation of a singly-linked list:
const cons = (hd, tl) => which => which(hd, tl),
car = l => l(tru),
cdr = l => l(fls);
You may have noticed something peculiar: tru and fls play a double role, they act both as the data values true and false, but at the same time, they also act as a conditional expression. They are data and behavior, bundled up into one … uhm … "thing" … or (dare I say) object!
Indeed, tru and fls are objects. And, if you have ever used Smalltalk, Self, Newspeak or other object-oriented languages, you will have noticed that they implement booleans in exactly the same way. I will demonstrate such an implementation here in Scala:
sealed abstract trait Buul {
def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): T
def &&&(other: ⇒ Buul): Buul
def |||(other: ⇒ Buul): Buul
def ntt: Buul
}
case object Tru extends Buul {
override def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): U = thn
override def &&&(other: ⇒ Buul) = other
override def |||(other: ⇒ Buul): this.type = this
override def ntt = Fls
}
case object Fls extends Buul {
override def apply[T, U <: T, V <: T](thn: ⇒ U)(els: ⇒ V): V = els
override def &&&(other: ⇒ Buul): this.type = this
override def |||(other: ⇒ Buul) = other
override def ntt = Tru
}
object BuulExtension {
import scala.language.implicitConversions
implicit def boolean2Buul(b: ⇒ Boolean) = if (b) Tru else Fls
}
import BuulExtension._
(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3
This BTW is why the Replace Conditional With Polymorphism Refactoring always works: you can always replace any and every conditional in your program with polymorphic message dispatch, because as we have just shown, polymorphic message dispatch can replace conditionals by simply implementing them. Languages like Smalltalk, Self and Newspeak are existence proof of that, because those languages don't even have conditionals. (They also don't have loops, BTW, or really any sort of language built-in control structures except for polymorphic message dispatch aka virtual method calls.)
You could also define or using pattern matching, or something like Haskell's partial function definitions:
True ||| _ = True
_ ||| b = b
Of course, pattern matching is a form of conditional execution, but then again, so is object-oriented message dispatch.
Another way to express the logical operators as an integer arithmetic expressions (where feasible). This way can avoid lots of branching for a larger expression of many predicates..
Let True be 1 Let False be 0
if the summation of both is greater than 1 then it is true or false to be returned.
boolean isOR(boolean arg1, boolean arg2){
int L = arg1 ? 1 : 0;
int R = arg2 ? 1 : 0;
return (L+R) > 0;
}
Here's another way to define OR, or indeed any logical operator, using the most traditional way of defining it: use a truth table.
This is of course quite trivial to do in higher level languages such as Javascript or Perl but I'm writing this example in C to show that the technique does not depend on high level language features:
#include <stdio.h>
int main (void) {
// Define truth table for OR:
int OR[2][2] = {
{0, // false, false
1}, // false, true
{1, // true, false
1} // true, true
}
// Let's test the definition
printf("false || false = %d\n",OR[1==2]['b'=='a']);
printf("true || false = %d\n",OR[10==10]['b'=='a']);
// Usage:
if (OR[ 1==2 ][ 3==4 ]) {
printf("at least one is true\n");
}
else {
printf("both are false\n");
}
}
You can do the same with AND, NOR, NAND, NOT and XOR. The code is clean enough to look like syntax such that you can do stuff like this:
if (OR[ a ][ AND[ b ][ c ] ]) { /* ... */ }
The two forms:
OR(arg1, arg2)
if arg1
return True
else:
return arg2
OR
OR(arg1, arg2)
if arg1
return arg1
else:
return arg2
Have as well as the code golf-like advantage of being a bit smaller than the other suggestions so far, one less branch. It's not even that silly a micro-opt to reduce the number of branches if we're considering the creation of a primitive that would hence be very heavily used.
Javascript's definition of || is akin to this, which combined with its loose typing means that the expression false || "abc" has the value "abc" and 42 || "abc" has the value 42.
Though if you already have other logical operators then the likes of nand(not(arg1), not(arg2)) might have the advantage of no branching at all.
All the good answers have already been given. But I won't let that stop me.
// This will break when the arguments are additive inverses.
// It is "cleverness" like this that's behind all the most amazing program errors.
or(arg1, arg2)
return arg1 + arg2
// Or if you need explicit conversions:
// return (bool)((short)arg1 + (short)arg2)
Alternatively:
// Since `0 > -1`, negative numbers will cause weirdness.
or(arg1, arg2)
return max(arg1, arg2)
I hope no one would ever actually use approaches like these. They're here only to promote awareness of alternatives.
Update:
Since negative numbers can break both of the above approaches, here is another awful suggestion:
or(arg1, arg2)
return !(!arg1 * !arg2)
This simply uses DeMorgan's Laws and abuses the fact that * is similar to && when true and false are treated like 1 and 0 respectively. (Wait, you're saying this isn't code golf?)
Here's a decent answer:
or(arg1, arg2)
return arg1 ? arg1 : arg2
But that's essentially identical to other answers already given.
In addition to all the programmed solutions using the if construct, it's possible to construct an OR gate by combining three NAND gates. If you want to see how it's done in wikipedia, click here.
From this, the expression,
NOT[ NOT( A AND A ) AND NOT( B AND B )]
which uses NOT and AND gives the same answer as OR. Notice that the use of both NOT and AND is just an obscure way of expressing NAND.
One way to define or is via a lookup table. We can make this explicit:
bool Or( bool a, bool b } {
bool retval[] = {b,true}; // or {b,a};
return retval[a];
}
we create an array with the values that the return value should have depending on what a is. Then we do a lookup. In C++ like languages, bool promotes to a value that can be used as an array index, with true being 1 and false being 0.
We can then extend this to other logical operations:
bool And( bool a, bool b } {
bool retval[] = {false,b}; // or {a,b};
return retval[a];
}
bool Xor( bool a, bool b } {
bool retval[] = {b,!b};
return retval[a];
}
Now a downside of all of these is that it requires prefix notation.
namespace operators {
namespace details {
template<class T> struct is_operator {};
template<class Lhs, Op> struct half_expression { Lhs&& lhs; };
template<class Lhs, class Op>
half_expression< Lhs, Op > operator*( Lhs&&lhs, is_operator<Op> ) {
return {std::forward<Lhs>(lhs)};
}
template<class Lhs, class Op, class Rhs>
auto operator*( half_expression<Lhs, Op>&& lhs, Rhs&& rhs ) {
return invoke( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
}
}
using details::is_operator;
}
struct or_tag {};
static const operators::is_operator<or_tag> OR;
bool invoke( bool a, or_tag, bool b ) {
bool retval[] = {b,true};
return retval[a];
}
and now you can type true *OR* false and it works.
The above technique requires a language that supports argument dependent lookup, and templates. You could probably do it in a language with generics and ADL.
As an aside, you can extend the *OR* above to work with sets. Simply create a free function invoke in the same namespace as or_tag:
template<class...Ts>
std::set<Ts...> invoke( std::set<Ts...> lhs, or_tag, std::set<Ts...> const& rhs ) {
lhs.insert( rhs.begin(), rhs.end() );
return lhs;
}
and now set *OR* set returns the union of the two.
This one remembers me the charasteristic functions:
or(a, b)
return a + b - a*b
This only applies to languages which can treat booleans as (1, 0). Does not apply to Smalltalk or Python since boolean is a class. In smalltalk they go even further (this will be written in sort of a pseudocode):
False::or(a)
return a
True::or(a)
return self
And the dual methods exist for and:
False::and(a)
return self
True::and(a)
return a
So the "logic" is perfectly valid in the OP statement, althought it is verbose. Beware, it is not bad. It is perfect if you need a function which acts like a mathematical operator based on, say, a kind of matrix. Others would implement an actual cube (like a Quine-McCluskey statement):
or = array[2][2] {
{0, 1},
{1, 1}
}
And you will evaluate or[a][b]
So yes, every logic here is valid (except that one posted as using the in-language OR operator xDDDDDDDD).
But my favorite one is the DeMorgan's law: !(!a && !b)
Look at the Swift standard library and check out their implementation of the shortcut OR and shortcut AND operations, which don’t evaluate the second operands if not needed/allowed.
The logic is perfectly correct, but can be simplified:
or(arg1, arg2)
if arg1 = True
return True
else if arg2 = True
return True
else
return False
And presumably your language has an OR operator so - unless it's against the spirit of the question - why not
or(arg1, arg2)
if arg1 = True or arg2 = True
return True
else
return False
