CSC152 2006S, Class 25: Types (1)

Admin:
* Reading: Abstraction Mechanisms in CLU
* Missing: Dimitar

Overview:
* Type Basics
* Primitive/Basic Types
* Type Combinators/Constructors

What is a type?
* A mechanism for representing data (mapping sequences of 0's and 1's to something more understandable by the programmer)
* A type describes data ; labels the bits with their purpose
* Abstraction
* Types provide restrictions on how you can and cannot use 
  particular values.  For example, you can't call a method
  that expects a string on an int (except in Perl).
  * "Can": Integers can be multiplied
* A type is a set.
  I (the integers)
    0 is in I
    if i is in I, then i+1 is in I
    if i is in I, then i-1 is in I

Why have types in a language?
* Abstraction
  * Readability
* Type checking helps avoid programming errors
  * No, you can't multiply two strings
  * No, you can't add a temperature to a price
* A good set of types permit some clever optimizations (e.g.,
  using short rather than long)
* Gives programmer options for representing things
* To give us another topic to talk about

How does a language designer treat types in his/her language?
How does the language designer support the programmer in defining types?  (Not at all?) (Somewhat?) (Equiv to language designer?)
How does the programmer use types?

/Simple Types/
* You need to start somewhere in defining types
* Most languages provide "primitive types" that are direct
  interpretations of bit strings.
  * integer
  * real
  * character
  * boolean
* Abstraction breakdown: We need to consider the relationshp
  between the abstract type and the underlying implementation
  * 16 bit, two's complement, int
  * 32 bit, IEEE standard floating point number
  * ...
* Some languages include other "built in" types that are
  really combinations of the previous types
  * string
  * array of X
* Do we expect programmers to be able to define primitive types?
  * Pascal programmers can build subrange types
    type digits = 0 .. 9;
  * Pascal, C, Java, C++, ... programmers can build enuerated types
    typedef enum { a, b, c, d, f } grades; 
    typedef enum { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday } weekday;
    weekday today;
    today = Monday;
    today = today+1;
    - Defining a set by listing the elements of a set.
    - Pascal does type checking
    - C treats them as ints

Type Theory: Types as Sets
* Given the basic sets (above), build new sets
* Cross product - Build a set of pairs
  AxB is a type (a set)
  AxB = { (a,b) | a in A, b in B }
  * Like a record or a method-less object
* Function - Given sets A and B
  A->B = { f | a in A => f(a) in B }
  + has type (int x int) -> int
  inc has type int -> int
  round has type float -> int
* Sequence: Given a type A
  A* = { (a1 ... an) | n >= 0, for all i, ai in A }

Type Practice: Defining Your Own Types
* In C: Struct (product), Enum (primitive), 
  Pointers, Arrays, Functions, Aliases
  typedef (int) *fip(); // fip is a pointer to a function that  returns an integer
  typedef int temperature;
    temperature roomtemp;
* What is the relationship of the actual C type building mechanisms to the theoretical ones just discussed?
  * Struct -> Product
  * Enum -> Build primitive set by listing contents
  * Arrays -> 
    Sequence: int[] means "indexed collection of ints of some unknown length"
    typedef weekday dave[5];
    dave ventresca;
    dave is;
    Hmmm ... dave is not a sequence.  What is it?
    * Function: dave is an element of (0..4) -> weekday
    * Product: dave is an element of weekday x weekday x weekday x weekday x weekday
  * Functions -> function
  * Aliases -> Bookkeeping?

What set building operations do you know other than those listed above?

* Intersection
* Union
* Complement/Difference
* Apply function to set, giving new set

Think about (do not email answer, but be prepared to be asked)
* Which, if any, of these are supported by languages you know?