CSC302 2007S, Class 31: Types (1)

Admin:
* No office hours today (hopefully the last day)
  * But around this afternoon.
* Project groups!
  * Assigned
  * Topics due on Friday

Overview:
* An Introduction to Types.
* Simple Data Types.
* Type Constructors.

/About Types/

* A common programming language construct.
  * What?
  * Why?
  * How? (Design options)
* What are some types you typically use in languages?
  * Strings, integers, symbols
* What is a type?
  * Typically shorthand for data type; a "species" of data
  * A way to say what kind of data you have, so that you know
    how to treat it
    * Division for integers is different than division for
      floating point numbers
    * So you know what operations you can and cannot perform
      on those values
  * A set of values
* What is an integer? (alternately "whole", "natural", "nonnegative integer", "counting number")
  * A buncha bits
  * A whole number.  BZZZ.  Whole numbers are positive integers.
  * The "counting numbers", from negative infinity to infinity.
    * 1, 2, 3, and negative 100.
  * Any number between negative infinity to infinity that has
    no decimal places
  * Any number you can reach by starting at 0 and adding or subtracting one repeatedly.
  * Recursive:
    * 0 is a natural number
    * if n is a natural number, n+1 is a natural number
    * The whole numbers are the natural numbers, excluding 0
    * The integers are the union of the natural numbers and the
      negative whole numbers (needs def'n)
* Three core views of type:
  * In terms of the operations we perform
  * As a set of values
  * As a way to interpret the bits used to store everything on most computers

* Why do we have types?
  * Correctness - Does it make sense to do X to values Y and Z?
  * Clarity - It helps us to understand the program better
  * Design -
    * Part of program design is choosing the right types
      for the problem
      * Accuracy in numeric calcs - Integers
      * Large numbers - Floating Point
    * Part of program design is thinking about the use of memory;
      types CAN speak to this issue
    * Brainstorming - Some of us write programs by scanning 
      through lists of available procedures
  * Display - How to interpet the underlying bits

* Language design issue: You've decided to include types.
  * How?
  * What built-in types?
  * Can users define their own types?  If so, how?
* Built-in types: Two kinds
  * Simple/Primitive types - Building blocks of other types;
    typically supported by the underlying architecture
    * Architecture
      * integers (of different sizes)
      * floats (of different sizes)
      * collections of bits (since we usually have bitwise and, 
        or, not, etc.)
    * Easily layered on the architecture
      * Boolean
      * char
      * Generic pointer
      * pairs (at least on the IBM704 or whatever)
  * Compound types
    * Built by combining (or otherwise modifying) simple types
      * E.g., pair made from two pointers
      * E.g., arbitrary length integer made by stringing together
        integers
      * E.g., string
        * Array of characters
          * in C, it's null terminated
          * with an accompanying "length" field, which could
            be at the beginning of the array
      * Two ways to think about this:
        * What's going on 'behind the scenes'?
        * What is the 'high level' design idea here?
* Detour: Why primitive?
  * An alternative term for "atomic" - cannot be divided
  * The things that came first
  * We stole it from Math

* Should we let the user define types?
  * Yes, it makes the language more attractive - gives the 
    programmer more control
  * No, it's simpler if the programmer only has to learn the
    basic types
  * Yes, the programmer is still going to have to figure out ways
    to represent more complex values, and it's better to have that
    formalized than ad hoc.
  * Yes, supports abstraction, and abstraction is good (at least
    in the abstract)
  * Yes, simplifies language design - if you forget a type, your
    users will define it.
  * No, complicates language design - You have to write the user
    defined types system.
  * No, compilcates programmer's life - Need to learn different 
    type extensions
    
* How do you let the user build types?
* And what types can she build?