Why need recursive methods a type?

On Mon, Jul 25, 2011 at 3:29 PM, Antoras <mail@antoras.de> wrote:

When i want to use recursion to create a loop I need explicitly to
specify the return type of the method:

def loop(i: Int, xs: List[Int]): List[Int] =
  if (i < 10) loop(i+1, i :: xs) else xs

If I leave it I get an error. Why can't the compiler detect that only
the List `xs` is returned?

Because to type "loop" it probably needs to check the LUB of the if-expression, and since "loop" is not typed, it needs to be inferred, hence the recursive type inference, hence the error message.

Cheers,
√
--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

On 25.07.2011 15:42, √iktor Ҡlang wrote:

bBFOyQjJYirepS4qZygCA [at] mail [dot] gmail [dot] com" type="cite">

On Mon, Jul 25, 2011 at 3:29 PM, Antoras <mail [at] antoras [dot] de" rel="nofollow">mail@antoras.de> wrote:

When i want to use recursion to create a loop I need explicitly to
specify the return type of the method:

def loop(i: Int, xs: List[Int]): List[Int] =
  if (i < 10) loop(i+1, i :: xs) else xs

If I leave it I get an error. Why can't the compiler detect that only
the List `xs` is returned?

Because to type "loop" it probably needs to check the LUB of the if-expression, and since "loop" is not typed, it needs to be inferred, hence the recursive type inference, hence the error message.

What do you mean with LUB?

i guess the correct answer is because nobody implemented an algorithm for that and plugged it into the compiler. it's definately possible.
in this simple case, it would be enough just to ignore all recursive calls to figure out the return type

-------- Original-Nachricht --------
> Datum: Mon, 25 Jul 2011 15:42:49 +0200
> Von: "√iktor Ҡlang"
> An: Antoras
> CC: scala-user@googlegroups.com
> Betreff: Re: [scala-user] Why need recursive methods a type?

> On Mon, Jul 25, 2011 at 3:29 PM, Antoras wrote:
>
> > When i want to use recursion to create a loop I need explicitly to
> > specify the return type of the method:
> >
> > def loop(i: Int, xs: List[Int]): List[Int] =
> > if (i < 10) loop(i+1, i :: xs) else xs
> >
> > If I leave it I get an error. Why can't the compiler detect that only
> > the List `xs` is returned?
> >
>
> Because to type "loop" it probably needs to check the LUB of the
> if-expression, and since "loop" is not typed, it needs to be inferred,
> hence
> the recursive type inference, hence the error message.
>
> Cheers,
> √

On Mon, Jul 25, 2011 at 3:51 PM, Antoras <mail@antoras.de> wrote:

On 25.07.2011 15:42, √iktor Ҡlang wrote:

On Mon, Jul 25, 2011 at 3:29 PM, Antoras <mail@antoras.de> wrote:

When i want to use recursion to create a loop I need explicitly to
specify the return type of the method:

def loop(i: Int, xs: List[Int]): List[Int] =
  if (i < 10) loop(i+1, i :: xs) else xs

If I leave it I get an error. Why can't the compiler detect that only
the List `xs` is returned?

Because to type "loop" it probably needs to check the LUB of the if-expression, and since "loop" is not typed, it needs to be inferred, hence the recursive type inference, hence the error message.

What do you mean with LUB?

http://dictionary.reference.com/browse/least+upper+bound

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

> it's definately possible. in this simple case, it would be enough
> just to ignore all recursive calls to figure out the return type

There's no generic way for doing complete type inference under the
presence of subtyping as you not only have equalities to solve, but also
inequalities. This may lead to multiple solutions where non of them is
more general than the others. (Something I vaguely remember from my last
PL course, may the Scala folks correct me if I'm wrong.)

Scala has local type inference. It doesn't have Hindley Milner type inference which is difficult to combine with subtyping. According to Odersky it's not that it is impossible, but I guess it's still an active area of research. And since Scala started with an intention to integrate well with Java, strong subtyping support took precedence over HM ..

On Mon, Jul 25, 2011 at 8:24 PM, Lars Hupel <hupel@in.tum.de> wrote:

> it's definately possible. in this simple case, it would be enough
> just to ignore all recursive calls to figure out the return type

There's no generic way for doing complete type inference under the
presence of subtyping as you not only have equalities to solve, but also
inequalities. This may lead to multiple solutions where non of them is
more general than the others. (Something I vaguely remember from my last
PL course, may the Scala folks correct me if I'm wrong.)

--
Debasish Ghosh
http://manning.com/ghosh

Twttr: @debasishg
Blog: http://debasishg.blogspot.com
Code: http://github.com/debasishg

there might be cases that cannot be solved without hints from the programmer, but i have yet to see one. in the current case, the solution is obvious.

-------- Original-Nachricht --------
> Datum: Mon, 25 Jul 2011 16:54:19 +0200
> Von: Lars Hupel
> An: scala-user@googlegroups.com
> Betreff: [scala-user] Re: Why need recursive methods a type?

> > it's definately possible. in this simple case, it would be enough
> > just to ignore all recursive calls to figure out the return type
>
> There's no generic way for doing complete type inference under the
> presence of subtyping as you not only have equalities to solve, but also
> inequalities. This may lead to multiple solutions where non of them is
> more general than the others. (Something I vaguely remember from my last
> PL course, may the Scala folks correct me if I'm wrong.)
>

2011/7/25 √iktor Ҡlang :
>
>
> On Mon, Jul 25, 2011 at 3:29 PM, Antoras wrote:
>>
>> When i want to use recursion to create a loop I need explicitly to
>> specify the return type of the method:
>>
>> def loop(i: Int, xs: List[Int]): List[Int] =
>>   if (i < 10) loop(i+1, i :: xs) else xs
>>
>> If I leave it I get an error. Why can't the compiler detect that only
>> the List `xs` is returned?
>
> Because to type "loop" it probably needs to check the LUB of the
> if-expression, and since "loop" is not typed, it needs to be inferred, hence
> the recursive type inference, hence the error message.

But the type of this.loop(...) is necessarily the same as the type of
def loop so it isn't relevant to determining its type. Things are
trickier with mutual recursion, but self-recursion is so common (and
would be even more common without this annoyance) that it ought to be
handled.

2011/7/25 Jim Balter <Jim@balter.name>

2011/7/25 √iktor Ҡlang <viktor.klang@gmail.com>:
>
>
> On Mon, Jul 25, 2011 at 3:29 PM, Antoras <mail@antoras.de> wrote:
>>
>> When i want to use recursion to create a loop I need explicitly to
>> specify the return type of the method:
>>
>> def loop(i: Int, xs: List[Int]): List[Int] =
>>   if (i < 10) loop(i+1, i :: xs) else xs
>>
>> If I leave it I get an error. Why can't the compiler detect that only
>> the List `xs` is returned?
>
> Because to type "loop" it probably needs to check the LUB of the
> if-expression, and since "loop" is not typed, it needs to be inferred, hence
> the recursive type inference, hence the error message.

But the type of this.loop(...) is necessarily the same as the type of
def loop so it isn't relevant to determining its type. Things are
trickier with mutual recursion, but self-recursion is so common (and
would be even more common without this annoyance) that it ought to be
handled.

I'm not saying it couldn't be solved, I was merely trying to explain why it was like it was.
 

2011/7/25 √iktor Ҡlang :
>
>
> 2011/7/25 Jim Balter
>>
>> 2011/7/25 √iktor Ҡlang :
>> >
>> >
>> > On Mon, Jul 25, 2011 at 3:29 PM, Antoras wrote:
>> >>
>> >> When i want to use recursion to create a loop I need explicitly to
>> >> specify the return type of the method:
>> >>
>> >> def loop(i: Int, xs: List[Int]): List[Int] =
>> >>   if (i < 10) loop(i+1, i :: xs) else xs
>> >>
>> >> If I leave it I get an error. Why can't the compiler detect that only
>> >> the List `xs` is returned?
>> >
>> > Because to type "loop" it probably needs to check the LUB of the
>> > if-expression, and since "loop" is not typed, it needs to be inferred,
>> > hence
>> > the recursive type inference, hence the error message.
>>
>> But the type of this.loop(...) is necessarily the same as the type of
>> def loop so it isn't relevant to determining its type. Things are
>> trickier with mutual recursion, but self-recursion is so common (and
>> would be even more common without this annoyance) that it ought to be
>> handled.
>
> I'm not saying it couldn't be solved, I was merely trying to explain why it
> was like it was.

a) You said "needs" twice. b) I too was merely trying to explain something.

2011/7/26 Jim Balter <Jim@balter.name>

2011/7/25 √iktor Ҡlang <viktor.klang@gmail.com>:
>
>
> 2011/7/25 Jim Balter <Jim@balter.name>
>>
>> 2011/7/25 √iktor Ҡlang <viktor.klang@gmail.com>:
>> >
>> >
>> > On Mon, Jul 25, 2011 at 3:29 PM, Antoras <mail@antoras.de> wrote:
>> >>
>> >> When i want to use recursion to create a loop I need explicitly to
>> >> specify the return type of the method:
>> >>
>> >> def loop(i: Int, xs: List[Int]): List[Int] =
>> >>   if (i < 10) loop(i+1, i :: xs) else xs
>> >>
>> >> If I leave it I get an error. Why can't the compiler detect that only
>> >> the List `xs` is returned?
>> >
>> > Because to type "loop" it probably needs to check the LUB of the
>> > if-expression, and since "loop" is not typed, it needs to be inferred,
>> > hence
>> > the recursive type inference, hence the error message.
>>
>> But the type of this.loop(...) is necessarily the same as the type of
>> def loop so it isn't relevant to determining its type. Things are
>> trickier with mutual recursion, but self-recursion is so common (and
>> would be even more common without this annoyance) that it ought to be
>> handled.
>
> I'm not saying it couldn't be solved, I was merely trying to explain why it
> was like it was.

a) You said "needs" twice. b) I too was merely trying to explain something.

Yup, that's what the current impl needs to do
Question is: Do we need the current impl? ;-)
 

2011/7/25 √iktor Ҡlang :
>
>
> 2011/7/26 Jim Balter
>>
>> 2011/7/25 √iktor Ҡlang :
>> >
>> >
>> > 2011/7/25 Jim Balter
>> >>
>> >> 2011/7/25 √iktor Ҡlang :
>> >> >
>> >> >
>> >> > On Mon, Jul 25, 2011 at 3:29 PM, Antoras wrote:
>> >> >>
>> >> >> When i want to use recursion to create a loop I need explicitly to
>> >> >> specify the return type of the method:
>> >> >>
>> >> >> def loop(i: Int, xs: List[Int]): List[Int] =
>> >> >>   if (i < 10) loop(i+1, i :: xs) else xs
>> >> >>
>> >> >> If I leave it I get an error. Why can't the compiler detect that
>> >> >> only
>> >> >> the List `xs` is returned?
>> >> >
>> >> > Because to type "loop" it probably needs to check the LUB of the
>> >> > if-expression, and since "loop" is not typed, it needs to be
>> >> > inferred,
>> >> > hence
>> >> > the recursive type inference, hence the error message.
>> >>
>> >> But the type of this.loop(...) is necessarily the same as the type of
>> >> def loop so it isn't relevant to determining its type. Things are
>> >> trickier with mutual recursion, but self-recursion is so common (and
>> >> would be even more common without this annoyance) that it ought to be
>> >> handled.
>> >
>> > I'm not saying it couldn't be solved, I was merely trying to explain why
>> > it
>> > was like it was.
>>
>> a) You said "needs" twice. b) I too was merely trying to explain
>> something.
>
> Yup, that's what the current impl needs to do

An implementation does precisely what it does; needs are not
attributes of implementations -- that's a category error. My comment
was a reasonable response to an *apparent* claim that it is necessary
to know the type of loop in order to infer the type of loop -- whether
or not that's the claim you intended to make, such a claim is false.

> Question is: Do we need the current impl? ;-)

No, of course not. But a more sensible question is whether there is a
feasible change to the implementation that would remove the
requirement that methods be typed merely because they are
self-recursive, and that's the question I tried to address.

On Monday 25 July 2011, Dennis Haupt wrote:
> there might be cases that cannot be solved without hints from the
> programmer, but i have yet to see one. in the current case, the
> solution is obvious.

Is obviousness computable?

RRS

obviously not :D

but for the current case, this would work:

val returnType = if (allReturnPoints.forAll(e => e.solveableWithCurrentAlgorithm || e.isSimpleRecursiveCallOnSelf) allReturnPoints.find(_.solveableWithCurrentAlgorithm).returnType else None

-------- Original-Nachricht --------
> Datum: Wed, 27 Jul 2011 21:29:22 -0700
> Von: Randall R Schulz
> An: scala-user@googlegroups.com
> Betreff: Re: [scala-user] Re: Why need recursive methods a type?

> On Monday 25 July 2011, Dennis Haupt wrote:
> > there might be cases that cannot be solved without hints from the
> > programmer, but i have yet to see one. in the current case, the
> > solution is obvious.
>
> Is obviousness computable?
>
>
> RRS

On Thu, Jul 28, 2011 at 05:04, Dennis Haupt wrote:
> obviously not :D
>
> but for the current case, this would work:
>
> val returnType = if (allReturnPoints.forAll(e => e.solveableWithCurrentAlgorithm || e.isSimpleRecursiveCallOnSelf) allReturnPoints.find(_.solveableWithCurrentAlgorithm).returnType else None

I'd go further. If @tailrec would be true, then the return type can be
inferred from the non-recursive calls. The type inference algorithm,
however, is not exactly easily changed.

Hi,


The question would be if the algorithm could be enhanced, making it recognize more return types, without introducing any "false positives"...

Thanks,

Simon

i don't know how the algorithm currently works. if it doesn't require
years of studying, i might even take a look at it. where can i find it?

Am 28.07.2011 18:10, schrieb Simon Ochsenreither:
> Hi,
>
>
> The question would be if the algorithm could be enhanced, making it
> recognize more return types, without introducing any "false positives"...
>
> Thanks,
>
> Simon