Self referential type

Question

What type T makes the following code compilable?

T f(){ return &f; }

I'd prefer a C answer, but I marked the question as C and C++ in case there is only an answer using templates.

Answer 1

I hope this isn't cheating (C++ only):

class T {
private:
    T (*_func)();

public:
    T(T (*func)()) : _func(func) {}

    T operator()() {
        return *this;
    }
};

T f() { return &f; }

int main() {
    f()()()()()()()();
}

Answer 2

In C++, easy:

struct my_function {
    my_function& operator()() {
        return *this;
    }
};

In C, you'll have to cast void*s, which will work in any reasonable implementation, but is, I believe, technically undefined.

It would be nice if both languages allowed straightforward recursive types. Alas, they do not.

Answer 3

No type makes that compatible, as you would have an infinite recursion in the typedef.

It is, however, possible to do tricks like DrPizza's to simulate it. However, you could never literally do that.

Supported by the miracle of auto/decltype:

auto f() -> decltype(&f) { return &f; } = a shitload of errors.

Answer 4

The answer to this question is going to cost nothing less than your eternal soul.

Answer 5

Funny, I've been thinking about this exact thing very recently (only I wanted the function to take pointer to itself rather than return it).

For C++, you already have the answer from zildjohn01.

If we stick to Standard C, there's no solution that would compile exactly as written. You can pull it off with an explicit cast - void* won't work, because function-pointer-to-data-pointer conversion is not standard conformant, but you can use any other function pointer type (e.g. void(*)() will do) - the Standard explicitly permits casting from any function pointer type to any other function type and back, and guarantees that you'll get the original value.

Answer 6

As C FAQ Question 1.22 explains, this is impossible in C. Workarounds include wrapping the function pointer in a struct and returning that or returning another (arbitrary) function pointer type, which is possible as casting between function pointer types is guaranteed to be lossless.

Answer 7

Interesting problem, but without acceptable C solution, I guess.

Why this is impossible with C ? (some speculation here)

The type of a function returning T is:

T (*)(void) ;

Which expects T to be defined, of course... But then, as T is the type of the function itself, there is a circular dependency.

For a struct T, we could have had:

struct T ;               /* forward declaration */
typedef T * (*f)(void) ; /* f is a function returning a pointer to T */

Wouldn't the next notation have been handy?

function T ; /* fictional function forward-declaration.
                It won't compile, of course */
T T(void) ;  /* function declaration */

But as there is no way to forward-declare a function, then there is no way use the construct you wrote in your question.

I am no compiler lawyer, but I believe this circular dependency is created only because of typedef notation, not because of C/C++ limitation. After all, function pointers (I'm talking about functions here, not object methods) all have the same size (in the same way struct or class pointers all have the same size).

Studying the C++ solution

As for the C++ solutions, previous answers gave good ones (I'm thinking about zildjohn01's answer, here).

The interesting point is that they are all based upon the fact that structs and classes can be forward declared (and are considered forward-declared in their declaration body) :

#include <iostream>

class MyFunctor
{
   typedef MyFunctor (*myFunctionPointer)() ;
   myFunctionPointer m_f ;
   public :
      MyFunctor(myFunctionPointer p_f) : m_f(p_f) {}
      MyFunctor operator () ()
      {
         m_f() ;
         return *this ;
      }
} ;

MyFunctor foo()      {
   std::cout << "foo() was called !" << std::endl ;
   return &foo ;
}

MyFunctor barbar()   {
   std::cout << "barbar() was called !" << std::endl ;
   return &barbar ;
}

int main(int argc, char* argv[])
{
   foo()() ;
   barbar()()()()() ;
   return 0 ;
}

Which outputs:

foo() was called !
foo() was called !
barbar() was called !
barbar() was called !
barbar() was called !
barbar() was called !
barbar() was called !

Inspiration from the C++ solution to reach a C solution

Couldn't we use a similar way in C to achieve comparable results ?

Somehow, yes, but the results are not as sexy as a C++ solution:

#include <stdio.h>

struct MyFuncWrapper ;

typedef struct MyFuncWrapper (*myFuncPtr) () ;

struct MyFuncWrapper { myFuncPtr f ; } ;

struct MyFuncWrapper foo()
{
   printf("foo() was called!\n") ;

   /* Wrapping the function */
   struct MyFuncWrapper w = { &foo } ; return w ;
}

struct MyFuncWrapper barbar()
{
   printf("barbar() was called!\n") ;

   /* Wrapping the function */
   struct MyFuncWrapper w = { &barbar } ; return w ;
}

int main()
{
   foo().f().f().f().f() ;
   barbar().f().f() ;

   return 0 ;
}

Which outputs:

foo() was called!
foo() was called!
foo() was called!
foo() was called!
foo() was called!
barbar() was called!
barbar() was called!
barbar() was called!

Conclusion

You'll note that the C++ code is very similar semantically to the C code: Each source will use a structure as a container to the pointer of the function, and then, use the pointer contained to call it again if needed. Of course, the C++ solution uses operator () overload, makes symbols privates, and uses a specific constructor as syntactic sugar.

(This is how I found the C solution: Trying to reproduce the C++ solution "by hand")

I don't believe we could better the C solution's syntactic sugar by using macros, so we're stuck to this C solution, which I find far from impressive, but still being interesting for the time it took me to find it.

After all, searching solutions to bizarre problems is a sure way to learn...

:-)

Answer 8

There is no reason that a C compiler back end shouldn't be able to handle that and a lucky front end (aside from the parser and the symbol resolution pass) could as well. But the way C is defined make it imposable to get the data to the later bits of the compiler. OTOH a C compiler that implements typdefs via reference and is non conforming enough to stuff typedefs into the symbol table before it resolves symbols they use would actual swallow it just fine.