Clearer Conditionals using De Morgan's Laws | Hacker News Reader

Clearer Conditionals using De Morgan's Laws

robots.thoughtbot.com

115 pointsgabebw79 comments

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).

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.

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.

OK; I see what you mean now. The article assumes the only possible states are "trusted" or "untrusted", and you disagree with that assumption.

Amazon.com is perhaps a better example. That site has multiple sign-in levels. It's not a binary state. I'm not sure what names they use, but I'll call them signed-in, signed-in-untrusted, and signed-out.

If you are fully signed-in, you can purchase something or make account changes. If you are signed-in-untrusted, you can put things in the cart associated with your account, but you can't purchase anything without typing a password. If you are signed out, you are fully dissociated from any account.

Note that you can refactor that single trinary property into two binary properties: signed-in/signed-out and trusted/untrusted. (Signed-out+trusted happens to be unused.)

Perhaps it's obvious, but it's true that every multi-state property (or set of properties) can be broken down into a set of binary properties like that, and the breakdown can be done in multiple ways. The resulting binary properties may not be have sensible names as they do in my example, but it can be done. In general, find all possible combinations of values for your set of many-state properties. Enumerate those combinations and write the numbers in binary. Each binary digit is a property in your new set of binary properties. There are multiple possible enumerations, so there are multiple possible mappings from a set of many-state properties to a set of binary properties.

For example, if you have a three-state property and a four-state property, then you'll a combination of 12 possible states. Number those 12 states. Write those numbers in binary. You'll need at least four binary digits. That means you'll have at minimum four binary properties. Those four properties can have 16 total states, so four of the states will be unused.

You can similarly decompose your properties into a set of three-state properties by writing your enumeration in base-three. I suppose you could also consider the current state of your program, with it's many multi-state properties (integers have lots of possible states, strings have even more), to be a single variable-base number that enumerates a state in the state-space of your program. If you consider the remaining input to your program to be part of your state, and the set of all possible outputs to be enumerated in a similar fashion, then the problem of programming is reduced to the building of a machine that maps numbers from one set to numbers in another. How hard can that be? So I'll need your project done by Monday.

The article title was clearer conditionals using DeMorgan's Law - to that end, the article illustrated how to move to that step for cleaner code through first applying the law.

Yes, and the other thing I find baffling is that a trivial post talking about something that would be covered in the first part of any baby logic course---before you even get to quantifiers!---is currently ranked as high as it is.

Many coders out there haven't taken a course that teaches symbolic logic or such. It's a simple article that wasn't aimed at you is all.

Math is hard, let's discuss what new blah.js is there, or how that new company abandoned managers and uses github to order vegan lunches.

Do tell more about how to use github to order vegan lunches.

The article was trivial. I upvoted because I learned about Karnaugh maps in the discussion.

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

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.

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.

> 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?

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.

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

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

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

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)

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.

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

A digital electronics class, more specifically.

Always go back to the K-maps.

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" :-)

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.

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.

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()
      }
   }

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.

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

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

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

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

What the sign clearly means is "no [members of the set] food and drink."

But what the sign says is either "no(food && drink)" or "no(food) && drink", depending on how you feel about precedence. The obvious implication in the first case is that either food or drink, or neither, but not both, is permissible; in the second, it's that drink is acceptable only when not also accompanied by food, but no other constraint is expressed with regard to either. If the intent was to express that neither food nor drink is permissible in any combination, the correct form, both logically and grammatically, would be "No food or drink".

That first statement is false because English “and” is not the same thing as logical “and”.

Rebels.

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

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!

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

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.

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

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).

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.

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.

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

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.

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.
  }

Interestingly I've been going back and forth on this lately. I have been playing around with SD cards on the STM32F4 and a typical SD Card transaction consists of 3 to 10 commands which, if any one fails, the transaction fails. I'm currently using negative conditionals of the form "Not Error" (the Error test is an affirmative, and so that seems ok to me)

A typical sequence is like the one to set the bus width.

   err = sdio_select(rca);
   if (! err) {
     err = sdio_command(55, rca << 16);
     if (! err) {
       err = sdio_command(6, 2);
     }
   }
   sdio_deslect();
   return err;

I had originally done it the other way

  err = sdio_select(rca);
  if (err) {
     return err;
  }
  err = sdio_command(55, rca << 16);
  if (err) {
      sdio_deselect();
      return err;
  }
  err = sdio_command(6, 2);
  sdio_deselect();
  return err;

I find the first form more readable. It also generates fewer branches in the generated code. The sample code I first looked at was doing Goto's to the exit code (deselect/return error) which was unacceptable :-).

In the original article the confusion arose around negative test cases and then testing for them negatively (double negatives) which I think are always bad from a readability point of view.

What I've found myself doing in such cases is adding a function that processes multiple commands and indicates an error if any one of the commands failed (sdio_batch could be a varargs function):

  struct sdio_cmd {
      enum { SDIO_SELECT, SDIO_COMMAND } cmd;
      int reg; // Guesses at suitable names without
      int val; // knowing anything about SDIO
  }

  int sdio_batch(int count, ...);
  
  err = sdio_batch(3,
      &(struct sdio_cmd){ SDIO_SELECT, .val = rca },
      &(struct sdio_cmd){ SDIO_COMMAND, 55, rca << 16 },
      &(struct sdio_cmd){ SDIO_COMMAND, 6, 2 },
      );

I've been doing it in Ruby with network remote procedure calls, where it's not quite as ugly to use inline lists and variable argument counts as it is in C, and where branch count isn't quite as important.

The sample code I first looked at was doing Goto's to the exit code (deselect/return error) which was unacceptable :-).

What's so bad about a little goto between friends?

This is a nice structure, It also suggests something like closures where you inverse stacked the functions and did something like:

   int do_command(sdio_command_chain *cmd) {
           int err = 0;
           if (cmd->next) {
              err = do_command(cmd->next);
           }
           return (err) ? err : call_command(cmd->parms);
     }

Thanks for that!

I actually prefer your second form: return as soon as you know you are done in the function/method -- if nothing more can be done, then don't pretend to do any more.

In the case of cleanup that must be done in the end, perhaps 2 functions would be better: a top level func to acquire and dispose of resources, calling an inner func to do as much work as it can with the resources. (assuming something like C that doesn't have a "finally" clause like Java)

I've never understood how finding the end of a long / nested mess of if/else blocks, rather than leaving the function, is somehow better. Which one feels more like a GOTO in terms of least astonishment?

   > I actually prefer your second form: return as soon as
   > you know you are done in the function/method -- if 
   > nothing more can be done, then don't pretend to do 
   > any more.

The first form actually does that. As soon as one if condition fails, the code falls through down to the bottom and returns. This is most impressive in the initialization/identification phase (see sdio_open() [1]) because that has like a dozen commands it has to get through successfully. By collapsing this way it allows for common cleanup, and if the cleanup requirements change you only have to change it in one place.

The effect of the first form (in C) is to collapse all of the if's "else" clauses into a single one at the bottom.

As for finding the other end of an off screen if clause, I agree with you, that it is a crutch to use the 'find matching' command in the editor with the open brace. The interesting about this problem is that it is driven by the SDIO spec, which was driven by a strict requirement of backwards compatibility, which results in very carefully crafted command / response / flow options.

This discussion has been helpful for me as at some point I am going to have to describe this to people new to, or possibly unfamiliar with, programming which should be interesting.

[1] https://github.com/ChuckM/stm32f4-sdio-driver/blob/master/sd...

Not to drag the thread off topic, but this seems like the kind of situation where a version of Haskell's Maybe or Either monads might come in handy, so you could write:

    do
      command1
      command2
      ...

and have the failures propagate automatically.

One of the legitimate use cases for goto is for complex error handling. I'm not sure why it needs to be unacceptable across the board.

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

Unless they actually are a VB programmer and And doesn't short circuit.

`AndAlso` short circuits.

Fantastic! If only I could write Excel macros in vb.net

Yes, the that was a very simple example.

iirc, robotics commonly uses something similar called ladder logic.

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

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.

Well, this is a tutorial for Ruby programmers.

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

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

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).

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)

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.

Deleted comment

> In most programming languages, AND will short circuit. OR requires both operands to be evaluated.

Can you name any widely-used programming language(s) that has a short-circuit AND that returns on the first non-true result but not a short-circuit OR that returns on the first non-false result?

Huh? OR will short-circuit if the first element is true in every language I have ever seen (barring ones that don't short circuit at all).

Why OR doesn't short circuit?

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)

What IDE do you use ?

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?

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

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

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

Reply on news.ycombinator.com