将 haskell 样式类型签名转换为 C

Question

我有一组 haskell 类型签名，类似于下面：（对于任何了解 haskell 的人来说，这是 的单态版本..）

(t2 -> t3) -> (t1 -> t2) ->  t1 -> t3

并使用隐式括号（方便地，这就是我的程序当前存储类型签名的方式 - 作为树。）：

(t2 -> t3) -> ((t1 -> t2) -> (t1 -> t3))

我正在寻找一种编程方法来将这种风格的类型签名转换为带有函数指针的 C 风格类型签名。到目前为止，我所能找到的只是有关一层（也许是两层）函数指针的资源 - 显然，在这种情况下，我需要它支持理论上无限的层。任何资源或指示都会有帮助。

先感谢您。

编辑：将类型编码为 C 数据结构也可以。

Answer 1

如果 @Dmitry 的评论准确地反映了您想要做的事情，那么执行此类转换的 Haskell 代码出奇地简单：

data HType = (:->) HType HType | H String
  deriving (Show)
infixr 0 :->

ctype :: String -> HType -> String
ctype x (a :-> b) = ctype ("(*" ++ x ++ ")(" ++ ctype "" a ++ ")") b
ctype "" (H a) = a
ctype x  (H a) = a ++ " " ++ x

main = do
  let t = (H "t2" :-> H "t3") :-> (H "t1" :-> H "t2") :-> H "t1" :-> H "t3"
  putStrLn $ ctype "compose" t

对于此示例，它生成类型签名：

t3 (*(*(*compose)(t3 (*)(t2)))(t2 (*)(t1)))(t1)

实际上，它描述了一种类型，compose该类型是指向函数的指针t2 -> t3，该函数接受指向函数的指针，返回指向函数的指针，该函数接受指向函数的指针t1 -> t2，该函数返回指向函数的指针t1 -> t3。

很难看出如何使用这种类型。我的意思是，如果您想为实际上可以分配给此类指针的组合函数发出代码，那么如果没有一等函数，就很难做到。作为概念证明，这是一个使用全局变量的不可重入版本，证明该类型“有效”：

#include <stdio.h>

/* some concrete types to use */
typedef char t1;
typedef int t2;
typedef char* t3;

/* compose :: (t2 -> t3) -> ((t1 -> t2) -> (t1 -> t3)) */
typedef t3 (*(*(*compose)(t3 (*)(t2)))(t2 (*)(t1)))(t1);

/* code defining a `do_compose` function pointer of C type `compose` */

t3 (*f1)(t2);
t2 (*f2)(t1);

t3 compose2(t1 x)
{
        return (*f1)((*f2)(x));
}

t3 (*compose1(t2 (*g)(t1)))(t1)
{
        f2 = g;
        return compose2;
}

t3 (*(*compose0(t3 (*f)(t2)))(t2 (*)(t1)))(t1)
{
        f1 = f;
        return compose1;
}

compose do_compose = compose0;

/*
 * a test case for `do_compose`
 */

/* ord :: t1 -> t2 */
int ord(char c)
{
        return (int)c;
}

/* print :: t2 -> t3 */
char* print(int i)
{
        static char buffer[256];
        sprintf(buffer, "%d", i);
        return buffer;
}

int main()
{
        puts(do_compose(print)(ord)('A'));
}

或者，如果您想要该类型的“非柯里化”版本，在本例中为：

t3 (*compose)(t3 (*)(t2), t2 (*)(t1), t1)

（即，compose是一个指向函数的指针，它接受一个指向函数的指针t2 -> t3、一个指向函数的指针t1 -> t2和一个 type 的值t1，然后返回一个 type 的值t3），Haskell 代码仍然还不错：

ctype' :: String -> HType -> String
ctype' "" (H a) = a
ctype' x (H a) = a ++ " " ++ x
ctype' x funcall = go [] funcall
  where go args (a :-> b) = go (ctype "" a : args) b
        go args b = ctype ("(*" ++ x ++ ")(" ++ intercalate ", " (reverse args) ++ ")") b

生成的函数对于用 C 语言实现来说更加符合人体工程学：

/* compose :: (t2 -> t3) -> ((t1 -> t2) -> (t1 -> t3)), uncurried version */
typedef t3 (*compose)(t3 (*)(t2), t2 (*)(t1), t1);

t3 compose0(t3 (*f)(t2), t2 (*g)(t1), t1 x)
{
        return (*f)((*g)(x));
}

compose do_compose = compose0;

...

int main()
{
        puts(do_compose(print, ord, 'A'));
}