Monday, December 20, 2004

The stack

Noam Chomsky, talking about the social responsibility of the intellectual, said that most facts about US foreign policy are, even when in official records, not open for discussion with scholars, for example, in political science.

By contrast, he mentions some papers that he presented to computer people in the late 1950's. He wasn't in their field at all. But they listened to his findings, analyzed them, and used what they could.

Well, these findings revolutionized the creation of computer languages. Chomsky's most influential result was the one-to-one mapping between the capabilities of pushdown automata, what we call a "stack", and languages describable by context-free grammar productions. He also noted that finite state machines mapped to regular expressions.

Within twenty years, all significant computer languages, and much data processing, were implemented using these tools. Human-readable computer languages were recognized by stack-based parsers, generated automatically from descriptions shaped by context-free productions. The compilers were, and still are, functionally compartmentalized into the regular-expression and grammar components.

The effect this had on language design & development is incalculable. At the very least, it leads to compiler-compilers such as Lex & Yacc, developed with Unix at Bell labs, along with the movement towards software tools, and the endless applications and extensions of regular expressions. At most, one might say that it crystalized context-switching, the basis for all multi-process computing, bringing on the heyday of the stack, whose use was now easily defined due to Chomsky's work.

Note that this is the way it appears to me, having entered the field in 1974. I'll amend this speculation, as people who were there provide me with more material.

The Approach

Exhaustive listing of the influences of two influential people would be incredibly boring, for you and for me. And I simply don't want to ask anyone "how have you been effected by Noam Chomsky or Christopher Alexander?" Nonetheless, when I come across a good story, of course I'll tell it.

Chomsky & Alexander

The computer was the invention of curious people. Not computer scientists.

It's your choice where to start the history of computing. Use any point along the evolution of counting or mathematics. Or start with Euclid's logic or Blaise Pascal's calculator. You can begin with Descartes methodology or Charles Babbages' difference engine or Alan Turing's models of computation.

But note: these weren't "computer people". They were just people.

Fast forward, past the explosion of business & government use of systems of advanced calculation, past philosophical & practical contributions from the generation of Norbert Weiner & John von Neumann. There are now millions of contributors to computing, who are computing people.

But there are two very odd professors who are not. They are not particularly interested in computers. But their profound influence on computing is an amazing story.