Use in Programming Languages
The version of System F used in this article is as an explicitly typed, or Church-style, calculus. The typing information contained in λ-terms makes type-checking straightforward. Joe Wells (1994) settled an "embarrassing open problem" by proving that type checking is undecidable for a Curry-style variant of System F, that is, one that lacks explicit typing annotations.
Wells' result implies that type inference for System F is impossible. A restriction of System F known as "Hindley–Milner", or simply "HM", does have an easy type inference algorithm and is used for many strongly typed functional programming languages such as Haskell 98 and ML. Over time, as the restrictions of HM-style type systems have become apparent, languages have steadily moved to more expressive logics for their type systems. As of 2008, GHC, a Haskell compiler, goes beyond HM, and now uses System F extended with non-syntactic type equality, for example.
Read more about this topic: System F
Famous quotes containing the words programming and/or languages:
“If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
—Melinda M. Marshall (20th century)
“No doubt, to a man of sense, travel offers advantages. As many languages as he has, as many friends, as many arts and trades, so many times is he a man. A foreign country is a point of comparison, wherefrom to judge his own.”
—Ralph Waldo Emerson (1803–1882)