Y-комбинатор в D?

Question

Я пытаюсь лучше изучить Y-комбинатор (вроде как я это понимаю на Схеме) и внедрить его в D 2.0, и у меня довольно плохо получается:

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

fact(fact)(5);

Это не работает, по очевидной причине, что я не могу пройти fact в fact (что бы это был за тип?). И кроме того, мне все еще нужно fact Имя, которое нужно передать самому себе, чтобы оно не сработало, верно?

Но... как мне реализовать Y-комбинатор в D?

Answer 1

Смотрите подробное объяснение здесь.

Answer 2

Это известное ограничение D (и C/C++), что функции, которые имеют дело с типизированными ссылками на себя, невозможно (в прошлый раз, когда я проверял) объявлять.

Я нахожу это ироничным, потому что это сводится к ограничению синтаксиса (длина прототипа функции бесконечна) или соглашению об именах (та же проблема, но с искажением имен), а не что-либо семантическое или архитектурное.

Answer 3

Я не знаю D, но с большинством языков у вас возникнут проблемы с типом функции, когда вы попытаетесь реализовать не-рекурсию (в вашем коде пока нет Y-Combinator). Обычный способ обойти это можно сделать, разделив типы на несколько частей, и таким образом получить рекурсию в тип.

Некоторые примеры из других языков:

• В Си обычно пишется структура, содержащая указатель на функцию. Эта структура может быть использована в качестве аргумента.

• В OCaml можно было бы добавить тип варианта, который переносит тип функции. Опять же, это позволяет разделить типы, поэтому возможна рекурсия типов.

Если вам нужен пример с других языков, взгляните на эту страницу.

Answer 4

Мой общий Y комбинатор в 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)));
}

Я начал с тривиального рекурсивного определения факториальной функции и модифицировал ее, пока мой код не выглядел следующим образом. Проблема бесконечного типа решается с помощью обёртки типа (struct F).