C# dynamic을 사용하여 Y-combinator를 구현했는데 그렇지 않은 경우 무엇입니까?

Question

내 뇌가 매시 키즘 모드 인 것 같습니다. this, this 및 this에 익사 한 후 C#에서 DIY를 사용하고 싶었습니다.

은 내가 이는 Y-콤비라고 생각하지 않습니다 다음, 함께했다,하지만 는 자체를 참조하지 않고, 비 재귀 함수의 재귀를 만들기 위해 관리 보인다 :

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x); 

는 그래서이 주어진 :

Func<dynamic, Func<dynamic, dynamic>> fact = 
        self => n => n == 0 ? 1 : n * self(self)(n - 1); 
Func<dynamic, Func<dynamic, dynamic>> fib = 
        self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2); 

우리는 이것들을 생성 할 수 있습니다

Func<dynamic, dynamic> Fact = Y(fact); 
Func<dynamic, dynamic> Fib = Y(fib); 

Enumerable.Range(0, 10) 
      .ToList() 
      .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i))); 

Enumerable.Range(0, 10) 
      .ToList() 
      .ForEach(i => Console.WriteLine("Fib({0})={1}", i, Fib(i))); 

Answer 1

아니요, Y 결합자가 아닙니다. 당신은 그곳의 중간에 있습니다. 아직 적용하고있는 "시드"함수 내에서 자체 응용 프로그램을 분석해야합니다. 그 대신 이것이다 : 당신이해야

Func<dynamic, Func<dynamic, dynamic>> fact = 
        self => n => n == 0 ? 1 : n * self(self)(n - 1); 

:

Func<dynamic, Func<dynamic, dynamic>> fact = 
        self => n => n == 0 ? 1 : n * self(n - 1); 

주 첫 번째 정의에이 명 발생 반대로 두 번째 정의에 self의 단일 발생.

(the one often called Z, not Y

(:) 정교한 다시 편집 추가 : BTW, C 번호의 사용이 호출에 의해 가치 평가와 람다 계산법을 시뮬레이션하기 때문에 편집, 고정 소수점 당신이 원하는 콤비한다

Y g = g (Y g) 

그러나 당신이 함수를 호출하기 전에 가장 실용적인 프로그래밍 언어로, 당신은 함수의 인수 평가를 : Y을 설명 방정식이 (유도를 위해 the wikipedia page 참조). C/C++/Fortran/etc 프로그래머가 "값으로 호출"과 "참조로 호출"을 "vs"copy-restore로 호출 "을 구별하는 방식과 혼동해서는 안됩니다. , 등).

그러나 우리가했다, 우리는

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ... 

, 우리는 재귀 함수를 구성하는 우리의 시간 을 모두 보내고을 적용 주위에 결코 것 얻을 것입니다.

호출 이름 별 평가에서, 여기에 g이라는 함수를 평가되지 않은 인수 표현식 (여기서는 (Y g))에 적용합니다. 그러나 g이 fact과 같은 경우에는 다른 인수를 기다리고 있습니다. 따라서 우리는 (Y g)을 더 평가하기 전에 두 번째 인수가 g이 될 때까지 기다릴 것입니다. 그리고 함수가 무엇을하는지 (즉, 기본 경우)에 따라 (Y g)을 전혀 평가할 필요가 없을 수도 있습니다. 그렇기 때문에 Y이 이름 별 호출을 위해 작동합니다.

call-by-value에 대한 수정은 방정식을 변경하는 것입니다.. 대신 Y g = g (Y g), 우리는 대신 다음 방정식과 같이합니다 :

Z g = g (λx. (Z g) x) 

이 (내가 오른쪽으로 오른쪽 또는 가까운 방정식을 가지고 생각을 당신은 그것을 계산하고 Z의 정의에 맞는지 확인할 수 있습니다.)

"전체 재귀 함수"를 계산하고 g으로 넘겨주는 대신 한 번에 조금씩 재귀 함수를 계산하는 함수를 건네줍니다. 우리는 실제로 그것을 더 필요로하므로 인수 (x)에 적용 할 수 있습니다.