type inference
An href="module.php?name=Lexikon&file=search&eid=1&query=algorithm">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 (href="module.php?name=Lexikon&file=search&eid=1&query=LaTeX">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 href="module.php?name=Lexikon&file=search&eid=1&query=infix">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 href="module.php?name=Lexikon&file=search&eid=1&query=unification">unification on href="module.php?name=Lexikon&file=search&eid=1&query=type variable">type variables to match the href="module.php?name=Lexikon&file=search&eid=1&query=partial application">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 href="module.php?name=Lexikon&file=search&eid=1&query=generic type variable">generic type variable, href="module.php?name=Lexikon&file=search&eid=1&query=principal type">principal type. (1995-02-03) In addition suitable contents:
[ href="module.php?name=Lexikon&op=content&tid=31">2 ] [ href="module.php?name=Lexikon&op=content&tid=134">= ] [ href="module.php?name=Lexikon&op=content&tid=262">ad ] [ href="module.php?name=Lexikon&op=content&tid=396">ag ] [ href="module.php?name=Lexikon&op=content&tid=411">ai ] [ href="module.php?name=Lexikon&op=content&tid=433">al ] [ href="module.php?name=Lexikon&op=content&tid=492">algorithm ] [ href="module.php?name=Lexikon&op=content&tid=531">alt ] [ href="module.php?name=Lexikon&op=content&tid=544">am ] [ href="module.php?name=Lexikon&op=content&tid=592">an ] [ href="module.php?name=Lexikon&op=content&tid=683">app ] [ href="module.php?name=Lexikon&op=content&tid=700">application ] [ href="module.php?name=Lexikon&op=content&tid=740">ar ] [ href="module.php?name=Lexikon&op=content&tid=743">arc ] [ href="module.php?name=Lexikon&op=content&tid=759">arg ] [ href="module.php?name=Lexikon&op=content&tid=760">argument ] [ href="module.php?name=Lexikon&op=content&tid=800">as ] [ href="module.php?name=Lexikon&op=content&tid=822">ash ] [ href="module.php?name=Lexikon&op=content&tid=861">assignment ] [ href="module.php?name=Lexikon&op=content&tid=894">at ] [ href="module.php?name=Lexikon&op=content&tid=1025">B ] [ href="module.php?name=Lexikon&op=content&tid=1026">b ] [ href="module.php?name=Lexikon&op=content&tid=1034">ba ] [ href="module.php?name=Lexikon&op=content&tid=1120">base ] [ href="module.php?name=Lexikon&op=content&tid=1181">be ] [ href="module.php?name=Lexikon&op=content&tid=1269">bi ] [ href="module.php?name=Lexikon&op=content&tid=1444">bo ] [ href="module.php?name=Lexikon&op=content&tid=1501">bot ] [ href="module.php?name=Lexikon&op=content&tid=1606">bs ] [ href="module.php?name=Lexikon&op=content&tid=1695">by ] [ href="module.php?name=Lexikon&op=content&tid=1724">ca ] [ href="module.php?name=Lexikon&op=content&tid=1863">cat ] [ href="module.php?name=Lexikon&op=content&tid=2001">ch ] [ href="module.php?name=Lexikon&op=content&tid=2099">ci ] [ href="module.php?name=Lexikon&op=content&tid=2136">ck ] [ href="module.php?name=Lexikon&op=content&tid=2138">cl ] [ href="module.php?name=Lexikon&op=content&tid=2247">co ] [ href="module.php?name=Lexikon&op=content&tid=2545">con ] [ href="module.php?name=Lexikon&op=content&tid=2606">cons ] [ href="module.php?name=Lexikon&op=content&tid=2630">constructor ] [ href="module.php?name=Lexikon&op=content&tid=2791">cr ] [ href="module.php?name=Lexikon&op=content&tid=3151">de ] [ href="module.php?name=Lexikon&op=content&tid=3177">dec ] [ href="module.php?name=Lexikon&op=content&tid=3436">ding ] [ href="module.php?name=Lexikon&op=content&tid=3565">do ] [ href="module.php?name=Lexikon&op=content&tid=3752">du ] [ href="module.php?name=Lexikon&op=content&tid=3865">ec ] [ href="module.php?name=Lexikon&op=content&tid=3896">ed ] [ href="module.php?name=Lexikon&op=content&tid=3923">edu ] [ href="module.php?name=Lexikon&op=content&tid=3929">ee ] [ href="module.php?name=Lexikon&op=content&tid=4148">er ] [ href="module.php?name=Lexikon&op=content&tid=4150">era ] [ href="module.php?name=Lexikon&op=content&tid=4171">es ] [ href="module.php?name=Lexikon&op=content&tid=4199">et ] [ href="module.php?name=Lexikon&op=content&tid=4317">expression ] [ href="module.php?name=Lexikon&op=content&tid=4497">fi ] [ href="module.php?name=Lexikon&op=content&tid=4520">file ] [ href="module.php?name=Lexikon&op=content&tid=4595">fix ] [ href="module.php?name=Lexikon&op=content&tid=4700">fo ] [ href="module.php?name=Lexikon&op=content&tid=4727">for ] [ href="module.php?name=Lexikon&op=content&tid=4828">fr ] [ href="module.php?name=Lexikon&op=content&tid=4859">free ] [ href="module.php?name=Lexikon&op=content&tid=4867">free variable ] [ href="module.php?name=Lexikon&op=content&tid=4983">G ] [ href="module.php?name=Lexikon&op=content&tid=4989">ga ] [ href="module.php?name=Lexikon&op=content&tid=5057">ge ] [ href="module.php?name=Lexikon&op=content&tid=5070">gen ] [ href="module.php?name=Lexikon&op=content&tid=5100">generic type variable ] [ href="module.php?name=Lexikon&op=content&tid=5141">gi ] [ href="module.php?name=Lexikon&op=content&tid=5171">gl ] [ href="module.php?name=Lexikon&op=content&tid=5205">gn ] [ href="module.php?name=Lexikon&op=content&tid=5291">gr ] [ href="module.php?name=Lexikon&op=content&tid=5403">gu ] [ href="module.php?name=Lexikon&op=content&tid=5434">h ] [ href="module.php?name=Lexikon&op=content&tid=5540">hat ] [ href="module.php?name=Lexikon&op=content&tid=5656">hing ] [ href="module.php?name=Lexikon&op=content&tid=5675">hm ] [ href="module.php?name=Lexikon&op=content&tid=5768">hr ] [ href="module.php?name=Lexikon&op=content&tid=5931">id ] [ href="module.php?name=Lexikon&op=content&tid=5956">ie ] [ href="module.php?name=Lexikon&op=content&tid=6013">il ] [ href="module.php?name=Lexikon&op=content&tid=6064">in ] [ href="module.php?name=Lexikon&op=content&tid=6068">inc ] [ href="module.php?name=Lexikon&op=content&tid=6099">inference ] [ href="module.php?name=Lexikon&op=content&tid=6101">inference rule ] [ href="module.php?name=Lexikon&op=content&tid=6413">io ] [ href="module.php?name=Lexikon&op=content&tid=6449">ir ] [ href="module.php?name=Lexikon&op=content&tid=6482">is ] [ href="module.php?name=Lexikon&op=content&tid=6558">it ] [ href="module.php?name=Lexikon&op=content&tid=6789">ke ] [ href="module.php?name=Lexikon&op=content&tid=6861">kn ] [ href="module.php?name=Lexikon&op=content&tid=6918">la ] [ href="module.php?name=Lexikon&op=content&tid=6950">language ] [ href="module.php?name=Lexikon&op=content&tid=6989">LaTeX ] [ href="module.php?name=Lexikon&op=content&tid=7023">ld ] [ href="module.php?name=Lexikon&op=content&tid=7091">Lex ] [ href="module.php?name=Lexikon&op=content&tid=7107">li ] [ href="module.php?name=Lexikon&op=content&tid=7151">line ] [ href="module.php?name=Lexikon&op=content&tid=7220">list ] [ href="module.php?name=Lexikon&op=content&tid=7395">lr ] [ href="module.php?name=Lexikon&op=content&tid=7399">ls ] [ href="module.php?name=Lexikon&op=content&tid=7410">lt ] [ href="module.php?name=Lexikon&op=content&tid=7415">lu ] [ href="module.php?name=Lexikon&op=content&tid=7441">ly ] [ href="module.php?name=Lexikon&op=content&tid=7463">ma ] [ href="module.php?name=Lexikon&op=content&tid=7932">mil ] [ href="module.php?name=Lexikon&op=content&tid=8019">mm ] [ href="module.php?name=Lexikon&op=content&tid=8032">mo ] [ href="module.php?name=Lexikon&op=content&tid=8040">mod ] [ href="module.php?name=Lexikon&op=content&tid=8079">module ] [ href="module.php?name=Lexikon&op=content&tid=8167">mp ] [ href="module.php?name=Lexikon&op=content&tid=8386">na ] [ href="module.php?name=Lexikon&op=content&tid=8460">nc ] [ href="module.php?name=Lexikon&op=content&tid=8472">ne ] [ href="module.php?name=Lexikon&op=content&tid=8622">nf ] [ href="module.php?name=Lexikon&op=content&tid=8627">ng ] [ href="module.php?name=Lexikon&op=content&tid=8630">ni ] [ href="module.php?name=Lexikon&op=content&tid=8675">no ] [ href="module.php?name=Lexikon&op=content&tid=8760">ns ] [ href="module.php?name=Lexikon&op=content&tid=8964">om ] [ href="module.php?name=Lexikon&op=content&tid=9204">pa ] [ href="module.php?name=Lexikon&op=content&tid=9457">pe ] [ href="module.php?name=Lexikon&op=content&tid=9550">ph ] [ href="module.php?name=Lexikon&op=content&tid=9651">pl ] [ href="module.php?name=Lexikon&op=content&tid=9736">plus ] [ href="module.php?name=Lexikon&op=content&tid=9908">pr ] [ href="module.php?name=Lexikon&op=content&tid=9959">principal type ] [ href="module.php?name=Lexikon&op=content&tid=9995">process ] [ href="module.php?name=Lexikon&op=content&tid=10023">program ] [ href="module.php?name=Lexikon&op=content&tid=10042">programming ] [ href="module.php?name=Lexikon&op=content&tid=10144">pt ] [ href="module.php?name=Lexikon&op=content&tid=10253">query ] [ href="module.php?name=Lexikon&op=content&tid=10364">rc ] [ href="module.php?name=Lexikon&op=content&tid=10385">re ] [ href="module.php?name=Lexikon&op=content&tid=10754">rl ] [ href="module.php?name=Lexikon&op=content&tid=10767">ro ] [ href="module.php?name=Lexikon&op=content&tid=10887">ru ] [ href="module.php?name=Lexikon&op=content&tid=10918">S ] [ href="module.php?name=Lexikon&op=content&tid=10922">sa ] [ href="module.php?name=Lexikon&op=content&tid=10999">say ] [ href="module.php?name=Lexikon&op=content&tid=11010">sc ] [ href="module.php?name=Lexikon&op=content&tid=11150">se ] [ href="module.php?name=Lexikon&op=content&tid=11281">set ] [ href="module.php?name=Lexikon&op=content&tid=11314">sh ] [ href="module.php?name=Lexikon&op=content&tid=11376">si ] [ href="module.php?name=Lexikon&op=content&tid=11389">sig ] [ href="module.php?name=Lexikon&op=content&tid=11510">sk ] [ href="module.php?name=Lexikon&op=content&tid=11651">so ] [ href="module.php?name=Lexikon&op=content&tid=11934">st ] [ href="module.php?name=Lexikon&op=content&tid=12109">struct ] [ href="module.php?name=Lexikon&op=content&tid=12133">su ] [ href="module.php?name=Lexikon&op=content&tid=12165">sum ] [ href="module.php?name=Lexikon&op=content&tid=12246">sy ] [ href="module.php?name=Lexikon&op=content&tid=12359">T ] [ href="module.php?name=Lexikon&op=content&tid=12440">tc ] [ href="module.php?name=Lexikon&op=content&tid=12588">th ] [ href="module.php?name=Lexikon&op=content&tid=12721">to ] [ href="module.php?name=Lexikon&op=content&tid=12787">tr ] [ href="module.php?name=Lexikon&op=content&tid=12970">type ] [ href="module.php?name=Lexikon&op=content&tid=12973">type assignment ] [ href="module.php?name=Lexikon&op=content&tid=12986">ua ] [ href="module.php?name=Lexikon&op=content&tid=13030">um ] [ href="module.php?name=Lexikon&op=content&tid=13058">unification ] [ href="module.php?name=Lexikon&op=content&tid=13175">us ] [ href="module.php?name=Lexikon&op=content&tid=13188">user ] [ href="module.php?name=Lexikon&op=content&tid=13252">va ] [ href="module.php?name=Lexikon&op=content&tid=13274">var ] [ href="module.php?name=Lexikon&op=content&tid=13275">variable ] [ href="module.php?name=Lexikon&op=content&tid=13310">ve ] [ href="module.php?name=Lexikon&op=content&tid=13891">X ] [ href="module.php?name=Lexikon&op=content&tid=14024">Y ]
[ Go Back ]
Free On-line Dictionary of Computing Copyright © by OnlineWoerterBuecher.de - (7218 Reads) |
