Type inference implemented in C++

Question

Is there an implementation in C++, of Damas-Hindley-Milner style type inference, preferably using modern C++ techniques?

Answer 1

I suspect you won't have much luck; the functional guys who write this stuff generally don't do it in C++! Most of the compilers you could go to are used to compile themselves (eg for OCaml, or GHC).

So, if someone did do Hindley-Milner as a toy project, it's probably not on the net; if it was part of compiler, then it's unlikely to be in C++.

Possible things that come to mind:

• Hugs for Haskell is in C; there'll be some C sources in there somewhere that do what you want, and Haskell's a nice familiar sugar. Not the C++ you want though.
• I don't know anything about F#, but I think that's HM, and if anyone has written a fat functional compiler in C++ with modern techniques, it could be probably MS. Obviously closed source though.

Answer 2

We have a type inference engine here (https://github.com/ltcmelo/psychec). Our approach is implemented after the HM(X) algorithm by Pottier and Remy, with separate stages for constraint generation and type inference properly. Constraint generation is implemented in C++, but type resolution is implemented in Haskell (sorry!). The algorithm infers types for C programs, to reconstruct code partially available. The tool is available on-line: http://cuda.dcc.ufmg.br/psyche-c/. You enter part of a C program, and it produces type declarations that are sufficient for compiling it.

Regards,

Fernando

Answer 3

Here's my implementation of Hindley-Milner type inference in C++11, based on the Python code by Robert Smallshire, the Scala code by Andrew Forrest, the Perl code by Nikita Borisov and the paper "Basic Polymorphic Typechecking" by Cardelli.

It makes heavy use of boost::variant and boost::apply_visitor.