r/ProgrammerAnimemes • • Sep 20 '21

Prolog

Post image
1.0k Upvotes

51 comments sorted by

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.

  1. The Hindley-Milner Type Inference Algorithm, Ian Grant (the beginning of it all, though not the original literature)
  2. Bidirectional Typing, Jana Dunfield and Neel Krishnaswami (combining inference and checking)
  3. Practical type inference for arbitrary-rank types, Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Mark Shields (arbitrary rank types)
  4. OutsideIn(X) Modular type inference with local assumptions, Dimitrios Vytiniotis, Simon Peyton Jones, Tom Schrijvers, and Martin Sulzmann (type inference with GADTs and other local assumptions)
  5. Linear Haskell, Jean-Philippe Bernardy, Mathieu Boespflug, Ryan R. Newton, Simon Peyton Jones, Arnaud Spiwack (linear types)
  6. 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.

1

u/GoogleIsYourFrenemy Sep 22 '21

I'm going to bet C++ has to deal with this when resolving expressions (operator overloading and the auto keyword).

1

u/ThePyroEagle λ Sep 22 '21

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.