<
programming> An
algorithm for ascribing types to ex
pressions 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 ex
pression f has type A -> B and ex
pression x has type A then we can deduce that ex
pression (f x) has type B. The ex
pressions 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 ex
pression x. The above can be read "under assumptions G, ex
pression 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 ex
pression plus (head l) 1 we can label each subex
pression 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 ex
pressions and to check that any types given by the user are consistent. See also
generic type variable,
principal type. (1995-02-03)
In addition suitable contents:
[ 2 ] [ = ] [ ad ] [ ag ] [ ai ] [ al ] [ algorithm ] [ alt ] [ am ] [ an ] [ app ] [ application ] [ ar ] [ arc ] [ arg ] [ argument ] [ as ] [ ash ] [ assignment ] [ at ] [ B ] [ b ] [ ba ] [ base ] [ be ] [ bi ] [ bo ] [ bot ] [ bs ] [ by ] [ ca ] [ cat ] [ ch ] [ ci ] [ ck ] [ cl ] [ co ] [ con ] [ cons ] [ constructor ] [ cr ] [ de ] [ dec ] [ ding ] [ do ] [ du ] [ ec ] [ ed ] [ edu ] [ ee ] [ er ] [ era ] [ es ] [ et ] [ expression ] [ fi ] [ file ] [ fix ] [ fo ] [ for ] [ fr ] [ free ] [ free variable ] [ G ] [ ga ] [ ge ] [ gen ] [ generic type variable ] [ gi ] [ gl ] [ gn ] [ gr ] [ gu ] [ h ] [ hat ] [ hing ] [ hm ] [ hr ] [ id ] [ ie ] [ il ] [ in ] [ inc ] [ inference ] [ inference rule ] [ io ] [ ir ] [ is ] [ it ] [ ke ] [ kn ] [ la ] [ language ] [ LaTeX ] [ ld ] [ Lex ] [ li ] [ line ] [ list ] [ lr ] [ ls ] [ lt ] [ lu ] [ ly ] [ ma ] [ mil ] [ mm ] [ mo ] [ mod ] [ module ] [ mp ] [ na ] [ nc ] [ ne ] [ nf ] [ ng ] [ ni ] [ no ] [ ns ] [ om ] [ pa ] [ pe ] [ ph ] [ pl ] [ plus ] [ pr ] [ principal type ] [ process ] [ program ] [ programming ] [ pt ] [ query ] [ rc ] [ re ] [ rl ] [ ro ] [ ru ] [ S ] [ sa ] [ say ] [ sc ] [ se ] [ set ] [ sh ] [ si ] [ sig ] [ sk ] [ so ] [ st ] [ struct ] [ su ] [ sum ] [ sy ] [ T ] [ tc ] [ th ] [ to ] [ tr ] [ type ] [ type assignment ] [ ua ] [ um ] [ unification ] [ us ] [ user ] [ va ] [ var ] [ variable ] [ ve ] [ X ] [ Y ]