Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Marc Peabody
pie sneak
Sheriff
Posts: 4727
Mac Ruby VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic