Part of a series of posts explaining programming for the lay-person.
This is part of a series of posts; see the introduction to this series.
Computer science theorists like to identify what they call “Turing Complete” sets of operations, meaning that with these operations (and a bit of ingenuity) you can create any program that can exist. The exclusive-or operator ⊕ and the constant 0 from Boolean algebra is one such set; another is lambda symbol λ and variables. These are not random examples Random examples would be TeX or Wolframs’s (2, 5) Turing machine but indicators of the two main fields of thought in computer science today. The ⊕ people love state, the λ people hate it.
State is what a program or part thereof “remembers”. It is contrasted with the purely functional or stateless. The square root function is stateless: it doesn’t remember anything from one invocation to the next. A counter is stateful: each time I invoke “count” I get back one more than I got the last time.
You never really need state. That is, you can always make the state of a procedure into another (set of) input(s). Thus the purely functional version of “count” is “+ 1”. State just makes things easier to describe. Using state, a chess program might look like “move white” while without it it would be “move white given the back king is on A7 and the black queen is on…”
State becomes horribly messy when you have multiple processors trying to do things at the same time. Consider a simple counter procedure that says “to count: (1) compute 1 + the state; (2) update the state to that value.” Let’s say two people, A amd B, both try to count once. If A gets to step (2) before B gets to step (1), the state goes up twice. But if both A and B do step (1) before either does step (2), the state only goes up once. This kind of behavior, called a race condition, becomes more problematic as the state becomes more complicated.
Race conditions appear in daily life, too. I used to have several roommates who all ran the procedure “when the dish soap is low, buy dish soap” and in a single day they’d each come home with a bottle of dish soap. More common is the “if on a collision course, get out of the way” back-and-forth dance in which people often engage.
It’s worth pointing out that, without state, you can’t have race conditions. There is no possible way for two square root computations to mess with one another. The problem is you also can’t have sharing.
There are two main ways around race conditions. Neither locks nor transactions are particularly simple to implement, but they are important enough most computers have them anyway. The first is to lock out other processors for a while. If, when I notice the soap is low, I remove the soap from view or remove my roommates’ keys until I purchase more soap, then my roommates are locked out of messing with the soap. The other is to proceed without a lock but after the fact make sure the outcome was what I wanted and, if not, to roll back the transaction. That is, before I add the soap to the kitchen I make sure the soap is still low; if it isn’t, I return the soap I bought to the store.
Transactions can lead to what’s called “live lock”. Two roommates bring home soap at the same time, see that the other brought home soap too, return their soap to the store, see that they’re low on soap, buy soap, bring home soap at the same time, and on and on forever. The simplest workaround here is to randomize things a bit so that this kind of extended synchronization becomes very unlikely.
Locks can lead to the more pernicious deadlock. Suppose both you and I need both the car and the phone to get our tasks done. You grab the phone, I grab the car, and then we both wait for the other one to become available before continuing with our tasks. We are deadlocked, waiting for the other person to act first. Workarounds for deadlock usually involve adding more locks or rules about the order each lock is acquired and released.
Concerns about parallelism, state, locks, race conditions, and transactions are matters of active research in computer science and software engineering today. They’re also increasingly common and important as computer hardware continues to multiply processor cores. Handling large groups of people has never been easy; when they are all dumbly obedient chips with no intuition, it gets even harder.
Looking for comments…