Counter-intuitive syntax for loop termination

[Boris Hollas]

Hello,

I've tried to implement the linear search, which revealed some rather
counter-intuitive behavior of Scala. The explicit implementation,
without using exists, requires to exit a loop. This approach

(1) def ls(x: Int, a: Array[Int]) = {
for(i <- 0 to a.length -1)
if(a(i) == x) i
-1
}

is seemingly compiled into a constant function. The second approach

(2) def ls(x: Int, a: Array[Int]) = {
for(i <- 0 to a.length -1)
if(a(i) == x) return i
-1
}

didn't compile because the return type was required. Finally,

(3) def ls(x: Int, a: Array[Int]): Int = {
for(i <- 0 to a.length -1)
if(a(i) == x) return i
-1
}

seems to work.

For someone without deep knowledge of Scala (think of students that
attend a one-semester course) program (1) doesn't do what he expects,
and Scala 2.9 doesn't even give a warning. This is a usability bug at least.

Furthermore, the requirement to use a return keyword violates the design
principle of regularity, ie similar things should looks similar and
there shouldn't be surprising exceptions.

Although program (2) is not recursive, its return type is not inferred.
Why this? Again, a violation of regularity.

Why doesn't the compiler discover that the for-loop may be terminated
prematurely in (1) and translate the code to (3)?

-Boris

[Alex Repain]

(1) : The program does what is expected. In Scala the last value computed is returned by default. The last computed in the function body of (1) will always be -1.

(2) : 'return' requires a return type. Most of times though, you can write your code without using 'return' at all, and it is the preferred style. So instead of 'return' being a requirement that violates a principle of regularity, not using 'return' is a recommandation, and what is at fault is your algorithm design (i.e. don't use a for-comprehension in the first place).

Why using 'return' needs an explicit return type, I'm not sure but there is probably a reason. Compiler guys, to the rescue ? But this is the work of the type inferer, which actually does only what it can. This is not an inconsistency of the language, because the language specs are not including the inference scheme, if I remember correctly. Thus, type inference may change its behaviour in Scala without modfications to the specs.

(3) : You can even put the if in the for-comprehension, ( it translates to a call to 'filter' somewhere in the chain call) :

def ls(x: Int, a: Array[Int]): Int = {

    for (i <- 0 to a.length -1; if a(i) == x) return i
    -1
}

But really, a 'for' is not the way to go here. You don't want a full traversal, so there are methods that handle aborted traversals for you.

Why doesn't the compiler discover that the for-loop may be terminated prematurely in (1) and translate the code to (3)?

-Boris

Because the for-loop in (1) may NOT be terminated prematurely. Think of this :

for(i <- 0 to a.length -1) if (a(i) == x) println(i)  // does this mean println(x) and return from the function ?

what is in the for body is something that is evaluated, why should it trigger a return if you don't specify it ?

[Jason Zaugg]

Methods with explicit 'return' statements must be type annotated. This
is an implementation restriction of the compiler.

But the compiler isn't able to guess that you want to return last
expression for the for. The rules are:

`for (gen1; ...; gen1) expr` evaluates to () (the value of type Unit).
{ expr1; ...; exprN} evaluates to the result of `exprN`, in your case, -1.

How can you know which spots are the 'return's from a method? If you
use IntelliJ, it's pretty easy:

- File, Settings, Editor, Highlight Usages of element at Caret
- click `def` (also works for val, if, case, match, try)
- Voila: http://twicsy.com/i/LEmKj

-jason

[pagoda_5b]

On Wednesday, October 10, 2012 1:36:19 PM UTC+2, Repain Alex wrote:

(3) : You can even put the if in the for-comprehension, ( it translates to a call to 'filter' somewhere in the chain call) :

def ls(x: Int, a: Array[Int]): Int = {
    for (i <- 0 to a.length -1; if a(i) == x) return i
    -1
}

But really, a 'for' is not the way to go here. You don't want a full traversal, so there are methods that handle aborted traversals for you.

Agreed, in a functional programming approach, you avoid looping explicitly and interrupting the loop. You do this with higher-order-functions like map, reduce, fold, exists, find... or using recursion or eventually a while loop.

If you're in for an imperative approach, then you should use return and fulfill the compiler's needs.

By the way, Boris, your function already exists and is called indexOf, I guess you had something different in your mind and made a simple example to 

show?

Bye, Ivano

[Alex Repain]

2012/10/10 Boris Hollas <hol...@informatik.htw-dresden.de>

On 10.10.2012 13:36, Alex Repain wrote:

(1) : The program does what is expected. In Scala the last value
computed is returned by default. The last computed in the function body
of (1) will always be -1.

I see. This is different to ML where an expression such as 1;3 is illegal.

what is at fault is your algorithm design (i.e. don't use a
for-comprehension in the first place).

As I wrote, I want to make the list scanning explicit by using a loop instead of a HOF such as exists. This way, it is easy to see that the running time is in O(n), which is less obvious if I use HOFs.

for(i <- 0 to a.length -1) if (a(i) == x) println(i)  // does this mean
println(x) and return from the function ?

That's a valid point.

Hoever, if for-loops evaluate to (), as Jason wrote, why doesn't give

for(...) i

a type error, since expression i is useless here?

So for-loops (without yield) may only be used for its side-effects?

That's a reasonable question, but scala just doesn't enforce that. It's not always easy to make sure "i" has actually no side-effect. That trivial case where i is an Int is just one easy case. In Scala, "i" can be a call to a parameterless method. Because we want the least surprise principle, it is recommended to put an empty arg list in side-effectul parameterless method, but since scala has no effect system at the moment, "i" might actually be effectful ! Plus, in your for-comprehension, some stuff might be effectful too, although it's definitely not recommended to write Scala this way. This is indeed tricky for programmers coming from a background where side-effects are very important and should be immediately distinguishable.

Aside from that, enforcing warnings or errors for dead code (here, if your for loop was tagged as effectless, it would indeed be useless code) is subject to debate, and not only in Scala I guess.

--
Best regards,
Boris

[sschaef]

I think it is extremely important here to mention that Scala does not have a for-loop! Instead it has a for-comprehension, which is not a loop but a call to a composition of higher order functions - thus, if you wanna use a loop don't use the for-comprehensions, use the while-loop or recursion.

For more explanation of the translation of the for-comprehension is this: http://stackoverflow.com/a/1059501/465304

If one understands what a for-comprehension is there shouldn't be any surprises why it works as it works.

On Wednesday, October 10, 2012 1:36:19 PM UTC+2, Repain Alex wrote:

[Boris Hollas]

On 10.10.2012 18:55, Alex Repain wrote:
> That's a reasonable question, but scala just doesn't enforce that. It's
> not always easy to make sure "i" has actually no side-effect. That
> trivial case where i is an Int is just one easy case. In Scala, "i" can
> be a call to a parameterless method. Because we want the least surprise

It would suffice to check that i has unit type. The compiler should be
able to do that, even if it's not obvious from the syntax. In ML, the
compiler emits a warning:

# for i=1 to 5 do i done;;
Characters 16-17:
for i=1 to 5 do i done;;
^
Warning 10: this expression should have type unit.
- : unit = ()

[Boris Hollas]

On 10.10.2012 21:08, sschaef wrote:
> I think it is extremely important here to mention that Scala does not
> have a for-loop! Instead it has a for-comprehension, which is not a loop
> but a call to a composition of higher order functions - thus, if you
> wanna use a loop don't use the for-comprehensions, use the while-loop or
> recursion.

Thanks for pointing this out. This wasn't at all obvious to me, even
after I read the section on for-expressions in "Programming in Scala" by
Martin Odersky.

I don't think it's a good idea to have an expression that looks like a
for in Java when in fact it isn't. It's a trap to fall in easily. In
contrast, if I use foreach or map, it is obvious that these are HOFs.
For the same reason, I don't like the do-notation in Haskell. It is
functional code disguised as imperative.

[Alex Repain]

2012/10/11 Boris Hollas <hol...@informatik.htw-dresden.de>

It is exactly the intention : providing the commodities of an imperative language but backed up by a functional programming background with solid theoretical grounds (for instance, read about the relation between for-comprehensions and the "monad" mathematical construct). The consequence is that you can use for-comprehension in the same way as for-loops of Java (or for each loops of C++), but not in the same cases, because to make better guarantees about the code, we have to limit some use cases. That's what functional programming is all about : stick to what is provenly safe, whenever you can...

Regarding your proposal to check if "i" has type Unit to determine if the loop is useful or not, it's not enough.Example below :

def i = {println("konnichiwa, sekai !"), true} // i will return a boolean value

for (j <- 1 to 10) {println("" + j + " : "); i} // the block evaluates to Boolean but has side-effects

The compiler COULD forbid the block to return a not-Unit value, but that would mean :

(1). that you can't reuse the method i the way you want. If you know the side-effects of method i, maybe you would like to use it for its side-effects, and not its return value. I'm thinking of unit testing or benchmarks for instance.

(2). that your compiler should probably do the following to stay coherent :

val x = {
  i // warning or error : unused return value of type Boolean
  5
}

Which would only accentuate the effect of (1).

ML has its own philosophy about that but ... I didn't even know that ML had a for-loop ! are you sure it's not syntactic sugar for something else (a fo-comprehension too maybe) ?

Scala has no effect-system at the moment, but there is active research toward finding one that is practicable. It would indeed be of interest to trigger a warning/error if non-effectful code is used as a sole expression and not returned, or better, to silently not include it in the compilation. But Scala has not that ability right now.

[nicola...@gmail.com]

> ML has its own philosophy about that but ... I didn't even know that ML had
> a for-loop ! are you sure it's not syntactic sugar for something else (a
> fo-comprehension too maybe) ?

Ocaml has one. SML does not.

[Boris Hollas]

On 11.10.2012 10:52, Alex Repain wrote:
> The compiler COULD forbid the block to return a not-Unit value, but that
> would mean :
>
> (1). that you can't reuse the method i the way you want. If you know the
> side-effects of method i, maybe you would like to use it for its
> side-effects, and not its return value. I'm thinking of unit testing or
> benchmarks for instance.

you can use
def ignore(x: Any) = ()

> (2). that your compiler should probably do the following to stay coherent :
>
> val x = {
> i // warning or error : unused return value of type Boolean
> 5
> }

yes, I'd like that.

> ML has its own philosophy about that but ... I didn't even know that ML
> had a for-loop ! are you sure it's not syntactic sugar for something
> else (a fo-comprehension too maybe) ?

You don't seem them in ML often. People use List.iter, which has type
('a -> unit) -> 'a list -> unit, or similar functions. Some very rare
cases allow for a more succinct syntax with for. For-loops are
translated into successive bindings of the "loop variable" and can't be
terminated prematurely.

[Daniel Sobral]

Well, please take what I said with a large pinch of salt, but...

Given that for loops and imperative programming are the wrong way of
doing things, why let them have precedence when picking out construct
names?

Now, maybe you don't think they are wrong, but there are people who
do, and, from their viewpoint, this question is valid.

And before you even think of using historical precedence, remember
that LISP is the second oldest high level language in the world,
Fortran is the oldest one, and mainstream meanings for "for" and "do"
are different from what they used.

--
Daniel C. Sobral

I travel to the future all the time.

[Daniel Sobral]

On Thu, Oct 11, 2012 at 4:42 AM, Boris Hollas
<hol...@informatik.htw-dresden.de> wrote:
>
> It would suffice to check that i has unit type. The compiler should be able
> to do that, even if it's not obvious from the syntax. In ML, the compiler
> emits a warning:

You'd be surprised how many side-effecting methods return non-Unit
values. For example:

for (line <- text.lines) sb.append(line) // error,
StringBuilder.append returns StringBuilder
for (word <- line.split("\\s+")) set += word // error if set: mutable.Set

[Alex Repain]

2012/10/11 Daniel Sobral <dcso...@gmail.com>

On Thu, Oct 11, 2012 at 4:42 AM, Boris Hollas
<hol...@informatik.htw-dresden.de> wrote:
>
> It would suffice to check that i has unit type. The compiler should be able
> to do that, even if it's not obvious from the syntax. In ML, the compiler
> emits a warning:

You'd be surprised how many side-effecting methods return non-Unit
values. For example:

for (line <- text.lines) sb.append(line) // error,
StringBuilder.append returns StringBuilder
for (word <- line.split("\\s+")) set += word // error if set: mutable.Set

FYI,  these are due to Scala API providing both mutable and immutable collection types. Because you will want to have the same interface for both, and because immutable collections have to return a new object, you can conclude the only way to provide the same interface with mutable collections is to make them return themselves (the modified collection). This way, both collections can be used seamlessly in affectations and argument-passing.

[pagoda_5b]

On Thursday, October 11, 2012 4:03:42 PM UTC+2, Daniel Sobral wrote:

On Thu, Oct 11, 2012 at 5:04 AM, Boris Hollas
<hol...@informatik.htw-dresden.de> wrote:
>
> I don't think it's a good idea to have an expression that looks like a for
> in Java when in fact it isn't. It's a trap to fall in easily. In contrast,
> if I use foreach or map, it is obvious that these are HOFs. For the same
> reason, I don't like the do-notation in Haskell. It is functional code
> disguised as imperative.

Well, please take what I said with a large pinch of salt, but...

Given that for loops and imperative programming are the wrong way of
doing things, why let them have precedence when picking out construct
names?

My guess is that the answer sounds like: "to ease out the learning path for Java/C* developers"

I would estimate that most Java developers will get on fairly well with for comprehension without noticing the difference until they try something more tricky, at which time they should be ready to learn what's behind the for syntax.

In any case as a java developer you can start using scala's for loops with the return syntax and no issue whatsoever. When you begin your path to functional style then you start questioning the syntax and go a little deeper...

.

--
Daniel C. Sobral

[Daniel Sobral]

for (word <- line.split("\\s+")) set.add(word) // error if set: java.util.Set

That is false, since neither method is present on immutable
collections. But let's get a Java example if you wish:

[Daniel Sobral]

Err, for some weird reason the code was pasted to the beginning, of
the message, not to the place I was editing...

[Alex Repain]

2012/10/11 Daniel Sobral <dcso...@gmail.com>

On Thu, Oct 11, 2012 at 5:04 AM, Boris Hollas
<hol...@informatik.htw-dresden.de> wrote:
> On 10.10.2012 21:08, sschaef wrote:
>>
>> I think it is extremely important here to mention that Scala does not
>> have a for-loop! Instead it has a for-comprehension, which is not a loop
>> but a call to a composition of higher order functions - thus, if you
>> wanna use a loop don't use the for-comprehensions, use the while-loop or
>> recursion.
>
>
> Thanks for pointing this out. This wasn't at all obvious to me, even after I
> read the section on for-expressions in "Programming in Scala" by Martin
> Odersky.
>
> I don't think it's a good idea to have an expression that looks like a for
> in Java when in fact it isn't. It's a trap to fall in easily. In contrast,
> if I use foreach or map, it is obvious that these are HOFs. For the same
> reason, I don't like the do-notation in Haskell. It is functional code
> disguised as imperative.

Well, please take what I said with a large pinch of salt, but...

Given that for loops and imperative programming are the wrong way of
doing things, why let them have precedence when picking out construct
names?

You can even go further : why do imperative language see for-comprehensions as a perversion of their for-loop, when their for-loop is actually a perversion of our for-comprehension ? :). Mathematical truth should prevail.

Alex

PS : what ? chronological order ? Declarative style doesn't have a concept of time, therefore I don't acknowledge it. U g0t 0wn3d, n00b.
 

[Alex Repain]

2012/10/11 Daniel Sobral <dcso...@gmail.com>

You're right, these were not my good examples. But then, how do you explain the choice of returning a modified self, if not for the reasons I mentioned (leaving alone the correspondance in immutable collections, and keeping the part about affectations and argument passing). One ages old example : i++ / ++i . Someone felt the need for this mutation to return itself. Why ?
 

[Daniel Sobral]

Fluent interfaces.

sb.append("x").append("y")

set += 1 += 2

In fact, mutable fluent interfaces are all about returning this on
mutating methods, so that you can chain them.

[Alex Repain]

Okay. Well, that looks pretty familiar to me since it's a big convenience in scala, I never actually used it in an imperative context, so I guess I just assimilated "fluent interfaces" to a facet of functional style. Thanks for the insight
 

[Boris Hollas]

On 11.10.2012 20:30, Daniel Sobral wrote:
> Fluent interfaces.
>
> sb.append("x").append("y")
>
> set += 1 += 2

What is wrong if you write

sb.append("x"); sb.append("y")

set += 1; set += 2

instead? It looks clearer to me.

But I see your point that concatenating unit functions requires to
change their type. The drawback is that the type system becomes less
useful for detecting bugs.
--
Best regards,
Boris

[Alex Repain]

2012/10/12 Boris Hollas <hol...@informatik.htw-dresden.de>

On 11.10.2012 20:30, Daniel Sobral wrote:

Fluent interfaces.

sb.append("x").append("y")

set += 1 += 2

What is wrong if you write

sb.append("x"); sb.append("y")

set += 1; set += 2

instead? It looks clearer to me.

Nothing fundamentally wrong, but if in C++ you had to write 

std::out << "Hello"; std::out << ", "; std::out << "World"; std::out << "!"; 

you'd be wanting the chained syntax, and that would be legitimate...
It's hard to argue that the former is easier to read or write than

std::out << "Hello" << ", " << "World" << "!";

[Naftoli Gugenheim]

On Thu, Oct 11, 2012 at 6:17 AM, Boris Hollas <hol...@informatik.htw-dresden.de> wrote:

(2). that your compiler should probably do the following to stay coherent :

val x = {
   i // warning or error : unused return value of type Boolean
   5
}

yes, I'd like that.

2.10 seems to do that.