컴퓨팅 기술의 원형 탐험, Part 8: 제어 흐름의 패턴

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

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

필자는 가끔씩 명료한 알고리즘을 수많은 괄호로 바꾸어 놓는 리스프의 식에 아연실색하곤 한다. 명료한 알고리즘도 괄호에 둘러싸이면 (특히 머리가 잘 돌아가지 않을 때에는) 어려운 문제로 둔갑한다. 이런 때는 인터프리터 기계가 아니라는 사실 정도로 위안을 삼을 수밖에 없다. 그러나 가끔 이런 괄호의 벽을 구성하는 제어 흐름을 생각해야 할 필요가 있다. 나무가 아닌 숲을 생각해 보는 것과 비슷하다.

지난번 다룬 call/cc와 컨티뉴에이션은 알고리즘이 괄호의 벽을 빠져나가고 들어오는 중요한 방법이라고 할 수 있다. SICP에서는 자세히 다루지 않았지만 스킴에서는 중요한 주제다. 책의 저자 서스만과 그의 학생이자 동료나 다름 없던 가이 스틸은 오리지널 람다 페이퍼, 특히 「Lambda the Ultimate Imperative」에서 제어 흐름을 집중적으로 다뤘다(많은 통찰을 얻을 수 있으니 읽기를 권한다). 생각해볼 주제가 많은 글이다.

프로그램의 제어를 전달하는 요소는 몇 가지로 나누어 살펴 볼 수 있다.

• 시퀀셜 블록
• goto
• if ~ then ~ else
• while ~ do 같은 루프
• exit

시퀀셜 블록

이런 요소들에 대한 명령형 언어의 코드와 람다 식을 비교해 보자. 먼저 명령 여러 개를 처리하는 시퀀셜 블록부터 시작한다. 가장 흔한 코드를 예로 들어 보자. 여기서 s1 등은 문(statement)이다.

begin 
	s1;
	s2;
	s3;
end

아니면 C 언어의 {s1 ; s2 ; s3;} 같이 표현할 수도 있겠다. 코드 블록으로 {s1 ; {s2 ; {s3}}}}처럼 적을 수도 있다. 문장을 이렇게 늘어놓는 것은 일종의 사이드 이펙트를 바라는 것이다. 계산이 일어나거나 대입이 일어나기를, 그것도 순차적으로 일어나기를 원한다. 너무나 일상적인 코딩이어서 전혀 생소하지 않다. 그러나 스킴 같은 함수형 언어에서는 대입이 일어나는 것을 항상 기대하지는 않는다(a=b ; c=b처럼 대입을 일으키는 일, 프린터나 화면에 출력을 하는 것도 일종의 사이드 이펙트다. 계산이 끝나면 항상 무엇인가 변화가 있다).

s1, s2 같은 것은 스킴이나 리스프에서는 람다 식을 계산하는 작업에 해당한다. 그러니 s1; s2를 순차적으로 계산하는 방법은 다음처럼 생각해 볼 수 있다.

((lambda (dummy) s2 ) s1)

인자의 계산이 먼저 일어나므로 s1을 먼저 계산한다. 그리고 이것을 람다 식에 적용하는 것이다. 람다 식은 변수 dummy를 받은 후 s2를 계산한다. 결과적으로 s1을 먼저 계산하고 s2를 계산한다. 이 식을 (block S1 S2)처럼 만들면 (block S1 S2 … Sn)은 (block S1 (block S2 (... (block Sn-1 block Sn) ...))처럼 적을 수 있겠다. 실제 스킴 코드는 (begin s1 s2 s3 ...)처럼 적는다. 별다른 것은 아니지만 한번 생각해볼 필요가 있다.

블록을 일반화한 (lambda (dummy) (lambda (dummy)(…)s3) s2) s1) 같은 패턴의 적용과 계산을 생각할 수 있다. 적용은 순차적으로 일어나며 무엇인가 사이드 이펙트를 기대한다. 마지막 식 Sn을 계산하면 이 값이 리턴값이며 그 앞의 식들은 사이드 이펙트를 제외한다면 결과에 영향이 없다. 그저 계산만 한 것이다. 그래서 예전의 어떤 순수한 함수형 리스프에서는 순차식을 인정하지 않았다. 모든 람다 함수는 조건 식을 제외하면 하나의 람다 식으로 이루어져야 했다. 람다의 인자도 lambda (a)처럼 하나만 받을 수 있도록 제한하려 했다.

시퀀셜 블록을 설명했으니 조금 도약해서 (define bar (lambda (x y) (f x y))) 같은 식을 생각해 보자. 이 식에 인수를 적용하므로 이를테면 (bar foo etc)는 foo와 etc를 앞서 정의한 bar에 적용한다. 이때 foo와 etc가 람다 식이라면 먼저 foo와 etc를 계산한다. foo를 먼저 etc를 나중에 계산한다. 결과적으로 내부의 (f x y)에 다시 대입되기 이전에 이미 한번 계산이 일어난다. 명시하지는 않았지만 foo와 etc를 미리 계산하는 것은 s1과 s2를 계산하는 패턴과 다르지 않다. 원래는 foo의 계산된 값이 x이고 etc의 계산된 값을 y에 적용하기 위한 계산이었으나 이것들이 함수 호출을 일으키면 일종의 시퀀셜 블록처럼 작용하는 것을 알 수 있다. 사이드 이펙트가 있었다면 당연히 무엇인가 변할 것이다.

이런 혼동을 피하기 위해 람다 식의 인자를 하나로, 내부의 식도 한 줄로 생각하는 것이 더 명확하게 람다 함수를 표현하는 방법일 수도 있다. 실제로 알론조 처치가 생각한 람다 식은 이런 형태였다고 한다. 하지만 수없이 많은 람다를 만들어내며 프로그래밍하기를 좋아하는 프로그래머는 없었다.

시퀀셜 블록을 이제 하나의 순차적 컨티뉴에이션처럼 생각할 수도 있다. s1의 컨티뉴에이션은 s2이며 s2의 컨티뉴에이션은 s3 ... 이런 식으로 생각할 수 있겠다. 람다 계산법을 발명한 처치 역시 컨티뉴에이션에 대해 잘 알았는데(이름을 짓지는 않았지만) 처치는 두 종류의 컨티뉴에이션을 생각했다. 하나는 지금 예로 든 것과 같은 순차적인 것이고 다른 하나는 조건에 따라 분기하는 컨티뉴에이션이다. 예전에 컨티뉴에이션 패싱 스타일(Continuation Passing Style)을 다루면서 든 예들과 비슷하다.

위로

어디로 갈까, goto

시퀀셜 블록 다음으로는 GOTO 문을 대체하는 패턴이다. C 언어에서는 label과 goto를 자주 사용하지는 않지만 가끔씩 쓴다. 먼저 알골의 예를 살펴 보자.

begin 

L1: 	if b1 then goto L2;
	s1;
	if b2 then goto L2;
	s2;
	goto L1;	
L2;	s3;

end;

스킴에서는 letrec을 사용하여 비슷한 일을 할 수 있다. letrec은 람다에 이름을 부여한다는 점에서 define과 비슷하다(letrec에 대해서는 r5rs 문서나 「learning scheme in fixnum days」 같은 문서의 예를 보기 바란다).

(letrec ((L1 (lambda ()
	(if b1 (L2)
		(begin s1
			(if b2 (L2)
				(begin s2 (L1)))))))
	(L2 (lambda () s3)))
	(L1))

이 예제는 L1부터 시작한다. 식의 끝부분에서 (L1)이 초기값으로 지정되었다. 많이 사용하는 letrec을 사용하여 예제를 보여주었지만 예전에 다룬 CPS 예제들과 본질적으로 같은 요소들을 갖고 있다. 공통적인 패턴은 쉽게 파악할 수 있다. 함수 호출은 본질적으로 goto다.

간단한 변수 대입(assignment) 역시 람다로 구현할 수 있다. 2차 방정식의 해를 구하는 예제다. 알골에서는 다음과 같다.

begin 

real a2, sqrtdsc;

a2 := 2*a;
sqrtdisc := sqrt (b ^2 - 4 * a *c );
root1 := (-b + sqrtdisc) / a2;
root2 := (-b - sqrtdisc) / a2;
print (root1);
print (root2);
print (root1 + root2);

end;

이 식을 람다로 만들어볼 수 있다.

((lambda (A2 SQRTDISC)
	((lambda (ROOT1 ROOT2)
		(BLOCK (PRINT ROOT1)
		(display ROOT2)
		(display (+ R00T1 ROOT2))))
	(/ (+ (- B) SQRTDISC) A2)
	(/ (- (- B) SQRTDISC) A2)))
(* 2 A)(SORT (- (^ B 2)(* 4 A C)))) 

특별한 트릭은 아니다. A2와 SQRTDIC을 인자로 받은 다음 ROOT1과 ROOT2에 해당하는 값을 계산하도록 람다 함수에 적용한 것이다. set!이나 다른 사이드 이펙트를 사용하지 않고 람다 식 내부에서 변수 대입처럼 처리했다. 이보다 조금 더 복잡한 예제도 있다. 음이 아닌 정수의 패리티를 구하는 예제다.

begin
	L1: if a = 0 then begin parity := 0; goto L2; end;
	a:=a- 1;
	if a = 0 then begin parity := 1;goto L2; end;
	a := a - 1;
	goto L1;
	L2: print(parity);
end

이 식을 스킴으로 표현하면 다음과 같다.

(letrec 	((L1 (lambda (A PARITY)
			(if (- A 0) (L2 A 0)
				(L3 (- A 1) PARITY))))
		(L3 (lambda (A PARITY)
			(if(- A 0) (L2 A 1)
				(LI (- A 1) PARITY))))
		(L2 (lambda (A PARITY)
			(display PARITY))))

		(L1 A PARITY)) 

사이드 이펙트를 일으키는 것이 아니라 A와 PARITY처럼 변경이 예상되는 변수를 함수의 인자로 전달하는 트릭을 사용했다. 그리고 letrec을 사용했다. 참고로 그림은 이 계산의 흐름도다. 함수는 일종의 GOTO처럼, 다시 말하면 인자를 갖는 GOTO처럼 사용되었다.

글에 나오는 나머지 문제들, 루프나 복합식 예제도 위에서 소개한 예제들을 이용하여 쉽게 바꾸어 볼 수 있다. 예들은 그다지 많지도 복잡하지도 않으니 독자들이 한번 읽어보는 것으로 쉽게 이해할 수 있을 것이다. 글에 나오는 이스케이프 연산자(escape operator)라는 것은 나중에 call/cc로 이름을 바꾸어 발전했고 이 주제 역시 지난 글에서 다루었다.

위로

함수 불러내기(Function Invocation: Ultimate Imperative)

스킴은 처음에는 액터 모델에 집착한 작은 장난감 언어로 시작했다. 액터 모델과의 유사성 내지는 동일성을 따져보고 구현하는 일에 많은 집착을 보였다. 클로저와 액터의 유사성이나 함수 호출에서 메시지 패싱, 제어의 전달이라는 측면을 부각했다. 그전까지는 막연하게 생각하던 것들에 집착하여 파고든 것이다. 필자는 이 내용을 몇 번에 걸쳐 소개했다. 저자들의 주장을 일관하는 내용은 ‘함수 불러내기(invocation) = goto + 메시지 전달’이라는 점이었다. 컨티뉴에이션을 연구하는 사람 중에는 이 관점을 가장 중요한 관찰이었다고 평하는 사람이 많다. 그런데 그 내용은 특별하거나 어려운 것이 아니다. 일반적으로 함수 호출(function call) 시나리오는 다음과 같다.

1. 인자를 미리 계산하여 함수가 필요로 할 것으로 예상되는 장소에 저장한다.
2. 함수를 부르고 돌아올 위치를 저장한다.
3. 함수는 값을 계산하고 이 값을 호출자가 가져갈 수 있는 위치에 저장한다.
4. 함수는 저장된 주소로 돌아가고 이 주소값을 버린다.

이 정도는 독자들도 다 아는 내용이다.

함수 호출을 하나의 goto로 생각한다면 함수가 되돌아갈 위치를 아는 방법은 무엇인지를 생각해 보아야 한다. 저자들은 다음과 같은 함수의 동작을 생각해 보았다고 한다.

(define bar 
	(lambda (x y ) (f (g x) (h y))))

bar는 x y를 인자로 받아 x를 g에 적용하여 계산하고 y를 h에 대해 계산한 다음 이 계산값들을 다시 f에 적용하는 함수로 정의했다.

리스프에서 bar를 계산할 때 인자를 미리 계산하고 돌아갈 위치(보통 스택에 존재한다)를 알 필요가 있다. 그 다음에는 f g h를 불러내야 한다. g와 h를 계산할 때에는 돌아올 주소를 알려주어야 한다. 계산은 진행되어야 하니까. f를 계산할 때에는 돌아올 주소를 알려줄 필요가 없으며 단지 GOTO만으로도 가능하다. 이 값은 이미 bar에 의해 물려받은 것이다. 컨티뉴에이션 관점에서 보았을 때 f의 계산이 끝나면 바로 다음의 식으로 진행해야 한다!

위로

꼬리 전달과 꼬리 재귀

람다 페이퍼의 3부작 글에서 이 주제는 모습을 바꾸어 여러 번 반복된다. 끝의 f에서 일어나는 제어의 전달은 무조건적인 것이며 휴이트의 액터에서도 거론되었던 문제다. 서스만은 이 함수의 끝부분을 꼬리 전달(Tail Transfer)이라 불렀다. 이 전달은 재귀에 있어서도 마찬가지라 꼬리 재귀(Tail Recursion)의 배경이 된다. 스택에 중간의 계산값들이 저장되는 일은 있어도 끝에 가면 아무것도 남지 않는다. 그냥 점프만이 일어난다. 이 주제의 설명은 별다르지는 않지만 결론은 특별하다.

저자들은 PDP-10의 기계어로 동작을 설명한다. 두 종류의 명령을 사용했다. 하나는 PUSHJ foo라는 명령으로 현재 주소를 스택에 PUSH하고 주소 foo로 Jump한다. 다른 하나는 POPJ로 스택에 저장된 주소를 POP하고 이 주소로 Jump한다. 그러면 BAR는 다음과 같이 구성된다. 함수 F G H도 같이 나타냈다. bar를 컴파일하면 다음과 비슷한 코드가 나온다.

BAR:  ... 
	PUSHJ G
BAR1: ...
	PUSHJ H
BAR2:  …
	PUSHJ F

BAR3: POPJ

F:      ...
	POPJ
G:     ...
	POPJ
H:      ...
	POPJ   

맨 처음 BAR를 불렀을 때 스택의 모습은 다음과 같다. BAR를 부른 함수는 돌아올 주소를 저장한다.

 
... , <BAR의 복귀할 주소>

BAR는 G를 먼저 계산해야 하니 BAR는 G를 푸시한다(PUSH G). 그러나 그 전에 돌아올 위치가 주어진다. PUSHJ G 바로 뒤의 BAR1이다. 그러면 스택은 다음과 같다.

 
... , <BAR의 복귀할 주소>, BAR1 

G에서 무엇인가를 한참 계산한 다음 POPJ를 실행하면 BAR1으로 돌아오고 스택은 처음과 같이 변한다.

 
... , <BAR의 복귀할 주소>

이것은 BAR1에서 H로 갈 때에도 마찬가지이며 BAR2에서 어디엔가 저장된 G와 H의 계산 결과를 가지고 F를 계산할 때에도 마찬가지다.

BAR2에서 F에 진입하였을 때 스택의 모습은 다음과 같다(BAR3은 BAR 함수의 끝부분이다).

 
... , <BAR의 복귀할 주소>, BAR3 

원래는 PUSHJ F, F를 계산하고 POPJ를 수행한다. 그러면 BAR3로 돌아오고 이때 스택의 모습은 다음과 같다.

 
... , <BAR의 복귀할 주소> 

이제 BAR3의 POPJ를 수행하면 BAR를 호출한 곳으로 돌아가며 스택은 처음과 같게 된다.

BAR2에서 PUSHJ F를 GOTO F로 대체하면 어떻게 될까? 다음과 같이 된다. BAR3가 저장되지 않는다. 다음은 F에 진입하였을 때 스택의 모습이다.

 
... , <BAR의 복귀할 주소>  

F가 POPJ를 수행하면 원래 BAR의 복귀할 주소로 돌아간다. 둘은 같은 결과를 낸다. 결과적으로는 PUSHJ F ; POPJ 하나가 생략된 스택 사용의 간단한 최적화처럼 보인다. 그러나 중간의 함수 계산과 끝부분의 함수 계산은 균등하지 않다. 둘은 다르게 컴파일되어야 한다.

다른 리스프 컴파일러의 결과를 기계어로 대조해 보아도 비슷한 결과를 만들어 냈다(이 내용은 「Lambda: The Ultimate Declarative」에 자세히 나오니 생략한다). 저자들은 몇 개의 기계에서 나온 결과들을 분석했다. 모두 비슷한 모습을 보였다.

중간 계산값들을 스택이 아니라 다른 레지스터에 저장한다고 하면 다음과 같이 적을 수 있다. 이번에는 PUSHJ를 사용하지 않고 PUSH를 사용했다.

 
BAR: <G에서 사용될 인수들을 레지스터에 설정한다>
	PUSH [BAR1]
	GOTO G
BAR1: <G의 결과를 저장한다>
	<H에서 사용될 인수들을 레지스터에 설정한다>
	PUSH [BAR2]
	GOTO H
BAR3: <F에서 사용될 인수들을 레지스터에 설정한다>
	GOTO F 

스킴 인터프리터를 구현하면서 선택한 설명은 F와 G를 다른 것으로 보는 것이다. G는 다른 함수의 인자가 되는 함수이고 이때는 돌아올 주소를 저장해 주어야 한다(function call이다). 그러나 F는 아니다(function invocation이다). F를 보았을 때 처음부터 아무것도 저장되지 않았고 끝에서는 점프가 일어난다. 이제 일반적인 형태를 다시 들여다 보자.

 
(lambda (A B C …) (F X Y Z ...))

중간의 값들이 어떤 형태를 갖건 F는 앞에서 적은 것처럼 처음부터 스택에 아무것도 갖지 않은 채로 출발했고 끝에서는 GOTO로 끝나며 아무것도 남지 않는다. 서스만은 꼬리 재귀가 아니라 꼬리 전달이 더 좋은 용어일 것이라고 했다.

위로

mar.gar.in

naver

eolin

del.icio.us

[지난 Special Issue 보기]