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.


Post a Comment

<< Home