サブ構造型システム

部分構造型システムは、部分構造論理に類似した型システムの一種であり、構造規則の1つ以上が欠落しているか、制御された状況下でのみ許可されている。このようなシステムは、状態の変化を追跡し、無効な状態を禁止することで、ファイル、ロック、メモリなどのシステムリソースへのアクセスを制限できる。 ^[1]^{: 4}

異なるサブ構造型システム

交換、弱化、縮小の構造ルールの一部を破棄することで、いくつかの型システムが登場しました。


型システム	交換	弱体化	収縮	使用
注文済み	—	—	—	導入された順に1回だけ
リニア	許可された	—	—	正確に1回
アフィン	許可された	許可された	—	最大1回^[a]
関連する	許可された	—	許可された	少なくとも1回
普通	許可された	許可された	許可された	恣意的に^[b]

順序型システム

順序付き型は、交換、縮約、弱化が無視される非可換論理に対応する。これは、スタックベースのメモリ割り当てをモデル化するために使用できる（ヒープベースのメモリ割り当てをモデル化するために使用できる線形型とは対照的である）。^[1]^{: 30–31}交換プロパティがない場合、オブジェクトはモデル化されたスタックの先頭にある場合にのみ使用され、その後はポップオフされるため、すべての変数は導入された順序で正確に1回使用される。

線形型システム

線形型は線形論理に対応し、オブジェクトが正確に一度だけ使用されることを保証します。これにより、システムはオブジェクトの使用後に安全に解放することができます。 ^[1]^{: 6}また、リソースが閉じられたり、別の状態に遷移したりした後には使用できないことを保証するソフトウェアインターフェースを設計することもできます。^[2]

Cleanプログラミング言語は、同時実行性、入出力、配列のインプレース更新をサポートするために、一意性型（線形型の変形）を使用します。^[1]^{: 43}

線形型システムでは参照は許可されますが、エイリアスは許可されません。これを強制するために、参照は代入の右側に現れた後はスコープ外となり、同時に存在するオブジェクトへの参照は1つだけであることを保証します。関数への引数として参照を渡すことは代入の一種であり、関数パラメータには関数内部で値が代入されるため、このような参照の使用もスコープ外となることに注意してください。

単一参照特性は、量子状態の複製不可能定理を反映しているため、線形型システムを量子コンピューティング用のプログラミング言語として適したものにしています。圏論の観点から見ると、複製不可能定理とは、状態を複製できる対角関数が存在しないことを意味します。同様に、組合せ論理の観点から見ると、状態を破壊できるKコンビネータは存在しません。ラムダ計算の観点から見ると、変数は項中に1回だけ出現できます。^[3]x

線形型システムは、閉対称モノイド圏の内部言語であり、これは単純型付きラムダ計算がデカルト閉圏の言語であるのとほぼ同様である。より正確には、線形型システムの圏と閉対称モノイド圏の圏の間に関手を構築することができる。 ^[4]

アフィン型システム

アフィン型は線形型の一種で、リソースを破棄（つまり使用しないこと）することを可能にします。これはアフィン論理に対応します。アフィンリソースは最大1回しか使用できませんが、線形リソースは必ず1回だけ使用する必要があります。

リソースの解釈

部分構造型システムが提供する命名法は、言語のリソース管理の側面を特徴付けるのに役立ちます。リソース管理は、割り当てられた各リソースが正確に一度だけ解放されることを保証する言語安全性の側面です。したがって、リソース解釈は、所有権の移転、つまりリソースの解放の責任を負っている「移動」という使用のみを対象とします。

所有権を譲渡しない使用法 (借用) はこの解釈の範囲外ですが、有効期間セマンティクスでは、これらの使用法が割り当てと割り当て解除の間にさらに制限されます。


タイプ	勘当の動き	義務的な動き	移動の定量化	強制可能な関数呼び出しステートマシン
普通	いいえ	いいえ	何度でも	位相的順序付け
アフィン	はい	いいえ	最大1回	注文
リニア	はい	はい	正確に1回	注文と完了

リソースアファイン型

リソース解釈では、アフィン型を複数回使用することはできません。

例として、 Hoare の自動販売機の同じ変種を英語、論理、 Rustで表現できます。

自販機
英語	論理	さび
コインでキャンディーや飲み物を買ったり、スコープ外に出たりできます。	コイン ⊸ キャンディコイン ⊸ ドリンクコイン ⊸ ⊤	fn buy_candy ( _ :コイン) ->キャンディ{キャンディ{} } fn buy_drink ( _ :コイン) ->ドリンク{ドリンク{} }

この例では、 Coinがアフィン型である ( Copy特性を実装していない限りアフィン型です)ということは、同じコインを 2 回使用しようとすることはコンパイラが拒否する権限を持つ無効なプログラムであることを意味します。

let coin = Coin {}; let candy = buy_candy ( coin ); // coin 変数の有効期間はここで終了します。let drink = buy_drink ( coin ); // コンパイル エラー: Copy 特性を持たない移動された変数を使用しています。

言い換えれば、アフィン型システムは型状態パターンを表現できます。関数は異なる型でラップされたオブジェクトを消費し、返すことができます。これは、呼び出し元のコンテキストに型（型状態）として状態を保存する状態マシンにおける状態遷移のように機能します。APIはこれを利用して、関数が正しい順序で呼び出されることを静的に強制できます。

ただし、これは、変数を使い切らずに使用できないという意味ではありません。

// この関数はコインを借りるだけです。アンパサンドは借りることを意味します。fn validate ( _ : & Coin ) -> Result < (), () > { Ok (()) }        // 同じコイン変数は、移動されない限り、無限に使用できます。let coin = Coin { }; loop { validate ( & coin ) ? ; }

Rust が表現できないのは、スコープ外に出ることができないコイン型です。これは線形型を取ることになります。

リソース線形型

リソース解釈では、線形型はアフィン型のように移動できるだけでなく、移動する必要があります。スコープ外になると無効なプログラムになります。

{ //ドロップせずに渡す必要があります。let token = HotPotato {};       // すべてのブランチがこれを廃止するわけではないと仮定します: if ! queue . is_full () { queue . push ( token ); }      // コンパイル エラー: スコープの終了時にドロップできないオブジェクトが保持されます。}

線形型の魅力は、デストラクタが引数を取ったり失敗したりできる通常の関数になる点です。^[5]これにより、例えば、デストラクタ専用の状態を保持する必要がなくなります。関数の依存関係を明示的に渡すことの一般的な利点は、関数の呼び出し順序（デストラクタの順序）が、引数のライフタイムに基づいて静的に検証可能になることです。内部参照と比較すると、Rustのようなライフタイムアノテーションは必要ありません。

手動リソース管理と同様に、実用的な問題として、エラー処理に典型的な早期リターンは、必ず同じクリーンアップを実行しなければならないという点があります。これは、スタックの巻き戻し機能を持つ言語では、すべての関数呼び出しが早期リターンとなる可能性があるため、非常に煩雑になります。しかし、近い類推として、暗黙的に挿入されたデストラクタ呼び出しの意味は、遅延関数呼び出しによって復元できます。^[6]

リソース通常型

リソース解釈においては、通常の型は変数の移動回数を制限しません。C ++（特に非破壊的な移動セマンティクス）はこのカテゴリに該当します。

auto coin = std :: unique_ptr < Coin > (); auto candy = buy_candy ( std :: move ( coin )); auto drink = buy_drink ( std :: move ( coin )); // これは有効な C++ です。

プログラミング言語

以下のプログラミング言語は線形型またはアフィン型をサポートしています^{[引用が必要]}：

ATS
クリーン
イドリス
水銀
クソ*
リニアML
施し
Glasgow Haskellコンパイラ（GHC）9.0.1以上を搭載したHaskell ^[7]
顆粒
さび
Swift 5.9以上^[8]

参照

注記

^ アフィン型システムの説明は、「変数の各出現は最大で 1 回使用される」と言い換えると最もよく理解できます。
^ すべての変数は任意に使用できます。

参考文献

^ abcd Walker, David (2002). 「部分構造型システム」. Pierce, Benjamin C. (編). 型とプログラミング言語の高度なトピック(PDF) . MIT Press. pp. 3– 43. ISBN 0-262-16228-8。
^ Bernardy, Jean-Philippe; Boespflug, Mathieu; Newton, Ryan R; Peyton Jones, Simon ; Spiwack, Arnaud (2017). 「Linear Haskell: 高階多態言語における実用的な線形性」. Proceedings of the ACM on Programming Languages . 2 : 1– 29. arXiv : 1710.09756 . doi :10.1145/3158093. S2CID 9019395.
^ Baez, John C.; Stay, Mike (2010). 「物理学、トポロジー、論理、そして計算：ロゼッタストーン」 Springer (編). New Structures for Physics (PDF) . pp. 95– 174.
^ Ambler, S. (1991). 対称モノイド閉圏における第一階述語論理 (PhD). エディンバラ大学.
^ 「Vale's Vision」 . 2023年12月6日閲覧。パラメータと戻り値を持つデストラクタを可能にする線形型付けの一種であるHigher RAII。
^ 「Go by Example: Defer」。 2023年12月5日閲覧。Deferは、関数呼び出しがプログラム実行の後半で実行されるようにするために使用されます。通常はクリーンアップを目的としています。deferは、例えば他の言語でensureやfinallyが使用されるような場合によく使用されます。
^ “6.4.19. 線形型 — Glasgow Haskell Compiler 9.7.20230513 ユーザーズガイド”. ghc.gitlab.haskell.org . 2023年5月14日閲覧。
^ Hudson @twostraws, Paul. 「コピー不可能な構造体と列挙型 - Swift 5.9から利用可能」Hacking with Swift .

[2] アフィン型システムの説明は、「変数の各出現は最大で 1 回使用される」と言い換えると最もよく理解できます。

[3] すべての変数は任意に使用できます。

[Walker-1] Walker, David (2002). 「部分構造型システム」. Pierce, Benjamin C. (編). 型とプログラミング言語の高度なトピック(PDF) . MIT Press. pp. 3– 43. ISBN 0-262-16228-8。

[BernardyEtAl-4] Bernardy, Jean-Philippe; Boespflug, Mathieu; Newton, Ryan R; Peyton Jones, Simon ; Spiwack, Arnaud (2017). 「Linear Haskell: 高階多態言語における実用的な線形性」. Proceedings of the ACM on Programming Languages . 2 : 1– 29. arXiv : 1710.09756 . doi :10.1145/3158093. S2CID 9019395.

[Baez-5] Baez, John C.; Stay, Mike (2010). 「物理学、トポロジー、論理、そして計算：ロゼッタストーン」 Springer (編). New Structures for Physics (PDF) . pp. 95– 174.

[Ambler-6] Ambler, S. (1991). 対称モノイド閉圏における第一階述語論理 (PhD). エディンバラ大学.

[7] 「Vale's Vision」 . 2023年12月6日閲覧。パラメータと戻り値を持つデストラクタを可能にする線形型付けの一種であるHigher RAII。

[defer-8] 「Go by Example: Defer」。 2023年12月5日閲覧。Deferは、関数呼び出しがプログラム実行の後半で実行されるようにするために使用されます。通常はクリーンアップを目的としています。deferは、例えば他の言語でensureやfinallyが使用されるような場合によく使用されます。

[9] “6.4.19. 線形型 — Glasgow Haskell Compiler 9.7.20230513 ユーザーズガイド”. ghc.gitlab.haskell.org . 2023年5月14日閲覧。

[10] Hudson @twostraws, Paul. 「コピー不可能な構造体と列挙型 - Swift 5.9から利用可能」Hacking with Swift .