계속 구현 방법

계속 구현 방법

저는 C로 표기된 스킴 통역기를 제작하고 있습니다.현재 C 런타임스택을 자체 스택으로 사용하고 있으며, 이 스택은 연속 구현에 약간의 문제가 있습니다.현재의 솔루션은 C 스택을 수동으로 힙에 복사한 후 필요에 따라 다시 복사하는 것입니다.표준 C가 아닌 것 외에 이 솔루션은 거의 이상적이지 않습니다.

C에서 Scheme의 계속을 구현하는 가장 간단한 방법은 무엇입니까?

처음부터 시작하는 경우에는 CPS(Continuation Passing Style)의 변혁을 고려해야 합니다.

좋은 소스로는 "LISP in small pieces"와 Marc Feelley's Scheme in 90 minutes가 있습니다.

당신에게 도움이 될 만한 기사를 읽은 기억이 나요.체니 부통령 M.T.A. :-)

SISC 등의 스킴의 실장 중에는 힙에 콜프레임을 할당하는 것이 있습니다.

@ollie: 모든 콜 프레임이 힙 상에 있는 경우에는 호이스트를 실행할 필요가 없습니다.물론 성능에는 단점이 있습니다. 즉, 모든 프레임을 힙에 할당하는 데 필요한 오버헤드 대비 상승 시간입니다.인터프리터에서 조정 가능한 런타임 파라미터여야 합니다. :-P

Dybvig의 논문은 아직 언급되지 않은 것 같다.읽는 것은 즐겁다.힙 기반 모델이 가장 구현하기 쉽지만 스택 기반 모델이 더 효율적입니다.문자열 기반 모델은 무시하십시오.

R. 켄트 다이비그"스킴을 위한 3가지 구현 모델"http://www.cs.indiana.edu/~dyb/http/3imp.pdf

또한 ReadScheme.org에서 구현 문서를 확인하십시오.https://web.archive.org/http://library.readscheme.org/page8.html

요약은 다음과 같습니다.

이 논문은 Scheme Programming Language의 3가지 구현 모델을 제시합니다.첫 번째는 지금까지 대부분의 스킴 구현에서 어떤 형태로든 사용된 힙 기반 모델입니다.두 번째는 대부분의 프로그램을 실행하는 힙 기반 모델보다 훨씬 효율적인 새로운 스택 기반 모델입니다.세 번째는 스킴의 다중 프로세서 구현에서 사용하기 위한 새로운 문자열 기반 모델입니다.

힙 기반 모델에서는 실제 파라미터 목록, 바인딩 환경, 콜프레임 등 여러 중요한 데이터 구조가 힙에 할당됩니다.

스택 기반 모델에서는 가능한 한 동일한 구조가 스택에 할당됩니다.따라서 힙 할당, 메모리 참조, 명령 시퀀스 단축, 가비지 컬렉션 감소 및 메모리 사용 효율이 향상됩니다.

문자열 기반 모델은 이러한 구조의 버전을 프로그램 텍스트에 바로 할당합니다. 프로그램 텍스트는 기호 문자열로 표시됩니다.문자열 기반 모델에서 Scheme 프로그램은 Scheme를 지원하기 위해 특별히 설계된 FFP 언어로 변환됩니다.이 언어의 프로그램은 다중 프로세서 문자열 감소 컴퓨터인 FFP 머신에 의해 직접 실행됩니다.

스택 기반 모델은 즉시 실용적인 이점이 있습니다. 이는 저자의 체즈 스킴 시스템에서 사용하는 모델이며 스킴의 고성능 구현입니다.문자열 기반 모델은 기계가 실현되면 FFP 기계에서 FFP에 대한 높은 수준의 대안으로 Scheme를 제공하는 데 유용합니다.

Clinger, Hartheimer 및 Ost의 기사인 "Implementation Strategies for First-class Continuations for First-class Continuations"에 좋은 요약이 나와 있습니다.나는 특히 Chez Scheme의 구현을 볼 것을 추천한다.

스택 복사는 그다지 복잡하지 않으며 성능을 향상시키기 위해 잘 알려진 많은 기술이 있습니다.힙 할당 프레임을 사용하는 것도 매우 간단하지만 명시적 연속성을 사용하지 않는 "일반" 상황에서는 오버헤드를 발생시킬 수 있습니다.

입력 코드를 Continuation Passing Style(CPS; 연속 패스 스타일)로 변환하면 스택을 완전히 제거할 수 있습니다.단, CPS는 우아하지만 프런트 엔드에 다른 처리 단계가 추가되어 특정 성능의 영향을 극복하기 위해 추가 최적화가 필요합니다.

~로soegaard된 바와 같이, 주요 는 그대로입니다.R. Kent Dybvig. "Three Implementation Models for Scheme".

스택을 입니다.합니다.call/cc.

보통 계속을 호출하면 실행 시간이 오래 걸리고 중복된 스택으로 메모리를 채웁니다.내가 이 멍청한 코드를 쓴 이유는 MIT-Scheme에서 계획이 깨진다는 걸 증명하기 위해서야

의 숫자를 한 것입니다.1+2+3+...+1000.

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

1000에서 100000으로 전환하면 코드는 2초 동안 지속되며 입력 수를 늘리면 코드가 크래시됩니다.

지금까지의 훌륭한 답변 외에 Andrew Appel의 Compiling with Continuations를 추천합니다.이것은 매우 잘 쓰여져 있고, C와 직접 거래하지는 않지만, 컴파일러 라이터에게는 매우 좋은 아이디어의 원천입니다.

또한 치킨 위키에는 내부 구조 및 컴파일 프로세스(CPS가 실제 컴파일 예시로 설명됨)와 같이 매우 흥미로운 페이지가 있습니다.

예를 들면, 다음과 같습니다.Chicken(연속성을 지원하는 C로 작성된 스킴 구현), Paul Graham의 On Lisp(Common Lisp에서 연속성의 서브셋을 구현하기 위한 CPS 변압기) 및 연속성 기반의 웹 프레임워크인 Weblocks(Common Lisp에서도 제한된 형식의 연속성을 구현합니다.

계속은 문제가 되지 않습니다.CPS를 사용하여 정기적으로 고차 함수를 구현하면 됩니다.단순한 스택 할당의 문제는 테일콜이 최적화되지 않는다는 것입니다.즉, 스킴을 설정할 수 없습니다.

현재 스킴의 스파게티 스택을 스택에 매핑하는 최선의 방법은 트램펄린을 사용하는 것입니다.트램펄라인은 기본적으로 C와 유사하지 않은 호출과 프로시저 종료에 대응하기 위한 추가 인프라스트럭처입니다.트램펄린 스타일(ps)을 참조하십시오.

이 두 가지 아이디어를 설명하는 몇 가지 코드가 있습니다.

연속성은 기본적으로 컨텍스트스위치 포인트에서의 스택과 CPU 레지스터의 저장된 상태로 구성됩니다.적어도 전환 시 전체 스택을 힙에 복사할 필요는 없습니다. 스택 포인터만 리다이렉트 할 수 있습니다.

연속은 광섬유를 사용하여 구현됩니다.http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 를 참조해 주세요.신중하게 캡슐화할 필요가 있는 것은 파라미터의 전달값과 반환값뿐입니다.

Windows 에서는, 파이버는 CreateFiber/SwitchToFiber 패밀리의 콜을 사용해 행해집니다.Posix 호환 시스템에서는 makecontext/swapcontext를 사용하여 실행할 수 있습니다.

boost::coroutine에는 구현의 기준점이 될 수 있는 C++용 코루틴이 구현되어 있습니다.

Use an explicit stack instead.

Patrick is correct, the only way you can really do this is to use an explicit stack in your interpreter, and hoist the appropriate segment of stack into the heap when you need to convert to a continuation.

This is basically the same as what is needed to support closures in languages that support them (closures and continuations being somewhat related).

전통적인 방법은 다음과 같습니다.setjmp그리고.longjmp단, 주의사항이 있습니다.

Here's a reasonably good explanation

ReferenceURL : https://stackoverflow.com/questions/6512/how-to-implement-continuations