꼬리 전화 제거를 구현하는 좋은 방법은 무엇입니까?

Question

나는 C/C++의 신성하지 않은 혼합으로 작은 Scheme 인터프리터를 작성했지만 아직 proper tail calls을 구현해야합니다.

나는 고전적인 Cheney on the MTA algorithm을 알고 있지만 이것을 구현하는 다른 좋은 방법이 있습니까? 나는 Scheme 스택을 힙에 넣을 수는 있지만, 여전히 표준 제거는 활성 테일 호출을 무제한으로 지원해야한다고 말한 것처럼 적절한 제거가되지는 않을 것입니다.

나는 또한 longjmps로 피딩했지만, 지금까지는 비 상호적인 경우에만 잘 작동 할 것이라고 생각합니다. 재귀 호출 꼬리 호출.

주요 C 기반 방식이 적절한 테일 재귀를 어떻게 구현합니까?

Answer 1

컴파일러를 작성하는 것보다 간단하고 VM은 통역사를 등록하고 트램 폴린하는 것입니다. 컴파일러가 아닌 인터프리터가 있기 때문에 꼬리 호출에 대한 적절한 지원을 얻으려면 몇 가지 간단한 변환 만하면됩니다.

C/C++에서 생각하고하는 것은 이상 할 수있는 연속 전달 스타일로 모든 것을 먼저 작성해야합니다. 댄 프리드먼의 ParentheC 튜토리얼은 결국 C.

으로 기계 번역하는 형태로 높은 수준을 변화, 재귀 프로그램을 단계별로, 당신은 기본적으로 간단한 VM을 구현하는 곳이 아닌 일반 함수를 사용합니다

return applyProc(rator, rand) 

는

된다 ... 평가, applyProc는 등, 당신이 전역 변수를 설정하여 인수를 전달하고 다음 인수에 goto을 (또는 최상위 루프와 프로그램 카운터를 사용) 할 호출

reg_rator = rator 
reg_rand = rand 
reg_pc = applyProc 
return 

즉, 일반적으로 서로를 재귀 적으로 호출하는 모든 함수는 반복되지 않는 코드 블록 인 의사 어셈블리로 축소됩니다. 최상위 루프는 프로그램을 제어합니다

for(;;) { 
    switch(reg_pc) { 
    case EVAL: 
     eval(); 
     break; 
    case APPLY_PROC: 
     applyProc(); 
     break; 
    ... 
    } 
} 

편집 : 내가 자바 스크립트로 작성 취미 계획 인터프리터에 대해 같은 과정을 통해 갔다. 익명의 절차를 많이 사용했지만 구체적인 참조로 도움이 될 수 있습니다. 2011-03-15 통해 2011-03-13부터 FoxScheme's commit history (30707a0432563ce1632a) (5dd3b521dac582507086) 봐.

편집^2 : 비 꼬리 재귀는 스택에 없더라도 여전히 메모리를 소비합니다.

Answer 2

당신이 무엇을 가지고 있는지 알지 못해도 가장 쉬운 (가장 계몽적인) 방법은 Dybvig의 "Scheme for Three Implementation Models"에서 스키마 컴파일러와 VM을 구현하는 것입니다. 나는 자바 스크립트 여기에 그것을 한 적이
(Dybvig의 PDF의 사본도있다) : SRC/vm.js에서 compileCons하고 "연산 코드"의 구현 : https://github.com/z5h/zb-lisp

체크 SRC/compiler.js

Answer 3

인터프리터 구현 기술에 관심이 있으시면 은 Christian Queinnec의 "LiSP - Lisp in Small Pieces"라는 책이 없습니다. 코드로 Scheme 시스템을 구현하는 모든 측면을 매우 철저하게 설명합니다. 그것은 훌륭한 책입니다.

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

그러나 ReadScheme.org에 서류를 확인하는 것을 잊지 마세요.

섹션

컴파일러 기술/구현 기술 및 최적화 http://library.readscheme.org/page8.html

는 꼬리 호출 최적화에 꽤 많은 논문이있다.

Dybvig의 논문 (고전) 인 에 대한 링크를 찾을 수 있습니다. 그것은 매우 명확한 태도 인 의 모든 것을 설명하고 동기 부여합니다.