We'll start with ye'olde primes program straight from the nofib benchmark suite. This is the exact code, except that for the sake of example I've hard wired it to show the 1500th prime instead of taking a command line argument.
suCC :: Int -> Int
suCC x = x + 1
isdivs :: Int -> Int -> Bool
isdivs n x = mod x n /= 0
the_filter :: [Int] -> [Int]
the_filter (n:ns) = filter (isdivs n) ns
primes :: [Int]
primes = map head (iterate the_filter (iterate suCC 2))
main = print $ primes !! 1500
This program builds an infinite list of primes, and then uses list indexing to take the 1500'th one. A couple of nice functional programming paradigms are used, namely higher order functions and laziness. Disciple is a default-strict dialect of Haskell, so we can use almost the same code, except we have to be explicit when we want laziness:
suCC :: Int -> Int
suCC x = x + 1
isdivs :: Int -> Int -> Bool
isdivs n x = mod x n /= 0
the_filter :: [Int] -> [Int]
the_filter (n:ns) = filterL (isdivs n) ns
primes :: [Int]
primes = mapL head (iterateL the_filter (iterateL suCC 2))
main () = println $ show $ primes !! 1500
That's it. I've changed map, filter and iterate to mapL, filterL and iterateL, and wibbled the main function slightly, but it's otherwise the same code. The difference between something like map and mapL is like the difference between foldl and foldl' in Haskell, they're implemented almost the same way, but have slightly different behaviours. Check the base libs for details.
Ok, so Disciple can express the dominant paradigms of Haskell, now it's time to subvert them. In the "Beyond Haskell" session at HIW 2010 we talked about how sometimes when optimising a program in a high level language, you reach a point where you just have to drop down to a "lower level" language for performance reasons. This is like when you're writing a Ruby program and it's running so slow there's simply nothing else to do than to "shell out" to a C routine. This also happens in Haskell, but perhaps not as much.
Anyway, one of the goals of Disciple is to avoid this problem if at all possible. If the lazy, purely functional version of primes just isn't fast enough for you, then let's write the same program using destructive update of a mutable array:
-- | Check if an int is a multiple of any in a given array.
checkPrime :: Array Int -> Int -> Int -> Int -> Bool
checkPrime array high x n
| n >= high = True
| mod x array.(n) == 0 = False
| otherwise = checkPrime array high x (n + 1)
-- | Fill an array with primes.
fillPrimes :: Array Int -> Int -> Int -> Int -> ()
fillPrimes primes max high i
| high > max = ()
| checkPrime primes high i 0
= do primes.(high) := i
fillPrimes primes max (high + 1) (i + 1)
| otherwise
= fillPrimes primes max high (i + 1)
main ()
= do -- We want the 1500'th prime.
max = 1500
-- Start with an array containing the first prime as its first element.
primes = generate&{Array Int} (max + 1) (\_ -> 0)
primes.(0) := 2
-- Fill the array with more primes.
fillPrimes primes max 1 2
-- Take the last prime found as the answer.
println $ show primes.(max)
The syntax primes.(max) means "return the max'th element of the primes array". The syntax primes.(high) := i means "destructively update the high'th element of the primes array to the value i". Updating an array requires the array to be mutable. It's possible to express this mutability constraint in the type signature, but it's not required, so I usually just leave it to the inferencer. The compiler knows that you're using side effects, and will optimise around them, but you usually don't have to say anything about it in source level type sigs. I'll talk about the cases when you do in another post. Note that we don't have to pollute the type sigs with the IO constructor just to use destructive update. After all, checkPrime and fillPrimes aren't doing any IO...
The above code is good, but it still feels like a Haskell program. I'm particularly looking at the tail calls to checkPrime and fillPrimes. This is how you express primitive looping in many functional languages, but it can become tedious when there are lots of state variables to pass back to each iteration. Here is another version of primes written in a more imperative style.
-- | Check if an int is a multiple of any in a given array.
checkPrime :: Array Int -> Int -> Int -> Bool
checkPrime array high x
= do n = 0
isPrime = 1
while (n < high)
do when (mod x array.(n) == 0)
do isPrime := 0
break
n := n + 1
isPrime /= 0
main ()
= do -- We want the 1500'th prime.
max = 1500
-- Start with an array containing the first prime as its first element.
primes = generate&{Array Int} (max + 1) (\_ -> 0)
primes.(0) := 2
-- Fill the array with primes.
high = 1
i = 2
while (high <= max)
do when (checkPrime primes high i)
do primes.(high) := i
high := high + 1
i := i + 1
-- Take the last prime found as the answer.
println $ show primes.(max)
Now we've got while loops, and break, even. Of course, the while syntax desugars to a simple higher order function that takes the loop body, and break just throws an exception to end the iteration. Such syntax should help the Python programmers feel at home, but Disciple is still lambdas all the way down.
Finally, note that we started with a lazy, purely functional program but arrived at an unapologetically imperative program all in the same language. In my dreams people talk about "functional vs imperative" programs instead of "functional vs imperative" languages.
Write the lazy functional program because it's shorter, cleaner, and easier to understand.. but when the clock is tickin' and the space is leakin' then wouldn't it be nicer "shell out" to the same language?
PS: Code examples are part of the DDC test suite here
PPS: Of couse the absolute performance of these programs compiled with DDC today is atrocious. This is a development blog after all, and we're still developing. They do work though. See the wiki to find out how you can help.
No comments:
Post a Comment