Clearer Conditionals using De Morgan's Laws

http://robots.thoughtbot.com/clearer-conditionals-using-de-morgans-laws/

by gabebw • 13 years ago

115 75 13 years ago

robots.thoughtbot.com

bennyg• 13 years ago

Good naming conventions are pretty key here. My guess is the original writer of that code had used those in something else entirely, then reused those methods in a new method so he wouldn't have to rewrite.

I always feel like it's better to positively name Boolean values, personally, but I know everyone is different.

saraid216• 13 years ago

What he hand-waves is that he's got something that looks like this:

  def signed_out?
    # Code
  end
  
  def signed_in?
    !signed_out?
  end

Which can easily start to become its own problem. On the other hand, with Ruby, it might be worthwhile to define something like Class#invert such that you have this:

  def signed_out?
    # Code
  end
  method_invert :signed_out?, :signed_in?

Dunno. I haven't ever found myself in a position where it mattered.

glifchits• 13 years ago

Cool to see De Morgan's Laws used at a high level. But the real takeaway: rewrite your conditional until it makes sense.

ChuckMcM4• 13 years ago

Or conversely that it is better to write affirmative conditionals rather than negative conditionals. I always find reading the affirmative ones much easier, as I have always found working in positive logic easier than work with negative logic circuits.

VBprogrammer2• 13 years ago

Except where writing negative conditionals are clearer. For example turning:

  if(a) {
    if(b) {
      if (c) {
        // Do something.
      }
    }
  }

Into:

  if(!a) {

  } elseif(!b) {

  } elseif(!c) {

  } else { 
    // Do something.
  }

abalashov• 13 years ago

More widespread knowledge of all the other classical deductive logical equivalences can make program syntax clearer, too. :-)

joeframbach2• 13 years ago

Alternative title: Why a CS degree is worthwhile even if you're a web developer.

dj-wonk2• 13 years ago

In my experience, electrical engineering curriculums instill logical thinking (e.g. Boolean logic) in ways that most computer science programs overlook. (This is fine and probably quite reasonable.) But when every logic gate counts, you must think differently about boolean expressions!

discom4rt• 13 years ago

The distributivity law is also really helpful for simplifying conditionals. http://en.wikipedia.org/wiki/Boolean_algebra#Monotone_laws

kenko3• 13 years ago

The transition from !signed_out? to signed_in? is entirely non-logical, so it's hard to see what it's doing in this post, which is supposedly illustrating logical laws (two of the most elementary logical laws, at that, that I'm surprised it would ever have occurred to someone to think needed introduction to an audience of professional programmers).

socillion2• 13 years ago

Not not x is equivalent to x using the double negation rule (DN).

"Not signed out" can be rephrased as "not not signed in" and thus simplified to "signed in". Same for "not untrusted ip" equaling "not not trusted ip" and, after DN, simply "trusted ip".

It's completely logical, so I'm not sure what your point is. Perhaps the article should have explained this better.

kenko3• 13 years ago

The fact that "signed out" and "signed in" are opposites is not a logical fact; there's no general inference from "not p_out" to "p_in".

If you had "outside" and went from !outside?" to "inside?", that would be erroneous (you could also be on the threshold).

ETA: this is especially obvious for trusted/untrusted; it doesn't have to be the case that every ip is either positively trusted or positively untrusted. If, in some application, it is binary in that way, then you can, in that case, go from not untrusted to trusted. But that isn't justified by purely logical considerations.

ETA again, in fact a better example is this, it's not a logical fact that if you flip a coin and it comes up not-heads, it has come up tails. (Even ignoring improbably things like its landing on its side.) That's a conclusion that is justified by knowledge of the substantive domain of coins.

batbomb• 13 years ago

If you want to get good at clarifying conditionals, take an electronics class and revel in the Karnaugh maps.

tsmith• 13 years ago

I transferred midway through my undergraduate degree, and was surprised to discover that Karnaugh maps weren't taught at my destination school - they are such an intuitive and straightforward mechanism for whittling down complex logic into its simplest form.

nollidge• 13 years ago

Always go back to the K-maps.

RamiK• 13 years ago

No need for a full blown electronics class. This subject falls under Switching Theory and can be covered thoroughly in the first (and often a single) semester. Starting with elementary set theory and boolean algebra, you go into the combinatorial logic (that covers De Morgan and Karnaugh), and finish with finite state machines (automata).

There are very few requisites too. Some high schools and trade schools teach the material to 16-18 year-olds in a year or two. I suspect this is partially why it's so often omitted in CS curriculum. It's too easy.

krisgee• 13 years ago

Yeah, K-maps were part of the circuit design course we had to take for our undergrad CS degree.

signa11• 13 years ago

yup, zvi-kohavi is a good text...

dorian-graph• 13 years ago

Starting with elementary set theory and boolean algebra, you go into the combinatorial logic (that covers De Morgan and Karnaugh), and finish with finite state machines (automata).

Do you happen to have a link to an online course, textbook or other resource that covers this in a combined way that flows to well?

mindcrime• 13 years ago

My Discrete Math 101 course (UNC-Wilmington) covered Karnaugh Maps, along with a heavy dose of Boolean Algebra. For various historical reasons, I've actually taken Discrete Math twice, and have noticed that the content of a class titled such can very dramatically. The other Discrete Math course had much less emphasis on Boolean Algebra and logic, and a lot more on elements of probability and statistics.

bcbrown• 13 years ago

That was a very painful module to take, but it was incredibly useful.

baddox2• 13 years ago

A digital electronics class, more specifically.

flpgr• 13 years ago

I don't think this is necessary. I never wrote a conditional complicated enough to make me even think about getting down to K maps and I believe such a thing would be actually a smell and better be refactored as a whole. Knowing some boolean algebra is nice, though

dugmartin• 13 years ago

They were covered when I took my first CS math class (discrete math) - I'd imagine they are still part of the standard basic CS core (that was 24 years ago so it might have changed)

zerohp• 13 years ago

I am at a highly ranked school right now and they are not covered in any CS class. Computer Engineering majors learn them in their introductory course.

dj-wonk2• 13 years ago

No! Don't stop there! Don't quit until you've refactored all of your conditionals to use NAND's! http://www.physicsforums.com/showthread.php?t=442775

morgante• 13 years ago

Sorry, but I just don't see what was unclear about the original conditional. Anyone with a basic grasp of logic could parse it instantly.

As for the refactoring, that might be a good choice (I myself prefer positive boolean methods) but it's not a logic lesson.

yogo• 13 years ago

I see the double negative in code the same as it is in English (and probably any verbal language). Even though I can understand the first version of this code, for me second version can be understood much faster. The lesson I gathered is one that's already taught in verbal languages: double negatives should not be used (or used sparingly).

stan_rogers• 13 years ago

Actually, double negatives are the norm in natural languages. Prescriptive "standard" English is weird in that there's a notion that there's a sort of algebraic multiplication of negatives/negators. As in most non-standard English dialects, a construct shaped like "I haven't done nothing" usually means exactly the same as "I haven't done anything" in most languages (and the double-negative version is usually considered to be more proper or more elegant). Yes, there is a way of looking at things that says we have gained some precision of language by the artificial imposition of a lot of the "rules" of English imposed (primarily and almost exclusively) by self-declared experts in the late seventeenth and eighteenth centuries, but there is no evidence that many of the rules that are more commonly broken than followed in vernacular English ever exited before Lowth, Murray and a handful of their contemporaries told us that they knew what was best for us.

velis_vel• 13 years ago

I don't not agree, it was perfectly not unclear at all.

praptak2• 13 years ago

Old CS students' prank: improving the "no food and drink" sign unsurprisingly often found in labs by scribbling "no (food && drink) == (no food || no drink)" on it.

ygra• 13 years ago

Wouldn't that be (no food) and (drink) anyway?

praptak2• 13 years ago

Dunno, maybe spoken language does not have such strict operator priority. Or maybe it has one different than maths and programming languages.

dmak• 13 years ago

Rebels.

danpalmer• 13 years ago

Our CS labs solved that by allowing any food and drink we want. Dominos understand "the undergrad labs, ECS" as an address.

jjaredsimpson• 13 years ago

Those pranksters just don't understand the left distributive law of foodstuffs.

ChristianMarks• 13 years ago

Well, this is a tutorial for Ruby programmers.

VeejayRampay• 13 years ago

Ruby tends to be a very straightforward and readable language though, it's as good as it gets for this kind of example.

yarou• 13 years ago

I guess it depends on whether or not you want your code to read like natural language.

The refactored version reads like:

Allow access to the site if the user is signed in or has a trusted IP.

The original (DeMorgan's applied):

Allow access to the site if the user isn't signed out or doesn't have an untrusted IP.

It does help to have a good understanding of propositional logic and Boolean algebra, though.

snorkel• 13 years ago

So don't use non-assertive redundant uninverted comparisons or otherwise use positive conditionals unless the reverse is negative because it might not be clear or unless it is the opposite.

radicalbyte• 13 years ago

This is why every developer should read Code Complete - it contains a myriad of tips learnt through many years of hard work.

Suffice to say that it contains such tips as avoiding negation in conditionals.

In the end it boils down to strategic optimization towards readability with the least mental overhead (the cycles you spend parsing, the more you can spend thinking).

Roboprog3• 13 years ago

As weird as it sounds, "or" ends up being kind of evil, and something to avoid, as well. Mix it with "and", and the result likely doesn't say what your tired brain thought it did. Also, how many "or" statements have you seen that should really be set membership tests? (it helps to have a language that makes it easy to make a literal of a set)

Roboprog3• 13 years ago

Yep, learned that back in college, more years ago than I should admit.

Experience then teaches that if the expression is complicated enough for that to matter, you've already lost. Instead, make a boolean function with explicit "short circuit" returns.

    // return true if we're screwed
    isScrewed ( relevant parameters...):
        if failure-mode-one:
            return true
        if failure-mode-two:
            return true
        if guaranteed-save-otherwise:
            return false
        if failure-mode-three:
            return true
        return false

I remember seeing a horrible "if" statement that caused many thousands of dollars worth of wasted inventory back at one job cuz the clever coder thought he know the operator precedence and was saving time and money jamming a bunch of crap on one "if" line.

Now if I could just get coworkers to stop writing "fooFlag == true" and "fooFlag == false" :-)

minor_nitwit• 13 years ago

It's about Ruby conditionals, but they didn't talk about my favorite part.

   eat_gruel unless has_parents?
   puts "Please sir, I want some more" if shortest_straw?

elwell2• 13 years ago

How does this get so many upvotes? Besides being rather straightforward logic, it's taught in surely every comp sci 101 course.

aimhb• 13 years ago

Clearly you haven't been to many comp sci 101 courses.

elwell2• 13 years ago

actually we learned this in AP comp sci in high school.

joe_the_user• 13 years ago

While it's nice learn De Morgan's Law if you don't know it, it occurs to me that the problem of finding the simplest version of a given logical expression in n logical variables is a classic NP-complete problem (or NP-hard, the simpler question of whether the negation of an expression can be reduced to true is basically SAT).

There is no easy method to reduce every expression to a simple normal form - the conjunctive normal form of a given be exponentially larger than the original expression, etc.

nraynaud• 13 years ago

I sometime get my IDE to rotate the various representations of a boolean equation to try to find a better looking one (it's not always the shortest, sometimes some concept make more sense, like in his example)

delian66• 13 years ago

What IDE do you use ?

AYBABTME• 13 years ago

Something more useful I've found with DeMorgan is to flatten nested ifs:

   if (hasBread) {
      // do something
   }

Can be flattened to:

   if (!hasBread) {
      return
   }

As you start your function, flush out all the edge cases, invalid conditions and errors, then at every step forward in the function, you know you're always in a state were the odd balls have been taken care of and you deal with the general case.

This has two advantages:

   - it keeps the code tidy (the important parts are pretty 
     much never in a nested block).
   - it makes you handle the odd balls explicitely.

I really hate seeing functions such as :

   func cookBread() {
      if (hasBread) {
         do()
         a()
         bunch()
         of()
         stuff()
      }
   }

Clearer Conditionals using De Morgan's Laws

Related Stories