스택 머신(Stack Machine)은 컴퓨터과학, 컴퓨터공학 및 프로그래밍 언어 구현 분야에서 널리 알려진 컴퓨터 아키텍처 또는 프로세스 가상 머신의 한 형태이다. 주된 상호 작용이 단기간 존재하는 임시 값을 푸시다운 스택(push-down stack)으로 이동시키거나 스택에서 꺼내는 방식으로 이루어진다. 하드웨어 프로세서의 경우 하드웨어 스택이 사용된다.
개념
스택 머신은 연산을 수행할 때 피연산자를 컴퓨터 레지스터나 메모리 주소에서 직접 가져오는 대신, 스택의 최상단(top)에서 꺼내어(pop) 연산을 수행하고 그 결과를 다시 스택에 넣는(push) 방식을 사용한다. 대부분의 명령어는 피연산자의 위치를 명시할 필요가 없으므로, 명령어가 연산 코드(opcode)만을 포함하는 제로 주소 형식(zero-address format)을 갖는다. 이는 명령어 디코딩을 크게 단순화하는 장점이 있다.
스택 머신은 푸시다운 오토마타(pushdown automata)를 확장한 개념으로, 추가적인 load/store 연산 또는 다중 스택을 지원함으로써 튜링 완전(Turing-complete)하다.
연산 방식
스택 머신에서 산술 연산은 역폴란드 표기법(RPN, Reverse Polish Notation)에 따라 수행된다. 예를 들어, A*(B-C)+(D+E)라는 수식이 있다면 다음과 같은 순서로 연산이 진행된다.
- A를 스택에 push
- B를 스택에 push
- C를 스택에 push
- subtract (B-C 계산, 결과를 스택에 push)
- multiply (A*(B-C) 계산, 결과를 스택에 push)
- D를 스택에 push
- E를 스택에 push
- add (D+E 계산, 결과를 스택에 push)
- add (최종 결과 계산)
각 산술 연산은 스택 최상단의 두 피연산자를 pop하여 연산한 후, 그 결과를 다시 스택에 push한다.
역사 및 구현 사례
스택 머신의 개념은 1961년 로버트 S. 바턴(Robert S. Barton)이 학술 회의에서 처음으로 제시한 것으로 알려져 있다.
하드웨어 스택 머신
- 콘라트 추제(Konrad Zuse)가 설계한 Z4(1945년)는 2단계 스택을 갖추었다.
- 버로우즈 대형 시스템(Burroughs Large Systems) 아키텍처(1961년 이후)
- English Electric KDF9(1964년 첫 납품)는 19단계 깊이의 산술 레지스터 스택과 17단계 깊이의 서브루틴 복귀 주소 스택을 갖추었다.
- UCSD 파스칼 p-머신(Pascal MicroEngine)
- HP 3000, HP FOCUS 마이크로프로세서 기반 시스템
- RTX2000, RTX2010, F21, PSC1000 등 여러 "포스(Forth) 칩"
- 인모스(Inmos) 트랜스퓨터
가상 스택 머신
- JVM(Java Virtual Machine)의 명령어 집합
- WebAssembly 바이트코드
- .NET Framework의 CIL(Common Intermediate Language) 명령어 집합
- 포스(Forth) 프로그래밍 언어
- 어도비 포스트스크립트(PostScript)
- 이더리움의 EVM(Ethereum Virtual Machine)
- CPython 바이트코드 인터프리터
- Ruby YARV 바이트코드 인터프리터
레지스터 머신과의 비교
스택 머신은 일반적으로 레지스터 머신(register machine)과 비교된다. 스택 머신은 코드 밀도가 높고 명령어 디코딩이 단순하다는 장점이 있으나, 실행해야 하는 명령어의 총 개수가 많은 경향이 있다. 레지스터 머신은 일반적으로 동일한 연산을 더 적은 명령어로 수행할 수 있어 하드웨어에서 더 높은 성능을 보이는 경우가 많다.
이 때문에 스택 머신은 하드웨어 구현보다는 구현의 단순성과 이식성 때문에 가상 머신(VM) 구현에 널리 사용된다. 반면 현대의 주류 범용 프로세서는 대부분 레지스터 아키텍처를 채택하고 있다.
참고 사항
스택 머신이라는 용어가 오늘날의 대부분의 컴퓨터가 사용하는 콜 스택(call stack) 및 스택 프레임(stack frame) 구조와 혼동되어서는 안 된다. 대부분의 현대 컴퓨터는 레지스터 아키텍처를 사용하면서도 메모리에 콜 스택을 사용하지만, 이는 표현식 평가를 위해 스택만을 사용하는 순수한 스택 머신을 의미하지 않는다. 스택 머신이라는 용어는 통상적으로 표현식 스택과 스택 전용 산술 명령어를 사용하여 단일 문장의 일부를 평가하는 기계를 가리키는 데 사용된다.
