The X=X+1 Issue

Like many people my age, my first programming experience was with the BASIC language. I recall using an ASR 33 telprinter to create/edit/run BASIC programs. I would marvel at how the cylindrical print head would dance and bang across the paper printing error messages from my ten line programs. Of course, at 300 BAUD you had plenty of time to watch things happen. Back in the day, BASIC was usually the first computer language you would learn. There were other more “advanced” languages like FORTRAN or COBOL that were deemed too difficult for the novice. By the way we capitalized Fortran back then.

I was a senior in high school at the time and had the requisite college prep math (algebra, trigonometry, geometry). I was interested in learning about how computers worked and took the BASIC programming course. (Actually, I wanted to build my own HAL 2000, but that is another story.) In any case, the teacher started talking about variables and writing things like:

Let X = 1

on the blackboard. Then something new was presented. Something weird like:

Let X = X + 1

Wait a minute, I thought, if X=1 then how can X = X + 1 or 1 = 1 + 1. That whole idea was counter to what I was just taught in algebra. I don’t think I was the only one confused. The teacher preceded to explain why you can do this with a computer. The word variable means it can be assigned at any time to anything on the right hand side of the equal sign — including itself.

The ability to assign a memory location with variable data is the cornerstone of computer programming. It turns out the ability to re-assign that same memory location is perhaps one of the biggest consternations in the parallel programming world. At the time, multiple assignment seemed like (and was) a good idea. Coupled with a looping control structure, massive calculations could be performed. For instance, one could write a program to sum the numbers from 1 to 100 (and beyond with simple variable change):

Let SUM = 0
FOR I = 1 to 100
 LET SUM = SUM + I
NEXT

While incredibly useful, multiple assignment creates “state” within the program because the value of variables can change as program runs. The typical programming language allows you to manage the state of program variables. i.e. the memory location that holds the variable SUM changes over time. As any programmer will tell you, program state is easily managed on a single Von Neuwman CPU through the plethora of programming languages. (Some may argue this point, however.) On a large number of CPUs, managing coupled program states becomes extremely difficult. In a parallel environment, it is up to the programmer to manage the state of I and SUM. In a sequential single CPU environment, the programmer can assume I = 100 after the loop completes. In a parallel environment, where the loop may have been broken into parts, I may equal 10 on one CPU, and 20 on another. Of course, the example is simple and obvious. Creating large complex parallel applications does not present such luxuries, however.

This type of “state management” programming has been very successful and is often called “procedural” or imperative programming. The programmer provide statements (the procedure) that change the program state. Adapting procedural programs to parallel environments can range from easy to difficult. Given a typical sequential C program with data structures and pointers, how easy do you think it would be to manage the program state across 16 cores? Could you be sure that those indirect pointers are pointing to the correct data at all times? And, what if there is serialized loop dependency that requires synchronization across all cores?

The simple powerful idea of multiple assignment has come back to bite us in the asymptote. Who could have guessed. Some people not only guessed, but they did not like the whole multiple assignment thing in the first place. What if, they suggested, we only allow single assignment of variables like we do in algebra. Can we do computing in this fashion and avoid managing programming state? Their answer takes the form of declarative programming. Instead of describing “how” (managing state) the programmer specifies “what” the program must do. By moving to the “what”, the programmer relinquishes state management duties. Research and case studies have shown declarative programming is more efficient than procedural programming. In general, declarative programming requires less lines of code (and therefore less opportunity for bugs) and higher programmer efficiency. Even with these impressive results, the majority of the programming community has continued to use X, where X is a single assignment of your favorite procedural language (C, C++, Perl, Python, Java, Fortran, etc.) For many, the legacy cost to move away from the established methods is considered too high to facilitate any kind of switch. It has long been my belief, however, that parallel (i.e. Multi-core) software development costs may require reevaluation of this conclusion.

Declarative languages fall into three basic categories, functional, logic, and constraint. I’ll talk about the differences in the next column, but each of these only allow single assignment to variables. This concept is perhaps the most difficult to grasp because it does not allow looping control structures, which is actually good because loops are the “how” stuff from which we want to move away. So the “how” does one “do a loop” with single assignment. The answer, is recursion, but not procedural recursion. Let’s think about “what” we want to do first, then we will worry about the “how” part. When we add the numbers from 1 to 100 we can start at 100 and we know our answer is 100 plus the sum of 1 to 99. Continuing we know that the sum of 1 to 99 is 99 plus the sum of 1 to 98, and so on. When we reach the number 1, we are done and the sum of number 1 to 1 is 1. I have represented these facts in pseudo code rules to help the procedural side of your brain.

SUM(1) THEN RETURN 1
SUM(I) THEN NEW_I = I - 1; RETURN {I + SUM(NEW_I)}

If I ask for SUM(100), then the rules I have proposed will recursively find the total. How do I represent these rules into a declarative language? I just did. The pseudo-code rules are essentially a declarative program. Each recursive loop assigns NEW_I only once. Note, each new invocations of the rule uses new variables, even though they have the same name. Something else, to notice, there are two definitions of the SUM function. The first only works when the argument it is 1. The second works for everything else. And, notice my rules tell the computer “what” to do, not “how” to do it.

The procedural programmer in you is probably jumping up and down screaming “recursion is inefficient, looping is better, you are going to run out of memory.” Take a breath code boy it will be alright. Recall, I said we are not going to worry about the “how” just the “what.” We have described “what” we want with recursive rules, how the rules are executed is up the declarative language. In reality, any good declarative language recognizes recursive rules and executes efficiently as though it were actually a loop, but then we don’t worry about the “how.” Think about this example for a minute. It is concise, clean, and more like the algebra we learned many years ago. Most importantly it is “closer” to our problem.

We’ll let that percolate for this week. The take-way for this week is multiple assignment is bad for parallel, single assignment is good for parallel. Well see how this works out in upcoming columns. And you thought BASIC was the bomb.