De Morgan's laws in Perl

We've been simplifying some ugly code recently, and De Morgan's laws have come up more than once. A developer on the team complained the Wikipedia entry obscured - from a developer's perspective - the simplicity of these quite useful transformation rules, so, expressed in Perl:

Given $p and $q as truth values:

(! ( $p && $q ) ) == ( (! $p) || (! $q) )
(! ( $p || $q ) ) == ( (! $p) && (! $q) )


NOT( p AND q ) is equivalent to (NOT p) OR  (NOT q)
NOT( p OR  q ) is equivalent to (NOT p) AND (NOT q)

So for example, say you come across a beauty like:

foo() unless (! $bar) or $baz;

You can use De Morgan's to translate it to:

foo() if $bar and (! $baz);

Wikipedia entry: De Morgan's laws


Yes, good old De Morgan is often a lot of use simplifying ugly conditionals. There are a whole bunch of other boolean algebra rules which can be of use too, such as distributivity...

if ($x && $z or $y && $z)

can be simplified as:

if ($x||$y and $z)

Though it is possible to become unstuck applying boolean algebra to Perl blindly. This is because Perl expressions can have side-effects, and are evaluated lazily. So, if foo() and bar() have side-effects, then:

if (foo() or bar())

can act differently to:

if (bar() or foo())

even if the principle of commutativity says that they should be equivalent. (This is another good reason to stick to the functional programming principle of writing zero-side-effect functions.)

On a side note, does anyone remember the good ol' Turbo Pascal days, when the compiler has an option to short-circuit boolean expression or not. So when short-circuiting is off:

if ($false && somefunc()) { ... }

would still execute somefunc() no matter what $false is.

How I lived through that, I'm still not sure.


Turbo Pascal! The Good Old Days. Someone who used that can't be all bad :-))).

As for short-circuiting, one of the most embarrassing days was when I did something like this, in Cobol (precise syntax mercifully forgotten :-):

if (a and b or c and d)...

Having spent too much time writing Burrough's (Over-extended) Algol (The Real Man's Language), I'd forgotten that in Cobol 'or' has higher precedence than 'and'.


I stared and stared at it, but could not see the problem, until another programmer looked over my shoulder and said 'Watch out for that...'.

The consequences were that the code outputted a blank record, which got sorted to the start of the next program's input file. This header record was meant to contain batch and record counts, but the 2nd program's checking was so lax, it let the blank record thru, as did the next program, and staggeringly, the next. Yep, four-in-a-row. The output, call up letters to a blood blank, was not pretty.

Ever since I've written:

if ( (a and b) or (c and d) )

no matter how 'simple' the expression.

So, "Over-parenthesize rather than Under-parenthsize", has been my motto to this day, and shall be ever more.

Because parameters to function calls are evaluated before the function is executed, it's pretty easy to create "eager" equivalents of "and" and "or"...

use 5.010;
sub AND { $_[0] and $_[1] }
sub OR  { $_[0] or  $_[1] }
sub foo { say "foo"; 1 }
sub bar { say "bar"; 0 }
# foo() executed, even though bar() was false
AND( bar(), foo() );
# bar() executed, then though foo() was true
OR( foo(), bar() );

It's just a shame the infix notation can't be reproduced (short of source filters anyway).

I just wanted to say that this is a nice, solid little post... I went through the same thing myself recently: getting annoyed at the mathematical notation used in the wikipedia page, and then re-writing them as more familiar programmer's constructs. (I also like you're other recent post about set operations, for similar reasons, but I should say something about it over there.)

There seems to be an unstated rule that a perl blog should only be used for cutting-edge work, but there's nothing wrong with reviewing basics.

(As for Pascal, that's one of the reasons I'm still a perl programmer: after Pascal, I became completely immune to language hype.)

Leave a comment

About Peter Sergeant

user-pic I blog about Perl.