Type inference implemented in C++

Question

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

Erm... what is Damas-Hindley-Milner style type inference? Any links would be nice. Also note that C++11 adds `auto` for type inference, and `template`s are by-nature inferencing types when used as function parameters. — Xeo, Jan 08 '12 at 02:13
Can you elaborate on what "Damas-Hindley-Milner style type inference" is? I don't feel like googling it. — Benjamin Lindley, Jan 08 '12 at 02:13
@BenjaminLindley: I imagine that this is a situation where if you have to look it up you probably won't have the answer, either... — Kerrek SB, Jan 08 '12 at 02:16
I think the question isn't `{implementation of {type inference in C++}}`, but rather, `{implementation in C++ of {type inference}}`. @Keveman: Check the other questions on SO (I added the right tag), maybe they're of some help... maybe the source code of a C++ compiler can be educational, since templates are sort of a functional programming language. — Kerrek SB, Jan 08 '12 at 02:17
@KerrekSB Yes, but templates aren't even "type checked" prior to their instantiation, so I'd doubt an implementation of C++ templates would contain very much that's similar to HM type inference. Plus: I'd imagine that any C++ compiler's source code would be particular easy to read/understand. — sepp2k, Jan 08 '12 at 02:30
@BenjaminLindley: http://stackoverflow.com/questions/399312/what-is-hindley-milner — Daniel Daranas, Jan 10 '12 at 11:13

Jared Hoberock · Answer 1 · 2012-08-11T06:53:18.833

14

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.

edited Aug 11 '12 at 06:53

answered Mar 02 '12 at 08:22

Jared Hoberock

11,118
3
40
76

You may also find `boost::disjoint_sets` useful for union-find operations. – max Sep 29 '16 at 16:47

score 1 · Answer 2 · answered Nov 30 '16 at 16:33

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

score 1 · Answer 3 · answered Jan 10 '12 at 14:03

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.

Type inference implemented in C++

3 Answers3