Boolean Algebra and Recursion

We’ve spent the last few sections building up to creating highly complex programs. The specific style of programming we’re going to use is Recursion, which is a way of scaling up simple functions to massively complex problems. These are problems that can run on hundreds or even thousands of processors, where the functions interact with each other in a very specific way.

Before we start with recursion, however, we’ll first do a quick refresher on logic. The magic of logic is that it lets us reason about unseen cases, and to be confident that our programs will work even before we run them. Way back in the introduction to this CBOOK, we talked about how skilled programmers don’t leap into coding, rather they spend time thinking about: How do I design my program so that it will work first time? Logic and abstraction are key to this, in fact, the first computer, the Difference Engine, was designed in 1822 by Charles Babbage, just a year after Faraday’s electric engine was unveiled. This machine was capable of solving polynomial functions, and just eight years later, in 1822, he designed the Analytical Engine, which was programmable, had memory, a printer and a CPU, and it was mechanical!

This machine was so complex and ingenious that it was a full 153 years later before it was built, but it worked first time, because Babbage designed it so well.

The key figure in Computer Science logic is, of course, George Boole, who formalised logic with his Boolean Operators. We’re not going to do an introduction to Boolean Logic here, but the next section will do a quick review of logic and relational operators, and how to use them with λ calculus and Racket.