테일 콜

컴퓨터 과학에서 테일 콜은 ^[1]프로시저의 마지막 동작으로 실행되는 서브루틴 콜입니다.테일 타깃이 같은 서브루틴일 경우 서브루틴은 테일 재귀라고 하며 이는 직접 재귀의 특수한 경우입니다.테일 재귀(또는 테일 엔드 재귀)는 특히 유용하며 구현 시 최적화를 쉽게 처리할 수 있습니다.

테일 콜은 새로운 스택프레임을 콜스택에 추가하지 않고 실장할 수 있습니다.현재 프로시저의 프레임의 대부분은 불필요하게 되어 테일콜의 프레임으로 대체할 수 있습니다(프로세스의 오버레이와 비슷하지만 함수 콜의 경우).그러면 프로그램은 호출된 서브루틴으로 점프할 수 있습니다.표준 콜 시퀀스가 아닌 이러한 코드를 생성하는 것을 테일콜 제거 또는 테일콜 최적화라고 합니다.테일 콜을 배제함으로써 테일 위치에서의 프로시저 콜을 goto 문과 같이 효율적으로 구현할 수 있으므로 구조화된 효율적인 프로그래밍이 가능합니다.Guy L. Steel의 말에 따르면, "일반적으로 프로시저 호출은 매개 변수를 통과하는 GOTO 문으로 유용하게 간주될 수 있으며 [기계 코드] JUMP ^[2]명령으로 균일하게 코딩될 수 있습니다."

모든 프로그래밍 언어가 테일콜 제거를 필요로 하는 것은 아닙니다.그러나 기능하는 프로그래밍 언어에서는 테일콜 제거가 언어 표준으로 보증되는 경우가 많기 때문에 테일 재귀는 동등한 루프로 동일한 양의 메모리를 사용할 수 있습니다.테일 재귀 콜의 특수한 경우는 함수가 자신을 호출할 때 일반 테일콜보다 콜 제거에 더 적합합니다.언어 시멘틱스가 일반적인 테일 콜을 명시적으로 지원하지 않는 경우 컴파일러는 형제 콜을 최적화하거나 ^[3]호출자와 동일한 유형을 수신하고 반환하는 함수에 테일 콜을 최적화할 수 있습니다.

묘사

함수가 호출될 때 컴퓨터는 호출된 장소, 반환 주소를 "기억"해야 합니다.이것에 의해, 콜이 완료하면, 그 장소와 함께 반환됩니다.일반적으로 이 정보는 콜스택에 저장됩니다.이 정보는 콜스택에 기재되어 있는 콜로케이션에 도달한 시각에 따라 반환 로케이션의 단순한 리스트입니다.테일 콜의 경우 발신자를 기억할 필요가 없습니다.대신 테일 콜 삭제는 스택프레임을 ^[4]전달하기 전에 필요한 최소한의 변경만 이루어지며 테일 콜 함수는 원래 발신자에게 직접 돌아갑니다.테일 콜은 소스 코드의 다른 모든 문 뒤에 어휘적으로 표시될 필요는 없습니다.최적화가 실행될 때 호출 함수는 바이패스되므로 호출 함수는 테일콜 직후에 반환하고 테일콜 결과가 있으면 반환하는 것이 중요합니다.

비재귀 함수 호출의 경우 호출할 수 있는 함수가 그다지 많지 않기 때문에 이는 보통 약간의 시간과 공간만 절약하는 최적화입니다.그러나 테일 콜을 통해 재귀가 발생하는 재귀 또는 상호 재귀 함수를 처리할 경우 스택스페이스와 저장된 반환 수가 매우 커질 수 있습니다.이는 함수가 직접 또는 간접적으로 호출하여 매번 새로운 콜스택 프레임을 생성할 수 있기 때문입니다.테일콜을 삭제하면 점근 스택스페이스 요건이 선형(O(n))에서 상수(O(1)로 감소하는 경우가 많습니다.따라서 테일콜 제거는 ^[5][6]Scheme와 같은 일부 프로그래밍 언어 및 ML 패밀리의 언어 표준 정의에 의해 필요합니다.스킴 언어 정의는 테일 ^[7]컨텍스트에서 결과를 가질 수 있는 구문 형식을 지정함으로써 테일 위치의 직관적 개념을 정확하게 공식화합니다.테일 콜을 배제하는 것으로, 동시에 무제한의 테일 콜을 액티브하게 할 수 있는 실장은, 「적절하게 테일 재귀적」^[5]이라고도 불립니다.

공간 및 실행 효율성 외에도 테일콜 제거는 Continuation-Passing Style(CPS; 연속 통과 스타일)로 알려진 기능적 프로그래밍 용어에서 중요합니다.이 기능을 사용하지 않으면 스택 공간이 빠르게 고갈됩니다.

구문 형식

테일 콜은 함수의 구문 종료 직전에 배치할 수 있습니다.

기능. 후우(데이터.) {     a(데이터.);     돌아가다 b(데이터.); } 

여기, 둘 다a(data)그리고.b(data)콜이지만b이 순서는 복귀하기 전에 마지막으로 실행되며, 따라서 테일 위치에 있습니다.단, 모든 테일콜이 반드시 서브루틴의 구문 끝에 있는 것은 아닙니다.

기능. 막대기(데이터.) {     한다면 ( a(데이터.) ) {         돌아가다 b(데이터.);     }     돌아가다 c(데이터.); } 

여기에서는, 양쪽의 콜이b그리고.c꼬리 위치에 있습니다.이것은, 각각 if-branch의 끝에 놓여져 있기 때문입니다.단, 첫 번째 것이 구문적으로 if-branch의 끝에 있는 것은 아니지만,bar의 몸입니다.

이 코드에서는:

기능. foo1(데이터.) {     돌아가다 a(데이터.) + 1; } 

기능. foo2(데이터.) {     변화하다 리트 = a(데이터.);     돌아가다 리트; } 

기능. foo3(데이터.) {     변화하다 리트 = a(데이터.);     돌아가다 (리트 == 0) ? 1 : 리트; } 

에의 요구.a(data)에서 꼬리 위치에 있습니다.foo2단, Tail 위치도 아닙니다.foo1또는 인foo3는, 반환치를 반환하기 전에, 반환치를 검사 또는 변경할 수 있도록, 제어가 발신자에게 반환할 필요가 있기 때문입니다.

프로그램 예시

다음 프로그램은 ^[8]Scheme의 예시입니다.

;; 요인 : 숫자 -> 숫자 ;; 모든 양의 곱을 계산합니다. ; n 이하의 정수. (정의하다(요인 n)  (한다면(=n 0)     1     (*n (요인 (-n 1))))) 

곱셈 함수("*")가 꼬리 위치에 있기 때문에 이것은 테일 반복 스타일로 작성되지 않습니다.이는 다음과 같습니다.

;; 요인 : 숫자 -> 숫자 ;; 모든 양의 곱을 계산합니다. ; n 이하의 정수. (정의하다(요인 n)   (팩트 아이터 1 n)) (정의하다(팩트 아이터 제품. n)   (한다면(=n 0)       제품.       (팩트 아이터 (*제품. n)                  (-n 1)))) 

이 프로그램은 적용 순서 평가를 전제로 합니다.내부 절차fact-iter콜 자체가 제어 흐름의 마지막입니다.이를 통해 인터프리터 또는 컴파일러는 보통 다음과 ^[8]같이 실행을 재구성할 수 있습니다.

call fact-iter (4) call fact-iter (4) call fact-iter (4) call fact-iter (122) call fact-iter (24 1) return 24 return 24 return 24 return 24 return 24

공간 및 시간 측면에서 보다 효율적인 변종으로 전환합니다.

call fact-iter (4) call fact-iter (4) 인수를 (4) 인수 치환 (12) 인수를 (24 1) return 24 return 24

이 재구성에 의해, 콜 함수의 주소를 스택 또는 힙에 보존할 필요가 없고, 콜 스택프레임을 제외하고, 공간을 절약할 수 있습니다.fact-iter는 중간 결과 저장소로 재사용됩니다.이것은 또한 프로그래머가 매우 깊은 재귀에 필요한 스택 또는 힙 공간이 부족해지는 것에 대해 걱정할 필요가 없다는 것을 의미합니다.일반적인 구현에서 테일 재귀형 변종은 다른 변종보다 상당히 빠릅니다. 단, 일정한 요인에 의해서만 가능합니다.

기능적 언어로 작업하는 일부 프로그래머는 이 기능을 이용할 수 있도록 재귀 코드를 테일 재귀적으로 고쳐 씁니다.이를 위해서는 종종 "accumulator" 인수를 추가해야 합니다( ).product위의 예에서)를 함수에 적용합니다.경우에 따라서는(필터링 리스트 등), 또 언어에 따라서는 풀테일 재귀로 인해 이전에는 순수하게 기능했던 함수가 쓰여져 ^{[citation needed]}다른 변수에 저장된 참조를 변환해야 하는 경우가 있습니다.

테일 재귀 모듈로 단점

테일 재귀 모듈로 컨스(Tail recursion modulo cons)는 데이비드 H. D[9]. 워렌이 프롤로그의 컴파일 컨텍스트에서 도입한 테일 재귀 최적화의 일반화로서, 명시적으로 설정된 1회 언어로 간주됩니다.그것은 Daniel P에 의해 기술되었다. 프리드먼과 데이비드 S. 1974년에^[10] LISP 컴파일 기법으로 사용.이름에서 알 수 있듯이 재귀 호출 후에 실행할 수 있는 유일한 조작이 반환된 목록 앞에 기존 값을 추가하는 경우(또는 일반적으로 일정한 수의 단순한 데이터 구축 작업을 수행하는 경우)에 적용됩니다.따라서 이 콜은 전술한 cons 조작의 테일콜 저장("modulo")이 됩니다.단, 재귀 콜 종료 시 목록의 선두에 값을 프리픽스 하는 것은 재귀 콜에 대한 엔트리의 증가 목록 끝에 이 값을 부가하는 것과 같기 때문에 암묵적 어큐뮬레이터 파라미터와 같이 리스트가 부작용으로 구축됩니다.다음 Prolog fragment는 이 개념을 나타내고 있습니다.

코드 예시

프롤로그, 테일 재귀 모듈로 결점(%): 칸막이([], _, [], []). 칸막이([X Xs], 피벗, [X 쉬다], 빅스) :-   X @< 피벗, !,   칸막이(Xs, 피벗, 쉬다, 빅스). 칸막이([X Xs], 피벗, 스몰스, [X 쉬다]) :-   칸막이(Xs, 피벗, 스몰스, 쉬다). 

-- 하스켈의 경계된 재귀: 칸막이 :: 오르드 a => [a] -> a -> ([a],[a]) 칸막이 [] _ = ([],[]) 칸막이 (x:xs) p   x < > p     = (x:a,b)                      그렇지않으면 = (a,x:b)    어디에       (a,b) = 칸막이 xs p 

프롤로그 비율(명시적인 통합 포함): 비테일 재귀 변환 비율: 칸막이([], _, [], []). 칸막이(L, 피벗, 스몰스, 빅스) :- L=[X Xs],  (  X @< 피벗  -> 칸막이(Xs,피벗,쉬다,빅스), 스몰스=[X 쉬다]  ;  칸막이(Xs,피벗,스몰스,쉬다), 빅스=[X 쉬다]  ). 

프롤로그 비율(명시적인 통합 포함): 테일 슬레이브 변환 비율:%): 칸막이([], _, [], []). 칸막이(L, 피벗, 스몰스, 빅스) :- L=[X Xs],  (  X @< 피벗  -> 스몰스=[X 쉬다], 칸막이(Xs,피벗,쉬다,빅스)  ;  빅스=[X 쉬다], 칸막이(Xs,피벗,스몰스,쉬다)  ). 

따라서 테일 리커시브 변환에서는 이러한 콜이 최초로 새로운 리스트노드를 생성하여 그 노드를 설정하는 것으로 변환됩니다.first[ ] [ ], [ ], [ ], [ ], [ ], [ ], [ ], [rest필드는 인수로 재귀적으로 채워집니다.재귀가 게으르게 평가된 데이터 생성자 아래에서 보호될 때 동일한 효과가 달성됩니다. 데이터 생성자는 Haskell과 같은 느린 프로그래밍 언어에서 자동으로 달성됩니다.

C의 예

다음 fragment는 링크된 목록을 복제하는 C의 재귀 함수를 정의하고 있습니다(비교하기 위해 일부 동등한 Scheme 코드와 Prolog 코드를 코멘트로서 사용합니다).

유형화된 구조 목록. {     무효 *가치;     구조 목록. *다음 분.; } 목록.;  목록. *복제하다(컨스턴트 목록. *이요) {     목록. *머리 = 특수한 순서;      한다면 (이요 != 특수한 순서) {         목록. *p = 복제하다(이요->다음 분.);         머리 = 마로크(크기 *머리);         머리->가치 = 이요->가치;         머리->다음 분. = p;     }     돌아가다 머리; } 

;;; 스킴에서 (정의하다(복제하다 이요)   (한다면(것은 아니다.(특수 절차입니까?이요))     (단점(차이요)           (복제하다 (CDR이요)))     '())) 

프롤로그 %%, 복제하다([X Xs],R):-   복제하다(Xs,YS),   R=[X YS]. 복제하다([],[]). 

이 형식에서는 재귀 호출이 입력 목록의 나머지 부분을 복제한 후 제어가 발신자에게 반환되기 때문에 함수는 테일 재귀가 아닙니다.나머지를 복제하기 전에 헤드노드를 할당하는 경우에도 재귀 콜의 결과를 에 연결해야 합니다.next[^[a] ] 필드입니다.이 함수는 거의 꼬리 재귀적입니다.워렌의 방법은 메우는 책임을 떠넘긴다.next재귀 콜 자체에 입력하기 때문에 테일콜이 됩니다

유형화된 구조 목록. {     무효 *가치;     구조 목록. *다음 분.; } 목록.; 무효 duplicate_aux(컨스턴트 목록. *이요, 목록. *끝.);  목록. *복제하다(컨스턴트 목록. *이요) {       목록. 머리;      duplicate_aux(이요, &머리);     돌아가다 머리.다음 분.; }  무효 duplicate_aux(컨스턴트 목록. *이요, 목록. *끝.) {     한다면 (이요 != 특수한 순서) {         끝.->다음 분. = 마로크(크기 *끝.);         끝.->다음 분.->가치 = 이요->가치;         duplicate_aux(이요->다음 분., 끝.->다음 분.);     } 또 다른 {         끝.->다음 분. = 특수한 순서;     } } 

;;; 스킴에서 (정의하다(복제하다 이요)   (허락하다((머리 (목록.1)))     (허락하다이중 ((이요  이요)               (끝. 머리))       (견디다         ((것은 아니다.(특수 절차입니까?이요))          (set-cdr! 끝. (목록.(차이요)))          (이중 (CDR이요) (CDR끝.)))))     (CDR머리))) 

프롤로그 %%, 복제하다([X Xs],R):-    R=[X YS],    복제하다(Xs,YS). 복제하다([],[]). 

(센티넬 헤드노드는 코드를 단순화하기 위해 사용됩니다.)착신측은, 발신자가 반환 리스트의 선두에 부가하는 것이 아니고, 증가 리스트의 마지막에 부가됩니다.이 작업은 리스트의 시작에서 재귀 호출 전에 진행되며, 재귀 호출이 결과를 반환한 후에 리스트의 끝에서 뒤로 가는 것이 아니라 더 진행됩니다.따라서 재귀 계산을 반복 계산으로 바꾸는 누적 매개변수 기술과 유사합니다.

이 기법의 특징으로는 실행 콜스택에 부모 프레임이 작성됩니다.이러한 프레임은 테일콜 최적화가 존재하는 경우 테일재귀 콜의 착신측이 자신의 콜프레임으로 재사용할 수 있습니다.

테일 리커시브 실장은 누적 루프로서 명시적으로 반복적인 실장으로 변환할 수 있습니다.

유형화된 구조 목록. {     무효 *가치;     구조 목록. *다음 분.; } 목록.;  목록. *복제하다(컨스턴트 목록. *이요) {     목록. 머리, *끝.;     끝. = &머리;     하는 동안에 (이요 != 특수한 순서)     {         끝.->다음 분.        = 마로크(크기 *끝.);         끝.->다음 분.->가치 = 이요->가치;         이요 = 이요->다음 분.;         끝. = 끝.->다음 분.;     }     끝.->다음 분. = 특수한 순서;     돌아가다 머리.다음 분.; } 

 ;;; 스킴에서  (정의하다(복제하다 이요)    (허락하다((머리 (목록.1)))      (하다((끝. 머리 (CDR끝.))           (이요  이요   (CDR이요 )))          ((특수 절차입니까?이요) (CDR머리))        (set-cdr! 끝. (목록.(차이요)))))) 

프롤로그 %%, % % N/A 

역사

1977년 시애틀에서 열린 ACM 컨퍼런스에 전달된 문서에서 GOTO와 구조화된 프로그래밍에 대한 논쟁을 요약하고 프로시저의 꼬리 위치에서의 프로시저 호출은 호출된 프로시저에 대한 직접적인 제어 이전으로 가장 잘 처리될 수 있으며, 일반적으로 불필요한 스택 조작 조작을 제거할 수 있다는 것을 관찰했다.s.^[2] 이러한 "테일 콜"은 프로시저 콜이 어디에나 있는 언어인 리스프(Lisp)에서 매우 일반적이기 때문에, 이러한 형태의 최적화는 다른 구현에 비해 프로시저 콜의 비용을 크게 절감합니다.스틸은 제대로 시행되지 않은 절차 호출이 절차 호출에 비해 GOTO가 저렴하다는 인위적인 인식을 가져왔다고 주장했다.Steel은 또한 기계 코드 스택 조작 명령과 함께 "일반적인 절차에서 호출은 매개변수를 전달하고 [기계 코드] JUMP 명령으로 균일하게 코딩될 수 있다"^[2]고 주장했다.Steel은 Lisp에서 프로시저 호출 비용이 훨씬 낮았기 때문에 Lisp에서 잘 최적화된 수치 알고리즘이 당시 상용 Fortran 컴파일러에 의해 생성된 코드보다 더 빨리 실행될 수 있다는 증거를 인용했습니다.Steel과 Gerald Jay Sussman이 개발한 리스프 방언인 Scheme에서는 테일콜 제거가 모든 ^[11]인터프리터에 구현될 것이 보증됩니다.

구현 방법

테일 재귀는 일부 고급 언어, 특히 기능 및 논리 언어 및 리스프 어족에 중요합니다.이러한 언어에서는 테일 재귀가 가장 일반적으로 사용되는 반복 구현 방법(경우에 따라서는 유일한 방법)입니다.Scheme 언어 지정에서는 스택이 증가하지 않도록 테일콜을 최적화해야 합니다.테일 콜은 함수 이름을 사용하는 "goto" 문의 배리언트를 사용하여 Perl에서 명시적으로 발신할 수 있습니다.goto &NAME;^[12]

단, 함수 인수와 로컬 변수를 콜스택(적어도 x86과 같은 하드웨어 스택을 갖춘 시스템에서는 많은 언어의 디폴트 구현)에 저장하는 언어 구현에서는 일반화된 테일콜 최적화(상호 테일 재귀 포함)를 구현하는 것이 문제가 됩니다.콜처의 사이즈가 다음과 같습니다.의 액티베이션레코드가 발신자의 것과 다르기 때문에 스택프레임의 청소 또는 크기 조정이 필요할 수 있습니다.이러한 경우 테일 재귀의 최적화는 사소한 것이지만 일반적인 테일콜 최적화는 효율적으로 구현하기 어려울 수 있습니다.

예를 들어 Java Virtual Machine(JVM; Java 가상 머신)에서는 테일 재귀 콜을 제거할 수 있지만(기존 콜스택을 재사용하기 때문에), 일반 테일콜은 제거할 수 없습니다(이것에 의해 콜스택이 ^[13][14]변경되기 때문에).그 결과, JVM을 대상으로 하는 Scala와 같은 기능 언어는 직접 테일 재귀를 효율적으로 구현할 수 있지만 상호 테일 재귀는 구현할 수 없습니다.

GCC, LLVM/Clang 및 인텔 컴파일러 스위트는 C 및 기타 언어에 대해 보다 높은 최적화 수준 또는 다음과 같은 경우에 테일콜 최적화를 수행합니다.-foptimize-sibling-calls옵션이 ^[15][16][17]통과되었습니다.특정 언어 구문은 명시적으로 지원하지 않을 수 있지만, 컴파일러는 발신자와 착신자의 반환 유형이 동일하며, 두 함수에 전달된 인수 유형이 동일하거나 콜스택 ^[18]상의 총 스토리지 공간이 동일한지 여부를 판단할 수 있을 때마다 이 최적화를 수행할 수 있습니다.

다양한 구현 방법을 사용할 수 있습니다.

조립중

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2014년 6월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

테일 콜은 종종 기능 프로그래밍 및 논리 프로그래밍 언어의 인터프리터 및 컴파일러에 의해 보다 효율적인 반복 형식으로 최적화됩니다.예를 들어 스킴프로그래머는 보통 테일 위치에 있는 프로시저에 대한 호출로서 while loops를 표현하고 테일 콜을 ^[19]보다 효율적인 점프 명령으로 대체하기 위해 스킴 컴파일러 또는 인터프리터에 의존합니다.

어셈블리를 직접 생성하는 컴파일러의 경우 테일콜 제거는 간단합니다.스택에서 파라미터를 수정한 후 콜 opcode를 점프 opcode로 치환하면 충분합니다.컴파일러의 관점에서 위의 첫 번째 예는 처음에 의사 어셈블리 언어로 번역됩니다(실제로 이것은 유효한 x86 어셈블리입니다).

 foo:   불러 B   불러 A   리트 

테일콜 삭제는 마지막 두 행을 단일 점프 명령으로 대체합니다.

 foo:   불러 B   jmp  A 

서브루틴 후A완료하면, 다음의 반송 주소로 직접 돌아옵니다.foo불필요한 것은 생략하고ret진술.

일반적으로 호출되는 서브루틴에는 파라미터를 지정해야 합니다.따라서 생성된 코드는 테일이라고 불리는 서브루틴으로 점프하기 전에 A의 콜프레임이 올바르게 설정되어 있는지 확인해야 합니다.예를 들어 콜 스택에 리턴 주소뿐만 아니라 서브루틴의 파라미터가 포함되어 있는 플랫폼에서는 컴파일러가 콜스택을 조정하기 위한 명령을 발행해야 할 수 있습니다.이러한 플랫폼에서는 코드의 경우:

함수 foo(data1, data2) B(data1)가 A(data2)를 반환합니다.

(어디서)data1그리고.data2are parameters)는 컴파일러에 ^[b]의해 다음과 같이 변환됩니다.

 foo:    움직이다  조정하다,[sp+data1] ; 스택(sp) 파라미터에서 스크래치 레지스터로 data1을 가져옵니다.    밀다 조정하다            ; data1을 B가 예상하는 스택에 배치한다.    불러 B              ; B는 data1을 사용한다.    팝                 스택에서 data1을 삭제합니다.    움직이다  조정하다,[sp+data2] ; 스택(sp) 파라미터에서 스크래치 레지스터로 data2를 가져옵니다.    밀다 조정하다            ; data2를 A가 예상하는 스택에 배치한다.    불러 A              ; A는 data2를 사용한다.    팝                 ; 스택에서 data2를 삭제합니다.    리트 

테일콜 옵티마이저는 코드를 다음과 같이 변경할 수 있습니다.

 foo:    움직이다  조정하다,[sp+data1] ; 스택(sp) 파라미터에서 스크래치 레지스터로 data1을 가져옵니다.    밀다 조정하다            ; data1을 B가 예상하는 스택에 배치한다.    불러 B              ; B는 data1을 사용한다.    팝                 스택에서 data1을 삭제합니다.    움직이다  조정하다,[sp+data2] ; 스택(sp) 파라미터에서 스크래치 레지스터로 data2를 가져옵니다.    움직이다  [sp+data1],조정하다 data2를 A가 예상하는 곳에 배치한다.    jmp  A              ; A는 data2를 사용하여 즉시 발신자에게 돌아갑니다. 

이 코드는 실행 속도와 스택 공간 사용 측면에서 더 효율적입니다.

트램펄리닝을 통해

많은 Scheme 컴파일러가 C를 중간 타깃코드로 사용하기 때문에 C 컴파일러가 테일콜을 최적화하지 않는 경우에도 스택을 늘리지 않고 테일 재귀는 C로 부호화해야 합니다.많은 구현이 함수를 반복적으로 호출하는 코드 조각인 트램펄린으로 알려진 장치를 사용하여 이를 달성합니다.모든 기능은 트램펄린을 통해 입력됩니다.함수가 다른 함수를 직접 호출한 후 결과를 반환하는 대신 다른 함수를 호출해야 할 경우 호출할 함수의 주소와 호출 파라미터를 트램펄린(자체 호출된 함수)으로 되돌리고 트램펄린은 지정된 파라미터로 이 함수를 호출합니다.이것에 의해, C스택이 증가하지 않게 되어, 무한히 반복할 수 있게 됩니다.

Groovy, Visual Basic 등 트램펄린을 지원하는 언어로 고차 함수를 사용하여 트램펄린을 구현할 수 있습니다.NET 및 C#.^[20]

모든 함수 호출에 trampoline을 사용하는 것은 일반 C 함수 호출보다 다소 비싸기 때문에 적어도 하나의 Scheme 컴파일러인 Chicken은 Andrew Appel에 의해 ^[21]공개되지 않은 제안에서 Henry Baker에 의해 최초로 기술된 기술을 사용합니다.여기서 일반 C 호출은 사용되지만 스택 크기는 호출 전에 확인됩니다.스택이 최대 허용 크기에 도달하면 모든 라이브 데이터를 별도의 힙으로 이동함으로써 스택 상의 개체가 Cheney 알고리즘을 사용하여 가비지 수집됩니다.그 후 스택이 언바인드('팝')되고 프로그램은 가비지 컬렉션 직전에 저장된 상태에서 재개됩니다.베이커는 "애플의 방법은 엠파이어 스테이트 ^[21]빌딩에서 가끔 뛰어내림으로써 많은 수의 작은 트램폴린이 튀는 것을 피한다"고 말한다.가비지 컬렉션을 통해 상호 테일 재귀가 무기한 지속될 수 있습니다.단, 이 접근방식에서는 발신자의 스택프레임이 아직 존재한다는 보장이 없기 때문에 C 함수 호출이 반환되지 않도록 해야 합니다.따라서 프로그램코드 내부 개서(계속 통과 스타일)를 훨씬 극적으로 해야 합니다.

while 스테이트먼트와의 관계

테일 재귀는 명시적인 반복인 while 문과 관련지을 수 있습니다. 예를 들어 다음과 같이 변환합니다.

p(x) return bar(x)가 return foo(x)가 return foo(baz(x)를 반환하는 경우 절차 foo(x)

안으로

절차 foo(x)가 참일 경우 p(x) 반환 막대(x) 그렇지 않을 경우 x ← baz(x)

여기서 x는 둘 이상의 변수를 포함하는 튜플일 수 있다. 그렇다면, 종속성이 존중되도록 할당 문 x ← baz(x)를 구현할 때 주의해야 한다.보조 변수를 도입하거나 스왑 구성을 사용해야 할 수 있습니다.

좀 더 일반적으로 말하면

절차 foo(x)는 p(x)가 bar(x)를 반환하는 경우, q(x)가 baz(x)를 반환하는 경우...else r(x)가 foo(qux(x)를 반환하는 경우... 그렇지 않으면 foo(quux(x)를 반환하는 경우)

으로 바뀔 수 있다

절차 foo(x)가 true인 경우 p(x)가 baz(x)를 반환하는 경우 true인 경우, q(x)가 baz(x)를 반환하는 경우...그렇지 않으면 r(x) x ← qux(x)...그렇지 않으면 x ← quux(x)

예를 들어, 이 Python 프로그램은 꼬리 이외의 재귀적 정의를 제공합니다.fact요인:

방어하다 사실(n):     한다면 n == 0:         돌아가다 1     또 다른:         돌아가다 n * 사실(n - 1) 

실제로.n * fact(n - 1)에 콜을 랩하다fact그러나 인수를 추가하면 테일재귀적 정의로 변환할 수 있습니다.a어큐뮬레이터라고 합니다.^[8]

이 Python 프로그램은 테일 재귀적 정의를 제공합니다.fact_iter요인:

방어하다 fact_iter(n, a):     한다면 n == 0:         돌아가다 a     또 다른:         돌아가다 fact_iter(n - 1, n * a)  방어하다 사실(n):     돌아가다 fact_iter(n, 1) 

이 Python 프로그램은 반복적인 정의를 제공합니다.fact_iter요인:

방어하다 fact_iter(n, a):     하는 동안에 진실의:         한다면 n == 0:             돌아가다 a         또 다른:             n, a = n - 1, n * a  방어하다 사실(n):     돌아가다 fact_iter(n, 1) 

언어 지원

• 클로쥬르 - 클로쥬르에는recur특수 ^[22]형식
• 공통 리스프 - 일부 구현에서는 속도를 최적화한 경우 컴파일 중에 테일콜 최적화를 수행합니다.
• Elixir - Elixir는 현재 BEAM VM을 대상으로 하는 모든 언어와 마찬가지로 테일콜 최적화를^[23] 구현합니다.
• 느릅나무^[24] - 네
• Erlang - 네
• F#- F#는 가능한 한 TCO를 디폴트로 구현합니다.
• Go - 지원 없음^[26]
• 하스켈^[27] - 네
• JavaScript - ECMAScript 6.0 준거 엔진에는 Tail^[28] Call이 필요합니다.Tail Call은 현재 Safari^[29]/WebKit에 구현되어 있지만 V8 및 Spider Monkey에 의해 거부됩니다.
• 코틀린 - Hastailrec함수의^[30] 수식어
• Lua - 언어 정의에^[31] 테일 재귀가 필요합니다.
• 목표 C - 컴파일러는 -O1(또는 그 이상) 옵션이 지정되었을 때 테일 콜을 최적화하지만 Automatic Reference Counting(ARC; 자동 참조 카운트)에 의해 추가된 콜에 의해 쉽게 방해됩니다.
• OCaml - 네
• Perl - 함수 이름을 사용하는 "goto" 문의 변형과 함께 명시적:goto &NAME;^[32]
• PureScript - 있음
• Python - Stock Python 구현에서는 테일콜 최적화를 수행하지 않지만 타사 모듈을 ^[33]사용할 수 있습니다.언어 발명가 Guido van Rossum은 스택트레이스가 테일콜 제거에 의해 변경되어 디버깅이 어려워진다고 주장하며 프로그래머가 대신 명시적 반복을^[34] 사용하는 것을 선호합니다.
• 라켓^[35] - 네
• Rust - 테일콜 최적화는 제한된 상황에서 실행할 수 있지만 보증은^[36] 되지 않습니다.
• Scala - 테일 재귀 함수는 컴파일러에 의해 자동으로 최적화됩니다.이러한 기능은 옵션으로 다음과 같이 표시할 수도 있습니다.@tailrec주석: 함수가 테일^[37] 재귀적이지 않은 경우 컴파일 오류가 됩니다.
• 스킴 - 언어 정의에^[38][39] 필요합니다.
• Tcl - Tcl 8.6 이후 Tcl에는 tailcall^[40] 명령어가 있습니다.

「 」를 참조해 주세요.

무료 사전인 Wiktionary에서 테일 재귀를 검색합니다.

• 가치관 재귀
• 재귀(컴퓨터 과학)
• 인라인 확장
• 리프 서브루틴
• 코어 커시언스

메모들

레퍼런스