스택 지향 프로그래밍

Stack-oriented programming

스택 지향 프로그래밍은 매개 변수를 전달하기 위해 스택 머신 모델에 의존하는 프로그래밍 패러다임입니다.스택 지향 언어는 하나 이상의 스택에서 작동하며, 각 스택의 용도는 다를 수 있습니다.스택 지향 [1]시스템에서 사용하려면 다른 프로그래밍 언어의 프로그래밍 구조를 수정해야 합니다.스택 지향 언어 중에는 포스트픽스 또는 리버스 폴란드어 표기로 동작하는 것이 있습니다.명령어 인수 또는 파라미터는 명령어 앞에 기재되어 있습니다.를 들어 (prefix 또는 폴란드어 표기) 또는 (infix 표기) 대신 postfix 표기법이 작성됩니다.Forth, RPL, PostScript, BibTeX 스타일의 설계[2] 언어 및 많은 어셈블리 언어가 이 패러다임에 들어맞습니다.

스택 기반 알고리즘에서는 스택 상단의 데이터 1개를 사용하여 데이터를 스택 상단으로 되돌림으로써 데이터를 고려합니다.스택 조작 연산자가 필요하기 때문에 스택이 데이터를 조작할 수 있습니다.스테이트먼트의 효과를 강조하기 위해 스테이트먼트 전후 스택의 상단을 나타내는 코멘트가 사용됩니다.이를 스택 효과 다이어그램이라고 합니다.

포스트스크립트 스택은 추가 목적으로 별도의 스택을 고려합니다.여기에는 변수, 사전, 절차, 일부 일반적인 절차의 해부도, 제어 및 흐름이 고려됩니다.언어 모델의 분석은 표현과 프로그램을 단순하고 이론적으로 해석할 수 있게 한다.

스택 기반 알고리즘

PostScript는 postfix 스택 기반 언어의 예입니다.이 언어의 식 예는 입니다.2 3 mul식을 계산하려면 스택 방향의 구조를 이해해야 합니다.

스택 방향은 다음과 같은 컨베이어 벨트의 유사성으로 나타낼 수 있습니다.컨베이어 벨트(입력)의 끝에 표시된 플레이트2,3,그리고.mul는 순서대로 배치됩니다.컨베이어 끝의 플레이트(2)를 사용할 수 있지만, 끝의 플레이트를 제거할 때까지 다른 플레이트에 접근할 수 없습니다.플레이트는 스택에만 저장할 수 있으며 스택 상부에서만 추가 또는 분리할 수 있으며 중앙 또는 하부에서 분리할 수 없습니다.블랭크 플레이트(및 마커)를 공급하고 플레이트를 영구적으로 폐기할 수 있습니다.

Human stack.svg

테이크 플레이트2쌓아놓고 접시를 들고3쌓아놨어요.다음, 다음,mul접시. 이것은 수행 지침입니다.그런 다음 위의 2개의 플레이트를 스택에서 꺼내 라벨을 곱합니다(2그리고.3결과를 기입합니다( ).6)을 새 접시에 담습니다.기존 플레이트 2개를 폐기한다(2그리고.3)와 플레이트mul새 플레이트를 스택 위에 놓습니다.컨베이어에 더 이상 플레이트가 남아 있지 않은 상태에서 계산 결과(6)는 스택 상단의 플레이트에 표시되어 있습니다.

이것은 매우 간단한 계산입니다.예를 들어, 보다 복잡한 계산이 필요한 경우, 예를 들어, 처음에 postfix 형식으로 작성되었을 경우, 즉 정확히 동일한 방법으로 계산을 수행하여 올바른 결과를 얻을 수 있습니다.계산 단계는 아래 표에 나와 있습니다.각 열은 입력 요소(컨베이어 끝의 플레이트)와 해당 입력을 처리한 후의 스택 내용을 나타냅니다.

입력 2 3 더하다 11 멀티 1 더하다
스택 2 3
2
5 11
5
55 1
55
56

모든 입력을 처리한 후 스택은 다음을 포함합니다.56그게 답이죠

이를 통해 다음과 같은 결론을 내릴 수 있습니다.스택 기반 프로그래밍 언어에는 데이터를 처리하는 방법이1개밖에 없습니다.이 방법은 popping이라고 불리는 데이터를 스택 상부에서 가져와 push라고 하는 데이터를 스택 상부에 되돌리는 것입니다.기존 또는 다른 프로그래밍 언어로 쓸 수 있는 표현은 포스트픽스(또는 프리픽스) 형식으로 쓸 수 있으므로 스택 지향 언어로 해석할 수 있습니다.

스택 조작

스택은 스택 지향 언어로 데이터를 조작하는 주요 수단이기 때문에 이러한 언어는 종종 일종의 스택 조작 연산자를 제공합니다.일반적으로 제공되는 것은 다음과 같습니다.dup스택 위에 요소를 복제하려면exch(또는swap스택 상단의 요소를 교환하려면 (첫 번째 요소가 두 번째 요소가 되고 두 번째 요소가 첫 번째 요소가 됩니다),roll스택 내 또는 스택 일부에서 요소를 주기적으로 허용하려면pop(또는drop스택 상단의 요소(암묵적인 의미)를 폐기합니다.이것들은 학습 절차에서 핵심이 된다.

스택 효과도

스테이트먼트의 효과를 이해하기 위해 스테이트먼트의 전후 스택의 상단을 나타내는 짧은 코멘트를 사용합니다.항목이 여러 개 있는 경우 스택의 맨 위가 맨 오른쪽입니다.이 표기법은 일반적으로 제4언어로 사용되며, 코멘트는 괄호로 둘러싸여 있습니다.

(전 --후) 

예를 들어 기본적인 4번째 스택 연산자에 대해 설명합니다.

이중  ( a -- a ) 떨어지다 ( a -- ) 바꾸다 ( a b -- b a ) 에 걸쳐서 ( a b -- a b a ) 썩다  ( a b c -- b c a ) 

그리고 그fib다음은 기능에 대한 설명입니다.

파이브  ( n -- n' ) 

이것은 Hoare 로직의 전제 조건 및 사후 조건과 동일합니다.두 코멘트는 모두 어설션으로 참조할 수도 있습니다.스택 기반 언어의 맥락에서는 생각할 수 없습니다.

PostScript 스택

PostScript 및 기타 스택 언어에는 다른 용도로 별도의 스택이 있습니다.

변수 및 사전

다른 표현에 대한 평가는 이미 분석되었다.변수의 실장은 모든 프로그래밍 언어에서 중요하지만 스택 지향 언어의 경우 데이터와 상호작용하는 방법은 하나뿐이기 때문에 특히 중요합니다.

PostScript와 같은 스택 지향 언어에서 변수를 구현하는 방법은 일반적으로 키와 의 쌍 사전을 보관하는 별도의 특수 스택을 포함합니다.변수를 작성하려면 먼저 키(변수 이름)를 만들고, 여기에 값을 관련지어야 합니다.PostScript에서 이름 데이터 개체 앞에/,그렇게/x이름 데이터 객체입니다.예를 들어, 번호에 관련지을 수 있습니다.42.그define명령어는def,그렇게

/x 42 def

이름과 관련짓다x숫자와 함께42스택 맨 위에 있는 사전에서.사이에 차이가 있다/x그리고.x– 전자는 이름을 나타내는 데이터 객체입니다.x에 정의되어 있는 것을 나타냅니다./x.

절차들

스택 베이스 프로그래밍 언어의 프로시저는 그 자체로 데이터 오브젝트로 취급된다.PostScript에서 절차는 다음과 같이 표시됩니다.{그리고.}.

예를 들어 PostScript 구문에서는

{ dup mul }

는, 스택의 상부에 있는 것을 복제해, 그 결과를 곱하는 어나니머스 프로시저를 나타냅니다(스쿼링 프로시저).

프로시저는 단순한 데이터 객체로 처리되므로 프로시저가 포함된 이름을 정의할 수 있습니다.검색되면 직접 실행됩니다.

사전은 범위를 제어하고 정의를 저장할 수 있는 수단을 제공합니다.

데이터 객체는 최상위 사전에 저장되므로 사전에서 정의를 검색할 때 최상위 사전을 확인한 후 다음 사전을 확인하는 등 예기치 않은 기능이 자연스럽게 발생합니다.다른 딕셔너리에 이미 정의되어 있는 프로시저와 이름이 같은 프로시저가 정의되어 있는 경우 로컬 프로시저가 호출됩니다.

일부 일반적인 절차의 해부도

절차에는 종종 인수가 필요합니다.이 절차는 다른 프로그래밍 언어와는 달리 매우 구체적인 방법으로 처리됩니다.

PostScript에서 Fibonacci 번호 프로그램을 조사하려면:

  /discloses(/disclosed.   {      이중 이중 1 이큐 교환하다 0 이큐 또는 것은 아니다.      {         이중 1 후보선수 파이브         교환하다 2 후보선수 파이브         더하다      } 한다면   } 방어하다 

스택에서 재귀 정의가 사용됩니다.피보나치 번호 함수는 1개의 인수를 사용합니다.먼저 1 또는 0으로 테스트됩니다.

프로그램의 각 주요 단계를 분해하여 스택을 반영하고, 다음 계산을 가정합니다.fib(4):

스택: 4 dup 스택: 4 4 dup 스택: 4 4 4 1 eq 스택: 4 false 4 eq 스택: 4 false 또는 스택: 4 false not stack: 4 true

식이 true로 평가되므로 내부 절차가 평가됩니다.

스택: 4 dup 스택: 4 4 1 서브 스택: 4 3 파이브
(여기에 전화주세요)
스택: 4 F(3) 교환 스택: F(3) 4 2 서브 스택: F(3) 2 파이브
(여기에 전화주세요)
스택: F(3) F(2) 스택 추가: F(3)+F(2)

예상된 결과입니다.

이 절차에서는 이름 있는 변수는 사용하지 않습니다.단순히 스택입니다.이름 있는 변수는 다음 명령을 사용하여 생성할 수 있습니다./a exch def건설하다.예를들면,{/n exch def n n mul}

명명된 변수를 사용하여 제곱하는 절차입니다.n라고 가정하면/sq {/n exch def n n mul} def그리고.3 sq호출됩니다.순서는sq다음과 같은 방법으로 분석됩니다.

스택: 3 /n 교환 스택: /n 3 def 스택: (정의 완료) n 스택: 3 n 스택: 3 3 mul 스택: 9

예상된 결과입니다.

제어 및 흐름

어나니머스 프로시저가 존재하기 때문에 흐름 제어가 자연스럽게 발생할 수 있습니다.if-then-else 문에는 조건, 조건이 참일 경우 수행할 절차, 조건이 거짓일 경우 수행할 작업의 세 가지 데이터가 필요합니다.예를 들어 PostScript에서는

 2 3 gt { (2는 3보다 크다) = } { (2는 3 이하) = } ifelse 

는 C에서 거의 동등한 기능을 수행합니다.

 한다면 (2 > 3) { 인쇄물(2는 3보다 크다.\n"); } 또 다른 { 인쇄물("2는 3보다 크지 않습니다.\n"); } 

루핑 및 기타 구성도 비슷합니다.

언어 모델 분석

스택 지향 언어로 제공되는 단순한 모델은 구문 분석이 필요하지 않고 어휘 분석만 수행되므로 표현식과 프로그램을 훨씬 더 빠르게 해석할 수 있습니다.이러한 프로그램을 작성하는 방법은 기계에 의한 해석을 용이하게 하기 때문에 PostScript는 프린터에 매우 적합합니다.그러나 약간 인위적인 PostScript 프로그램 작성 방식은 PostScript와 같은 스택 지향 언어를 이해하는 데 초기 장벽을 형성할 수 있습니다.

내장된 정의나 다른 정의를 덮어쓰고 섀도우 기능을 사용하면 프로그램을 디버깅하기 어렵고 이 기능을 무책임하게 사용하면 예측할 수 없는 동작이 발생할 수 있지만 일부 기능을 크게 단순화할 수 있습니다.예를 들어 PostScript 사용 시showpage사용자 연산자를 정의하거나 코드를 반복하여 스타일을 생성하는 대신 페이지에 특정 스타일을 적용하는 사용자 연산자로 재정의할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Luerweg, T. (2015년)스택 기반 프로그래밍 패러다임.프로그래밍 언어의 개념– CoPL'15, 33.
  2. ^ Oren Patashnik, Designing BibTeX styles (PDF)[데드링크]