콜로이 가치가있는 Z 결합기의 종단

Question

나는 자신의 λ-calculus 통역사를 구축하려고 노력하고 있습니다. 지금까지는 콜로 - 가치와 정상 순서를 모두 지원합니다.

이제 고정 점을 통해 재귀를 시도하고 싶습니다. $ y $ 결합자는 정상적인 순서로 작동합니다. $$ \ text {fac}=lambda f . \ lambda n. \ text {iszero} \, n \, 1 (\ text {mul} \, n \, (f (\ text {pred} \, n)) \ text {,} $$ 예를 들어, 내 통역사는 $ y \, \ text {fac} \, 3 \ stackrel {\ text {no}} {\ no} 6 $ 을 산출합니다. (나는 거동적으로 동등한 교회 숫자를 소수 숫자로 쓸 것입니다)

콜로 - 가치에 대해 아는 한 $ z $ 결합기가 필요합니다 :

$$ z= λlambda f. (\ lambda x. f (\ lambda y. x x y)) (\ lambda x. f (\ lambda y. x x y)) \ text {,} $$

$ y $ 은 즉각적인 무한 회귀를 일으킬 수 있습니다.

내 문제는 $ z \, \ text {fac} \, 0 $ 을 어떻게 종료하도록 이해하지 못합니다. 또한 내 통역사에서 종료되지는 않지만 수동으로 먼저 이해하고 싶습니다.

몇 단계 후에 콜로 - 가치가 도착해야합니다. $$ Z \, \ TEXT {FAC} \, 0 \\= amambda f. (\ lambda x. f (\ lambda y. x x y)) (\ lambda x. f (\ lambda y. x x y)) \, \ text {fac} \, 0 \\\ StackRel {\ text {cbv}} {\ Nowarlow} (\ lambda x. \ text {fac} (\ lambda y. xxy)) (\ lambda x. \ text {fac} (\ lambda y. xxy) ) \, 0. \\\ StackRel {\ text {cbv}} {\ Nowarlow} \ text {fac} (\ lambda x. \ lambda x. \ text {fac} (\ lambda y '. xx y')) (\ lambda x . \ text {fac} (\ lambda y. xx y ')) y) \, 0 \\\ stackrel {\ text {cbv}} {\ Nowarrow} \ text {fac} \, f \, 0 \ stackrel {\ text {cbv}} {\ Nowarrow} \ text {iszero} \, 0 \ 1 \, a \ text {,} $$ < / span>

생략 된 용어가있는

$$ a=text {mul} \, 0 \, (f \, (\ text {pred} \, 0)) $$ 포함 < / P>

$$ f=amambda y. (\ lambda x. \ text {fac} (\ lambda y'xxy ')) (\ lambda x. \ text {fac } (\ lambda y'xxy ')) \, y $$ 다시.

이제 $ \ text {iszero} \, 0 \ stackrel {\ text {cbv}} {\ text} \ lambda t. \ lambda ft $ , ST

$$ \ text {iszero} \, 0 \ 1 \, a \ stackrel {\ text {cbv}} {\ narwar} (\ lambda t. \ lambda ft ) \, 1 \, \ stackrel {\ text {cbv}} {\ Nowarlow} (\ lambda f. 1) \, \ text {.} $$

우리의 언어가 $ a $ 지점을 무시할 분기 구조가있는 경우, 우리는 완료 될 것이지만, 콜로라도를 평가해야합니다 < Span 클래스="수학 용기"> $ a $ 값, 즉 추상화.

$ a=text {mul} \, 0 \, (f \, 0) $ 및 $ \ text {mul} \, 0 $ 은 또 다른 추상화가되므로 $ f \, (\ text {pred) } \, 0) $ .

$ \ text {pred} \, 0 \ stackrel {\ text {cbv}} {\ Nowarrow} 0 $ 이므로 $ F \, 0 $ .

$$ f \, 0= (\ lambda x. \ leambda x. \ lambda x. \ text {fac} (\ lambda y'xxy ')) (\ leambda x. \ text {fac} (\ lambda y'.xxy ')) \, y) \, 0 \ stackrel {\ text {cbv}} {\ text {cbv}} {\ narwarow} (\ lambda x. \ lambda x. \ text {fac} (\ lambda y' .xxy ')) (\ lambda x. \ text {fac} (\ lambda y'xxy') \, 0 \ stackrel {\ text {cbv}} {\ Nowarl} \ text {fac} \, f \ , 0 $$

이제 우리는 정사각형으로 돌아 왔습니다. 내가 뭔가 잘못하고 있니?

Answer 1

나는 당신이 감소를 잘못하고 있다고 생각하지 않지만 문제는 Z 결합자가 아닙니다.문제는 $ \ text {iszero} $ 입니다.콜 바이 가치에있는 분기 구문은 테스트에 관계없이 두 가지가 평가되기 때문에 각 지점에 대한 직접 조항을 콜 - 이름 (또는 이와 유사한 것과 같은 인수) 만 수행 할 수 없습니다.이것은 재귀와 함께 잘못 상호 작용하지만 일반적으로 바람직하지 않습니다.

대신, 콜 레인에서 분기 구문은 명시 적으로 지연된 인수를 취해야합니다.그래서 $$ \ t 텍스트 {iszero} \n\ (λ \ _. 1) (λ \ _ \ text {mul} \n\ 텍스트 \ (f \ text){pred} \ n)) $$ 실제로 필요하지 않으면 재귀 적 평가를 피할 수 있습니다. 물론 $ \ text {Iszero}를 남겨 둘 수 있습니다.$ 은 항상 이런 식으로 사용하며 추가 논쟁을 제공하지만 일반적으로 지연된 인수를 기대하는 것으로 정의 될 것이라고 생각합니다.