ミュータブルはイミュータブルのサブタイプになれないのはなぜか、あるいはその逆も然りか？

FAQ: ミュータブルはイミュータブルのサブタイプになれないのはなぜか、あるいはその逆も然りか？ 2026年9月17日 イミュータビリティ（不変性）について学んだ時のことを覚えている。それはすべてを変えた。 — Denis Defreyne 様々なプログラミング言語のフォーラムで、あるデータ構造のイミュータブル版とミュータブル版を互いのサブタイプまたはスーパータイプとして提供しないのはなぜか、という議論が定期的に持ち上がります。これは不可能ではありませんが、形式的には正しくなく、そうすることで言語が通常提供してくれる型チェックの保証の一部を失うことになります。これがなぜうまくいかないのかを理解するには、サブタイプの定義を思い出す必要があります。すなわち、リスコフの置換原則です。型Sは、型Sの値があらゆるコンテキストで型Tが期待される場所で使用できる場合に、Tのサブタイプとなります。形式的な事柄を扱う場合、この定義は厳密に解釈されます。あらゆるコンテキストとは、ほとんどではなく、文字通りあらゆるコンテキストを意味します。（置換原則をOOクラスのための単なる推奨デザインパターンとして学んだかもしれませんが、形式的には真のサブタイプはこの基準を満たす必要があります。）サブタイピングをサポートする静的型システムは、プログラムを型チェッカーに通すために、これを証明する必要があります。これを説明するために、想像できる最も単純な複合データ構造、すなわち謙虚なペアを取り上げましょう。イミュータブルバージョンの操作は以下の通りです。（cons a d）aとdを含む新しいペアを構築して返します。（car p）ペアpが構築されたときに提供されたaの値を返します。（cdr p）ペアpが構築されたときに提供されたdの値を返します。それだけです！ミュータブルバージョンは2つの新しい操作を追加します。（set-car! p a）ペアp内のaの値を変更します。（set-cdr! p d）ペアp内のdの値を変更します。（新しいコンストラクタもありますが、それは後で扱います。）さて、ミュータブルペアが期待される場所でイミュータブルペアを提供できないことは明白であるはずです。ミュータブルペアを必要とする場所は、おそらくこれらの2つの操作のいずれかを使用しようとするでしょうが、これらはイミュータブルペアでは定義されていません。したがって、型エラーが発生します。しかし、なぜ逆はありえないのでしょうか？イミュータブルペアによって提供されるすべての操作は、ミュータブルペアによっても提供されるため、イミュータブルペアが期待される場所でミュータブルペアを使用できるはずのように思えます。理由はより微妙です。置換原則は、型が提供する操作（メソッド）のセットを超えて、それらの操作に伴う暗黙の契約にまで拡張されます。イミュータブルペアのcarまたはcdrを取得すると、そのペアに対して呼び出すたびに結果が常に同じであるという契約に依存できます。この契約は、例えば、その内容に基づいてペアのハッシュ値を安全に計算し、別のデータ構造に保存し、後で検索するために再計算したときに値が変わらないことを知ることができることを意味します。（言い換えれば、イミュータビリティはハッシュコンシングの前提条件です！）このため、イミュータブルペアとミュータブルペアは完全に異なる型である必要があります：（icons a d）aとdを含む新しいイミュータブルペアを構築して返します。（icar i）イミュータブルペアiが構築されたときに提供されたaの値を返します。（icdr i）イミュータブルペアiが構築されたときに提供されたdの値を返します。（mcons a d）aとdを含む新しいミュータブルペアを構築して返します。（mcar m）ミュータブルペアmが構築されたときに提供されたaの値を返します。（mcdr m）ミュータブルペアmが構築されたときに提供されたdの値を返します。（set-mcar! m a）ミュータブルペアm内のaの値を変更します。（set-mcdr! m d）ミュータブルペアm内のdの値を変更します。iがミュータブルペアであったり、mがイミュータブルペアであったりすると、型エラーになります。反論：しかし、私はそれをミューテートしておらず、私のユースケースではイミュータビリティの契約を気にしません。2種類のペアはサブタイプ階層を形成しないため、完全に別個の型であり、それぞれに操作のセットが定義されている必要があります。幸いなことに、多くの言語はアドホックポリモーフィズムのいずれかのメカニズムを提供しており、それにより、階層を形成しない場合でも、複数の型に対して同じ操作を定義できます。Schemerとしては、動的型付けのコンテキストではこれは悪い考えだと思います。なぜなら、データ型の流れについて行う推論が大幅に複雑になり、したがって正しく行うのがより困難になるからです。実際には、ほとんどの言語は、動的型付けか静的型付けかにかかわらず、このための何らかのメカニズムを提供しています。まず静的型付けの場合を考えてみましょう。WadlerとBlottは、アドホックポリモーフィズムについて形式的に推論し、型チェッカーがそれを実際に健全だと証明できるメカニズムを導入しました。彼らの用語では、ミュータブルペアとイミュータブルペアは異なる型ですが、どちらも上記で定義した元のcarとcdrの操作を持つ共通のペア型クラスに属することができます。ミュータブルペアでは、これらは基盤となるmcarおよびmcdr操作を参照し、イミュータブルペアではicarおよびicdr操作を参照します。これは、ペア型クラスがミュータビリティについて何も言わない新しい契約を定義するため、依然として形式的に健全です。型クラスの適切な実装では、型システムは、入力型の最も緩い定義が何らかのペア（ミュータブルまたはイミュータブル）であるメソッドで、ミューテータを使用しようとするのを阻止します。イミュータブルであると期待してcarおよびcdr操作を使用することを阻止するわけではありませんが、両方の粒度を明示的に選択できます。関数の入力型を、関数が実際に期待する契約に応じて、ミュータブルペア、イミュータブルペア、またはその両方として宣言できます。サブタイプ関係は、一方向のみを許可し、もう一方は許可しません。関数の引数としてイミュータブルペアを許可すると宣言できますが、ミュータブルペアを誤って暗黙的に含める可能性があります。あるいは、その逆の場合、ミュータブルペアを許可するが、イミュータブルペアを誤って含める可能性があります。しかし、どちらの型も一貫して除外することはできません（置換原則に違反することなく）。型クラスに似たものは、いくつかの静的型付け言語で利用可能であり、それらはしばしばインターフェース、トレイト、またはロールと呼ばれます。しかし、実際の型システムは、チェックをどの程度厳密に強制するかについて大きく異なります。動的型付けのオブジェクト指向言語では、これは通常ダックタイピングの形式を取り、複数の異なる型に同じ名前のメソッドを定義し、実行時の型ディスパッチに作業を行わせます。明示的なチェックを追加することで、関数が呼び出されることを許可する前に、ミューテーション操作の有無を確認することで、利点を得ることができます。実際には、これはほとんど行われません。特にミューテータの不在をチェックすることは、動的型付け言語でのアドホックポリモーフィズムが問題を引き起こしやすい理由です。コメントMastodonでこの投稿に返信してコメントを投稿してください。