Earlier posts on Rook showed that it was a dynamically typed language: the type of an object was not declared, and was not known until the last moment at runtime. Typing mistakes on the part of the programmer would be discovered at runtime. Although I like the brevity of dynamic languages like Python, I have also been interested in using type inference to get some of the benefits of dynamic typing along with the benefits of static typing. The latest version of Rook, which is not quite complete enough to be made public, uses the Hindley-Milner Type Inference Algorithm instead of dynamic typing. The basic idea is that all of the sample source code in previous posts still works unchanged, with the added benefit of having all types checked prior to running.

I found this paper to be the most accessible description of the Hindley-Milner algorithm: Basic Polymorphic Type Checking by Luca Cardelli. It gives a lot of background information in plain English, assumes little about the reader other than familiarity with language constructs similar to those in Scheme, and includes a working implementation of the algorithm. Some of the formal theory went a little over my head, but the remainder of the paper proved very useful.

The sample implementation was in Modula-2, and understandably it did not include tests that would translate directly into NUnit tests. Still, I wanted to make sure that as I translated the sample implementation into C#, I would have a large set of tests to back it up. First, I made a translation from Modula-2 to C#-flavored pseudocode. Then, I attacked that code in several small pieces: whenever a relatively small part of the pseudocode could be tested/developed in isolation, I would move that piece into C# with tests. This approach allowed me to chip away at the stone with confidence that I wasn’t missing anything in the translation. Another fortunate side effect of this approach is that by making myself writes tests for each small piece being translated, I gained a better understanding of how the type inference system actually works.