1646:
1270:
1719:. This is very similar to what is called "ML-style" or "Let-polymorphism" (technically ML's Let-polymorphism has a few other syntactic restrictions). This restriction makes the distinction between polymorphic and non-polymorphic types very important; thus in predicative systems polymorphic types are sometimes referred to as
186:: they behave identically regardless of the type they are instantiated at. In contrast, ad hoc polymorphic definitions are given a distinct definition for each type. Thus, ad hoc polymorphism can generally only support a limited number of such distinct types, since a separate implementation has to be provided for each type.
1140:
2298:
if it is self-referential; in type theory, it refers to the ability for a type to be in the domain of a quantifier it contains. This allows the instantiation of any type variable with any type, including polymorphic types. An example of a system supporting full impredicativity is
2474:
2020:) performs type inference and supports impredicative polymorphism, but in some cases when impredicative polymorphism is used, the system's type inference is incomplete unless some explicit type annotations are provided by the programmer.
2700:
With one exception (that of the distinguished type variable in a class declaration (Section 4.3.1)), the type variables in a
Haskell type expression are all assumed to be universally quantified; there is no explicit syntax for universal
2263:
2379:
on the type parameters. Many operations require some knowledge of the data types, but can otherwise work parametrically. For example, to check whether an item is included in a list, we need to compare the items for equality. In
2204:
2073:
1265:{\displaystyle {\begin{aligned}{\mathsf {fst}}&:\forall \alpha .\forall \beta .\alpha \times \beta \to \alpha \\{\mathsf {snd}}&:\forall \alpha .\forall \beta .\alpha \times \beta \to \beta \end{aligned}}}
1619:
have each introduced "generics" for parametric polymorphism. Some implementations of type polymorphism are superficially similar to parametric polymorphism while also introducing ad hoc aspects. One example is
488:
1854:
906:
399:
1337:
335:
1145:
2336:
283:
155:
allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed. Parametrically polymorphic
237:
1999:
1960:
1767:
1068:
978:
604:
557:
1440:
1534:
1500:
1470:
1387:
1128:
1098:
1029:
939:
426:
2411:
773:
684:
2145:
1897:
1357:
1002:
515:
1407:
1730:
A consequence of predicativity is that all types can be written in a form that places all quantifiers at the outermost (prenex) position. For example, consider the
1921:
1877:
819:
2114:
799:
2209:
2863:(1971). "Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types".
1539:
is implicit and may be omitted. Other languages require types to be instantiated explicitly at some or all of a parametrically polymorphic function's
2823:
2758:
2028:
Some type systems support an impredicative function type constructor even though other type constructors remain predicative. For example, the type
1509:
used to introduce parametric polymorphism varies significantly between programming languages. For example, in some programming languages, such as
2162:
2031:
2576:
520:
The identity function is a particularly extreme example, but many other functions also benefit from parametric polymorphism. For example, an
445:
3213:
2476:
in
Haskell. In most object-oriented programming languages that support parametric polymorphism, parameters can be constrained to be
1775:
827:
3640:
2001:
itself. Polymorphism in the language ML is predicative. This is because predicativity, together with other restrictions, makes the
1663:
3584:
3218:
2957:
3208:
3203:
130:
2755:
Kfoury, A. J.; Wells, J. B. (1 January 1999). "Principality and decidable type inference for finite-rank intersection types".
340:
3061:
2935:
2556:
3191:
3092:
1278:
288:
2306:
242:
1070:
are parameterized over a single type, but functions may be parameterized over arbitrarily many types. For example, the
3369:
2915:
2880:
1685:
2684:
3342:
22:
3459:
3264:
3196:
3158:
2949:
2777:
2401:
1667:
1608:
1576:
1572:
1564:
1506:
2633:
1592:
2867:. Studies in Logic and the Foundations of Mathematics (in French). Vol. 63. Amsterdam. pp. 63–92.
3635:
3359:
3289:
3137:
2512:
1588:
1584:
1962:
can be applied to pairs of lists with elements of any type—even to lists of polymorphic functions such as
1711:
system), type variables may not be instantiated with polymorphic types. Predicative type theories include
239:
simply returns its argument unmodified. This naturally gives rise to a family of potential types, such as
3614:
3249:
1604:
200:
2730:
1965:
1926:
1733:
1034:
944:
570:
523:
3237:
1712:
1568:
194:
It is possible to write functions that do not depend on the types of their arguments. For example, the
123:
2469:{\textstyle \mathrm {Eq} \,\alpha \,\Rightarrow \alpha \,\rightarrow \left\rightarrow \mathrm {Bool} }
1412:
3547:
3499:
3411:
3389:
3384:
3312:
3178:
3132:
2017:
1516:
1475:
1445:
1362:
1103:
1073:
1007:
917:
404:
3421:
3085:
3016:
433:
2507:
2388:
are restricted so that the equality operation is available, thus the function would have the type
3489:
2715:, Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types",
1656:
1624:
1552:
689:
609:
3317:
3173:
3127:
3011:
2362:
156:
2130:
3307:
3282:
3002:
2907:
2502:
2346:
1882:
1342:
987:
500:
116:
2895:
Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur
1392:
3645:
3109:
2852:
2572:
2481:
1899:
such that the resulting function type is consistent with the types of the arguments. In an
429:
144:
43:
38:
8:
3579:
3557:
3484:
3337:
3329:
3078:
2994:
2485:
179:
172:
66:
29:
2258:{\displaystyle ((\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T)\rightarrow T}
2151:
or more arrows, when the type is drawn as a tree. A type system is said to support rank-
3562:
3542:
3494:
3469:
3254:
3223:
3049:
3037:
2974:
2840:
2783:
2614:
2542:
1906:
1862:
1536:
804:
104:
2872:
2078:
778:
567:
does not inspect the elements of the list, only the list structure itself. Therefore,
3449:
3379:
3354:
3168:
3163:
3057:
3029:
2970:
2931:
2876:
2773:
2606:
2552:
1612:
195:
99:
2787:
2659:
2618:
3594:
3479:
3277:
3041:
3021:
2966:
2923:
2903:
2890:
2868:
2860:
2832:
2818:
2763:
2598:
89:
84:
61:
2978:
1723:
to distinguish them from ordinary (monomorphic) types, which are sometimes called
3599:
3464:
3416:
3349:
2848:
2546:
2295:
1700:
94:
2581:(Lecture notes), Copenhagen: International Summer School in Computer Programming
3552:
3374:
3364:
3272:
2272:
2006:
1630:
2927:
2602:
1923:
may be any type whatsoever, including a type that is itself polymorphic; thus
3629:
3474:
3033:
2986:
2610:
2497:
2368:
2075:
is permitted in a system that supports higher-rank polymorphism, even though
1616:
1580:
436:
3431:
3406:
2990:
2945:
2712:
2372:
2291:
2275:
for rank-2 polymorphism is decidable, but for rank-3 and above, it is not.
2159:. For example, a type system that supports rank-2 polymorphism would allow
1131:
2768:
2586:
3609:
3604:
3454:
3401:
3228:
2381:
2350:
2342:
2199:{\displaystyle (\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T}
2068:{\displaystyle (\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T}
2002:
1556:
1551:
Parametric polymorphism was first introduced to programming languages in
564:
148:
2265:. A type system that admits types of arbitrary rank is said to be "rank-
3514:
3509:
3426:
3394:
3299:
3242:
2844:
2821:(1969), "The principal type scheme of an object in combinatory logic",
2405:
1670: in this section. Unsourced material may be challenged and removed.
1596:
3025:
3589:
3567:
3524:
3519:
3186:
3142:
3101:
2477:
1540:
160:
75:
2836:
1859:
In order to apply this function to a pair of lists, a concrete type
1645:
3504:
2300:
1510:
483:{\displaystyle {\mathsf {id}}:\forall \alpha .\alpha \to \alpha }
2155:
polymorphism if it admits types with rank less than or equal to
1706:
560:
1849:{\displaystyle {\mathsf {append}}:\forall \alpha .\times \to }
901:{\displaystyle {\mathsf {append}}:\forall \alpha .\times \to }
3070:
2013:
1716:
1621:
1600:
1560:
2995:"On Understanding Types, Data Abstraction, and Polymorphism"
1631:
Predicativity, impredicativity, and higher-rank polymorphism
3122:
2290:) is the most powerful form of parametric polymorphism. In
3117:
2794:
2762:. Association for Computing Machinery. pp. 161–174.
2404:, bounding is achieved by requiring types to belong to a
1769:
function described above, which has the following type:
1130:
functions that return the first and second elements of a
394:{\displaystyle {\mathsf {String}}\to {\mathsf {String}}}
2865:
2685:"Haskell 2010 Language Report § 4.1.2 Syntax of Types"
2414:
2309:
2212:
2165:
2133:
2081:
2034:
1968:
1929:
1909:
1885:
1865:
1778:
1736:
1519:
1478:
1448:
1415:
1395:
1365:
1345:
1332:{\displaystyle {\mathsf {fst}}((3,{\mathsf {true}}))}
1281:
1143:
1106:
1076:
1037:
1010:
990:
947:
920:
911:
which can be instantiated to any type in the family.
830:
807:
781:
692:
612:
573:
526:
503:
448:
407:
343:
291:
245:
203:
1635:
330:{\displaystyle {\mathsf {Bool}}\to {\mathsf {Bool}}}
2717:Proc. Conference on Proving and Improving Programs
2541:
2468:
2356:
2331:{\displaystyle \forall \alpha .\alpha \to \alpha }
2330:
2257:
2198:
2139:
2108:
2067:
1993:
1954:
1915:
1891:
1871:
1848:
1761:
1528:
1494:
1464:
1434:
1401:
1381:
1351:
1331:
1264:
1134:, respectively, can be given the following types:
1122:
1092:
1062:
1023:
996:
972:
933:
900:
813:
793:
767:
678:
598:
551:
509:
482:
420:
393:
329:
278:{\displaystyle {\mathsf {Int}}\to {\mathsf {Int}}}
277:
231:
2824:Transactions of the American Mathematical Society
2731:"Kwang's Haskell Blog - Higher rank polymorphism"
3627:
2759:Symposium on Principles of Programming Languages
606:can be given a similar family of types, such as
2587:"Fundamental Concepts in Programming Languages"
517:, yielding the full family of potential types.
178:Parametric polymorphism may be contrasted with
2985:
2950:"A Theory of Type Polymorphism in Programming"
2897:(Ph.D. thesis) (in French), Université Paris 7
2800:
3086:
2578:Fundamental Concepts in Programming Languages
2400:can only be a type with defined equality. In
2278:
182:. Parametrically polymorphic definitions are
124:
2565:
2345:, the most frequently studied impredicative
401:, and so on. Parametric polymorphism allows
2757:Proceedings of the 26th ACM SIGPLAN-SIGACT
2754:
2023:
1472:, so the type of the overall expression is
171:, respectively, and they form the basis of
3093:
3079:
914:Parametrically polymorphic functions like
131:
117:
3015:
2767:
2728:
2434:
2427:
2423:
1686:Learn how and when to remove this message
2902:
2584:
2571:
2958:Journal of Computer and System Sciences
2817:
493:The polymorphic definition can then be
3628:
3048:
2944:
2889:
2859:
2585:Strachey, Christopher (1 April 2000).
2537:
2535:
2533:
2531:
2529:
2527:
2408:; thus the same function has the type
2375:recognized the advantages of allowing
1986:
1983:
1980:
1977:
1974:
1971:
1947:
1944:
1941:
1938:
1935:
1932:
1796:
1793:
1790:
1787:
1784:
1781:
1754:
1751:
1748:
1745:
1742:
1739:
1487:
1484:
1481:
1457:
1454:
1451:
1427:
1424:
1421:
1418:
1374:
1371:
1368:
1318:
1315:
1312:
1309:
1290:
1287:
1284:
1213:
1210:
1207:
1156:
1153:
1150:
1115:
1112:
1109:
1085:
1082:
1079:
1055:
1052:
1049:
1046:
1043:
1040:
1016:
1013:
965:
962:
959:
956:
953:
950:
926:
923:
848:
845:
842:
839:
836:
833:
757:
754:
751:
748:
732:
729:
726:
723:
707:
704:
701:
698:
668:
665:
662:
646:
643:
640:
624:
621:
618:
591:
588:
585:
582:
579:
576:
544:
541:
538:
535:
532:
529:
497:by substituting any concrete type for
454:
451:
413:
410:
386:
383:
380:
377:
374:
371:
361:
358:
355:
352:
349:
346:
322:
319:
316:
313:
303:
300:
297:
294:
270:
267:
264:
254:
251:
248:
209:
206:
3074:
2591:Higher-Order and Symbolic Computation
2508:Type class#Higher-kinded polymorphism
1879:must be substituted for the variable
821:. The most general type is therefore
2908:"Towards a Theory of Type Structure"
2660:"Parametric Polymorphism - SML Help"
2634:"More polymorphism and type classes"
1668:adding citations to reliable sources
1639:
2524:
801:denotes a list of elements of type
232:{\displaystyle {\mathsf {id}}(x)=x}
189:
13:
2631:
2480:of a given type (see the articles
2462:
2459:
2456:
2453:
2419:
2416:
2310:
2219:
2169:
2134:
2085:
2038:
1994:{\displaystyle {\mathsf {append}}}
1955:{\displaystyle {\mathsf {append}}}
1804:
1762:{\displaystyle {\mathsf {append}}}
1520:
1234:
1225:
1177:
1168:
1063:{\displaystyle {\mathsf {append}}}
973:{\displaystyle {\mathsf {append}}}
856:
599:{\displaystyle {\mathsf {append}}}
552:{\displaystyle {\mathsf {append}}}
462:
14:
3657:
2916:Lecture Notes in Computer Science
2147:quantifier passes to the left of
1636:Rank-1 (predicative) polymorphism
2127:) if no path from its root to a
1644:
1435:{\displaystyle {\mathsf {Bool}}}
3641:Polymorphism (computer science)
3054:Types and Programming Languages
2548:Types and Programming Languages
2357:Bounded parametric polymorphism
2338:at any type, including itself.
1655:needs additional citations for
1529:{\displaystyle \forall \alpha }
1495:{\displaystyle {\mathsf {Int}}}
1465:{\displaystyle {\mathsf {fst}}}
1382:{\displaystyle {\mathsf {Int}}}
1123:{\displaystyle {\mathsf {snd}}}
1093:{\displaystyle {\mathsf {fst}}}
3100:
2748:
2722:
2706:
2677:
2657:
2651:
2625:
2449:
2435:
2428:
2384:, type parameters of the form
2322:
2249:
2246:
2240:
2237:
2231:
2216:
2213:
2190:
2187:
2181:
2166:
2103:
2097:
2082:
2059:
2056:
2050:
2035:
1843:
1837:
1834:
1831:
1825:
1819:
1813:
1326:
1323:
1298:
1295:
1252:
1195:
1024:{\displaystyle {\mathsf {id}}}
934:{\displaystyle {\mathsf {id}}}
895:
889:
886:
883:
877:
871:
865:
788:
782:
762:
743:
740:
737:
718:
712:
693:
673:
657:
654:
651:
635:
629:
613:
474:
421:{\displaystyle {\mathsf {id}}}
366:
308:
259:
220:
214:
1:
3159:Arbitrary-precision or bignum
2912:Colloque Sur la Programmation
2873:10.1016/S0049-237X(08)70843-7
2809:
2303:, which allows instantiating
2294:, a definition is said to be
2119:A type is said to be of rank
1704:type system (also known as a
2971:10.1016/0022-0000(78)90014-4
2513:Trait (computer programming)
2016:(a descendant or dialect of
1555:in 1975. Today it exists in
16:Basis of generic programming
7:
2491:
768:{\displaystyle \times \to }
679:{\displaystyle \times \to }
90:Single and dynamic dispatch
10:
3662:
2801:Cardelli & Wegner 1985
2360:
2349:are based on those of the
2284:Impredicative polymorphism
2279:Impredicative polymorphism
1546:
3533:
3500:Strongly typed identifier
3442:
3328:
3298:
3263:
3151:
3108:
2928:10.1007/3-540-06859-7_148
2518:
2288:first-class polymorphism
2140:{\displaystyle \forall }
2123:(for some fixed integer
2024:Higher-rank polymorphism
2012:As a practical example,
2005:simple enough that full
3575:Parametric polymorphism
2603:10.1023/A:1010000313106
2353:, especially System F.
1892:{\displaystyle \alpha }
1625:template specialization
1352:{\displaystyle \alpha }
997:{\displaystyle \alpha }
510:{\displaystyle \alpha }
153:parametric polymorphism
53:Parametric polymorphism
2719:, Arc-et-Senans (1975)
2470:
2363:Bounded quantification
2332:
2259:
2200:
2141:
2110:
2069:
1995:
1956:
1917:
1893:
1873:
1850:
1763:
1713:Martin-Löf type theory
1530:
1496:
1466:
1436:
1403:
1402:{\displaystyle \beta }
1383:
1353:
1333:
1266:
1124:
1094:
1064:
1025:
998:
974:
935:
902:
815:
795:
769:
680:
600:
553:
511:
484:
434:universally quantified
432:type by introducing a
428:to be given a single,
422:
395:
331:
279:
233:
3003:ACM Computing Surveys
2769:10.1145/292540.292556
2573:Strachey, Christopher
2503:Polymorphic recursion
2471:
2333:
2260:
2201:
2142:
2111:
2070:
1996:
1957:
1918:
1894:
1874:
1851:
1764:
1531:
1497:
1467:
1437:
1404:
1384:
1354:
1334:
1267:
1125:
1095:
1065:
1026:
999:
975:
936:
903:
816:
796:
770:
681:
601:
554:
512:
485:
423:
396:
332:
280:
234:
163:are sometimes called
145:programming languages
2482:Subtype polymorphism
2412:
2307:
2210:
2163:
2131:
2079:
2032:
2009:is always possible.
1966:
1927:
1907:
1883:
1863:
1776:
1734:
1664:improve this article
1517:
1476:
1446:
1413:
1393:
1363:
1343:
1279:
1141:
1104:
1074:
1035:
1008:
988:
945:
918:
828:
805:
779:
690:
610:
571:
524:
501:
446:
405:
341:
289:
243:
201:
44:Operator overloading
39:Function overloading
3636:Generic programming
3580:Primitive data type
3485:Recursive data type
3338:Algebraic data type
3214:Quadruple precision
3050:Pierce, Benjamin C.
2486:Generic programming
1409:is instantiated to
1359:is instantiated to
775:, and so on, where
180:ad hoc polymorphism
173:generic programming
67:Generic programming
30:Ad hoc polymorphism
3543:Abstract data type
3224:Extended precision
3183:Reduced precision
2922:, Paris: 408–425,
2638:www.seas.upenn.edu
2583:. Republished in:
2543:Benjamin C. Pierce
2466:
2328:
2255:
2196:
2137:
2106:
2065:
1991:
1952:
1913:
1889:
1869:
1846:
1759:
1526:
1492:
1462:
1432:
1399:
1379:
1349:
1329:
1275:In the expression
1262:
1260:
1120:
1090:
1060:
1021:
994:
984:an arbitrary type
982:parameterized over
970:
931:
898:
811:
791:
765:
676:
596:
549:
507:
480:
418:
391:
327:
275:
229:
105:Predicate dispatch
3623:
3622:
3355:Associative array
3219:Octuple precision
3063:978-0-262-16209-8
3026:10.1145/6041.6042
2993:(December 1985).
2937:978-3-540-06859-4
2904:Reynolds, John C.
2891:Girard, Jean-Yves
2861:Girard, Jean-Yves
2819:Hindley, J. Roger
2664:smlhelp.github.io
2558:978-0-262-16209-8
1916:{\displaystyle T}
1872:{\displaystyle T}
1696:
1695:
1688:
1613:Visual Basic .NET
814:{\displaystyle T}
196:identity function
169:generic datatypes
165:generic functions
141:
140:
100:Multiple dispatch
3653:
3595:Type constructor
3480:Opaque data type
3412:Record or Struct
3209:Double precision
3204:Single precision
3095:
3088:
3081:
3072:
3071:
3067:
3045:
3019:
2999:
2982:
2954:
2940:
2898:
2886:
2855:
2804:
2798:
2792:
2791:
2771:
2752:
2746:
2745:
2743:
2741:
2726:
2720:
2710:
2704:
2703:
2697:
2695:
2681:
2675:
2674:
2672:
2670:
2655:
2649:
2648:
2646:
2644:
2629:
2623:
2622:
2582:
2569:
2563:
2562:
2539:
2475:
2473:
2472:
2467:
2465:
2448:
2422:
2396:list → bool and
2337:
2335:
2334:
2329:
2264:
2262:
2261:
2256:
2205:
2203:
2202:
2197:
2146:
2144:
2143:
2138:
2115:
2113:
2112:
2109:{\displaystyle }
2107:
2074:
2072:
2071:
2066:
2000:
1998:
1997:
1992:
1990:
1989:
1961:
1959:
1958:
1953:
1951:
1950:
1922:
1920:
1919:
1914:
1898:
1896:
1895:
1890:
1878:
1876:
1875:
1870:
1855:
1853:
1852:
1847:
1800:
1799:
1768:
1766:
1765:
1760:
1758:
1757:
1691:
1684:
1680:
1677:
1671:
1648:
1640:
1535:
1533:
1532:
1527:
1501:
1499:
1498:
1493:
1491:
1490:
1471:
1469:
1468:
1463:
1461:
1460:
1441:
1439:
1438:
1433:
1431:
1430:
1408:
1406:
1405:
1400:
1388:
1386:
1385:
1380:
1378:
1377:
1358:
1356:
1355:
1350:
1338:
1336:
1335:
1330:
1322:
1321:
1294:
1293:
1271:
1269:
1268:
1263:
1261:
1217:
1216:
1160:
1159:
1129:
1127:
1126:
1121:
1119:
1118:
1099:
1097:
1096:
1091:
1089:
1088:
1069:
1067:
1066:
1061:
1059:
1058:
1030:
1028:
1027:
1022:
1020:
1019:
1003:
1001:
1000:
995:
979:
977:
976:
971:
969:
968:
940:
938:
937:
932:
930:
929:
907:
905:
904:
899:
852:
851:
820:
818:
817:
812:
800:
798:
797:
794:{\displaystyle }
792:
774:
772:
771:
766:
761:
760:
736:
735:
711:
710:
685:
683:
682:
677:
672:
671:
650:
649:
628:
627:
605:
603:
602:
597:
595:
594:
558:
556:
555:
550:
548:
547:
516:
514:
513:
508:
489:
487:
486:
481:
458:
457:
427:
425:
424:
419:
417:
416:
400:
398:
397:
392:
390:
389:
365:
364:
336:
334:
333:
328:
326:
325:
307:
306:
284:
282:
281:
276:
274:
273:
258:
257:
238:
236:
235:
230:
213:
212:
190:Basic definition
133:
126:
119:
85:Virtual function
62:Generic function
19:
18:
3661:
3660:
3656:
3655:
3654:
3652:
3651:
3650:
3626:
3625:
3624:
3619:
3600:Type conversion
3535:
3529:
3465:Enumerated type
3438:
3324:
3318:null-terminated
3294:
3259:
3147:
3104:
3099:
3064:
2997:
2952:
2938:
2883:
2837:10.2307/1995158
2812:
2807:
2799:
2795:
2780:
2753:
2749:
2739:
2737:
2729:Kwang Yul Seo.
2727:
2723:
2711:
2707:
2701:quantification.
2693:
2691:
2689:www.haskell.org
2683:
2682:
2678:
2668:
2666:
2656:
2652:
2642:
2640:
2632:Yorgey, Brent.
2630:
2626:
2570:
2566:
2559:
2540:
2525:
2521:
2494:
2452:
2438:
2415:
2413:
2410:
2409:
2365:
2359:
2347:typed λ-calculi
2308:
2305:
2304:
2281:
2211:
2208:
2207:
2164:
2161:
2160:
2132:
2129:
2128:
2080:
2077:
2076:
2033:
2030:
2029:
2026:
1970:
1969:
1967:
1964:
1963:
1931:
1930:
1928:
1925:
1924:
1908:
1905:
1904:
1884:
1881:
1880:
1864:
1861:
1860:
1780:
1779:
1777:
1774:
1773:
1738:
1737:
1735:
1732:
1731:
1692:
1681:
1675:
1672:
1661:
1649:
1638:
1633:
1549:
1518:
1515:
1514:
1480:
1479:
1477:
1474:
1473:
1450:
1449:
1447:
1444:
1443:
1442:in the call to
1417:
1416:
1414:
1411:
1410:
1394:
1391:
1390:
1367:
1366:
1364:
1361:
1360:
1344:
1341:
1340:
1308:
1307:
1283:
1282:
1280:
1277:
1276:
1259:
1258:
1218:
1206:
1205:
1202:
1201:
1161:
1149:
1148:
1144:
1142:
1139:
1138:
1108:
1107:
1105:
1102:
1101:
1078:
1077:
1075:
1072:
1071:
1039:
1038:
1036:
1033:
1032:
1012:
1011:
1009:
1006:
1005:
989:
986:
985:
980:are said to be
949:
948:
946:
943:
942:
922:
921:
919:
916:
915:
832:
831:
829:
826:
825:
806:
803:
802:
780:
777:
776:
747:
746:
722:
721:
697:
696:
691:
688:
687:
661:
660:
639:
638:
617:
616:
611:
608:
607:
575:
574:
572:
569:
568:
528:
527:
525:
522:
521:
502:
499:
498:
450:
449:
447:
444:
443:
409:
408:
406:
403:
402:
370:
369:
345:
344:
342:
339:
338:
312:
311:
293:
292:
290:
287:
286:
263:
262:
247:
246:
244:
241:
240:
205:
204:
202:
199:
198:
192:
137:
95:Double dispatch
17:
12:
11:
5:
3659:
3649:
3648:
3643:
3638:
3621:
3620:
3618:
3617:
3612:
3607:
3602:
3597:
3592:
3587:
3582:
3577:
3572:
3571:
3570:
3560:
3555:
3553:Data structure
3550:
3545:
3539:
3537:
3531:
3530:
3528:
3527:
3522:
3517:
3512:
3507:
3502:
3497:
3492:
3487:
3482:
3477:
3472:
3467:
3462:
3457:
3452:
3446:
3444:
3440:
3439:
3437:
3436:
3435:
3434:
3424:
3419:
3414:
3409:
3404:
3399:
3398:
3397:
3387:
3382:
3377:
3372:
3367:
3362:
3357:
3352:
3347:
3346:
3345:
3334:
3332:
3326:
3325:
3323:
3322:
3321:
3320:
3310:
3304:
3302:
3296:
3295:
3293:
3292:
3287:
3286:
3285:
3280:
3269:
3267:
3261:
3260:
3258:
3257:
3252:
3247:
3246:
3245:
3235:
3234:
3233:
3232:
3231:
3221:
3216:
3211:
3206:
3201:
3200:
3199:
3194:
3192:Half precision
3189:
3179:Floating point
3176:
3171:
3166:
3161:
3155:
3153:
3149:
3148:
3146:
3145:
3140:
3135:
3130:
3125:
3120:
3114:
3112:
3106:
3105:
3098:
3097:
3090:
3083:
3075:
3069:
3068:
3062:
3046:
3017:10.1.1.117.695
3010:(4): 471–523.
2987:Cardelli, Luca
2983:
2965:(3): 348–375.
2942:
2936:
2900:
2887:
2881:
2857:
2815:
2811:
2808:
2806:
2805:
2793:
2778:
2747:
2735:kseo.github.io
2721:
2705:
2676:
2650:
2624:
2564:
2557:
2522:
2520:
2517:
2516:
2515:
2510:
2505:
2500:
2493:
2490:
2464:
2461:
2458:
2455:
2451:
2447:
2444:
2441:
2437:
2433:
2430:
2426:
2421:
2418:
2361:Main article:
2358:
2355:
2327:
2324:
2321:
2318:
2315:
2312:
2280:
2277:
2273:Type inference
2269:polymorphic".
2254:
2251:
2248:
2245:
2242:
2239:
2236:
2233:
2230:
2227:
2224:
2221:
2218:
2215:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2136:
2105:
2102:
2099:
2096:
2093:
2090:
2087:
2084:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2025:
2022:
2007:type inference
1988:
1985:
1982:
1979:
1976:
1973:
1949:
1946:
1943:
1940:
1937:
1934:
1912:
1888:
1868:
1857:
1856:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1798:
1795:
1792:
1789:
1786:
1783:
1756:
1753:
1750:
1747:
1744:
1741:
1694:
1693:
1652:
1650:
1643:
1637:
1634:
1632:
1629:
1548:
1545:
1525:
1522:
1489:
1486:
1483:
1459:
1456:
1453:
1429:
1426:
1423:
1420:
1398:
1376:
1373:
1370:
1348:
1328:
1325:
1320:
1317:
1314:
1311:
1306:
1303:
1300:
1297:
1292:
1289:
1286:
1273:
1272:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1219:
1215:
1212:
1209:
1204:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1162:
1158:
1155:
1152:
1147:
1146:
1117:
1114:
1111:
1087:
1084:
1081:
1057:
1054:
1051:
1048:
1045:
1042:
1018:
1015:
993:
967:
964:
961:
958:
955:
952:
928:
925:
909:
908:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
850:
847:
844:
841:
838:
835:
810:
790:
787:
784:
764:
759:
756:
753:
750:
745:
742:
739:
734:
731:
728:
725:
720:
717:
714:
709:
706:
703:
700:
695:
675:
670:
667:
664:
659:
656:
653:
648:
645:
642:
637:
634:
631:
626:
623:
620:
615:
593:
590:
587:
584:
581:
578:
559:function that
546:
543:
540:
537:
534:
531:
506:
491:
490:
479:
476:
473:
470:
467:
464:
461:
456:
453:
415:
412:
388:
385:
382:
379:
376:
373:
368:
363:
360:
357:
354:
351:
348:
324:
321:
318:
315:
310:
305:
302:
299:
296:
272:
269:
266:
261:
256:
253:
250:
228:
225:
222:
219:
216:
211:
208:
191:
188:
139:
138:
136:
135:
128:
121:
113:
110:
109:
108:
107:
102:
97:
92:
87:
79:
78:
72:
71:
70:
69:
64:
56:
55:
49:
48:
47:
46:
41:
33:
32:
26:
25:
15:
9:
6:
4:
3:
2:
3658:
3647:
3644:
3642:
3639:
3637:
3634:
3633:
3631:
3616:
3613:
3611:
3608:
3606:
3603:
3601:
3598:
3596:
3593:
3591:
3588:
3586:
3583:
3581:
3578:
3576:
3573:
3569:
3566:
3565:
3564:
3561:
3559:
3556:
3554:
3551:
3549:
3546:
3544:
3541:
3540:
3538:
3532:
3526:
3523:
3521:
3518:
3516:
3513:
3511:
3508:
3506:
3503:
3501:
3498:
3496:
3493:
3491:
3488:
3486:
3483:
3481:
3478:
3476:
3475:Function type
3473:
3471:
3468:
3466:
3463:
3461:
3458:
3456:
3453:
3451:
3448:
3447:
3445:
3441:
3433:
3430:
3429:
3428:
3425:
3423:
3420:
3418:
3415:
3413:
3410:
3408:
3405:
3403:
3400:
3396:
3393:
3392:
3391:
3388:
3386:
3383:
3381:
3378:
3376:
3373:
3371:
3368:
3366:
3363:
3361:
3358:
3356:
3353:
3351:
3348:
3344:
3341:
3340:
3339:
3336:
3335:
3333:
3331:
3327:
3319:
3316:
3315:
3314:
3311:
3309:
3306:
3305:
3303:
3301:
3297:
3291:
3288:
3284:
3281:
3279:
3276:
3275:
3274:
3271:
3270:
3268:
3266:
3262:
3256:
3253:
3251:
3248:
3244:
3241:
3240:
3239:
3236:
3230:
3227:
3226:
3225:
3222:
3220:
3217:
3215:
3212:
3210:
3207:
3205:
3202:
3198:
3195:
3193:
3190:
3188:
3185:
3184:
3182:
3181:
3180:
3177:
3175:
3172:
3170:
3167:
3165:
3162:
3160:
3157:
3156:
3154:
3150:
3144:
3141:
3139:
3136:
3134:
3131:
3129:
3126:
3124:
3121:
3119:
3116:
3115:
3113:
3111:
3110:Uninterpreted
3107:
3103:
3096:
3091:
3089:
3084:
3082:
3077:
3076:
3073:
3065:
3059:
3056:. MIT Press.
3055:
3051:
3047:
3043:
3039:
3035:
3031:
3027:
3023:
3018:
3013:
3009:
3005:
3004:
2996:
2992:
2991:Wegner, Peter
2988:
2984:
2980:
2976:
2972:
2968:
2964:
2960:
2959:
2951:
2947:
2946:Milner, Robin
2943:
2939:
2933:
2929:
2925:
2921:
2917:
2913:
2909:
2905:
2901:
2896:
2892:
2888:
2884:
2882:9780720422597
2878:
2874:
2870:
2866:
2862:
2858:
2854:
2850:
2846:
2842:
2838:
2834:
2830:
2826:
2825:
2820:
2816:
2814:
2813:
2802:
2797:
2789:
2785:
2781:
2775:
2770:
2765:
2761:
2760:
2751:
2736:
2732:
2725:
2718:
2714:
2709:
2702:
2690:
2686:
2680:
2665:
2661:
2658:Wu, Brandon.
2654:
2639:
2635:
2628:
2620:
2616:
2612:
2608:
2604:
2600:
2596:
2592:
2588:
2580:
2579:
2574:
2568:
2560:
2554:
2551:. MIT Press.
2550:
2549:
2544:
2538:
2536:
2534:
2532:
2530:
2528:
2523:
2514:
2511:
2509:
2506:
2504:
2501:
2499:
2498:Parametricity
2496:
2495:
2489:
2487:
2483:
2479:
2445:
2442:
2439:
2431:
2424:
2407:
2403:
2399:
2395:
2391:
2387:
2383:
2378:
2374:
2370:
2369:Luca Cardelli
2364:
2354:
2352:
2348:
2344:
2339:
2325:
2319:
2316:
2313:
2302:
2297:
2296:impredicative
2293:
2289:
2286:(also called
2285:
2276:
2274:
2270:
2268:
2252:
2243:
2234:
2228:
2225:
2222:
2193:
2184:
2178:
2175:
2172:
2158:
2154:
2150:
2126:
2122:
2117:
2100:
2094:
2091:
2088:
2062:
2053:
2047:
2044:
2041:
2021:
2019:
2015:
2010:
2008:
2004:
1910:
1902:
1901:impredicative
1886:
1866:
1840:
1828:
1822:
1816:
1810:
1807:
1801:
1772:
1771:
1770:
1728:
1726:
1722:
1718:
1714:
1710:
1708:
1703:
1702:
1690:
1687:
1679:
1676:February 2019
1669:
1665:
1659:
1658:
1653:This section
1651:
1647:
1642:
1641:
1628:
1626:
1623:
1618:
1614:
1610:
1606:
1602:
1598:
1594:
1590:
1586:
1582:
1581:Visual Prolog
1578:
1574:
1570:
1566:
1562:
1558:
1554:
1544:
1542:
1538:
1523:
1512:
1508:
1503:
1396:
1346:
1304:
1301:
1255:
1249:
1246:
1243:
1240:
1237:
1231:
1228:
1222:
1220:
1198:
1192:
1189:
1186:
1183:
1180:
1174:
1171:
1165:
1163:
1137:
1136:
1135:
1133:
991:
983:
912:
892:
880:
874:
868:
862:
859:
853:
824:
823:
822:
808:
785:
715:
632:
566:
562:
518:
504:
496:
477:
471:
468:
465:
459:
442:
441:
440:
438:
437:type variable
435:
431:
226:
223:
217:
197:
187:
185:
181:
176:
174:
170:
166:
162:
158:
154:
150:
146:
134:
129:
127:
122:
120:
115:
114:
112:
111:
106:
103:
101:
98:
96:
93:
91:
88:
86:
83:
82:
81:
80:
77:
74:
73:
68:
65:
63:
60:
59:
58:
57:
54:
51:
50:
45:
42:
40:
37:
36:
35:
34:
31:
28:
27:
24:
21:
20:
3574:
3380:Intersection
3053:
3007:
3001:
2962:
2956:
2919:
2911:
2894:
2864:
2828:
2822:
2796:
2756:
2750:
2740:30 September
2738:. Retrieved
2734:
2724:
2716:
2708:
2699:
2692:. Retrieved
2688:
2679:
2667:. Retrieved
2663:
2653:
2641:. Retrieved
2637:
2627:
2597:(1): 11–49.
2594:
2590:
2577:
2567:
2547:
2397:
2393:
2389:
2385:
2376:
2373:Peter Wegner
2366:
2340:
2292:formal logic
2287:
2283:
2282:
2271:
2266:
2156:
2152:
2148:
2124:
2120:
2118:
2116:may not be.
2027:
2011:
1900:
1858:
1729:
1724:
1721:type schemas
1720:
1705:
1699:
1697:
1682:
1673:
1662:Please help
1657:verification
1654:
1603:and others.
1550:
1504:
1274:
981:
913:
910:
561:concatenates
519:
495:instantiated
494:
492:
430:most general
193:
183:
177:
168:
164:
152:
142:
52:
23:Polymorphism
3646:Type theory
3610:Type theory
3605:Type system
3455:Bottom type
3402:Option type
3343:generalized
3229:Long double
3174:Fixed point
2382:Standard ML
2351:lambda cube
2343:type theory
2003:type system
1709:polymorphic
1701:predicative
1557:Standard ML
149:type theory
3630:Categories
3515:Empty type
3510:Type class
3460:Collection
3417:Refinement
3395:metaobject
3243:signedness
3102:Data types
2810:References
2779:1581130953
2713:Milner, R.
2406:type class
1597:TypeScript
1541:call sites
1537:quantifier
161:data types
3590:Subtyping
3585:Interface
3568:metaclass
3520:Unit type
3490:Semaphore
3470:Exception
3375:Inductive
3365:Dependent
3330:Composite
3308:Character
3290:Reference
3187:Minifloat
3143:Bit array
3034:0360-0300
3012:CiteSeerX
2831:: 29–60,
2694:1 October
2669:1 October
2643:1 October
2611:1573-0557
2450:→
2443:α
2436:→
2432:α
2429:⇒
2425:α
2367:In 1985,
2326:α
2323:→
2320:α
2314:α
2311:∀
2250:→
2241:→
2235:α
2232:→
2229:α
2223:α
2220:∀
2191:→
2185:α
2182:→
2179:α
2173:α
2170:∀
2135:∀
2101:α
2098:→
2095:α
2089:α
2086:∀
2060:→
2054:α
2051:→
2048:α
2042:α
2039:∀
1887:α
1841:α
1835:→
1829:α
1823:×
1817:α
1808:α
1805:∀
1725:monotypes
1524:α
1521:∀
1397:β
1347:α
1256:β
1253:→
1250:β
1247:×
1244:α
1238:β
1235:∀
1229:α
1226:∀
1199:α
1196:→
1193:β
1190:×
1187:α
1181:β
1178:∀
1172:α
1169:∀
992:α
893:α
887:→
881:α
875:×
869:α
860:α
857:∀
741:→
716:×
655:→
633:×
505:α
478:α
475:→
472:α
466:α
463:∀
367:→
309:→
260:→
157:functions
76:Subtyping
3615:Variable
3505:Top type
3370:Equality
3278:physical
3255:Rational
3250:Interval
3197:bfloat16
3052:(2002).
2948:(1978).
2906:(1974),
2893:(1972),
2788:14183560
2619:14124601
2575:(1967),
2545:(2002).
2492:See also
2478:subtypes
2301:System F
2206:but not
1903:system,
3558:Generic
3534:Related
3450:Boolean
3407:Product
3283:virtual
3273:Address
3265:Pointer
3238:Integer
3169:Decimal
3164:Complex
3152:Numeric
3042:2921816
2853:0253905
2845:1995158
2402:Haskell
1577:Mercury
1573:Haskell
1547:History
1511:Haskell
1004:. Both
184:uniform
3548:Boxing
3536:topics
3495:Stream
3432:tagged
3390:Object
3313:String
3060:
3040:
3032:
3014:
2979:388583
2977:
2934:
2879:
2851:
2843:
2786:
2776:
2617:
2609:
2555:
2377:bounds
1707:prenex
1617:Delphi
1593:Python
1513:, the
1507:syntax
3443:Other
3427:Union
3360:Class
3350:Array
3133:Tryte
3038:S2CID
2998:(PDF)
2975:S2CID
2953:(PDF)
2841:JSTOR
2784:S2CID
2615:S2CID
2519:Notes
2014:OCaml
1717:Nuprl
1698:In a
1589:Julia
1585:Scala
1561:OCaml
565:lists
3563:Kind
3525:Void
3385:List
3300:Text
3138:Word
3128:Trit
3123:Byte
3058:ISBN
3030:ISSN
2932:ISBN
2877:ISBN
2774:ISBN
2742:2022
2696:2022
2671:2022
2645:2022
2607:ISSN
2553:ISBN
2484:and
2371:and
1715:and
1615:and
1605:Java
1505:The
1389:and
1132:pair
1100:and
1031:and
941:and
563:two
167:and
159:and
147:and
3422:Set
3118:Bit
3022:doi
2967:doi
2924:doi
2869:doi
2833:doi
2829:146
2764:doi
2599:doi
2488:).
2398:’’a
2394:’’a
2390:’’a
2386:’’a
2341:In
1666:by
1622:C++
1601:C++
1569:Ada
143:In
3632::
3036:.
3028:.
3020:.
3008:17
3006:.
3000:.
2989:;
2973:.
2963:17
2961:.
2955:.
2930:,
2920:19
2918:,
2914:,
2910:,
2875:.
2849:MR
2847:,
2839:,
2827:,
2782:.
2772:.
2733:.
2698:.
2687:.
2662:.
2636:.
2613:.
2605:.
2595:13
2593:.
2589:.
2526:^
2392:Ă—
2018:ML
1727:.
1627:.
1611:,
1609:C#
1607:,
1599:,
1595:,
1591:,
1587:,
1583:,
1579:,
1575:,
1571:,
1567:,
1565:F#
1563:,
1559:,
1553:ML
1543:.
1502:.
1339:,
686:,
439::
337:,
285:,
175:.
151:,
3094:e
3087:t
3080:v
3066:.
3044:.
3024::
2981:.
2969::
2941:.
2926::
2899:.
2885:.
2871::
2856:.
2835::
2803:.
2790:.
2766::
2744:.
2673:.
2647:.
2621:.
2601::
2561:.
2463:l
2460:o
2457:o
2454:B
2446:]
2440:[
2420:q
2417:E
2317:.
2267:n
2253:T
2247:)
2244:T
2238:)
2226:.
2217:(
2214:(
2194:T
2188:)
2176:.
2167:(
2157:k
2153:k
2149:k
2125:k
2121:k
2104:]
2092:.
2083:[
2063:T
2057:)
2045:.
2036:(
1987:d
1984:n
1981:e
1978:p
1975:p
1972:a
1948:d
1945:n
1942:e
1939:p
1936:p
1933:a
1911:T
1867:T
1844:]
1838:[
1832:]
1826:[
1820:]
1814:[
1811:.
1802::
1797:d
1794:n
1791:e
1788:p
1785:p
1782:a
1755:d
1752:n
1749:e
1746:p
1743:p
1740:a
1689:)
1683:(
1678:)
1674:(
1660:.
1488:t
1485:n
1482:I
1458:t
1455:s
1452:f
1428:l
1425:o
1422:o
1419:B
1375:t
1372:n
1369:I
1327:)
1324:)
1319:e
1316:u
1313:r
1310:t
1305:,
1302:3
1299:(
1296:(
1291:t
1288:s
1285:f
1241:.
1232:.
1223::
1214:d
1211:n
1208:s
1184:.
1175:.
1166::
1157:t
1154:s
1151:f
1116:d
1113:n
1110:s
1086:t
1083:s
1080:f
1056:d
1053:n
1050:e
1047:p
1044:p
1041:a
1017:d
1014:i
966:d
963:n
960:e
957:p
954:p
951:a
927:d
924:i
896:]
890:[
884:]
878:[
872:]
866:[
863:.
854::
849:d
846:n
843:e
840:p
837:p
834:a
809:T
789:]
786:T
783:[
763:]
758:l
755:o
752:o
749:B
744:[
738:]
733:l
730:o
727:o
724:B
719:[
713:]
708:l
705:o
702:o
699:B
694:[
674:]
669:t
666:n
663:I
658:[
652:]
647:t
644:n
641:I
636:[
630:]
625:t
622:n
619:I
614:[
592:d
589:n
586:e
583:p
580:p
577:a
545:d
542:n
539:e
536:p
533:p
530:a
469:.
460::
455:d
452:i
414:d
411:i
387:g
384:n
381:i
378:r
375:t
372:S
362:g
359:n
356:i
353:r
350:t
347:S
323:l
320:o
317:o
314:B
304:l
301:o
298:o
295:B
271:t
268:n
265:I
255:t
252:n
249:I
227:x
224:=
221:)
218:x
215:(
210:d
207:i
132:e
125:t
118:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.