• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ]
 
pie sneak
Posts: 4727
Mac VI Editor Ruby
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
reply
    Bookmark Topic Watch Topic
  • New Topic