Chapter 8: Data Types

  • Reasons to have strongly typed language (static type checking)
    • execution efficiency (memory allocation and machine code generation by compiler)
    • translation efficiency (reduce recompilation)
    • writability (catch programming error earlier)
    • security and reliability (reduce execution error)
    • readability
    • remove ambiguities
    • design tool (catch incorrect design descision)
    • interface consistency and correctness

8.1 Data Types and Type Information

  • data type is a set of values.
  • type checking determine whether the type information in a program is consistent.
  • type inference is the process of attaching a type to an expression.
  • type constructor uses to create complex types out of the basic types call user-defined types.
  • type declaration or definition gives name to the user-defined types.
  • untyped language (dynamically typed languages) are without static type systems and all type checking is performed at execution time.

8.2 Simple Types

  • ordinal types has a discrete order that exist on the set.

8.3 Type Constructors

  • Cartesian Product is an ordered pairs of element from multiple sets. (e.g. struct, tuple)
  • Union is discriminated if a tag or discriminator is added to the union to distinghish which type the element is.
  • Undiscriminated union is similar to disjoint union. (e.g. union in c)
  • array on row-major form vs column-major form. (e.g. a[][20] as an argument in function because row size must be known in row-major form so compiler know how to store a).
  • recursive type define a set by taking the smallest solution (least fixed point)

8.4 Type Nomenclature in Sample Languages

8.5 Type Equivalence

  • structural equivalence is when two type have the same structure or built in exactly the same way using the same type constructors from the same simple types.
  • name equivalence is when two type is the same only if they have the same name.
  • declaration equivalence is when new names for existing type names are equivalent to the original types.

8.6 Type Checking

  • Type compatibility (e.g. assignment compatibility, where l-value and r-value are the same type)
  • Implicit type (e.g. constant)

8.7 Type Conversion

  • implicit conversion (or coercions)
  • widening conversion is where the target data type can hold all of the information being converted without loss of data. narrowing conversion is the opposite.
  • explicit conversion (or cast)

8.8 Polymorphic Type Checking

  • overloaded function is ad hoc polymorphism.
  • parametric polymorphism (array of α where α is a type parameter for the array)
  • implicit vs explicit parametric polymorphism
  • subtype or pure polymorphism when objects that share a common ancestor can also either share or redefine the operations that exist for that ancestor.
  • monomorphic is no polymorphism.
  • without knowing the type, a translator cannot determin the size of the values, which much be known in order to make copies from location to location by the code.
    • Expansion generate a copy of the code for each different type used in the function call. Result in code bloat.
    • Boxing or tagging by fix a size for all data that contain any scalar value and add a tag bit to note if its a scalar or not. Result in indirection.

8.9 Explicit Polymorphism

  • mechanism for explicit polymorphism is the template.
  • implicitly constrained parametric polymorphism implicitly applies a constraint to the type parameter with a specific operator (e.g. >) defined for its values.
  • an explicit type parameter example in C++
template <typename T>
struct StackNode{
  T data;
  StrackNode<T> * next;

template <typename T>
struct Stack{
  StackNode<T> * theStack;

template <typename T>
T top (Stack<T> s) {
  return s.theStack->data;

Stack<int> s;
s.theStack = new StackNode<int>;
s.theStack->data = 3;
s.theStack->next = 0;

int t = top(s); // t is now 3

8.10 Case Study: Type Checking in TinyAda

Additional Notes


Other Resources