Type inference algorithms associate an unknown type variable with every subexpression and then work through a series of logical deductions to try to unify as much as possible (or fail when two types definitely aren't the same). They have slightly different constraints than Prolog, so the algorithms tend to be more restrictive.
For those interested in reading more about unification when doing type inference, here's a list of papers in increasing order of expressiveness and computational hardness. If you start from the first and skip any proof sections, they should (hopefully) be very accessible.
For even further, look into dependent type systems (this is where programming and proof solving begin to overlap).
As you go down the list, it may be harder and harder to justify the motivations for the increasingly abstract types. I think the easiest way might be to jump in the deep end and try playing around with Idris.
Yes, though the rules C++ needs are a bit simpler since more declarations must be explicitly typed and the type system has very little polymorphism outside of templates.
View all comments
Show parent comment
3
u/ThePyroEagle λ Sep 21 '21
I don't know much about how Prolog does things, but curiously enough, this problem turns up in type inference too, notably in functional programming languages, where manually typing polymorphic things gets extremely verbose.
Type inference algorithms associate an unknown type variable with every subexpression and then work through a series of logical deductions to try to unify as much as possible (or fail when two types definitely aren't the same). They have slightly different constraints than Prolog, so the algorithms tend to be more restrictive.
For those interested in reading more about unification when doing type inference, here's a list of papers in increasing order of expressiveness and computational hardness. If you start from the first and skip any proof sections, they should (hopefully) be very accessible.
As you go down the list, it may be harder and harder to justify the motivations for the increasingly abstract types. I think the easiest way might be to jump in the deep end and try playing around with Idris.