型理論
型システムの定義は様々だが、プログラミング言語理論の世界では Benjamin C. Pierce の定義が一般に受け入れられている。
(型システムは)プログラムが計算する値の種類に従って句(phrase)を分類することで、そのプログラムがある動作をしないことを証明する扱いやすい文法的手法である。 (Pierce 2002)
換言すれば、型システムはプログラムの値を「型」と呼ばれる集合に分類し(これを「型設定」あるいは「型割り当て」と呼ぶ)、特定のプログラムの動作が不正であることを示す。例えば、"hello" という値を文字列型、5 という値を整数型としたとき、プログラマに "hello" と 5 を加算できないといった制限を課すのである。このような型システムでは、次のプログラム
"hello" + 5
は不正である。もちろん、文字列と整数を加算することを許す型システムもありうる。
型システムの設計と実装は、プログラミング言語そのものと同じ程度に広がりを持った話題である。実際、プログラミング言語の最大の基盤は型システムであるとも言われ、「型システムを正しく設計すれば、言語は自分自身で設計される」と言われている。
型理論の最も顕著な応用は、プログラミング言語のコンパイラでの意味論解析部での型チェックアルゴリズムの構築である。
型理論は自然言語の意味論の理論構築にもよく使われる。以下ではモンタギュー文法の内包論理(型理論と様相論理を折衷したもの)での型を例として説明する。最も基本的な型として e {\displaystyle e} (entity=もの)と t {\displaystyle t} (truth-value=真理値)があり、以下の規則を帰納的に適用して型の集合を定義する。
a {\displaystyle a} と b {\displaystyle b} が型であるとき、 ⟨ a , b ⟩ {\displaystyle \langle a,b\rangle } も型である。
a {\displaystyle a} が型であるとき、 ⟨ s , a ⟩ {\displaystyle \langle s,a\rangle } も型である。ここで、 s {\displaystyle s} は型ではなく、指標(可能世界と時点の組み合わせ)である。