aspose file tools*
The moose likes Scala and the fly likes Can't figure out what's wrong with this method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Languages » Scala
Bookmark "Can Watch "Can New topic
Author

Can't figure out what's wrong with this method

Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
I've been playing around a bit at night using Scala to solve some problems at Project Euler. Many PE problems have to do with prime numbers so I needed to come up with a reusable sieve of eratosthenes to generate the primes. I started out using a fully functional sieve with no mutable state that produced an *infinite* lazy stream of prime numbers. It turned out to be slow and exhausted the heap for large primes. So I scrapped that and went with a more classic version using mutable arrays.

Here was my first attempt


And my code to test the method (using the specs testing framework):


And unexpectedly (to me at least) the test fails:


But when I replace arr.indices with a range object (0 until limit), it works as expected


To my eyes the code is equivalent, but obviously I'm missing something. What is it?
[ September 04, 2008: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Marc Peabody
pie sneak
Sheriff

Joined: Feb 05, 2003
Posts: 4727

Bizzare. I can't explain the behavior but I was able to isolate the problem.

When using arr.indices, the bottom for loop evaluates all of the pattern guards first and then the for loop executes every iteration as if the guards all returned true.

However, when using the range, the pattern evaluations simply happen at the beginning of each iteration, as one would expect.

Below is my nasty tweak to prove it:

[ September 06, 2008: Message edited by: Marc Peabody ]

A good workman is known by his tools.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
Thanks for looking at it Marc. I'll distill it down to the essence of the problem and post it to the Scala mailing list and see if it is a bug or if there is just something I'm not understanding.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
As I think a little more, I don't think its a bug, just a feature I didn't understand .

0 until limit

returns a Range object which is a subtype of Projection. The primary feature of Projections is that they are lazy and all the operations on them, including Projection.filter which the guard is compiled to, are also lazy.

Array.filter on the other hand is strict, hence the difference in behavior.
T. Morris
Greenhorn

Joined: Sep 09, 2008
Posts: 3
You are mixing lazy evaluation with side-effects, which is a big no-no. As you have observed, reasoning about the correctness of your program becomes difficult.
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
T. Morris: You are mixing lazy evaluation with side-effects, which is a big no-no.

In this case the side-effects are strictly local. That is, no global state is affected by utilizing a mutable array *under the hood* to implement the algorithm. As I stated before, I was using a functional algorithm free of side-effects initially, but it was not suitable for my purposes.

As to mixing laziness and side effects, I suppose you're right. Initially, it didn't even occur to me (I'm a little slow) that the algorithm I was using depended on the laziness of the filter method, that's why I was surprised at the results. With side effects and without laziness then:



T. Morris: As you have observed, reasoning about the correctness of your program becomes difficult.

Isn't that what the tests are for?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Can't figure out what's wrong with this method