컴퓨팅 기술의 원형 탐험, Part 5: 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션(2)

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

연재순서
1회(2008년 3월): 간단한 레지스터 머신에서 시작해 보기
2회(2008년 4월): 작은 아이디어가 만들어낸 큰 차이
3회(2008년 5월): 폰 노이만과 프로그램 내장식 컴퓨터
4회(2008년 6월): 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션(1)
5회(2008년 7월): 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션(2)

컨티뉴에이션 패싱 스타일

지난번에는 컨티뉴에이션(continuation)을 설명했다. 컨티뉴에이션 패싱 스타일(continuation passing style)의 재귀(recursion)라고 부르는 방법이다. 중요한 개념이기 때문에 약간의 설명을 덧붙이겠다. 이 방법이 스택을 사용하는 방법과 다른 점은 스택을 사용하는 방법이 중간 계산값을 저장하는 반면 컨티뉴에이션은 함수와 계산값을 같이 건넨다는 점이 다르다. 예제를 들지는 않겠지만 더 정교한 계산이 가능하다.

지난 회 예제에서 함수 fact는 컨티뉴에이션 함수인 answer에 값을 전해주는 역할을 한다. 결국 나중에 일을 처리할 함수는 answer다. 지난 회 예제의 긴 식에서 answer는 람다 함수 (lambda(x) x)다. 그러니까 받은 값이 무엇이든 그 값을 그대로 되돌리는 함수이고 이 answer에 적용할 값을 건네준 것이다. answer는 끝에서 계산된 값을 그대로 되돌린다. 이제 원래 예제를 생각해보고 설명을 덧붙이자.

(define fact (lambda n c)
		(if (= n c 1 )
			(fact (- n 1)
				(lambda (a) (c (* n a)))))))

마지막 식의 a는 결국 길어진 식을 인자로 받는다. 이 간단한 식에서 컨티뉴에이션 c는 변하지 않으며 n은 계속 감소한다. 자꾸 길어지는 식은 결국 앞으로 계산할 식이 늘어나는 것이니 늘어나는 식을 받는 람다 함수는 n을 a에 곱하고 함수 c에 적용한다. (c (* n a)) 부분이 계속 늘어난다. 별것 아니지만 지금까지의 방법과 다른 것은 사실이다. 실행 문맥이 전해진 것이다.

다음과 같이 간략히 설명할 수 있다. 앞의 fact에서 n이 0이면 c에 1을 적용한다.

(c 1)

n이 0이 아니면 fact는 (fact (- n 1) (lambda (a) (c (* n a))))를 계산한다. 그러니까 n에서 1을 뺀 값과 새로운 람다 함수를 부른다. 그러면 함수의 정의에서 fact (lambda (n c)...)의 n에는 (- n 1)이, c에는 (lambda (a) (c (* n a)))가 주어진다. 물론 (lambda(a) (…로 시작하는 c는 계속 길어진다. 그러다가 (lambda (a) (…에 적용할 값이 주어지면 계산이 일어나면서 줄어든다. 위 예제에서는 c에 1을 적용하는 경우다. 그러면 이번 예제의 c는 (lambda (x) x)로 정했으므로 1을 되돌린다. 그리고 기다란 람다식이 계산을 일으키며 줄어든다. 스택이 늘어난 대신 람다식의 중첩(nesting)이 일어났다.

이 방법이 컨티뉴에이션을 전달하는 재귀의 예제다. 조금 생소하지만 강력한 패러다임이다. 함수형 언어의 표기법과 람다 함수의 생소함이 독자에게 낯선 느낌을 줄 뿐이다. 아무튼 독자들이 재귀와 스택으로 만들어진 예제들로만 생각할 필요는 없다는 것이 중요하다. 중요한 내용은 계산의 컨트롤을 전달하는 일과 접근 방식이다. 컨트롤은 다른 함수를 부르는 것으로 전해진다. Hewitt이 말한 액터(actor)의 역할과 같은 것이다. 이것이 가장 중요한 아이디어라고 스틸과 서스만은 말하고 있다.

다시 한번 소스코드를 열심히 들여다본 독자들이 모든 것을 이해하지는 않았더라도 컨티뉴에이션이 어떤 것인지는 대략 알게 되었다고 가정한다면 이제 다시 다음과 같은 내용을 생각할 수 있겠다.

일단 fact의 내부에서는 어떤 요소도 리턴값을 되돌리지 않았다. 리턴값을 되돌린 것은 컨티뉴에이션 answer다. 이전 예제에서 마지막 문장 (answer 6)이 값을 되돌린다. answer는 (lambda (x) x) 말고도 여러 가지가 가능하다. 이를테면 (fact 3 (lambda (x) print (x)))가 될 수도 있다. (fact 3 (lambda (x) sqrt (x)))를 (sqrt ((fact 3 (lambda (x) x))) 대신 사용할 수 있다. 두 사용법의 차이는 컨트롤을 전달하는 접근 방식이다.

CPS(Continuation Passing Style)에서 생각한다면 스택과 함수의 리턴값에 익숙한 관행을 바꾸어 생각하는 접근이 몇 가지 더 있다.

우선 앞의 예제에서 =, -, *는 값을 되돌리는 프리미티브를 사용했다. 그러나 이것은 프리미티브의 특성이다. 컨티뉴에이션을 사용하는 새로운 프리미티브를 만들면 프로그램의 스타일을 바꿀 수 있다. =, -, *의 새로운 구현을 ==, --, **처럼 표기하자. 이것들의 마지막 요소는 컨티뉴에이션이다. ==는 두 개의 컨티뉴에이션을 받아 조건이 참이면 앞의 컨티뉴에이션을, 나머지 경우는 두 번째 컨티뉴에이션을 부른다.

이런 프리미티브가 구현된다면 앞의 fact를 아래와 같이 표기할 수 있다. 아주 이해하기 쉽고 명료한 코드다(단 프리미티브가 구현되어 있어야 한다).

 
(define fact 
	(lambda (n c)
		(== n 0)
			(lambda () (c 1))
			(lambda () 
				(-- n 1 
					(lambda (m)	
						(fact m (lambda (a) (** a n c)))))))

앞서의 길어지는 람다와 위에서처럼 CPS로 작성한 코드는 같다! 프리미티브를 구현한다면 앞의 예제와 같은 작용을 한다. 설명을 덧붙이면 이 예제에서는 팩토리얼 계산에서 값을 되돌리는 함수 적용이 없다. 모두 다른 함수를 호출할 뿐이다. 의도한 스타일이 더 명확해 보인다!(프리미티브 구현은 Lambda: The Ultimate Declarative의 뒷부분에 적고 있다)

아마추어인 이유로 인터넷이 스승인 필자는 처음에 위키백과에 나오는 CPS와 컨티뉴에이션을 잘 이해하지 못했다. 사실 두 개의 글이 잘 요약되기는 했으나 좀처럼 이해할 수가 없었다. 약간의 이해라도 제공한 문헌은 사실 오리지널 람다 페이퍼였다. 그나마 반나절 동안 fact 코드를 들여다 보고서야 간신히 이해했다. 앞의 CPS 버전의 fact를 위키백과에 나오는 예제들과 비교해 보면 독자들의 이해가 조금 쉬워질 것으로 보인다.

CPS를 사용하면 프로그래머의 프로그램 컨트롤에 대한 통제력이 증가하지만 반면에 확실하게 돌아가도록 신경을 써야 한다는 전제 조건이 붙는다. 여러 가지 고려해야 할 조건이 있기 때문이며 프로그래머는 이를 모두 고려해야 한다.

우선 컨티뉴에이션을 사용하기는 하지만 명료하지 않은 방식으로 사용하는 경우를 예로 들어보자. 이 예제는 Kent Dybvig의 책에 있는 예제다(R. Kent Dybvig의 The Scheme Programming Language 2판 3.4절에 나온다.)

 
(letrec ((f (lambda (x) (cons 'a x)))
         (g (lambda (x) (cons 'b (f x))))
         (h (lambda (x) (g (cons 'c x)))))

코드에서 h를 계산하면 g가 계산되고 g는 어쩔 수 없이 f를 계산해야 한다. 결국 위 식은 다음과 같이 계산된다.

 
  (cons 'd (h '()))) --> (d b a c) 

위의 식을 CPS 스타일로 바꾸면 다음과 같다.

 
(letrec ((f (lambda (x k) (k (cons 'a x))))
         (g (lambda (x k)
              (f x (lambda (v) (k (cons 'b v))))))
         (h (lambda (x k) (g (cons 'c x) k))))

  (h '() (lambda (v) (cons 'd v)))) 

프로그램에 대한 통제가 증가하며 같은 결과가 나온다. 위의 식에서 k는 컨티뉴에이션이다.

CPS는 사실상 goto와 마찬가지 역할을 하며 함수형 언어의 goto처럼 보인다. 함수에 전달할 값들을 잘 지정할 수 있으면 어셈블리어나 포트란으로도 같은 일을 할 수 있다. 필요한 것은 (계산할 함수의 번지, 계산에 필요한 값)이다. 그러니 jump와 본질적으로 다를 것이 없다. 실제로 goto와 람다는 모두 컨트롤을 불러 일으키는 것뿐이다. 표기법이 다를 뿐이다. 필자가 서스만과 스틸의 오리지널 람다 페이퍼를 보고 경탄한 부분은 컨트롤의 전이에 대해 명쾌히 설명한 부분이다. 많은 생각을 불러일으키는 부분으로 우리가 알고 있는 프로그램의 요소들과 람다를 비교하여 설명했다.

위키백과의 CPS에는 자바의 스윙 UI 사용과 비교했으며 필자는 유닉스 커널에 있는 컨티뉴에이션을 예로 들었다. 전통적인 과거의 유닉스 커널은 중첩된 시스템 콜을 가지고 스택을 중심으로 프로시저 호출을 하듯 작업을 처리했으며 스택은 종종 한없이 커지곤 했다. MS-DOS의 경우에는 인터럽트처럼 사용하는 시스템 콜로 운영체계를 돌렸다. 어떤 부분은 중첩된 스택이 불리한 경우도 있다. Richard P. Draves는 Control Transfer in Operating System Kernels라는 글에서 이것들의 장단점과 실제 사례를 분석했다. 널리 인용되는 글이니 한번 읽어 보아도 좋을 것이다.

실제로 컨티뉴에이션은 신기한 개념이 아니다. 어떤 언어를 쓰건 계산할 식과 계산할 값을 주고 이것을 처리할 함수나 다른 처리 장치를 지정하는 것이다. 어셈블리나 C 프로그램에도 컨티뉴에이션과 비슷한 일들을 하는 코드들이 있다. 컴파일러 구현에도 사용된다.

Call/CC(Call-With-Current-Continuation)

CPS를 통해 컨티뉴에이션을 설명했다. 별다른 내용은 아니었다. 이제 컨티뉴에이션에 대해 어느 정도 이해했으니 call/cc를 설명할 때가 되었다. 상당히 중요하지만 별로 다루지 않는 내용이었다. 필자 역시 정확한 문헌 부족으로 몇 개를 이어 모아서 이해할 수밖에 없었다.

우선 SICP에 나오는 컨티뉴에이션 예제를 생각해보자. SICP에서는 4.3.3의 amb 실행기 구현에서 나온다. amb는 비결정적인 실행기의 구성요소다. 이 실행기를 수행하다 보면 답이 나오는 경우도 있고 계산을 하지 못하는 경우도 있다. 실행기는 계산의 결과값이 나오면 그 값을 가지고 success continuation을, 실패하면 failure continuation을 부른다(번역판 SICP는 컨티뉴에이션을 ‘다음 할 일’이나 ‘할 일’이라고 번역했는데 필자도 이후로는 이 용어를 사용하겠다). 값을 얻는 데 성공한 다음 할 일은 이 값으로 계산을 이어나가는 것이고 계산 때에는 실패 시 할 일도 넘겨준다. 뒤에 이어지는 계산 과정이 막다른 길에 이르면 실패 시 할 일의 프로시저를 불러온다. 실패한 할 일의 역할은 다른 길을 찾아 계산이 이어지도록 하는 것이다. 결국 amb의 계산 과정 자체가 하나의 트리 구조를 이룬다고 볼 수 있는데 여러 대안 중 먼저 찾아낸 값으로 계산을 이어나가는 구조다.

설명은 장황하지만 앞에서 말한 == 같은 함수와 구조가 비슷하다고 생각하면 된다. 이를테면 (== (answer_exist?) success-continuation failure-continuation)처럼 생각할 수 있다.

amb는 한 예이고 여러 인공지능 문제는 답을 얻어내기 위한 선택의 트리 구조를 가지고 있다. 선택의 트리를 조작하기 위한 여러 가지 기법이 전통적인 인공지능의 문제라고 해도 과언이 아니다.

선택의 가지를 고르면서 어느 경로가 더 이상 답이 없다는 사실을 알았을 때 이런 프로그램들이 할 일은 다른 대안을 찾기 위해 바로 앞의 갈림길로 돌아가는 것이다. 만약 여기서도 찾지 못하면 그 앞의 갈림길로 돌아간다. 이때 아래의 선택 가지에서 변수값 지정이나 여타 상태 변화가 일어난다면 계산은 완전히 다르게 된다. 따라서 선택의 갈림길에서 할 일은 올바른 계산을 위해 원래 상태까지도 되돌려 놓아야 한다. 프롤로그처럼 backtrack이 하나의 프로그램 구성요소인 언어에서는 더 중요한 문제다(여담이지만 Paradigms of Artificial Intelligence Programming은 책의 1/3 정도를 리스프로 프롤로그를 만드는 데 할애했다는 비평이 있을 정도로 중요한 문제다. 저자인 Peter Norvig은 아주 중요하다고 생각했다).

쉬운 일처럼 보이지만 실제로 어떤 루프에서 빠져 나오는 일은 쉬운 것이 아니다. 리스프뿐만 아니라 C나 자바로 짠 프로그램에서도 쉬운 것이 아니다. 여러 개의 중첩된 do 루프에서 goto를 사용하지 않고 빠져 나오기도 쉬운 일이 아니다. The C Programming Language에는 우아하게 goto를 사용하는 예제가 있다. 알골도 예외가 아니었다. 길게 중첩된 재귀 트리에서 쉽게 빠져 나오는 뾰족한 방법은 오랜 기간 프로그래머들을 괴롭혔다.

오래된 리스프에서는 throw와 catch를 이용해 프로그램이 루프를 빠져 나왔다. 커먼 리스프에는 goto와 그보다 정교한 매크로들이 이런 역할을 했다. 그러나 매크로 역시 나름대로 어려운 요소가 많았다. 컨티뉴에이션이 하나의 답을 제시했다.

스킴에서는 call-with-current continuation이라는 연산자를 만들어 이런 문제를 해결했다. call/cc를 중요한 제어 구성요소로 사용한 최초의 언어이기도 하다. 위키백과에 나오는 예제는 쉽다기보다는 실제로 가장 간단하게 call/cc의 용례를 보여주는 예다. 코드는 아주 단순하다.

 
(define theContinuation #f)
 
 (define (test)
   (let ((i 0))
     ; call/cc calls its first function argument, passing 
     ; a continuation variable representing this point in
     ; the program as the argument to that function. 
     ;
     ; In this case, the function argument assigns that
     ; continuation to the variable theContinuation. 
     ;
     (call/cc (lambda (k) (set! theContinuation k)))
     ;
     ; The next time theContinuation is called, we start here.
     (set! i (+ i 1))
     i))

중간의 문장 (call/cc (lambda (k) (set! theContinuation k)))가 핵심으로 k는 컨티뉴에이션이다. 이 변수를 theContinuation에 지정한다. 그 다음에 다음과 같은 문장을 입력해 보자.

 
> (test)
1
> (theContinuation)
2
> (theContinuation)
3
> (define anotherContinuation theContinuation)
> (test)
1
> (theContinuation)
2
> (anotherContinuation)
4

중간의 (define anotherContinuation theContinuation)은 theContinuation을anotherContinuation 변수를 만들고 지정한다. 그러면 두 변수는 서로 다른 상태를 갖게 된다. 이것들을 실행(evaluate)하며 서로 다른 상태의 프로그램이 돌아가는 것을 보고 있는 것이 바로 위 예제다.

그렇다면 call/cc는 상태를 저장하는 포인터와 같은 것인가? 현재로서는 그렇다라고 대답할 수밖에 없다. 그렇다면 별것이 아니지 않는가라고 물을 수도 있다. 부분적으로는 그렇다. 그러나 call/cc는 많은 프로그래머들이 이해하느라고 고생한 부분이다. 그리고 다음번 주제다(람다와 컨티뉴에이션의 중요한 주제들을 같이 비교하며 살펴볼 문제다).

call/cc는 어떤 일을 하는 것일까? call/cc는 현재 하는 일(current continuation)을 얻어서 하나의 인자를 갖는 프로시저 p로 건넨다. 위의 예제 (call/cc (lambda (k) (set! theContinuation k)))에서 하나의 인자를 갖는 프로시저 (lambda (k) (set! theContinuation k))로 컨티뉴에이션 k를 건네는 것이다. 프로시저는 이 값을 변수에 지정했다.

그 다음에 프로시저가 k에 대해 어떤 값을 적용하는지에 따라 call/cc는 다르게 반응한다. k에 어떤 값이 적용되면 call/cc가 적용된 컨티뉴에이션은 이 값을 되돌려 받는다. 가장 중요한 내용이다. 프로시저가 k에 값을 적용하지 않으면(결국 k를 사용하지 않으면) 그냥 프로시저가 되돌린 값이 call/cc를 적용한 결과가 된다. 아마 말보다는 예제가 더 쉬울 것이다. Dyvbig의 책에 나오는 예제를 그대로 인용하겠다.

 
(call/cc
  (lambda (k)
    (* 5 4))) ==> 20 

;; k에 아무것도 적용하지 않았다.

(call/cc
  (lambda (k)
    (* 5 (k 4)))) ==> 4 
;; k에 4를 적용하자마자 바로 call/cc로 4를 되돌린다. 

(+ 2
   (call/cc
     (lambda (k)
       (* 5 (k 4))))) ==> 6 
;; 앞서 예제와 같이 되돌린 4에 2를 더했다.
 

쉽지 않은가? 다음번에는 조금 더 어려운 문제들이 기다리고 있다.

위로

mar.gar.in

naver

eolin

del.icio.us

[지난 Special Issue 보기]