Channels ▼

Christopher Diggins

Dr. Dobb's Bloggers

Implementing Type Inference: Not so Hard!

April 19, 2008

I recently uncovered a free computer science textbook which is not as well-known as it should be, called Programming Languages: Application and Interpretation by Shriram Krishnamurthi. One of the gems inside was a very lucid explanation of type systems and type inference.

I have been working recently on trying to explain the rather ad-hoc type inference algorithm I use in the Cat language in the form of a technical report. During this process I uncovered what I consider to be the best description of basic Hindley-Milner (HM) type inference in the book Programming Languages: Application and Interpretation by Shriram Krishnamurti, sometimes referred to as the PLAI. Type-inference is explained in Chapter 30

Other papers that I have found very helpful and accessible in learning about type-inference are:

I hope more language implementors will consider seriously the advantages of including type-checking in their languages (and optimizers), and explore the different ways that we can extend HM type-inference to make it even more powerful.



Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags


<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags


<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

