Lecture Notes on Polymorphism 15 122 Principles of Imperative Computation Frank Pfenning Lecture 20 March 29 2011 1 Introduction In this lecture we will start the transition from C0 to C In some ways the lecture is therefore about knowledge rather than principles The underlying issue that we are trying to solve in this lecture is nevertheless a deep one how can a language support generic implementations of data structures that accomodate data elements of different types The name polymorphism derives from the fact that data take on different forms for different uses of the same data structure A simple example is the data structure of stacks In our C0 implementation the definition of the stack interface used an unspecified type elem of elements typedef struct stack stack bool stack empty stack S stack stack new void push stack S elem e elem pop stack S O 1 O 1 O 1 O 1 The type elem must be defined before this file is compiled In our testing code we used typedef int elem to test stacks of integers So it was already true that the implementation was generic to some extent but this genericity could not be exploited For example if we wanted a second client using stacks of strings we would L ECTURE N OTES M ARCH 29 2011 Polymorphism L20 2 have to cut and paste our stack code and rename the functions in its interface to avoid conflicts In this lecture we will see how we can make the implementation generic to allow reuse at different types 2 A First Look at C Syntactically C and C0 are very close Philosophically they diverge rather drastically Underlying C0 are the principles of memory safety and type safety A program is memory safe if it only reads from memory that has been properly allocated and initialized and only writes to memory that has been properly allocated A program is type safe if all data it manipulates have their declared types In C0 all programs type safe and memory safe The compiler guarantees this through a combination of static that is compile time and dynamic that is run time checks An example of a static check is the error issued by the compiler when trying to assign an integer to a variable declared to hold a pointer such as int p 37 An example of a dynamic check is an array out of bounds error which would try to access memory that has not been allocated by the program Advanced modern languages such as Java ML or Haskell are both type safe and memory safe In contrast C is neither type safe nor memory safe This means that the behavior of many operations in C is undefined Unfortunately undefined behavior in C may yield any result or have any effect which means that the outcome of many programs is unpredictable In many cases even programs that are patently absurd will yield a consistent answer on a given machine with a given compiler or perhaps even across different machines and different compilers No amount of testing will catch the fact that such programs have bugs but they may break when say the compiler is upgraded or details of the runtime system changes Taken together these design decisions make it very difficult to write correct programs in C This fact is in evidence every day when we download so called security critical updates to operating systems browsers and other software In many cases the security critical flaws arise because an attacker can exploit behavior that is undefined but predictable across some spectrum of implementations in order to cause your machine to execute some arbitrary malicious code You will learn in 15 213 Computer Systems exactly how such attacks work L ECTURE N OTES M ARCH 29 2011 Polymorphism L20 3 These difficulties are compounded by the fact that there are other parts of the C standard that are implementation defined For example the size of values of type int is explicitly not specified by the C standard but each implementation must of course provide a size This makes it very difficult to write portable programs Even on one machine the behavior of a program might differ from compiler to compiler Despite all these problems almost 40 years after its inception C is still a significant language For one it is the origin of the object oriented languages C and strongly influenced Java and C For another much systems code such as operating systems file systems garbage collectors or networking code are still written in C Designing type safe alternative languages for systems code is still an active area of research including the Static OS project at Carnegie Mellon University 3 Lack of Memory Safety When compared to C0 the most shocking difference is that C does not distinguish arrays from pointers As a consequence array accesses are not checked and out of bounds memory references whose result is formally undefined may lead to unpredictable results For example the code fragment int 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 the strictest settings Here the call to malloc allocates enough space for a single integer in memory In this class we are using gcc with the following flags gcc Wall Wextra std c99 pedantic Werror which generates all warnings pedantically applies the C99 standard and turns all warnings into errors The code above executes ok and in fact prints 32 despite four blatant errors in the code To discover whether such errors may have occurred at runtime we can use the valgrind tool L ECTURE N OTES M ARCH 29 2011 Polymorphism 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 4 error in code whose observable behavior was bug free valgrind slows down execution but if at all feasible you should test all your C code in the manner to uncover memory problems For best error messages you should pass the g flag to gcc which preserves some correlation between binary and source code You can also guard memory accesses with approriate assert statements that abort the program when attempting out of bounds accesses Conflating pointers and arrays provides a hint on how to convert C0 programs to C We need to convert t which indicates a C0 array with elements of type t to t to indicate a pointer instead In addition the alloc and alloc array calls need to be changed or defined by appropriate macros Of course there are many cases where C0 programs have a well defined