Y-combinator in D?

Question

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) 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?

Tidewater

delegates are already reference types, you can drop the &. – Vosges

@BCS: Good point, it was originally a method and I forgot to remove that. Will fix. :) – Tidewater

Answer 1

See an extensive explanation here.

Homogenesis

Seems like the critical feature D lacks (as compared to C#) is ability to use a delegate alias's name inside the signature itself... – Tidewater

The example code at RosettaCode works, so it is fair to say D is lacking a critical feature? – Rosarosabel

The example code at RosettaCode uses type casts to circumvent the problem which is ugly. It is possible to wrap the delegate inside a struct, since structs can have members whose types depend recursively on the struct type. But Mehrdad has a point: alias declarations are currently more limited than necessary since the compiler disallows most forms of alias recursion. (Eg: struct Foo(T){Bar* qux;} alias Foo!int Bar; // compile error struct Foo(T){.Foo!int* qux;} // works ) – Jehu

Answer 2

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.

Vosges

+1 yeah it's a little silly, I was getting really confused trying to wrap my brain around how to pass a function to itself. Any idea if they plan on fixing this? (e.g. void foo(typeof(foo)) { } gives a forward reference error.) – Tidewater

@Mahrdad: Not that I know of. OTOH a trivial struct wrapper around the item fixes the issue. – Vosges

By the way, Haskell also fails to do that saying something like "Can't declare a type of infinite length" – Affirmative

Answer 3

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.

Posterity

Answer 4

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).

Jehu