스택리스 언어는 어떻게 작동하나요?
https://stackoverflow.com/questions/1016218
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
스택리스 언어에 대해 들어본 적이 있습니다.그러나 나는 그러한 언어가 어떻게 구현될지 전혀 모릅니다.누군가 설명해줄 수 있나요?
해결책
우리가 보유한 최신 운영 체제 (Windows, Linux)는 내가 "큰 스택 모델"이라고 부르는 것과 함께 작동합니다. 그리고 그 모델은 때때로 잘못되었으며 "스택이없는"언어의 필요성을 동기를 부여합니다.
"Big Stack Model"은 컴파일 된 프로그램이 인접한 메모리 영역에서 기능 호출에 "스택 프레임"을 할당 할 것이라고 가정합니다. 머신 지침을 사용하여 스택 포인터 (및 선택적 스택 프레임 포인터)를 매우 빠르게 조정합니다. 이로 인해 스택을위한 크고 연속적인 지역이있는 가격으로 빠른 기능 호출/반환이 발생합니다. 모든 프로그램의 99.99% 가이 최신 OS에서 실행되기 때문에이 스택 영역에 대한 큰 스택 모델, 컴파일러, 로더 및 OS "알 수"와 잘 어울립니다.
그러한 응용 프로그램이 가지고있는 모든 일반적인 문제는 "내 스택이 얼마나 커야합니까?". 메모리가 흙이 저렴하므로 대부분 발생하는 일은 스택을 위해 큰 청크가 따로 설정되어 있으며 (MS 기본값 1MB), 일반적인 애플리케이션 통화 구조는 그것을 사용하는 곳 근처에서는 결코 얻지 못합니다. 그러나 애플리케이션이 모든 것을 사용한다면, 스택의 끝을 벗어나면서 불법 메모리 참조 ( "죄송합니다.
가장 소위 "스택리스"언어는 실제로 스택이없는 것이 아닙니다. 그들은이 시스템에서 제공하는 인접한 스택을 사용하지 않습니다. 대신 그들이하는 일은 각 함수 호출의 힙에서 스택 프레임을 할당하는 것입니다. 기능 호출 당 비용은 다소 증가합니다. 함수가 일반적으로 복잡하거나 언어가 해석되는 경우이 추가 비용은 중요하지 않습니다. (또한 프로그램 통화 그래프에서 통화 DAG를 결정하고 전체 DAG를 덮기 위해 힙 세그먼트를 할당 할 수 있습니다.이 방법으로 힙 할당과 클래식 빅 스택 함수의 속도는 통화 DAG 내부의 모든 통화에 대한 호출을 얻습니다).
스택 프레임에 힙 할당을 사용하는 데 몇 가지 이유가 있습니다.
1) 프로그램이 해결중인 특정 문제에 대해 깊은 재귀를하는 경우 필요한 크기가 알려지지 않기 때문에 "큰 스택"영역을 사전에 전용하기가 매우 어렵습니다. 어색하게 함수 호출을 정리하여 스택이 충분한 지 확인하기 위해 점검 할 수 있으며, 그렇지 않은 경우 더 큰 덩어리를 재 할당하고 이전 스택을 복사하고 모든 포인터를 스택에 다시 조정하십시오. 그것은 너무 어색하여 어떤 구현도 모릅니다. 스택 프레임을 할당한다는 것은 말 그대로 할당 가능한 메모리가 남지 않을 때까지 애플리케이션이 미안하다고 말할 필요가 없음을 의미합니다.
2) 프로그램은 하위 작업을 포크합니다. 각 하위 작업에는 자체 스택이 필요하므로 제공된 "큰 스택"을 사용할 수 없습니다. 따라서 각 하위 작업에 스택을 할당해야합니다. 수천 개의 가능한 하위 작업이있는 경우 이제 수천 개의 "큰 스택"이 필요할 수 있으며 메모리 요구가 갑자기 우스꽝스럽게됩니다. 스택 프레임 할당하면이 문제가 해결됩니다. 종종 하위 작업 "스택"은 어휘 스코핑을 구현하기 위해 상위 작업을 다시 참조합니다. 하위 태스크 포크로서 "Subsacks"의 트리가 "선인장 스택"이라고 불립니다.
3) 귀하의 언어에는 연속이 있습니다. 이들은 현재 기능으로 볼 수있는 어휘 스코프의 데이터가 어떻게 든 나중에 재사용을 위해 보존되어야합니다. 부모 스택 프레임을 복사하고 선인장 스택을 등반하고 진행하여 구현할 수 있습니다.
그만큼 앵무새 구현 한 Langauge 프로그래밍 1) 및 2). 나는 3)에서 일하고있다.
다른 팁
언어 프레임 워크 앵무새에 대한 좋은 기사가 있습니다. http://www.linux-mag.com/cache/7373/1.html. 앵무새는 통화를 위해 스택을 사용하지 않으며이 기사는이 기술을 약간 설명합니다.
스택이없는 환경에서는 (Turing Machine, Assembly 및 Brainfuck)에 대해 다소 익숙하지 않으므로 자신의 스택을 구현하는 것이 일반적입니다. 언어에 스택을 내장하는 것에 대한 근본적인 것은 없습니다.
이 중 가장 실용적인 조립품에서 사용 가능한 메모리 영역을 선택하고 스택 레지스터를 바닥을 가리 키거나 푸시 및 팝을 구현하기 위해 점점 또는 감소합니다.
편집 : 일부 아키텍처에는 전용 스택이 있지만 필요하지 않습니다.
이 기사에는 계속되는 내용에 대한 이해하기 쉬운 설명이 있습니다. http://www.defmacro.org/ramblings/fp.html
연속은 스택 기반 언어의 함수에 전달할 수 있지만 언어 고유의 의미에 따라 "스택리스"로 만드는 데 사용될 수도 있습니다.물론 스택은 여전히 존재하지만 Ira Baxter가 설명했듯이 이는 하나의 큰 연속 세그먼트가 아닙니다.
스택리스 C를 구현하고 싶다고 가정해 보겠습니다.가장 먼저 알아야 할 것은 스택이 필요하지 않다는 것입니다.
a == b
그런데, 이런가요?
isequal(a, b) { return a == b; }
아니요.스마트 컴파일러는 호출을 인라인하기 때문에 isequal, 그것들을 a == b.그렇다면 모든 것을 인라인으로 처리하는 것은 어떨까요?물론, 더 많은 코드를 생성하게 되지만, 스택을 제거하는 것이 그만한 가치가 있다면 약간의 절충을 통해 쉽게 수행할 수 있습니다.
재귀는 어떻습니까?괜찮아요.다음과 같은 꼬리 재귀 함수:
bang(x) { return x == 1 ? 1 : x * bang(x-1); }
여전히 인라인될 수 있습니다. 실제로는 위장된 for 루프이기 때문입니다.
bang(x) {
for(int i = x; i >=1; i--) x *= x-1;
return x;
}
이론적으로는 정말 똑똑한 컴파일러가 이를 알아낼 수 있습니다.그러나 덜 똑똑한 사람은 여전히 이를 goto로 단순화할 수 있습니다.
ax = x;
NOTDONE:
if(ax > 1) {
x = x*(--ax);
goto NOTDONE;
}
작은 거래를 해야 하는 경우가 하나 있습니다.이는 인라인될 수 없습니다.
fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }
스택리스 C는 이것을 할 수 없습니다.많이 포기하고 계시나요?설마.이것은 일반적인 C도 잘 할 수 없는 일입니다.내 말을 믿을 수 없다면 그냥 전화해 보세요 fib(1000) 그리고 당신의 소중한 컴퓨터에 무슨 일이 일어나는지 살펴보세요.
나를 고대라고 부르지 만 Fortran 표준과 Cobol이 재귀 통화를 지원하지 않았으므로 스택이 필요하지 않은시기를 기억할 수 있습니다. 실제로, 나는 스택이없는 CDC 6000 시리즈 머신의 구현을 기억하며, 서브 루틴을 재귀 적으로 부르려고한다면 Fortran은 이상한 일을 할 것입니다.
레코드의 경우 콜 스택 대신 CDC 6000 시리즈 명령어 세트는 RJ 명령어를 사용하여 서브 루틴을 호출했습니다. 이로 인해 통화 대상 위치에서 현재 PC 값을 저장 한 다음 다음 위치에 분기됩니다. 결국, 서브 루틴은 통화 대상 위치로 간접적으로 점프 할 것입니다. 다시로드 된 PC를 재 장전하여 발신자에게 효과적으로 반환했습니다.
분명히, 그것은 재귀적인 전화로 작동하지 않습니다. (그리고 내 기억은 재귀를 시도하면 CDC Fortran IV 컴파일러가 깨진 코드를 생성한다는 것입니다 ...)
내가 틀렸다면 자유롭게 수정 해주세요. 그러나 각 함수 호출 프레임에 대한 힙에 메모리를 할당하면 극도의 메모리 스 래싱이 발생한다고 생각합니다. 운영 체제는 결국이 메모리를 관리해야합니다. 이 메모리 스 래싱을 피하는 방법은 통화 프레임의 캐시 일 것이라고 생각합니다. 따라서 어쨌든 캐시가 필요한 경우 메모리가 연속적으로 만들어 스택이라고 할 수도 있습니다.
