type inference
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) 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 ]
[ Go Back ]
Free On-line Dictionary of Computing Copyright © by OnlineWoerterBuecher.de - (7244 Reads) |
