<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
*******
 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 before execution if types are inconsistent.
- 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::
   single: type system
   pair: dynamic; typing
   pair: static; typing
   single: type annotation
   single: type hints
   single: type checking

==================
 Type system
==================

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.

Dynamic typing
  Syntactic entities (e.g. variables) have no type declarations
  whereas semantic entities (e.g. values) have types.
  The type of an expression is determined
  when its value is calculated.
  Any type of values can be assigned to any variable.

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

Gradual typing
  Some expressions are given types before execution
  while othes are left untyped and determined dynamically.

* 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.
* Recently, some dynamic typing languages such as Python and Ruby
  introduce *type annotations* or *type hints* to provide gradual typing.

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

.. comment::

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

Algebraic data type
-------------------

An algebraic data type is constructed from other types
by two methods: a *sum* and a *product*.

* A sum is a choice among types (same as a union type).  It contains a
  constructor to indicate which component type the value belongs.

* A product is a combination of types (same as a record type).

.. admonition:: Single linked list

   .. code-block:: haskell

      data IntList = Nil | Cons Int IntList

Reference type
--------------

A reference type (or 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 C, pointers are virtually same as the hardware memory
  addresses.  C has many problems including the above two.

* 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 Java, objects are implicitly referred to by pointers.
  Automatic garbage collection prevents the above two problems.

* In case of Rust, the concept of ownership enables the compiler to
  guarntee the safety of reference handling without garbage
  collection.

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 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 F#

   Fully decalared version:

   .. code-block:: fsharp

      let addone (x:int) : int =
        let result:int = x + 1
	result

   We can omit type declaration.  Still, a function call ``addone
   1.5`` causes an error at compile time.  The compiler infers the
   type of ``x`` is ``int`` because arguments of ``+`` must have the
   same type.

   .. code-block:: fsharp

      let addone x =
        let result = x + 1
	result

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