CSC302 2007S, Class 32: Types (2) Admin: * I would have liked to have seen more of you at yesterday's talk. * EC for Ferrett/Stewart or Kesho Scott lectures tomorrow. Overview: * Types, Revisited. * Types as Sets. * Describing Types * Lessons from CLU. * References, Pointers, and Variables. What did we learn about types on Monday? * N ways to think about types * A collection of operations (reiterated in CLU) * In computers, a way to interpret the underlying bits * As a set of values. * Most languages include "primitive types" * Need to think about whether and how you support user-defined types How does a language support the construction of new types? * Start with set theory * How do you describe primitive sets? * How do you build new sets from other sets? * Primitive sets: * Natural Numbers * Describe recursively: 0 is a natural number if N is a natural number, then so is N+1 * Days of the Week * DaysOfTheWeek = { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday } * Two strategies for building primitive sets: * Write a procedure that describes the set * Necessary for infinite sets * List the elements of the set * Good for small sets * Names are necessary * Some things are so "primitive" that we wouldn't even bother trying to describe them * What are the typical things we do with sets * Union * Math if R and S are sets then R union S is the set { x | x is in R or x is in S } * CS CLU's oneof type constructor builds a new type that is either in the first or the second (or the third or the fourth) C's union type constructor does the same Pascal's variant record does the same * CLU tells us that a tree is the union of null and pair(tree,tree) * In practice, you don't always know what you're going to store Example: record that represents a Grinnell student student = record { ... studiedAbroad: boolean * If you have two different things you might store, but won't store both simultaneously, they should share memory * Product * Math If R is a set and S is a set, then R*S is the set { s.t. r is in R and s is in S } If S1 ... Sn are sets then S1*S2*...*Sn is the set { s.t., for all i, si is in Si } * CS Record Struct Class, ignoring the methods * Why? We think about grouping these values into a natural whole * With classes and clusters, can also provide a bit of protection * Powerset (star) * Math if S is a set, then S* is the set { <> } union S union S*S union S*S*S union S*S*S*S union ... * CS * perhaps list list-of-int () (i) (i i) (i i i) (i i i i) * String is Char* * perhaps array * Subset * Math If S is an ordered set, r and s are elements of S, then [r..s] is a set { x in S | r <= x <= s } * [0..100] is the set of integers between 0 and 100 * CS * In Pascal, subsets are used to define types for array indices * In typeful worlds, we might want subranges of integers that are valid for the particular domani type grades = 0..100; type weekdays = Monday..Friday; * Subtyping or otherwise renaming integers provides type safetfy * Function * Math If R and S are sets then R=>S is the set { | r in R, s in S, every element of R appears in exactly one pair } * CS Arrays might be thought of as functions from indices to range * Inverse (or difference) * Intersection