Переполнение стека сокращения контекста при передаче функции в качестве формального параметра в привязках llvm

Question

Я пытаюсь устранить ошибку времени компиляции, возникающую при использовании привязок Haskell llvm.

Код :

-- 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 - это монадическая функция, которая генерирует код прикуса для функции llvm. Сгенерированная функция должна принимать три аргумента: l: длина массива целых чисел; ptr_x указатель на массив целых чисел; и fn Функция. (строка 32) Сгенерированная функция будет циклически проходить через элементы массива и аккумулятора с именем sum. Для каждого значения x, sum и x будут переданы в функцию fn. Результатом этой функции станет значение sum в следующий раз в цикле. Окончательное значение суммы будет возвращено как значение сгенерированной функции.

Ошибка :

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)) $ ...;
                  .... }

Вопрос : Есть два возможных вопроса: если я неправильно передаю функцию, как передать указатель на функцию в LLVM? еще, что мне нужно сделать, чтобы удовлетворить проверку типа?

В сторону : Я недостаточно хорошо понимаю работу Haskell, чтобы понять, почему я получил эту ошибку. Я тоже не понимаю тип подписи на createNamedFunction:

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

Answer 1

О, хорошее горе .

Да, возможно, у вас ошибка типа. Библиотека здесь использует UndecidableInstances для выполнения какой-то причудливой логики на уровне типов, где «причудливое» означает «заставит средство проверки типов войти в бесконечный цикл, если вам не повезло». Вы можете догадаться, насколько вам повезло в данный момент. К сожалению, хотя результирующая вопиющая ошибка сообщает нам , где происходит цикл, он не настолько информативен, как хотелось бы о , почему .

Также обратите внимание, что совершенно разумно не понимать, почему вы получили эту ошибку. Это грязно и запутанно. Далее следует грубое объяснение и мои мысли о сужении причины:

Прежде всего, цикл явно происходит при вычислении FunctionArgs. Рассмотрим определение класса:

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

Часть после | - это функциональных зависимостей , указывающих, что одни параметры однозначно определяют другие. В этом случае f и комбинация g и r определяют друг друга, так что это своего рода двусторонняя функция, которая может вычислять в любом направлении.

Ваша функция mSum :: CodeGenModule (Function Sig), объединение с сигнатурой createNamedFunction дает нам Sig в качестве параметра f, с r и g в настоящее время неизвестными. Синоним типа Sig расширяется до Int32 -> Ptr Int32 -> Function Acc-> IO Int32. Теперь мы можем взглянуть на список экземпляров для FunctionArgs и посмотреть, что это нам дает.

Приоритет оператора дает нам крайнюю левую стрелку функции как конструктор внешнего типа для Sig, поэтому мы находим соответствующий экземпляр: FunctionArgs b b' r => FunctionArgs (a -> b) (Value a -> b') r. Мы можем подставить типы, при необходимости выполнить объединение и повторить:

• 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

Вы должны быть в состоянии сопоставить эти шаги с трассировкой стека в полученной ошибке. Одна интересная вещь заключается в том, что в трассировке стека есть дополнительные шаги, причина которых я не знаю - как-то связано с тем, как они заполняют типы на основе функциональных зависимостей, я полагаю. Похоже, что сначала он выбирает экземпляр на основе конструктора типа (->), затем заполняет конструкторы типа Value a -> b для параметра g, затем выполняет рекурсивный шаг (в контексте) перед возвратом, чтобы объединить остальные типы .

Теперь мы знаем, что в этот момент происходит что-то неправильное; это может быть выведено из универсального принципа переполнения стека, который заключается в том, что проблема где-то перед тем, как трассировка стека начинает повторять один и тот же шаблон снова и снова.

Для следующего сокращения, f создается с Function Acc-> IO Int32, в то время как g и r пока остаются неопределенными (хотя мы знаем, что они должны быть однозначно определены f). Также, вероятно, будет хорошей идеей взглянуть на определение Function на этом этапе: type Function a = Value (Ptr a)

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

Опять мы выбираем экземпляр со стрелкой функции: FunctionArgs b b' r => FunctionArgs (a -> b) (Value a -> b') r

... и здесь происходит что-то подозрительное, потому что, если сравнить приведенную выше трассировку стека, для параметра g будет показано (Function (...) -> ...). Это технически соответствует приведенному выше определению Function, потому что мы ожидали Value, который является самым внешним конструктором синонима типа Function. К сожалению, у нас также есть (Function (...) -> ...) для параметра f, что является непоследовательным, поскольку параметр g должен иметь дополнительный конструктор Value.

После заполнения неправильной структуры, он переходит к застреванию на шаге, где он должен заполнить оставшиеся переменные типа; похоже, что двунаправленные функциональные зависимости заставляют его подпрыгивать назад и вперед, неоднократно пытаясь объединить a с Value a. Итак, с расширением синонимов типа мы получаем:

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

... до бесконечности.

На данный момент я действительно не уверен, что привело бы к этому конфликту.Я ожидаю, что результатом будет последовательный выбор экземпляра FunctionArgs (Value (Ptr Acc) -> b) (Value (Value (Ptr Acc)) -> b') r, и я не могу точно сказать, почему он застрял таким, какой он есть.

Редактировать : Подождите, я 'Я глупый.Сначала я неправильно прочитал ваш код - он довольно явно получает некоторую часть неправильного типа из выведенного типа лямбда-выражения, которое, на мой взгляд, было более полиморфным, чем на самом деле.В частности, параметр fn задается в качестве аргумента функции call :: CallArgs f g => Function f -> g, которая создает описанный выше несовместимый тип.Я до сих пор не знаю, почему он входит в бесконечный цикл, но, по крайней мере, это объясняет конфликт.

При условии, что предполагаемый тип из-за call является правильным, параметр g должен иметьтип Value Int32 -> Value (Ptr Int32) -> Function Acc-> CodeGenFunction Int32 (), что означает f, должно быть Int32 -> Ptr Int32 -> Ptr Acc-> IO Int32, в отличие от вашего типа Sig.

. Это то, что, если вы посмотрите на класс IsFunction, который такжеПрименительно к f он ожидает, что аргументы функции будут примитивными типами, такими как Int32 или Ptr s, к примитивным типам, но не Value, то есть то, к чему Function расширяется.

Так что послевсе это, я думаю, что ваша проблема только в том, что ваш тип Sig немного неправильный.

... привет.Хорошо, тогда.