体系ガイド · 基礎から応用へ

型検査と型推論を制約から理解する

小さな型規則と制約の解き方から、型検査・型推論・実行時の入力検証が何を判断するかを区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 文法を読めても型が合うとは限らない
  2. 型検査と型推論で分かっている情報を比べる
  3. 型の環境と値の環境を分ける
  4. x + 1から制約を一つずつ作る
  5. 関数の型を使う場合も同じ記号を追う
  6. 統一で一致させられる形を確認する
  7. 型の成功を入力検証や認可へ広げない
  8. 使う場所ごとの変数と一つの変数を区別する
  9. 課題は制約と失敗の理由を示す
  10. この記事をロゲイアに質問する理解を確かめる

文法を読めても型が合うとは限らない

構文解析は、入力が言語の形に合っているかを調べます。型検査は、その構造へ型の規則を当てはめ、操作に必要な値の種類が整合しているかを調べます。説明用に、整数Intと真偽値Boolを区別し、加算はInt二つからIntを返す言語を考えます。この規則なら1 + trueは演算子と二つの式を持つ形にはできても、加算の条件を満たしません。Pythonのboolが整数と関係を持つという実装上の規則を、この説明用の言語へ持ち込まないでください。ここではIntとBoolを異なる型として定義しています。また、先の字句解析・構文解析の実験は整数の式を扱う実装で、真偽値や条件分岐を既に追加したという意味ではありません。型を説明するために、別に拡張した小さな規則を紙の上で追います。対象の構文と型の規則を明示することが、検査の結果を説明する前提です。

型検査と型推論で分かっている情報を比べる

型検査では、例えばxはInt、式の結果はIntであるべきだという情報と、実際の式の規則が矛盾しないかを調べます。型推論では、まだ明記していない型を、式の使われ方から求めます。x + 1なら、加算の規則によりxもIntでなければならず、結果もIntだと分かります。推論は、実行してよさそうな型を統計的に予想することではありません。この教材では、宣言した規則が要求する制約を作り、それを満たす型があるかを求めます。全ての言語で型注釈が不要になるわけでも、どんなプログラムにも便利な一つの型を出せるわけでもありません。どの構文や多相性、再帰的な型を扱うかによって、求められる型と推論の性質は変わります。注釈と推論を併用する方式もあるため、実用言語を「検査だけ」「推論だけ」の二種類へ単純に分けないでください。

型の環境と値の環境を分ける

評価器ではxから実際の整数12を取り出す値の環境を使いました。型検査では、xからIntという型を取り出す型の環境を使います。二つは似た表ですが、目的と中身が違います。x + 1の型を知るために、xが12か100かを具体的に計算する必要はありません。環境にx:Intがあり、右の1が整数リテラルなら、両方がIntで結果もIntという規則を適用できます。一方、xが型の環境にも存在しないなら、未定義の名前として扱うか、新しい型変数を作るかを、その言語の規則で決めます。今回の推論の説明では、未確定の名前の型を記号αとして置く場合を明示して使います。実行時の値を勝手に仮定するのではありません。この区別を保つと、型が分かったことと、値を取得できたことや実行に成功したことを混同しなくなります。

x + 1から制約を一つずつ作る

xの型をα、式全体の型をβと置きます。整数リテラル1にはIntを割り当て、加算の規則から左の型α=Int、右の型Int=Int、結果の型β=Intという制約を作ります。自明な等式を除けば、αとβをIntへ置き換えれば全てを満たします。これが、式を実行せずに型を導ける小さい例です。同じxを条件分岐の条件にも使い、条件はBoolでなければならないとすると、今度はα=Boolという制約も追加されます。この模型ではIntとBoolが異なるので、一つのαへ両方を割り当てる解はありません。拒否の理由は、実際にxへどんな値が入ったかを試したからではなく、同じ束縛に要求される型が矛盾したからです。どの式のどの操作がその制約を生んだかを残すと、診断も「型が違います」より具体的に説明できます。

関数の型を使う場合も同じ記号を追う

ここからは関数を持つ別の単純な型模型を考えます。引数xをそのまま返す関数なら、引数の型をαと置いたとき、戻り値も同じαです。型はα→αと表せます。その関数を整数へ一回適用するなら、α=Intという制約を解きます。ただし、同じ束縛を整数にも真偽値にも使えるかは、多相性の規則によります。一つの型変数を共有する単相の束縛へα=Intとα=Boolを同時に要求すれば矛盾します。一般化した型を各利用で新しく具体化する方式なら、別々の型変数として扱える場面があります。単に「同じ関数だから何にでも使える」と考えるのでなく、どの時点で型変数を共有し、どの時点で新しくするかを述べます。この教材は多相型推論器を実装したという主張ではなく、同じ記号を追う際に必要な区別を説明しています。

統一で一致させられる形を確認する

型変数の等式を解く操作を考えると、α=IntはαをIntへ置くことで解けます。関数型同士を一致させる場合は、引数と戻り値の型をそれぞれ比較します。例えばα→IntとBool→βなら、α=Bool、β=Intが条件です。一方、IntとBoolという異なる具体的な型を同じものへ統一することは、この規則ではできません。有限の単純な型だけを扱う模型では、αがα自身を内側に含む関数型になるような等式も、そのまま無限の型へ広げないように扱います。実際の型体系によって再帰型を認める方法などは異なるため、ここでの制約を全言語の限界とは説明しません。重要なのは、型の形に応じて何を比較し、どの時点で不一致と判断したかを追えることです。結果の型だけでなく、失敗した制約も残すと、入力のどの使い方を改めればよいか考えられます。

型の成功を入力検証や認可へ広げない

xがIntであることから、在庫数として非負であることや、利用者Bがその文書を更新してよいことは分かりません。JSONで届いたageへ型注釈を書くだけで、文字列の18が整数へ変換されたり範囲検査されたりするとは限らないことも、既存の総論で扱っています。外部入力を検証して型付きの内部処理へ渡す境界は別に設計します。また、型が付いた式でも、除数が0になる、ファイルが存在しない、通信が失敗するなど、型体系が対象にしない失敗は残ります。どこまでを型で表現するかは設計の選択ですが、「型が合う」と「どんな条件でも成功する」を同じ意味にはしません。型検査、単体試験、実行時の検証、権限判断を、それぞれの契約に合わせて組み合わせます。何を型へ書かなかったかを説明することも、型の保証を正確に使うために必要です。

使う場所ごとの変数と一つの変数を区別する

推論の変数αは、同じ制約の中で別の都合のよい型へ勝手に読み替えられる記号ではありません。一度Intと等しい条件を得た同じαに、同時にBoolと等しい条件が必要なら、この小例では矛盾です。多相な関数を複数の型で使う仕組みを追加するなら、どの変数を一般化し、どの使用で新しく具体化するかという規則が必要です。型変数があることだけで多相性を実装したとは言えません。この教材の単純な制約と、より広い型体系の機能を分けます。

課題は制約と失敗の理由を示す

課題として、x + 2のxと結果の型を未確定にして、加算の規則から必要な制約を書きます。解答はxの型がInt、結果もIntです。次に同じ単相のxをBoolの条件にも使うと、この模型では解がなくなります。どの行がIntを要求し、どの行がBoolを要求したかを示してください。最後にα→IntとBool→βを一致させる課題では、α=Bool、β=Intと置けば両方の形がそろいます。この答えを得ても、実際に関数を呼び出したことにはなりません。型の環境と値の環境を別々に描いて説明します。追加の課題として、型がIntでもアプリで拒否すべき入力を一つ挙げてください。負の在庫数などは、その値域を型で表していないなら別の条件として検査します。制約を追い、型の保証と残る責務を分けて説明できることが、この教材の到達点です。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 19

学習コースから次を選ぶ