D에서 Y- 연결자?

Question

나는 (내가의 종류의 계획에 이해)와 D 2.0을 구현하는 Y-콤비 더 배우려고 노력하고있어 나는 매우 비참하게 실패하고 있습니다 :

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의 이름을 전달해야하므로 어쨌든 작동하지 않을 것입니다, 그렇습니까?

하지만 ... D에서 Y-combinator를 구현하려면 어떻게해야합니까?

Answer 1

광범위한 설명은 here을 참조하십시오.

Answer 2

D가 잘 모르지만 대부분의 언어에서는 비 재귀를 구현하려고 할 때 함수 유형에 문제가 발생합니다 (코드에 Y-Combinator가 아직 없음). 타입을 여러 부분으로 분리하고 재귀를 유형으로 분리함으로써 일반적인 방법을 얻을 수 있습니다. 다른 언어

일부 예 : C 하나에

• 은 일반적으로 함수 포인터를 포함하는 구조체를 기록합니다. 이 구조체는 인수로 사용될 수 있습니다.

• OCaml에서 함수 유형을 래핑하는 변형 유형을 추가합니다. 이 경우에도 유형을 분리 할 수 ​​있으므로 유형 재귀가 가능합니다.

다른 언어의 예제가 필요하면 this page을보십시오.

Answer 3

형식화 된 자체 참조를 다루는 함수가 선언하기가 불가능한 (마지막으로 확인한) D (및 C/C++)의 알려진 제한 사항입니다.

의미 론적이거나 구조적인 것보다 구문의 제한 (함수 프로토 타입의 길이가 무한 함) 또는 명명 규칙 (동일한 문제이지만 이름이 맹 글링 됨)이 있기 때문에이 아이러닉을 찾습니다. D에서

Answer 4

내 일반적인 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)로 해결되고 있습니다.