Essay #3: Programming - nuwen.net

"This is the Information Age not only because data processing is so common but because it is increasingly possible to cast all problems as matters of data manipulation - to see the world as a frenzy of bits waiting to be tamed" - John Rennie, Editor in Chief, Scientific American Special Issue: The Solid-State Century

The real problem with the Information Age is not computers, but humans. Computing has entered the scale of billions: a personal computer can do billions of operations per second, can store billions of characters, and can transmit billions of bits per second - well, we're not quite to the point where everyone has Gigabit Ethernet, but we'll get there. In contrast, humans work at the scale of single digits. We can do perhaps one thing per second, we can store about seven different things at a time in our short-term working memory, we can read perhaps nine words a second, and we can write one word a second. Our minds are powerful, but they are slow. We did not evolve to compute - it is merely an interesting thing that we can train ourselves to do with great difficulty. Computers are very dumb. Most of the interesting tasks a 5 year old child can do (e.g. recognizing faces, reading text, and walking through a house without bumping into too many things) a computer finds exceedingly difficult or impossible. (The term for such interesting tasks is "AI-Complete".) Yet computers are also exceedingly fast. This poses significant problems when the computer must communicate to a human. We have invented a simple language of icons, menus, dialog boxes, and windows by which computers communicate things to us, and most of the time we can understand what the infernal machine is doing. Using keyboards with a hundred keys and mice with five buttons (and a scroll wheel!), we can instruct the computer to do simple tasks, and most of the time things go smoothly. This is not as efficient as speaking to another human, asking questions and giving commands, being told things and being shown things, but it works, and well. Yet we still must instruct computers precisely what to do, and this is the job that falls to the thankless computer programmer.

"Real Programmers aren't afraid to use GOTOs. Real Programmers can write five page long DO loops without getting confused. Real Programmers like Arithmetic IF statements - they make the code more interesting. Real Programmers write self-modifying code, especially if they can save 20 nanoseconds in the middle of a tight loop. Real Programmers don't need comments - the code is obvious" - Ed Post, "Real Programmers Don't Use Pascal", a letter to the editor of Datamation, vol. 29, #7, July 1983

Computer languages - at first assembly, then FORTRAN, and other languages shrouded in the mists of time - started off "close to the machine". They provided minimal insulation from actual machine code, which computers speak fluently but which remains gibberish to (sane) humans. As time progressed, machines became more powerful. The entire history of the Information Age thus far is incomprehensible without understanding the background that it is set against: the relentless, exponential march of Moore's Law. Things which were expensive a decade ago are cheap today, in all senses of the word: economic, time, and space.

"Programmer time is expensive; conserve it in preference to machine time" - Eric S. Raymond, The Art of Unix Programming

Computer languages arose to serve computers, but now they must serve us. Source code is intended for humans to read, not computers. In the decades since the invention of the transistor and its progeny - the integrated circuit, the microprocessor - we have learned that power corrupts, and absolute power is kind of fun, but corrupts absolutely all the same. A programmer has access to the nearly limitless resources of the machine - billions of operations per second, billions of bytes of storage - and if he is not careful, he will drown in complexity. Complexity is the bane of programming. A computer will happily compile megabytes of source code, but woe to the programmer who must understand the workings of such an amount of machinery. During the rise of the computer, many lessons have been learned. Most of them have the same moral: reduce complexity, or else. These lessons are usually taught by explaining that something is "evil". X is evil, so don't do X. Programmers are by nature very intelligent and individualistic people - when given a challenge, they rarely back down. To some, being told that X will produce incredibly complicated and impossible to understand programs isn't a deterrent, it is a challenge. These people are wrong. Things are said to be evil for a reason, and anything which increases complexity usually leads to problems down the road. Good programmers remember what things are evil and what things are good - sometimes after being told, most of the time after being burned - and they follow what seem to be arbitrary rules with a religious fervor. This is a Good Thing.

"A software system is transparent when you can look at it and immediately see what is going on. It is simple when what is going on is uncomplicated enough for a human brain to reason about all the potential cases without strain" - Eric S. Raymond, The Art of Unix Programming

One of the first lessons to be learned by the collective world of computer programmers was summed up by Edsger W. Dijkstra's 1968 article, "Goto Statement Considered Harmful". The GOTO statement, found in languages like BASIC, causes the machine to jump somewhere else in the source code and begin executing statements there. It was eventually realized that this led to "spaghetti code", where control flow jumps between widely separated parts of the problem. The problem with GOTO is that it causes incredible complexity, and code rich in GOTOs is nearly impossible to understand. It is fairly easy to understand what happens when a GOTO statement is encountered. But what about the reverse? At any given point in the code, some other part of the code could be jumping right there. A program has a "state", which is the collective status of files, variables, memory, and other resources, and GOTO makes it incredibly difficult to understand what the state of a program is at any given point. Using GOTO is evil, and thanks to this realization, GOTO is rarely if ever used. Programs can work perfectly fine without it, given the existence of other instructions. "Structured programming", as seen in C, is clearly superior to the "unstructured programming" of BASIC. C programming centers around for() and while() loops, along with switch() statements and some other friends. It is much easier to understand what a program does if it is well structured.

"Cleverness is evil; use it only when necessary" - Marshall Cline, Greg Lomow, and Mike Girou, C++ FAQs, Second Edition

Furthermore, there is the problem of "global variables". These are variables which can be seen throughout the entire program - any piece of code anywhere can read and write such variables. This opens up a problem - what state are the global variables in? It depends what other parts of the program have done to them. Since there is no way to determine by glancing at the code which parts touch which global variables and when, it is very difficult to understand the state of a program at any given time. Global variables are almost as bad as GOTO. Thus, they have been shunned in structured programming, and again, for good reason. Global variables are evil. Programs can always be written without them.

"I decided to use a dialect of Lisp called Scheme to build such a toolbox [of graph algorithms].... I realized during this activity that side effects are important, because you cannot really do graph operations without side effects. You cannot replicate a graph every time you want to modify a vertex. Therefore, the insight at that time was that you can combine high order techniques when building generic algorithms with disciplined use of side effects. Side effects are not necessarily bad; they are bad only when they are misused" - Alexander Stepanov, March 1995 interview, Dr. Dobb's Journal

Structured programming was not the last word in complexity management. There is still the problem of variables. Variables, even local ones, still have state. And while the amount of code which can affect local variables is much reduced, it is still significant. Languages arose that essentially banned local variables. Setting a variable to some value, termed "assignment", was classified as a "side effect". Structured programming took the idea of functions, chunks of code which do something and then return data, and made it into the unit around which programs were to be broken up. If a function does its job well, then it can be viewed as a black box. The programmer can look inside the box and determine that everything is working properly. Then he can close the box and be ignorant of what goes on inside - he need only remember that the box squares numbers, or something. In computer science, ignorance is a good thing. When you can be ignorant of something, that means there's less complexity for your mind to stumble over. However, functions can still have side effects, things they do other than returning a value. They may allocate a chunk of memory, and forget to give it up when they're done. Functions which return nothing aren't really functions at all - they're "procedures". The languages which arose as a reaction to side effects followed the "functional programming" philosophy. In functional programming, functions are not just the main tools by which programs are properly structured into black boxes, they are the ONLY tools. Functions cannot have side effects. In this manner, complexity is further reduced. You need not worry about the abstract state of a program because there really is no abstract state - just data being passed around between functions.

"Narrowness of experience leads to narrowness of imagination" - Rob Pike, "Systems Software Research Is Irrelevant"

Functional programming (e.g. LISP and its dialect Scheme), touted as being infinitely superior to the unwashed structured programming languages (e.g. C), has fallen by the wayside. Side effects, it turns out, are just a bit too useful to give up. They offer more power than danger, at least when used carefully. This is what Alex Stepanov is talking about. Yet the reaction against functional programming has been too strong. Functional languages are rarely used in industry; they are taught at a few universities, but that's it. They should be given more attention than they currently get. While functional languages are too constricted to get any real work done easily, exposure to them is important. They teach a way of thinking which can be usefully applied to other languages. After all, the functional philosophy is about giving up power (side effects) in the name of safety (not having the state of the program trashed by another part of the program). Once a programmer understands the functional philosophy, the dangers of side effects are never forgotten. Then the philosophy can be applied even to non-functional languages like C, simply by being very careful about the use of side effects, always making sure to use them properly.

"Let's consider now why C is a great language. It is commonly believed that C is a hack which was successful because Unix was written in it. I disagree.... C, reflecting the genius of Dennis Ritchie, provided a minimal model of the computer that had evolved over 30 years. C was not a quick hack. As computers evolved to handle all kinds of problems, C, being the minimal model of such a computer, became a very powerful language to solve all kinds of problems in different domains very effectively. This is the secret of C's portability: it is the best representation of an abstract computer that we have. Of course, the abstraction is done over the set of real computers, not some imaginary computational devices. Moreover, people could understand the machine model behind C. It is much easier for an average engineer to understand the machine model behind C than the machine model behind Ada or even Scheme. C succeeded because it was doing the right thing" - Alexander Stepanov, March 1995 interview, Dr. Dobb's Journal

C is a great language, but even it has problems. C is a very small language. C has few concepts and few structures, though the ones it does have are very important. From C rose the very large language C++, which has a great deal of concepts and structures. C++ is an "object-oriented" language. It takes structured programming one step further. In C, there are fundamental data types - integers, floating-point numbers, and pointers. These fundamental data types can be grouped together into "structs", which are buckets of bits. A date struct might contain three integers, for day, month, and year. The fundamental data types and the user-defined structs are then operated on by algorithms, in the form of functions. Object-oriented programming combines data and algorithms. Instead of having buckets of bits lying around, with tools scattered that work on the buckets, the two are synthesized into black boxes called objects. An object has both state (data) and behavior (algorithms). In structured programming, there may be a date struct lying around and an algorithm which, given a date, will find when the next total solar eclipse will occur. In object-oriented programming, the date becomes an object, a black box, with a button labeled "find when the next total solar eclipse will occur". It seems trivial to package data with the algorithms which operate on it, but it is in fact very important. Objects form ideal black boxes, as black boxes must have both state and behavior. Decomposing a program into objects, rather than functions, makes things clearer and reduces complexity. Object-oriented programming is really data-oriented programming - it makes data structures all-important, and puts algorithms in a less exalted position.

"I spent several months programming in Java. Contrary to its author's prediction, it did not grow on me. I did not find any new insights - for the first time in my life programming in a new language did not bring me new insights. It keeps all the stuff that I never use in C++ - inheritance, virtuals - OO gook - and removes the stuff that I find useful. It might be successful... but it has no intellectual value whatsoever" - Alexander Stepanov

After C++ came Java. Java introduces nothing new, as Stepanov explains. It only takes away. Unlike functional programming languages, which take away side effects and force programmers to look at problems in a new light, Java takes away power and gives nothing in return. It may reduce danger, by having no explicit pointers and no explicit memory allocation, but it increases complexity, and this is evil. In the rush to be "purely object-oriented", Java has doomed itself to uselessness. Along with C, C++ is the language which the world speaks, and will speak for decades to come. C++ is a multiparadigm programming language, and is superior to monoparadigm programming languages - which include nearly everything else (LISP, Java, and so forth; C comes close to being multiparadigm, since you can even code in an object-oriented manner in C, but it lacks enough support in the language to make this a reality). C++ is object-oriented, but it is more than that. It has three strengths. The first strength is its inheritance of C's machine model. That C++ looks like C with respect to syntax is merely a side effect. The second strength is being object-oriented. This is Java's only strength, as Java lacks C's machine model even though its syntax looks like C's syntax. You can tell, since Java lacks pointers, and pointers - love them or hate them - are the lifeblood of C. Being object-oriented is only one of C++'s three strengths. The third is genericity. With C++'s templates, abstract containers and algorithms can be developed which don't care what they hold or what they operate on. These strengths are why C++ has become so extraordinarily successful in industry - it is the best way yet devised for programmers to conquer complexity. There are other benefits of C++ - operator overloading is a useful way to make it easier to see what objects are doing at a glance, and it's also horrible that Java has removed operator overloading - but they are not as central as the three pillars upon which C++ rests.

"The only way to write complex software that won't fall on its face is to hold its global complexity down - to build it out of simple pieces connected by well-defined interfaces, so that most problems are local and you can have some hope of fixing or optimizing a part without breaking the whole" - Eric S. Raymond, The Art of Unix Programming

C++ is a multiparadigm language because it does not artificially constrict the programmer into doing things in only one way. You can write bad, unstructured, code in C++, though you shouldn't. You can write procedural or structured code, in the manner of C, if that is necessary (and sometimes, it is). You can write object-oriented code. You can write generic code. You can even use C++ as a nearly functional programming language - it supports recursive functions (just like C does), though this is a nontraditional use of C++. You can combine paradigms: writing generic object-oriented code, for instance. In this manner, the language molds itself to the task at hand. C++ is a good thing, and with it we can tame the frenzy of bits that is the world.

A Perspective From The Top Down

What is a better approach when learning a programming language and when writing programs? Top down, first viewing a system from its most abstract parts and then understanding the internals only when necessary? Or bottom up, first viewing a system from its fundamental building blocks and then grouping them together into abstract collections only when necessary?

When you learn to drive, do you learn what a crankshaft is, what all the stages of a four-cycle internal combustion engine are, how catalytic converters reduce pollution, and how airbags sense crashes precisely? No! You learn what the pedals do, what the wheel does, how to shift gears, how to look in your mirrors, and how to refuel your car. You first learn the interface to a car, and become a driver. Later, if you want, you can learn the implementation and become a mechanic. Note that there are very many more drivers than mechanics. This has consequences: the interface is very much more important than the implementation.

Similarly, when learning a programming language, you should not learn how the compiler passes arguments to functions, how virtual functions do their thing, how signed integers are represented by the machine, and how malloc(), free(), new, new[], delete, and delete[] perform their magic. You should learn how to pass arguments to functions, how to write vararg functions, how to use virtual functions, to be aware of implementation-dependent and undefined behavior when working with signed integers, and how to properly allocate and deallocate memory. This is the first step to becoming a programmer. Later, if you want, you can learn the implementation and become a compiler writer or a system designer. Learning the interface before the implementation is vital, because the implementation changes, often without warning, while the interface stays well-traveled and stable. Many people are seriously surprised when they realize that bytes are not necessarily 8 bits! To someone who learns the implementation before the interface, "byte == octet" isn't just an assumption, it's a fundamental belief. When that changes, bad things happen. Granted, octet bytes are probably here to stay, since they're so damned useful. But there are plenty of other assumptions one can make after learning the implementation before the interface, and they are all bad.

Learn systems from the top down. Know how to use them before you learn how to make them. Similarly, design systems top down. Understand what the eventual user will need to do with it (possibly this will be a user-programmer, if you are writing a library), rather than what you will need to do to implement it. If you are writing code that implements a Stack, should your first consideration be to use an array or a linked list, due to possible performance issues? No! Your first consideration should be what the user will see when she uses the Stack. In pseudo-C++, will you want a void push(DataType thing) and a DataType pop(void), or perhaps a void push(DataType thing), DataType read(void) const, and a void pop(void)? What will be the asymptotic time complexity of these operations (if this stack is going to be used, they had better be O(1) - complexity assertions have to be a part of the interface too)? Will the maximum size of the stack be compiletime defined (use arrays), runtime defined (use dynamically allocated memory), or infinite (use linked lists)? Now that you have answered the questions from the user's (possibly user-programmer's) point of view, now you have some idea of what you will have to do to implement the thing.

This is the essence of good programming.

http://nuwen.net/essay3.html
Stephan T. Lavavej
stl@nuwen.net
Updated a long time ago.