プログラミング言語論：機械語から型システムとパラダイムまで
対象読者: 本テーマ第 1〜2 章（CPU の命令符号化、OS の役割）を読み、何らかのプログラミング言語で関数を書いた経験のある人。帰納法による証明は仮定しますが、型理論や意味論は仮定しません。
前提となる記事:OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か
0. この記事の要点
Section titled “0. この記事の要点”プログラムを書くとき、私たちは「この書き方で本当に思ったとおり動くのか」「間違いを実行する前に見つけられないか」と考えます。この記事は、その問いに答えるために、プログラムの意味を小さな言語で厳密に決め、「型が付けば途中で止まらない」ことを証明する道筋を追います。読み終えると、コンパイラと型検査が何を保証し、何を保証できないのか、関数型とオブジェクト指向がなぜ違う形をしているのかを、理由つきで説明できるようになります。
- CPU が実行できるのは固定長のビット列（機械語）だけです。アセンブリ言語はそのビット列に人間が読める名前を付けただけのもので、高級言語との間には「意味を保つ翻訳」という質的な断絶があります。
- コンパイラとインタプリタの違いは、言語の性質ではなく実装戦略の違いです。同じ言語に両方の処理系を作れます。区別が本質的に効くのは、エラーを実行前に見つけるか実行時に見つけるかという点です。
- 型システムの価値は「進行定理」（型の付いた式は値になるか、まだ先へ進めるか）と「保存定理」（1 ステップ進んでも型は変わらない）の 2 本に集約されます。この 2 つから、型の付いたプログラムは実行の途中で行き詰まらないという保証（型健全性）が従います。
- 静的型検査は健全である限り必ず不完全です。これは実装の未熟さではなく、停止性問題の決定不能性から導かれる原理的な限界です。
- 関数型プログラミングの中心概念は参照透過性であり、これは「同じ式は何度評価しても同じ値になる」という定理を成立させます。オブジェクト指向の中心概念は動的ディスパッチと部分型であり、関数型の部分型規則は引数について反変（部分型の向きが引数の側では逆になること）になります。
1. 動機：なぜ「言語」が必要なのか
Section titled “1. 動機：なぜ「言語」が必要なのか”コンピュータアーキテクチャと CPU の構造 の 定義 6.1［コンピュータアーキテクチャとCPUの構造］ で見たとおり、CPU が理解するのは 32 ビットや 64 ビットのビット列だけです。1940 年代の計算機は、実際にこのビット列を人間が紙に書き、スイッチやパンチカードで入力していました。
この作業は 2 つの意味で耐えがたいものでした。第 1 に、間違えます。1 ビット違えば別の命令になり、しかも大抵の場合それも「有効な」命令なので、計算機は何事もなかったかのように誤った計算を続けます。第 2 に、書き換えられません。プログラムの真ん中に命令を 1 つ挿入すると、それ以降のすべての分岐先アドレスがずれます。
そこで生まれた発想が「記号で書いて、機械に翻訳させる」ことでした。ここには 1 つの飛躍があります。翻訳をするのもまたプログラムだ、という自己言及です。1952 年に Grace Hopper が A-0 システムを、1957 年に IBM の John Backus のチームが FORTRAN のコンパイラを完成させたとき、多くの技術者は「機械が生成したコードが人間の手書きに勝てるはずがない」と考えていました。今日、その懐疑は完全に覆っています。
しかし翻訳を機械に任せた瞬間、新しい問いが生まれます。翻訳が正しいとは、どういうことか。これに答えるには、まず「プログラムの意味」を数学的に定義しなければなりません。この記事はその定義から始めて、型システムとパラダイムの設計原理までを見ていきます。
2. 抽象度の階段：機械語とアセンブリ言語
Section titled “2. 抽象度の階段：機械語とアセンブリ言語”2.1. 機械語は命令の符号化である
Section titled “2.1. 機械語は命令の符号化である”RISC-V の 32 ビット命令 addi（即値加算）を例に取ります。どの命令名がどのビット並びに対応するかを定める規約が 定義 8.1［コンピュータアーキテクチャとCPUの構造］ の命令セットアーキテクチャです。この命令は I 形式と呼ばれる並びを持ち、上位から順に 12 ビットの即値、5 ビットのソースレジスタ番号 rs1、3 ビットの funct3、5 ビットのデスティネーションレジスタ番号 rd、7 ビットのオペコードが並びます。
例 2.1（addi 命令の符号化を手で計算する）
「レジスタ a0 の値に 1 を足して a0 に戻す」という命令を符号化します。RISC-V では a0 はレジスタ番号 10、すなわち 2 進で 01010 です。addi のオペコードは 0010011、funct3 は 000 です。即値 1 は 12 ビットで 000000000001 です。
これを上位から連結します。
000000000001 01010 000 01010 0010011 即値=1 rs1=10 funct3 rd=10 opcode区切りを外して 4 ビットずつ切り直すと 0000 0000 0001 0101 0000 0101 0001 0011、16 進で 0x00150513 です。同じ手順で add a0, a0, a1（R 形式。R 形式の符号化は 例 8.2［コンピュータアーキテクチャとCPUの構造］ でも計算しています）は 0x00B50533、関数からの復帰命令 ret（実体は jalr x0, 0(x1)）は 0x00008067 になります。
つまり addi a0, a0, 1 というアセンブリの 1 行は、0x00150513 という 32 ビット整数に1 対 1 で対応する別表記にすぎません。
この対応が 1 対 1 であることが決定的です。アセンブラの仕事は、命令名をオペコードの表で引き、レジスタ名を番号に直し、ラベルをアドレスに解決してビットを詰めることだけです。新しい概念を導入しません。
2.2. 高級言語は何を追加したのか
Section titled “2.2. 高級言語は何を追加したのか”一方、C 言語の 1 行はしばしば複数の命令に展開されます。
int add1(int x) { return x + 1; }これを RISC-V 向けに最適化付きでコンパイルすると、次の 2 命令になります。
add1: addi a0, a0, 1 # 0x00150513 ret # 0x00008067ここで起きていることは、単なる記号の置換ではありません。「引数 x は第 1 引数レジスタ a0 に入っている」「返り値も a0 に置く」という呼び出し規約の知識、「int は 32 ビット 2 の補数である」という型と表現の対応、そして「局所変数はレジスタに割り付けてよい」という最適化の判断が使われています。高級言語が追加したのは、こうした決定を人間の手から取り上げる抽象化です。
3. コンパイラとインタプリタ
Section titled “3. コンパイラとインタプリタ”言語 （原始言語）、言語 （目的言語）、言語 （実装言語）を考えます。
コンパイラとは、 で書かれたプログラム であって、 のプログラム を入力すると のプログラム を出力し、任意の入力 について を に適用した結果と を に適用した結果が一致するものをいいます。
インタプリタとは、 で書かれたプログラム であって、 のプログラム と入力 の組を受け取り、 を に適用した結果を直接出力するものをいいます。
この定義から読み取ってほしいのは、コンパイラかインタプリタかは言語の属性ではないということです。どちらも「 の意味を実現する」という同じ目標を、出力の形を変えて達成しているだけです。実際、C++ にはインタプリタ（Cling など）があり、Python には機械語を生成する処理系（PyPy の JIT）があります。「Python はインタプリタ言語である」という言い方は、正確には「Python の主要な実装 CPython がバイトコードインタプリタである」という意味です。
| 観点 | コンパイル方式 | インタプリタ方式 |
|---|---|---|
| 誤りの発見時期 | 翻訳時（実行前）に構文・型の誤りを検出 | 該当行に到達したときに検出 |
| 実行速度 | 最適化を翻訳時に済ませられるため速い | 命令ごとの解釈オーバーヘッドが載る |
| 起動の速さ | 翻訳の時間が先に必要 | すぐ動く |
| 移植性 | 目的機械ごとに翻訳し直す | インタプリタさえあれば同じコードが動く |
| 実行時情報の活用 | 静的にわかる範囲に限られる | 実際に通った経路に基づく最適化ができる |
最後の行が JIT（実行時コンパイル）の存在理由です。「この呼び出し箇所には過去 1 万回すべて同じ型のオブジェクトが来た」という事実は静的にはわからず、実行時にしか観測できません。JIT はこの観測に賭けて特化コードを生成し、賭けが外れたら解釈実行へ戻ります。コンパイルとインタプリタは対立ではなく、情報が使える時点の違いだと捉えるのが正確です。
4. プログラムの意味を厳密に述べる
Section titled “4. プログラムの意味を厳密に述べる”「翻訳が意味を保つ」と言うためには意味の定義が要ります。ここでは最も広く使われる操作的意味論、すなわち「1 ステップずつどう書き換わるか」で意味を与える方法を、極小の言語で実演します。
次の定義は、真偽値と自然数だけを扱う言語を決め、「どの式がどの式に書き換わるか」を規則の一覧で与えます。規則は、横線の上に前提、下に結論を書く形で並びます。上が成り立つならば下が成り立つ、と読みます。「最小の関係」とは、これらの規則から導けるものだけを含む関係のことです。以後の定理は、この規則の表だけを根拠に証明されます。
項 を次の文法で定める。
数値 と値 を次で定める。
1 ステップ簡約関係 を、次の規則で生成される最小の関係とする。
どの規則も適用できない項を正規形という。値でない正規形を行き詰まり項（stuck term）という。
行き詰まりが、この形式化における「実行時エラー」の定義です。たとえば は、E-PredZero も E-PredSucc も形が合わず、E-Pred を使おうにも が簡約できないため、どの規則も適用できません。しかも値でもありません。実機なら「Boolean に対して pred は使えません」という例外が飛ぶ場面です。
例 4.2（評価列を最後まで追う）
項 を簡約します。使った規則を各行に添えます。
は値なので、ここで停止します。注意すべきは、2 行目で「まず条件式を最後まで評価する」と決めているのは E-If ただ 1 つの規則だという点です。この規則がなければ、条件が未評価のまま分岐する意味論も書けてしまいます。意味論とは、こうした選択を明示的に固定する作業です。
この規則集合はそのまま実行できるプログラムに書き写せます。以下は言語 L の完全なインタプリタです。
def is_numeric(t): if t == ("zero",): return True if t[0] == "succ": return is_numeric(t[1]) return False
class Stuck(Exception): pass
def step(t): """項 t を 1 ステップ簡約する。規則が適用できなければ Stuck を送出する。""" k = t[0] if k == "if": _, t1, t2, t3 = t if t1 == ("true",): return t2 # E-IfTrue if t1 == ("false",): return t3 # E-IfFalse return ("if", step(t1), t2, t3) # E-If if k == "succ": return ("succ", step(t[1])) # E-Succ if k == "pred": u = t[1] if u == ("zero",): return ("zero",) # E-PredZero if u[0] == "succ" and is_numeric(u): return u[1] # E-PredSucc return ("pred", step(u)) # E-Pred if k == "iszero": u = t[1] if u == ("zero",): return ("true",) # E-IszeroZero if u[0] == "succ" and is_numeric(u): return ("false",) # E-IszeroSucc return ("iszero", step(u)) # E-Iszero raise Stuck(t)
def evaluate(t): while True: try: t = step(t) except Stuck: return t # 正規形に到達
term = ("if", ("iszero", ("pred", ("succ", ("zero",)))), ("zero",), ("succ", ("zero",)))print(evaluate(term)) # ('zero',)print(evaluate(("pred", ("false",)))) # ('pred', ('false',)) ← 行き詰まり次の補題は、後の決定性の証明で使う下準備です。「値はこれ以上書き換わらない」という当たり前に見える事実を、規則の表と照らして確かめておきます。
証明（補題 4.3）
(1) を の構造に関する帰納法で示します。 のとき、定義 4.1 の規則のうち左辺が という形の項であるものは存在しません（E-PredZero の左辺は であって ではありません）。よって簡約できません。
のとき、左辺が で始まる規則は E-Succ だけです。E-Succ を使うには前提 が必要ですが、帰納法の仮定より は簡約できないので、この前提は満たせません。よって も簡約できません。
(2) 値は 、、数値のいずれかです。 と を左辺に持つ規則は存在せず（E-IfTrue の左辺は で始まる項です）、数値については (1) が示しています。
次の定理は、どの式にも次の一手が高々 1 つしかないことを言います。証明は、式の形ごとに「適用できる規則は 1 つだけ」と確かめる場合分けです。「導出に関する帰納法」とは、ある 1 ステップの書き換えを規則から組み立てた手順の、前提にあたる部分から順に仮定を使う帰納法のことです。
証明（定理 4.4）
の導出に関する帰納法で示します。 の形で場合分けします。
のとき。 ならば適用できるのは E-IfTrue だけです。E-If を使うには前提 が要りますが、補題 4.3 (2) より は簡約できないので E-If は使えません。よって です。 も同様です。 が でも でもなければ E-IfTrue も E-IfFalse も形が合わないので、両方の簡約は E-If によるもので、それぞれ 、 を前提とします。帰納法の仮定より となり、 が従います。
のとき。 ならば E-PredZero のみが適用でき（E-Pred の前提 は 補題 4.3 (1) により成立しない）、 です。（ は数値）ならば E-PredSucc が適用でき、E-Pred は前提 を要求しますが 補題 4.3 (1) よりこれは成立しません。よって です。ここで補題 (1) が本質的に効いています。 が の形でも が数値でない場合は、E-PredSucc の形が合わないので両方 E-Pred であり、帰納法の仮定で決まります。 がそれ以外の形のときも E-Pred のみです。
の場合は と完全に同じ議論です。 のときは E-Succ のみが適用でき、帰納法の仮定から従います。 が値のときは 補題 4.3 より簡約できないので、仮定に反し、この場合は起こりません。
決定性は「同じプログラムは何度動かしても同じ結果になる」ことの形式的な内容です。並行実行や乱数を導入するとこの定理は成り立たなくなり、その瞬間にデバッグの難しさが跳ね上がります（並行実行のときに順序を制御して結果を定める仕組みについては 定義 6.1［OS の役割］ を参照してください）。
5. 型：静的型付けと動的型付け
Section titled “5. 型：静的型付けと動的型付け”定義 4.1 の直後で見たように、L には行き詰まる項があります。型システムとは、実行する前に、行き詰まる項の一部を排除する仕組みです。
T-If が と に同じ を要求している点に注目してください。この 1 箇所が、後で見る型システムの不完全性の主要な原因になります。
証明（補題 5.2）
(1) 値は 、、数値のいずれかです。 が数値だと仮定すると、 なら型を与える規則は T-Zero だけなので しか導けず、 に矛盾します。 なら型を与える規則は T-Succ だけで、やはり結論は です。よって は数値ではなく、 か です。
(2) 同様に、 なら T-True により しか導けず、 でも T-False により しか導けません。いずれも仮定 に矛盾するので、 は数値です。
進行定理の狙いは、「型が付けば、行き詰まる場面にそもそも出会わない」ことの片方の半分を示すことです。方針は、型の付いた式について、値でなければ必ず規則が 1 つ適用できることを、型付けの最後の規則ごとに確かめます。
証明（定理 5.3）
の導出に関する帰納法で示します。
T-True、T-False、T-Zero が最後に使われた場合、 はそれぞれ 、、 であり、いずれも値です。
T-If の場合、 で です。帰納法の仮定より、 は値であるか簡約できます。簡約できるなら E-If により 全体も簡約できます。 が値なら、 と 補題 5.2 (1) より は か であり、E-IfTrue または E-IfFalse が適用できます。
T-Succ の場合、 で です。帰納法の仮定より は値か簡約可能です。簡約可能なら E-Succ で も簡約できます。値なら 補題 5.2 (2) より は数値なので、 自体が数値、すなわち値です。
T-Pred の場合、 で です。 が簡約可能なら E-Pred を使います。 が値なら 補題 5.2 (2) より数値であり、数値は か の形です。前者は E-PredZero、後者は E-PredSucc が適用できます。この 2 通りで数値を尽くしていることが要点で、 のような場合は が導けないため、そもそもこの場合分けに現れません。
T-Iszero の場合も同じ構造で、E-IszeroZero と E-IszeroSucc が数値のすべての形を覆っています。
保存定理はもう片方の半分です。1 ステップ進んだ後の式にも型が付いていれば、進行定理をもう一度使えます。証明は簡約規則を 1 つずつ取り上げ、それぞれで型が変わらないことを確かめる作業です。
証明（定理 5.4）
の導出に関する帰納法で、規則ごとに確かめます。以下、型付け規則は形で一意に決まるので、 の形から最後に使われた型付け規則を逆に読み取れます（反転補題）。
E-IfTrue：。 の導出は T-If で終わるので、前提として があります。よって です。E-IfFalse も同様に が前提にあります。
E-If： で前提は 。T-If の前提から 、、。帰納法の仮定より 。この 3 つに T-If を適用して を得ます。
E-Succ：T-Succ より かつ 。帰納法の仮定より 、T-Succ を適用して 。
E-PredZero：。T-Pred より で、T-Zero より です。
E-PredSucc：。T-Pred より かつ 。これを導けるのは T-Succ だけなので、その前提として があります。
E-Pred：T-Pred の前提 に帰納法の仮定を適用し、T-Pred を再適用します。
E-IszeroZero：。T-Iszero より で、T-True より 。E-IszeroSucc も同じく T-False を使います。
E-Iszero：T-Iszero の前提に帰納法の仮定を適用し、T-Iszero を再適用します。以上ですべての簡約規則を尽くしました。
証明（系 5.5）
「進行 + 保存 = 健全性」というこの 2 段構えは、Wright と Felleisen が 1994 年に定式化して以来、型システムを設計するときの標準的な証明義務になっています。新しい言語機能を足したら、この 2 つの定理を証明し直す。それが「型システムを設計する」ことの実質です。
5.1. 静的型検査は必ず不完全である
Section titled “5.1. 静的型検査は必ず不完全である”系 5.5 で保証されるのは片側だけです。型が付けば安全ですが、逆は成り立ちません。 は E-IfTrue で に簡約されて何の問題もなく終わりますが、T-If が枝の型の一致を要求するため型が付きません。これは L という玩具言語の欠陥でしょうか。違います。
をチューリング完全なプログラミング言語とし、 を「実行しても型エラーで停止しないプログラム」全体の集合とする。 が決定可能（あるプログラムが に属するか否かを必ず有限時間で判定できる）かつ健全（）ならば、 である。すなわち、安全であるのに が受理しないプログラムが必ず存在する。
証明（定理 5.6）
まず が決定不能であることを、停止性問題からの帰着で示します。チューリング機械 と入力 の組が与えられたとき、次のプログラム を機械的に構成します。
p(M, w) の本体: M を w 上でシミュレートする # 停止しないかもしれない 1 + true を評価する # ここに到達すれば必ず型エラーはチューリング完全なので のシミュレータを で書けます。このとき、 が型エラーを起こすのは、シミュレーションが停止して 2 行目に到達したとき、かつそのときに限ります。よって
が成り立ちます。 が決定可能だとすると、この対応によって停止性問題も決定可能になり、チューリングの結果に矛盾します。よって は決定不能です。
さて は決定可能、 は決定不能なので です。仮定より ですから、 が従います。 の元が、安全なのに受理されないプログラムです。
5.2. 静的と動的の比較
Section titled “5.2. 静的と動的の比較”| 観点 | 静的型付け（Java, OCaml, Rust, TypeScript） | 動的型付け（Python, Ruby, JavaScript） |
|---|---|---|
| 誤りの検出 | 実行前。到達しない経路の誤りも見つかる | 実行時。そのコードを通るテストが必要 |
| 拒否されるプログラム | 安全でも型が付かないものを拒否する | 拒否しない。動かして初めて分かる |
| 実行性能 | 型が確定するので値の表現を最適化できる | 実行時に型タグを検査する分の負荷がある |
| 保守性 | 型が機械検査される仕様書として働く | 仕様は文書とテストに依存する |
| 記述の柔軟さ | 型を通すための記述が必要になることがある | 試作や探索的なコードを短く書ける |
| リファクタリング | 型検査器が呼び出し側の修正漏れを指摘する | 漏れは実行して初めて露見する |
例 5.7（型推論を最後まで計算する）
静的型付けの「型を書く手間」は、型推論でかなり削れます。関数 twice（引数 f を 2 回適用する）の型を、制約を集めて解く方法で求めます。
の型を型変数 、 の型を と置きます。
- 内側の適用 が型付くには、 は を受け取る関数でなければなりません。結果の型を と置くと、制約 が出ます。
- 外側の適用 では、 は を受け取ります。結果を と置くと、制約 が出ます。
- 2 つの制約から 。関数型の等式は引数どうし・結果どうしの等式に分解できるので、 かつ を得ます。
- したがって 、 です。
全体の型は となり、 に制約が残っていないので全称量化して が得られます。型注釈を 1 つも書かずに、最も一般的な型が一意に決まりました。この手続きが Hindley–Milner 型推論であり、OCaml や Haskell、そして Rust の局所的な型推論の基礎になっています。
6. パラダイム：関数型とオブジェクト指向
Section titled “6. パラダイム：関数型とオブジェクト指向”6.1. 関数型：参照透過性が定理を生む
Section titled “6.1. 関数型：参照透過性が定理を生む”関数型プログラミングの理論的な母体は 1930 年代の 計算です。項は変数 、抽象 、適用 の 3 つだけで、計算規則も 簡約 の 1 つだけです。この極小の体系がチューリング機械と同じ計算能力を持ちます。
証明は Tait と Martin-Löf による平行簡約を使う方法が標準で、Barendregt の教科書の第 3 章に完全な形が載っています。ここでは主張の意味だけ押さえてください。定理 4.4 が「簡約の順序が 1 通りしかない」ことを言っていたのに対し、Church–Rosser は「順序は複数あってよいが、結果は合流する」ことを言っています。だから正規形は高々 1 つに定まり、式のどの部分から評価しても最終結果は変わりません。並列実行や遅延評価が意味を壊さない根拠がここにあります。
評価関係が決定的であり、式の評価結果が自由変数への束縛のみに依存し、評価が計算機の状態（変数の書き換え、入出力、時刻など）を変化させないとき、その言語は参照透過であるという。
参照透過な言語において、式 が環境 のもとで値 に評価されるとする。 の 2 度の出現がいずれも環境 のもとにある（すなわち の自由変数がどちらの出現でも同じ束縛を受ける）とき、その 2 度の出現をどちらも で置き換えても、全体の評価結果は変わらない。
証明（命題 6.4）
の 1 度目の評価が値 を返したとします。定義 6.3 より評価は状態を変化させないので、1 度目の評価の前後で環境 は同一です。仮定より 2 度目の出現も の自由変数に同じ束縛を与える位置にあるので、2 度目の評価も同じ環境 のもとで行われます。同じ環境・同じ式に対する評価は、決定性の仮定より同じ値を返します。よって 2 度目の結果も です。両方の出現がいずれも に等しい値へ評価される以上、それらを で置き換えても全体の値は変わりません。
この命題が、 を 1 度だけ計算して使い回す最適化（共通部分式除去）を正当化します。逆に、参照透過性がないとこの最適化は不正になります。
例 6.5（副作用があると最適化が壊れる）
次の Python コードで、f() + f() を「共通部分式」とみなして 1 回の呼び出しにまとめると結果が変わります。
counter = 0
def f(): global counter counter += 1 return counter
print(f() + f()) # 1 + 2 = 3
counter = 0a = f()print(a + a) # 1 + 1 = 2出力は 3 と 2 で一致しません。定義 6.3 の「評価が状態を変化させない」という仮定が破れているため、命題 6.4 の証明の第 1 段（環境が同一であること）が成立しないからです。関数型言語が副作用を型で隔離したり禁止したりするのは、禁欲のためではなく、この種の等式変形を安全に使うためです。
6.2. オブジェクト指向：動的ディスパッチと部分型
Section titled “6.2. オブジェクト指向：動的ディスパッチと部分型”オブジェクト指向の中心は継承ではなく、呼ぶべきコードを実行時に受け手が決めるという動的ディスパッチです。その正体は、データと関数ポインタを束ねたレコードにすぎません。
def make_circle(r): return {"area": lambda: 3.14159 * r * r, "name": lambda: "円"}
def make_square(s): return {"area": lambda: s * s, "name": lambda: "正方形"}
shapes = [make_circle(1.0), make_square(2.0)]for sh in shapes: print(sh["name"](), sh["area"]()) # 円 3.14159 / 正方形 4.0sh["area"] がどの関数を指すかは、sh の中身を見るまで決まりません。機械語のレベルでは、これは「関数ポインタをメモリから読んで、そのアドレスへ間接ジャンプする」という 2 命令に落ちます（C++ や Java の仮想関数表がまさにこの構造です）。分岐先が静的に決まらないため、コンピュータアーキテクチャと CPU の構造 で扱った分岐予測が効きにくく、これが仮想呼び出しのコストの正体です（予測が外れるとパイプラインの利得が失われます。命題 7.2［コンピュータアーキテクチャとCPUの構造］ を参照）。
これが Liskov の置換原則の型理論版です。では関数型どうしの部分型関係はどうなるでしょうか。
直感は次のとおりです。「猫を受け取る関数」を「動物を受け取る関数」の代わりに使うと、犬が渡されたときに困ります。逆に、「動物を受け取る関数」は猫が渡されても困りません。そのため、引数の側では部分型の向きが逆になります。下の図は、この向きの違いを並べたものです。
証明（命題 6.7）
を型 の関数とし、これを が期待される場所で使ったとします。定義 6.6 の要求は「その使い方で型エラーが起きない」ことです。
引数について。呼び出し側は だと信じているので、 型の任意の値を渡してきます。 が受け取れるのは 型の値なので、 型の値がすべて 型として通用しなければなりません。これはまさに です。
結果について。 は 型の値を返します。呼び出し側はそれを 型として扱うので、 型の値がすべて 型として通用する必要があります。これが です。
以上より、この 2 条件のもとで の使用は型エラーを起こしません。
例 6.8（共変にすると壊れる：Java の配列）
Java は配列を共変にしています。すなわち String が Object の部分型なら String[] も Object[] の部分型として扱われます。命題 6.7 の観点で言えば、配列への書き込みは引数の位置（Object を受け取る操作）なので、反変でなければ健全になりません。共変にした結果、次のコードはコンパイルを通ってしまいます。
String[] names = new String[1];Object[] objs = names; // 共変なので許されるobjs[0] = Integer.valueOf(42); // コンパイル時は Object[] なので通るしかし実行すると 3 行目で ArrayStoreException が送出されます。これは 系 5.5 でいう型健全性が破れている状態で、Java は実行時に配列の要素型を検査する動的チェックを追加して穴を塞いでいます。ジェネリクス（List<String> と List<Object>）が非変に設計されているのは、同じ失敗を繰り返さないためです。
6.3. どちらが「正しい」のか
Section titled “6.3. どちらが「正しい」のか”両者は同じ問題の異なる面を最適化しています。「図形の種類」と「図形に対する操作」からなる 2 次元の表を考えると、拡張の方向が直交していることが見えます。
| 新しいデータ（三角形を追加） | 新しい操作（周長を追加） | |
|---|---|---|
| 関数型（代数的データ型 + パターンマッチ） | 既存の全関数に分岐を書き足す必要がある | 新しい関数を 1 つ足すだけで済む |
| オブジェクト指向（クラス + 動的ディスパッチ） | 新しいクラスを 1 つ足すだけで済む | 既存の全クラスにメソッドを足す必要がある |
これが Wadler の言う「式問題」です。片方が楽な方向は、もう片方では苦しい方向になります。近年の言語（Scala、Rust、Swift、Kotlin）が代数的データ型とトレイト・プロトコルの両方を備えているのは、対象の性質に応じて拡張しやすい側を選べるようにするためです。パラダイムは信条ではなく、拡張の軸をどちらに取るかという設計判断だと考えるのがよいでしょう。
演習 7.2標準
言語 L の項で、型が付かないにもかかわらず、簡約すると値に到達する（行き詰まらない）ものを 1 つ挙げ、両方を確認してください。この現象が 系 5.5 と矛盾しない理由も述べてください。
解答
を取ります。
型が付かないこと： に型を与えうる規則は T-If だけで、その前提は と を同じ について要求します。 に型を与える規則は T-Zero だけなので 、 に型を与える規則は T-False だけなので です。 なので両立せず、 には型が付きません。
値に到達すること：E-If の前提を E-IszeroZero で導いて 、次に E-IfTrue で 。 は値です。
矛盾しない理由：系 5.5 は「型が付く 行き詰まらない」という一方向の含意であり、その逆「行き詰まらない 型が付く」は主張していません。そして 定理 5.6 が示すとおり、逆向きが成り立つ決定可能な型システムは（チューリング完全な言語では）そもそも存在しません。 の枝は決して実行されませんが、型検査器は「どちらの枝も実行されうる」という保守的な前提で判断します。
演習 7.3標準
定理 4.4 の証明で、 の場合を、補題 4.3 をどこで使うかを明示しながら完全に書いてください。
解答
の形で場合分けします。
(a) のとき。適用候補は E-IszeroZero と E-Iszero です。E-Iszero を使うには前提 が必要ですが、 は数値なので 補題 4.3 (1) よりこの前提は成立しません。よって適用できるのは E-IszeroZero だけで、 です。
(b) （ は数値）のとき。 自身が数値なので、同じく 補題 4.3 (1) より E-Iszero の前提は成立しません。適用できるのは E-IszeroSucc だけで、 です。
(c) で が数値でないとき。E-IszeroSucc は右辺の が数値であることを要求するので形が合いません。E-IszeroZero も形が合いません。よって両方の簡約は E-Iszero によるもので、それぞれ前提 、 を持ちます。帰納法の仮定より 、したがって です。
(d) が上のいずれでもないとき（、、あるいは や で始まる項）。E-IszeroZero も E-IszeroSucc も形が合わないので、両方 E-Iszero であり、(c) と同じ議論で を得ます。なお が や の場合は 補題 4.3 (2) より E-Iszero の前提も成立せず、そもそも は簡約できないため、 という仮定のもとでは起こりません。
関数型の部分型規則を「引数についても共変」、すなわち かつ ならば と定めたとします。型 Cat と Dog がともに Animal の部分型であるとして、この規則のもとで型検査を通るのに実行時に破綻するプログラムを構成してください。
解答
関数 を「猫を受け取り、その猫の爪を研がせる」ものとします。すなわち で、本体では Cat にしかない操作（たとえば「爪を研ぐ」）を呼びます。
いま仮の共変規則を使うと、 かつ より
が導けます。よって 定義 6.6 の包摂規則により、 を型 の値として使えます。
そこで、 を引数に取る高階関数 に を渡し、 の中で の値を適用します。 なのでこの適用は型検査を通ります。しかし実行時に の本体は渡された値に「爪を研ぐ」を要求し、Dog にはその操作がないので破綻します。型が付いたのに行き詰まったので、系 5.5 の型健全性が失われています。
正しい規則 命題 6.7 では、 を導くには が必要ですが、これは成り立たないため、最初の一歩が塞がれます。例 6.8 の Java 配列は、まさにこの反変性を破った実例です。
- Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002 — 第 3 章（算術式の意味論）、第 8 章（型付き算術式、進行定理と保存定理）、第 15 章（部分型）。この記事の言語 L と定理の骨格はこの本の構成に沿っています。
- Robert Harper, Practical Foundations for Programming Languages, 2nd ed., Cambridge University Press, 2016 — 構造的操作的意味論と型安全性の一般的な扱い。
- A. Wright and M. Felleisen, “A Syntactic Approach to Type Soundness”, Information and Computation 115 (1994), 38–94 — 進行と保存による型健全性証明の定式化。
- H. P. Barendregt, The Lambda Calculus: Its Syntax and Semantics, revised ed., North-Holland, 1984 — 第 3 章に Church–Rosser の定理の完全な証明。
- A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Addison-Wesley, 2006 — 字句解析から最適化・コード生成までの標準的な教科書。
- B. H. Liskov and J. M. Wing, “A Behavioral Notion of Subtyping”, ACM Transactions on Programming Languages and Systems 16(6) (1994), 1811–1841 — 置換原則の厳密な定式化。
- RISC-V International, The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA — https://riscv.org/technical/specifications/ 命令形式と符号化の一次資料。
執筆: Claude Code（Sonnet 5.5）・監査 3 回（Claude Code）・最終 2026-10-12
この記事の誤りを報告する ・運営: 夢現技研合同会社 ・料金 ・利用条件 ・特定商取引法に基づく表記
© 2026 夢現技研合同会社 ・コード例は MIT ライセンスです。