System F

System F (also polymorphic lambda calculus or second-order lambda calculus) is a <a href="/facts/Typed_lambda_calculus/g86GP4uK">typed lambda calculus</a> that introduces, to <a href="/facts/Simply_typed_lambda_calculus/5RQlXLjy">simply typed lambda calculus</a>, a mechanism of <a href="/facts/Universal_quantification/agNmvJKN">universal quantification</a> over types. System F formalizes <a href="/facts/Parametric_polymorphism/ETb0G1zd">parametric polymorphism</a> in <a href="/facts/Programming_language/cWTYbgWa">programming languages</a>, thus forming a theoretical basis for languages such as <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a> and <a href="/facts/ML_(programming_language)/RfwxASRF">ML</a>. It was discovered independently by <a href="/facts/Logician/8JnpJLtt">logician</a> <a href="/facts/Jean-Yves_Girard/yX6YTFRy">Jean-Yves Girard</a> (1972) and <a href="/facts/Computer_scientist/DavggjGL">computer scientist</a> <a href="/facts/John_C._Reynolds/6cdgIrBx">John C. Reynolds</a>.
Whereas <a href="/facts/Simply_typed_lambda_calculus/5RQlXLjy">simply typed lambda calculus</a> has variables ranging over terms, and binders for them, System F additionally has variables ranging over types, and binders for them. As an example, the fact that the identity function can have any type of the form A → A would be formalized in System F as the judgement

⊢
        Λ
        α
        .
        λ
        
          x
          
            α
          
        
        .
        x
        :
        ∀
        α
        .
        α
        →
        α
      
    
    {\displaystyle \vdash \Lambda \alpha .\lambda x^{\alpha }.x:\forall \alpha .\alpha \to \alpha }

where 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is a <a href="/facts/Type_variable/72tpqsqS">type variable</a>. The upper-case 
 
 
 
 Λ
 
 
 {\displaystyle \Lambda }
 
 is traditionally used to denote type-level functions, as opposed to the lower-case 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 which is used for value-level functions. (The superscripted 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 means that the bound variable x is of type 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
; the expression after the colon is the type of the lambda expression preceding it.)
As a <a href="/facts/Term_rewriting_system/9PHlnnnJ">term rewriting system</a>, System F is <a href="/facts/Normalization_property_(lambda-calculus)/eV9G3veH">strongly normalizing</a>. However, <a href="/facts/Type_inference/vX9K8Qhf">type inference</a> in System F (without explicit type annotations) is undecidable. Under the <a href="/facts/Curry%25E2%2580%2593Howard_isomorphism/Q3eVu60u">Curry–Howard isomorphism</a>, System F corresponds to the fragment of second-order <a href="/facts/Intuitionistic_logic/zI7ulCnM">intuitionistic logic</a> that uses only universal quantification. System F can be seen as part of the <a href="/facts/Lambda_cube/tSR2laCs">lambda cube</a>, together with even more expressive typed lambda calculi, including those with <a href="/facts/Dependent_types/wCeQI7ds">dependent types</a>.
According to Girard, the "F" in System F was picked by chance.

System F open-in-new

System F