문제

스택 머신은 현재는 더 이상 사용되지 않는 컴퓨터의 구현 방법 및 구성 중 하나로, 레지스터 대신에 내부적으로 스택을 활용하여 모든 연산을 수행하는 방식으로 동작한다. 스택 머신은 여러 장점을 가졌지만 결과적으로 요새는 물리적으로 이런 구조를 구현한 컴퓨터는 멸종하였고, 대신 내부적으로 레지스터를 사용하여 레지스터 사이의 계산을 정의하는 것이 일반적이다. 하드웨어적으로 스택을 구현하고 지원할 정도의 성능이면 레지스터들을 지원하는 편이 여러 모로 이득이기 때문이다. 이해를 돕기 위해 코드를 살펴 보자. 아래의 평범한 MIPS 어셈블리 코드는 두 상수를 더하기 위해 레지스터에 불러 온 뒤에 덧셈 인스트럭션을 수행하여 결과를 저장한다.

li $r1, 0x10        # $r1 = 0x10
li $r2, 0x20        # $r2 = 0x20
add $r0, $r1, $r2   # $r0 = $r1 + $r2

한편으로 보통의 스택 머신에서는 아래와 같이 계산할 수 있다.

push 0x10   # push 0x10 to the stack
push 0x20   # push 0x20 to the stack
add         # pop two values from the stack, add them and push the result back

이렇듯 서로 다른 계산 방식을 가지게 된다. 그런데, 만약에 우리가 하드웨어가 아닌 소프트웨어를 통해 컴퓨터를 구현한다면 구현의 난이도 측면에서 어떤 방식이 더 쉬울까? 당연히 후자가 그 가상 머신을 위한 컴파일러를 만드는 측면에서도, 인터프리터를 만드는 측면에서도 훨씬 유리하다. 이 외에도 몇 가지 이유로 Java Virtual Machine, CIL 코드(즉, .net 코드) 수행을 위한 VES, Adobe ActionScript의 구동을 위해 쓰이는 ActionScript Virtual Machine 등은 스택 기반의 가상 머신으로 구현되었다.

하여 우리도 아주 간단한 스택 머신을 하나 정의하여 보기로 하자. 우리의 스택 머신은 단 네 가지 인스트럭션을 갖는다.

• push: 외부에서 정수를 입력받아 그 값을 스택에 push한다.
• add: 스택에서 두 값을 꺼내 더하고 결과를 스택에 push한다.
• subtract: 스택에서 두 값을 꺼내 먼저 꺼낸 것에서 나중에 꺼낸 것을 빼고 결과를 스택에 push한다.
• negate: 스택에서 값을 하나 꺼내, -1을 곱한 결과를 스택에 push한다.

예를 들어, 입력으로 [5, 3, 2, 10] 이 순서대로 주어질 때 다음 어셈블리 코드를 수행하고 나면 스택에는 16만이 남게 된다.

push         # [5]
push         # [5, 3]
add          # [8]
push         # [8, 2]
subtract     # [-6]
negate       # [6]
push         # [6, 10]
add          # [16]

이 어셈블리 언어에 대한 인터프리터를 구현하는 것은 전산학과 학부생이라면 누구라도 10분 안에 할 수 있는 일이기 때문에 문제를 조금 더 재미있게 바꿔 보자: 우리의 가상 머신에 대한 어셈블리 코드와 이 코드를 실행시킬 때 입력으로 제공할 수들의 수열이 주어지면, 이 수열의 원소들의 순서를 마음대로 변경하여 스택에 마지막으로 남는 값을 최대화하기 위해서는 어떻게 해야 할까?