컴퓨팅 기술의 원형 탐험 Part 1: 간단한 레지스터 머신에서 시작해 보기

안윤호 mindengine@freechal.com 필자는 아마추어 리눅스 커널 해커였으며 최근에 팹(Fab)이라는 책을 번역 출간했다. 컴퓨터의 여러 분야에 관심이 많고 컴퓨터와 문화의 인터페이스에도 관심이 많다. 2008년 3월 18일

연재순서
1회(2008년 3월):간단한 레지스터 머신에서 시작해 보기

지난해 썼던 「해커 문화의 뿌리를 찾아서」에서는 해커와 리스프(LISP) 구현 이야기를 하다가 『괴델, 에셔, 바흐』와 『Society of Mind』라는 책을 소개하는 것으로 매듭지으면서 그 이야기들이 하나의 화두 역할을 하기를 바라는 소망적인 생각을 전했다.

「해커…」의 주제가 된 SICP는 『컴퓨터 프로그램의 구조와 해석』이라는 제목으로 책이 번역, 출판되었으니 관심 있는 독자들은 원서와 같이 읽어보아도 좋을 것이다. 필자는 때로 번역이 참으로 편리함을 주는 수단이라는 생각을 한다. 일정 수준 이상의 번역은 아무래도 술술 읽히는 신비한 능력이 있다. 그래서 번역이 중요하며 책의 번역이 일어나면 읽는 사람도 늘어나며 동시에 관심이 있는 사람도 늘어난다. 책의 내용을 떠나 책 자체가 논의나 토론의 대상이 되기도 한다. 그래서 필자는 SICP 번역이 중요한 의미가 있다고 믿는다.

지난해 연재에서는 시작하면서 「The Root of LISP」라는 글을 재료 삼아 리스프 인터프리터를 만드는 방법을 설명했는데 이는 역사적으로도 리스프 언어의 시작이었다. 매카시는 포트란에서 자극을 받아 람다(lambda) 계산법을 실행하는 방법을 생각하기 시작했고 그 생각이 실제로 구현되었던 것이다.

이 주제가 SICP 4장을 중심으로 한 메타서큘러 계산기(metacircular evaluator)의 실제 골격이다. SICP를 학교에서 가르칠 때 1장에서 3장만 가르치는 관행으로 볼 때 약간 파격적인 구상이나, 반대로 독자들이 다른 접근법을 통해 통찰력을 갖고 리스프를 바라볼 수 있다고 생각해 적어 보았던 것이다. 리스프에 관심이 있는 독자들은 지난 연재 1회와 2회 내용을 (다시) 읽어 보기를 바란다.

이번 연재는 비슷한 주제의 반복이다. 그러나 조금 현실적인 목표를 잡아 잘 다루지 않지만 중요하다고 판단되는 주제들을 생각해 보려 한다. 그 주제들은 레지스터 머신, 상태(state), 컨티뉴에이션(continuation), 클로저(closure) 같은 것들이다. 어려운 것들이라 깊이 들어가지 않고 중요한 주제의 화두와 그림을 제시하고 간단한 설명을 더하는 수준이 될 것이다. 이해가 잘 되지 않아도 너무 걱정할 필요는 없다. 원래 쉬운 주제가 아니기 때문이다. 그러나 이 용어들이 무엇인지 알아둘 필요는 있으며 생각할 거리로만 남겨두어도 된다(교양 과목처럼 생각해도 된다. 교양 과목은 중요한 주제를 다루지만 이를 아주 심각하게 받아들이는 순진한 사람들은 별로 없기 때문이다). SICP 책을 이해하기 위해 필요하기도 하지만 두고두고 생각할 주제가 되기에 충분한 중요성이 있다.

위로

레지스터 머신 단순하게 보기

SICP 5장 제목은 ‘레지스터 기계로 계산하기’다. 책의 지은이들은 이 기계를 설계한 이유가 일종의 신비(mystery)를 풀기 위한 것이라고 말한다. 신비라는 것은 잘 알 수 없는 일들이 일어나는 것이다. 원인과 결과의 인과 관계가 복잡해 보일 때가 그렇다.

이때는 문제들을 단순화해 바라볼 필요가 있다. 지난번의 리스프 계산기(evaluator)는 그 자체가 다른 리스프 위에서 구현된 것으로 자세한 부분은 눈에 보이지 않는다. 그래서 신통하게도 A4 한 장도 안 되는 소스 코드로 매카시의 코드를 구현했다. 그러나 정작 최초의 구현을 맡은 프로그래머는 엄청난 양의 어셈블리 작업에 매달렸다. 하부를 이루는 apply의 마지막 부분들을 모두 손으로 만들어야 했던 것이다. 그러니 마법은 없었다. 신비스럽게 보이는 재귀(recursion)나 apply, eval 모두 마지막에는 기계어로 만든 낮은 레벨의 함수에서 실행되어야 했던 것이다.

신비로운 부분을 없애려면 어셈블리나 기계어로 바꾸는 과정으로 마지막 부분을 설명할 수 있을 것이다. 기계마다 하드웨어가 다르나 본질적인 요소는 실제로 간단하다. 그래서 등장하는 레지스터 기계는 이 계산기를 더 낮은 수준으로 구현하기 위해 만든 가상의 기계다. 몇 가지 기계 요소의 동작을 정의하는 것이 레지스터 기계 설계의 시작이다. 추상적이지만 중요한 부분을 모두 보여주는 편리한 교재이기도 하다.

당연한 것이지만 신기하게 문제를 푸는 정교한 알고리즘도 끝에 가면 수없이 많은 단순한 기계적인 조작의 연속이자 합으로 되어 있다. 독자들은 레지스터 기계를 살펴보는 것으로 반복(iteration)과 재귀의 차이를 알 수 있고 continue 레지스터와 스택(stack)을 이용하는 방법의 차이도 알 수 있다. 기계어를 따로 배우거나 기계어 코드에 정통하지 않아도 핵심 부분을 배우는 데는 지장이 없다. 따라서 레지스터 머신은 좋은 비유이자 모델이다. 조금 더 비유를 하자면 하노이의 탑(tower of hanoi)과 같은 수학적 예제가 있다. 알고리즘을 배우는 시간에 재귀 문제의 모델로 곧잘 등장한다. 복잡하게 보이는 고리 옮기기는 끝에 가서는 단순한 기계적 옮기기로 변한다. 정교한 알고리즘이나 복잡한 프로그램도 끝에 가서는 레지스터나 스택에서 순수하게 기계적인 조작을 하는 단순한 조작으로 변한다. 그렇지 않으면 연산이 일어나지 않는다. 그러니 끝까지 도달하면 신비는 없어지는 셈이다.

SICP 5장은 레지스터 머신을 정의해 밑바닥에서 일어나는 일들을 정의하는 작업과 리스프 언어 구현을 통합하는 작업을 그려보는 큰 그림을 그리고 있다. 어셈블러도 만들고 컴파일러도 만들며 인터프리터와 분석기(analyzer)도 다룬다. 그리고 결국은 언어를 실행하는 하나의 완결된 주제를 다루게 된다. 이른바 대통합인 셈이며 커다란 도전이기도 하다.

5장 시작은 매우 간단한 기계를 생각하면서 시작한다. 레지스터 머신이다. 간단하게 접근할 수 있는 몇 개의 저장소(register)를 사용하는 기본적인 방법을 그려보고 있다. 그림 1은 책의 5.1장에 나오는 GCD(최대공약수)를 구하는 기계의 그림이다. 알고리즘은 a를 b로 나눈 나머지가 0이 될 때까지 같은 작업을 되풀이(반복: iteration)하는 알고리즘을 기계로 구현해 본 것이다(책의 원문은 http://mitpress.mit.edu/sicp/full-text/book/book.html에서 읽어 볼 수 있다).

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
 

GCD 기계는 별다른 것이 없다. 기계는 같은 동작을 되풀이한다. a를 b로 나눈 나머지를 t에 저장하고 이 임시 결과의 값은 b로 옮긴다. b는 a로 이동한다. 반복 동작으로 나머지가 0이 되도록 기계적으로 계산할 따름이다. 나머지가 0이 되면 a가 최대공약수가 되는 알고리즘이다.

기계는 크게 두 가지 요소로 나눌 수 있다. 일종의 설비나 부품과 같은 레지스터 a, b, t와 중간의 데이터 흐름을 제어하는 밸브 역할을 하는 a←b, b←t, t←r 같은 것들로 이들을 데이터패스(data path)라 부른다. 그리고 어디엔가 이들을 제어하는 제어기(controller)가 있다. 그림 2가 제어기의 그림이다. 간단한 플로 차트로 되어 있다. 그림 3은 서스먼과 아벨슨의 강의 동영상 9a의 화면으로 데이터패스와 컨트롤러의 관계를 보여주고 있다. 이 추상적인 기계의 요소들은 모두 정의가 가능하다. 정의된 소스 코드는 쉬운 내용으로 책의 5.1에 나온다. 필자는 이 부분을 다룬 지은이들의 동영상 9a를 한번 보기를 권장한다(동영상을 받을 수 있는 곳은 http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/다).

위로

그림 4는 팩토리얼을 구하기 위한 코드를 구현하고 있다. 팩토리얼 코드는 다음과 같다.

(define (factorial n)
  (if (= n 1)<br />
      1<br />
      (* (factorial (- n 1)) n)))

이 코드를 구현하는 그림에서 앞의 GCD 기계와의 중요한 차이는 스택을 구현한다는 점이다. 스택이 있으면 스택에 데이터 값을 저장할 수도 있으며 저장할 수 있는 값 중에는 컨트롤러가 되돌아올 장소를 저장할 수 있다. 그래서 continue라는 레지스터가 도입되는데 이 레지스터는 goto 명령을 수행하기 위한 장소를 지정하고 저장된 몇 개의 label 사이를 오간다.

GCD와 팩토리얼의 코드는 차이가 거의 없다. 그러나 팩토리얼의 코드는 중간 계산값과 n을 저장해야 하는 문제가 있다. 그래서 데이터패스는 그림 4처럼 조금 복잡하게 변했다. 복잡하게 변하는 이유를 책의 구절을 인용하면 다음과 같다.

장황한 설명처럼 들리지만 기계를 여러 벌 만들면 해결되는 문제다. 그런데 필요한 기계를 여러 벌 만드는 것은 항상 어렵거나 불가능했다. 과거에는 어려운 문제였지만 튜링머신의 아이디어가 나온 이후에는 간단한 기억장치를 이용하는 것으로 문제들을 해결할 수 있다는 것을 알게 되었다.

보통 이런 문제는 스택을 사용하여 해결한다. 스택에 데이터를 저장하고 정확히 되돌릴 수만 있으면 한 벌의 설비(데이터패스)로 많은 계산을 할 수 있기 때문이다. 스택이 무엇인지 모르는 사람은 별로 없겠지만 스택 사용 방법이 쉬운 것은 아니다. 반드시 자료구조로서 스택으로 한정할 것도 아니다. 하지만 필요한 데이터는 어떠한 형태로든 저장되어야 한다(스택은 컴퓨터가 나오고 10년 정도 지난 후 발명되었다).

예제의 팩토리얼 계산은 서브루틴을 풀듯이 해결한다. 이 방법은 제어기가 안에 있는 문제를 풀고 난 다음, 원래 문제를 이어서 풀려고 할 때, 알맞은 명령 위치로 되돌아갈 목적으로 continue 레지스터를 사용한다(continue는 C 언어의 label과 goto라고 생각하면 된다). continue 레지스터에 저장된 엔트리 포인트로 돌아가는 팩토리얼 서브루틴을 만들 수 있다. 서브루틴이 호출될 때마다 n 레지스터와 continue를 저장(아래 소스 코드의 save 명령으로 push와 같다고 생각하면 된다)하고 나중에 값을 되돌릴(소스 코드의 restore로 pop과 같다) 수 있다. 계산의 ‘단계’마다 continue 레지스터를 사용한다. 팩토리얼 서브루틴은 낮은 레벨의 문제를 불러낼 때 그 위치(안에 있는 문제를 막 풀기 시작한 곳)를 새로운 값으로 하여 continue 레지스터에 넣는다. 또한 자신을 호출한 곳으로 돌아가려면 다시 예전 값이 필요하다. 그 예전 값은 스택에 저장되어 있다.

(controller 
   (assign continue (label fact-done)) ; 끝으로 되돌아갈 장소를 지정하는 초기화 
                         
fact-loop 
   (test (op =) (reg n) (const 1)) 
   (branch (label base-case)) 

;;   되도는 계산(recursive call)을 위한 준비작업으로 n과 continue를 저장한다. 
;;   스택에 n과 continue는 계속 쌓인다. 
;;   서브루틴에서 돌아올 때 after-fact에서 계속할 수 있도록 continue를 설정 

   (save continue) 
   (save n) 
   (assign n (op -) (reg n) (const 1)) 
   (assign continue (label after-fact)) 
   (goto (label fact-loop)) 

;;   
;; 

after-fact 
   (restore n) 
   (restore continue) 
   (assign val (op *) (reg n) (reg val))   ; val에 (n - 1)! 할당 
   (goto (reg continue))                   ; 호출한 곳으로 돌아가기 

base-case 
   (assign val (const 1))                  ; 끝에 도달한 경우: 1! = 1 
   (goto (reg continue))                   ; 호출한 곳으로 돌아가기 

fact-done) ; 기계가 fact-done에 이르면 계산은 끝나고 val 레지스터 값이 결과가 된다. 

갑자기 기계어 같은 컨트롤러 코드가 나와서 황당하지만 별다른 것이 아니다. 처음에는 모두 기계어를 썼으니 이런 코드들을 손으로 만들어 보는 것이 당연했을 것이다.

구현 전략은 간단하다. 제어기 시퀀스는 n과 continue에 되도는 계산(recursive call)을 하기 전 값을 저장하고 베이스 케이스인 n=1이 될 때까지 fact-loop 루프를 진행한다. continue와 n 레지스터는 스택에 쌓인다. n=1이 되면 base case에서 val 레지스터에 1을 지정하고 스택에 지정된 continue 위치로 돌아간다(계산이 끝날 때까지는 after-fact로 지정되어 있다). after-fact에서는 계산을 끝내고 난 다음 되돌아가 넣어둔 값을 다시 꺼내도록 한다. 스택을 모두 소비하면 마지막 fact-done으로 가는 구조다(물론 책에 나오는 내용과 다른 구현 방법도 있다). 복잡하게 보이는 내용은 9a의 동영상에 포함되어 있다. 서스만이 칠판에 그리는 내용을 보면 독자들은(영어로 설명하는 장벽을 넘어) 무슨 말을 하려는지 알 수 있을 것이다. 그러니 동영상을 보라!

평범했던 레지스터 기계에 스택 연산을 추가한 팩토리얼 기계를 만들면서 재귀적 계산 방법의 일반적 전략을 살펴볼 수 있다. 책에 나오는 피보나치 수열을 포함하여 더 복잡한 예제들도 비슷한 전략으로 풀어낼 수 있다. 반복이나 재귀나 구현의 차이는 근소하고 스택과 continue 레지스터 사용 전략이 바뀔 뿐이다. 완전히 기계적인 내용이다.

결론적으로 스택이나 레지스터를 잘 조작할 수 있으면 아주 복잡한 문제들도 풀어낼 수 있다. 하부 레벨에서는 단순한 기계적 작업이 더 많아지는 것뿐이다. 기계적으로는 분명히 그렇다. 이 아이디어를 조금 더 확장해 보자. 스택과 continue 레지스터와 비슷한 설비를 갖는 조금 더 복잡한 기계를 만들면 원하는 연산을 수행할 수 있는 범용 처리기가 될 것이다. 우리는 물론 매일 이 기계를 사용하고 있다. 바로 컴퓨터의 프로세서다.

손으로 그려 돌려본 레지스터 머신을 이해했다면 그 다음 행보는 기계의 동작을 수행해보는 것이다. 간단한 레지스터 머신을 시뮬레이트하는 코드는 비교적 쉽게 만들 수 있으며 기계 내부 동작은 투명하게 보인다.

우선 모형 기계(시뮬레이션하려는 기계 부품에 해당하는 데이터 구조)를 만들기 위해 레지스터 기계의 설명(specification)을 사용하는 프로시저가 필요하다. 이 기계를 만들려면 레지스터의 이름을 정의하고 조작들을 정의하며 제어기도 필요하다. 그 형식은 다음과 같다.

(make-machine <register-names><operations><controller>) 

레지스터, 연산, 제어기를 받아 모형 기계를 내놓는다. 그리고 모형 기계를 조작해 실제 기계를 시뮬레이트하는 프로시저들이 필요하다.

(set-register-contents! <machine-model><register-name><value>) 

기계의 시뮬레이트된 레지스터에 값을 넣는다.

(get-resister-contents <machine-model><register-name>) 

기계의 시뮬레이트된 레지스터에서 값을 꺼낸다.

(start <machine-model>)

기계의 제어 시퀀스 시작에서 출발해 시퀀스 끝에 이르면 멈춘다. 정말 단순하다. 나중에 얼마나 복잡해질지 모르게 될 코드의 시작은 이렇게 단순하다. 코끼리를 냉장고에 집어넣는 방법(냉장고 문을 연다 -> 코끼리를 냉장고에 넣는다 -> 냉장고 문을 닫는다)처럼 단순한 느낌이 드는 이 간단한 식을 구현하는 일은 SICP 1장부터 4장까지 설명한 모든 내용의 총체다. 기계를 만드는 make-machine의 와 가 긴 코드로 바뀌면서도 깔끔한 구조를 유지하며 독자들에게 포기하지 않고 생각을 계속할 수 있도록 설명을 이어나가는 것이 SICP의 매력이다.

위로

간단한 프로세서 만들어 보기

글을 쓰면서 느낀 것은 책에는 빠진 과정이 하나 있다는 점이다. 교과 과정이나 지면상 어쩔 수 없겠지만 바로 프로세서 구현이다. 프로세서가 레지스터 머신이라는 사실이 이해돼도 코드로만 적어보면 실감이 나지 않는다. 실제로 간단한 프로세서를 만들어 보는 것이 이해가 더 빠를 것이다. 실감이 나지 않으면 이해의 성취감도 줄어든다.

그래서 궁리 끝에 정말 간단한 프로세서 구현을 설명하는 것이 좋겠다는 생각을 하게 되었다. 일반적으로는 디지털 회로로 구성하는 것을 하드웨어 예제와 코드로 간단히 구현하는 것이 좋을 것으로 생각하고 있다. 간신히 돌아갈 수 있는 프로세서를 C의 유사 코드와 그림으로 설명하려는 시도다. 아마도 긴 시도가 될 것 같다.

소셜 북마크
	mar.gar.in
	Digg
	del.icio.us
	Slashdot

레지스터 머신을 간단하게 설명했지만 수학적인 추상적 기계의 계보는 매우 복잡하다. 관심이 있는 독자는 위키백과의 레지스터 머신을 읽어보는 것도 좋을 것이다.

[지난 Special Issue 보기]