* wren ng thornton [2012-01-29 17:30:34-0500]

On 1/29/12 5:48 AM, Roman Cheplyaka wrote:

...

* wren ng thornton [2012-01-28 23:06:08-0500]

...

* Math.Combinatorics.Primes: provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.)

Why not to make it more pure? That is, return a lazy list of Ints (but not a CAF), which user can throw away by the usual GC means?

The functions from the other modules that use primes would have to be put in a Reader monad. That would make it a little bit more awkward to use, but personally I'd prefer that over memory leaks.

I'd also prefer a more pure solution, but I don't think that the Reader monad is the right tool here. I played around with that approach, but it requires extremely invasive changes to client code, obfuscating what should be simple mathematical formulae. And, it's too fragile, exposing the implementation in a way that breaks client code should I change a non-prime-using algorithm to a prime-using one, or vice versa. The fragility could be partially avoided by providing both prime-using and non-prime-using algorithms, but then that forces users to decide which one they want--- and if their only concern is performance, then they'd have to go through the code-breaking refactoring anyways, just to determine which is faster for their application.

Makes sense; but doesn't making the monad abstract and putting all functions in the monad address the fragility issue? -- Roman I. Cheplyaka :: http://ro-che.info/

Hi, On 29.01.2012, at 23:30, wren ng thornton wrote:

On 1/29/12 5:48 AM, Roman Cheplyaka wrote:

...

* wren ng thornton [2012-01-28 23:06:08-0500]

Why not to make it more pure? That is, return a lazy list of Ints (but not a CAF), which user can throw away by the usual GC means?

The functions from the other modules that use primes would have to be put in a Reader monad. That would make it a little bit more awkward to use, but personally I'd prefer that over memory leaks.

I'd also prefer a more pure solution, but I don't think that the Reader monad is the right tool here. I played around with that approach, but it requires extremely invasive changes to client code, obfuscating what should be simple mathematical formulae. And, it's too fragile, exposing the implementation in a way that breaks client code should I change a non-prime-using algorithm to a prime-using one, or vice versa. The fragility could be partially avoided by providing both prime-using and non-prime-using algorithms, but then that forces users to decide which one they want--- and if their only concern is performance, then they'd have to go through the code-breaking refactoring anyways, just to determine which is faster for their application.

One alternative I'm exploring is, rather than (only) making the primes not a CAF, instead make the prime-using functions non-CAFs as well. That is, provide a makePrimeUsingFunctions function which returns a record/tuple of all the functions, sharing a stream of primes. This way, after allocating the functions, they can be used purely just as in the current model; and when the client wants the primes to be GCed, they can drop their references to the allocated functions which use those primes (allocating new functions later, if necessary).

A slight variation on that approach is to use implicit parameters to parameterize your functions by the primes. Something allong the following lines:

{-# LANGUAGE ImplicitParams, Rank2Types #-}

data PrimeTable -- abstract

withPrimes :: ((?primes :: PrimeTable) => a) -> a withPrimes e = e where ?primes = ...

factorial :: (?primes :: PrimeTable) => Integer -> Integer factorial = ...

example = withPrimes $ ... factorial n ….

This has the advantage that the user doesn't have to bring all the elemnts of your tuple/record into scope. And you can have two modules with an almost identical content, one uses the implicit primes argument and the other uses a global CAF for its primes. A user would only have to change his type signatures and strategically add/remove a call to withPrimes when switching. Cheers, Jean