Why do wet get the "Can't vectorise expression GHC.Prim.Int#" error in DPH programs?

Question

I was trying to implement the nqueens problem using DPH but I ended up with the Can't vectorise GHC.Prim.Int# error. When I googled for the error I found a GHC Bug which talks about vectorizing literals used for pattern matching (http://haskell.1045720.n5.nabble.com/GHC-5702-Can-t-vectorise-pattern-matching-on-numeric-literals-td5076659.html). I am not sure if this is the same bug. My code is as follows,

{-# LANGUAGE ParallelArrays #-}
{-# OPTIONS_GHC -fvectorise #-}
module NQueensP (nqueens_wrapper) 
where

import qualified Prelude
import Data.Array.Parallel
import Data.Array.Parallel.Prelude
import Data.Array.Parallel.Prelude.Int as I
import qualified Data.Array.Parallel.PArray as P


isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1]) 
            where isSafeHelper i []  = True
                  isSafeHelper i (x:xs) = (i I.== Prelude.fst x) && I.abs(i I.-   
                                  (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x)) && 
                                       isSafeHelper i xs

nqueens_wrapper::Int -> PArray (PArray Int)
nqueens_wrapper n = toPArrayP (mapP toPArrayP (nqueens n 0))

nqueens::Int -> Int -> [:[:Int:]:]
nqueens n 1 = [:[:i:] | i <- (enumFromToP 1 n) :]
nqueens n k = [: [:i:] +:+ q | i <- oneton, q <- boards, isSafe i q k:]
           where boards = nqueens n (k I.- 1)
                 oneton = (enumFromToP 1 n) 

Please let me know if I am doing something wrong. I am using GHC 7.4.1.

Thanks in advance.

Answer 1

Yes, this seems to be related to the bug you referred to. The error you get stems from this line:

nqueens n 1 = [:[:i:] | i <- (enumFromToP 1 n) :]

Apparently, you can't use n-patterns with -fvectorise enabled. Let's manually desugar this line to remove the n-pattern:

nqueens n w | w I.== 1 = [:[:i:] | i <- (enumFromToP 1 n) :]

---

We have now dealt with one cryptic error message. This doesn't mean that we're done, because the next error message seems just as cryptic:

*** Vectorisation error ***
    Tycon not vectorised:  []

The problem with isSafe (I think) is that you're using a lot of data types and variables that weren't compiled with -fvectorise. This means you can't just use linked lists (Tycon not vectorised: []), Prelude.fst, Prelude.snd, or Prelude.zip, unless you redefine those structures in your module. (Annoyingly enough, I can't even use (.) without redefining it.)

We will have to rewrite isSafe. Let's look at the first line of it:

isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1]) 

We can't use Prelude.zip, but we could use zipP instead, which means we don't have to convert q anymore. However, our decreasing list should be rewritten using DPH combinators. Stupidly enough, enumFromThenToP doesn't exist, so instead, we'll say mapP (n I.-) (enumFromToP 0 (n I.- 1)) to get the parallel equivalent of [n, n I.- 1..1]. So this line becomes:

isSafe i q n  = isSafeHelper i (zipP q (mapP (n I.-) (enumFromToP 0 (n I.- 1))))

Now for isSafeHelper:

isSafeHelper i [] = True
isSafeHelper i (x:xs)
    = (i I.== Prelude.fst x)
    && I.abs(i I.- (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x))
    && isSafeHelper i xs

Because Prelude.fst and Prelude.snd are unavailable, you can fix this by just extracting these parts of the tuple in the pattern itself:

isSafeHelper i [] = True
isSafeHelper i ((x1,x2):xs)
    = (i I.== x1)
    && I.abs(i I.- x) I./= I.abs(n I.- x2)
    && isSafeHelper i xs

But, of course, it still won't compile: your argument will be a parallel list, not a Prelude-style linked list. To deal with this, we're going to rewrite this in a more functional style, using the function all:

isSafeHelper i xs = all (isSafePredicate i) xs

isSafePredicate i (x1,x2)
    = (i I.== x1)
    && I.abs(i I.- x) I./= I.abs(n I.- x2)

all still works on linked lists, but note that you're not manually deconstructing the list in your own function. Wouldn't it be nice if there were an allP for parallel lists? It would, but there isn't. It's not hard to write it, though:

allP :: (a -> Bool) -> [: a :] -> Bool
allP p arr = andP (mapP p arr)

Putting it all together, you can write isSafe as follows:

isSafe i q n = allP (isSafePredicate i n) (zipP q ntoone) 
  where
    isSafePredicate i n (x1, x2)
        = (i I.== x1)
        && I.abs(i I.- x1) I./= I.abs(n I.- x2)
    ntoone = mapP (n I.-) (enumFromToP 0 (n I.- 1))

---

nqueens_wrapper seems fine as it is. Your code should now compile.

A few notes:

• I don't know whether it works (I get *** Exception: crossMapP: not implemented, and don't know how to fix it), but it looks like it should.
• Rewriting isSafe the other way around won't work. If you try to work with Prelude numbers in Prelude lists, you'll end up with the complaint about Int# again. I think this is because isSafe is used by at least one vectorised function nqueens.

• Don't include Data.Array.Parallel.Prelude. The module description says so:

  This module should not be explicitly imported in user code anymore. User code should only import Parallel and, until the vectoriser supports type classes, the type-specific modules.

• Don't go crazy with local definitions. isSafeHelper is missing its n argument in your version.