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

Я пытаюсь лучше изучить Y-комбинатор (я отчасти понимаю его в Scheme) и реализовать его в 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?


functional-programming d lambda-calculus y-combinator
person user541686    schedule 04.08.2011    source источник
comment
делегаты уже являются ссылочными типами, вы можете удалить &.   -  person BCS    schedule 04.08.2011
comment
@BCS: Хорошо, изначально это был метод, и я забыл его удалить. Починю. :)   -  person user541686    schedule 04.08.2011

Ответы (4)


arrow_upward
7
arrow_downward

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

person Eli Barzilay    schedule 04.08.2011
comment
Похоже, что критической функцией D, которой не хватает (по сравнению с С#), является возможность использовать имя псевдонима делегата внутри самой подписи... - person user541686; 04.08.2011
comment
Пример кода в RosettaCode работает, поэтому справедливо сказать, что в D отсутствует важная функция? - person gmfawcett; 04.08.2011
comment
Пример кода в RosettaCode использует приведение типов, чтобы обойти эту уродливую проблему. Делегат можно обернуть внутри структуры, поскольку структуры могут иметь члены, типы которых рекурсивно зависят от типа структуры. Но у Мердада есть точка зрения: объявления псевдонимов в настоящее время более ограничены, чем необходимо, поскольку компилятор запрещает большинство форм рекурсии псевдонимов. (Например: struct Foo(T){Bar* qux;} псевдоним Foo!int Bar; // ошибка компиляции struct Foo(T){.Foo!int* qux;} // работает) - person tgehr; 05.08.2011

arrow_upward
4
arrow_downward

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

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

person BCS    schedule 04.08.2011
comment
+1 да, это немного глупо, я действительно запутался, пытаясь понять, как передать функцию самой себе. Есть идеи, планируют ли они это исправить? (например, void foo(typeof(foo)) { } дает ошибку forward reference.) - person user541686; 04.08.2011
comment
@Mahrdad: Не то, чтобы я знал. OTOH, тривиальная оболочка структуры вокруг элемента устраняет проблему. - person BCS; 04.08.2011
comment
Кстати, Haskell тоже не может этого сделать, говоря что-то вроде "Can't declare a type of infinite length" - person vines; 06.08.2011

arrow_upward
3
arrow_downward

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

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

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

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

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

person LiKao    schedule 04.08.2011

arrow_upward
3
arrow_downward

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

person tgehr    schedule 04.08.2011