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