CP2003 - Type Checking and Expressions

Strings

Although strings are supported by all modern programming languages, there is no consensus on how strings should be handled. There are a number of options:

• as an array of characters

    /* C example */
    char string[20];	/* string of length 20 */
    string = "hello";	/* Fill in array with characters (null terminated) */
  
    /* can apply all the usual array operations */
  

• as a flexible array of characters

    /* PL/C example */
    var jim of character[varying];	/* Any length array */
    jim = "hello";			/* string is any length */
  
    /* string can be any length */
  

• as a list of characters

    Some languages (e.g. Miranda, Prolog) have a specific list type.  This
    makes all the usual list operations applicable to a string.  Similar to a
    linked-list in C/C++, but there is a problem with accessing elements
    (that is, they can only accessed from the front of the list).
  

• as a primitive type

    Size is not a problem; also allows use of string manipulation operators.
  
    # Perl example
    # the string "hello there" is assigned to the scalar variables
    $s = "hello there";
  
    $h = "hello ";
    $s = "$h there"
  
  
    // Java Example
    // Java has a type "Vector" which replaces arrays, lists etc.
    Vector string_object = new Vector();
    string_object.addElement("H");
  
    // MANY operations available on Vectors
  
  

Type Checking

Why bother with type checking?

• To ensure that nonsensical operations are prevented (e.g. don't allow multiplication of a character by a boolean; both sides of a logical operation must be a boolean etc.)
• Type errors are a common kind of programmer error, especially when pointers are involved.

    /* C example */
    void swap(int *x, int *y) {
      ...
    }
    ...
    int a,b;
    swap(a, b);  /* type mismatch error! */
  

When are types checked?

• compile-time: also known as ``static typing''. Every variable and parameter has a fixed type that is chosen by the programmer, and these can only take on values of the given type. Alleviates run-time overhead.
• run-time: also known as ``dynamic typing''. Variables and parameters have no designated type. This allows much greater flexibility, but type checking must be performed at run-time, making execution slower.

    # Perl example
  
    $x = "Hello World\n";		# x has a value of type string
    $x = 3;				# x has a value of type integer
    $z = "5";				# z has a value of type string
  
    $x = $z + $x;			# convert z into an integer and add
  

How are types checked - What is type equivalence?

There are two categories of type equivalence:

• Name Equivalence: The two variables are of exactly the same name type.

    typedef int new_int;
  
    int z;
    new_int y;
  
    z = y;  /* not name equivalent, so fails type check! */
  

• Structural Equivalence: The two variables are of the same type, if their types are represented by the same set. That is, check to make sure the variables have the same structure, rather than type name.

    typedef int new_int;
  
    typedef struct {
      int value;
    } simple_type;
  
    typedef struct {
      int value;
    } another_type;
  
    typedef struct {
      int value;
      char kind;
    } a_third_type;
  
    int z;
    new_int y;
    simple_type var_one;
    another_type var_two;
    a_third_type var_three;
  
    z=x;	/* OK by structure, not by name */
    var_one = var_two;	/* OK by structure, not by name */
    var_one = var_three;  /* not the same structure */
  

Type Completeness

There is a principle which exists in the study of types and values called the type completeness principle. This states that no operation should be arbitrarily restricted in the types of values it takes or returns.

Why? Arbitrary restrictions tend to reduce the expressive power of a programming languages. For example, Pascal functions cannot return a string, set or record. This is a violation of the type completeness principle and causes problems if you need to return these values.