5. 型

5.1. 型とは何か

型は、値の集合と、その値への操作から構成される。

言語によって、型をほとんど使わないものや、型理論に基づいた高度な使い方をするものがある。型を積極的に使う理由として、次のような点が挙げられる。

• 人間にとって読みやすい。

• コンパイル時にエラーを発見できる。

• 効率の良いコードを生成できる。

課題10

Cでは真偽値を整数で表す(0が偽、それ以外が真)が、Javaでは真偽値と整数は別の型である。それぞれの利点と欠点は何か。

【解答例】

5.2. 型システム

ある言語において、プログラム中の式に型を対応させるやり方を、その言語の型システム(type system)という。

動的型付け(dynamic typing)

変数や式（構文的要素）に対して型宣言を行わない。データそのもの（意味的実体）には型があるので、実行時に式を評価すれば型が決まる。Lisp, JavaScript, Rubyなど。

静的型付け(static typing)

変数や式（構文的要素）に対して型宣言を行う。実行する前に型が決まるので、型が一致していないなどのバグを検出できる。

• 多くの言語(特にAlgol系)では、変数・関数の引数・関数の返り値に対して明示的に型を宣言する。

• FORTRANでは、明示的に型が宣言されていない変数には暗黙の型宣言が行なわれ、変数名がI〜Nで始まる場合は INTEGER 、それ以外は REAL になる。

• MLやHaskellなど、変数だけでなく任意の式に型宣言が書ける言語もある。

• PHP, Python, Rubyなど動的型付けの言語でも、アノテーションや型ヒントなどを付加して実行前に検査する機能がある。

5.3. いろいろな型

基本型

ハードウェアが直接扱う型か、それ以上分解できないもの。整数、浮動小数点数、文字など。

構造型

既存の型を組み合わせた型。多くの言語では、ユーザが新しい構造型を定義できる。

5.3.1. 列挙型

取りうる値をすべて列挙することにより定義した型。

• 内部的には整数で表現されるのが普通。

• 比較演算しか許されない。（整数と演算できてしまう言語もある）

• 読みやすさやエラー検出の点で優れている。

5.3.2. 部分範囲型

元の型に対して、ある範囲に含まれる値だけを取り出した型。

• 元の型と同じ演算ができる。

• 範囲外の値を使用すると検出できるという利点がある。（でも効率が悪くなるので、検出するかどうか選べるようになっていることが多い）

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;   { エラー }
  myhand[2].v := 0; { エラー }
end

5.3.3. 共用体型

静的型付けの言語で、一つの変数に、場合によって違う型の値を記憶したい時に使用する型。

• Cのunion型では、同じ記憶領域を違う型としてアクセスすることが可能。

  • どの型を使ってアクセスするかはプログラマの自由なので、代入と参照で違う型を使うことができてしまう。

  • これを悪用し、意図的に違う型でアクセスする手段として使うことがある。

• Pascalでは、可変部付きrecord型によってもう少しまともなやり方を提供している。

  • タグの値は、可変部に現在記憶されているのがどの型のデータであるかを示している。

  • タグが示している型と違う型で可変部にアクセスするとエラーになる。

  • タグの値を勝手に変更するという抜け道は、ある。

Pacalの可変部付きレコード型

{ shapeは列挙型で、circleまたはrectangleという値を持つ }
type shape = (circle, rectangle);

{ figureはレコード型で、円または長方形のデータを記憶する }
type figure = record
                { xとyというフィールドは必ずある }
                x : real, y : real;
                { formというフィールドの値によって、これ以後は変化する }
                case form : shape of
                  { formの値がcircleならradiusというフィールドが存在する }
                  circle:    (radius : real);
                  { formの値がrectangleならwidthとheightというフィールドが存在する }
                  rectangle: (width: real; height: real);
                end;

var myfigure : figure;
begin
  { 変数myfigureに中心が(2.0, 3.0)、半径が1.0の円を代入する }
  myfigure.x := 2.0; myfigure.y := 3.0;
  myfigure.form := circle;
  myfigure.radius := 1.0;
end

• オブジェクト指向言語では、サブクラスがスーパークラスの部分型になるので、特に共用体のための型はない。

Javaでスーパークラス型の変数にサブクラス型のオブジェクトを代入する

class Figure
  double x, y;
end

class Circle extends Figure
  double radius;
end

class Rectangle extends Figure
  double width, height;
end

class Foo
   public static void main() {
     Figure myfigure;
     myfigure = new Circle(2.0, 3.0, 1.0);
   }
end

5.3.4. 代数的データ型

データ・コンストラクタを使って構造を定義する。実は、これさえあればリストや列挙型や共用体型などと同じことができる。

代数的データ型 - wikipedia

5.3.5. ポインタ型

他の記憶領域への参照を値とする型。dereference演算を行なうと、参照している記憶領域の内容を取り出せる。

ポインタを使用すると、名前に束縛されていない変数を参照できるが、その場合、次の二つの問題が発生する。

Dangling Pointer

ポインタが動的に割り当てられた変数を指しているとき、その記憶領域が解放されてしまうと、ポインタは意味のないところを参照することになる。

Lost Heap-dynamic Variable

動的に割り当てられた変数がポインタで参照されているとき、ポインタを記憶している変数の値を変更すると、その変数への参照がなくなってしまい、二度とアクセスできなくなる。

• Pascalのポインタ型は、 new によってヒープ領域に動的に割り当てられた変数のみを参照できる。記憶領域の解放は dispose によって明示的に行なうため、上の二つの問題が発生する。

• Cのポインタ型は、事実上ハードウェアにおけるメモリアドレスと同じものであり、とんでもないところを指すポインタも簡単に作れる。上の二つはもちろん、それ以外にもいろいろ問題がある。

  • 例えば、昔のVAXマシンでは各プロセスの0番地に必ず0が入っていたので、nullポインタをdereferenceしてもエラーにならずに0が返ってくる。その結果、VAXでは動くが他のマシンでは動かないCプログラムがたくさんあった。

• Javaの参照型は、オブジェクトのみを参照でき、自動的にdereferenceを行なう。記憶領域の解放はゴミ集めによって自動的に行われるので、上の問題は起こらない。

5.3.6. 関数型

関数（あるいはメソッド）を first class object （整数や文字など基本的なデータ型と同様に変数に代入したり関数の引数にしたりできる）として扱う言語では、引数の型と返り値の型から関数の型を構成する。引数や返り値がまた関数になっていると、非常に複雑な型になる。

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)   -- => 3

5.4. 型変換

5.4.1. 自動的な型変換

違う型の値を混ぜて演算する場合、自動的にどれかの型に揃えてから演算する場合がある。

四則演算

多くの言語では、整数と浮動小数点数を混ぜた式を評価すると、整数を浮動小数点数に変換してから計算する。例えば、 3 / 2.0 は 3.0 / 2.0 と同じになる。

数値から文字列への変換

JavaやRubyでは、数値と文字列に対して + 演算子を適用すると、数値が文字列に変換される。例えば、 2 + "3" は "2" + "3" と同じになる。

5.4.2. 明示的な型変換

多くの言語では、ユーザが指定した型に変換する機能がある。

5.5. 型検査

型検査(type checking)とは、プログラム中の式が型について整合的であるかどうか検査することである。整合的であるのは、演算の対象となる値の型が、その演算を許している型か、自動的な型変換によってそのような型に変換できる場合である。

静的型付けの言語では、コンパイル時に型検査ができるので、実行する前にバグが発見できる。（明示的な型変換でむりやり型を合わせたりすることもあるが…）

5.6. 型推論

MLやHaskellでは、プログラム中のあらゆる式に対して静的に型が決まらないといけない。しかし、すべての式に型を書くのは面倒なので、必要な部分にのみ型宣言を行なうと、残りの式に対しては型を自動的に推論してくれる。これを型推論(type inference)と言う。

Standard MLにおける型推論

1増やす関数 inc の定義には型宣言が必要ない。

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

足し算を行なう関数 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

注釈

SMLバージョン0.5以降では + 演算子はデフォルトで int 型に作用すると解釈されるようになったので、 fun add(x, y) = x + y; はエラーにならずに fn: int * int -> int 型になる。

5.7. 多相性

一つの演算子や関数が複数の型に対応することを多相性(polymorphism)と言う。

ad hoc polymorphism

特定の複数の型に対して、個別に定義する。Overloading とも言う。

parametric polymorphism

型を値とする変数（型変数）があり、それによって実際に取り扱うデータの型が決まる。

Javaの + 演算子

Javaでは + は数値の加算と、文字列の結合の両方に使われる。

C++のテンプレート

C++では、順序を持つ型に対して max を次のように書くことができる。

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

このテンプレートは、int や char に対して具体化することができる。

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

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

Haskellにおける多相型の関数

Haskellでは、配列の型は要素の型を [ ] で囲んで表す。例えば、 [1, 2, 3] の型は [Int] で ["abc", "def"] の型は [String] になる。

配列の長さを求める関数 length は、要素の型が何であっても適用できる。例えば、 length [1, 2, 3] は3を返し、 length ["abc" "def"] は2を返す。 length の型は、型変数 a を用いて [a]->Int になる。

課題11

Haskellで、 map f x は、配列 x の各要素に関数 f を適用し、その結果を集めて配列にする。例えば、 map abs [-5, 3] は [5, 3] を返し、 map length ["abc", "de"] は [3, 2] を返す。 map の型は、型変数 a と b を使ってどのように表せるか？

【解答例】