Компиляция оптимизации хвостового вызова во взаимной рекурсии между C и Haskell

Я экспериментирую с интерфейсом сторонних функций в Haskell. Я хотел реализовать простой тест, чтобы увидеть, могу ли я выполнить взаимную рекурсию. Итак, я создал следующий код на Haskell:

module MutualRecursion where
import Data.Int

foreign import ccall countdownC::Int32->IO ()
foreign export ccall countdownHaskell::Int32->IO()

countdownHaskell::Int32->IO()
countdownHaskell n = print n >> if n > 0 then countdownC (pred n) else return ()

Обратите внимание, что рекурсивный случай — это вызов countdownC, поэтому он должен быть рекурсивным.

В моем коде C у меня есть

#include <stdio.h>

#include "MutualRecursionHaskell_stub.h"

void countdownC(int count)
{
    printf("%d\n", count);
    if(count > 0)
        return countdownHaskell(count-1);
}

int main(int argc, char* argv[])
{
    hs_init(&argc, &argv);

    countdownHaskell(10000);

    hs_exit();
    return 0;
}

Что также является хвостовой рекурсией. Итак, я делаю

MutualRecursion: MutualRecursionHaskell_stub
    ghc -O2 -no-hs-main MutualRecursionC.c MutualRecursionHaskell.o -o MutualRecursion
MutualRecursionHaskell_stub:
    ghc -O2 -c MutualRecursionHaskell.hs

и скомпилируйте с помощью make MutualRecursion.

И... при запуске он выдает ошибку после печати 8991. Просто в качестве теста, чтобы убедиться, что сам gcc может обрабатывать tco во взаимной рекурсии, я сделал

void countdownC2(int);

void countdownC(int count)
{
    printf("%d\n", count);
    if(count > 0)
        return countdownC2(count-1);
}

void countdownC2(int count)
{
    printf("%d\n", count);
    if(count > 0)
        return countdownC(count-1);
}

и это работало вполне нормально. Это также работает в случае одиночной рекурсии только в C и только в Haskell.

Итак, мой вопрос: есть ли способ указать GHC, что вызов внешней функции C является хвостовой рекурсией? Я предполагаю, что кадр стека возникает из вызова из Haskell в C, а не наоборот, поскольку код C очень явно является возвратом вызова функции.


c haskell mutual-recursion tail-call-optimization multiple-languages
person Crazycolorz5    schedule 03.11.2015    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Я считаю, что межъязыковые хвостовые вызовы C-Haskell очень и очень трудно реализовать.

Я не знаю точных деталей, но среда выполнения C и среда выполнения Haskell сильно отличаются. Основными факторами этой разницы, насколько я вижу, являются:

  • другая парадигма: чисто функциональная vs императивная
  • сборка мусора против ручного управления памятью
  • ленивая семантика против строгой

Виды оптимизации, которые, вероятно, выживут за пределами языковых границ, учитывая такие различия, близки к нулю. Возможно, теоретически можно было бы изобрести специальную среду выполнения C вместе со средой выполнения Haskell, чтобы сделать некоторые оптимизации возможными, но GHC и GCC не были разработаны таким образом.

Просто чтобы показать пример потенциальных различий, предположим, что у нас есть следующий код Haskell

p :: Int -> Bool
p x = x==42

main = if p 42
       then putStrLn "A"     -- A
       else putStrLn "B"     -- B

Возможная реализация main может быть следующей:

  • поместите адрес A в стек
  • поместите адрес B в стек
  • поместить 42 в стек
  • перейти к p
  • A: напечатать "A", перейти в конец
  • B: напечатать "B", перейти в конец

а p реализовано следующим образом:

  • p: извлечь x из стека
  • вытащить b из стека
  • вытащить a из стека
  • тест x против 42
  • если равно, перейти к a
  • перейти к b

Обратите внимание, как p вызывается с двумя адресами возврата, по одному для каждого возможного результата. Это отличается от C, стандартные реализации которого используют только один адрес возврата. При пересечении границ компилятор должен учитывать эту разницу и компенсировать ее.

Выше я также не учитывал случай, когда аргумент p является переходником, для простоты. Распределитель GHC также может запускать сборку мусора.

Обратите внимание, что приведенная выше вымышленная реализация фактически использовалась в прошлом GHC (так называемая машина STG "push/enter"). Даже если сейчас он больше не используется, машина STG "eval/apply" лишь незначительно ближе к среде выполнения C. Я даже не уверен, что GHC использует обычный стек C: я думаю, что нет, используя свой собственный.

Вы можете проверить вики разработчиков GHC, чтобы увидеть кровавые подробности.

person chi    schedule 03.11.2015
comment
Есть ли способ предотвратить двойное возвращение мест? Например, я написал альтернативную процедуру, используя сопоставление с образцом (вместо 0 в базовом случае), но это не помогло. Как правило, есть ли способ заставить GHC компилироваться таким образом, чтобы обеспечить хвостовую рекурсию через границу? - person Crazycolorz5; 03.11.2015
comment
@Crazycolorz5 Адаптация среды выполнения - очень сложная задача. Кажется, вы считаете, что именно GHC должен адаптировать свою среду выполнения к стандартной C. Чтобы понять, насколько это сложно, подумайте об обратном: изменить GCC таким образом, чтобы разрешить множественные возвраты, сборку мусора и т. д. Это практически невозможно. То, о чем вы спрашиваете, очень, очень маловероятно будет достигнуто с текущим GHC или даже в далеком будущем, насколько я вижу. - person chi; 04.11.2015

arrow_upward
0
arrow_downward

Хотя я не эксперт по взаимодействию Haskel-C, я не думаю, что вызов из C в Haskel может быть прямым вызовом функции - скорее всего, для настройки среды он должен пройти через посредника. В результате ваш вызов haskel фактически будет состоять из вызова этого посредника. Этот вызов, вероятно, был оптимизирован gcc. Но вызов от посредника к фактической процедуре Haskel не обязательно был оптимизирован, поэтому я предполагаю, что это то, с чем вы имеете дело. Вы можете проверить вывод сборки, чтобы убедиться.

person SergeyA    schedule 03.11.2015