Y-combinator en D?

Question

estoy tratando de aprender el Y-Combinator mejor (tipo de entiendo que en el esquema) y ponerlo en práctica en D 2.0, y yo estoy fallando bastante miserablemente:

auto fact = delegate(uint delegate(uint) recurse) 
{ 
    return delegate(uint n) 
    { 
     return n > 1 ? n * recurse(n - 1) : 1; 
    }; 
}; 

fact(fact)(5); 

Esto no lo hace trabajo, por la razón obvia de que no puedo pasar fact a fact (¿cuál sería su tipo?). Y además, todavía necesito el nombre fact para pasar a sí mismo, por lo que no funcionaría de todos modos, ¿verdad?

Pero ... ¿cómo hago para implementar el Y-combinator en D?

Answer 1

Consulte una explicación detallada here.

Answer 2

No sé D, pero con la mayoría de los idiomas tendrá problemas con el tipo de función cuando intente implementar la no recursión (todavía no hay Y-Combinator en su código). Se puede lograr el camino habitual separando los tipos en varias partes y de esta manera obteniendo la recursión en el tipo.

Algunos ejemplos de otros idiomas:

• En C por lo general se escribe una estructura que contiene el puntero de función. Esta estructura se puede usar como argumento.

• En OCaml se agregaría un tipo de variante que ajusta el tipo de función. De nuevo, esto permite separar los tipos para que la recursión de tipo sea posible.

Si quiere un ejemplo de otros idiomas, eche un vistazo a this page.

Answer 3

Es una limitación conocida de D (y C/C++) que las funciones que se ocupan de referencias automáticas mecanografiadas son imposibles (la última vez que lo comprobé) para declarar.

Me resulta irónico porque equivale a una limitación de sintaxis (la longitud del prototipo de función es infinita) o convención de nomenclatura (el mismo problema pero con el nombre de manipulación) en lugar de cualquier cosa semántica o arquitectónica.

Answer 4

Mi combinador Y genérica en 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))); 
} 

Empecé con una definición recursiva trivial de la función factorial y modificar hasta que mi código se veía así. El problema de tipo infinito se está trabajando con un wrapper de tipo (struct F).