Donating to Brown Dogs and Barbers: Small update

Some readers have recently reported to me that the PayPal donate button (which in theory should allow you to donate to the publication of my book Brown Dogs and Barbers) isn’t working.

I’m not certain yet, but I think PayPal have recently made changes that have stopped the button from working… I’m currently looking into getting it working again.

In the meantime, if you’re interested in using PayPal to donate to the production of my book, you can send contributions to my email address:

Thank you for your continued support.

Brown Dogs and Barbers: Donations have topped €1000!

Recently I launched a donation service whereby people who wanted to see my book, Brown Dogs and Barbers, in print, could donate in order to make it happen. The levels of funding and what each level brings are visible on the donations page.

I’m pleased to report that with your help the total recently went over €1000 – in fact they currently stand at €1085. This not only means I can now hire a proof reader and an artist, but I am almost at the point where I can commission the production of a paperback version that can then be put on sales in places like Amazon and Lulu.

I’d like to thank everyone who donated so far. There’s still more I’d like to do, so please either donate to the project or pass this information on.

Chapter 1: Inputs, Processes and Outputs

The definition of computer science

[Note: This is a sample of my upcoming book Brown Dogs and Barbers. Please be aware that this text is subject to change and that diagrams are only placeholders.

If you'd like to see this book become a fully illustrated and professional book, why not consider donating?]

Computer scientists study the science of computation. Yes, I admit, it seems embarrassingly obvious to say that, after all it’s right there in the name. Nonetheless I promise you I’m not being flippant; it’s a useful thing to say, but it needs some explanation. Ask yourself: what does it mean to compute? In particular, what possible meaning of compute could apply to all the diverse fields of computer science?

Figure 1: What it means to compute
Figure 1: What it means to compute

In its most general form, computation is as simple a concept as that in Figure 1. It involves taking some input data, processing it in some way, and giving the output. Simple as that. It’s like a conveyor belt that carries the raw materials into a machine, whereupon the machine thrashes around doing its magic and eventually pushes the finished product out the other end. As a model of computation it’s widely applicable. From the smallest little operation to the biggest computer task imaginable, computing always involves taking some input, doing some work with it and returning some output.

It describes all sorts of things you do when you use your computer, even the simplest thing like moving the mouse pointer across the screen. During this action, your hand movement is fed via the mouse into your computer as input. The computer must then process it, before outputting the corresponding movement of the mouse pointer on screen. It looks simple and you do it all the time without giving it a thought. But for such a simple action, the computer actually has to do an awful lot of stuff to animate that pointer.

Figure 2: The movement of a mouse pointer
Figure 2: The movement of a mouse pointer

First, let’s talk about the input. When you move the mouse, the distance it has moved is fed into the computer. In this case, there’s actually more than one piece of information involved in the input. Because the computer records the mouse pointer’s position as a pair of coordinates on the screen, the distance is broken down into its horizontal and vertical components. Modern mice sense movement optically, but back in the days when mice had balls — if you’ll pardon the expression — that ball would turn two internal wheels when the mouse was moved: one wheel measured horizontal movement and the other vertical movement. There are therefore two pieces of input to this computation, or — to give them their posh names — two input parameters: distance moved along the horizontal axis and distance moved along the vertical axis.

Next comes the process. In this case, the mouse alerts the computer to a change in its position and passes the parameters along.

“Hey!” says the mouse. “This guy just moved me five millimetres to the right and two millimetres up.”

“OK,” the computer acknowledges, “I’ll get right on it.”

The computer then has to take those physical movements and turn them into on-screen movements via some quick computations. The current position of the mouse pointer on the screen is kept by the computer and continuously updated. Now let’s say that each millimetre of movement corresponds to two pixels distance on screen. In this case, the computer would change the value of the mouse pointer’s screen position, increasing it ten pixels further to the right and four pixels further to the top. Sounds simple enough, but there are a few hidden subtleties in any computer process. If, for example, the user moves the mouse left but the mouse pointer is already at the extreme left of the screen, the computer must not move the pointer any further left. Why, in this case, would the computer essentially ignore the user? Because if the computer didn’t make this check, the x-coordinate would keep decreasing past 0 into negative numbers and cause the mouse pointer to disappear off the left-hand side of the screen! Computations are almost always riddled with hidden traps like these which can cause errors. Sometimes they’re little ones which cause weird side effects, sometimes they’re whoppers which crash a whole system. (Note: Computer bugs are examined in more detail in Part IV: Mastering the Machine.)

After the process has finished comes the output. The updated coordinates are passed to the computer screen, which redraws the whole image showing the new position of the mouse pointer (along with any other parts of the screen which may have changed too). In order to maintain a smooth user experience, the computer will repeat this whole computation about fifty or sixty times every second. The example in Figure 2 shows a mouse pointer on a screen 1024 pixels wide and 768 pixels high. It has moved from coordinates 200 by 100 along the dotted line to 800 by 400. It is thus 600 pixels further to the right and 300 pixels higher than the beginning, but the rapid repetition inbetween presented an apparent smooth motion to the user. During all this, your computer is also working on dozens of other computations simultaneously, most of which are much more complicated than processing your mouse movements. It’s just as well that today’s computers are extremely fast.

This input-process-output model describes how computers execute programs, but it’s just as applicable when people write them too. When coming up with a new program, a computer scientist frames it as a series of instructions which accept input, carry out some processing and return output. This model of computation occurs all over computer science. Every computer scientist is involved in an effort to process information according to this basic form. They are each thinking hard, trying to come up with a series of steps which start with one state and end with another. Each person may be trying to achieve different things, but they all share the same goal of taking input, processing it and giving output.

In doing this, a computer scientist is basically trying to work out how to solve a problem. Her ultimate goal is to enable a computer to actually perform the work rather than a human, which means reforming the eventual solution into a computer program. The study of how best to achieve this is what computer science is all about. This work may involve using a lot of mathematics, but computer science diverges from its mathematical parent in the following way. Mathematicians seek to understand fundamental things like quantities, structures and change, with their goal being to create new proofs and theories about them. Computer scientists take established mathematical ideas and understand how they can best be used to solve problems automatically.

A trivial example might involve calculating square roots. Just in case you’ve forgotten, squaring a number means multiplying it by itself, hence three squared (32) is nine. Reversing this process is called taking the square root, meaning the square root of nine (√9) is three. In this example, our input is nine, the process is the square root operation, and the output is three. Figure 3 illustrates it. This computation takes in just one input parameter and calculates the square root of it, which it spits it out the other end.

Figure 3: Input, processing and output of taking a square root.
Figure 3: Input, processing and output of taking a square root.

A computer scientist’s interest in square roots would lead them to developing a program for computing the square root of any arbitrary number. She would know that mathematics already provides a wonderful range of methods for humans to perform this particular calculation. Her job would be to prepare one of them for automatic execution by a computer. This gives her all sorts of new worries. Working out a square root is a laborious process that can potentially take a long time — that’s why this computer scientist chose to automate it, I suppose. The usual method requires the repetition of the same series of steps, iteratively building up the result until finally the full number is found. But, just like in the mouse example when the possibility of a disappearing mouse pointer cropped up, our computer scientist has to worry about things going wrong when a computer tries to follow her instructions.

Computers — and I want you to remember this — are dumb. They are exceedingly literal-minded things who will do exactly as you tell them, even if what you told them to do was stupid. For example, if we humans begin to work out the square root of two, we will notice after a while as we construct the result (1.4142135623…) that the number never seems to end. That’s because the result is an irrational number and literally does go on forever. Eventually a human would get bored of all this and stop, but computers never tire. If the computer scientist failed to take this eventuality into account, she would end up developing a program that causes a computer to repeat the same steps endlessly when given 2 as a parameter. It would continue until the power were cut off, its circuits rotted away or the universe ended; whichever came first.

To prevent irrational numbers from playing such havoc, our imaginary computer scientist faces a choice. How should the possibility of a never-ending program be dealt with? Should she just impose a maximum size on results, like ten decimal places, and so force the computer to stop calculating upon reaching this limit? This wouldn’t give a strictly accurate answer, and the question still remains how many decimal places is enough. Or should she instead analyse the parameter first to see if it would yield an irrational answer and deal with it differently than usual? Is that preferable? Is it even possible? She also faces a lot of other choices too, such as how to deal with bad input. What should happen if the parameters are negative numbers? What if they’re not numbers at all?

Questions like these, particularly whether a program will actually finish or not, are fundamental concerns of computer science. Those raised here are just a tiny selection of the issues that computer science deals with at its foundation. Many of these issues are actually now well-developed and understood, so that other fields in computer science are able to build on them routinely. But there was a time when there was no foundational knowledge; a time before computer science, when no-one could even conceive of computers, let alone deal with the issues they raise.

The next chapter will take you back to such a place.

Part I. Fundamental Questions

“When all is said and done, the only thing computers can do for us is to manipulate symbols and produce results of such manipulations.”
–Edsger Dijkstra (1930 — 2002)

What is computer science? What does a computer scientist actually do? This is actually a difficult question to answer, but if we hope to learn anything about the subject then I suppose we’d better deal with it.

Looking for the definition of computer science in a dictionary won’t be much help because there are as many different definitions as there are dictionaries. In fact, even computer scientists don’t tend to agree on the definition of their subject, so what chance have the dictionary writers? What’s more, the subject has developed a huge array of sub-fields over the years and at first glance they seem absurdly diverse. For instance, computer vision specialists look at how computers deal with images; network experts concern themselves with how to get computers talking with each other; and information theorists don’t even deal with computers at all, instead spending their time worrying about how to process and quantify information. Given all this, how could I possibly discuss computer science in a way that covers the whole discipline?

But physics also covers a lot of diverse ground, and physicists can collectively claim that they are studying the fundamental nature of matter and how the universe behaves, whether it’s sub-atomic particles or whole families of galaxies. Surely, then, we can also sum up computer science in such a nice, tidy phrase. That’s one thing I’ll do in this first part. I’ll show that there is a way to address computer science collectively, and in so doing I’ll show that all its practitioners share a stock in trade, which is studying how to compute.

Furthermore, no subject is born in a vacuum. Every science we developed branched off from some predecessor, taking a handful of ideas with it along the way and using them to form the core of a new discipline. To demonstrate the kind of concepts essential to the subject, this first part will also explain a few ideas that pre-date computer science but nevertheless lie at its heart.

Chapter 0: Why Do Programmers Start Counting at Zero?

[Note: This is a sample of my upcoming book Brown Dogs and Barbers. Please be aware that this text is subject to change and that diagrams are only placeholders.

If you'd like to see this book become a fully illustrated and professional book, why not consider donating?]

I’d like to begin this book about computer science by asking you about your toaster. If I asked you to tell me how your toaster worked, I bet you’d have no trouble coming up with a decent explanation. Initially, you might claim you have no idea, but I’m sure a moment’s thought would yield a good description. Even in the worst case, you could actually look inside a toaster and deduce what was happening. Perhaps then you’d be able to tell me all about how electricity causes the filaments to heat up and that heat radiates onto the bread or the crumpet or whatever, causing it to cook.

If I were to ask about how a car worked, that might be more challenging. Again, you might instinctively feel that a car’s workings are a mystery to you. But even then, if you stop and think about it, you might recall a few vague terms that help out. Perhaps you could tell me about how petroleum is stored in the car’s tank and when you press the footpedal, the fuel is drawn into the engine where it’s ignited. Then you’d go on and tell me that this action drives the pistons… or something… and they turn the… I think it’s called the crankshaft… which is connected to the wheels and makes them turn. That’s what I would say anyway, and I know virtually nothing about how cars actually work.

I’m guessing all this without even knowing you, your occupation or your interests. True, you might be an engineer or a physicist for all I know, and able to give better explanations, but the chances are that you’re not. My point is, even if you have only the merest passing interest in science and technology, I’m confident that you comprehend things like toasters and cars enough to give half-decent explanations of them. Understanding things like these comes partly from school learning where, even if you sat spaced out during physics lessons, you still picked up some of that stuff about electricity and internal combustion engines. And let’s not underestimate how ingrained on our popular consciousness these concepts are. The people around us talk about the workings of everyday technical items all the time, so some of it is bound to stick with us whether we realise it or not.

But computers are different. Many of us haven’t got the first clue how computers work. Think about it. Could you tell me how the individual components in your computer work together? Could you even name any of the components? I’m certain some of you could, but I’m just as sure that a lot more people couldn’t even begin to explain a computer. To some, it’s a kind of magic box that sits under the desk and somehow draws letters and images on the monitor screen at breathtaking speed.

Let’s get one thing straight: I wouldn’t blame you for being unable to offer an explanation, because there are several reasons why you shouldn’t be expected to know about computers. One very important reason, again, is schooling. In many countries, computer science is not taught as part of general education. In my own country of birth (the United Kingdom), computing education has for many years meant nothing more than learning how to use word processors and spreadsheets; important skills to be sure, but this is definitely not computer science, a topic that studies at a fundamental level how to use mathematical principles in the solving of problems. The great majority of children leave school having learned to be passive users of computers at the most and many people are currently asking why such an important area of knowledge is absent from the curriculum.

The mystery surrounding computers is a problem that’s only becoming worse over time. When computers first arrived they were monstrous things bigger than a family-sized fridge and kept in huge, environmentally-controlled rooms. Their job was usually to carry out boring tasks like process tax returns and payrolls; tasks that anyone could do by hand, albeit a lot slower. They had banks of flickering lights that lit up when the machines were “thinking”; spools of tape mounted on the front spun around, indicating that the computer was looking in its databank; some were even partly mechanical, clicking and tapping uproariously when the numbers were being crunched. Yes, they were still mysterious — but today it’s even worse.

Computers are no longer just mysterious — they’re magical.

Today’s computers are a million light years ahead of their early ancestors. Nowadays they’re small, sometimes able to fit into the palm of your hand. How can something so tiny do such impressive things? They’re also ubiquitous, having gone far beyond their original, humble number-crunching duties until they organise every aspect of our lives. As a result they’ve become utterly unknowable. Today’s computer is an impersonal black box that gives no hint as to its workings. Of course, there’s a user interface that allows us mere humans to operate the computer, but one main purpose of a modern user interface is actually to hide the internal workings of the machine as much as possible. There are few external indicators about what’s really happening inside. Without moving parts (apart from the cooling fan, which I assure you performs no calculations) and with internal components that give no visible clue as to what they’re doing, it’s become impossible to try and deduce how a computer works by examining it. So advanced and unknowable have computers become, they may as well operate on principles of magic.

But there are genuinely knowable principles upon which computers operate. We find things that pump, rotate or burn easier to understand, because physical principles are more intuitive to us. In contrast, the driving principles behind computers are mathematical and thinking in these terms comes harder to humans. There are some physical principles involved, of course. Your computer contains various things —
circuit-boards, wires and chips — which all function according to good old-fashioned physics. But (and I don’t mean this to sound dismissive), those are merely the computer’s hardware. In computer science, there is a sharp and critical distinction between the physical machinery that performs the work (the hardware) and the mathematical principles which allow it to do anything meaningful. These principles make up the field of computer science. In theory, you can build computers out of all sorts of weird and wonderful parts, be they mechanical, electronic, or even water-powered. Yet, however a computer is implemented, it must work according to the principles of computer science in the same way that every car’s internal combustion engine, as varied as they are, all work according to the relevant laws of physics.

Hardware gets mixed up with the field of computer science. I’m pretty laid back about that, but some purists like to emphasise the strict division between the machinery and the principles. Roughly speaking, this corresponds to a separation between hardware and software. Software, a word I’m sure you’ve heard before, is the collection of programs which computers run and the concept of a program goes to the heart of computer science. Unfortunately, programs are a little hard to define, but rest assured that you’ll come to understand what a program is over the course of this book. What makes them tough to penetrate is that they’re nebulous, abstract things rooted in mathematics, a subject that’s a sort of parent to computer science. Programs have numerous legacies through this inheritance. Like mathematics, programs don’t really exist in a physical sense. They’re conceptual things, ideas that exist in programmers’ minds which are only given substance after they’re written down.

This inheritance from mathematics explains many things. It explains why programs look like jumbles of mathematical formulae. It explains why computer science attracts so many nerdy folks who are good with numbers. And it explains why programmers count up from 0 instead of 1 like the rest of the human race. Maybe you’ve noticed that? You might look through some of the programs on your computer and find a new one labelled version 1.0 . Why 1.0 ?

OK, you might say, after a program is updated the author appends a number to the version to make it clear. After the initial version is updated several times we progress through versions like 1.4 to 1.5 to 1.6 and so on. I get that. But why start at 1.0 ? Why not 1.1 ? And why, when I upgrade to the second version, is that called version 1.1 ?

You’d also find this peculiarity were you to read through the contents of a computer program. If you watch a race on TV, then at the end you’d say that the winner came in position 1, the runner-up in position 2 and so on. If you ask a programmer to write a program for processing the race, the results would begin with the winner assigned position 0 instead and the runner-up in position 1. To a programmer, the hero is a zero.

Counting up from zero, which instinctively seems unnatural, actually simplifies matters when you deal with lists of things. In these cases, counting up from 1 can cause confusion. For instance, have you ever stopped to think why the years of the twentieth century all began with 19 and not 20 ? It’s something that often trips up little kids (and occasionally big ones too). Why was the year 1066 part of the eleventh century and not the tenth?

Figure 1: Two buildings with different floor numbering schemes.
Figure 1: Two buildings with different floor numbering schemes.

To explain, let’s look at an example of counting up from 0, because we all do that occasionally whether we realise it or not. In some parts of the world, the bottom floor of a building is called the ground floor and the next one up is the first floor. In this case, the ground floor could just as easily be called the zeroth floor. Similarly, when programmers refer to specific items in a list (which they do a heck of a lot), they often need to calculate the position of an item in that list by offsetting it from a base position. This base item is labelled number 0. Working out a position when a list is arranged like the floors in a building makes things a little simpler. Floor 3 (or the third item) is three above the ground floor (or zeroth item). If the ground floor were floor 1, then the third floor would be two above the ground floor. This is visualised in Figure 1. We count centuries similarly to the left-hand building. Because we count centuries up from the one (the years 1 to 100 were the first century, not the zeroth century), we then have to remember that centuries don’t match with the years within them. It’s only a small confusion, but working out positions in a list is done so often that little hiccups like this can actually cause more problems than you think.

With this explanation, you’ve hopefully just learned something new about computer science. I know it’s only trivial, but nevertheless it shows you something about the subject and explains why that something is the way it is. This example is just the tip of the iceberg, so there’s much more complex and interesting stuff still to come. Computers are complex things, more so than any other machine we’re likely to use on a daily basis. Unfortunately, they remain mysterious to many people. For many of us, our relationship with computers is one of bemusement, frustration, and fascination, all experienced at arm’s length. We sometimes even find ourselves as the servile member in the relationship, desperately reacting to the unfathomable whims of our computer trying to make it happy. This is not the best state of affairs to be in if we’re going to be so reliant on them in our everyday lives. It doesn’t have to be this way. If our relationship with computers is sullied by their mysteriousness, the answer is simple: learn more about them. And I don’t mean learn how to make spreadsheets.

To understand what’s going on in that magic box beneath your desk, we’ll look in this book at the science behind it.

This book presents you with the core ideas of computer science. By reading them you will learn about the subject’s history, its fundamentals and a few things about its most pertinent protagonists. Understanding them will help to demystify the machine. Each chapter can be read as a self-contained unit, but nevertheless, they have all been written together in a way that reading from start to finish is like a story. They vaguely follow a chronology and each chapter builds gently on preceding ones. It’s your choice.

However you choose to read it, this book will take you from the earliest beginnings of mechanical computation and show you how we arrived at today’s world of the magical and ubiquitous electronic computer. You will learn of the monumental problems that faced computer scientists at every stage. You will see how they developed ingenious solutions which allowed the field to progress. And you will observe how progress leads to both new opportunities and new problems.