Lecture 8 Data Structures 15 122 Principles of Imperative Computation Spring 2024 Frank Pfenning Andr Platzer Rob Simmons Iliano Cervesato In this lecture we introduce the idea of imperative data structures So far the only interfaces we ve used carefully are pixels and string bundles Both of these interfaces had the property that once we created a pixel or a string bundle we weren t interested in changing its contents In this lecture we ll talk about an interface that extends the arrays that are primitively available in C0 To implement this interface we ll need to round out our discussion of types in C0 by discussing pointers and structs two tastes that go great to gether We will discuss using contracts to ensure that pointer accesses are safe Additional Resources Review slides pdf tgz Pointers and Structs https cs cmu edu 15122 handouts slides review 08 pointers pdf Libraries https cs cmu edu 15122 handouts slides review 08 library OLI modules https cs cmu edu 15122 handouts oli oli 08 shtml Code for this lecture https cs cmu edu 15122 handouts code 08 libraries There is one short video associated with this lecture Libraries https youtu be ERGA4PaaUrE Relating this to our learning goals we have Computational Thinking We illustrate the power of abstraction by con sidering both the client side and library side of the interface to a data structure Algorithms and Data Structures The abstract data structure will be one of our first examples of abstract datatypes LECTURE NOTES Carnegie Mellon University 2024 Lecture 8 Data Structures 2 Programming Introduction of structs and pointers use and design of in terfaces 1 Structs So far in this course we ve worked with five different C0 types int bool char string and arrays t there is a array type t for every type t The character Boolean and integer values that we manipulate store locally and pass to functions are just the values themselves For arrays and strings the things we store in assignable variables or pass to functions are addresses references to the place where the data stored in the array can be accessed An array allows us to store and access some number of values of the same type which we reference as A 0 A 1 and so on Therefore when entering the following commands in Coin the outputs have been elided cid 7 cid 6 char c n int i 4 string A alloc array string 4 A 0 hi A 1 je A 2 ty A 3 lo cid 4 cid 5 the interpreter will store something like the following in its memory The next data structure we will consider is the struct A struct can be used to aggregate together different types of data which helps us create data structures By contrast an array is an aggregate of elements of the same type Structs must be explicitly declared in order to define their shape For example if we think of an image we want to store an array of pixels along side the width and height of the image and a struct allows us to do that struct img header pixel t data int width int height Lecture 8 Data Structures Here data width and height are fields of the struct The declaration expresses that every image has an array of pixel ts called data as well as a width and a height This description is incomplete as there are some missing consistency checks we would expect the length of data to be equal to the width times the height for instance but we can capture such properties in a separate data structure invariant C0 values such as integers characters the address of an array are small Depending on the computer an address is either 64 bits long or 32 bits long which means that the small types take at most 64 bits to represent Because structs can have multiple components they can grow too large for the computer to easily copy around and C0 does not allow us to use structs as locals coin structs c0 C0 interpreter coin 0 3 2 Nickel Type help for help or quit to exit struct img header IMG stdio 1 1 1 22 error type struct img header not small Hint cannot pass or store structs in variables directly use pointers Therefore we can only create structs in allocated memory just like we This is true can only store the contents of arrays in allocated memory even if they happen to be small enough to fit into 32 bits Instead of alloc array we call alloc which returns a pointer to the struct that has been allocated in memory Let s look at an example in coin struct img header IMG alloc struct img header IMG is 0xFFAFFF20 struct img header We can access the fields of a struct for reading or writing through the notation p f where p is a pointer to a struct and f is the name of a field in that struct Continuing above let s see what the default values are in the allocated memory IMG data default empty int with 0 elements IMG width 0 int IMG height 0 int 3 cid 4 cid 5 cid 4 cid 5 cid 4 cid 5 cid 7 cid 6 cid 7 cid 6 cid 7 cid 6 We can write to the fields of a struct by using the arrow notation on the Lecture 8 Data Structures cid 7 cid 6 left hand side of an assignment IMG data alloc array pixel t 2 IMG data is 0xFFAFC130 int with 2 elements IMG width 1 IMG width is 1 int IMG height 2 IMG height is 2 int IMG data 0 0xFF00FF00 IMG data 0 is 16711936 int IMG data 1 0xFFFF0000 IMG data 1 is 65536 int 4 cid 4 cid 5 The notation p f is a longer form of p f First p follows the pointer to arrive at the struct in memory then f selects the field f We will rarely use this dot notation p f in this course preferring the arrow notation p f An updated picture of memory taking into account the initialization above looks like this As we have seen in the previous section a pointer is needed to refer to a struct that has been created in allocated memory It can also be used more generally to refer to an element of arbitrary type that has been created in allocated memory For example Lecture 8 Data Structures 2 Pointers int ptr1 alloc int ptr1 is 0xFFAFC120 int ptr1 16 ptr1 is 16 int ptr1 16 int In this case we refer to the value of p using the notation p either to read when we use it inside an expression or to write if we use it on the left hand side of an assignment So we would be tempted to say that a pointer value is simply an ad dress But this story which was correct for arrays is not quite correct for pointers There is also a special value NULL Its main feature is that NULL is not a …