HiveBrain v1.2.0
Get Started
← Back to all entries
debugcppMinor

Fixed point combinator in C++1x

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
fixedcombinatorpoint

Problem

This has been tested and compiled under Visual Studio 2010. Are there any serious problems with this implementation?

PS. This implementation is fully lambda expression based. If I can make fixpoint::fix a real member function it will be simpler than this.

//As decltype(variable)::member_name is invalid currently, 
//the following template is a workaround.
//Usage: t2t::t::member_name
template
struct t2t
{
    typedef T t;
};

template
struct fixpoint
{
    typedef std::function func_t;
    typedef std::function tfunc_t;
    typedef std::function yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template
        loopfunc_t(const L &l):func(l){}
        typedef V Parameter_t;
    private:
        std::function func;
    };
    static yfunc_t fix;
};
template
typename fixpoint::yfunc_t fixpoint::fix = 
[](fixpoint::tfunc_t f) -> fixpoint::func_t {
    fixpoint::loopfunc_t l = [f](fixpoint::loopfunc_t x) ->
        fixpoint::func_t{
            //f cannot be captured since it is not a local variable
            //of this scope. We need a new reference to it.
            auto &ff = f;
            //We need struct t2t because template parameter
            //V is not accessable in this level.
            return [ff, x](t2t::t::Parameter_t v){
                return ff(x(x))(v); 
            };
        }; 
        return l(l);
    };

int _tmain(int argc, _TCHAR* argv[])
{
    int v = 0;
    std::function fac = 
    fixpoint::fix([](std::function f)
        -> std::function{
        return [f](int i) -> int{
            if(i==0) return 1;
            else return i * f(i-1);
        };
    });

    int i = fac(10);
    std::cout << i; //3628800
    return 0;
}

Solution

I hav tried the same thing in G++ (version 4.5 from Ubuntu 11.04 original), and the result is quite impressing me. We now do have a lot more features to generise the solution.

-
we can now support any number of parameters without modifying the code.

-
the t2t class is no longer needed as G++ lambda supports accessing all identifiers in scope, including global things.

I also tried write a free template function to access the internal function. And the result looks good. I just wanted to say: it is elegant!

#include 
#include 

template
struct fixpoint
{
    typedef std::function func_t;
    typedef std::function tfunc_t;
    typedef std::function yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template
        loopfunc_t(const L &l):func(l){}
        loopfunc_t(){}
    private:
        std::function func;
    };
    static func_t Fix(tfunc_t f){
        return [](loopfunc_t x){ return x(x); }
        ([f](loopfunc_t x){ return [f, x](V... v){ return f(x(x))(v...); }; });
    }
};
template
struct getfixpoint
{
    typedef typename getfixpoint::fp fp;
};
template
struct getfixpoint (T::*)(std::function)>
{
    typedef fixpoint fp;
};
template
struct getfixpoint (T::*)(std::function)const>
{
    typedef fixpoint fp;
};
template
struct getfixpoint (*)(std::function)>
{
    typedef fixpoint fp;
};

template
auto getFix(T f) -> typename getfixpoint::fp::func_t {
    return getfixpoint::fp::Fix(f);
};

int main(int argc, char* argv[])
{
    auto fac = getFix([](std::function f) -> std::function{
        return [f](int n)->int { if(n==0) return 1; else return n * f(n-1); };
    });
    std::cout<<fac(10)<<std::endl; //3628800
    return 0;
}

Code Snippets

#include <iostream>
#include <functional>

template<typename R, typename... V>
struct fixpoint
{
    typedef std::function<R (V...)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        loopfunc_t(){}
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static func_t Fix(tfunc_t f){
        return [](loopfunc_t x){ return x(x); }
        ([f](loopfunc_t x){ return [f, x](V... v){ return f(x(x))(v...); }; });
    }
};
template<typename T>
struct getfixpoint
{
    typedef typename getfixpoint<decltype(&T::operator())>::fp fp;
};
template<typename R, typename T, typename... V>
struct getfixpoint<std::function<R (V...)> (T::*)(std::function<R (V...)>)>
{
    typedef fixpoint<R, V...> fp;
};
template<typename R, typename T, typename... V>
struct getfixpoint<std::function<R (V...)> (T::*)(std::function<R (V...)>)const>
{
    typedef fixpoint<R, V...> fp;
};
template<typename R, typename... V>
struct getfixpoint<std::function<R (V...)> (*)(std::function<R (V...)>)>
{
    typedef fixpoint<R, V...> fp;
};

template<typename T>
auto getFix(T f) -> typename getfixpoint<T>::fp::func_t {
    return getfixpoint<T>::fp::Fix(f);
};

int main(int argc, char* argv[])
{
    auto fac = getFix([](std::function<int (int)> f) -> std::function<int (int)>{
        return [f](int n)->int { if(n==0) return 1; else return n * f(n-1); };
    });
    std::cout<<fac(10)<<std::endl; //3628800
    return 0;
}

Context

StackExchange Code Review Q#3111, answer score: 3

Revisions (0)

No revisions yet.