News for hackers. Stuff that matters.
Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by kragen on Wednesday April 27, 2016 @12:04AM (#11577758)
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 by krat0sprakhar on Wednesday April 27, 2016 @12:14AM (#11577784)
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 by kragen on Wednesday April 27, 2016 @03:29AM (#11578460)
I don't know if I understand unification well or not; I feel like the control flow in Algorithm W is still a bit of a mystery to me, but I suspect that this is more a function of the effort I've put into understanding it than of the adequacy of the explanations I've found. http://canonical.org/~kragen/sw/dev3/term-rewriting.scm was the last time I implemented unification, in August, and sort of represented my understanding of unification at the time — but looking at it now, I see that it only does pattern-matching, which is really only kind of half of unification. I think I did a more general first-order vaguely unificationy thing for queries on triple stores some years back, but the details are now fuzzy in this thing of mine that I flatter by calling it a mind.

So, yes! I'd love a detailed tutorial of unification step-by-step (or perhaps recursive function by recursive function, if that turns out to be simpler). Maybe it already exists somewhere, perhaps in a textbook, and I just haven't found it. Or maybe I got intimidated and need to calm down and work some exercises instead of going off to read Facebook and HN.

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by igravious on Wednesday April 27, 2016 @05:06AM (#11578801)
I second that. But I would also love to know why type inference and unification are so closely related. I mean, I learnt about Prolog (and thus unification) years ago. Like a decade or more later I'm learning about type systems (properly I mean, via type theory) and type inferencing and unification shows up. I kind of get that intensional typing schemes define typing relations and that logic programming is synonymous with relational programming but is that all there is to it?

The second thing I would like to say. And I've said this before. Languages like Ocaml and Haskell (never mind Agda, Coq, what have you) already have too much typing 'smarts' built into them. I would like to see -- hint, I'm probably going to have to get my hands dirty! -- an implementation in either a dynamically typed language like Ruby/Python/Perl/PHP/Javascript/… or a non-functional language like C/C++/Obj-C/…

What think ye?

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by Peaker on Wednesday April 27, 2016 @05:26AM (#11578881)
I can try to explain why HM type inference and unification are related.

If you take just the lambda calculus where you have:

1) Lambdas that bind variables

2) Usages of bound variables

3) Function applications

The inference rules for the first 2 are simple & straight-forward and require no unification.

For 1 (lambdas) - you create a fresh type variable (e.g: 'a') for the parameter type and infer the lambda body (e.g: 'T'), and the lambda's type is then 'a -> T'. While inferring the lambda body, you also pass the information that the parameter bound by the lambda has-type 'a'.

For 2 (variable usage), you just use the known type information that was passed down by the lambda inference.

For 3 (application), you need unification. Function application is between two subexpressions (e.g: 'f' and 'x'). You infer both of these recursively, and get 2 types (e.g: 'fType' and 'xType'). But you also know that 'fType' must look like: 'xType -> resType' because it's being applied to 'x'. You also know that 'resType' is the result of the entire application. So you have to unify 'fType' with 'xType -> resType'.

This is why inference relates to unification: You have 2 sources of information for 'fType' and 'xType' -- the recursive inference AND the fact they're being applied together.

This unification, by the way, is the only way that type information is learned for parameter types. If all parameter types are always specified (as in, e.g: C++) then formally, there's no type inference at all. So what C++ calls "local type inference" is formally just type checking.

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by eric_bullington on Wednesday April 27, 2016 @05:49AM (#11578961)
> I would like to see -- hint, I'm probably going to have to get my hands dirty! -- an implementation in either a dynamically typed language like Ruby/Python/Perl/PHP/Javascript/… or a non-functional language like C/C++/Obj-C/…

I understand where you're coming from. I'm working on a mini-ML in Python as a learning exercise for myself and possibly as a tutorial for others; will open source it soon.

As such, I've come across a few good resources:

check out Robert Small's Hindley-Milner in Python[0], as well as alehander42's Hermetic language in Python[1].

I also just found out about Hask, an implementation of many Haskell language features in Python. Looking at the source code, it's well-commented and clear, so I suspect I'll learn a lot from it as well [2].

Finally, even though it's not in a dynamic or non-functional language like you request, I highly recommend Andrej Bauer's Programming Language Zoo[3], which contains very simple and easy-to-understand implementations of various type systems in OCaml. Very elucidating.

0. http://smallshire.org.uk/sufficientlysmall/2010/04/11/a-hind...

1. https://github.com/alehander42/hermetic

2. https://github.com/billpmurphy/hask

3. http://andrej.com/plzoo/

Edit: Oh, and one more resource that's been extremely helpful has been "Introduction to Functional Programming through Lambda Calculus" by Michaelson. Well worth the cost of the book.

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by igravious on Wednesday April 27, 2016 @06:30AM (#11579185)
Brilliant, I'm attempting something very similar in Ruby :)

Will check out those links.

When I have something workable, I'll post it to Github as well and then we can see about creating some kind of umbrella structure?

A related idea I have is that what is needed is some kind of grammar interchange format, or typing-relation interchange format -- kind of like JSON (or Amazon's ION) but for this sort of work. In some ways that is what S-expressions are, maybe there is no need to reinvent the wheel but my hunch is that a domain specific format is needed. Apologies if this is a bit vague, it's a hunch, and I'm going by intuition.

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by eric_bullington on Wednesday April 27, 2016 @06:45AM (#11579246)
Check out RAML: https://github.com/raml-org/raml-spec Maybe it will fit the bill? It can even encode sum types. But I'm not sure if that's what you're looking for.

I'll ping you when I put my mini-ml in Python on Github.

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by igravious on Wednesday April 27, 2016 @08:08AM (#11579623)
That's not really what I mean. Take the file `parser.mly` from http://andrej.com/plzoo/html/miniml.html . See how it has it's own format for describing grammars. So does Yacc, so does X, Y, and Z. Is there an interchange format for parser generators?
Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by kragen on Tuesday May 03, 2016 @08:54AM (#11620137)
There's BNF, and there's DFDL, and there's just plain lists of productions without the extra decorations in BNF, but basically no. The issue is that each parser generator in current wide use has its particular funky set of limitations that you have to hack around one way or another when you write the grammar for it: it can't handle left recursion, or right recursion, or ambiguity, except in certain special cases (maybe if it doesn't continue for more than one token, or two syntax-tree levels), or it can handle them but has potentially exponential runtime, or it just arbitrarily resolves them in a certain way which may be adequate for your needs or may require you to restructure the grammar, or whatever. And then there are lots of ways that our languages aren't quite context-free, and different parsing systems have different ways to shoehorn that into a basically context-free framework.

I think it's maybe a solvable problem, but I haven't seen anyone try to solve it.

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by igravious on Wednesday April 27, 2016 @08:32AM (#11579771)
Hermetic is amusing. Hask is very like what I'm aiming towards, not PLZoo. I'm starting with a PEG library (https://kschiess.github.io/parslet/) and working my way up. I'd prefer to start with a GLL parser which could handle mildly context-sensitive grammars and work my way up but I think creating a PEG version as a proof of concept is the way to go first.

Thanks for the book reference!

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by sklogic on Wednesday April 27, 2016 @06:55AM (#11579288)
> an implementation in either a dynamically typed language

ML in Lisp and Prolog:

https://github.com/combinatorylogic/mbase/tree/master/src/l/...

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by BhavdeepSethi on Wednesday April 27, 2016 @12:53AM (#11577898)
No link to Columbia's PLT lectures? :)
Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by edmob on Wednesday April 27, 2016 @02:29AM (#11578238)
Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by eric_bullington on Wednesday April 27, 2016 @05:27AM (#11578888)
> Would you be interested in something along those lines?

Yes! That would be very cool to read.

I've been working on an implementation of Mini-ML in Python using Robert Small's Hindley-Milner in Python [0] (and also eagerly awaiting the rest of Diehl's series on writing a Haskell).

I understand the fundamentals of the algorithm, but even now I don't think I could yet implement it from scratch. I'd love to read a detailed tutorial.

By the way, those Cornell lecture notes you referenced have also been very helpful to me.

0. http://smallshire.org.uk/sufficientlysmall/2010/04/11/a-hind...

Re:Show HN: Hindley-Milner Type Inference Algorithm in OCaml by Peaker on Wednesday April 27, 2016 @05:18AM (#11578848)
Another really helpful resource to understand algorithm W inferring types for HM is Algorithm-W-Step-by-Step at [1].

[1]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65....