Why does C# infer this while Scala doesn't?

[mar]

Out of curiousity, I wanted to implement a generic iterative fold/Aggregate function in these languages to see how they compared. They're both quite straight forward and low level:

C#
public T Aggr<T>(IEnumerable<T> eble, Func<T, T, T> fn) {
    var etor = eble.GetEnumerator();
    etor.MoveNext();
    var res = etor.Current;
    while (etor.MoveNext())
        res = fn(res, etor.Current);

    return res;
}

Scala
def aggr[T](iterable: Iterable[T], fn: (T, T) => T): T = {
    val it = iterable.iterator
    var res = it.next
    while (res.hasNext)
        res = fn(res, res.next)

    res
}

Disregarding my lack of respect for best practices, the C# code is callable without passing any type information while I have to annotate the Scala method at call site.

Why is it that, in this scenario, C# makes the connection while scalac fails? Moving the function to its own parameter list like so solves the problem:
def aggr[T](iterable: Iterable[T])(fn: (T, T) => T): T = { ...

.. so its obviously able to reevaluate the situation if you force it. It's almost like it's passing over the method twice if it has to, and failing lazily when it doesn't.

My question is: if C# can do this with its (as I understand it) limited inference, what's keeping Scala from adopting the same strategy?

[Andreas Hofstadler]

Just change the signature to

def aggr[T](iterable: Iterable[T])(fn: (T, T) => T): T = ....

Type inference only infers types from one parameter list to the next, not inside a single parameter list.

Too tired to find it in the language specification now.

On 2012-09-12 23:38, mar wrote:

Out of curiousity, I wanted to implement a generic iterative fold/Aggregate function in these languages to see how they compared. They're both quite straight forward and low level:

C#
public T Aggr<T>(IEnumerable<T> eble, Func<T, T, T> fn) {
    var etor = eble.GetEnumerator();
    etor.MoveNext();
    var res = etor.Current;
    while (etor.MoveNext())
        res = fn(res, etor.Current);

    return res;
}

Scala
def aggr[T](iterable: Iterable[T], fn: (T, T) => T): T = {
    val it = iterable.iterator
    var res = it.next
    while (res.hasNext)
        res = fn(res, res.next)

    res
}

Greets

Andi

[Sonnenschein]

Sorry, but your code below does not compile. Nevertheless, you may use your signature to let infer types at call site as expected:

def aggr[T](iterable: Iterable[T], fn: (T, T) => T) {}
aggr(List(1,2), (a: Int, b: Int) => a + b)

So where is the problem?

[mar]

Thank you for your reply :)

Two parameter lists works as I mentioned earlier. What I'm wondering is how the C# inferrer differs from Scala in the case of a single parameter list (since that's the only straight way to compare them using my example).

[mar]

I managed to mess it up as I was typing the examples, the working code is

def aggr[T](iterable: Iterable[T], fn: (T, T) => T): T = {

    val it = iterable.iterator

    var res = it.next

    while (it.hasNext)

        res = fn(res, it.next)

    res

}

I know that annotating the types work, the question is why it doesn't work without them.

[nicola...@gmail.com]

There is a discussion relating to that precise point in the comments
of this post:

http://pchiusano.blogspot.co.uk/2011/05/making-most-of-scalas-extremely-limited.html

This should help answer your question.

[Sonnenschein]

Ok, Nicolas seems to have better understood your concern.
Just to add:
1) consider to bank on Iterator's sliding instead of programming aggr anew
2) if programming on your own, never call next without a prior hasNext

[Alec Zorab]

Based on his mail, I think he's aware that he's ignored good practice,
and has done so because he was trying to ask his question cleanly ;)

[Razvan Cojocaru]

So now that we understand why, back to the original question: why?

I understand why the current compiler doesn't do it: because it chose not
to! I however don't see any reasons why it shouldn't do it (i.e. the
inferred types propagate in the parm list) do you?

Cheers,
Razie

[Josh Suereth]

def foo[T](one: T, two: T) = ...

foo("HI", 5)  // You would be annoyed if this inferred String and didn't allow Int then.

Scala has currying partly so you can choose where/how inference looks a bit.  It's by no means perfect, but it does help.

[Razvan Cojocaru]

Wow! That freaked me out for a second J…

 

I see your point, not that it seems too useful in this case to essentially typecast all to Any…

 

scala> def fooo[T](a:T,b:T)=b

fooo: [T](a: T, b: T)T

 

scala> fooo("a",4)

res2: Any = 4

 

cheers,

Razie

[Ken Scambler]

So it has to lock in the T type when it gets to the first parameter; it can't wait and infer T=Any once it's found all the parameters?

[Matthew Pocock]

So consider fooo("a", new StringBuffer()) - in this case it will infer something more specific than Any, because String and StringBuffer share a more specific common supertype in CharSequence.

M

--

Dr Matthew Pocock

Integrative Bioinformatics Group, School of Computing Science, Newcastle University

mailto: turingate...@gmail.com

gchat: turingate...@gmail.com

msn: matthew...@yahoo.co.uk

irc.freenode.net: drdozer

skype: matthew.pocock

tel: (0191) 2566550

mob: +447535664143

[Daniel Sobral]

On Thu, Sep 13, 2012 at 7:59 PM, Ken Scambler <ken.sc...@gmail.com> wrote:

So it has to lock in the T type when it gets to the first parameter; it can't wait and infer T=Any once it's found all the parameters?

That would be backtracking. Backtracking is usually a sign of serious performance problems in the algorithm.

--
Daniel C. Sobral

I travel to the future all the time.

[Rafał Krzewski]

I was wondering if it was possible to enhance performance of the Scala compiler using GPGPU.

I don't know enough of the compiler theory to if it's feasible at all, but I can only imagine that some of the problems the compiler is dealing with correspond to graph traversal / manipulation problems.

Those problems are tractable using parallel algorithms, and most of computers in use have between a dozen (Intel HD graphics integrated in mobile CPUs) and a thousand (consumer grade nVidia / ATI graphics cards) processing cores that just sit there unused when the CPU toils hard compiling Scala code... If the compiler could tap into that potential, quite a few problems could be solved by sheer brute force, if one does not mind turning some electricity into heat in the process :)

I hope I am making sense here. Also, my apologies if this subject was extensively discussed before.

Cheers,
Rafał

[Alec Zorab]

You might find this interesting: http://code.google.com/p/scalacl/

[Rex Kerr]

That sounds like a strange fit to me--compilers need to do a lot of symbolic work (tree manipulation, map lookups, etc.), which is exactly the sort of stuff that is tricky to get GPGPU code to do well unless you can turn your symbolic manipulation problem into matrix math or something similar (min cut, etc.).

I'd think that one wouldn't resort to GPU programming until one had first made sure that the most commonly used data structures were the correct ones to allow the most efficient algorithms to be used (which themselves were implemented near-optimally), and second had parallelized for conventional CPUs.

  --Rex

[mar]

That's an explanation I can accept :-)

I still don't see where the difference in resolving types lies between C# and Scala, it would be great if anyone could shed some light on that.

Regarding multiple parameter lists, what's the overhead cost? I think I read that (X)(Y) is syntactic sugar for X => Y (yo dawg, I put put some sugar in your sugar..) which would imply that closures are involved.

[mar]

I was responding to Josh Suereth in my previous post, but the quote seems to have been eaten. My apologies for double posting.

[Jason Zaugg]

Scala methods with 0, 1, or N parameter lists all compile to a JVM
method with a single parameter list.

The only time a closure is involved is if you partially apply:

def foo(a: Int, b: Int) = a + b
def bar(a: Int)(b: Int) = a + b

val f: Int => Int = foo(1, _)
val b: Int => Int = bar(1)

There isn't any difference between `f` and `b` these, performance wise.

-jason

[Seth Tisue]

On Sat, Sep 15, 2012 at 12:06 PM, Jason Zaugg <jza...@gmail.com> wrote:
> Scala methods with 0, 1, or N parameter lists all compile to a JVM
> method with a single parameter list.

I've been wondering, is that just a contingent fact about a particular
implementation, or is this somehow required by the spec?

In other words, could a valid implementation use currying instead of
smashing parameter lists together?

--
Seth Tisue | Northwestern University | http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/