태그 보관물: logic

logic

이것이 재귀 프로 시저를 꼬리 재귀로 변환하는 일반적인 방법입니까? 적용하십시오. 시작하려면이 도우미 절차를 호출하십시오. “result”매개 변수의 초기

내가 변환하는 일반적인 방법을 발견 한 것 같습니다 어떤 꼬리 재귀에 재귀 절차를 :

  1. 추가 “result”매개 변수를 사용하여 헬퍼 서브 프로 시저를 정의하십시오.
  2. 프로 시저의 리턴 값에 적용될 항목을 해당 매개 변수에 적용하십시오.
  3. 시작하려면이 도우미 절차를 호출하십시오. “result”매개 변수의 초기 값은 재귀 프로세스의 종료점에 대한 값이므로 재귀 프로세스가 축소되기 시작하는 위치에서 결과 반복 프로세스가 시작됩니다.

예를 들어, 변환 할 원래 재귀 프로시 저는 다음과 같습니다 ( SICP 연습 1.17 ).

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

다음은 변환 된 꼬리 재귀 프로 시저입니다 ( SICP 연습 1.18 ).

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

누군가 이것을 증명하거나 반증 할 수 있습니까?

답변

이 시점에서 알고리즘을 설명하기에 너무 모호합니다. 그러나 고려해야 할 사항이 있습니다.

CPS

실제로 모든 코드를 테일 콜만 사용하는 형식으로 변환하는 방법이 있습니다. 이것이 CPS 변환입니다. CPS ( Continuation-Passing Style )는 각 함수에 연속을 전달하여 코드를 표현하는 형식입니다. 연속은 “나머지 계산”을 나타내는 추상적 인 개념입니다. CPS 형식으로 표현 된 코드에서 연속 을 구체화 하는 자연스러운 방법 은 값을 받아들이는 함수입니다. CPS에서는 값을 반환하는 함수 대신 현재 연속을 나타내는 함수를 함수가 “반환”하는 것에 적용합니다.

예를 들어 다음 기능을 고려하십시오.

(lambda (a b c d)
  (+ (- a b) (* c d)))

이것은 CPS에서 다음과 같이 표현 될 수 있습니다.

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

추악하고 종종 느리지 만 특정 장점이 있습니다.

  • 변환은 완전히 자동화 될 수 있습니다. 따라서 CPS 형식으로 코드를 작성하거나 볼 필요가 없습니다.
  • 썽킹 및 trampolining 과 함께 사용하여 테일 콜 최적화를 제공하지 않는 언어로 테일 콜 최적화를 제공 할 수 있습니다. 직접 테일 재귀 함수의 테일 콜 최적화는 재귀 호출을 루프로 변환하는 등의 다른 방법을 통해 수행 할 수 있습니다. 그러나 간접 재귀는 이러한 방식으로 변환하는 것만 큼 간단하지 않습니다.
  • CPS를 통해 연속은 일류 개체가됩니다. 연속성이 제어의 본질이기 때문에 언어의 특별한 지원 없이도 거의 모든 제어 연산자를 라이브러리로 구현할 수 있습니다. 예를 들어 goto, exceptions 및 cooperative threading은 모두 연속을 사용하여 모델링 할 수 있습니다.

TCO

테일 재귀 (또는 일반적으로 테일 콜)에 관심을 가지는 유일한 이유는 테일 콜 최적화 (TCO)를위한 것입니다. 그래서 더 좋은 질문은 “꼬리 호출 최적화 가능한 변환 수율 코드입니까?”입니다.

CPS를 다시 한 번 고려하면 그 특성 중 하나는 CPS로 표현 된 코드가 꼬리 호출만으로 구성된다는 것입니다. 모든 것이 테일 콜이므로 리턴 포인트를 스택에 저장할 필요가 없습니다. CPS 형식의 모든 코드는 테일 콜에 최적화 되어야합니다 .

글쎄요 우리는 스택을 제거한 것처럼 보일 수 있지만, 우리가 한 것은 단지 우리가 나타내는 방식을 바꾸는 것입니다. 스택은 이제 연속을 나타내는 클로저의 일부입니다. 따라서 CPS는 모든 코드 테일 콜을 마술처럼 최적화하지는 않습니다.

CPS가 모든 TCO를 만들 수 없다면 직접 재귀를위한 변형이 있습니까? 아니요, 일반적으로 아닙니다. 일부 재귀는 선형이지만 일부는 그렇지 않습니다. 비선형 (예 : 트리) 재귀는 단순히 어딘가에 가변적 인 양의 상태를 유지 해야합니다 .

답변