Typed_lambda_calculus
「型付きラムダ計算」
型付きラムダ計算は、入力される形式主義ラムダシンボルを（使用します λ { lambda}
）無名関数の抽象化を示します。このコンテキストでは、型は通常、ラムダ用語に割り当てられる構文上の性質のオブジェクトです。タイプの正確な性質は、考慮される微積分によって異なります（以下の種類を参照）。ある観点からは、型付きラムダ計算は型なしラムダ計算の改良版と見なすことができますが、別の観点からは、より基本的な理論であり、型なしラムダ計算は1つの型のみの特殊なケースと見なすこともできます。
型付きラムダ計算は基本的なプログラミング言語であり、MLやHaskellなどの型付き関数型プログラミング言語、より間接的には型付き命令型プログラミング言語のベースです。型付きラムダ計算は、プログラミング言語の型システムの設計において重要な役割を果たします。ここで、タイピング可能性は通常、プログラムの望ましいプロパティをキャプチャします（たとえば、プログラムはメモリアクセス違反を引き起こしません）。
型付きラムダ計算は、カリー・ハワード同形性を介して数理論理学および証明論と密接に関連しており、カテゴリーのクラスの内部言語と見なすことができます。たとえば、単純に型付きラムダ計算は、デカルト閉圏（CCC）の言語です。
コンテンツ
1 型付きラムダ計算の種類
2 プログラミング言語への応用
3 も参照してください
4 ノート
5 参考文献
型付きラムダ計算の種類
さまざまな型付きラムダ計算が研究されてきました。単に型付きラムダ計算は一つだけ持っている型コンストラクタ、矢印を
{ to}
、およびその唯一の型は基本型と関数型ですσ τ
{ sigma to tau}
。システムTは、単純に型付きラムダ計算を、ある種の自然数と高階の原始再帰で拡張します。このシステムでは、ペアノ算術で再帰的であることが証明できるすべての関数を定義できます。システムFは、すべてのタイプで全称記号を使用することにより、ポリモーフィズムを可能にします。論理的な観点から、それは二階述語論理で確かに合計であるすべての関数を記述することができます。依存型を持つラムダ計算は、直観主義型理論の基礎であり、構造の計算と論理フレームワーク（LF）であり、依存型を持つ純粋なラムダ計算です。ベラルディの純粋な型システムに関する研究に基づいて、ヘンク・バレンドレッグは、純粋な型付きラムダ計算（単純型付きラムダ計算、システムF、LF、および構造の計算を含む）の関係を体系化するラムダキューブを提案しました。
いくつかは、型付きラムダ結石の概念を導入するサブタイピング場合、すなわち {A}
のサブタイプです {B}
、次にタイプのすべての用語 {A}
タイプもあります {B}
。サブタイピングを使用した型付きラムダ計算は、接続詞型とシステムF <：を使用した単純型付きラムダ計算です。
これまでに説明したすべてのシステムは、型指定されていないラムダ計算を除いて、強く正規化されています。すべての計算が終了します。したがって、チューリングで計算可能なすべての関数を記述することはできません。別の結果として、それらは論理として一貫しています。つまり、無人のタイプがただし、強く正規化されていない型付きラムダ計算が存在します。たとえば、すべての型（Type：Type）の型を持つ依存型ラムダ計算は、Girardのパラドックスのために正規化されこのシステムは、最も単純な純粋なタイプのシステムでもあり、ラムダキューブを一般化する形式です。Plotkinの「計算可能関数のプログラミング言語」（PCF）などの明示的な再帰コンビネータを備えたシステムは正規化されていませんが、ロジックとして解釈されることを意図し実際、PCFは典型的な型付き関数型プログラミング言語であり、型はプログラムが正常に動作することを保証するために使用されますが、必ずしもプログラムが終了しているとは限りません。
プログラミング言語への応用
コンピュータプログラミングのルーチン（関数、プロシージャ、メソッド）強く型付けされたプログラミング言語は密接型付きラムダ式に対応します。
も参照してください
カッパ計算—高階関数を除外した型付きラムダ計算の類似体
ノート
^ 以来停止問題後者のクラスのためであることが証明された決定不能
参考文献
バレンドレッグ、ヘンク（1992）。「型付きラムダ計算」。Abramsky、S。（ed。）背景：計算構造。コンピュータサイエンスにおける論理のハンドブック。2。オックスフォード大学出版局。pp。117–309。ISBN 9780198537618。”