<p>You can take a look at type systems for intersection types which can give you something like <code>a :: Int -&gt; Int | Bool -&gt; Bool</code>, so you know that two specializations to <code>Int</code> and <code>Bool</code> are enough, or to use a usual type inference to infer most general types followed by a control flow analysis to collect actual type arguments. In fact there are hybrid approaches (CFA expressed as a type system and vice versa).</p>

<p>Research works on inferring least general types instead of most general types may exist, but I'm unaware of them.</p>

<p>As for techniques to implement polymorphism, two solutions exist: 1) specialization (think of C++ templates) 2) uniform representation assumption (think of C-style collections with void*).</p>

<p>For 2 you don't need the type from call-site during typechecking, and can support separate compilation more easily.</p>

<p>Note that we are talking about parametric polymorphism here, and OO virtual method calls are completely different thing called subtype polymorphism. Note that C++ templates support both something like parametric polymorphism and duck typing, which is yet another form of polymorphism. </p>

CC BY-SA 3.0
2011-11-28T16:54:40.223Z
"OO virtual method calls are completely different thing called ad-hoc polymorphism" Ad-hoc polymorphism is another name for overloading. You seem to confuse it with subtype polymorphism.
Radu GRIGore
CC BY-SA 3.0
2011-11-28T17:11:05.880Z
But subclasses are not necessarily subtypes, aren't they? E.g. for subtypes LSP is supposed to hold.
nponeccop
CC BY-SA 3.0
2011-11-28T18:27:30.833Z
True, but beside the point. "Subtype polymorphism" is the standard term. See http://en.wikipedia.org/wiki/Subtype_polymorphism for details.
Radu GRIGore
CC BY-SA 3.0
2011-11-28T09:52:31.440Z
2011-11-28T22:37:04.090Z
2011-11-28T22:37:04.090Z
nponeccop
<p>Almost all systems with type inference use call-site information to do this.  Examples include Standard ML, OCaml, F#, and Haskell.  Many other languages use call-site information to infer type parameter instantiation, such as Java, C#, Scala, and Typed Racket.  This often goes by the name "Local Type Inference".</p>

<p>I would just describe what you're looking for as "Type Inference", and you should probably start by looking up what's commonly known as the "Hindley-Milner" system.  The Wikipedia <a href="http://en.wikipedia.org/wiki/Hindley%E2%80%93Milner">page</a> gives a reasonable introduction, and pointers to the original papers.  </p>

<p>The place to start for Local Type Inference is Pierce and Turner's original paper, best read in the TOPLAS 2000 version (<a href="http://dl.acm.org/citation.cfm?id=345100">ACM</a>, <a href="http://www.cis.upenn.edu/~bcpierce/papers/lti.pdf">PDF</a>).</p>

CC BY-SA 3.0
2011-11-28T19:23:17.157Z
The Pierce and Turner paper was very enlightening, thanks. Are you aware of a minimal implementation of the algorithm they describe in code? I think that would be very interesting to look at as well, if it exists.
Derek Thurn
CC BY-SA 3.0
2011-11-28T20:49:07.003Z
I don't know of any minimal implementations.  There's one in Typed Racket, and one in Scala, but both implement substantially more complicated algorithms.
Sam Tobin-Hochstadt
CC BY-SA 3.0
2011-11-28T16:42:41.583Z
2011-11-28T16:42:41.583Z
Sam Tobin-Hochstadt
<p>I'm trying to learn more about whole-program type checking and type inferencing systems that use information from function call sites to compute type information (in addition to the standard approach of using the function body). For example, such an algorithm might use a function call like <code>foo(1)</code> to infer that the function in <code>foo</code> takes integer arguments. Obviously this would complicate inference a lot and make the check non-modular.</p>

<p>Anyway, I haven't had much luck finding any research on this approach, probably because I don't know the correct terminology to describe what I'm talking about. Any pointers?</p>

CC BY-SA 3.0
2011-11-28T09:57:51.250Z
What you are describing has hints of bidirectional type inference, unless I'm mistaken.  Describing what you are trying to do may clarify, however.
Dominic Mulligan
CC BY-SA 3.0
2011-11-28T09:59:46.477Z
Are you asking because you seek a way to specialize polymorphic functions?
nponeccop
CC BY-SA 3.0
2011-11-28T15:55:47.117Z
I'm mostly just trying to learn more about type systems really, and yes, I was thinking mostly about how to handle polymorphic functions (and method calls in OO languages, the same thing). I'm  trying to identify the right terms for this so I can read up on it.
Derek Thurn
<pl.programming-languages><type-theory><type-inference><type-systems>
Research on call-site based type inference?
Derek Thurn
# Research on call-site based type inference?

(Asked by: username_0 on 2011-11-28)

I'm trying to learn more about whole-program type checking and type inferencing systems that use information from function call sites to compute type information (in addition to the standard approach of using the function body). For example, such an algorithm might use a function call like `foo(1)` to infer that the function in `foo` takes integer arguments. Obviously this would complicate inference a lot and make the check non-modular.

Anyway, I haven't had much luck finding any research on this approach, probably because I don't know the correct terminology to describe what I'm talking about. Any pointers?

**Tags:** pl.programming-languages, type-theory, type-inference, type-systems

> **Comments:**
> **username_1**: What you are describing has hints of bidirectional type inference, unless I'm mistaken.  Describing what you are trying to do may clarify, however.  
> **username_2**: Are you asking because you seek a way to specialize polymorphic functions?  
> **username_0**: I'm mostly just trying to learn more about type systems really, and yes, I was thinking mostly about how to handle polymorphic functions (and method calls in OO languages, the same thing). I'm  trying to identify the right terms for this so I can read up on it.  

---

## 2 answers

### Answer by username_4 on 2011-11-28. Score: 11 | Accepted answer

Almost all systems with type inference use call-site information to do this. Examples include Standard ML, OCaml, F#, and Haskell. Many other languages use call-site information to infer type parameter instantiation, such as Java, C#, Scala, and Typed Racket. This often goes by the name "Local Type Inference".

I would just describe what you're looking for as "Type Inference", and you should probably start by looking up what's commonly known as the "Hindley-Milner" system. The Wikipedia [page](http://en.wikipedia.org/wiki/Hindley%E2%80%93Milner) gives a reasonable introduction, and pointers to the original papers.

The place to start for Local Type Inference is Pierce and Turner's original paper, best read in the TOPLAS 2000 version ([ACM](http://dl.acm.org/citation.cfm?id=345100), [PDF](http://www.cis.upenn.edu/~bcpierce/papers/lti.pdf)).

> **Comments:**
> **username_0**: The Pierce and Turner paper was very enlightening, thanks. Are you aware of a minimal implementation of the algorithm they describe in code? I think that would be very interesting to look at as well, if it exists.  
> **username_4**: I don't know of any minimal implementations.  There's one in Typed Racket, and one in Scala, but both implement substantially more complicated algorithms.  

---

### Answer by username_2 on 2011-11-28. Score: 0

You can take a look at type systems for intersection types which can give you something like `a :: Int -> Int | Bool -> Bool`, so you know that two specializations to `Int` and `Bool` are enough, or to use a usual type inference to infer most general types followed by a control flow analysis to collect actual type arguments. In fact there are hybrid approaches (CFA expressed as a type system and vice versa).

Research works on inferring least general types instead of most general types may exist, but I'm unaware of them.

As for techniques to implement polymorphism, two solutions exist: 1) specialization (think of C++ templates) 2) uniform representation assumption (think of C-style collections with void\*).

For 2 you don't need the type from call-site during typechecking, and can support separate compilation more easily.

Note that we are talking about parametric polymorphism here, and OO virtual method calls are completely different thing called subtype polymorphism. Note that C++ templates support both something like parametric polymorphism and duck typing, which is yet another form of polymorphism.

> **Comments:**
> **username_3**: "OO virtual method calls are completely different thing called ad-hoc polymorphism" Ad-hoc polymorphism is another name for overloading. You seem to confuse it with subtype polymorphism.  
> **username_2**: But subclasses are not necessarily subtypes, aren't they? E.g. for subtypes LSP is supposed to hold.  
> **username_3**: True, but beside the point. "Subtype polymorphism" is the standard term. See http://en.wikipedia.org/wiki/Subtype_polymorphism for details.  

---

