Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Hindley-Milner Type Inference Algorithm in OCaml

github.com

Post reply on HN
Print view View original

1–10 of 30 posts

Re: Show HN: Hindley-Milner Type Inference Algorithm in OCaml

#2

Post by kragen »

This is cool! It's nice to have a bite-sized runnable illustration of HM. Maybe I will finally be able to understand it — both the code and the linked lecture notes (http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec...) look pretty informative. I don't think I can digest it in time to comment before it scrolls off the HN front page.

It's a little unfortunate that this version doesn't include let-polymorphism, since that's necessary for parametrically polymorphic functions to be actually polymorphic, and it's not a recent addition — it's in the original Damas-Milner paper. All the other stuff about tuples, lists, sum types, and whatnot can be emulated with functions, but not let-polymorphism, not without a potentially exponential blowup in the program size.

Re: Show HN: Hindley-Milner Type Inference Algorithm in OCaml

#3

Post by krat0sprakhar »

kragen wrote: post #2

This is cool! It's nice to have a bite-sized runnable illustration of HM. Maybe I will finally be able to understand it — both the code and the linked lecture notes ( http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec... ) look pretty informative. I don't think I can digest it in time to comment before it scrolls off the HN front page. It's a little unfortunate that this version doesn't include let-polymorp…

Thanks for the feedback! This is actually a smaller part of a much bigger full-blown type-inferred programming language[0], we've been working on as a part of course in school. Our plan was to directly add type-inference in the language but after reading through Stephen Diehl's tutorial[1] we were intimidated and wanted to have a working version on a bite-sized language.

I'm assuming a lot developers like me would be keen to understand how HM works, so I was considering writing a detailed tutorial of the unification algorithm step-by-step. Would you be interested in something along those lines?

[0] - http://www.cs.columbia.edu/~sedwards/classes/2016/4115-sprin...

[1] - http://dev.stephendiehl.com/fun/006_hindley_milner.html

Re: Show HN: Hindley-Milner Type Inference Algorithm in OCaml

#5

Post by BhavdeepSethi »

krat0sprakhar wrote: post #3
kragen wrote: post #2

This is cool! It's nice to have a bite-sized runnable illustration of HM. Maybe I will finally be able to understand it — both the code and the linked lecture notes ( http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec... ) look pretty informative. I don't think I can digest it in time to comment before it scrolls off the HN front page. It's a little unfortunate that this version doesn't include let-polymorp…

Thanks for the feedback! This is actually a smaller part of a much bigger full-blown type-inferred programming language[0], we've been working on as a part of course in school. Our plan was to directly add type-inference in the language but after reading through Stephen Diehl's tutorial[1] we were intimidated and wanted to have a working version on a bite-sized language. I'm assuming a lot developers like me would be…

No link to Columbia's PLT lectures? :)

Re: Show HN: Hindley-Milner Type Inference Algorithm in OCaml

#8

Post by bsaul »

I remember doing this in a practical exercice session with a teacher at university. We coded the algorithm, and i kept saying to myself that what i was coding didn't make any sense. I only understood many years later what i did that day, and how important it was.

Re: Show HN: Hindley-Milner Type Inference Algorithm in OCaml

#9

Post by edmob »

BhavdeepSethi wrote: post #5
krat0sprakhar wrote: post #3

Earlier quoted context omitted.

Thanks for the feedback! This is actually a smaller part of a much bigger full-blown type-inferred programming language[0], we've been working on as a part of course in school. Our plan was to directly add type-inference in the language but after reading through Stephen Diehl's tutorial[1] we were intimidated and wanted to have a working version on a bite-sized language. I'm assuming a lot developers like me would be…

No link to Columbia's PLT lectures? :)

Link to the PLT course home page: http://www.cs.columbia.edu/~sedwards/classes/2016/4115-sprin...

Re: Show HN: Hindley-Milner Type Inference Algorithm in OCaml

#10

Post by Patient0 »

catnaroek wrote: post #6

Oleg has a nice article on how to implement OCaml-style type inference. It's a more sophisticated approach than just Algorithm W: http://okmij.org/ftp/ML/generalization.html

For me, this article was the one where it "clicked": http://okmij.org/ftp/Haskell/AlgorithmsH.html#teval. Summary: type inference is just "evaluating" the program/expression, but the result is a type instead of a value. Each time you evaluate a function call, use unification to bind the arguments rather than pattern matching. Another way to understand it: pattern matching only works "one way", whereas unification works "both ways" - implying the caller's types as well as the callee's types. It also has a nice introduction of using a monad to simplify state management.
Post reply on HN