테일 추방 제거 란 무엇입니까?

Question

Steve Yegge는 그것을 a에서 언급했습니다 블로그 게시물 그리고 나는 그것이 무엇을 의미하는지 전혀 모른다. 누군가 나를 채울 수 있습니까?

그것은 같은 것입니다 꼬리 통화 최적화?

Answer 1

테일 콜 제거는 스택 공간을 절약하는 최적화입니다. 함수를 대체합니다 전화 a 이동. 꼬리 재귀 제거는 동일하지만 함수가 호출한다는 제약이 추가되었습니다.

기본적으로 마지막으로 기능이라면 A 그렇습니다 return A(params...) 그런 다음 스택 프레임의 할당을 제거하고 대신 적절한 레지스터를 설정하고 기능 본문으로 직접 점프 할 수 있습니다.

스택의 모든 매개 변수를 전달하고 일부 레지스터에서 값을 반환하는 (가상) 호출 규칙을 고려하십시오.

일부 기능은 (가상의 어셈블리 언어로) 컴파일 할 수 있습니다.

function:
//Reading params B, C, & D off the stack
pop B
pop C
pop D
//Do something meaningful, including a base case return
...
//Pass new values for B, C, & D to a new invocation of function on the stack
push D*
push C*
push B*
call function
ret

위의 내용이 실제로 무엇이든간에, 그것은 각 호출 기능에 대해 완전히 새로운 스택 프레임을 차지합니다. 그러나 반품을 제외하고는 테일 호출 후 기능 후에는 아무런 일이 발생하지 않기 때문에 해당 케이스를 안전하게 최적화 할 수 있습니다.

를 야기하는:

function:
//Reading params B, C, & D off the stack (but only on the first call)
pop B
pop C
pop D
function_tail_optimized:
//Do something meaningful, including a base case return
...
//Instead of a new stack frame, load the new values directly into the registers
load B, B*
load C, C*
load D, D*
//Don't call, instead jump directly back into the function
jump function_tail_optimized

최종 결과는 많은 스택 공간을 절약하는 동등한 기능, 특히 많은 수의 재귀 통화를 초래하는 입력에 대해 저장합니다.

내 대답에는 많은 상상력이 필요하지만 아이디어를 얻을 수 있다고 생각합니다.

Answer 2

~에서 여기:

"... 꼬리 재귀 제거는 꼬리 호출이 함수 자체에 대한 호출 인 꼬리 통화 제거의 특별한 경우입니다.이 경우, 새로운 인수를 이동 한 후 호출을 함수의 시작으로 점프하여 호출을 대체 할 수 있습니다. 적절한 레지스터 또는 스택 위치에 ... "

~에서 위키 백과:

"... 함수가 호출되면 컴퓨터는 호출 된 장소, 반환 주소를"기억해야 "하므로 통화가 완료되면 결과와 함께 해당 위치로 돌아갈 수 있습니다. 일반적 으로이 정보는 저장됩니다. 스택에서, 그들이 설명하는 통화 위치에 도달 한 시간의 순서대로 간단한 반환 위치 목록. 꼬리 재귀를 사용하면 우리가 부르는 곳을 기억할 필요가 없습니다. 대신 스택을 내버려 둘 수 있으며 새로 호출되는 함수는 결과를 원래 발신자에게 직접 반환합니다. 통화를 지점으로 변환하거나 이러한 경우 점프를 꼬리 통화 최적화라고합니다. 소스 코드의 다른 모든 설명 후에는 테일 호출이 어휘적으로 나타날 필요가 없습니다. 호출 함수는 최적화가 수행되면 호출 후에 아무것도 할 수있는 기회를 얻지 못하기 때문에 결과를 즉시 반환하는 것이 중요합니다 .... "