Y组合子在D语言中的应用？

Question

我尝试更好地学习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 的名称才能将其传递给它本身，所以它也行不通，对吧？

但是... 我该如何在D语言中实现Y组合器呢？

- user541686

---

委托已经是引用类型，您可以省略 &。 - BCS

@BCS：说得好，它原本是一个方法，我忘记删除了。我会修复的。 :) - user541686

Answer 1

在这里可以详细了解Y组合子。

- Eli Barzilay

---

似乎D语言相对于C#缺少的关键特性是无法在签名本身中使用委托别名的名称... - user541686

RosettaCode上的示例代码可以正常工作，因此可以说D缺少一个关键功能？ - gmfawcett

RosettaCode上的示例代码使用类型转换来规避问题，这很丑陋。可以将委托封装在结构体中，因为结构体可以具有其成员类型递归依赖于结构体类型的成员。但是Mehrdad有一点：别名声明目前比必要的更受限制，因为编译器不允许大多数形式的别名递归。（例如：struct Foo（T）{Bar* qux;} alias Foo！int Bar; //编译错误struct Foo(T){.Foo!int* qux;} //工作） - tgehr

Answer 2

这是D（和C/C++）的一个已知限制，处理类型化自引用的函数无法声明（据我上次检查时）。

我觉得这很讽刺，因为它实际上是语法（函数原型长度无限）或命名约定（相同的问题但是涉及名称重整）的限制，而不是任何语义或架构上的限制。

- BCS

---

+1 是的，这有点傻，我一直很困惑如何将一个函数传递给它自己。你知道他们是否计划修复这个问题吗？（例如，void foo(typeof(foo)) { }会产生“前向引用”错误。） - user541686

@Mahrdad：据我所知没有。但是，围绕该项的一个简单结构包装器可以解决这个问题。 - BCS

顺便说一下，Haskell也无法完成这项任务，会显示类似“无法声明长度无穷大的类型”的错误信息。 - vines

Answer 3

我的D语言中的通用Y组合器：

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）解决了无限类型问题。

- tgehr

Answer 4

我不了解D语言，但是对于大多数编程语言，当您尝试实现非递归时，函数类型会出现问题（在您的代码中尚未有Y-Combinator）。通常的解决方法是将类型分成几个部分，以此实现类型递归从而避免问题。

一些其他编程语言的例子：

- 在C语言中，通常会编写包含函数指针的结构体。然后可以将该结构体用作参数。

- 在OCaml中，可以添加一个包装函数类型的变量类型。同样，这可以将类型分离，使得类型递归成为可能。

如果您想了解其他语言的示例，请查看此页面。

- LiKao