The Impossible Function (a C puzzler)

[phaedrus]

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.

[joeld42]

The problem in your thinking is that you say "it can eventually bottom out by returning NULL". But you don't tell the compiler that.

You have to end the recursion somewhere. Fortunately, you can just use an equivalent type.

typedef void^(^func_ptr0)( void^ ); typedef func_ptr0 (^func_ptr)( funcptr0 );

func_ptr foo( func_ptr a ) { return a; }

void main() { func_ptr ^p = foo; }

There's really no reason to keep expanding it. If you're suggesting that using a void^ is not allowed, then that's like suggesting that you can't return NULL.

[mfukar]

This is a common occurrence:

http://c-faq.com/decl/recurfuncp.html

Enjoy.

[sajid]

You may be able to do it like this:

    typedef int *func_ptr;

Declare a function:

    func_ptr some_func(func_ptr);

Call a function (recursive example):

    some_func((func_ptr) &some_func);

[mfukar]

Could you indent the function definition (without the typedef), please? It is near impossible to read.

[phaedrus → mfukar]

I tried to, but the markdown ate my formatting & I don't know the escape code.