사용자 지정 VM에서 꼬리 호출을 구현하는 방법

Question

사용자 지정 가상 컴퓨터에서 꼬리 호출을 구현하려면 어떻게해야합니까?

필자는 원래 함수의 로컬 스택을 해제해야한다는 것을 알고 있습니다. 그런 다음 인수가되고 새로운 인수를 사용합니다. 그러나 함수의 로컬 스택을 해제하면 새 인수를 어떻게 푸시해야합니까? 그들은 방금 스택에서 튀어 나왔습니다.

Answer 1

나는 여기서 전통적인 "스택 기반"가상 머신에 대해 논의하고 있다고 생각합니다.

당신은 현재 함수의 로컬 스택 비 스택에서 여전히 관련 부품을 보존 ((여기서 "관련 부분"이며, 명확하게, 향후 재귀 꼬리 호출에 대한 인수가), 다음를 "등록"을 해제 팝 함수의 로컬 스택과 인수가 모두 정리되면 재귀 호출의 인수를 푸시합니다. CALL_FUN2는 "두 개의 인수로 함수를 호출"을 의미

AUX: LOAD_VAR N 
     LOAD_CONST 1 
     COMPARE 
     JUMPIF_GT LAB 
     LOAD_VAR TOT 
     RETURN_VAL 
LAB: LOAD_VAR N 
     LOAD_CONST 1 
     SUBTRACT 
     LOAD_VAR TOT 
     LOAD_VAR N 
     MULTIPLY 
     CALL_FUN2 AUX 
     RETURN_VAL 

: 최적화없이 같은 상징적으로 바이트 코드를 생성 할 수

def aux(n, tot): 
    if n <= 1: return tot 
    return aux(n-1, tot * n) 

: 예를 들어, 당신이 최적화있는 기능 같은 것을 가정하자.

POP_KEEP  2 
    POP_DISCARD 2 
    PUSH_KEPT 2 
    JUMP   AUX 

내가 함께 가서 내 상징적 인 바이트 코드를 만들고 있어요 물론

,하지만 의도는 분명하다 희망 : POP_DISCARD n 그냥 상단을 버리고 일반 대중이다 최적화, 그것은 언젠가처럼 될 수 n 항목을 스택에서 가져 왔지만 POP_KEEP n은 "어딘가에"보관하는 변형입니다 (예 : 응용 프로그램에 직접 액세스 할 수 없지만 VM 자체의 기계에만 해당하는 보조 스택 - 이러한 문자가있는 저장소를 "레지스터" VM 구현을 논의 할 때), 일치하는 "PUSH_KEPT n"은 "레지스터"를 VM의 정상 스택으로 다시 비 웁니다.

Answer 2

나는 이것이 잘못된 길을보고 있다고 생각합니다. 스택에서 이전 변수를 튕겨 내고 새 변수를 푸는 대신, 이미 존재하는 변수를 (신중하게) 다시 할당하기 만하면됩니다. 이것은 코드를 상응하는 반복 알고리즘으로 다시 작성한 경우 발생하는 것과 거의 동일한 최적화입니다. 이 코드에 대한

:

int fact(int x, int total=1) { 
    if (x == 1) 
     return total; 
    return fact(x-1, total*x); 
} 

는

fact: 
    jmpne x, 1, fact_cont # if x!=1 jump to multiply 
    retrn total   # return total 
fact_cont:    # update variables for "recursion 
    mul total,x,total  # total=total*x 
    sub x,1,x    # x=x-1 
    jmp fact    #"recurse" 

단지 재 할당, 팝업 또는 스택에 아무것도 밀어 필요가 없습니다 것입니다.
명백히 종료 조건을 두 번째로 지정하여 점진적으로 건너 뛸 수 있으므로 작업을 줄일 수 있습니다. 다시 찾고

fact_cont:    # update variables for "recursion 
    mul total,x,total  # total=total*x 
    sub x,1,x    # x=x-1 
fact: 
    jmpne x, 1, fact_cont # if x!=1 jump to multiply 
    retrn total   # return total 

이 '어셈블리는 "더 명확하게 재귀가 가진 문제는 문제의 유형 (및 크기) 완전히 알 수 있다는 것입니다

int fact(int x, int total=1) 
    for(; x>1; --x) 
     total*=x; 
    return total; 
}