8

我正在尝试更好地学习 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's name 来传递给它自己，所以它无论如何都行不通，对吧？

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

4

4 回答 4

7

请参阅此处的详细说明。

于 2011-08-04T09:09:33.837 回答
4

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

我觉得这很讽刺，因为它限制了语法（函数原型的长度是无限的）或命名约定（同样的问题，但名称修改），而不是任何语义或架构。

于 2011-08-04T15:53:49.890 回答
3

我不知道 D，但是对于大多数语言，当你尝试实现非递归时，你会遇到函数类型的问题（你的代码中还没有 Y-Combinator）。通常的方法是可以通过将类型分成几个部分来实现，这样就可以递归到类型中。

其他语言的一些例子：

  • 在 C 中，通常会编写一个包含函数指针的结构。然后可以将此结构用作参数。

  • 在 OCaml 中，可以添加一种包装函数类型的变体类型。同样，这允许分离类型，因此可以进行类型递归。

如果您想要其他语言的一些示例，请查看此页面。

于 2011-08-04T08:13:05.450 回答
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) 解决。

于 2011-08-04T19:30:05.667 回答