Alex Rivera | Logout

Is it possible to extend the Scala compiler to infer return types of recursive methods?

Asked 2011-10-11T18:57:32.510
12

The Scala compiler currently cannot infer return types of recursive methods as in the following code

def foo(i:Int) = if (i > 0) foo (i-1) else 0

Is there any ambuigity in the above statement? (i.e., is any type other than Int possible?)

I can imagine that in more complex example, it will be difficult to infer the type.

Is it possible to further characterize the cases of recursive methods where we can(not) infer the types?

[EDIT:] The compiler is intelligent enough to figure out that String is incorrect.

scala> def foo(i:Int):String = if (i > 0) foo (i-1) else 0
<console>:5: error: type mismatch;
found   : Int(0)
required: String
scala
Edit
Report

1 Answer

3

You'd need an unification algorithm much more powerful than what Scala provides. Scala does type checking left to right, top to bottom. So the inference would go somewhat like this:

What is the type of expression "if (i > 0) foo(i - 1) + 1 else 0"?
Unify "foo(i - 1) + 1" and "0"
What is the type of "foo(i - 1) + 1"?
What is the type of "foo(i - 1)"
What is "foo"?
foo is the current definition, so we don't know it's type
error

if you did the if the other way around you'd have:

What is the type of expression "if (i <= 0) 0 else foo(i - 1) + 1 "?
Unify "0" and "foo(i - 1) + 1"
What is the type of "0"?
"0" <: Int >: Nothing
What is the type of "foo(i - 1) + 1"?
What is the type of "foo(i - 1)"
What is "foo"?
foo is the current definition, so we don't know it's type
error
answered 2011-10-12T22:46:20.050

Your Answer