One day is not enough
I had been given one day to find the perfect (at least for now) typing algorithm for records and variants. I fear that wasn't quite enough. Typing records is a subject that many people have written long articles about: there simply was to much to read for me. The printer didn't want to cooperate either.
From all possible papers, obtained by looking on potential author's web sites, and through referencing by other potential papers, I've nominated 13 for the perfect algorithm final. Currently, Buneman & Ohori's 'Polymorphism and Type Inference in Database Programming' is the favourite, since it claims that Kleisli's type system derives from it's own. I still have to read it in more detail as well as some other nominated articles that I didn't have time to read in detail.
The 13 finalists are (from oldest to youngest):
- M. Wand; Complete type inference for Simple Objects, 1987.
- A. Ohori & P. Buneman; Type Inference in a Database Programming Language, 1988.
- A. Jategaonkar & C. Mitchell; ML with Extended Pattern Matching and Subtypes, 1988.
- D. Rémy; Type-checking records and variants in a natural extension of ML, 1989.
- M. Wand; Type Inference for record Concatenation and Multiple Inheritance, 1991.
- R. Harper & B. Pierce; A Record Calculus Based on Symmetric Concatenation, 1991.
- L. Cardelli & J. Mitchell; Operations on Records, 1991.
- A. Ohori & P. Buneman & V. Tannen; Database Programming in Machiavelli - a Polymorphic Language with Static type Inference, 1992.
- D. Rémy; Typing Record Concatenation for Free, 1993.
- P. Buneman & A. Ohori; Polymorphism and Type Inference in Database Programming, 1994.
- A. Ohori; A Polymorphic Record Calculus and it's Compilation, 1995.
- J. Garrigue; Programming with Polymorphic Variants, 1998.
- J. Garrigue; Simple Type Inference for Structural Polymorphism, 2002.