68

The F# compiler appears to perform type inference in a (fairly) strict top-to-bottom, left-to-right fashion. This means you must do things like put all definitions before their use, order of file compilation is significant, and you tend to need to rearrange stuff (via |> or what have you) to avoid having explicit type annotations.

How hard is it to make this more flexible, and is that planned for a future version of F#? Obviously it can be done, since Haskell (for example) has no such limitations with equally powerful inference. Is there anything inherently different about the design or ideology of F# that is causing this?

J Cooper
  • 16,891
  • 12
  • 65
  • 110
  • 4
    I actually dislike the question, but it's netted a few fantastic and illuminating responses already, so I begrudgingly upvote as well :) – Brian Jul 02 '10 at 13:04
  • 7
    @J Cooper: "Haskell (for example) has no such limitations with equally powerful inference". Haskell is nowhere near having equally powerful type inference when you consider impurities or performance. For example, Haskell's `floor` function typically runs orders of magnitude slower than any other compiled language precisely because its failure to infer the correct static type leaves it resorting to run-time dispatch. Also, if I stop removing the top-level type annotation from a `randIntList` function I have here then it stops compiling with the infamous `ambiguous type variable` error. – J D Sep 21 '10 at 20:20
  • 8
    I like the question because I suppose almost everyone who've just started to learn F# have two thoughts: "WOW, F# is so powerful!" and "WTF, why F# can't do this silly inference?!" :) – Dmitrii Lobanov Aug 19 '11 at 05:19
  • I am new to F#. Right now, I'm trying to figure out the FS0030: Value restriction errors I get occasionally get when working with generic functions. – ExternalReality Dec 17 '11 at 21:33

4 Answers4

51

Regarding "Haskell's equally powerful inference", I don't think Haskell has to deal with

  • OO-style dynamic subtyping (type classes can do some similar stuff, but type classes are easier to type/infer)
  • method overloading (type classes can do some similar stuff, but type classes are easier to type/infer)

That is, I think F# has to deal with some hard stuff that Haskell does not. (Almost certainly, Haskell has to deal with some hard stuff that F# does not.)

As is mentioned by other answers, most of the major .NET languages have the Visual Studio tooling as a major language design influence (see e.g. how LINQ has "from ... select" rather than the SQL-y "select... from", motivated by getting intellisense from a program prefix). Intellisense, error squiggles, and error-message comprehensibility are all tooling factors that inform the F# design.

It may well be possible to do better and infer more (without sacrificing on other experiences), but I don't think it's among our high priorities for future versions of the language. (The Haskellers may see F# type inference as somewhat weak, but they are probably outnumbered by the C#ers who see F# type inference as very strong. :) )

It might also be hard to extend the type inference in a non-breaking fashion; it is ok to change illegal programs into legal ones in a future version, but you have to be very careful to ensure previously-legal programs do not change semantics under new inference rules, and name resolution (an awful nightmare in every language) is likely to interact with type-inference-changes in surprising ways.

Brian
  • 117,631
  • 17
  • 236
  • 300
  • 1
    See also http://lorgonblog.wordpress.com/2009/10/25/overview-of-type-inference-in-f/ – Brian Feb 24 '11 at 08:52
  • 1
    Oh without method overloading its a bit easier for Haskell. Function definition (parameter and return types) are decipherable unambiguously.. – nawfal Dec 16 '13 at 17:27
19

I think that the algorithm used by F# has the benefit that it is easy to (at least roughly) explain how it works, so once you understand it, you can have some expectations about the result.

The algorithm will always have some limitations. Currently, it is quite easy to understand them. For more complicated algorithms, this could be difficult. For example, I think you could run into situations where you think that the algorithm should be able to deduce something - but if it was general enough to cover the case, it would be non-decidable (e.g. could keep looping forever).

Another thought on this is that checking the code from the top to the bottom corresponds to how we read code (at least sometimes). So, maybe the fact that we tend to write the code in a way that enables type-inference also makes the code more readable for people...

holsee
  • 1,974
  • 2
  • 27
  • 43
Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • 11
    On your last point, and I may be weird in this way, I tend to group related functions in the opposite way (in languages that let me). For example, say I have a complicated function C, and function A and B both use function C, then I order my functions top to bottom A, B, C. I suppose I like reading it that way because of the way the implementation unravels (show me the big picture, then the details). That being said, I haven't minded the ordering F# forces too much, though I haven't worked on big projects with it. – Stephen Swensen Jul 02 '10 at 01:22
  • 3
    The ordering you prefer is most natural with call-by-name because it reflects the order of evaluation. With call-by-value the F# way is more natural - particularly since definitions may have immediate effects. – RD1 Aug 05 '10 at 15:04
18

F# uses one pass compilation such that you can only reference types or functions which have been defined either earlier in the file you're currently in or appear in a file which is specified earlier in the compilation order.

I recently asked Don Syme about making multiple source passes to improve the type inference process. His reply was "Yes, it’s possible to do multi-pass type inference. There are also single-pass variations that generate a finite set of constraints.

However these approaches tend to give bad error messages and poor intellisense results in a visual editor."

http://www.markhneedham.com/blog/2009/05/02/f-stuff-i-get-confused-about/#comment-16153

Robert Harvey
  • 178,213
  • 47
  • 333
  • 501
  • 2
    Interesting. I don't seem to get great intellisense help for plain F# functions anyway; mostly it seems to come into play when you do Module.somefunc or use a class (which basically kills type inference anyway). I wonder how set-in-stone this design choice is. – J Cooper Jul 01 '10 at 23:42
  • 2
    It sounds like you're not creating VS projects for your code, or that you're leaving syntax errors in your code. As long as you don't do these, the intellisense is a massive help and will report the types of every variable on mouse hover, plus immediately indicate type errors. When I program in F# this makes me very nimble - it's a massively important feature, and the cost is just a rare use of |> and very rarely type constraints. – RD1 Aug 05 '10 at 15:18
13

The short answer is that F# is based on the tradition of SML and OCaml, whereas Haskell comes from a slightly different world of Miranda, Gofer, and the like. The differences in historical tradition are subtle, but pervasive. This distinction is paralleled in other modern languages too, such as the ML-like Coq which has the same ordering restrictions vs the Haskell-like Agda which doesn't.

This difference is related to lazy vs strict evaluation. The Haskell side of the universe believes in laziness, and once you already believe in laziness the idea of adding laziness to things like type inference is a no-brainer. Whereas in the ML side of the universe whenever laziness or mutual recursion is necessary it must be explicitly noted by the use of keywords like with, and, rec, etc. I prefer the Haskell approach because it results in less boilerplate code, but there are a lot of folks who think it's better to make these things explicit.

wren romano
  • 669
  • 4
  • 5
  • 1
    @ng: "...there are a lot of folks who think it's better to make these things explicit". A lot of folks would rather explicitly annotate laziness than strictness and impurities because laziness is very rarely useful whereas strictness and impurities are ubiquitous (even in real Haskell code). – J D Jul 10 '11 at 08:41
  • 5
    @JonHarrop That's true. But it changes the semantics of the code. A lot of folks would argue with you that laziness is very useful very often and enables different approaches to solving a problem. It's pretty clear that the ability to do both is best, which Haskell does indeed offer, albeit biased towards the lazy side instead of the strict side like most languages. – John Tyree May 15 '13 at 12:12