컴퓨팅 기술의 원형 탐험, Part 4: 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션 |
 |
 안윤호 mindengine@freechal.com
필자는 아마추어 리눅스 커널 해커였으며 최근에 팹(Fab)이라는 책을 번역 출간했다. 컴퓨터의 여러 분야에 관심이 많고 컴퓨터와 문화의 인터페이스에도 관심이 많다
2008년 6월 17일
|
|
|
|
연재순서
1회(2008년 3월): 간단한 레지스터 머신에서 시작해 보기
2회(2008년 4월): 작은 아이디어가 만들어낸 큰 차이
3회(2008년 5월): 폰 노이만과 프로그램 내장식 컴퓨터
4회(2008년 6월): 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션
제어의 흐름
이번 회에 적어볼 내용은 제어의 흐름에 관한 것이다. 바로 제어의 전달(control transfer)에 관한 내용으로 독자들은 이미 프로그래밍을 하면서 익숙한 부분이다. 그 중 하나가 ‘계속’(continuation, 이하 컨티뉴에이션)이라는 것인데 제어의 전달에 대해 생각할 화두를 제공하기에는 충분하다. 그래서 독자들의 머리를 크게 아프게 하지 않을 정도의 범위에서 스킴(Scheme)이나 리스프(Lisp) 방식으로 생각거리를 제공하려는 것이다.
우선 다른 곳에서 컨티뉴에이션이 사용되는 것을 살펴보자. 요즘 운영체제는 커널 스레드를 사용한다. 운영체제 커널이 몇 개의 스레드로 운영되면 단일 스레드로 운영될 때에 비해 장점이 있다. 단일 스레드의 커널이 시스템 콜을 호출하다 블록(이를테면 어떤 내부 자원이 이용 가능할 때까지 잠들거나 인터럽트를 기다리며 대기 상태에 빠져 있을 수 있다)이 일어나면 운영체제 전체가 멈추지만 커널 스레드를 몇 개 갖고 있으면 다른 스레드들은 일을 할 수 있다. 커널 스레드는 매우 편리하지만 하나의 스레드마다 많은 자원을 점유해 너무 많은 블록이 일어나면 효율이 떨어진다.
운영체제 교과서들을 보면, 특히 초기 유닉스의 경우 스택에 모든 정보를 저장하고 그대로 잠든다. 이런 스레드가 깨어나면 스택 정보를 바탕으로 다른 일을 모두 처리할 수 있지만 때로는 너무 많은 정보를 스택에 과도하게 저장하는 일도 있다. 어떤 운영체제는 모든 시스템 콜과 예외들을 처리할 때에도 이것들을 하나의 인터럽트처럼 처리한다. 그래서 필요한 정보만을 저장하고 그 다음 작업으로 나아간다. 말이 조금 어려워진 것 같은데 코드를 사용하는 편이 빠를 것 같다. 예전에 Mach에서 유닉스를 위한 절충을 낸 적이 있다. 우선 Mach의 스레드 봉쇄를 위한 thread_block 함수의 구문은 다음과 같다.
<![CDATA[
thread_block (void (*contfn) ())
]]>
|
여기서 contfn()은 스레드가 다음에 수행될 때 호출될 컨티뉴에이션의 함수다. 만약 contfn()이 NULL이면 전형적인 블록이 일어난다.
<![CDATA[
sys_call1 (arg1)
{
... thread_block ()
f2(arg1);
return;
}
f2 (arg1)
{
... return
}
]]>
|
컨티뉴에이션을 사용하는 예제는 블록이 풀리면 그 다음 문장을 수행하지 않는다. 바로 f2를 수행한다.
<![CDATA[
sys_call1 (arg1)
{
... arg1과 다른 상태 정보를 저장한다
… thread_block (f2)
/* 이곳에는 도달하지 않는다. */
}
f2 ()
{
… arg1과 다른 상태 정보를 복원한다.
thread_syscall_return (status);
}
]]>
|
시스템 사용자는 두 개의 시스템 콜을 구분할 수 없다. 둘은 같은 일을 하기 때문이다. syscall1을 부르는 방법마저 같다. f2가 할 일에 대한 정보를 제공할 수만 있으면 둘은 같은 일을 한다. 싱거워 보이긴 하지만 운영체제로 보면 중요한 차이가 있다. 운영체제 관점에서 이런 방식으로 일을 하면 커널 스택이 가벼워진다. 커널 스택에 많은 정보를 저장할 필요가 없으며 제어의 전이는 간단하게 f2로 옮겨지고 할 일을 마치면 시스템 호출로부터 돌아온다.
위의 코드를 보고 독자 중에는 jump나 goto 문을 떠올리는 사람도 있을 것이다. goto만을 사용해도 필요한 정보를 저장할 수만 있다면 같은 일을 할 수 있다. 위의 코드를 조건문과 goto f2로 바꿀 수도 있다. 컨티뉴에이션과 관련된 글들 역시 goto와 관련이 있다고 말한다. 함수(functional) 버전의 goto라고들 말한다. 제어는 컨티뉴에이션을 전달하면서 옮겨진다.
이것은 적당한 시점에 필요한 정보를 메모지에 적어 다른 사람에게 일을 맡기는 일상 생활의 업무들과 같다. 필요한 것은 메모지를 받을 사람과 메모지에 계속할 일을 적는 작업이다.
다시 보는 액터
예전 '해커 문화의 뿌리를 찾아서 Part 4: 액터와 람다'에서 필자는 액터 모델을 이야기했다. 어느 날 칼 휴이트가 람다와는 관련이 없어 보이는 액터 모델이라는 이론을 들고 나왔다(Carl Hewitt, Peter Bishop, Richard Steiger(1973). 「A Universal Modular Actor Formalism for Artificial Intelligence」). 람다가 하나의 계산 형태인 것처럼 액터 역시 형식이며 모델이다. 이 모델에서는 ‘세상의 모든 것은 액터’라는 개념을 채택했다. 마치 객체지향 프로그래밍에서 모든 것이 객체이며 리스프에서는 모든 것이 리스트인 것과 같다.
액터는 객체보다 더 동시적인 모델이었다. 액터는 물리적인 세상을 추상화하려는 시도에서 나왔다(반면 람다는 논리적인 모형으로부터 나왔다). 물리적인 시스템에서 중력이나 전기장은 다른 요소들과 직접적, 동시적으로 영향을 받는다. 액터는 이러한 동시적 작용을 위한 메시지를 보내는 모델을 만들고자 했다. 액터는 컴퓨터상의 존재로 메시지를 받으면 다음과 같은 일을 동시적으로 만들어낼 수 있다.
* 다른 액터에 한정된 개수의 메시지를 보낼 수 있다.
* 유한한 개수의 액터를 만들어낼 수 있다.
* 다른 액터가 받을 메시지에 수반될 행동(behavior)을 지정할 수 있다.
* 이런 일들이 동시적으로 진행되는 데 있어 미리 정해진 순서는 없다.
통신은 비동기적이며 메시지를 보내는 액터는 메시지가 다 수신되기를 기다리지 않는다. 메시지 수신자는 주소로 확인되며 우편주소라고 부른다. 그래서 액터는 주소를 갖고 있는 액터들에 한해 통신할 수 있다. 주소는 수신하면서 알아낼 수도 있고 자신이 만든 액터의 주소일 수도 있다. 요약하면 액터 모델은 액터들 사이의 동시적 계산, 액터의 동적인 생성, 메시지에 액터의 주소를 포함시킬 수 있는 것, 그리고 도착 순서의 제한을 받지 않은 비동기적 메시지 전달을 통한 상호작용이 특징이다.
내용을 읽다 보면 액터 모델은 실제 전자우편과 닮았다. 액터 모델은 리턴 값을 전달하는 이야기가 없으며 실제로 계산 값은 메시지를 전달하면서 전해질 수 있다. 그래서 액터 방식으로 계산하는 방법은 함수나 서브루틴을 호출하여 2와 3을 더하여 5를 리턴 받는 것이 아니다. 이를테면 다른 액터에 3이라는 값을 보내면서 여기에 2를 더할 것을 요구하는 메시지와 함께 전송한다. 그러면 더하기를 지시 받은 다른 액터는 자신이 계산을 하든가, 다른 액터에게 더 필요한 작업을 요구할 수 있다. 이메일로 지시사항과 필요한 자료를 보내 일을 처리하는 방식을 확장하는 것과 마찬가지다. 메시지를 여러 번 보내고 받다 보면 복잡한 일도 처리할 수 있다.
휴이트의 액터는 람다 계산, 스몰토크(Smalltalk), 시뮬라(Simula)의 영향을 받았다. 이들은 동시에 휴이트의 영향을 받았다. 모두 액터가 중요한 모델이라고 인정했다. 얼핏 보기에는 별다른 것이 없어 보이지만 튜링상을 받을 정도의 인물들이 인정할 정도면 어쩌면 중요한 일일지도 모른다.
액터를 이해하기 위해 서스만과 스틸이 만든 장난감 리스프 언어가 스킴이 되었다. 휴이트와 이야기를 나누던 서스만은 사소한 점 두 가지를 제외하고는 람다와 액터 모델이 거의 일치한다는 것을 알았다. 스틸은 이 내용을 「The History of Scheme」이라는 글에서 요약했다. 람다가 개별적으로 상태 변수를 갖고 서로 값을 주고받으면서 액터의 역할과 같은 일을 할 수 있다는 것을 알았다. 동시성 문제가 완전히 해결된 것은 아니지만 리스프 구조에 큰 변화가 왔고 그 와중에 지난번에 소개한 ‘original lambda papers’라는 것들이 나왔다. 그래서 람다라는 것은 개념으로부터 계산상의 실체가 되었다.
별다른 내용이 아닌 것 같지만 프로시저나 함수들, 액터, 객체 그리고 람다 객체들이 메시지를 주고받는 패턴으로 컴퓨터의 제어 구조를 결정한다는 간단하면서도 심오한 결론에 도달한다. 사실 조금만 파고들어도 복잡한 측면들이 나타난다. 일부 객체지향 언어에서 메시지는 객체를 통제하는 거의 유일한 수단이다. 만약 객체가 메시지에 반응한다면 그 객체는 메시지에 대한 메서드(method)를 갖고 있는 것이다. 객체지향 언어보다 먼저 나타난 구조적 프로그래밍에서 메시지를 보내는 방법은 함수 호출이다. 그 이전에는 포트란이나 베이직처럼 직접 goto(jump)하는 방법이 있었다. 프로그램이 제어를 전달하는 방법에서 jump는 나쁜 방법이 아니다. 많은 문헌에서 컨티뉴에이션(continuation)이라고 부르는 방법도 제어와 메시지를 전하는 방법이다. 스택을 쓰지 않아도 컨티뉴에이션으로 해결할 수 있고 파이썬(stackless python이 도전했던 문제다)이나 그 외 몇 가지 언어에서는 이미 시험대에 오른 문제이기도 하다. 차이가 있다면 일의 종류나 알고리즘에 따라 얼마만큼 우아하고 추상적으로 표현할 수 있느냐가 관건이다. 중요한 문제이기 때문에 한번 리스프나 스킴 방식으로 생각해 볼 때가 되었다.
제3의 방법, 컨티뉴에이션
SICP 책에는 나와 있지 않으나 original lambda paper에 나오는 컨티뉴에이션 예제가 있다. 독자들은 Call with Current Continuation을 생각하겠지만 원래 예제는 중간 계산값을 저장하거나 꺼내는 스택을 이용하지 않고 어떤 람다 함수에 계산 값을 보내어 일을 시킨다는 의미였다. 서스만과 스틸이 스킴을 이용하여 풀어낸 원래 문제는 팩토리얼을 구하는 문제였다. 팩토리얼이라고 하면 독자들은 다음에 나오는 식을 기억할 것이다. 책이건 필자의 설명이건 몇 번이나 보아온 선형 재귀(linear recursion) 예제다.
<![CDATA[
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
]]>
|
다음 그림은 (factorial 6)을 구하는 경우의 중간 계산을 보여준다.
그리고 독자들은 다음 식도 기억할 것이다. 이터레이션(iteration) 문제다.
<![CDATA[
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))]]>
|
이 식을 풀면 다음과 같은 중간 계산을 보여준다.
그런데 제3의 방법도 있다. 컨티뉴에이션을 이용하는 방법이다. 서스만과 스틸의 장난감 언어에서 구현한 예제다. 식은 매우 간단하다(출처는 Scheme: An Interpreter for Extended Lambda Calculus의 앞부분이다. 이 문서는 ‘inspired by actors’라는 문구로 시작한다). Hewitt이 발견한 방법으로 적용한 것이다.
<![CDATA[
(define fact
(lambda (n c)
(if (= n 0) (c 1)
(fact (- n 1)
(lambda (a) (c (* n a)))))))
]]>
|
얼핏 보기에는 이터레이션과 같다. 그러나 이 식은 컨티뉴에이션을 사용한다. 저장되는 것은 프로그램 수행에 필요한 정보이며 계산의 중간 값이 아니다.
(fact 3 answer)라는 식을 입력하였을 때 위의 식은 컨티뉴에이션인 answer에 결과를 적용한다. 이 프로그램을 스킴에서 실행하면 다음과 같이 된다. 컨티뉴에이션 패싱 스타일(continuation passing style)의 원시적인 모습이다. 계산의 중간 과정들을 옮겨본다.
fact 3 answer
<![CDATA[
-->(if (= 3 0) (answer 1)
(fact (-3 1) (lambda (a) (answer (* 3 a)))))
-->(fact (- 3 1) (lambda (a) (answer (* 3 a)))))
-->(fact (2) (lambda (a) (answer (* 3 a)))))
// 람다에 3을 적용한다.
-->(if (= 2 0) (lambda (a) (answer (* 3 a))) 1 )
(fact (- 2 1)
(lambda (a)
( (lambda (a) (answer (* 3 a)))
(* 2 a)))))
// 3이 적용된 람다 함수 자체의 실행 컨텍스트가 c의 값으로 적용되고
// 다시 (* 2 a)가 적용된다.
-->(fact (- 2 1)
(lambda (a)
( (lambda (a) (answer (* 3 a)))
(* 2 a)))))
-->(fact 1
(lambda (a)
( (lambda (a) (answer (* 3 a)))
(* 2 a)))))
-->(if (= 1 0)
( (lambda (a)
( (lambda (a) (answer (* 3 a)))
(* 2 a)))))
1)
(fact - 1 1)
(lambda(a)
((lmbda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
(* 1 a)))))
// c는 계속 길어진다.
-->(fact - 1 1)
(lambda(a)
((lmbda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
(* 1 a)))))
-->(fact 0)
(lambda(a)
((lmbda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
(* 1 a)))))
-->(if (=0 0)
((lambda(a)
((lmbda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
(* 1 a)))
1)
(fact (- 0 1)
......))
// 이제 n=0이 되었으므로 컨티뉴에이션에 1을 적용할 수 있다!
// 기다랗게 만들어진 람다 함수에 1을 적용하면서 계산이 일어난다.
---> ((lambda (a)
((lmbda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
(* 1 a)))
1)
---> ((lambda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
(* 1 1))
--->((lambda (a)
((lambda (a)
(answer (* 3 a)))
(* 2 a)))
1)
---> ((lambda (a)
(answer (* 3 a)))
(* 2 1))
---> ((lambda (a)
(answer (* 3 a)))
2)
--->( answer (* 3 2))
--->( answer 6)
]]>
|
 |
|
이제야 계산이 끝났다. 새로운 방법의 팩토리얼 계산법은 이렇게 끝난 것이다. 괄호가 한두 개 빠지거나 더해졌을지는 모르지만 컨티뉴에이션을 전달하여 문제를 푸는 방식의 기본적인 개념은 어떤 람다에게 값을 전해주는 것뿐이다. fact가 한 일은 아무것도 없다. fact는 이터레이션처럼 동작했고 마지막에는 (fact n c)의 컨티뉴에이션 c에게 n=0인 경우에 1을 적용(apply)했을 뿐이다. 위에 적은 식이 팩토리얼의 재귀나 이터레이션보다 복잡한 것도 없다. 결국 모든 치환과 적용이 일어나면 answer에게 값이 전달된다.
실제의 answer는 어떤 함수일까? 결과가 적용되는 가장 간단한 함수 answer는 자기가 받은 값을 되돌리는 (lambda (x) x)다. 그렇다면 (fact 3 (lambda (x) x))는 6을 되돌린다.
조금 싱겁겠지만 실행 문맥 자체를 적용하는 새로운 계산법이 등장한 것이다. 복잡하고 중요한 문맥을 되돌릴 수도 있으며 아주 복잡한 계산도 할 수 있다. 실제로 컴파일러 내부에서는 이런 방법을 적용할 수 있다. 문맥을 전달하면서 복잡한 제어 구조를 명시적인 식으로 만들어 낼 수도 있다. 계산식을 만들어 내는 것은 소스코드를 새로 쓰는 것과 다르지 않다. 컨티뉴에이션에 대해서는 생각할 거리가 많은 것이다.
다음 이야기인 CPS(continuation passing style)와 call/cc(call with current continuation)는 이보다 조금 더 복잡하기는 해도 컨티뉴에이션에 대한 가장 기본적인 부분은 이번 글에서 다룬 셈이다.
이 문서 북마킹 하기
 [지난 Special Issue 보기]
|
