IntroductionA First Look at CLack of Memory SafetyUndefined Behavior in CVoid PointersMemory AllocationGenericity on the Implementation SideMacrosHeader Files and Conditional CompilationFreeing MemoryLecture Notes onPolymorphism15-122: Principles of Imperative ComputationFrank PfenningLecture 20March 29, 20111 IntroductionIn this lecture we will start the transition from C0 to C. In some ways, thelecture is therefore about knowledge rather than principles. The underly-ing issue that we are trying to solve in this lecture is nevertheless a deepone: how can a language support generic implementations of data struc-tures that accomodate data elements of different types. The name polymor-phism derives from the fact that data take on different forms for differentuses of the same data structure.A simple example is the data structure of stacks. In our C0 implemen-tation, the definition of the stack interface used an unspecified type elem ofelements.typedef struct stack* stack;bool stack_empty(stack S); /* O(1) */stack stack_new(); /* O(1) */void push(stack S, elem e); /* O(1) */elem pop(stack S); /* O(1) */The type elem must be defined before this file is compiled. In our testingcode we usedtypedef int elem;to test stacks of integers. So it was already true that the implementationwas generic to some extent, but this genericity could not be exploited. Forexample, if we wanted a second client using stacks of strings, we wouldLECTURE NOTES MARCH 29, 2011Polymorphism L20.2have to cut-and-paste our stack code and rename the functions in its inter-face to avoid conflicts. In this lecture we will see how we can make theimplementation generic to allow reuse at different types.2 A First Look at CSyntactically, C and C0 are very close. Philosophically, they diverge ratherdrastically. Underlying C0 are the principles of memory safety and typesafety. A program is memory safe if it only reads from memory that hasbeen properly allocated and initialized, and only writes to memory thathas been properly allocated. A program is type safe if all data it manipu-lates have their declared types. In C0, all programs type safe and memorysafe. The compiler guarantees this through a combination of static (thatis, compile-time) and dynamic (that is, run-time) checks. An example ofa static check is the error issued by the compiler when trying to assign aninteger to a variable declared to hold a pointer, such asint* p = 37;An example of a dynamic check is an array out-of-bounds error, whichwould try to access memory that has not been allocated by the program.Advanced modern languages such as Java, ML, or Haskell are both typesafe and memory safe.In contrast, C is neither type safe nor memory safe. This means that thebehavior of many operations in C is undefined. Unfortunately, undefinedbehavior in C may yield any result or have any effect, which means thatthe outcome of many programs is unpredictable. In many cases, even pro-grams that are patently absurd will yield a consistent answer on a givenmachine with a given compiler, or perhaps even across different machinesand different compilers. No amount of testing will catch the fact that suchprograms have bugs, but they may break when, say, the compiler is up-graded or details of the runtime system changes. Taken together, thesedesign decisions make it very difficult to write correct programs in C. Thisfact is in evidence every day, when we download so-called security criticalupdates to operating systems, browsers, and other software. In many cases,the security critical flaws arise because an attacker can exploit behavior thatis undefined, but predictable across some spectrum of implementations, inorder to cause your machine to execute some arbitrary malicious code. Youwill learn in 15-213 Computer Systems exactly how such attacks work.LECTURE NOTES MARCH 29, 2011Polymorphism L20.3These difficulties are compounded by the fact that there are other partsof the C standard that are implementation defined. For example, the size ofvalues of type int is explicitly not specified by the C standard, but each im-plementation must of course provide a size. This makes it very difficult towrite portable programs. Even on one machine, the behavior of a programmight differ from compiler to compiler.Despite all these problems, almost 40 years after its inception, C is stilla significant language. For one, it is the origin of the object-oriented lan-guages C++ and strongly influenced Java and C#. For another, much sys-tems code such as operating systems, file systems, garbage collectors, ornetworking code are still written in C. Designing type-safe alternative lan-guages for systems code is still an active area of research, including theStatic OS project at Carnegie Mellon University.3 Lack of Memory SafetyWhen compared to C0, the most shocking difference is that C does not dis-tinguish arrays from pointers. As a consequence, array accesses are notchecked, and out-of-bounds memory references (whose result is formallyundefined) may lead to unpredictable results. For example, the code frag-mentint main() {int* A = malloc(sizeof(int));A[0] = 0; /* ok - A[0] is like *A */A[1] = 1; /* error - not allocated */A[317] = 29; /* error - not allocated */A[-1] = 32; /* error - not allocated */printf("A[-1] = %d\n", A[-1]);return 0;}will not raise any compile time error or even warnings, even under thestrictest settings. Here, the call to malloc allocates enough space for a singleinteger in memory. In this class, we are using gcc with the following flags:gcc -Wall -Wextra -std=c99 -pedantic -Werrorwhich generates all warnings, pedantically applies the C99 standard, andturns all warnings into errors. The code above executes ok, and in factprints 32, despite four blatant errors in the code. To discover whether sucherrors may have occurred at runtime, we can use the valgrind tool.LECTURE NOTES MARCH 29, 2011Polymorphism L20.4% valgrind ./a.out...==nnnn== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)which produces useful error messages (elided above) and indeed, flags 4error in code whose observable behavior was bug-free.valgrind slows down execution, but if at all feasible you should test allyour C code in the manner to uncover memory problems. For best errormessages, you should pass the -g flag to gcc which preserves some corre-lation between binary and source code.You can also guard memory accesses with approriate assert statementsthat abort the program when attempting