Does scala use Hindley - Milner type inference?

the inference system works 'flow based'

On Wed, Dec 23, 2009 at 4:22 PM, Nilanjan Raychaudhuri <nraychaudhuri [at] gmail [dot] com> wrote:

Hi ,

Lately I am seeing comparison of Scala with ML languages and how they are more succinct compare to Scala. I understand that ML family of languages use Hindley - Milner type inference
but I am not sure about Scala, what algorithm does it use to inter types. Is it only based on single expression?

Thanks
Nilanjan

--
  __~O
 -\ <,
(*)/ (*)

reality goes far beyond imagination

On Wednesday December 23 2009, Nilanjan Raychaudhuri wrote:
> Hi ,
>
> Lately I am seeing comparison of Scala with ML languages and how they
> are more succinct compare to Scala. I understand that ML family of
> languages use Hindley - Milner type inference
> but I am not sure about Scala, what algorithm does it use to inter
> types. Is it only based on single expression?

Scala does not use Hindley-Milner type inference. My very limited
understanding is that Scala's incorporation of inheritance is at cross
purposes with H-M type inference.

> Thanks
> Nilanjan

Randall Schulz

No, Scala does not use Hindley-Milner type inference.  Scala's type system is far too powerful and has a number of features which make it fundamentally incompatible with type reconstruction.

Instead, Scala's type inference is based on declaration-local information, appropriately known as "local type inference".  Consider the following statement:

val str: String = "Hey there!"

The compiler must compute the type of the expression "Hey there!" in order to check that it matches the declared type, String.  Java's compiler does exactly the same thing.  The important thing to notice is that the computation doesn't require any context.  Scala merely allows you to omit the type annotation and bank off of this computation which the compiler had to perform regardless.

The important thing, and what makes this process decidable, is the fact that computing the type for str can be done in a single pass.  We don't have to compute a constraint set for the entire scope prior to assigning a type for this single value.  Intuitively, we are asking the question "what type is ...?" for str and str alone.  Once we figure out str, we can move on and ask the question for other values as necessary, but always one at a time.  For example:

val str = "Hey there!"
val str2 = str + "  Uhm?"

We need to infer the types of both str and str2.  However, we do it by first looking at str, getting its type and then looking at str2.  By the time we get to str2, we've already affixed a type to str.  The type inference algorithm just chugs through the code in one direction, never backtracking to try to get a "better" type for something it already looked at.

This is what leads to limitations like not being able to infer types for parameters.  For example:

def foo(str) = {
  val str2 = str + "  Uhm?"
  ...
}

Let's just imagine that Scala's inference algorithm was trying to infer types for str and str2 in this snippet.  First it looks at str, but it doesn't have any context to use in trying to pin down a type, so let's just imagine that it assigns "Nothing" and moves on.  Next, it comes down to str2.  At this point, it could infer a more specific type for str, specifically { def +(s: String): Any }.  However, we can't just go back and "fix" the type for str because the algorithm only moves in one direction.  Hence, we must explicitly annotate all parameters and all recursive methods/values.

I hope this helped to clarify things somewhat.  Scala's type inference algorithm really is quite simple, my explanation was simply an attempt to show why the algorithm obviates any possibility of inferring more complex things (like method parameters).

Daniel

On Wed, Dec 23, 2009 at 9:22 AM, Nilanjan Raychaudhuri <nraychaudhuri [at] gmail [dot] com> wrote:

Hi ,

Lately I am seeing comparison of Scala with ML languages and how they are more succinct compare to Scala. I understand that ML family of languages use Hindley - Milner type inference
but I am not sure about Scala, what algorithm does it use to inter types. Is it only based on single expression?

Thanks
Nilanjan

Thanks a lot, it helped

On Wed, Dec 23, 2009 at 11:08 AM, Daniel Spiewak <djspiewak [at] gmail [dot] com> wrote:

No, Scala does not use Hindley-Milner type inference.  Scala's type system is far too powerful and has a number of features which make it fundamentally incompatible with type reconstruction.

Instead, Scala's type inference is based on declaration-local information, appropriately known as "local type inference".  Consider the following statement:

val str: String = "Hey there!"

The compiler must compute the type of the expression "Hey there!" in order to check that it matches the declared type, String.  Java's compiler does exactly the same thing.  The important thing to notice is that the computation doesn't require any context.  Scala merely allows you to omit the type annotation and bank off of this computation which the compiler had to perform regardless.

The important thing, and what makes this process decidable, is the fact that computing the type for str can be done in a single pass.  We don't have to compute a constraint set for the entire scope prior to assigning a type for this single value.  Intuitively, we are asking the question "what type is ...?" for str and str alone.  Once we figure out str, we can move on and ask the question for other values as necessary, but always one at a time.  For example:

val str = "Hey there!"
val str2 = str + "  Uhm?"

We need to infer the types of both str and str2.  However, we do it by first looking at str, getting its type and then looking at str2.  By the time we get to str2, we've already affixed a type to str.  The type inference algorithm just chugs through the code in one direction, never backtracking to try to get a "better" type for something it already looked at.

This is what leads to limitations like not being able to infer types for parameters.  For example:

def foo(str) = {
  val str2 = str + "  Uhm?"
  ...
}

Let's just imagine that Scala's inference algorithm was trying to infer types for str and str2 in this snippet.  First it looks at str, but it doesn't have any context to use in trying to pin down a type, so let's just imagine that it assigns "Nothing" and moves on.  Next, it comes down to str2.  At this point, it could infer a more specific type for str, specifically { def +(s: String): Any }.  However, we can't just go back and "fix" the type for str because the algorithm only moves in one direction.  Hence, we must explicitly annotate all parameters and all recursive methods/values.

I hope this helped to clarify things somewhat.  Scala's type inference algorithm really is quite simple, my explanation was simply an attempt to show why the algorithm obviates any possibility of inferring more complex things (like method parameters).

Daniel

On Wed, Dec 23, 2009 at 9:22 AM, Nilanjan Raychaudhuri <nraychaudhuri [at] gmail [dot] com> wrote:

Hi ,

Lately I am seeing comparison of Scala with ML languages and how they are more succinct compare to Scala. I understand that ML family of languages use Hindley - Milner type inference
but I am not sure about Scala, what algorithm does it use to inter types. Is it only based on single expression?

Thanks
Nilanjan