Monday, March 27, 2006

C rots the brain

It's high time for a good rant. I'll warm up by quoting Cassandra:
I'm sorry to be politically incorrect, but for the ACM to then laud "C" and
its inventors as a major advance in computer science has to rank right up
there with Chamberlain's appeasement of Hitler.
One of our nastiest inheritances from C is a set of ingrained assumptions about the implementation of the control of any programming language.

Consider the pure lambda calculus. Application of a β-redex completely replaces the application node with the body of the function being applied. That is, there is never any space consumed in the representation of control for a procedure application. Rather, it is when one of these applications occurs in the context of some other computation that the program's control consumes space. To quote Guy Steele:
Intuitively, function calls do not "push control stack"; instead, it is argument evaluation which pushes control stack.
A continuation frame represents a kind of to-do list of what the program has left to do. It only needs to save this information in memory somewhere if it's going to do something else first, i.e., call another procedure.

The pernicious legacy of C is that we assume entry to a procedure body must always create a stack frame. But what is this frame for? It keeps a finger on our current point in the program, i.e., the program counter, and perhaps it stores some local data that we'll need in order to complete the evaluation of the function. If the procedure happens to be a leaf procedure, i.e., does not make any function calls, there's no need to save the current position, since we're not going anywhere else. Or maybe the procedure only conditionally calls another procedure. In that case, we might not need a continuation frame until we jump to the particular branch that is guaranteed to make the procedure call.

The assumption that procedure calls must push stack is so built-in to my head that I constantly have to remind myself: procedure entry and continuation frame allocation are not necessarily correlated!

But now the true folly is in the representation of the continuation as a simple stack. Gone are the days where we were told "if you want a string, just allocate a fixed buffer that's really, really big and hope you never need any more than that." (Well, gone should be the days.) Why then do we only get a fixed buffer size for the single most important part of every single program, the program's control itself? It's absurd to have your program tell you, "other than, like, those couple of gigabytes sitting over there, I'm totally out of space."

Why do these silly limitations persist? Because C rots the brain.

Update: Sam doesn't think it's fair for me to blame C. I guess C has been the drug that led to my personal brain damage, but it's perfectly possible for programmers of older generations to have been addled by Algol or Fortran, or newer generations by Java or C#. There's plenty of blame to go around...

3 comments:

Sam Tobin-Hochstadt said...

I think this is grossly unfair to C. C isn't responsible for stack allocation of continuation frames, or for lack of proper tail calls. It just brought along the assembly language traditions, which wrote code the same way. I don't think we can blame Kernighan and Ritchie for not anticipating Guy's insight (which was written *after* C).

Stevie said...

While it may be unfair to blame C for this, I can't help but rage against this and other aspects of it daily now that it's an integral part of what I'm doing. At least it makes sure that I won't want to do this for any longer than I need to at this point, and then I can get back to doing what I should be.

Cale Gibbard said...

We can to some extent blame the popularity of C though. Perhaps when K&R wrote their book, they didn't know any better, but things have happened since then. However, C's popularity initially (and even today it's more popular than it probably deserves to be), has helped people to ignore the languages which would have broadened the ways they think about programming. People moved to new languages that were not very different from C. About the largest change for the popular languages has been the move to OOP, which is a decent collection of abstractions, but imperative OO languages still allow people to ignore different ideas about evaluation, or control over side effects. Also, the more popular OO languages have been the ones which were actually less object oriented, allowing people to fall back into that imperative comfort-zone and not really think much about whether there's a better way to use the abstractions that are available.