<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:dc="http://purl.org/dc/elements/1.1/">
  <channel>
    <title>DEV Community: Anton Harnik</title>
    <description>The latest articles on DEV Community by Anton Harnik (@ohtoh04).</description>
    <link>https://dev.to/ohtoh04</link>
    <image>
      <url>https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F4220655%2F533bf955-1746-44b2-8770-6f51c71d147f.png</url>
      <title>DEV Community: Anton Harnik</title>
      <link>https://dev.to/ohtoh04</link>
    </image>
    <atom:link rel="self" type="application/rss+xml" href="https://dev.to/feed/ohtoh04"/>
    <language>en</language>
    <item>
      <title>Polymorphism in Programming Languages</title>
      <dc:creator>Anton Harnik</dc:creator>
      <pubDate>Wed, 18 Nov 2026 10:04:39 +0000</pubDate>
      <link>https://dev.to/ohtoh04/polymorphism-in-programming-languages-2p18</link>
      <guid>https://dev.to/ohtoh04/polymorphism-in-programming-languages-2p18</guid>
      <description>&lt;p&gt;In this article we'll summarize the classical literature that defines the kinds of polymorphism found in programming languages. As there is a lot of inconsistency in online material, I felt an urge to structurize the knowledge, offering a comprehensive breakdown of polymoprhism into categories, providing links to credible sources. The examples of polymorphism will be given in C#, since it's my primary language.&lt;/p&gt;




&lt;h2&gt;
  
  
  1 TERMINOLOGY AND CLASSIFICATION
&lt;/h2&gt;

&lt;p&gt;&lt;strong&gt;Polymorphism&lt;/strong&gt; is the property of a program fragment, such as a function, an operator, or a value, that can be used at more than one type. Polymorphic languages are those languages in which some values and variables have more than one type, in contrast to &lt;strong&gt;monomorphic&lt;/strong&gt; languages, in which every value and variable has exactly one type [2].&lt;/p&gt;

&lt;p&gt;There are two classifications of polymorphism commonly use:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;The &lt;strong&gt;static/dynamic&lt;/strong&gt; classification&lt;/li&gt;
&lt;li&gt;The &lt;strong&gt;universal/ad hoc&lt;/strong&gt; classification&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Static/dynamic classification describes when the implementation is selected: at compile time or at run time. Unversal/ad hoc classification describes how the code is shared: one implementation for all types, or a separate implementation for each type.&lt;/p&gt;

&lt;h3&gt;
  
  
  1.1 Static and Dynamic Polymorphism
&lt;/h3&gt;

&lt;p&gt;The &lt;strong&gt;static type&lt;/strong&gt; of an expression is the type the compiler assigns to it from the source code. The &lt;strong&gt;run-time type&lt;/strong&gt; is the type of the object the expression actually refers to during execution. The two classes of polymorphism differ in which of these types determines the implementation.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;Static (compile-time) polymorphism&lt;/strong&gt; selects the implementation from the static types of the arguments. The selection is fixed once the code compiles. The language constructs that fall under static polymorphism:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Overloading&lt;/strong&gt; – a language feature in which several methods share the same name but have different parameter lists. It lets the compiler select the applicable method at compile time based on the static types and number of the arguments.
&lt;/li&gt;
&lt;/ul&gt;

&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;    &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; $&lt;span class="s2"&gt;"int {x}"&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; $&lt;span class="s2"&gt;"string {s}"&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;     &lt;span class="c1"&gt;// compiler selects Describe(int)&lt;/span&gt;
&lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"hi"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// compiler selects Describe(string)&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;



&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Generics&lt;/strong&gt; – a language feature that lets you define types and methods with type parameters. They let one generic definition be reused with many concrete types while preserving static type safety; at each use site, the compiler infers or checks the type argument and fixes the instantiation during compilation.
&lt;/li&gt;
&lt;/ul&gt;

&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;     &lt;span class="c1"&gt;// T = int&lt;/span&gt;
&lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"hi"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// T = string&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;


&lt;/li&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;Dynamic (run-time) polymorphism&lt;/strong&gt; selects the implementation from the run-time type of an object. This selection is called &lt;strong&gt;dynamic dispatch&lt;/strong&gt;. The language constructs that fall under dynamic polymorphism:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Virtual methods&lt;/strong&gt; – instance methods declared with the virtual modifier (and their override implementations in derived classes) that participate in runtime dispatch. When such a method is called through a reference, the override associated with the receiver’s run-time type is invoked, regardless of the static type of the reference.
&lt;/li&gt;
&lt;/ul&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;abstract&lt;/span&gt; &lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;abstract&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Circle&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;r&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;override&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="nc"&gt;Math&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;PI&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="n"&gt;r&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="n"&gt;r&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Square&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;side&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;override&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;side&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="n"&gt;side&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nc"&gt;Random&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Shared&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Next&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt; &lt;span class="o"&gt;?&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;Circle&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;Square&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// Circle.Area or Square.Area, selected at run time&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;


&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;The &lt;code&gt;dynamic&lt;/code&gt; keyword&lt;/strong&gt;, which defers overload resolution from compile time to run time.
&lt;/li&gt;
&lt;/ul&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;object&lt;/span&gt; &lt;span class="n"&gt;o&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="s2"&gt;"something"&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="k"&gt;object&lt;/span&gt; &lt;span class="n"&gt;o&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="s2"&gt;"hi"&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;o&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;            &lt;span class="c1"&gt;// "something": selected from the static type, object&lt;/span&gt;
&lt;span class="nc"&gt;Describe&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;dynamic&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="n"&gt;o&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// "string hi": selected from the run-time type, string&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;


&lt;p&gt;The first call in this example illustrates a common misconception: overload resolution always uses the static type, so the compiler selects &lt;code&gt;Describe(object)&lt;/code&gt; even though &lt;code&gt;o&lt;/code&gt; refers to a string at run time.&lt;/p&gt;
&lt;/li&gt;
&lt;/ul&gt;

&lt;blockquote&gt;
&lt;p&gt;Note&lt;/p&gt;
&lt;p&gt;
The same distinction appears under the names early binding and late binding, or equivalently static binding and dynamic binding. A binding is the association of a name – a method call, a member access – with the implementation it denotes. Overload resolution and generic instantiation are resolved at compile time and are therefore early-bound; the choice of a virtual override, and every member access on a dynamic expression, is resolved at run time and is therefore late-bound. The pairs overlap closely with static/dynamic polymorphism, but they answer different questions: binding terms describe when a name is resolved, while static/dynamic describe which types a piece of code works for.&lt;/p&gt;
&lt;/blockquote&gt;
&lt;h3&gt;
  
  
  1.2 Universal and Ad Hoc Polymorphism
&lt;/h3&gt;

&lt;p&gt;The second classification originates with Cardelli and Wegner [2] and is the standard one in type theory. It separates universal from ad hoc polymorphism.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;Universal polymorphism&lt;/strong&gt; uses one implementation for an unbounded range of types. The forms of universal polymorphism are:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Parametric polymorphism&lt;/strong&gt; – a form of universal polymorphism in which code is written over one or more type parameters instead of concrete types. The code never inspects values of the parameterized type, so it behaves identically for every type argument.
&lt;/li&gt;
&lt;/ul&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="nc"&gt;Count&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;List&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;items&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;items&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Count&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// same code for List&amp;lt;int&amp;gt;, List&amp;lt;string&amp;gt;, ...&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;


&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Inclusion polymorphism&lt;/strong&gt;, also called &lt;strong&gt;subtype polymorphism&lt;/strong&gt; – a form of universal polymorphism in which a value of a subtype can be used wherever a value of its base type is expected. Code written against a base type therefore accepts every subtype of that base type, including subtypes defined later.
&lt;/li&gt;
&lt;/ul&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;TotalArea&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;IEnumerable&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="nc"&gt;Shape&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;shapes&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;shapes&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="c1"&gt;// accepts Circle, Square, and any other subtype of Shape&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/li&gt;
&lt;li&gt;
&lt;p&gt;&lt;strong&gt;Ad hoc polymorphism&lt;/strong&gt; applies one name to a finite set of possibly unrelated types, usually with separate code for each type. The forms of ad hoc polymorphism are:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Overloading&lt;/strong&gt; – a form of ad hoc polymorphism in which one name denotes several distinct implementations, one for each of a finite set of types or type combinations. Each implementation is written separately, and the choice among them is made at compile time.
&lt;/li&gt;
&lt;/ul&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt;    &lt;span class="nc"&gt;Twice&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;    &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Twice&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;


&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Coercion&lt;/strong&gt; – a form of ad hoc polymorphism in which a value is implicitly converted to the type that a function expects. The function itself is written for one type, and values of other types are adapted to it rather than handled by separate implementations.
&lt;/li&gt;
&lt;/ul&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Half&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;/&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Half&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;5&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// the int 5 is converted to the double 5.0&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/li&gt;
&lt;/ul&gt;
&lt;h3&gt;
  
  
  1.3 Relationship Between the Two Classifications
&lt;/h3&gt;

&lt;p&gt;The two classifications are independent. The family of a mechanism does not determine its binding time, and the binding time does not determine its family. Every mechanism therefore occupies a position on both axes:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Overloading&lt;/strong&gt; is ad hoc and static.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Overloading through &lt;code&gt;dynamic&lt;/code&gt;&lt;/strong&gt; is ad hoc and dynamic.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Generics&lt;/strong&gt; are parametric and static.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Virtual methods&lt;/strong&gt; invoked through a base type are inclusion and dynamic.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Introductory material on object-oriented programming commonly uses "polymorphism" to mean only one of these combinations: virtual methods, that is, inclusion polymorphism with dynamic dispatch. The term "compile-time polymorphism" in the same material usually refers to overloading. Both are genuine forms of polymorphism, and neither covers the whole concept.&lt;/p&gt;


&lt;h2&gt;
  
  
  2 ORIGIN OF THE TERMINOLOGY
&lt;/h2&gt;

&lt;p&gt;The distinction between two kinds of polymorphism were introduced in Christopher Strachey's lecture notes  delivered at the International Summer School in Computer Programming in Copenhagen in 1967 [1]. The notes circulate informally for decades and appear in print in 2000 in a memorial issue of &lt;em&gt;Higher-Order and Symbolic Computation&lt;/em&gt;.&lt;/p&gt;

&lt;p&gt;Strachey separates the two kinds as follows.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Ad hoc polymorphism&lt;/strong&gt; occurs when a function is defined over several types and behaves differently for each, with no systematic rule relating the argument types to the result type. Arithmetic operators are the characteristic case: integer addition and floating-point addition share a symbol but use different algorithms.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Parametric polymorphism&lt;/strong&gt; occurs when a function is defined over a range of types and acts in the same way for each type. A list-length function is the characteristic case: it counts elements without inspecting them, so its behavior is identical for lists of integers and lists of strings.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;

&lt;/p&gt;
&lt;div class="katex-element"&gt;
  &lt;span class="katex-display"&gt;&lt;span class="katex"&gt;&lt;span class="katex-mathml"&gt;&lt;/span&gt;&lt;span class="katex-html"&gt;&lt;span class="base"&gt;&lt;span class="strut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mtable"&gt;&lt;span class="col-align-r"&gt;&lt;span class="vlist-t vlist-t2"&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;span class="mord mathit"&gt;length&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mopen"&gt;(&lt;/span&gt;&lt;span class="mord"&gt;+&lt;/span&gt;&lt;span class="mclose"&gt;)&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mopen"&gt;(&lt;/span&gt;&lt;span class="mord"&gt;+&lt;/span&gt;&lt;span class="mclose"&gt;)&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-s"&gt;​&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="col-align-l"&gt;&lt;span class="vlist-t vlist-t2"&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;:&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;∀&lt;/span&gt;&lt;span class="mord mathnormal"&gt;α&lt;/span&gt;&lt;span class="mord"&gt;.&lt;/span&gt;&lt;span class="mspace"&gt;&amp;nbsp;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;List&lt;/span&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&amp;nbsp;&lt;/span&gt;&lt;span class="mord mathnormal"&gt;α&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;→&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Int&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;:&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Int&lt;/span&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;→&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Int&lt;/span&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;→&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Int&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;:&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Double&lt;/span&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;→&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Double&lt;/span&gt;&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mrel"&gt;→&lt;/span&gt;&lt;span class="mspace"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord mathsf"&gt;Double&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-s"&gt;​&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="arraycolsep"&gt;&lt;/span&gt;&lt;span class="col-align-r"&gt;&lt;span class="vlist-t vlist-t2"&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-s"&gt;​&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="col-align-l"&gt;&lt;span class="vlist-t vlist-t2"&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;span class="mord text"&gt;&lt;span class="mord"&gt;parametric:&amp;nbsp;one&amp;nbsp;algorithm&amp;nbsp;for&amp;nbsp;every&amp;nbsp;&lt;/span&gt;&lt;/span&gt;&lt;span class="mord mathnormal"&gt;α&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;span class="mord text"&gt;&lt;span class="mord"&gt;ad&amp;nbsp;hoc:&amp;nbsp;integer&amp;nbsp;addition&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span&gt;&lt;span class="pstrut"&gt;&lt;/span&gt;&lt;span class="mord"&gt;&lt;span class="mord"&gt;&lt;/span&gt;&lt;span class="mord text"&gt;&lt;span class="mord"&gt;ad&amp;nbsp;hoc:&amp;nbsp;floating-point&amp;nbsp;addition&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-s"&gt;​&lt;/span&gt;&lt;/span&gt;&lt;span class="vlist-r"&gt;&lt;span class="vlist"&gt;&lt;span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;
&lt;/div&gt;


&lt;p&gt;I wouldn’t rely on these notes as a definitive source of truth for categorizing polymorphism, as they are informal and contain no type system. Their lasting contribution is the vocabulary itself, which was later widely adopted. The categorization, however, has changed since then, and we’ll look at those changes next.&lt;/p&gt;




&lt;h2&gt;
  
  
  3 THE CARDELLI–WEGNER TAXONOMY
&lt;/h2&gt;

&lt;h3&gt;
  
  
  3.1 Universal and Ad Hoc Polymorphism
&lt;/h3&gt;

&lt;p&gt;The first comprehensive taxonomy came form Cardelli and Wegner in 1985 [2], which refined Strachey's distinction into the classification that serves as the standard reference up to this day. The top-level division separates &lt;strong&gt;universal polymorphism&lt;/strong&gt;, in which a single piece of code works uniformly on a potentially infinite range of types that share a common structure, from &lt;strong&gt;ad hoc polymorphism&lt;/strong&gt;, in which a name works, or appears to work, on a finite set of possibly unrelated types, often by executing different code for each. Universal polymorphism can be regarded as polymorphism in the strict sense and ad hoc polymorphism as an apparent form that a translation step can eliminate.&lt;/p&gt;

&lt;p&gt;Each family is further divided into two forms, as shown in Figure 3.1.&lt;/p&gt;

&lt;p&gt;&lt;a href="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2F9p6r3xcmmi46noygir5j.png" class="article-body-image-wrapper"&gt;&lt;img src="https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2F9p6r3xcmmi46noygir5j.png" alt="Picture 3.1 – The two families of polymorphism and their forms" width="712" height="356"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;Form&lt;/th&gt;
&lt;th&gt;Family&lt;/th&gt;
&lt;th&gt;Range of types&lt;/th&gt;
&lt;th&gt;Implementations&lt;/th&gt;
&lt;th&gt;Characteristic mechanism&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;Parametric&lt;/td&gt;
&lt;td&gt;Universal&lt;/td&gt;
&lt;td&gt;Unbounded; determined by a type parameter&lt;/td&gt;
&lt;td&gt;One, uniform&lt;/td&gt;
&lt;td&gt;Generic functions; &lt;code&gt;∀&lt;/code&gt;-types&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Inclusion&lt;/td&gt;
&lt;td&gt;Universal&lt;/td&gt;
&lt;td&gt;Every subtype of a given type&lt;/td&gt;
&lt;td&gt;One, written against the supertype&lt;/td&gt;
&lt;td&gt;Subtyping; subclassing&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Overloading&lt;/td&gt;
&lt;td&gt;Ad hoc&lt;/td&gt;
&lt;td&gt;Finite and enumerated&lt;/td&gt;
&lt;td&gt;One per type&lt;/td&gt;
&lt;td&gt;Overloaded names and operators&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Coercion&lt;/td&gt;
&lt;td&gt;Ad hoc&lt;/td&gt;
&lt;td&gt;Finite; closed under the available conversions&lt;/td&gt;
&lt;td&gt;One, plus implicit conversions&lt;/td&gt;
&lt;td&gt;Implicit numeric widening&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;

&lt;h3&gt;
  
  
  3.2 Three Quantifiers
&lt;/h3&gt;

&lt;p&gt;The taxonomy rests on three ideas from type theory, called &lt;em&gt;quantifiers&lt;/em&gt;:&lt;/p&gt;

&lt;p&gt;1 &lt;strong&gt;Universal quantification: generics.&lt;/strong&gt; Recall the example from Section 1.1:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;   &lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

   &lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;     &lt;span class="c1"&gt;// T = int&lt;/span&gt;
   &lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"hi"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// T = string&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Without polymorphism, even the identity function has to be written once per type, as &lt;code&gt;IdInt(int x)&lt;/code&gt;, &lt;code&gt;IdBool(bool x)&lt;/code&gt;, and so on, with identical bodies. The generic &lt;code&gt;Id&amp;lt;T&amp;gt;&lt;/code&gt; replaces all of them with one definition.&lt;/p&gt;

&lt;p&gt;In type theory, &lt;code&gt;Id&lt;/code&gt; has the type &lt;code&gt;∀T. T → T&lt;/code&gt;, read "for every type &lt;code&gt;T&lt;/code&gt;, a function from &lt;code&gt;T&lt;/code&gt; to &lt;code&gt;T&lt;/code&gt;". Here &lt;code&gt;T&lt;/code&gt; is a &lt;strong&gt;type variable&lt;/strong&gt;, a placeholder that ranges over types, and a type of this form is &lt;strong&gt;universally quantified&lt;/strong&gt;. Supplying a concrete type, as in &lt;code&gt;Id&amp;lt;int&amp;gt;&lt;/code&gt;, is called &lt;strong&gt;instantiation&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;The formal calculus behind universal quantification is System F, discovered independently by Girard [3] and Reynolds [4] in the early 1970s. Section 4 looks at it in more detail.&lt;/p&gt;

&lt;p&gt;2 &lt;strong&gt;Existential quantification: hidden representations.&lt;/strong&gt; A universal type says "this works for every type". Its mirror image, an existential type &lt;code&gt;∃T. …&lt;/code&gt;, says "there is &lt;em&gt;some&lt;/em&gt; type here, but you don't get to know which". In C#, the closest everyday equivalent is an interface backed by private state:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;   &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;interface&lt;/span&gt; &lt;span class="nc"&gt;IPoint&lt;/span&gt;
   &lt;span class="p"&gt;{&lt;/span&gt;
       &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="nc"&gt;GetX&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
   &lt;span class="p"&gt;}&lt;/span&gt;

   &lt;span class="k"&gt;sealed&lt;/span&gt; &lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;IntPoint&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IPoint&lt;/span&gt;
   &lt;span class="p"&gt;{&lt;/span&gt;
       &lt;span class="k"&gt;private&lt;/span&gt; &lt;span class="k"&gt;readonly&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;_x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
       &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="nc"&gt;IntPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;_x&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
       &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="nc"&gt;GetX&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;_x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
   &lt;span class="p"&gt;}&lt;/span&gt;

   &lt;span class="k"&gt;sealed&lt;/span&gt; &lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;TuplePoint&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IPoint&lt;/span&gt;
   &lt;span class="p"&gt;{&lt;/span&gt;
       &lt;span class="k"&gt;private&lt;/span&gt; &lt;span class="k"&gt;readonly&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;Y&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="n"&gt;_coords&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
       &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="nc"&gt;TuplePoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;y&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;_coords&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;y&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
       &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="nc"&gt;GetX&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;_coords&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
   &lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Code that receives an &lt;code&gt;IPoint&lt;/code&gt; can call &lt;code&gt;GetX&lt;/code&gt;, but it isn't supposed to care whether an &lt;code&gt;int&lt;/code&gt; or a tuple is inside, so one implementation can replace the other without breaking callers. That is the idea of an abstract data type.&lt;/p&gt;

&lt;p&gt;3 &lt;strong&gt;Subtyping and bounded quantification: constrained generics.&lt;/strong&gt; A type &lt;code&gt;S&lt;/code&gt; is a &lt;strong&gt;subtype&lt;/strong&gt; of &lt;code&gt;T&lt;/code&gt;, written &lt;code&gt;S ≤ T&lt;/code&gt;, when a value of type &lt;code&gt;S&lt;/code&gt; is acceptable wherever a value of type &lt;code&gt;T&lt;/code&gt; is expected. Here &lt;code&gt;Point&lt;/code&gt; and &lt;code&gt;ColorPoint&lt;/code&gt; are both subtypes of &lt;code&gt;IHasX&lt;/code&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;   &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;interface&lt;/span&gt; &lt;span class="nc"&gt;IHasX&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="n"&gt;get&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;

   &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;record&lt;/span&gt; &lt;span class="nc"&gt;Point&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IHasX&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
   &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;record&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Color&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IHasX&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

   &lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="nc"&gt;IHasX&lt;/span&gt; &lt;span class="nc"&gt;Rightmost&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;IHasX&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nc"&gt;IHasX&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;&amp;gt;=&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;?&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;&lt;code&gt;Rightmost&lt;/code&gt; accepts any two values that have an &lt;code&gt;X&lt;/code&gt;, which is inclusion polymorphism as described in Section 1.2. Subtyping on its own loses information, though:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;   &lt;span class="kd"&gt;var&lt;/span&gt; &lt;span class="n"&gt;p&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nc"&gt;Rightmost&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="s2"&gt;"red"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;5&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="s2"&gt;"blue"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
   &lt;span class="nc"&gt;Console&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;WriteLine&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;p&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Color&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// compile error: IHasX has no Color&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The returned object is still a &lt;code&gt;ColorPoint&lt;/code&gt;, but its static type is only &lt;code&gt;IHasX&lt;/code&gt;. &lt;em&gt;Bounded quantification&lt;/em&gt; fixes this by combining a type parameter with a subtype constraint:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;   &lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Rightmost&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="k"&gt;where&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IHasX&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;&amp;gt;=&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;?&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

   &lt;span class="kd"&gt;var&lt;/span&gt; &lt;span class="n"&gt;q&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="nc"&gt;Rightmost&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="s2"&gt;"red"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;5&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="s2"&gt;"blue"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
   &lt;span class="nc"&gt;Console&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;WriteLine&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;q&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Color&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// "blue": T is ColorPoint&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;In type theory, this &lt;code&gt;Rightmost&lt;/code&gt; has the type &lt;code&gt;∀T ≤ IHasX. T → T → T&lt;/code&gt;, read "for every subtype &lt;code&gt;T&lt;/code&gt; of &lt;code&gt;IHasX&lt;/code&gt;". Cardelli and Wegner introduced bounded quantification in [2], and C#'s &lt;code&gt;where T : …&lt;/code&gt; constraints and Java's &lt;code&gt;&amp;lt;T extends …&amp;gt;&lt;/code&gt; are its direct descendants.&lt;/p&gt;

&lt;p&gt;The table below summarizes the three quantifiers.&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;Quantifier&lt;/th&gt;
&lt;th&gt;Read as&lt;/th&gt;
&lt;th&gt;C# counterpart&lt;/th&gt;
&lt;th&gt;Concept&lt;/th&gt;
&lt;th&gt;Covered in&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;&lt;code&gt;∀T. …&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;for every type &lt;code&gt;T&lt;/code&gt;
&lt;/td&gt;
&lt;td&gt;&lt;code&gt;T Id&amp;lt;T&amp;gt;(T x)&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;Parametric polymorphism&lt;/td&gt;
&lt;td&gt;Section 4&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;&lt;code&gt;∃T. …&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;for some hidden type &lt;code&gt;T&lt;/code&gt;
&lt;/td&gt;
&lt;td&gt;An interface over private state&lt;/td&gt;
&lt;td&gt;Abstract data types&lt;/td&gt;
&lt;td&gt;This section&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;&lt;code&gt;∀T ≤ S. …&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;for every subtype &lt;code&gt;T&lt;/code&gt; of &lt;code&gt;S&lt;/code&gt;
&lt;/td&gt;
&lt;td&gt;&lt;code&gt;where T : S&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;Parametric and inclusion polymorphism combined&lt;/td&gt;
&lt;td&gt;Section 5&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;




&lt;h2&gt;
  
  
  4 PARAMETRIC POLYMORPHISM
&lt;/h2&gt;

&lt;h3&gt;
  
  
  4.1 System F: The Polymorphic Lambda Calculus
&lt;/h3&gt;

&lt;p&gt;Let's go back to the identity function from Section 3.2 and look at it closer:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// explicit type argument&lt;/span&gt;
&lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;        &lt;span class="c1"&gt;// type argument inferred by the compiler&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The call &lt;code&gt;Id&amp;lt;int&amp;gt;(42)&lt;/code&gt; happens in two steps. First, the type argument &lt;code&gt;int&lt;/code&gt; is supplied, which turns the generic &lt;code&gt;Id&amp;lt;T&amp;gt;&lt;/code&gt; into an ordinary function &lt;code&gt;int → int&lt;/code&gt;. Then the value &lt;code&gt;42&lt;/code&gt; is passed to that function. This two-step view is the core of &lt;strong&gt;System F&lt;/strong&gt;, also called the &lt;strong&gt;polymorphic lambda calculus&lt;/strong&gt; – a minimal formal language in which functions can take types as parameters, exactly like &lt;code&gt;Id&amp;lt;T&amp;gt;&lt;/code&gt;, and types are supplied explicitly at each use [3], [4]. System F is the standard formal model of parametric polymorphism.&lt;/p&gt;

&lt;p&gt;System F goes further than C# in one important way: a polymorphic function is a value like any other, so it can be passed to and returned from other functions. In C#, a generic method loses its polymorphism as soon as it is turned into a delegate, because a &lt;code&gt;Func&amp;lt;T, T&amp;gt;&lt;/code&gt; needs a concrete &lt;code&gt;T&lt;/code&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="c1"&gt;// Does not compile: T is fixed by the caller, so f cannot accept both an int and a string&lt;/span&gt;
&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="nc"&gt;ApplyToBoth&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;Func&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;f&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nf"&gt;f&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nf"&gt;f&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"hi"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The workaround would be an interface with a generic method, which packages a polymorphic function as an object:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;interface&lt;/span&gt; &lt;span class="nc"&gt;IPolyFunc&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Invoke&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;sealed&lt;/span&gt; &lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Identity&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IPolyFunc&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Invoke&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="nc"&gt;ApplyToBoth&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;IPolyFunc&lt;/span&gt; &lt;span class="n"&gt;f&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;f&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Invoke&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;42&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;f&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Invoke&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"hi"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;ApplyToBoth&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;Identity&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// (42, "hi")&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;In System F, &lt;code&gt;ApplyToBoth&lt;/code&gt; has the type &lt;code&gt;(∀T. T → T) → (Int, String)&lt;/code&gt;: the quantifier sits &lt;em&gt;inside&lt;/em&gt; the parameter type rather than at the front. Types like this are called &lt;strong&gt;higher-rank&lt;/strong&gt; types. System F supports them directly, and it is even &lt;strong&gt;impredicative&lt;/strong&gt; – a type variable can be instantiated with a polymorphic type, including the type of the identity function itself.&lt;/p&gt;

&lt;p&gt;This expressiveness has a price. Type inference for full System F is undecidable, so programs in it have to carry explicit type annotations. The next section describes the restriction that most functional languages adopt to avoid this.&lt;/p&gt;

&lt;h3&gt;
  
  
  4.2 Let-Polymorphism and Hindley–Milner Inference
&lt;/h3&gt;

&lt;p&gt;C# infers type arguments at call sites, but it cannot infer the type of a polymorphic lambda:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="kd"&gt;var&lt;/span&gt; &lt;span class="n"&gt;id&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;            &lt;span class="c1"&gt;// does not compile: the type of x cannot be inferred&lt;/span&gt;
&lt;span class="kd"&gt;var&lt;/span&gt; &lt;span class="n"&gt;idInt&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// compiles, but idInt is Func&amp;lt;int, int&amp;gt;, not polymorphic&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The ML family of languages (Standard ML, OCaml, F#, and, with extensions, Haskell) takes a different approach, known as &lt;strong&gt;Hindley–Milner&lt;/strong&gt; type inference [5]. It infers the most general type of every expression without any annotations, at the cost of restricting where polymorphism may appear. Here is the same idea in F#:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight fsharp"&gt;&lt;code&gt;&lt;span class="k"&gt;let&lt;/span&gt; &lt;span class="nb"&gt;id&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;                  &lt;span class="c1"&gt;// inferred type: 'a -&amp;gt; 'a&lt;/span&gt;
&lt;span class="k"&gt;let&lt;/span&gt; &lt;span class="n"&gt;pair&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nb"&gt;id&lt;/span&gt; &lt;span class="mi"&gt;3&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nb"&gt;id&lt;/span&gt; &lt;span class="kc"&gt;true&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;    &lt;span class="c1"&gt;// id is used at int and at bool&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The system has three defining characteristics:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Type schemes&lt;/strong&gt; – quantifiers appear only at the outermost level of a type, as in &lt;code&gt;∀α. α → α&lt;/code&gt;. The higher-rank type of &lt;code&gt;ApplyToBoth&lt;/code&gt; from Section 4.1 is not expressible.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Let-polymorphism&lt;/strong&gt; – a definition becomes polymorphic only when it is bound with &lt;code&gt;let&lt;/code&gt;. A function parameter stays monomorphic inside the function body, so the following F# expression is rejected, even though it looks equivalent to the one above:
&lt;/li&gt;
&lt;/ul&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight fsharp"&gt;&lt;code&gt;  &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;fun&lt;/span&gt; &lt;span class="nf"&gt;id&lt;/span&gt; &lt;span class="o"&gt;-&amp;gt;&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nb"&gt;id&lt;/span&gt; &lt;span class="mi"&gt;3&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nb"&gt;id&lt;/span&gt; &lt;span class="kc"&gt;true&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;fun&lt;/span&gt; &lt;span class="nf"&gt;x&lt;/span&gt; &lt;span class="o"&gt;-&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;   &lt;span class="c1"&gt;// type error: id cannot be both int -&amp;gt; int and bool -&amp;gt; bool&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Principal types&lt;/strong&gt; – every well-typed expression has a most general type, of which every other valid type is an instance, and the inference algorithm (Algorithm &lt;em&gt;W&lt;/em&gt;) always finds it.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;The same work proves that well-typed programs cannot go wrong at run time [5]. The table below compares the three approaches.&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;Property&lt;/th&gt;
&lt;th&gt;System F&lt;/th&gt;
&lt;th&gt;Hindley–Milner&lt;/th&gt;
&lt;th&gt;C#&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;Quantifier position&lt;/td&gt;
&lt;td&gt;Anywhere in a type&lt;/td&gt;
&lt;td&gt;Outermost only&lt;/td&gt;
&lt;td&gt;Generic methods and types; higher-rank only through interfaces&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Type annotations&lt;/td&gt;
&lt;td&gt;Required&lt;/td&gt;
&lt;td&gt;Not required&lt;/td&gt;
&lt;td&gt;Required on lambdas and members; type arguments inferred at call sites&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Type inference&lt;/td&gt;
&lt;td&gt;Undecidable&lt;/td&gt;
&lt;td&gt;Decidable, with principal types&lt;/td&gt;
&lt;td&gt;Local, per call site&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Impredicativity&lt;/td&gt;
&lt;td&gt;Yes&lt;/td&gt;
&lt;td&gt;No&lt;/td&gt;
&lt;td&gt;No&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;

&lt;h3&gt;
  
  
  4.3 Parametricity and Free Theorems
&lt;/h3&gt;

&lt;p&gt;Parametric code never inspects values of the parameterized type, so it behaves identically for every type argument. This property is called &lt;strong&gt;parametricity&lt;/strong&gt;, and it has a surprisingly strong consequence: the type of a parametric function alone restricts what the function can do [6].&lt;/p&gt;

&lt;p&gt;Let's take the identity function from Section 4.1 once more. A function with the signature &lt;code&gt;T F&amp;lt;T&amp;gt;(T x)&lt;/code&gt; knows nothing about &lt;code&gt;T&lt;/code&gt;: it cannot create a new &lt;code&gt;T&lt;/code&gt;, compare two values of type &lt;code&gt;T&lt;/code&gt;, or call any method on them. The only thing it can return is &lt;code&gt;x&lt;/code&gt; itself. The type &lt;code&gt;∀T. T → T&lt;/code&gt; therefore has exactly one well-behaved implementation, the identity.&lt;/p&gt;

&lt;p&gt;The same reasoning applies to less trivial signatures. Consider any function of this type:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;List&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="no"&gt;R&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;List&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="cm"&gt;/* ... */&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Since &lt;code&gt;R&lt;/code&gt; cannot create or inspect elements of type &lt;code&gt;T&lt;/code&gt;, all it can do is rearrange, duplicate, or drop the elements it receives. It follows that applying a function &lt;code&gt;f&lt;/code&gt; to every element commutes with &lt;code&gt;R&lt;/code&gt;, whatever &lt;code&gt;R&lt;/code&gt; actually does:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="c1"&gt;// For every R of the type above and every function f:&lt;/span&gt;
&lt;span class="no"&gt;R&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Select&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;f&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;ToList&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;   &lt;span class="c1"&gt;// equals&lt;/span&gt;
&lt;span class="no"&gt;R&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Select&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;f&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Reversing a list, taking its first three elements, and removing every second element all satisfy this equation, and none of them needs a separate proof. Results of this kind follow from the type alone, and are therefore called &lt;strong&gt;free theorems&lt;/strong&gt; [7]. In languages with general recursion, a few free theorems additionally require the functions involved to terminate.&lt;/p&gt;

&lt;p&gt;Parametricity is also the precise line between parametric and ad hoc polymorphism: as soon as a function can branch on its type argument, the free theorems stop holding, whatever the syntax looks like. Section 7 shows that both C# generics and C++ templates allow exactly that.&lt;/p&gt;




&lt;h2&gt;
  
  
  5 INCLUSION POLYMORPHISM
&lt;/h2&gt;

&lt;p&gt;Consider this example from Section 1.1:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;abstract&lt;/span&gt; &lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;abstract&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Circle&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;r&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;override&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="nc"&gt;Math&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;PI&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="n"&gt;r&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="n"&gt;r&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Square&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;side&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;override&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;side&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="n"&gt;side&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;TotalArea&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;IEnumerable&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="nc"&gt;Shape&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;shapes&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;shapes&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;&lt;code&gt;TotalArea&lt;/code&gt; accepts circles and squares because &lt;code&gt;Circle ≤ Shape&lt;/code&gt; and &lt;code&gt;Square ≤ Shape&lt;/code&gt;. The name &lt;em&gt;inclusion&lt;/em&gt; comes from reading types as sets of values: every circle is also a shape, so the set of circles is included in the set of shapes. The interesting question is what makes one type a subtype of another. Programming languages answer it in three main ways, described in Sections 5.1–5.3.&lt;/p&gt;

&lt;h3&gt;
  
  
  5.1 Structural and Nominal Subtyping
&lt;/h3&gt;

&lt;p&gt;In C#, &lt;code&gt;Circle&lt;/code&gt; is a subtype of &lt;code&gt;Shape&lt;/code&gt; only because its declaration says so. A class with exactly the same members but no &lt;code&gt;: Shape&lt;/code&gt; in its declaration is not a subtype. This is &lt;strong&gt;nominal subtyping&lt;/strong&gt; – the subtype relation is established by declared names.&lt;/p&gt;

&lt;p&gt;The alternative is &lt;strong&gt;structural subtyping&lt;/strong&gt; – the subtype relation follows from the shape of the types alone [8]. A record type with more fields is a subtype of a record type with fewer, as long as the shared fields agree. TypeScript works this way:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight typescript"&gt;&lt;code&gt;&lt;span class="kd"&gt;type&lt;/span&gt; &lt;span class="nc"&gt;HasX&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="kt"&gt;number&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="kd"&gt;const&lt;/span&gt; &lt;span class="n"&gt;colorPoint&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;y&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;color&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="s2"&gt;"red"&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="kd"&gt;const&lt;/span&gt; &lt;span class="n"&gt;p&lt;/span&gt;&lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;HasX&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;colorPoint&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// accepted: colorPoint has an x field, nothing else is required&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Both kinds of subtyping extend to function types, and C# exposes the rule through variance on delegates. A function can safely replace another if it accepts &lt;em&gt;more general&lt;/em&gt; arguments and returns &lt;em&gt;more specific&lt;/em&gt; results:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="nc"&gt;Func&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="nc"&gt;Shape&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nc"&gt;Circle&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;fromShape&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;Circle&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Area&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nc"&gt;Func&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="nc"&gt;Circle&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nc"&gt;Shape&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;f&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;fromShape&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// compiles: Func is contravariant in its argument and covariant in its result&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The argument position is &lt;strong&gt;contravariant&lt;/strong&gt; – the subtype relation on arguments is reversed – and the result position is &lt;strong&gt;covariant&lt;/strong&gt; – the subtype relation on results is preserved. This rule is what makes the next section's problem appear.&lt;/p&gt;

&lt;h3&gt;
  
  
  5.2 Inheritance Versus Subtyping
&lt;/h3&gt;

&lt;p&gt;Object-oriented languages usually tie two different ideas together. &lt;strong&gt;Inheritance&lt;/strong&gt; – a mechanism for building one class's implementation from another's. &lt;strong&gt;Subtyping&lt;/strong&gt; – a relation that decides where a value may be used. In C#, every subclass is automatically a subtype of its base class, but the two ideas can come apart [9].&lt;/p&gt;

&lt;p&gt;The classic example is a method that takes an argument of the receiver's own type, called a &lt;strong&gt;binary method&lt;/strong&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;Point&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;virtual&lt;/span&gt; &lt;span class="kt"&gt;bool&lt;/span&gt; &lt;span class="nc"&gt;Equal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;Point&lt;/span&gt; &lt;span class="n"&gt;other&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="n"&gt;other&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="n"&gt;color&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;Point&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Color&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;color&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

    &lt;span class="c1"&gt;// public override bool Equal(ColorPoint other)   // not allowed: the parameter type must stay Point&lt;/span&gt;

    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;override&lt;/span&gt; &lt;span class="kt"&gt;bool&lt;/span&gt; &lt;span class="nc"&gt;Equal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;Point&lt;/span&gt; &lt;span class="n"&gt;other&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt;
        &lt;span class="n"&gt;other&lt;/span&gt; &lt;span class="k"&gt;is&lt;/span&gt; &lt;span class="nc"&gt;ColorPoint&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt; &lt;span class="o"&gt;&amp;amp;&amp;amp;&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;&amp;amp;&amp;amp;&lt;/span&gt; &lt;span class="nc"&gt;Color&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="n"&gt;cp&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Color&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Ideally, &lt;code&gt;ColorPoint.Equal&lt;/code&gt; would take a &lt;code&gt;ColorPoint&lt;/code&gt;, since comparing colors only makes sense between two colored points. But narrowing the parameter type breaks the contravariance rule from Section 5.1: code that holds a &lt;code&gt;Point&lt;/code&gt; reference could pass a plain &lt;code&gt;Point&lt;/code&gt; to a method that expects a &lt;code&gt;ColorPoint&lt;/code&gt;. A &lt;code&gt;ColorPoint&lt;/code&gt; with such a method would &lt;em&gt;inherit&lt;/em&gt; from &lt;code&gt;Point&lt;/code&gt; without being a &lt;em&gt;subtype&lt;/em&gt; of it. C# avoids the contradiction by forbidding the narrowing, which is why the override above has to fall back on a run-time type test. Eiffel, which does allow this kind of narrowing, has a well-known type-safety gap at exactly this point.&lt;/p&gt;

&lt;h3&gt;
  
  
  5.3 Behavioral Subtyping
&lt;/h3&gt;

&lt;p&gt;Matching signatures are not enough for safe substitution. The following code compiles without warnings:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;FixedPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;protected&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;_x&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="no"&gt;X&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;_x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// documented guarantee: X never changes&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;MovablePoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;FixedPoint&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;void&lt;/span&gt; &lt;span class="nc"&gt;Move&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;dx&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;_x&lt;/span&gt; &lt;span class="o"&gt;+=&lt;/span&gt; &lt;span class="n"&gt;dx&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Code that receives a &lt;code&gt;FixedPoint&lt;/code&gt; may rely on &lt;code&gt;X&lt;/code&gt; staying the same, for example by caching it. Passing a &lt;code&gt;MovablePoint&lt;/code&gt; breaks that assumption, even though the type checker sees nothing wrong. &lt;strong&gt;Behavioral subtyping&lt;/strong&gt; closes this gap – a subtype must preserve every property that can be proved about its supertype, not just the method signatures [10]. These properties include invariants, the preconditions and postconditions of each method, and &lt;strong&gt;history constraints&lt;/strong&gt;, which describe how an object's state may change over its lifetime. "X never changes" is a history constraint, and &lt;code&gt;MovablePoint&lt;/code&gt; violates it.&lt;/p&gt;

&lt;p&gt;This requirement is widely known as the &lt;strong&gt;Liskov Substitution Principle&lt;/strong&gt;. Its best-known illustration, a &lt;code&gt;Square&lt;/code&gt; that inherits from a mutable &lt;code&gt;Rectangle&lt;/code&gt;, fails for the same reason: setting the width of a square also changes its height, which code written against &lt;code&gt;Rectangle&lt;/code&gt; does not expect.&lt;/p&gt;

&lt;p&gt;The three notions of subtyping compare as follows:&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;Notion of subtyping&lt;/th&gt;
&lt;th&gt;Basis of the relation&lt;/th&gt;
&lt;th&gt;Checked by&lt;/th&gt;
&lt;th&gt;Example languages&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;Structural&lt;/td&gt;
&lt;td&gt;Shape of the types&lt;/td&gt;
&lt;td&gt;Type checker&lt;/td&gt;
&lt;td&gt;TypeScript, Go interfaces, OCaml objects&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Nominal&lt;/td&gt;
&lt;td&gt;Declared inheritance or implementation&lt;/td&gt;
&lt;td&gt;Type checker&lt;/td&gt;
&lt;td&gt;C#, Java, C++&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;Behavioral&lt;/td&gt;
&lt;td&gt;Specified behavior&lt;/td&gt;
&lt;td&gt;The developer, through design, contracts, and tests&lt;/td&gt;
&lt;td&gt;Any language&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;




&lt;h2&gt;
  
  
  6 AD HOC POLYMORPHISM
&lt;/h2&gt;

&lt;h3&gt;
  
  
  6.1 Overloading
&lt;/h3&gt;

&lt;p&gt;Let's go back to the &lt;code&gt;Twice&lt;/code&gt; example from Section 1.2 and look at it closer:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt;    &lt;span class="nc"&gt;Twice&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;    &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;Twice&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Twice&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;21&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;     &lt;span class="c1"&gt;// calls Twice(int)&lt;/span&gt;
&lt;span class="nc"&gt;Twice&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"ab"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// calls Twice(string)&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The two methods share a name, but nothing else: they have different bodies and different types, and the compiler decides which one to call at each call site. Renaming them makes the overloading disappear without changing what the program does:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt;    &lt;span class="nc"&gt;TwiceInt&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;       &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="nc"&gt;TwiceString&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;string&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="n"&gt;s&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;TwiceInt&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;21&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nc"&gt;TwiceString&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="s2"&gt;"ab"&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;This is why ad hoc polymorphism is considered polymorphism only in appearance (Section 3.1): a simple compile-time translation removes it entirely [2]. The same holds for operator overloading, such as the predefined &lt;code&gt;+&lt;/code&gt; on &lt;code&gt;int&lt;/code&gt; and &lt;code&gt;double&lt;/code&gt; or a user-defined &lt;code&gt;operator +&lt;/code&gt; on a &lt;code&gt;Vector&lt;/code&gt; type.&lt;/p&gt;

&lt;h3&gt;
  
  
  6.2 Coercion
&lt;/h3&gt;

&lt;p&gt;Let's look at the &lt;code&gt;Half&lt;/code&gt; example from Section 1.2 once more:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Half&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;/&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Half&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;5&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// the int 5 is converted to the double 5.0&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;&lt;code&gt;Half&lt;/code&gt; has exactly one implementation, written for &lt;code&gt;double&lt;/code&gt;. The call works with an &lt;code&gt;int&lt;/code&gt; only because the compiler inserts a conversion. C# also lets you define such conversions for your own types:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;readonly&lt;/span&gt; &lt;span class="k"&gt;record&lt;/span&gt; &lt;span class="k"&gt;struct&lt;/span&gt; &lt;span class="nc"&gt;Meters&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="nc"&gt;Value&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="k"&gt;implicit&lt;/span&gt; &lt;span class="k"&gt;operator&lt;/span&gt; &lt;span class="nc"&gt;Meters&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;v&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;v&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="nc"&gt;Meters&lt;/span&gt; &lt;span class="nc"&gt;Stretch&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;Meters&lt;/span&gt; &lt;span class="n"&gt;m&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;m&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Value&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="nc"&gt;Stretch&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mf"&gt;5.0&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// the double 5.0 is converted to Meters&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;From the call site alone, overloading and coercion are often indistinguishable [2]:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="kt"&gt;double&lt;/span&gt; &lt;span class="n"&gt;d&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;3&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mf"&gt;4.0&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;This line can be explained in two ways: as one of several overloaded &lt;code&gt;+&lt;/code&gt; operators, one for each combination of &lt;code&gt;int&lt;/code&gt; and &lt;code&gt;double&lt;/code&gt;, or as a single &lt;code&gt;double + double&lt;/code&gt; operator preceded by a conversion of &lt;code&gt;3&lt;/code&gt;. C# actually uses both. The language defines a set of overloaded &lt;code&gt;+&lt;/code&gt; operators for its numeric types, and overload resolution picks &lt;code&gt;double + double&lt;/code&gt; after converting &lt;code&gt;3&lt;/code&gt; to &lt;code&gt;3.0&lt;/code&gt;.&lt;/p&gt;

&lt;h3&gt;
  
  
  6.3 Type Classes and Generic Math
&lt;/h3&gt;

&lt;p&gt;Plain overloading has a limitation: a generic method cannot use it. Inside &lt;code&gt;Sum&amp;lt;T&amp;gt;&lt;/code&gt;, there is no &lt;code&gt;+&lt;/code&gt; that works for an arbitrary &lt;code&gt;T&lt;/code&gt;, because the compiler resolves overloads statically and &lt;code&gt;T&lt;/code&gt; is unknown. &lt;strong&gt;Type classes&lt;/strong&gt; solve this by turning a set of overloaded operations into a constraint that a type parameter can carry [12]. They first appeared in Haskell and today underlie Rust traits and Scala implicits.&lt;/p&gt;

&lt;p&gt;C# gained the same capability in C# 11, through static abstract interface members. The generic math interfaces in .NET use it:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;using&lt;/span&gt; &lt;span class="nc"&gt;System&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Numerics&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;IEnumerable&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="k"&gt;where&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;INumber&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;total&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Zero&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;foreach&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kd"&gt;var&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="k"&gt;in&lt;/span&gt; &lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="n"&gt;total&lt;/span&gt; &lt;span class="o"&gt;+=&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;total&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;new&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mi"&gt;3&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;         &lt;span class="c1"&gt;// 6, using int addition&lt;/span&gt;
&lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;new&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="mf"&gt;1.5&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mf"&gt;2.5&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;        &lt;span class="c1"&gt;// 4.0, using double addition&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;&lt;code&gt;Sum&lt;/code&gt; is generic, but &lt;code&gt;+&lt;/code&gt; still does something different for each type, so the polymorphism is ad hoc. What has changed is that the set of types is no longer fixed in advance: any type that implements &lt;code&gt;INumber&amp;lt;T&amp;gt;&lt;/code&gt; qualifies.&lt;/p&gt;

&lt;p&gt;The standard way to compile type classes shows why this works. Each constraint becomes an extra argument, called a &lt;strong&gt;dictionary&lt;/strong&gt; – an object that carries the implementations of the constrained operations. Written by hand in C#, the translation looks like this:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;interface&lt;/span&gt; &lt;span class="nc"&gt;IAdditive&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Zero&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="n"&gt;get&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Add&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;   &lt;span class="c1"&gt;// the dictionary&lt;/span&gt;

&lt;span class="k"&gt;sealed&lt;/span&gt; &lt;span class="k"&gt;class&lt;/span&gt; &lt;span class="nc"&gt;IntAdditive&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="nc"&gt;IAdditive&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="nc"&gt;Zero&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;public&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="nc"&gt;Add&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;a&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="n"&gt;b&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="nc"&gt;IEnumerable&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nc"&gt;IAdditive&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;d&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;
&lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;total&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;d&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Zero&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;foreach&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kd"&gt;var&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="k"&gt;in&lt;/span&gt; &lt;span class="n"&gt;xs&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="n"&gt;total&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="n"&gt;d&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nc"&gt;Add&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;total&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
    &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;total&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;

&lt;span class="nc"&gt;Sum&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;new&lt;/span&gt;&lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mi"&gt;2&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mi"&gt;3&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="k"&gt;new&lt;/span&gt; &lt;span class="nc"&gt;IntAdditive&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// 6&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;After the translation, &lt;code&gt;Sum&lt;/code&gt; is ordinary parametric code: it never inspects &lt;code&gt;T&lt;/code&gt;, and all type-specific behavior arrives through the dictionary. Type classes thus bring ad hoc polymorphism into the framework of parametric polymorphism, reconnecting the two kinds that Strachey separated in 1967.&lt;/p&gt;




&lt;h2&gt;
  
  
  7 BOUNDARY CASES
&lt;/h2&gt;

&lt;p&gt;There are mechanisms and concepts in different programming languages that don't fit the four forms as neatly:&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;Mechanism&lt;/th&gt;
&lt;th&gt;Cardelli–Wegner form&lt;/th&gt;
&lt;th&gt;Binding time&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;ML and Haskell polymorphic functions&lt;/td&gt;
&lt;td&gt;Parametric (universal)&lt;/td&gt;
&lt;td&gt;Compile time checking; one compiled body&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;C# and Java generics&lt;/td&gt;
&lt;td&gt;Parametric; bounded when constrained with &lt;code&gt;where T : C&lt;/code&gt; or &lt;code&gt;T extends C&lt;/code&gt;
&lt;/td&gt;
&lt;td&gt;Compile time checking&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;C# generic math, Haskell type classes, Rust traits&lt;/td&gt;
&lt;td&gt;Ad hoc, structured as in Section 6.3&lt;/td&gt;
&lt;td&gt;Implementations selected at compile time&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;C++ templates&lt;/td&gt;
&lt;td&gt;Parametric in form; ad hoc in effect&lt;/td&gt;
&lt;td&gt;Compile time, per instantiation&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;

&lt;p&gt;The syntax of a mechanism does not determine its category. Section 4.3 shows that every well-behaved function of type &lt;code&gt;∀T. T → T&lt;/code&gt; is the identity. C++ templates break this through &lt;strong&gt;explicit specialization&lt;/strong&gt;, which permits a different definition for a particular type argument:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight cpp"&gt;&lt;code&gt;&lt;span class="k"&gt;template&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="k"&gt;typename&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nf"&gt;identity&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="k"&gt;template&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&amp;gt;&lt;/span&gt;           &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;identity&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt; &lt;span class="k"&gt;return&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="p"&gt;}&lt;/span&gt;  &lt;span class="c1"&gt;// legal specialization&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;C# generics break it too. Let's go back to &lt;code&gt;Id&lt;/code&gt; from Section 1.1 one last time and add a run-time type test, which is legal on values of a type parameter:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight csharp"&gt;&lt;code&gt;&lt;span class="k"&gt;static&lt;/span&gt; &lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="nc"&gt;Id&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="o"&gt;=&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt; &lt;span class="k"&gt;is&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;?&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="no"&gt;T&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="k"&gt;object&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;+&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;:&lt;/span&gt; &lt;span class="n"&gt;x&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;   &lt;span class="c1"&gt;// compiles; not the identity for int&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Neither mechanism therefore satisfies parametricity in the sense of Section 4.3. In C#, Java, and C++ alike, free theorems hold only for code that avoids type tests, reflection, and specialization.&lt;/p&gt;




&lt;h2&gt;
  
  
  8 FURTHER READING
&lt;/h2&gt;

&lt;p&gt;The sources below cover the material of this article in more depth:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;Cardelli and Wegner [2] – the original taxonomy and the quantifiers behind it.&lt;/li&gt;
&lt;li&gt;Wadler [7] – an accessible introduction to parametricity and free theorems, followed by Reynolds [6] for the underlying theory.&lt;/li&gt;
&lt;li&gt;Milner [5] – let-polymorphism and type inference.&lt;/li&gt;
&lt;li&gt;Wadler and Blott [12] – type classes as structured ad hoc polymorphism.&lt;/li&gt;
&lt;li&gt;Cardelli [8], Cook, Hill, and Canning [9], and Liskov and Wing [10] – structural subtyping, inheritance versus subtyping, and behavioral subtyping.&lt;/li&gt;
&lt;li&gt;Pierce [13] – the standard textbook, covering subtyping, System F, existential types, and bounded quantification in one framework. Pierce [14] and Harper [15] continue from there, and Cardelli [16] is a compact survey of the same ground.&lt;/li&gt;
&lt;li&gt;Abadi and Cardelli [11] – the most complete formal account of objects, subtyping, and variance.&lt;/li&gt;
&lt;li&gt;Strachey [1], Girard [3], and Reynolds [4] – the historical primary sources.&lt;/li&gt;
&lt;/ol&gt;




&lt;h2&gt;
  
  
  REFERENCES
&lt;/h2&gt;

&lt;ol&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1023/A:1010000313106" rel="noopener noreferrer"&gt;Strachey, "Fundamental Concepts in Programming Languages"&lt;/a&gt;. Lecture notes, International Summer School in Computer Programming, Copenhagen, 1967. Reprinted in &lt;em&gt;Higher-Order and Symbolic Computation&lt;/em&gt; 13(1–2):11–49, 2000.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://lucacardelli.name/papers/onunderstanding.a4.pdf" rel="noopener noreferrer"&gt;Cardelli &amp;amp; Wegner, "On Understanding Types, Data Abstraction, and Polymorphism"&lt;/a&gt;. &lt;em&gt;ACM Computing Surveys&lt;/em&gt; 17(4):471–522, 1985. DOI: 10.1145/6041.6042.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://girard.perso.math.cnrs.fr/These.pdf" rel="noopener noreferrer"&gt;Girard, "Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur"&lt;/a&gt;. Thèse de Doctorat d'État, Université Paris VII, 1972.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1007/3-540-06859-7_148" rel="noopener noreferrer"&gt;Reynolds, "Towards a Theory of Type Structure"&lt;/a&gt;. &lt;em&gt;Programming Symposium (Colloque sur la Programmation)&lt;/em&gt;, Lecture Notes in Computer Science 19, pp. 408–425. Springer, 1974.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1016/0022-0000%2878%2990014-4" rel="noopener noreferrer"&gt;Milner, "A Theory of Type Polymorphism in Programming"&lt;/a&gt;. &lt;em&gt;Journal of Computer and System Sciences&lt;/em&gt; 17(3):348–375, 1978.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://researchr.org/publication/Reynolds83%3A0" rel="noopener noreferrer"&gt;Reynolds, "Types, Abstraction and Parametric Polymorphism"&lt;/a&gt;. &lt;em&gt;Information Processing 83&lt;/em&gt; (IFIP Congress), pp. 513–523. North-Holland, 1983. The link is a bibliographic record; the proceedings carry no DOI.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1145/99370.99404" rel="noopener noreferrer"&gt;Wadler, "Theorems for Free!"&lt;/a&gt;. &lt;em&gt;Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture (FPCA '89)&lt;/em&gt;, pp. 347–359. ACM, 1989.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1016/0890-5401%2888%2990007-7" rel="noopener noreferrer"&gt;Cardelli, "A Semantics of Multiple Inheritance"&lt;/a&gt;. &lt;em&gt;Semantics of Data Types&lt;/em&gt;, Lecture Notes in Computer Science 173, pp. 51–67. Springer, 1984. Extended version in &lt;em&gt;Information and Computation&lt;/em&gt; 76(2–3):138–164, 1988 (linked).&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1145/96709.96721" rel="noopener noreferrer"&gt;Cook, Hill &amp;amp; Canning, "Inheritance Is Not Subtyping"&lt;/a&gt;. &lt;em&gt;Proceedings of the 17th ACM Symposium on Principles of Programming Languages (POPL '90)&lt;/em&gt;, pp. 125–135. ACM, 1990.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1145/197320.197383" rel="noopener noreferrer"&gt;Liskov &amp;amp; Wing, "A Behavioral Notion of Subtyping"&lt;/a&gt;. &lt;em&gt;ACM Transactions on Programming Languages and Systems&lt;/em&gt; 16(6):1811–1841, 1994.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1007/978-1-4419-8598-9" rel="noopener noreferrer"&gt;Abadi &amp;amp; Cardelli, &lt;em&gt;A Theory of Objects&lt;/em&gt;&lt;/a&gt;. Monographs in Computer Science. Springer, 1996.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://doi.org/10.1145/75277.75283" rel="noopener noreferrer"&gt;Wadler &amp;amp; Blott, "How to Make Ad-Hoc Polymorphism Less Ad Hoc"&lt;/a&gt;. &lt;em&gt;Proceedings of the 16th ACM Symposium on Principles of Programming Languages (POPL '89)&lt;/em&gt;, pp. 60–76. ACM, 1989.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://www.cis.upenn.edu/~bcpierce/tapl/" rel="noopener noreferrer"&gt;Pierce, &lt;em&gt;Types and Programming Languages&lt;/em&gt;&lt;/a&gt;. MIT Press, 2002.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://www.cis.upenn.edu/~bcpierce/attapl/main.html" rel="noopener noreferrer"&gt;Pierce (ed.), &lt;em&gt;Advanced Topics in Types and Programming Languages&lt;/em&gt;&lt;/a&gt;. MIT Press, 2005.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://www.cambridge.org/core/books/practical-foundations-for-programming-languages/3D852B5A14F48F85C60B95A0BBCAB7D9" rel="noopener noreferrer"&gt;Harper, &lt;em&gt;Practical Foundations for Programming Languages&lt;/em&gt;&lt;/a&gt;, 2nd ed. Cambridge University Press, 2016.&lt;/li&gt;
&lt;li&gt;
&lt;a href="https://lucacardelli.name/papers/typesystems.pdf" rel="noopener noreferrer"&gt;Cardelli, "Type Systems"&lt;/a&gt;. In A. B. Tucker (ed.), &lt;em&gt;The Computer Science and Engineering Handbook&lt;/em&gt;, Chapter 103. CRC Press, 1997; 2nd ed., Chapter 97, 2004.&lt;/li&gt;
&lt;/ol&gt;

</description>
      <category>computerscience</category>
      <category>csharp</category>
      <category>programming</category>
      <category>softwareengineering</category>
    </item>
  </channel>
</rss>
