C came into being in the years 1969-1973,in parallel with the early developmentof the Unix operating system;the most creative period occurred during 1972.Another spate of changes peaked between 1977 and 1979,when portability of the Unix system was being demonstrated.In the middle of this second period, the first widely available descriptionof the language appeared:The C Programming Language,often called the `white book' or `K&R' [Kernighan 78].Finally, in the middle 1980s, the language was officially standardizedby the ANSI X3J11 committee, which made further changes.Until the early 1980s, although compilers existed for a varietyof machine architectures and operating systems, the language was almost exclusivelyassociated with Unix;more recently, its use has spread much more widely, and today itis among the languages most commonly used throughout the computer industry.
The late 1960s were a turbulent erafor computer systems research at Bell Telephone Laboratories[Ritchie 78] [Ritchie 84].The company was pullingout of the Multics project [Organick 75], which had started as a joint ventureof MIT, General Electric, and Bell Labs; by 1969, Bell Labs management,and even the researchers, came to believethat the promises of Multics could be fulfilledonly too late and too expensively. Even before the GE-645 Multicsmachine was removed from the premises, an informal group, ledprimarily by Ken Thompson, had begun investigating alternatives.
Thompson wanted to create a comfortable computingenvironment constructed according to his own design, using whatevermeans were available. His plans, it is evident in retrospect,incorporated many of the innovative aspects of Multics, including anexplicit notion of a process as a locus of control,a tree-structured file system, a command interpreteras user-level program, simple representation of text files, and generalizedaccess to devices.They excluded others, such as unified access tomemory and to files. At the start, moreover, he and the restof us deferred another pioneering (though not original)element of Multics, namely writing almost exclusively in ahigher-level language.PL/I, the implementation language of Multics, was notmuch to our tastes, but we were also using other languages, including BCPL, andwe regretted losing the advantages of writing programs in alanguage above the level of assembler, such asease of writing and clarityof understanding.At the time we did not put much weighton portability; interest in this arose later.
Thompson was faced witha hardware environment cramped and spartan even for the time:the DEC PDP-7 on which he started in 1968 was a machine with 8K 18-bit wordsof memory and no software useful to him.While wanting to use a higher-level language,he wrote the original Unix system in PDP-7 assembler.At the start, he did not even programon the PDP-7 itself, but instead used a set of macrosfor the GEMAP assembler on aGE-635 machine.A postprocessorgenerated a paper tape readable by the PDP-7.
These tapes werecarried from the GE machine to the PDP-7 for testing until a primitive Unix kernel,an editor, an assembler, a simple shell (command interpreter), and a few utilities(likethe Unixrm, cat, cpcommands)were completed. After this point, the operating system was self-supporting:programs could be written and tested without resort to paper tape,and development continued on the PDP-7 itself.
Thompson's PDP-7 assembler outdid even DEC's in simplicity;it evaluated expressions and emitted the corresponding bits.There were no libraries,no loader or link editor: the entire source of a program was presented tothe assembler, and the output file—with a fixed name—that emerged was directlyexecutable.(This name,a.out,explains a bit of Unix etymology;it is the output of the assembler.Even after the system gained a linkerand a means of specifying another name explicitly,it was retained as the default executableresult of a compilation.)
Not long after Unix first ran on the PDP-7, in 1969, Doug McIlroy createdthe new system's first higher-level language: an implementation ofMcClure's TMG [McClure 65]. TMG is a language for writing compilers(more generally, TransMoGrifiers) in a top-down, recursive-descentstyle that combines context-free syntax notation withprocedural elements. McIlroy and Bob Morris had used TMG to write the earlyPL/I compiler for Multics.
Challenged by McIlroy's feat in reproducing TMG,Thompson decided that Unix—possibly it had not even beennamed yet—needed a system programming language.After a rapidly scuttled attempt at Fortran,he created instead a language of his own,which he called B.B can be thought ofas C without types; more accurately, it is BCPL squeezed into 8K bytes of memoryand filtered through Thompson's brain.Its name most probably representsa contraction of BCPL, thoughan alternate theory holds thatit derives from Bon [Thompson 69],an unrelated language created byThompson during the Multics days.Bon in turn was named either after his wife Bonnie,or (according to an encyclopedia quotation in its manual),after a religion whose rituals involve the murmuring of magic formulas.
BCPL wasdesigned by Martin Richards in the mid-1960s while he was visiting MIT,and was used during the early 1970sfor several interesting projects, among them the OS6 operating systemat Oxford [Stoy 72], and parts of the seminal Alto work at Xerox PARC [Thacker 79].We became familiar with itbecause theMIT CTSS system [Corbato 62] on which Richards worked was used for Multics development.The original BCPL compiler was transported both to Multics and to the GE-635GECOS systemby Rudd Canadayand others at Bell Labs [Canaday 69];during the final throes of Multics's life at Bell Labsand immediately after, it was the language of choiceamong the group of people who would later become involved with Unix.
BCPL, B, and C all fit firmly in the traditionalprocedural family typified by Fortran and Algol 60.They are particularly oriented towardssystem programming, are small and compactly described,and are amenable to translation by simple compilers. They are `closeto the machine' in that the abstractions they introduce are readilygrounded in the concrete data types and operations supplied byconventional computers, and they rely on library routinesfor input-output and other interactions with an operating system.With less success, they also use library procedures to specify interestingcontrol constructs such as coroutines and procedureclosures. At the same time, their abstractions lie at a sufficientlyhigh level that, with care, portability between machines canbe achieved.
BCPL, B and C differ syntactically in many details, but broadlythey are similar.Programs consist of a sequence ofglobal declarations and function (procedure) declarations.Procedures can be nested in BCPL, but may not refer to non-staticobjects defined in containing procedures.B and C avoid this restriction by imposing a more severe one:no nested procedures at all.Each of the languages (except for earliest versions of B)recognizesseparate compilation, and provides a means for includingtext from named files.
Several syntactic and lexical mechanisms of BCPL aremore elegant and regular than those of B and C.For example, BCPL's procedure and data declarationshave a more uniform structure, and it supplies a more completeset of looping constructs.Although BCPL programs are notionally supplied from an undelimitedstream of characters, clever rules allow most semicolons to be elidedafter statements that end on a line boundary.B and C omit this convenience, and endmost statements with semicolons.In spite of the differences, most of the statements and operators of BCPL mapdirectly into corresponding B and C.
Some of the structural differences between BCPL and Bstemmed from limitations on intermediate memory.For example, BCPL declarations may take the form
let P1 becommandand P2 becommandand P3 becommand ...
E1 := valof(declarations ;commands ; resultis E2) + 1
Certain less pleasant aspects of BCPL owed to its own technologicalproblems and were consciouslyavoided in the design of B.For example, BCPL uses a `global vector' mechanism for communicatingbetween separately compiled programs.In this scheme,the programmer explicitly associates the name of each externally visibleprocedure and data object with a numeric offset in the globalvector; the linkage is accomplished in the compiled codeby using these numeric offsets.B evaded this inconvenience initially by insisting that the entireprogram be presented all at once to the compiler.Later implementations of B, and all those of C, use a conventionallinker to resolve external names occurring in files compiled separately,instead of placing the burden of assigning offsets on the programmer.
Other fiddles in the transition from BCPL to B were introduced asa matter of taste, and some remain controversial, for example the decisionto use the single character=for assignment instead of:=.Similarly, B uses/**/to enclose comments, where BCPL uses//,to ignore text up to the end of the line.The legacy of PL/I is evident here.(C++ has resurrected the BCPL comment convention.)Fortran influenced the syntaxof declarations:B declarations begin with a specifierlikeautoorstatic,followed by a list of names, and Cnot only followed this style but ornamented it byplacing its type keywords at the start of declarations.
Not every difference between the BCPL language documented inRichards's book[Richards 79]and B was deliberate;we started from an earlier version of BCPL [Richards 67].For example, theendcasethat escapes from a BCPLswitchonstatement was not present in the language when we learned itin the 1960s,and so the overloading of thebreakkeywordto escape from the B and Cswitchstatementowes to divergentevolution rather than conscious change.
In contrast to the pervasive syntax variation that occurredduring the creation of B, the core semantic content of BCPL—itstype structure and expression evaluation rules—remained intact.Both languages are typeless, or rather have a single data type,the `word,' or `cell,' a fixed-length bit pattern. Memory in these languagesconsists of a linear array of such cells, and the meaning ofthe contents of a cell depends on the operation applied.The+operator, for example, simply adds its operands using the machine'sinteger add instruction, and the other arithmeticoperations are equally unconscious of the actual meaningof their operands. Because memory is a linear array, it is possibleto interpret the value in a cell as an index in this array,and BCPL supplies an operator for this purpose. In theoriginal language it was spelledrv,and later!,while B uses the unary*.Thus, ifpis a cell containingthe index of (or address of, or pointer to) another cell,*prefers to the contents of the pointed-to cell, eitheras a value in an expression or as the target ofan assignment.
Because pointers in BCPL and B are merely integer indicesin the memory array, arithmetic on them is meaningful:ifpis the address of a cell, thenp+1is the address ofthe next cell.This convention is the basis for the semanticsof arrays in both languages. When in BCPL one writes
let V = vec 10
auto V[10];
*(V+i)
V[i]
V!i
None of BCPL, B, or C supports character data stronglyin the language; each treats stringsmuch like vectors of integers and supplements general rules bya few conventions.In both BCPL and B a string literal denotes the address of astatic area initialized with the characters of the string,packed into cells.In BCPL, the first packed byte contains the number of charactersin the string;in B, there is no count and strings are terminated bya special character, which B spelled`*e'.This change was made partially to avoid the limitationon the length of a string caused by holding the countin an 8- or 9-bit slot, and partly because maintainingthe count seemed, in our experience, less convenient than using aterminator.
Individual characters in a BCPL string were usually manipulatedby spreading the string out into another array, one character per cell,and then repacking it later;B provided corresponding routines, but people more often usedother library functions that accessed or replaced individualcharacters in a string.
After the TMG version of B was working, Thompson rewrote B in itself(a bootstrapping step).During development, he continually struggled against memory limitations:each language additioninflated the compiler so it could barely fit, but eachrewrite taking advantage of the feature reduced its size.For example, B introduced generalized assignment operators, usingx=+yto addytox.The notation came fromAlgol 68 [Wijngaarden 75] via McIlroy, who had incorporatedit into his version of TMG.(In B and early C, the operator was spelled=+instead of+=; this mistake, repaired in 1976, was induced by a seductively easyway of handling the first form in B's lexical analyzer.)
Thompson went a step further by inventing the++and--operators, which increment or decrement;their prefixor postfix position determines whether the alterationoccurs before or after noting the value of the operand.They were not in the earliest versions of B, but appearedalong the way.People often guess thatthey were created to use the auto-increment andauto-decrement address modes provided by the DEC PDP-11 on which C and Unixfirst became popular.This is historically impossible, since there was no PDP-11when B was developed.The PDP-7, however,did have a few `auto-increment' memory cells, with the propertythat an indirect memory reference through them incremented the cell.This feature probably suggested such operators to Thompson;the generalization to make them both prefix and postfixwas his own.Indeed, the auto-increment cells were not used directly in implementation of theoperators, and a stronger motivation for the innovation was probablyhis observation thatthe translation of++xwas smaller than that ofx=x+1.
The B compiler on the PDP-7 did not generate machine instructions,but instead `threaded code' [Bell 72], an interpretive scheme in whichthe compiler's output consistsof a sequence of addresses of code fragments that perform theelementary operations.The operations typically—in particular for B—act on a simple stack machine.
On the PDP-7 Unix system, only a few things were written in B except B itself,because the machine was too small and too slow to do more thanexperiment; rewriting the operating system and the utilitieswholly into B was too expensive a step toseem feasible.At some point Thompson relieved the address-space crunch by offering a`virtual B' compiler that allowed the interpreted program to occupy more than 8K bytesby paging the code and data within the interpreter,but it was too slow to be practical for the common utilities.Still, some utilities written in B appeared, including an early version ofthe variable-precision calculatordcfamiliar to Unix users [McIlroy 79].The most ambitious enterprise I undertook was a genuinecross-compiler that translated B to GE-635 machine instructions, not threaded code.It was a smalltour de force:a full B compiler, written in itsown language and generating code for a 36-bit mainframe,that ran on an 18-bit machine with 4K words of user address space.This project was possible only because of the simplicityof the B language and its run-time system.
Although we entertained occasional thoughtsabout implementing one of the major languages of the time like Fortran,PL/I, or Algol 68, such a project seemed hopelessly large for our resources:much simpler and smaller tools were called for.All these languages influenced our work,but it was more fun to do things on our own.
By 1970, the Unix project had shown enough promise that we wereable to acquire the new DEC PDP-11.The processor was among the first of its line delivered by DEC, and three monthspassed before its disk arrived.Making B programsrun on it using the threaded techniquerequired only writing the code fragments for the operators,and a simple assembler which I coded in B;soon,dcbecame the firstinteresting program to be tested, before any operating system, on our PDP-11.Almost as rapidly, still waiting for the disk, Thompson recodedthe Unix kernel and some basic commands in PDP-11 assembly language.Of the 24K bytes of memory on the machine, the earliest PDP-11 Unix systemused 12K bytes for the operating system,a tiny space for user programs, and the remainder as a RAM disk.This version was only for testing, not for real work;the machine marked time by enumerating closed knight'stours on chess boards of various sizes.Once its disk appeared, we quickly migrated to it aftertransliterating assembly-language commands to the PDP-11 dialect, andporting those already in B.
By 1971, our miniature computer center was beginning to have users.We all wanted to create interesting software more easily.Using assembler was dreary enough that B, despite its performanceproblems, had been supplemented by a small library of useful service routinesand was being used for more and more new programs.Among the more notable results of this period was Steve Johnson'sfirst version of theyaccparser-generator [Johnson 79a].
The machines on which we first used BCPL and then B were word-addressed,and these languages' single data type, the `cell,' comfortablyequated with the hardware machine word.The advent of the PDP-11 exposed several inadequacies of B's semantic model.First, its character-handling mechanisms, inherited with few changes from BCPL,were clumsy:using library procedures to spread packed strings into individualcells and then repack, or to access and replaceindividual characters,began to feel awkward, even silly, on a byte-oriented machine.
Second, although the original PDP-11 did not provide for floating-pointarithmetic,the manufacturer promised that it would soon be available.Floating-point operations had been added to BCPLin our Multics and GCOS compilers by definingspecial operators, but the mechanism was possibleonly because on the relevant machines, a single wordwas large enough to contain a floating-point number;this was not true on the 16-bit PDP-11.
Finally, the B and BCPL model implied overhead in dealingwith pointers: the language rules, by defining a pointeras an index in an array of words, forced pointers to be representedas word indices.Each pointer referencegenerated a run-time scale conversion from the pointer to thebyte address expected by the hardware.
For all these reasons, it seemed that a typing schemewas necessary to copewith characters and byte addressing, and to prepare for thecoming floating-point hardware.Other issues, particularly type safety and interface checking, did notseem as important then as they became later.
Aside from the problems with the language itself, the B compiler'sthreaded-code technique yielded programsso much slower than their assembly-language counterpartsthat we discounted the possibility of recoding theoperating system or its central utilities in B.
In 1971 I began to extend the B language by adding a character typeand also rewrote its compiler to generate PDP-11 machine instructionsinstead of threaded code.Thus the transition from B to Cwas contemporaneous with the creation of a compilercapable of producing programs fast and small enoughto compete with assembly language.I called the slightly-extended language NB, for `new B.'
NB existed so briefly that no full description ofit was written.It supplied the typesintandchar,arrays of them, and pointers to them, declared in a style typified by
int i, j;char c, d;int iarray[10];int ipointer[];char carray[10];char cpointer[];
Values stored in the cells bound toarray and pointer nameswere the machine addresses,measured in bytes, of the corresponding storage area.Therefore, indirection through a pointer implied norun-time overhead to scale the pointer from word to byte offset.On the other hand, the machine code for array subscripting and pointer arithmeticnow depended on the type of the array or the pointer:to computeiarray[i]oripointer+iimplied scaling the addendiby the size of the object referred to.
These semantics represented an easy transition from B,and I experimented with them for some months.Problems became evident when I tried to extend the type notation, especiallyto add structured (record) types.Structures, it seemed, should map in an intuitive wayonto memory in the machine,but in astructure containing an array, there was no good place to stash thepointer containing the base of the array, nor anyconvenient way to arrange that it be initialized.For example, the directory entries of early Unix systemsmight be described in C as
struct {intinumber;charname[14];};The solution constituted the crucial jumpin the evolutionary chain between typeless BCPL and typed C.It eliminated thematerialization of the pointer in storage, and instead caused thecreation of the pointer when the array name is mentioned in an expression.The rule, which survives in today's C, is that values of arraytype are converted, when they appear in expressions, intopointers to the first of the objects making up the array.
This invention enabled most existing B code to continueto work, despite the underlying shift in the language's semantics.The few programs that assigned new values toan array name to adjust its origin—possible in B and BCPL,meaningless in C—were easily repaired.More important, the new language retained a coherent and workable (if unusual)explanation of the semantics of arrays, while opening the way to amore comprehensive type structure.
The second innovation that most clearlydistinguishes C from its predecessors isthis fuller type structure and especially its expression in the syntax of declarations.NB offered the basic typesintandchar,together with arrays of them, and pointers to them,but no further ways of composition.Generalization was required:given an object of any type, it shouldbe possible to describe a new object that gathers several into an array,yields it from a function, or is a pointer to it.
For each object of such a composed type, therewas already a way to mention the underlying object:index the array,call the function, use the indirection operator on the pointer.Analogical reasoning led to a declaration syntax for namesmirroring that of the expression syntax in which the names typically appear.Thus,
int i, *pi, **ppi;
int f(), *f(), (*f)();
int *api[10], (*pai)[10];
The scheme of type composition adopted by C owes considerable debtto Algol 68, although it did not, perhaps, emerge in a formthat Algol's adherents would approve of.The central notion I captured from Algol was a type structurebased on atomictypes (including structures), composed into arrays, pointers (references),and functions (procedures).Algol 68's concept of unionsand casts also had an influence that appeared later.
After creating the type system, the associatedsyntax, and the compiler for the new language,I felt that it deserved a new name;NB seemed insufficiently distinctive.I decided to follow the single-letter style and called it C,leaving open the question whether the name representeda progression through the alphabet or through the letters in BCPL.
Rapid changes continued after the language had been named,for examplethe introduction of the&&and||operators.In BCPL and B, the evaluation of expressions dependson context: withinifand other conditional statements that comparean expression's value with zero,these languages place a special interpretation on theand(&)andor(|)operators.In ordinary contexts, they operate bitwise, butin the B statement
if (e1 & e2) ...
Their tardy introduction explains aninfelicity of C's precedence rules. In B one writes
if (a==b & c) ...
if ((a&mask) == b) ...
Many other changes occurred around 1972-3, but the most importantwas the introduction of the preprocessor,partly at the urging of Alan Snyder [Snyder 74],but also in recognition of the utility of thethe file-inclusion mechanisms available in BCPL and PL/I.Its original version was exceedingly simple,and provided only included files andsimple string replacements:#includeand#defineof parameterless macros.Soon thereafter, it was extended, mostly by Mike Leskand then by John Reiser,to incorporate macros with arguments and conditionalcompilation.The preprocessor was originally considered an optional adjunctto the language itself. Indeed, for some years,it was not even invoked unless the source program containeda special signal at its beginning.This attitude persisted, and explainsboth the incomplete integration of the syntax of thepreprocessor with the rest of the languageand the imprecision of its description in early referencemanuals.
By early 1973, the essentials ofmodern C were complete.The language and compiler were strong enough to permit us torewrite the Unix kernel for the PDP-11 in C during the summer of that year.(Thompson had made a brief attempt to produce a system coded in an early version ofC—before structures—in 1972, but gave up the effort.)Also during this period, the compiler was retargeted to other nearby machines,particularly the Honeywell 635 and IBM 360/370;because the language could not live in isolation,the prototypes for the modern librarieswere developed.In particular, Lesk wrote a `portable I/O package' [Lesk 72]that was later reworked to become the C `standard I/O' routines.In 1978 Brian Kernighan and I publishedThe C Programming Language[Kernighan 78].Although it did not describe some additionsthat soon became common, this book served as the languagereference until a formal standard was adopted more thanten years later.Although we worked closely together on this book, there was a clear division of labor:Kernighan wrote almost all the expository material, whileI was responsible for the appendix containing the reference manual andthe chapter on interfacing with the Unix system.
During 1973-1980,the language grew a bit:the type structure gained unsigned, long, union, and enumeration types,and structures became nearly first-class objects(lacking only a notation for literals).Equally important developments appeared in its environment and the accompanyingtechnology.Writing the Unix kernel in C had given us enough confidence in the language'susefulness and efficiency that we began to recode thesystem's utilities and tools as well,and then to move the most interesting among them to the otherplatforms.As described in [Johnson 78a], we discovered that the hardest problemsin propagating Unix tools lay not in theinteraction of the C language with new hardware,but in adapting to the existing software of otheroperating systems.Thus Steve Johnson began to work onpcc,a C compiler intended to be easy to retarget to new machines [Johnson 78b],while he, Thompson, and I began to move the Unix system itself tothe Interdata 8/32 computer.
The language changes during this period, especially around 1977,were largely focused on considerations of portability and type safety,in an effort to cope with the problems we foresaw and observedin moving a considerable body of code to the new Interdataplatform.C at that time still manifested strong signs of its typelessorigins.Pointers, for example, were barely distinguished fromintegral memory indices in early language manuals or extant code;the similarity of the arithmetic properties ofcharacter pointers and unsigned integers made it hardto resist the temptation to identify them.Theunsignedtypes were added to make unsigned arithmetic availablewithout confusing it with pointer manipulation.Similarly, the early language condoned assignments betweenintegers and pointers, but this practice began to be discouraged;a notation for type conversions (called `casts' from the example of Algol 68)was invented to specify type conversions more explicitly.Beguiled by the example of PL/I, early Cdid not tie structure pointers firmly to the structuresthey pointed to, and permitted programmers to writepointer->memberalmost without regard to the type ofpointer;such an expression was taken uncritically as a referenceto a region of memory designated by the pointer, while the membername specified only an offset and a type.
Although the first edition of K&R described most of therules that brought C's type structure to its present form,many programs written in the older, more relaxed stylepersisted, and so did compilers that tolerated it.To encourage people to pay more attention to theofficial language rules, to detect legal but suspicious constructions,and to help find interface mismatchesundetectable with simple mechanisms for separate compilation,Steve Johnson adapted hispcccompiler to producelint[Johnson 79b],which scanned a set of files and remarked on dubious constructions.
The success of our portability experiment on theInterdata 8/32 soon led to another by Tom London and John Reiseron the DEC VAX 11/780.This machine became much more popular than the Interdata, andUnix and the C language began to spread rapidly, both within AT&T andoutside.Although by the middle 1970sUnix was in use bya variety of projects within the Bell Systemas well as a small group of research-orientedindustrial, academic, and government organizations outside our company,its real growth began only after portability had been achieved.Of particular note were the System III and System Vversions of the system from the emerging Computer Systems division of AT&T, basedon work by the company's development and research groups,and the BSD series of releases by the Universityof California at Berkeley that derived from researchorganizations in Bell Laboratories.
During the 1980s the use of the C language spread widely,and compilers became available on nearly every machine architectureand operating system; in particular it became popular as aprogramming tool for personal computers, both for manufacturersof commercial software for these machines, and for end-usersinterested in programming.At the start of the decade, nearly every compiler was based on Johnson'spcc;by 1985 there were many independently-produced compiler products.
By 1982 it was clear that C needed formal standardization.The best approximation to a standard,the first edition of K&R, no longer described the language in actual use;in particular, it mentioned neither thevoidorenumtypes.While it foreshadowed the newer approach to structures, only afterit was published did the language support assigning them, passing themto and from functions, and associating the names of members firmlywith the structure or union containing them.Although compilers distributed by AT&T incorporated these changes,and most of the purveyors of compilers not based onpccquickly picked up them up, there remained no complete, authoritativedescription of the language.
The first edition of K&R was also insufficiently precise on many detailsof the language, and it became increasingly impractical to regardpccas a `reference compiler;'it did not perfectlyembody even the language described by K&R, let alone subsequent extensions.Finally, the incipient use of C in projects subject to commercialand government contract meant that the imprimatur of an officialstandard was important.Thus (at the urging of M. D. McIlroy), ANSI established the X3J11committee under the direction of CBEMAin the summer of 1983, with the goal of producinga C standard.X3J11 produced its report [ANSI 89] at the end of 1989,and subsequently this standard was accepted by ISO asISO/IEC 9899-1990.
From the beginning, the X3J11 committee took a cautious,conservative view of language extensions.Much to mysatisfaction, they took seriously their goal:`to develop a clear, consistent, and unambiguous Standardfor the C programming language which codifies the common,existing definition of C and which promotes the portabilityof user programs across C language environments.' [ANSI 89]The committee realized that mere promulgation of a standarddoes not make the world change.
X3J11 introduced only one genuinely important change to the language itself:it incorporated the types of formal arguments in the typesignature of a function, using syntax borrowed from C++ [Stroustrup 86].In the old style, external functions were declared like this:
double sin();
double sin(double);
X3J11 also introduceda host of smaller additions and adjustments, for example,the type qualifiersconstandvolatile,and slightly different type promotion rules.Nevertheless, the standardization process did not change the characterof the language.In particular, the C standard did not attempt to specify formallythe language semantics, and so there can be dispute over fine points;nevertheless, it successfully accounted for changes inusage since the original description, and is sufficiently precise tobase implementations on it.
Thus the core C language escaped nearly unscathed from thestandardization process, and the Standard emerged moreas a better, careful codification than a new invention.More important changes took place in the language's surroundings:the preprocessor and the library.The preprocessor performs macro substitution, using conventionsdistinct from the rest of the language.Itsinteraction with the compiler had neverbeen well-described, and X3J11 attempted to remedy thesituation.The result is noticeably better than the explanation in the first edition of K&R;besides being more comprehensive, it providesoperations, like token concatenation, previously availableonly by accidents of implementation.
X3J11 correctly believed that a full and carefuldescription of a standard C library was as important as itswork on the language itself.The C language itself does not provide for input-outputor any other interaction with the outside world, and thusdepends on a set of standard procedures.At the time of publication of K&R, C was thought of mainlyas the system programming language of Unix; although weprovided examples of library routines intended to be readily transportableto other operating systems, underlying support from Unix was implicitlyunderstood.Thus, the X3J11 committee spent much of its time designingand documenting a setof library routines required to be available in allconforming implementations.
By the rules of the standards process, the current activity of the X3J11committee is confined to issuing interpretations on the existingstandard.However, an informal group originally convened by Rex Jaeschkeas NCEG (Numerical C Extensions Group) has been officially acceptedas subgroup X3J11.1,and they continue to consider extensions to C.As the name implies, many of these possible extensions are intended to make the languagemore suitable for numerical use: for example, multi-dimensional arrayswhose bounds are dynamically determined, incorporation of facilitiesfor dealing with IEEE arithmetic, and making the language more effective on machineswith vector or other advanced architectural features.Not all the possible extensions are specifically numerical; theyinclude a notation for structure literals.
C and even B have several direct descendants, though theydo not rival Pascal in generating progeny.One side branch developed early.When Steve Johnson visited the University of Waterloo on sabbaticalin 1972,he brought B with him. It became popularon the Honeywell machines there, and later spawned Eh and Zed(the Canadian answers to `what follows B?').When Johnson returned to Bell Labs in 1973, he was disconcerted tofind that the language whose seeds he brought to Canadahad evolved back home;even his ownyaccprogram had been rewritten in C, by Alan Snyder.
More recent descendants of C proper include Concurrent C [Gehani 89],Objective C [Cox 86], C* [Thinking 90],and especially C++ [Stroustrup 86].The language is also widely used as an intermediaterepresentation (essentially, as a portable assembly language)for a wide variety of compilers, both for direct descendentslike C++, and independent languages likeModula 3 [Nelson 91] andEiffel[Meyer 88].
Two ideas are most characteristic of C among languages of its class:the relationship between arrays and pointers,and the way in which declaration syntax mimics expression syntax.They are also among its most frequently criticized features,and often serve as stumbling blocks to the beginner.In both cases, historical accidents or mistakes have exacerbatedtheir difficulty.The most important of these has been the tolerance of C compilersto errors in type.As should be clear from the history above, C evolved from typelesslanguages.It did not suddenly appear to its earliestusers and developers as an entirely new language with its own rules;instead we continually had to adapt existing programs as thelanguage developed, and make allowance for an existing bodyof code. (Later, the ANSI X3J11 committee standardizing C wouldface the same problem.)
Compilers in 1977, and even well after,did not complain about usages such as assigning between integersand pointers or using objects of the wrong type to referto structure members.Although the language definition presented in the first edition of K&Rwas reasonably (though not completely) coherent in its treatment of type rules,that book admitted that existing compilers didn't enforce them.Moreover, some rules designed to ease early transitionscontributed to later confusion.For example, the empty square brackets in the function declaration
int f(a) int a[]; { ... }In K&R C, supplying arguments of the proper type to a function callwas the responsibility of the programmer, and the extant compilersdid not check for type agreement.The failure of the original language to include argument typesin the type signature of a functionwas a significant weakness,indeed the one that required the X3J11 committee's boldest and most painfulinnovation to repair.The early design is explained (if not justified) by my avoidance of technologicalproblems, especially cross-checking between separately-compiled source files,and my incomplete assimilation of the implications of moving betweenan untyped to a typed language.Thelintprogram,mentioned above,tried to alleviate the problem:among its other functions,lintchecks the consistency and coherency of a whole program by scanning a setof source files,comparing the types of function arguments used in calls with thosein their definitions.
An accident of syntax contributed to the perceived complexity of the language.The indirection operator, spelled*in C, is syntactically a unary prefix operator, just as in BCPL and B.This works well in simple expressions, but in more complex cases,parentheses are required to direct the parsing.For example, to distinguish indirection through the valuereturned by a function from calling a function designated bya pointer, one writes*fp()and(*pf)()respectively.The style used in expressions carries through to declarations, so the names might bedeclared
int *fp();int (*pf)();
int *(*pfp)();
In spite of its difficulties,I believe that the C's approach to declarations remains plausible,and am comfortable with it; it is a useful unifying principle.
The other characteristic feature of C, its treatment of arrays,is more suspect on practical grounds, though it also hasreal virtues.Although the relationship between pointers and arraysis unusual, it can be learned.Moreover, the language shows considerable power to describe importantconcepts, for example, vectors whose length varies at run time,with only a few basic rules and conventions.In particular, character strings are handled by the same mechanismsas any other array, plus the convention that a null characterterminates a string.It is interesting to compare C's approach with that of twonearly contemporaneous languages, Algol 68 and Pascal [Jensen 74].Arrays in Algol 68 either have fixed bounds, or are `flexible:'considerable mechanism is required both in the languagedefinition, and in compilers, to accommodate flexible arrays(and not all compilers fully implement them.)Original Pascal had only fixed-sized arrays and strings,and this proved confining [Kernighan 81].Later, this was partially fixed, though the resultinglanguage is not yet universally available.
C treats strings as arrays of charactersconventionally terminated by a marker.Aside from one special rule about initialization by string literals,the semantics of strings are fully subsumed by more generalrules governing all arrays, andas a result the language is simpler to describe andto translate than one incorporating the string as a uniquedata type.Some costs accrue from its approach:certain string operations are more expensive than in other designsbecause application code ora library routine must occasionally search for the end of a string,because few built-in operations are available, and becausethe burden of storage management for strings falls moreheavily on the user.Nevertheless, C's approach to strings works well.
On the other hand, C's treatment of arrays in general (not just strings)has unfortunate implications both for optimizationand for future extensions.The prevalence of pointers in C programs, whether those declaredexplicitly or arising from arrays, means thatoptimizers must be cautious, and must use careful dataflow techniquesto achieve good results.Sophisticated compilers can understand what most pointerscan possibly change, but some important usages remain difficultto analyze.For example, functions with pointer arguments derived fromarrays are hard to compile into efficient code onvector machines, because it is seldom possible to determinethat one argument pointer does not overlap data alsoreferred to by another argument, or accessible externally.More fundamentally, the definition of C so specifically describesthe semantics of arrays thatchanges or extensions treating arrays as moreprimitive objects, and permitting operations on them as wholes,become hard to fit into the existing language.Even extensions to permit the declaration and use of multidimensional arrays whosesize is determined dynamically are not entirely straightforward [MacDonald 89][Ritchie 90],although they would make it much easier to write numericallibraries in C.Thus, C covers the most important uses of strings and arraysarising in practice by a uniform and simple mechanism,but leaves problems for highly efficient implementations and for extensions.
Many smaller infelicities exist in the languageand its descriptionbesides those discussed above, of course.There are alsogeneral criticisms to be lodged that transcend detailed points.Chief among these is that the language and its generally-expectedenvironment provide little help for writing very large systems.The naming structure provides only two main levels,`external' (visible everywhere) and `internal' (withina single procedure).An intermediate levelof visibility (within a single file of data and procedures)is weakly tied to the language definition.Thus, there is little direct support for modularization,and project designers are forced to create their own conventions.
Similarly, C itself provides two durations of storage:`automatic' objects that exist while control resides in or belowa procedure, and `static,' existing throughout execution of a program.Off-stack, dynamically-allocated storage is provided onlyby a library routine andthe burden of managing it is placed onthe programmer: C is hostile to automatic garbage collection.
C has become successful to an extent far surpassing any earlyexpectations. What qualities contributed to its widespread use?
Doubtless the success of Unix itself was the most important factor;it made the language available to hundreds of thousands of people.Conversely, of course, Unix's use of C and its consequentportability to a wide variety of machineswas important in the system's success.But the language's invasion of other environments suggests morefundamental merits.
Despite some aspects mysterious to the beginner andoccasionally even to the adept,C remains a simple and small language, translatable with simple and small compilers.Its types and operations arewell-grounded in those provided byreal machines, and forpeople used to how computers work,learning the idioms for generating time- and space-efficient programsis not difficult.At the same time the language is sufficiently abstracted from machinedetails that program portability can be achieved.
Equally important, C and its central library support alwaysremained in touch with a real environment.It was not designed in isolation to prove a point, or to serveas an example, but as a tool to write programs that diduseful things; it was always meant to interact with a largeroperating system, and was regarded as atool to build larger tools.A parsimonious, pragmatic approach influenced the things that went into C:it coversthe essential needs of many programmers,but does not try to supply too much.
Finally, despite the changes that it has undergone since its firstpublished description, which was admittedly informaland incomplete, the actual C language as seen by millions of usersusing many different compilers has remained remarkably stableand unified compared to those of similarly widespread currency,for example Pascal and Fortran.There are differing dialects of C—most noticeably, those described bythe older K&R and the newer Standard C—but on the whole, C has remainedfreer of proprietary extensions than other languages.Perhaps the most significant extensions are the `far' and `near'pointer qualifications intended to deal with peculiaritiesof some Intel processors.Although C was not originally designed with portabilityas a prime goal, it succeeded in expressingprograms, even including operating systems,on machines ranging from the smallest personalcomputers through the mightiest supercomputers.
C is quirky, flawed, and an enormous success.While accidents of history surely helped,it evidently satisfied a need for a system implementation languageefficient enoughto displace assembly language, yet sufficiently abstract and fluent todescribe algorithms and interactions in a wide variety of environments.
It is worth summarizing compactly the roles of the direct contributors to today'sC language.Ken Thompson created the B language in 1969-70; it was derived directlyfrom Martin Richards's BCPL.Dennis Ritchie turned B into C during 1971-73, keeping most of B's syntaxwhile adding types and many other changes, and writing thefirst compiler.Ritchie, Alan Snyder, Steven C. Johnson, Michael Lesk, and Thompson contributed languageideas during 1972-1977,and Johnson's portable compiler remains widely used.During this period, the collection of library routines grewconsiderably, thanks to these people and many others at Bell Laboratories.In 1978, Brian Kernighan and Ritchie wrote the book thatbecame the language definition for several years.Beginning in 1983, the ANSI X3J11 committee standardizedthe language. Especially notable in keeping itsefforts on track were its officersJim Brodie, Tom Plum, and P. J. Plauger, and the successive draft redactors,Larry Rosler and Dave Prosser.
I thank Brian Kernighan, Doug McIlroy, Dave Prosser, PeterNelson, Rob Pike, Ken Thompson, and HOPL's refereesfor advice in the preparation of this paper.