Context reduction stack overflow when passing a function as a formal parameter in the llvm bindings

Question

I am trying to solve a compile time error that is occurring when I use the Haskell llvm bindings.

The code:

-- Line 14 follows
type Acc = Int32 -> Int32 -> IO Int32
type Sig = Int32 -> Ptr Int32 -> Function Acc-> IO Int32

-- [...]

-- Line 31 follows
mSum :: CodeGenModule (Function Sig)
mSum = createNamedFunction ExternalLinkage "sum" $ \l ptr_x fn ->  do
    r <- forLoop (valueOf 0) l (valueOf (0::Int32)) $ \i sum -> do
      xi <- getIndex ptr_x i
      x <- load xi
      call fn sum x
    ret r 

Comentary: mSum is a monadic function which generates a the bite code for an llvm function. The generated function is intended to take three arguments: l: the length of a array of integers; ptr_x a pointer to the array of integers; and fn a Function. (line 32) The generated function will loop through the elements of the array with and accumulator called sum. For each value, x, sum and x will be passed to the function fn. The result of that function will become the value of sum the next time through the loop. The final value of sum will be returned as the value of the generated function.

The Error:

llvm3.hs:32:8:
Context reduction stack overflow; size = 21
Use -fcontext-stack=N to increase stack size to N
  $dFunctionArgs :: FunctionArgs
                      (Function Acc -> b17)
                      (Value (Ptr (Int32 -> Int32 -> IO Int32)) -> b'17)
                      r18
  $dFunctionArgs :: FunctionArgs
                      (Ptr (Int32 -> Int32 -> IO Int32) -> b16)
                      (Value (Function Acc) -> b'16)
                      r17

  -- [ ... ]

  $dFunctionArgs :: FunctionArgs
                      (Ptr (Int32 -> Int32 -> IO Int32) -> b4)
                      (Value (Function Acc) -> b'4)
                      r5
  $dFunctionArgs :: FunctionArgs
                      (Function Acc -> b3)
                      (Value (Ptr (Int32 -> Int32 -> IO Int32)) -> b'3)
                      r4
  $dFunctionArgs :: FunctionArgs
                      (Ptr (Int32 -> Int32 -> IO Int32) -> b2)
                      (Value (Function Acc) -> b'2)
                      r3
  $dFunctionArgs :: FunctionArgs
                      (Function Acc -> IO Int32)
                      (Function (Int32 -> Int32 -> IO Int32)
                       -> CodeGenFunction r Terminate)
                      (CodeGenFunction r0 ())
  $dFunctionArgs :: FunctionArgs
                      (Ptr a0 -> b1) (Value (Ptr Int32) -> b'1) r2
  $dFunctionArgs :: FunctionArgs
                      (Ptr Int32 -> Function Acc -> IO Int32)
                      (Value (Ptr a0)
                       -> Function (Int32 -> a0 -> IO Int32)
                       -> CodeGenFunction r Terminate)
                      (CodeGenFunction r0 ())
  $dFunctionArgs :: FunctionArgs (i0 -> b) (Value Int32 -> b') r1
  $dFunctionArgs :: FunctionArgs
                      Sig
                      (Value i0
                       -> Value (Ptr a0)
                       -> Function f0
                       -> CodeGenFunction r19 Terminate)
                      (CodeGenFunction r0 ())
In the expression: createNamedFunction ExternalLinkage "sum"
In the expression:
    createNamedFunction ExternalLinkage "sum"
  $ \ l ptr_x fn
      -> do { r <- forLoop (valueOf 0) l (valueOf (0 :: Int32))
                 $ \ i sum -> ...;
              ret r }
In an equation for `mSum':
    mSum
      = createNamedFunction ExternalLinkage "sum"
      $ \ l ptr_x fn
          -> do { r <- forLoop (valueOf 0) l (valueOf (0 :: Int32)) $ ...;
                  .... }

Question: There are two possible questions: If I am not passing a function correctly then how to I pass a pointer to a function in LLVM? else what do I need to do to satisfy the type checker?

Aside: I do not understand the working of Haskell well enough to understand why I got this error. I also do not understand the type signature on createNamedFunction:

(IsFunction f, FunctionArgs f g (CodeGenFunction r ()))  
=> Linkage   
-> String    
-> g    -- Function body.
-> CodeGenModule (Function f)  

Answer 1

Oh, good grief.

Yes, you probably have some sort of type error. The library here is using UndecidableInstances to do some fancy type-level logic, where "fancy" means "will cause the type checker to go into an infinite loop if you're unlucky". You can probably guess how lucky you are at the moment. Unfortunately, while the resulting egregious error tells us where the loop is occurring, it's not as informative as one would like about why.

Also, please note that it's entirely reasonable to not understand why you got this error. It's messy and confusing. What follows is some rough explanation and my thoughts on narrowing down the cause:

First of all, the loop is obviously happening while calculating FunctionArgs. Consider the definition of the class:

class FunctionArgs f g r | f -> g r, g r -> f where
    ...

The part after the | are functional dependencies, specifying that certain parameters uniquely determine others. In this case, f and the combination of g and r determine each other, so it's sort of a two-way function that can compute in either direction.

Your function is mSum :: CodeGenModule (Function Sig), unifying with the signature of createNamedFunction gives us Sig as the f parameter, with r and g currently unknown. The type synonym Sig expands to Int32 -> Ptr Int32 -> Function Acc-> IO Int32. Now we can look at the instance list for FunctionArgs and see what this gives us.

Operator precedence gives us the leftmost function arrow as the outermost type constructor for Sig, so we find the matching instance: FunctionArgs b b' r => FunctionArgs (a -> b) (Value a -> b') r. We can substitute in the types, do unification as needed, and repeat:

• FunctionArgs (Ptr Int32 -> Function Acc-> IO Int32) b' r => FunctionArgs (Int32 -> (Ptr Int32 -> Function Acc-> IO Int32)) (Value Int32 -> b') r

• FunctionArgs (Function Acc-> IO Int32) b' r => FunctionArgs (Ptr Int32 -> (Function Acc-> IO Int32)) (Value (Ptr Int32) -> b') r

You should be able to match these steps up with the stack trace in the error you got. One interesting thing is that there are extra steps in the stack trace that I'm not certain of the reason for--something to do with how it fills in the types based on the functional dependencies, I suppose. It looks like it's first selecting the instance based on the (->) type constructor, then filling in the Value a -> b type constructors for the g parameter, then doing the recursive step (in the context) before returning to unify the remaining types.

Now, we know that around this point is when it goes wrong; this can be deduced from the universal principle of stack overflows, which is that the problem is somewhere just before the stack trace starts repeating the same pattern over and over.

For the next reduction, f is instantiated with Function Acc-> IO Int32, while g and r remain undetermined so far (though we know they must be uniquely determined by f). It's also probably a good idea to look at the definition of Function at this point: type Function a = Value (Ptr a)

• FunctionArgs (Value (Ptr Acc) -> IO Int32) g r

Again, we pick the instance with a function arrow: FunctionArgs b b' r => FunctionArgs (a -> b) (Value a -> b') r

...and this is where something fishy happens, because if you compare the stack trace above, it shows (Function (...) -> ...) for the g parameter. That technically matches given the definition of Function above, because we expected Value, which is the outermost constructor of the Function type synonym. Unfortunately, we also have (Function (...) -> ...) for the f parameter, which is inconsistent, because the g parameter should have an additional Value constructor.

After filling in the incorrect structure, it then proceeds to get stuck on the step where it should fill in the remaining type variables; it appears as if the bidirectional functional dependencies cause it to bounce back and forth, repeatedly trying to unify a with Value a. So, with type synonyms expanded, we get this:

• FunctionArgs (Value (Ptr Acc) -> b) (Value (Ptr Acc) -> b') r
• FunctionArgs (Ptr Acc -> b) (Value (Value (Ptr Acc)) -> b') r

...ad infinitum.

At this point I'm really not sure what would have resulted in this conflict. The result I would expect would be a consistent instance choice of FunctionArgs (Value (Ptr Acc) -> b) (Value (Value (Ptr Acc)) -> b') r, and I can't really say why it's getting stuck the way it is.

Edit: Wait, I'm being silly. I misread your code at first--it's pretty clearly getting some part of the incorrect type from the inferred type of the lambda expression, which I thought was more polymorphic than it actually is. In particular, the parameter fn is given as an argument to the function call :: CallArgs f g => Function f -> g, which is what's creating the inconsistent type above. I still don't know why it's going into an infinite loop, but at least that explains the conflict.

On the assumption that the inferred type due to call is correct, the g parameter should have the type Value Int32 -> Value (Ptr Int32) -> Function Acc-> CodeGenFunction Int32 (), which means f should be Int32 -> Ptr Int32 -> Ptr Acc-> IO Int32, as opposed to your type Sig.

Bolstering this is that, if you look at the IsFunction class, which is also applied to f, it expects function arguments to be primitive types like Int32 or Ptrs to primitive types, but not Value, which is what Function expands to.

So after all that, I think your problem is just that your type Sig is slightly wrong.

...welp. Okay then.