5

I am recently studying computer science and I was introduced into boolean algebra. It seems that boolean algebra is used to simplify logic gates in hardware in order to make the circuit design minimal and thus cheaper. Is there any similar way that you can use it to reduce the number of code lines in your software in higher level languages like C++, C# or any other language?

22

You can use boolean algebra for many things in programming. It is a

  • basic calculation technique like adding, subtracting or multiplying numbers,

  • a multi-purpose tool, not just a tool for reducing the number of code lines in a program.

Note it is not a tool for just simplifying logic gates in hardware as well. However, it can sometimes be used for such cases (as well as for the opposite, or for completely different purposes).

For example, if your program contains an overly complicated boolean expression or sequence of conditionals, boolean algebra might help you to simplify the expression and the surrounding code. But that does not necessarily lead to less lines of code. In fact, sometimes complex one-line boolean code snippets get more maintainable when you split them up into several lines of code, and boolean algebra can help you to do this correctly.

So IMHO your question is like "can I use a pocket calculator to find the shortest route when traveling from A to B"? Sure you can, when you take a map with distance information for individual roads and use the calculator to add them up, and then pick the route with the smallest sum. But you could also use the calculator for finding longer routes, or for calculating completely different things.

21

Yes, you can. But should you?

Boolean algebra serves to reduce logical expressions to their minimal form, but whether this is good or bad is left to the programmer. Let's take this validation code:

...
if (person.Money == 0) return;
if (person.Money != 0 && person.Age < 15) return; 
if (person.Age > 90) return;
if (person.Children > 3) return;
if (person.HasWhiteShirt() && person.HasBlueSocks()) return;
...

This is a list of checks on the object person, and will exit the function as soon as one of those is true. The meaning of that is pretty clear, and anyone that reads it, even a non-programmer, can understand what checks we're doing.

There are different ways to write that, though. Let's go for lines of code and simplify it, as you asked in your question, and see what happens:

if (... || person.Money == 0 || person.Age < 15 || person.Age > 90 || person.Children > 3 || (person.HasWhiteShirt() && person.HasBlueSocks()) || ...) return;

We now have a single line of unreadable conditionals, and by simplifying we also lost the info that that <15 age check is somehow related to money. Editing this code is gonna be way more difficult in the future, so reducing it was a mistake.

In conclusion: Always go for readability, regardless of the minimal form of a logical expression.

  • 22
    A good compiler will "use Boolean algebra" internally to generate optimised code. Unless you are writing in assembler for an embedded system, make the source code easy to read and let the computer do the "clever stuff" for itself. – alephzero Jan 19 at 11:41
  • 30
    Honestly I would write it with ||s as in your second example, but split it so that each term is on a separate line. – Rotem Jan 19 at 12:10
  • 4
    FWIW, the check in 2nd line makes no sense - if we already checked the case that person.Money == 0 and if we had to return in such case, we can be 100% sure that person.Money != 0, so there's strictly no sense to check it. Also, it would be better if you just provide if (person.Age < 15 || person.Age > 90) instead of two separate checks, since it's a common idiom to do a range check that way (or even just use if ( !Range.of( 15, 90 ).contains( person.Age ) ) etc. – vaxquis Jan 19 at 14:56
  • 3
    @vaxquis True, but if the requirement really is person.Money != 0 && person.Age < 15, then having the extra condition makes that totally explicit. In the future, if person.Money == 0 needs to be removed and the second condition was just person.Age < 15 then a bug could be introduced if the editor does not realise that person.Money != 0 needs to be added again. – Richard Ward Jan 19 at 19:57
  • 2
    @vaxquis It can still be better to implement it that way, depending on how the business requirements are written. If your design doc lists the business requirements in exactly that order, implementing those exact checks in that exact order makes it easy to review the code and to be certain that it conforms to the requirements. "clever" code is an extremely big, but often underestimated, source of bugs. – Polygnome Jan 19 at 20:11
2

Boolean algebra is logic reduced to its most basic form. It maps nicely to a binary counting system, the second most basic imaginable counting system.

it seems that boolean algebra is used to simplify logic gates in hardware

Not quite. It makes it possible to implement any kind of logic in hardware in the first place. Once you have that, you can use software to build on that and create more complex logic again.

So no, you do not reduce the number of code lines using boolean algebra. You use it whenever there is a binary choice to be made. If your problem is complex, you are going to have a lot of choices in your software solution.

So it is the other way around: simple logic requires less boolean algebra, complex logic requires more. And more logic == more code.

2

Well, OK. The reason electronics engineers want to reduce the number of logic gates in a circuit is probably a matter of construction cost and operational performance of their final product. They are building the very thing that will do the work in the end.

When you are programming in any language other than assembly, the computer in the end will not execute your code, but a transformed version of it. This transformation from the programmer friendly language to the computer friendly language may be called «compilation». Boolean logic is indeed used by the compiler to achieve operational efficiency.

You may code in assembly and do the compiler's job yourself, but on a day-to-day basis, it becomes less and less worth the hassle. Modern compilers know more and more of the tricks, and better than you.

On the contrary, if you ask whether there exist a similar practice in higher-level languages, yes, it's called «refactoring», which means applying well-defined transformations to code chat change the structure and not the behaviour. In the 90s, Martin Fowler published a book that is a catalog of probably the most recurring basic refactorings in object languages.

1

Of course you can use Boolean Algebra for different cases in your project. This technique allows to get the same output with less steps and components when designing a circuit.

However in case of High-level languages it may result in more problems. HLL languages are designed for readability and ease of understanding. You can simplify your several lines of code into a single one, but it will become unreadable and complex, so much more time is required to grasp the idea of the code. Most of compilers perform such kind of optimizations by default.

All in all, I suggest not to think a lot about reducing lines of code, but consider behavior of the program in runtime, memory usage and architectual design. Generally when you are applying Boolean Algebra to your circuits you are acting as a compiler for most of existing languages.

0

To add to the existing discussion, including its idea that fewer lines is good if it also enhances readability, I'll just mention one thing you can do with Boolean algebra in a language where all values all truthy or falsy, such as Python. Here's a FizzBuzz solution in Python, written in a style that's achievable in just about any high-level language:

for i in range(1, 101):

    s = ''

    if i%3==0: s+= 'Fizz'

    if i%5==0: s+= 'Buzz'

    if s != '': print(s)

    else: print(i)

Now let's talk about what Python can do that some languages can't. For one, you can shorten

s != ''

to

s

because a string is truthy iff neither empty nor null (the latter wouldn't be achievable here). So we can replace the 2-line if/else statement with a 1-line

print(s or i)

In Python, "or" means "return the first argument if it's truthy, or the second if it isn't". It does not, in general, cast these values to Booleans; it just returns them as is.

I'd advocate the above make-it-shorter trick because I think it does in this case enhance readability, if only because

  1. by the time you're reading Python you hopefully know about truthy and falsy values (and if you don't know what Boolean operators do to them you'd better learn quickly to avoid some hilarious bugs!), and
  2. this is an example where fewer lines also gives you fewer concepts to think about when understanding the entire block.

In this case the benefit came because the same function needn't be mentioned in two lines of which only one is called, and we therefore seek an expression that equals this argument in every scenario, and we can get it using this not-all-that-little-known fact about how Python handles Boolean operators. I'd hate to have to write

s if s else i

or something even less succinct. (For starters, it'd arguably actually make it more confusing.)

You'll find several Python solutions to FizzBuzz here, using this trick but differing in what further Pythonic tricks they use to shorten the code even further. (They even show you can do the whole thing in one line, once you learn what happens when you multiply strings by integers.) These might be less conducive to readability, although of course they're worth learning how to do.

0

I used to think that changing:

if ($type == 'credit') {
  $total += $amount;
}

to:

$total += ($type == 'credit') * $amount;

was clever because it removed an if. Beware clever code! Code needs to be readable by both the programmer and the machine. It's the programmer's job to keep the code maintainable.

Usually, breaking a complex line into multiple, simpler lines will increase readability without significantly reducing performance. Only if benchmarking shows that there is a unacceptable performance issue should you refactor to increase performance at the expense of readability.

Boolean logic, as with everything else, should be used in the expected ways that make the code clear.

protected by gnat Jan 21 at 15:22

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.