Y-combinator in D?

I'm trying to learn the Y-combinator better (I sort of understand it in Scheme) and implement it in D 2.0, and I'm failing pretty miserably:

auto fact = delegate(uint delegate(uint) 开发者_StackOverflow中文版recurse)
{
    return delegate(uint n)
    {
        return n > 1 ? n * recurse(n - 1) : 1;
    };
};

fact(fact)(5);

This doesn't work, for the obvious reason that I can't pass fact to fact (what would its type be?). And besides, I still need fact's name to pass to itself, so it wouldn't work anyway, right?

But... how do I go about implementing the Y-combinator in D?

See an extensive explanation here.

It's a know limitation of D (and C/C++) that functions that deal with typed self references are impossible (last time I checked) to declare.

I find this ironic because it amounts to a limitation of syntax (the length of the function prototype is infinite) or naming convention (the same problem but with name mangling) rather than anything semantic or architectural.

I do not know D, but with most languages you will get problems with type of the function when you try to implement non-recursion (there is no Y-Combinator in your code yet). The usual way around is can be achieved by separating the types into several part and this way getting the recursion into the type.

Some example from other languages:

• In C one usually writes a struct that contains the function pointer. This struct then can be used as an argument.

• In OCaml one would add a variant type that wraps the function type. Again this allows for seperating the types so type recursion is possible.

If you want some example from other languages have a look at this page.

My generic Y combinator in D:

import std.stdio, std.algorithm, std.range;
auto Y(R,T...)(R delegate(T) delegate (R delegate(T)) f){
    struct F{R delegate(F,T) f;};
    return (R delegate(T)delegate(F) a){return a(F((F b,T i){return f(a(b))(i);}));
    }((F b){return (T n){return b.f(b,n);};});
}
void main(){
    auto factorial=Y((long delegate(long) self){return (long i){return i?self(i-1)*i:1;};});
    auto fibonacci=Y((int delegate(int) self){return (int i){return i<2?i:self(i-1)+self(i-2);};});
    auto ackermann=Y((long delegate(long,long) self){return (long n,long m){return n?m?self(n-1,self(n,m-1)):self(n-1,1):m+1;};});
    writeln(map!factorial(iota(0,20)));
    writeln(map!fibonacci(iota(0,20)));
    writeln(map!((a){return ackermann(a%4,a/4);})(iota(0,20)));
}

I started with a trivial recursive definition of the factorial function and modified it until my code looked like this. The infinite type issue is being worked around with a type wrapper (struct F).