c++ recursive function type

Question

Rob Pike made a talk in 2011 (link) about lexers in go, where he defined a type like this:

// stateFn represents the state of the scanner
// as a function that returns the next state.
type stateFn func() stateFn

I want to achieve the same in C++, but can't figure out how:

// 01: error C3861: 'statefn_t': identifier not found
typedef std::function<statefn_t()> statefn_t;

// 02: error C2371: 'statefn_t': redefinition; different basic types
typedef std::function<class statefn_t()> statefn_t;

// 03: error C2371: 'statefn_t': redefinition; different basic types
typedef std::function<struct statefn_t()> statefn_t;

// 04: error C2065: 'statefn_t': undeclared identifier
typedef std::function<statefn_t*()> statefn_t;

// 05: error C2371: 'statefn_t': redefinition; different basic types
typedef std::function<class statefn_t*()> statefn_t;

// 06: error C2371: 'statefn_t': redefinition; different basic types
typedef std::function<struct statefn_t*()> statefn_t;

Note: this question might be connected (it's the same in Rust)

Edit:

Here is what i am trying to achieve:

// statefn_t definition goes here ...

statefn_t* func1()
{
    return &func2;
}

statefn_t* func2()
{
    return &func1;
}

Answer 1

If you want the recursion to be resolved at runtime, while keeping it as similar as possible to your original code, you may use boost::any or C++17 std::any, something like:

std::any end(){ std::cout << "end\n"; return {}; }
std::any state(){ std::cout << "some state\n"; return &end; }
std::any begin(){ std::cout << "begin\n"; return &state; }

void advance( std::any& state )
    { state = std::any_cast<std::any(*)()>(state)(); }

int main()
{
    for( auto state = begin(); state.has_value(); advance( state ) );
}

---

If the recursion has to be resolved at compile time, you may exploit auto type deduction:

auto end(){ std::cout << "end\n"; }
auto state(){ std::cout << "some state\n"; return &end; }
auto begin(){ std::cout << "begin\n"; return &state; }

int main()
{
    begin()()();
}

of course, this won't work within loops, you need some kind of compile time iteration scheme in order for this to be useful ...

Answer 2

Type aliases cannot be recursive.

To achieve a state machine such as the one used in the go lecture, you will need to define a custom type:

class state
{
public:
    using fn = std::function<state()>;
    state() {}
    state(fn f) : f(f){}
    operator bool() { return (bool)f; }
    operator fn () { return f; }

private:
    fn f;
};

Usage:

state::fn stateEnd()
{
    std::cout << "end\n";
    return {};
}
state::fn stateTransit()
{
    std::cout << "transit\n";
    return stateEnd;
}

state::fn stateStart()
{
    std::cout << "start\n";
    return stateTransit;
}


int main() {
    state::fn s = stateStart;
    while(s = s());
}

---

Alternative form:

class state
{
public:
    state() {}
    template<class T>
    state(T&& t) : f(std::forward<T>(t)){}
    operator bool() { return (bool)f; }
    state operator()() { return f(); }

private:
    std::function<state()> f;
};

Usage:

state stateEnd()
{
    std::cout << "end\n";
    return {};
}
state stateTransit()
{
    std::cout << "transit\n";
    return stateEnd;
}

state stateStart()
{
    std::cout << "start\n";
    return stateTransit;
}


int main() {
    state s {stateStart};
    while(s = s());
}

Answer 3

It's not a natural way to do things in C++.

In C++ it's more like obfuscation, which is reflected in the difficulty of finding good self-describing names for the state advancing functions that also are states:

struct Context {};

class State
{
    using F = auto( Context const& ) -> State;
    F* next_state_;

public:
    auto is_finished() const -> bool { return next_state_ == nullptr; }

    auto operator()( Context const& ctx ) const
        -> State
    { return next_state_( ctx ); }

    State( F* f ): next_state_{ f } {}
    inline State();
};

auto intermediate( Context const& ) { return State{ nullptr }; }
auto start( Context const& ) { return State{ intermediate }; }

State::State(): next_state_{ start } {}

#include <iostream>
using namespace std;
auto main() -> int
{
    State       state;
    Context     ctx;

    cout << boolalpha;
    for( ;; )
    {
        cout << state.is_finished() << endl;
        if( state.is_finished() ) { break; }
        state = state( ctx );
    }
}

Answer 4

As Clearer commented, here is an example of a C++ type stateFn that behaves like a function and recursively returns an instance of the same type.

struct stateFn
{
    stateFn& operator() ();
}