컴퓨팅 기술의 원형 탐험, Part 6: 컨티뉴에이션과 클로저

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

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

필자는 지난 2회에 걸쳐 컨티뉴에이션(continuation)을 설명했다. 한번은 CPS(continuation passing style)를 다룬 「Original Lambda Papers」의 내용을, 그 다음은 call/cc(Call with Current Continuation)를 간략하게 소개했다.

프로그램의 진행을 의미하는 ‘다음 할 일(continuation)’은 여러 방법으로 생각할 수 있다. 많은 프로그래머와 학자 들의 머리를 싸매게 했고 그 의미는 여러 번 재발견되었다고 한다. 프로그램의 가장 본질적인 요소는 제어의 흐름(control flow)이고 제어는 어디에선가 계속되어야 한다. 그러니 제어 흐름에 대해 여러 가지로 생각할 수 있고 사람들이 새로운 생각을 갖게 되면 그때마다 재발견했다고 할 수 있다. 이것은 필자의 생각이 아니라 컴퓨터가 나오면서부터 존재한 오래된 현상이다. 아마 앞으로도 재발견과 발견을 되풀이할 것이다.

필자는 이 부분을 찾아보다가 Hayo Thielecke(컨티뉴에이션을 분류하여 학위를 땄다)라는 사람의 글을 읽게 되었다. 글은 「Continuation, functions and jumps」(http://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf)라는 제목으로 공개되어 있다. 복잡하긴 하지만 직관적인 요약본으로 전부를 이해하기는 어려워도 어느 정도 전반적인 윤곽을 제공한다. 이 글에서 Thielecke는 C 언어의 예를 들어 컨티뉴에이션의 의미를 설명하고 있다. 아무래도 C의 예문들이 제시하는 의미가 친숙하기 때문에 좋은 예들이다.

기계어를 다루어 본 경험이 있다면 리턴하지 않는 함수(non- returning function)와 인수를 갖는 점프(jumps with arguments)는 구별하기 어려우며 이것들이 ‘계속 할 일’과 관련이 있다는 것을 알 수 있다. 함수에서 return하는 일조차 때로는 jump나 goto로 이루어진다. 스택을 사용하지 않고 몇 개의 필요한 변수만 옮겨 다니는 경우도 많은 것이다(프로세서에 스택 포인터가 없는 경우도 있으니 스택보다는 goto나 jump가 더 보편적인 방법이다). C 언어의 return이 호출되는 경우도 컴파일러는 스택이나 문맥의 정보를 정리하고 goto로 처리하는 경우가 많다.

함수형 언어의 함수 호출 역시 호출 후 아무것도 되돌리지 않고 또 되돌아오지 않는다면 goto와 다를 바 없다. 되돌린다고 해도 goto와 다를 바가 없다. ‘다음 할 일’은 이런 일을 생각해보는 하나의 화두다. 스킴의 CPS는 이렇게 생각해보면 그다지 신기한 것이 아니다. 함수가 언제나 리턴하는 것이 아니라는 생각을 한다면 CPS는 별다른 것이 아니다.

위로

Call with Current Continuation

스킴의 식을 계산하면서 두 가지 요소가 꼭 필요하다. 하나는 무엇을 계산할 것인가와 계산 값으로 무엇을 할 것인가이다.

(if (null? x) (quote ()) (cdr x))의 식에서 (null? x)를 계산하는 경우를 생각해보자. ‘무엇을 계산할 것인가’는 (null? x)이며 이 값에 따라 quote ()나 (cdr x)를 계산한다. ‘계산 값으로 다음에 무엇을 할 것인가’가 다음에 할 일, 바로 컨티뉴에이션이다. 컨티뉴에이션이 계산 결과를 기다린다고 볼 수도 있겠다.

그림 1. Kent Dybvig의 책
: 좋은 설명이 있고 http://www.scheme.com/tspl3/에서 내용을 읽어 볼 수 있다. Chez 스킴의 구현자이기도 한 저자의 설명은 상당히 명확하다.

Dybvig의 책에는 x가 (a b c)의 값을 갖는 경우, 그러니까 (cdr x)를 기다리는 경우를 적고 있다. 이때 (if (null? x) (quote ()) (cdr x))를 평가하면서 값을 기다리는 컨티뉴에이션을 여섯 개로 분류했다. 이것들이 기다리는 값은 다음과 같다.

* (if (null? x) (quote ()) (cdr x))의 값 
* (null? x)의 값
* null?의 값 
* x의 값
* cdr의 값
* 다시 x의 값

별다른 것이 아니다. 계산이 일어나면 그 ‘계속 할 일’이 컨티뉴에이션이다.

스킴은 어떤 식(expression)의 ‘계속’이라도 call/cc를 사용하여 얻어낼 수 있도록 허용한다. call/cc는 강력한 제어 흐름 조절 수단이기도 하다. 어떤 사람들은 지나칠 정도로 강력하며 혼란을 일으킬 소지가 있다고 비평한다.

지난번의 설명과 예제들을 참조하면서 다음과 같은 예제를 한번 생각해 보자.

(define retry #f) 

(define factorial
  (lambda (x)
    (if (= x 0)
        (call/cc (lambda (k) (set! retry k) 1))
        (* x (factorial (- x 1)))))) 

우선 retry를 #f로(false) 정의한다. 그 다음은 일반적인 factorial의 식과 같다. 다만 call/cc가 있다는 사실과 call/cc가 건네준 컨티뉴에이션 k를 retry에 저장한다는 것만 다르다.

(factorial 4)를 입력하면 24가 나온다. 그 과정에서 retry는 현재의 컨티뉴에이션으로 지정된다. 하지만 k에 아무 값도 적용하지 않았으므로 지난번의 예처럼 x가 0인 경우 (= x 0) 1이 되돌려진다. 그러나 현재의 컨티뉴에이션을 저장하는 retry를 얻었다. retry는 모든 문맥을 갖고 있다. 설명은 어렵지만 실제로는 어렵지 않다. 우선 factorial 4를 구해보자.

(factorial 4) -> 24 

이제 factorial 4의 실행 문맥을 그대로 저장하고 있는 retry에 2를 지정하자. retry는 결국 factorial 4를 계산하다가 평상시 같으면 1을 되돌릴 경우의 컨티뉴에이션을 저장하고 있는 것이다. 그러면 retry에 다음과 같이 해 보자.

(retry 1) -> 24
(retry 2) -> 48 

(retry 2)를 입력하면 사실상의 점프가 일어나 원래 실행하던 곳으로 돌아간다. 그러면 원래 실행이 일어나던 컨티뉴에이션에서 k에 2가 적용되며 (call/cc (lambda (k) (set! retry k) 1))은 2를 되돌린다. 2뿐만 아니라 retry에 적용한 어떤 값도 되돌릴 수 있다. 2를 되돌리면 factorial의 식은 x=0의 케이스에서 2를 되돌린다. 그러면 식은 전체 문맥을 복원하며 48이 된다(엉뚱한 값을 적용하면 심각한 에러를 만날 것이다. 그러나 분명히 적용할 수 있다).

이 식을 몇 번만 돌려보면 독자들은 무엇인가를 깨달을 것이고 call/cc의 중요한 측면을 이해한 것이다(Escape Operator). 아주 복잡한 식이라도 retry와 같은 엔트리 포인트를 갖고 있으면 여기에서 문맥을 되돌리며 다시 시작할 수 있다. 재미있기는 하지만 언어라기보다는 운영체제의 문맥 교환이나 디버거에 가깝다. 일반적인 언어에서 보여주는 제한이나 표현 능력과는 커다란 차이가 있다. 변수나 함수 하나조차 실행 도중에 정의할 수 없는 언어와 리스프나 스킴처럼 람다나 컨티뉴에이션이 자유롭게 만들어지는 언어의 표현 능력은 큰 차이가 있다. 다만 프로그래머의 능력과 상상력이 필요하다.

이런 능력은 call/cc를 하나의 강력한 디버거처럼 사용할 수 있게 한다. 위의 retry는 여러 번 호출할 수 있다. retry의 위치도 정해진 것이 아니며 적용하는 값도 자유롭다. 복잡한 식을 적용할 수도 있다. 되돌리는 것이 새로 실행할 람다식이 될 수도 있는 것이다. 비슷한 예를 하나 더 적어보자.

(define return #f) 
  
 (+ 1 (call/cc 
        (lambda (k) 
          (set! return k) 
          1)))  

이 식은 처음에는 2를 되돌린다. call/cc 내부의 식이 정상으로 종료되어 1이 되돌려져 다시 1에 더해지기 때문이다. 하지만 전의 예제와 마찬가지로 return이 현재의 컨티뉴에이션을 갖고 있다. 그래서 여기에 값을 적용하면 원래 식이 다시 평가된다. 적용된 값에 1을 더한다. 그래서 (return 12) ==> 13처럼 된다.

이 일의 의미는 외부에서 내부의 계산에 다시 들어간 것이라고 말할 수 있다(re-entered the computation from outside). 그래서 계산은 여러 가지로 다시 평가해 볼 수 있다. 혼란을 일으킬 수 있지만 강력한 통제 수단이다.

아주 게으른 예제도 있다.

(define return #f) 

(call/cc 
        (lambda (k) 
          (set! return k) 
          ))  

필자가 만들어본 예인데 이 예제는 아무 일도 하지 않고 return만 정의하고 지정한다. 그러면 (return (* 3 4)) => 12처럼 사용할 수 있고 일종의 인터프리터나 마찬가지다. 실제로 일어난 일은 람다식을 저장된 컨티뉴에이션에 적용하며 되돌린 것뿐이다.

지난번의 예제들이 call/cc는 무엇이든지 되돌린다는 사실에 중점을 두었다면 이번 예제는 컨티뉴에이션을 저장하여 다시 제어를 되돌린다는 점이 다르다.

독자들은 이제 스킴의 R5RS에 나오는 call/cc를 봐도 별로 어렵지 않게 느껴질 것이다. 복잡한 예제가 많지만 사실은 간단한 요소들로 구성된 것이다. 그래서 스킴을 조금만 사용해본 독자들이라면 위키백과에 나오는 간단한 예제(http://en.wikipedia.org/wiki/Call-with-current-continuation에 나오는 generate digit 문제)를 풀어보는 것으로 조금 더 이해를 넓힐 수 있겠다. 쉽기도 하고 어렵기도 한 예제가 널려 있다. 풀어보고 이해하는 것은 관심 있는 사람들의 몫이다.

call/cc가 다른 함수형 언어에 많이 도입된 요즘은 필자의 설명이 별다를 것은 없으며 구현마다 난이도와 중요성이 다르지만, 설명에 열을 올린 의미를 찾는다면 컨티뉴에이션의 역사적인 맥락과 도입 과정을 설명한 것에서 찾고 싶다. 관심 있는 독자들은 스킴의 R5RS나 다른 문헌을 본다면 방향 감각 형성에 도움이 될 것으로 기대한다.

위로

Closure

SICP의 한국어판이 나오면서 책의 연습문제 풀이와 질문이 인터넷에 많이 올라오고 있다. 이해와 관심이 늘어나고 있다. 책을 열심히 읽는 것도 좋지만 필자는 통찰력을 강화하기 위해 다른 자료들을 읽어보는 것도 좋다고 생각한다. 그 자료 중 SICP보다 먼저 나온 「Original Lambda Papers」도 있다. 제럴드 서스만(Gerald Sussman)이 가이 스틸(Guy Lewis Steele, Jr.)과 함께 작성한 글 묶음이다. 스킴이 나오게 된 이유와 저변에 깔린 미니멀리즘을 이해하는 데 필요하다(특히 「Scheme: An Interpreter for Extended Lambda Calculus」, 「Lambda: The Ultimate Imperative」, 「Lambda: The Ultimate Declarative」).

스킴은 그 이전의 리스프보다 람다의 해석과 적용을 명확하게 하고 또 확장한 것이다. 언어의 구성요소가 단순해진 대신 람다로 과거의 리스프 변종들의 구성요소를 대체할 수 있다는 것을 보여 주었다. 그 중 하나가 리스프에서 람다식의 표현 방법이다. 우선 데이터와 함수의 구별이 없다. 표현 능력이나 특성이라고 해도 좋을 것 같다. 데이터의 표현과 제어의 흐름도 별로 다르지 않다. 그러니 어디에서 출발해도 좋을 것이다. 예전에 리스프에 대한 글을 처음 쓰기 시작하면서 모든 것이 리스트라고 했으니 리스트의 구조부터 출발하자.

1, 2, 3을 원소로 갖는 리스트는 (1 2 3)이라고 하며 cons 셀로 구성된다. 이 리스트를 만드는 방법은 cons 연산을 이용하는 것이다. cons 연산은 두 개의 원소를 받아 리스트를 리턴한다. 우선 cons (3, ())으로 리스트를 만들고 이 리스트와 2를 cons 연산하고 다시 이 결과를 1과 cons 연산한다.

결과적으로 (cons 1 (cons 2 (cons 3 nil)))을 계산하여 (1 . (2 . (3 . nil)))을 만든다. 큰 리스트는 작은 리스트로부터 만들어진다. 이렇게 보면 리스트는 데이터다. 그런데 예전에 액터(actor) 모델을 들고 나왔던 Hewitt가 cons에 대한 코드를 만든 적이 있다(오리지널 예제를 스킴으로 옮긴 것이다).

(define cons_new
	(lambda (a b) 
		(lambda (m)
			(if (eq? m 'first? ) a
				(if (eq? m 'rest? ) b 
					(if (eq? m 'list?) 'yes 
						(error 'unrecognized message )))))))

이렇게 정의한 cons_new는 일종의 객체와 비슷한 것을 만들어낸다. 값 2, 3을 갖고 있는 함수를 만들어낸다. 그리고 car와 같은 역할을 하는 first, cdr과 같은 역할을 하는 rest 함수를 정의한다. 객체의 메서드와 비슷한 역할을 한다. 예를 들면 다음과 같이 입력해 보자.

 
==>(cons_new 2 3)
#[closure arglist=(m) 148eca0]

화면에 closure라는 용어가 나타났다.

 
==> ((cons_new 2 3) 'first?)
2

==> (cons_new (cons_new 2 3) 4)  
#[closure arglist=(m) 148a3a0]

==> ((cons_new (cons_new 2 3) 4)  'rest?)
4

==> ((cons_new (cons_new 2 3) 4)  'first?)
#[closure arglist=(m) 1492030]

끝의 두 개의 예는 우리가 알고 있는 리스트와 조금 다르지만 코드를 보면 동작을 이해할 수 있다. 몇 가지 근소한 차이점을 빼면 람다로 구현한 함수로 구성한 리스트와 일반적인 데이터로서의 리스트는 구별하기 힘들다.

액터 모델은 이미 이전 컬럼에서 소개한 적이 있다. 스킴의 「Original Lambda Papers」는 그 자체가 액터 모델에서 출발한다(‘Inspired by ACTORS...’). 액터는 script와 set of acquaintances로 구성된다. 전자는 수행할 코드이고 후자는 다른 액터들을 알고 있는 것이다.

람다가 어떤 환경에서 계산(evaluate)되면 하나의 클로저(closure)가 된다. 위의 예에서 (cons_new 2 3)을 계산하면 새로운 클로저가 생긴다. 클로저 자체는 하나의 함수다. 여기에 메시지를 보내는 것이 ‘rest? 'first? 'list? 같은 인자를 덧붙이는 것이다. 메시지를 보내는(message passing) 방법은 리스프에서는 오랜 역사가 있다. 하지만 클로저를 온전히 구현한 것은 스킴이 처음이었다. 스킴은 지역 변수의 처리가 되어 있지 않던 리스프에 렉시컬 스코프(lexical scope)를 도입했다. 지역 변수는 상태(state)라고도 부른다. SICP의 3장은 이 부분의 설명에 많은 부분을 할애했다. 2장은 메시지 패싱과 데이터 요약에 관한 부분이다. 이미 1장부터 프로시저의 요약 부분에 나타나기 시작한다. 1장 뒷부분에 일등급 프로시저(first class procedure)의 조건이라는 권리와 특권을 다음과 같이 적고 있다.

프로시저는:

• 변수의 값이 될 수 있다.
• 프로시저 인자로 사용 가능하다.
• 프로시저의 결과가 될 수 있다.
• 데이터 구조 속에 집어넣을 수 있다.

람다는 무엇이든지 될 수 있다. 데이터가 되는 것은 자연스러운 일이다. 그래서 앞의 리스트의 cons와 같은 자연스러운 처리를 할 수 있다.

SICP에 나오는 예제 중 미분을 푸는 문제가 있다. 함수 f와 dx를 받아 하나의 클로저를 만들게 된다. 내부의 상태 변수가 만들어진다, 그리고 x를 받아 계산한다.

 
(define (derivative f dx)
  (lambda (x) (/ (- (f (+ x dx)) (f x)) dx))) 

우선 함수 f와 dx를 입력하여 내부 변수를 갖는 미분 함수를 정의해보자. 내부 변수를 갖는 프로시저가 만들어진다. 제곱근을 dx = 0.001로 차분하는 프로시저다.

 
(derivative sqrt .001) ==>
#[closure arglist=(x) 1472de0]

이 클로저는 x를 기다린다. 이를테면 7에 대한 계산 값은 다음과 같다.

 
((derivative sqrt .001) 7)==>
0.188975487620979

한 줄짜리 코드로 이 정도 일을 할 수 있다는 것은 놀랍다. 지역 변수에 해당하는 상태는 없어지지 않는다. 이를테면 mysqrt 프로시저를 정의해 보자(SICP의 문제라면 이런 예제들이 1장부터 쏟아져 나온다는 것이다. 책의 매력이기도 하다).

 
(define mysqrt (derivative sqrt .001)) ==>
mysqrt

(mysqrt 7) ==>0.188975487620979
(mysqrt 5) ==> 0.223595618527916

다른 언어들이 이런 능력에 영감을 받지 않을 이유가 없다. 다음 번에 다룰 주제다.

위로

mar.gar.in

naver

eolin

del.icio.us

[지난 Special Issue 보기]