*******
 Types
*******

.. index::
   single: type

=================
 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.

.. admonition:: Exercise 10
   :class: exercise

   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.

   :ref:`[Answer] <ex10-answer>`

.. index::
   pair: dynamic; typing
   pair: static; typing

==================
 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.

===============
 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.

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.

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.)

.. admonition:: An enumerate type and a subrange type in Pascal

   .. code-block:: 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

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.

.. admonition:: A record with variant parts in Pacal

   .. code-block:: pascal

     { `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.

.. admonition:: Class inheritance in Java

   .. code-block:: 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.

.. admonition:: Union class and narrowing in TypeScript

   .. code-block:: java

      "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
	  } 
      }

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.

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).

.. admonition:: Function type in Haskell

   .. code-block:: 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

.. index::
   single: type system
   single: type checking

==============
 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.

.. index::
   single: type inference

================
 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.

.. admonition:: Type inference in Standard ML

   We need no type declaration for the function ``inc``.

   .. code-block:: sml

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

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

   .. code-block:: sml

      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``.

.. index::
   single: polymorphism
   
==============
 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.

.. admonition:: ``+`` operator in Java

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

.. admonition:: Template in C++

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

   .. code-block:: c++

      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:

   .. code-block:: c++

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

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

.. admonition:: 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.

.. admonition:: Exercise 11
   :class: exercise

   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``.

   :ref:`[Answer] <ex11-answer>`