永遠に書きあがりそうもないやつ

2020-01-12

何かの参考とかにしたらダメです。書き始めて半年経つんだけどこっからどう直したらいいんだか（何をゴールにしたらいいのか）わからない。。

追記：合流性とか強正規化可能性とか停止性とか、全部チューリング不完全で、事前の静的解析で使うメモリの最大量が確定できる、とかそういう風に読み替えられる人を増やしたいのです、数式の添え字とΣと∫にびびらない人を増やしたいようなもので

数理論理学の一分野である証明論から成長した、数理論理学と理論計算機科学の境界領域の研究領域である型理論(type theory)は、大規模なプログラムの内的な整合性のチェックを行うための方法論を必要とする情報処理技術の分野で関心を集めている。

　そもそも「型」(type)とは何か。プログラミング言語は一般的にはレコードや関数といったプログラムを構成する「値」(value)の定義をする道具である(*1)。その言語のコンパイラ作成者はこれらレコードや関数などの値、もしくは第一級の対象(first-class object)の種類を区別する型システム(type system)を必要とする。抽象代数学の観点からすると、「型」とはこれらの値もしくは第一級の対象が属する高階の対象(higher order object)としての空間(space)ないし代数系(algebraic system)で、型システムはそれら「型」とそれら相互の関係(relation)つまり型のなす順序構造(order structure)ないし束構造(lattice structrure)であるといえる。

　プログラムを構成する値すべてに型が付くためには、曖昧でない(*2)こと、自己矛盾していないこと、悪循環を含まないこと、それぞれの値の内容をチェックするために無限の時間を要しない(*3)ことなどが必要で、これらを満たすなら、プログラムは有限時間で実行を終え、停止する。手続き型言語では無限ループ、型無しラムダ計算では無限再帰によって型付け不能なプログラムを書くことができるが、型理論はこれらのチューリング完全な計算機を意図しない停止しないプログラムから守る装甲でもあり、再帰やメモリ確保で好き勝手をさせないための拘束具でもある。型が付くプログラムには単に停止するというだけでなく、可能な実行経路（訂正：経路→方法）のすべてで同じ結果を出すなど種々の良い性質がある。

1)この定義は現実に使われているプログラミング言語の特徴を覆い切れていない、狭い不満足な定義だが本稿では都合上この定義に立脚して限定的に議論する。例えば変数(variable)というものを持つプログラミング言語もあり広く使われているが、これについてはレコードや関数と同じように性質の良いものとして扱うことが難しい。難しさの原因は次の注の内容と関連する。近年は変数を扱うかわりに値の不変のコピー(immutable copy)やその参照に名前を付ける機能を持つプログラミング言語が増えている。

2) 現実の情報システムでは、COBOL 言語のレコード再定義やC言語の共用体、一般的な関数ポインタやVisual Basic 言語のvariant型変数のように、同一領域に異なる型の値が共存する共用型(union type)の値がしばしば必要となる。共用型の値はgoto文を排除した構造化／オブジェクト指向プログラミングにおいて条件キャストやクラス分岐などによる実行経路の複雑さの主要な原因になるが、これは和型(sum type)すなわち相異なる型の非交和(disjoint sum)として定義することで曖昧さなく定義できる。