I have a set of haskell type signature, similar to below: (for anyone that knows haskell, this is a monomorphised version of .. )

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

And with the implicit parens (Conveniently, this is how my program currently stores the type signatures - as a tree.):

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

I am looking for a programmatic way to convert this style of type signature to a C style type signature with function pointers. So far, all I have been able to find is resources concerning one, maybe two levels of function pointers - Obviously, in this case, I need it to support theoretically infinite levels. Any resources or pointers would be helpful.

Thank you in advance.

EDIT: Encoding the type as a C datastructure would also work.

CodePudding user response：

If @Dmitry's comment accurately reflects what you're trying to do, the Haskell code to perform such a conversion is surprisingly simple:

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

For this example, it produces the type signature:

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

which does, indeed, describe a type compose that's a pointer to a function that accepts a pointer to a function t2 -> t3, returning a pointer to a function that accepts a pointer to a function t1 -> t2 that returns a pointer to a function t1 -> t3.

It's a little hard to see how such a type could be used. I mean, if you want to emit code for a compose function that could actually be assigned to such a pointer, it's tough to do without first-class functions. As a proof of concept, here's a non-reentrant version using global variables that proves that the type "works":

#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'));
}

Alternatively, if you want an "uncurried" version of the type, which in this case would be:

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

(i.e., compose is a pointer to a function that takes a pointer to a function t2 -> t3, a pointer to a function t1 -> t2, and a value of type t1 and then returns a value of type t3), the Haskell code still isn't too bad:

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

The resulting function is much more ergonomic for implementation in 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'));
}