The Impossible Function (a C puzzler)

A tutorial for LLVM uses a toy language which has only the datatype "double". The toy language can call C functions which accept doubles and return a double.

I decided to extend the language so that instead of using double, its sole datatype would be a pointer to a function. That function would itself accept pointers to other functions, and return pointers to functions. Instead of passing a value, you would pass a pointer to a function that produces the value. (Although that value in turn is also a function, it can eventually bottom out by returning special addresses; for instance returning the NULL pointer can mean "false".)

Here's the puzzler: Such a function signature is impossible to express it the C (and C++) type system! I encourage readers to try to formulate a typedef for it.

Naively: typedef func_ptr (^func_ptr)(func_ptr);

Edit: Using ^ in place of asterisk to represent pointers because the markdown eats asterisks.

Except that that is invalid code (you can't reuse func_ptr in its own definition). What if you try to declare the function without a typedef? Observe (successive iterations of replacing the word "void^" with a function pointer):

void^ (^the_function) (void^ (^)(void^)); void^ (^)(void^) (^the_function) (void^ (^)(void^) (^)(void^ (^)(void^))); void^ (^)(void^) (^)(void^ (^)(void^)) (^the_function) (void^ (^)(void^) (^)(void^ (^)(void^)) (^)(void^ (^)(void^) (^)(void^ (^)(void^))));

Now, it's certainly possible to think of types that are logically impossible because they are recursive, such as a struct that contains itself as a member. The difference with the Impossible Function is that it isn't a logical contradiction (a function that can accept a pointer to itself or to a function like itself). Furthermore it has a perfectly good representation in machine code; it would just be an indirect call to a function after pushing the its pointer argument on the stack.

It's a hole in the type system.