Math You Can Use

Refactoring If Statements with De Morgan's Laws

When I was in college, years ago, I discovered a little trick to use De Morgan's Laws, a basic principle from Discrete Math, to manipulate logical statements while Programming and I employ it whenever it fits. I started doing this so long ago that I do not recall if I came up with it on my own, I did take a lot of extra Logic classes in college, or if I picked it up from someone else. So naturally I was excited to write a blog entry about it and did, however, as I was finishing it up it occurred to me to Google it, and although I was not really surprised to find other mention of the idea, I was, however, dismayed to find out that Steve McConnell mentions it in his book, Code Complete, which is highly recommended and also has been on my list of books to read, I guess I am disheartened because now it might seem like I am just taking an idea from a fairly prominent book, and in looking through the book I see many good ideas, some that I think have been expressed by others as well, so the re-expressing a good software idea seems both justifiable and one that is consistent with the goals of my blog, so I am glad that I did not Google it earlier which might have discouraged me from writing this.

In Code Complete, this idea is treated, consistent with the rest of the book, very practically and concisely. It is discussed solely as a refactoring technique, and it is a good one to know, but to me it is much more than that, it is the actual application of Math to that act of Programming! And this presents an opportunity to use this technique to help Programmers understand an interesting Mathematical concept.

So let’s run through how this works. To apply this to Programming mechanics we can look at this from a symbol manipulation point of view, after all Programming in some senses is the manipulation of lexical symbols. Strictly speaking, it involves symbolic variants, if you will, of the distributive property and of factoring, in regards to the negation symbol.

The two forms of Demorgan’s Law, described using standard Java/C++ logical operators are:

!(a || b) == (!a && !b)

!(a && b) == (!a || !b)

Looking at either of the above logical forms of the De Morgan’s statements, identities actually, you can see that going left to right, the negation symbol is "distributed" across the two terms and going right to left, the negation symbol is "factored" out from the two terms and applied to the whole statement. Each operation causes the "and" symbol to be swapped with the "or" symbol or vice versa. A simple mnemonic might be "either distribute and flip or factor and flip." Please note that flip means switching between these two operators, and that these are not inverse operations.

Ok, so let’s put this to use, a recommended refactoring, also mentioned in Code Complete, is the "Reverse Conditional," . If you were to come across the following Java/C++ code, you would look at it and see that it is negative, if you have been using the Demorgan’s Law refactoring trick, you will instantly know how to refactor it:

if((a != b) || (c != d)) {

statementA1;

...

statementAn;

} else {

statementB1;

...

statementBn;

}

So we need to get the positive conditional which means we need to negate the current if statement’s logic, let’s walk through it:

First we’ll pull the negative’s out, using the following rule:

(x != a) == !(x ==a), I don’t know what this is called, but it should be pretty obvious that it is true.

So now we have:

if(!(a == b) || !(c == d)) {

Now we factor and flip:

if(!((a == b) && (c == d))) {

Negating gets rid of the "!" because !!x == x, which is called double negation, and the final refactored code with the if and else blocks reversed is:

if((a == b) && (c == d)) {

statementB1;

…

statementBn;

} else {

statementA1;

…

statementAn;

}

So now, you either already knew this or now know it, if this is new to you I would recommend that practice it. Perhaps write some test code and play with the various forms translating each form back and forth and seeing how the logic works.

Now let’s look at this from a more formal perspective:

¬ (p ∨ q) ⇔ (¬ p) ∧ (¬ q)

¬ (p ∧ q) ⇔ (¬ p) ∨ (¬ q)

Just a couple quick notes on the notation here, you most likely already know these ideas, but in case you are not familiar with this notation: The symbol ¬ means logical negation, the symbol ∧ is logical conjunction, aka "and," the symbol ∨ is logical disjunction aka "or," and the double arrow ⇔ means logical equivalence which can be read as "if and only if." The parentheses serve the usual purpose.

De Morgan’s laws also apply to set theory, and the Set Theoretic forms of De Morgan's Laws are:

Where ∪ is set union, ∩ is set intersection and X is set complementation.

If you received a CS degree then most likely you took some form Discrete Math which probably included Set Theory and possibly some basic Propositional Logic, if for whatever reason you didn’t learn them, I highly recommend learning them, and if you’ve forgotten them, I highly recommend reviewing them.

Set theory and Propositional Logic are intertwined, with a number of concepts which run parallel between the two disciplines and De Morgan's Law is not the only one. Additionally it seems that De Morgan's Law shows up a few other places as well.

Logic is a central construct in Programming and Math, in many respects it is one of the foundations of all of Math, of course like all things in Math it can also become very involved and complex once you dig just slightly below the surface, but this is really a good thing because it will never get boring. Also the interrelationship between Logic and Set Theory seems, to me, to be pretty intricate and extremely profound.

If you are a non Math oriented Programmer but want to be, my recommendation is that you take this refactoring trick and its associated Logic related Math and study it and make it part of your repertoire of skills. To put in mantra form: Learn it. Know it. Live it.

Typing vs. Editor Kung Fu

There have been some interesting blogs about the role of typing in programming, specifically I am referring to Jeff Atwood’s "The Keyboard Cult:", and in general his series on the topic and John Cook’s rebuttal: "How much does typing speed matter?". IMHO they both make good points and they both miss the point as they don’t take into account the role of Editor Kung Fu.

It’s not your typing speed, but your editing speed, which is painfully obviously to me as I clumsily type out this entry. Whoa, I’m having a weird self referential moment right now. My typing skills are mediocre in comparison to others I have seen, I position my fingers mostly correctly, however, I occasionally have to look and I’m slow when I have to type every character.

However, my relatively slow typing speed is irrelevant to my programming speed, it really boils down to the editor you use and how you use it, I mostly use a relatively obscure editor called Zeus, the reason I use this editor is because it supports an arcane key-mapping known as the Brief key-bindings, which originates from a DOS, yes MS-DOS, based editor called Brief, which I believe had some similarity to Emacs. I learned this a while ago, obviously, but the key-bindings and features are incredibly powerful, I feel that I am 3 to 5 times faster using these key-bindings vs. traditional vanilla Eclipse key-bindings and features. Due to my Editor Kung Fu I have seen cases where I easily outperform, in code production, other programmers who have superior typing skills, and of course this is partially due to a difference in ability and experience.

Interestingly this essay evokes a few of anecdotes from my career, one was by a coworker from about ten years ago who was noticing that when I was working my hands barely left the key board, he added that the younger programmers used the mouse much more during coding. Perhaps, my most poignant example demonstrates the true power of having a highly sophistimacated editor, a few years back I was working with a DBA and we needed to create a script that would replace a specific database field with a list provided in an excel file, about 300 rows that needed to be updated. Both the old and new value were provided as matching columns in an excel file, I spoke with her and she told me what needed to be done, using column cutting and pasting I was able to create the entire script, consisting of 300 update statements in a matter of minutes and I emailed it to her. She called me back after receiving it, and she was blown away that I had already written the whole script, I told her it was just editing tricks and that she could do it if she knew my editor, she responded with "I need to learn that editor."

My most surreal account would be that on a couple of occasions I’ve been told that my screen looked like the Matrix when I was coding, this wasn’t due to my lightning fast speed but to the use of keyboard macros to modify long SQL insert scripts, the weird thing is it really does look like the Matrix, ironically I never noticed it myself, probably because at the time I was in the Matrix.

My editing speed is also in part, due to experience, recently a young programmer remarked as he watched me edit, "You are so fast, man," and I replied, "It’s just a lots of years of practice." I mostly agree with John Cook’s points, however, I disagree about the musical analogy, when I am in the zone coding, I feel like I am working that keyboard like a musical instrument, it’s hard to describe, you just have to do it to know what I am saying.

When you construct a compiler you create several components the two "front end" components are the Lexical Analyzer and the Parser, these two create what is known as an Acceptor, although this particular Acceptor would be a PDA. I feel that when you type every character you are programming at the lexical level, when you are cutting and pasting variable names and other constructs you are programming at the Syntactic level. When you are coding at this level your edits are more conceptual.

Keyboard macros are a powerful feature, in Brief/Zeus you can perform an operation and record it and play it back, also no decent editor is without Regex Search and Replace, and any powerful editor will have column cutting and pasting. The true beauty of the Brief key-bindings is that it provides you with rich and easy to use cut and pasting and it turns the keyboard number pad into an editing super controller which lets you keep your hands on the keyboard, going to the mouse will always slow you down.

Editor Kung Fu is when your brain, fingers and your editor move in concert to produce code quickly and efficiently, which means that superior coding ability includes a combination of: "Typing" + "Editor Kung Fu" + "Ability."

So there it is: My Kung Fu is the best.