5. Types

5.1. What is a type?

A type consists of a set of values and designated operations on the values.

Some languages provide sophisticated types while others do not. Major reasons why we use types are as follows:

  • More informative for human readers.

  • Compilers can detect errors when types mismatch.

  • Compilers can generate more efficient code.

Exercise 10

An integer is used for conditional branch (0 is false, otherwise true) in C, while boolean and int are different types in Java. What are merits and demerits of these two methods.

[Answer]

5.2. Type declaration

Dynamic typing

Syntactic entities have no type declarations whereas semantic entities (data) have types. Types of expressions are determined when their values are calculated. Any data can be assigned to any variable.

Static typing

Types of expressions are determined before execution, based on type declarations.

  • In Fortran, explicit and implicit variable declarations are possible. Using implicit declaration, a variable is typed according to the initial letter of its name: integer if beginning with I, … , N, and real if beginning with other letters.

  • In Algol-like languages, variables, function parameters and return values need type declarations.

  • In ML and Haskell, a type can be declared for any expression in a program.

5.3. Various types

Primitive types

Hardware-defined or indecomposable types. (e.g. integer, floating point, character)

Structured types

Types composed of some other types. Many languages allow programmers to define new types.

5.3.1. Enumerated type

We can define a new enumerated type by writing all the possible values for that type.

  • Usually implemented by integer.

  • only comparison is allowed.

  • More readable. Easier to detect errors.

5.3.2. Subrange type

A subrange type is an extraction of a certain ordinal type by specifying its highest and lowest values.

  • Same operations are allowed as the original type.

  • We can detect errors when values are out of range. (For efficiency, some languages provide choices to detect errors or not.)

An enumerate type and a subrange type in Pascal

type
  suit = (club, diamond, heart, spade);
  card = record
           s: suit;
           v: 1..13;
         end;

var myhand: array[1..5] of card;
begin
  myhand[1].s := club;
  myhand[1].v := 1;
  myhand[2].s := club + heart;   { Error }
  myhand[2].v := 0; { Error }
end

5.3.3. Union type

A union type is a type whose value may be one of several different types.

  • In C, union allows programmers to access the same memory location with more than one types.

  • It is up to a programmer which type is used to read and write the content of the memory.

  • Some programmers intentionally use it for evil purposes.

  • In Pascal, record with variant parts provides more sophisticated way.

  • A tag field indicates the type currently stored in a variant part.

  • An error occurs when an operation mismatches with the type in the tag.

  • Still, some programmers may intentionally change the tag value to avoid type checking.

A record with variant parts in Pacal

{ `shape' is an enumerated type whose value is `circle' or `rectangle' }
type shape = (circle, rectangle);

{ `figure' is a record type to store data of rectangles and circles }
type figure = record
                x : real, y : real;
                case form : shape of      { variant parts whose tag is `form' }
                  circle:    (radius : real);
                  rectangle: (width: real; height: real);
                end;

var myfigure : figure;
begin
  myfigure.x := 2.0;
  myfigure.y := 3.0;
  myfigure.form := circle;
  myfigure.radius := 1.0;
  myfigure.width := 1.0;  {Error}
end

  • In object oriented languages, class inheritance is used for that puropose.

Class inheritance in Java

class Main {
  public static void main(String[] args) {
     Figure myfigure;
     myfigure = new Circle();
     myfigure.x = 2.0;
     myfigure.y = 3.0;
     ((Circle)myfigure).radius = 1.0;
  }
}

class Figure {
  double x, y;
}

class Circle extends Figure {
  double radius;
}

class Rectangle extends Figure {
  double width, height;
}

  • In TypeScript, the union operator combines any two types.

    • An operation is allowed if it is valid for all of original types.

Union class and narrowing in TypeScript

"use strict"

interface circle { kind: "circle", x:number, y:number, radius:number }
interface rectangle { kind: "rectangle", x:number, y:number, width: number, height: number }

type figure = circle | rectangle

function foo(f: figure) {
    console.log(f.x)       // OK
    console.log(f.radius)  // Error - Property 'radius' does not exist on type 'figure'.
}

function bar(f: figure) {
    if (f.kind == "circle") {   // Narrowing - Type of f is now circle
        console.log(f.radius)   // OK
    }
}

5.3.4. Pointer type

A pointer type is a type whose value is a reference to another variable. By applying dereference operation, we can get a value of the referred variable.

By using pointers, we can dynamically allocate variables that are not bound to any names. It may cause the following two problems:

Dangling Pointer

If a memory area is released during a pointer is referring to it, the pointer will refer to a garbage or a reused area.

Lost Heap-dynamic Variable

If values of pointers are changed, the memory area referred by the pointers may lose all the references, which means we can never access that area.

  • In case of Pascal, a pointer can only refer to an area allocated by new. We must explicitly release the allocated area by dispose. Pascal has the above two problems.

  • In case of C, pointers are virtually same as the hardware memory addresses. C has many problems including the above two.

    • For example, some programmers relied on the fact that address 0 always contains value 0 in VAX machines. As a result, there were plenty of C programs that run only on VAX machines.

  • In case of Java, objects are implicitly referred to by pointers. Automatic garbage collection prevents the above two problems.

5.3.5. Function type

A function type is composed of types of parameters and return values. It will be very complex for higher-order functions (i.e. parameters or return values are functions).

Function type in Haskell

inc :: Int -> Int
inc x = x + 1

add :: Int -> Int -> Int
add x y = x + y

twice :: (Int -> Int) -> Int
twice f = f(f(1))

twice(inc)   -- returns 3

5.4. Type systems

A type system is a set of rules that associates syntactic entities (usually expressions) with their types.

The process of verifying consistency of types in a program is called type checking. Type checking at compile time is very useful for debugging.

5.5. Type inference

In languages such as ML and Haskell, every expression in a program should have its type. It is too painful to write types for all expressions, the compiler makes an inference about proper typing if we give minimum declarations.

Type inference in Standard ML

We need no type declaration for the function inc.

fun inc x = x + 1;
  val inc = fn : int -> int

We need at least one type declaration for the function add.

fun add (x, y) = x + y;
  Error: overloaded variable '+' cannot be resolved

fun add (x, y) = x + (y : int);
  val add = fn : int * int -> int

fun add (x, y) : int = x + y;
  val add = fn : int * int -> int

Note

In SML ver0.5 or after, the + operator is an overloaded function that has default type int, which means fun add(x, y) = x + y; has the type fn: int * int -> int.

5.6. Polymorphism

When a single operator or function can deal with values of more than one type, we call it polymorphism.

ad hoc polymorphism

Definitions for each type are independent. Also called overloading.

parametric polymorphism

Definitions include formal parameters that receive types of data currently processed.

+ operator in Java

In Java, + operator has two meanings: addition of numbers and concatenation of strings.

Template in C++

We can write a function max in C++ as follows:

template <class Type>
Type max(Type first, Type second) {
    return first > second ? first : second;
}

This template can be instantiated for int and char as follows:

int a, b, c;
char d, e, f;

c = max(a, b);
f = max(d, e);

Polymorphic function in Haskell

In Haskell, an array type is denoted by a bracket [ ] and its element type. For example, the type of [1, 2, 3] is [Int], and the type of ["abc", "def"] is [[Char]] (because a string is an array of character [Char]).

Although [1, 2, 3] and ["abc", "def"] have different types, the function length can be applied to both of them. For example, length [1, 2, 3] returns 3 and length ["abc", "def"] returns 2.

The type of length is [a]->Int where a is a type variable.

Exercise 11

In Haskell, a function call map f x applies the function f to each element of the array x, and then make an array collecting their results. For example, map abs [-5, 3] returns [5, 3] and map length ["abc", "de"] returns [3, 2]. Write the type of map, using type variables a and b.

[Answer]