Historical Development and Evolution of the C Programming Language

Overview and Origins of C

• The C programming language was created in the early 1970s primarily as a system implementation language for the Unix operating system.
• It was derived from the typeless language BCPL ($Basic Combined Programming Language$) and its descendant, B.
• C evolved from a tool designed for a $8K$-byte memory environment into one of the most dominant languages in the computer industry.
• The most creative development period occurred during 1972.
• Major developmental phases include:
  • 1969-1973: Initial creation in parallel with Unix.
  • 1977-1979: Spate of changes focusing on portability.
  • 1978: Publication of The C Programming Language (the "white book" or "K&R") by Brian Kernighan and Dennis Ritchie.
  • Middle 1980s: Official standardization by the ANSI X3J11 committee.

The Setting: Bell Labs in the Late 1960s

• Bell Telephone Laboratories researchers (including Ken Thompson and Dennis Ritchie) were involved in the Multics project, a joint venture between MIT, General Electric ($GE$), and Bell Labs.
• In 1969, Bell Labs withdrew from Multics because it was deemed too expensive and slow to deliver on its promises.
• Ken Thompson led an informal group to create a new computing environment based on his own designs.
• Key features retained from Multics for the new system (Unix):
  • Notion of a process as a locus of control.
  • Tree-structured file system.
  • Command interpreter as a user-level program.
  • Simple representation of text files.
  • Generalized access to devices.
• Significant exclusion: Thompson excluded Multics' unified access to memory and files.
• The hardware environment was extremely limited: a DEC PDP-7 with $8K$ of $18\text{-bit}$ words of memory.
• The first Unix kernel, editor, assembler, shell, and utilities (like $rm$, $cat$, and $cp$) were written in PDP-7 assembler.
• Bootstrapping: Early development was done on a GE-635 machine using GEMAP assembler macros. Paper tapes were carried to the PDP-7 until the system became self-supporting.
• The name "a.out" stems from the fixed name of the output of Thompson's PDP-7 assembler.

The B Language

• In 1969, Doug McIlroy implemented McClure's TMG (a language for writing compilers in a top-down, recursive-descent style) on the PDP-7.
• Inspired by TMG, Thompson created B to serve as Unix's system programming language.
• B is essentially BCPL condensed to fit in $8K$ bytes of memory.
• Etymology of the name "B":
  • Likely a contraction of BCPL.
  • Potentially derived from "Bon," an unrelated language Thompson created during the Multics era (named after his wife Bonnie or a Tibetan religion).
• B was typeless: its only data type was the "cell" or "word," a fixed-length bit pattern.
• Pointers in B were merely integer indices in the memory array.

Comparison: BCPL, B, and C

• Family: Traditional procedural family ($Fortran$, $Algol 60$).
• Philosophy: Small, compact, close to the machine, relying on library routines for I/O.
• Syntax Evolution:
  • Procedures: BCPL allowed nested procedures; B and C prohibited them entirely to simplify code.
  • Formatting: BCPL elided semicolons at line boundaries; B and C require them.
  • Assignment: BCPL used $:=$; B adopted the single $=$ for assignment.
  • Comments: BCPL used $//$; B and C originally used $/* */$ (influenced by PL/I). C++ later restored $//$.
  • Declarations: BCPL used $let P1 be...$; B used specifiers like $auto$ or $static$ (influenced by Fortran), which C later combined with type keywords.
• Storage Limitations: BCPL required storing the entire program in memory for analysis; the B compiler used a one-pass technique to save memory.
• Linkage: BCPL used a "global vector" where programmers assigned numeric offsets to data and procedures; C moved to a conventional linker to resolve names.

Technical Innovations in Evolution

• Assignment Operators: B introduced operators like $x =+ y$ (later changed to $x += y$ to avoid lexical ambiguity) from Algol 68 via Doug McIlroy.
• Invention of Increment/Decrement: Thompson created the $++$ and $--$ operators.
  • Historical myth: They were created for PDP-11 auto-increment modes.
  • Fact: They were created on the PDP-7, which had "auto-increment memory cells" ($indirect memory reference through them incremented the cell$).
  • Motivation: The translation of $++x$ was smaller than $x = x + 1$.
• Threaded Code: The PDP-7 B compiler produced "threaded code" (an interpretive scheme acting on a simple stack machine) rather than machine instructions.

Transition from B to C

• The move to the DEC PDP-11 exposed B's weaknesses:
  1. Character Handling: B was word-oriented. On the byte-oriented PDP-11, manipulating packed characters via library calls was inefficient.
  2. Floating Point: B's typeless model couldn't accommodate floating-point numbers on a $16\text{-bit}$ machine where a double would require multiple words.
  3. Pointer Scaling: Since B pointers were word indices, every reference required a run-time scale conversion to byte addresses.
• In 1971, Ritchie created "NB" (New B).
• The NB Type System: Introduced $int$ and $char$, arrays of both, and pointers to both.
• The Array-Pointer Crux: Ritchie solved the problem of initializing pointers within structures containing arrays by creating a rule that is still in C today: values of array type are converted into pointers to the first object of the array when they appear in expressions. This eliminated the need to "stash" a literal pointer in memory for every array.

Neonatal C (1972-1973)

• Type Composition: Ritchie captured the Algol 68 notion of atomic types composed into arrays, pointers (references), and functions.
• Syntax Mirroring: The declaration syntax was designed to mimic the expression syntax. Example:
  • $int *pi;$ declares $pi$ as a pointer to an integer because $*pi$ results in an $int$ in an expression.
• Boolean Operators: && and || were introduced.
  • Previously, context (truth-value) determined if & and $|$ were bitwise or short-circuit logical.
  • The late introduction led to the current precedence of & being higher than && but lower than $==$, requiring parentheses in idioms like if ((a & mask) == b).
• The Preprocessor: Introduced at the urging of Alan Snyder for file inclusion and macro replacement. It was initially an optional adjunct.

Portability and the Standard

• 1973: The Unix kernel was rewritten in C for the PDP-11.
• Portability Testing: Moving Unix to the Interdata 8/32 computer (late 70s) forced improvements in type safety.
• Structural Changes: The addition of $unsigned$, $long$, $union$, and $enum$ types during 1973-1980.
• The Lint Tool: Created by Steve Johnson to detect type mismatches and suspicious constructions that the relaxed early C compilers ignored.
• ANSI X3J11 Committee: Established in 1983 (urged by M. D. McIlroy) to provide an authoritative description of C.
• Major Standard Additions:
  • Function Prototypes: Borrowed from C++ ($e.g., double sin(double);$) to enforce argument checking.
  • Type Qualifiers: Introduced $const$ and $volatile$.
  • Library Standardization: Defined a required set of functions (Standard I/O, etc.) to ensure portability across environments.

Critique and Characteristics

• Declaration Syntax: Often criticized for being read "inside-out" (e.g., $int *(*pfp)();$ is a pointer to a function returning a pointer to an integer).
• Arrays and Pointers: C's treatment of arrays as pointers to the first element is powerful but complicates optimization (aliasing issues) and prevents treating arrays as primitive "whole" objects.
• Strings: Handled as null-terminated character arrays ($*e$ in B, $0$ or '\0' in C). Simple to implement but puts the burden of storage management on the user.
• Shortcomings: C provides minimal support for modularization (only two main visibility levels) and is hostile to automatic garbage collection.
• Key to Success: Its success is attributed to the success of Unix, its small and simple compiler requirements, and its pragmatic role as a tool for building larger tools rather than proving a theoretical point.