Before C, There Were Theorems: Reading Dennis Ritchie's Recovered Harvard Dissertation

Dennis Ritchie is remembered as the author of C and the co-creator of Unix. The theoretical work that preceded both has been inaccessible for decades, sitting quietly in Harvard’s archives while the practical output of that thinking rewrote computing. The Computer History Museum digitized his 1968 dissertation and made it publicly available, and reading it alongside C’s design reveals a continuity of thought that is easy to miss when you only know the practical side of the story.

Ritchie completed his undergraduate degree in physics at Harvard in 1963, then stayed for a doctorate in applied mathematics. His dissertation, submitted around 1968 under the supervision of Patrick C. Fischer, sits at the intersection of formal language theory and early computational complexity. The topic is hierarchical programs and what sets of values they can define. That framing, what a program of a given structural form can and cannot compute, turns out to be exactly the kind of question that shapes how a language designer thinks about control flow and data layout.

What the Dissertation Is Actually About

The core subject is a specific class of programs where the subroutine calling graph forms a strict hierarchy: subroutine A can call B, and B can call C, but no subroutine at a lower level can call back up the chain. This is not the same as recursion, which allows a function to call itself or call something that eventually calls it back. Hierarchical programs in Ritchie’s sense form a DAG (directed acyclic graph) of calls, not a cycle.

The question the dissertation asks is: which sets of values, strings, or sequences are definable by programs with this structural restriction? The term “definable” comes from logic and recursion theory. A set is definable relative to some formal system if membership in that set can be characterized by an expression in that system. For programs, it means: given a hierarchical program, what is the set of inputs on which it terminates with a “yes” output, and can we characterize that set in a clean mathematical way?

This connects directly to the Chomsky hierarchy, the sequence of grammar classes (regular, context-free, context-sensitive, recursively enumerable) that had been worked out through the 1950s and 60s. Each class corresponds to a class of automata with specific resource constraints. Ritchie’s work on hierarchical programs is exploring a similar idea from the program structure side rather than the automata side: restrict the structure of the computation, and you get a restricted class of recognizable sets.

The Böhm-Jacopini theorem, published in 1966, had just demonstrated that any flowchart program can be rewritten using only sequence, selection (if-then-else), and iteration (while loops), without goto. This was theoretical ammunition for the structured programming movement that Dijkstra was about to make famous with his 1968 letter to the ACM. Ritchie’s dissertation is working in the same intellectual territory, asking what structural properties of programs determine their computational character.

The 1968 Intellectual Climate

It helps to understand how unusual formal program analysis was as a research topic in 1968. FORTRAN had existed for eleven years. COBOL was nine years old. The notion that a program, as distinct from a mathematical function or an automaton, could be the primary object of formal study was still relatively new. Floyd’s 1967 paper on assigning meanings to programs laid foundational groundwork for what would become Hoare logic. The Algol 60 report had introduced the idea of block structure and lexical scoping, which gave programs a hierarchical organization at the syntax level.

Ritchie’s dissertation is part of this broader effort to understand program structure mathematically, before moving to Bell Labs and beginning the practical work of building systems. The theoretical training shows up in unexpected places in C’s design.

Where the Theory Shows Up in C

C is not a hierarchical language in Ritchie’s formal sense. It has goto, which can jump to any labeled statement in the same function. It has setjmp and longjmp, which can transfer control across function call boundaries, breaking the stack discipline entirely. These are deliberate design choices, and they are the kind of choices you make when you understand precisely what you are giving up and what you are gaining.

The flat address space of C, the ability to cast any pointer to any other type, the explicit control over memory layout: these are features that a pure hierarchical model would forbid. Ritchie knew what computational properties the restrictions bought, and he chose not to impose them on a systems programming language that needed to address hardware directly.

What survived the transition from theory to practice is the hierarchical data model. C structs compose strictly: a struct can contain fields of other struct types, but there is no mutual recursion in type definitions without the explicit use of pointers. You can have a struct node that contains a struct node *next pointer, but you cannot have a struct that directly contains an instance of itself. The structural organization Ritchie studied formally in 1968 reappears as a constraint on data layout in 1972.

The same pattern holds in Unix. The file system is a strict hierarchy. Processes have a parent-child relationship that forms a tree. The shell pipeline is a linear composition of processes where data flows in one direction. The theoretical preference for hierarchical structure, where the mathematical properties are cleanest and the complexity is most tractable, is embedded in the architecture even when the language does not enforce it.

The Value of the Theoretical Foundation

There is a recurring argument in software engineering that theoretical computer science training is largely irrelevant to practical work. The counterexample is not that Ritchie used Chomsky hierarchies to design C’s parser, because he probably did not in any direct way. The counterexample is that when you understand what structural restrictions on programs mean formally, you make different design decisions than when you are optimizing purely by intuition.

Consider goto. Dijkstra’s objection to it was aesthetic and practical: programs with goto are hard to reason about, hard to prove correct, hard to maintain. Ritchie’s understanding was more precise: unrestricted control flow is what you need when your programs have to do things that hierarchical structures cannot express efficiently. That is not a contradiction of Dijkstra’s position; it is a more complete version of it. The practical systems programmer and the formal theorist arrived at the same language feature from opposite directions and understood it differently.

Reading the dissertation now, what stands out is not any single theorem but the mode of thinking. Ritchie is asking: given this constraint, what is possible? What is the boundary? How does the boundary move when I relax the constraint in a specific way? That is exactly the question driving good language design, and it is the question you can only ask clearly when you have built up the formal vocabulary to state it precisely.

Most working programmers never need to think in those terms explicitly. But the people who design the languages they use every day benefit enormously from having internalized that vocabulary. The dissertation is evidence of where that internalization happened for one of the people who mattered most.

The Computer History Museum has been systematically digitizing primary sources from the people who built early computing infrastructure. This dissertation is among the more significant ones because it bridges the theoretical and practical sides of a career that changed what software looks like. It is worth reading not as a historical curiosity but as a record of how a particular kind of thinking develops before it produces its most recognizable work.