type inference

Computing Dictionary

type inference definition

programming
An algorithm for ascribing types to expressions in some language, based on the types of the constants of the language and a set of type inference rules such as
f :: A -> B, x :: A --------------------- (App) f x :: B
This rule, called "App" for application, says that if expression f has type A -> B and expression x has type A then we can deduce that expression (f x) has type B. The expressions above the line are the premises and below, the conclusion. An alternative notation often used is:
G |- x : A
where "|-" is the turnstile symbol (LaTeX \vdash) and G is a type assignment for the free variables of expression x. The above can be read "under assumptions G, expression x has type A". (As in Haskell, we use a double "::" for type declarations and a single ":" for the infix list constructor, cons).
Given an expression
plus (head l) 1
we can label each subexpression with a type, using type variables X, Y, etc. for unknown types:
(plus :: Int -> Int -> Int) (((head :: [a] -> a) (l :: Y)) :: X) (1 :: Int)
We then use unification on type variables to match the partial application of plus to its first argument against the App rule, yielding a type (Int -> Int) and a substitution X = Int. Re-using App for the application to the second argument gives an overall type Int and no further substitutions. Similarly, matching App against the application (head l) we get Y = [X]. We already know X = Int so therefore Y = [Int].
This process is used both to infer types for expressions and to check that any types given by the user are consistent.
See also generic type variable, principal type.
(1995-02-03)
The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: type iii mucopolysaccharidosis
Words Near: type inference
More from Thesaurus.com
Synonyms and Antonyms for type inference
More from Reference.com
Search for articles containing type inference
More from Dictionary.com Translator
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature