함수형 프로그래밍 6강 : 시퀀스 자료구조와 병렬성

1강에서 함수형 프로그래밍의 장점중 하나는 코드의 병렬화가 간편해지는것이라고 말했었다.

오늘은 배열과 비슷하지만 병렬화가 더 쉬운 불변(immutable) 자료구조, 시퀀스(sequence)를 알아보자.

불변 자료구조는 저번 강의때 잠깐 설명한 영구적(persistent) 자료구조와 비슷하다. 다만 인터페이스 단계에선 영구적, 구현 단계에선 불변이란 말을 쓴다고 한다.

근데 찾아봐도 더 비슷한 말이 안나오는걸 보면 이 말이 틀렸을 수도 있다. 대충 비슷한 의미로 생각하자.

이번 글에 나오는 코드를 직접 돌려보고 싶다면 여기서 시퀀스 라이브러리를 다운받아서 적용시키자…라고 말하려 했으나, 특정 컴파일러를 필요로 하는 패키지 매니저를 필요로 하는것 같다. MLton이란 컴파일러가 필요하다 해서 다운받으려 했으나 에러가 났고 해결하기엔 굳이? 라는 생각이 들어 그냥 안하기로 했다.

1. 시퀀스

우선 우리가 사용할 시퀀스 자료구조는 임의의 원소에 대해 O(1) 접근이 가능하고 병렬화가 가능하지만 패턴 매칭을 할 수 없고 앞에 원소 추가하는 연산이 O(n)이나 걸린다.

시퀀스가 어떻게 구현되었는지는 생각하지 마라. 인터페이스를 쓰는 이유중 하나는 사용자가 어떻게 구현이 되었는지 신경 쓸 필요가 없다는 것이니까.

인터페이스는 다음과 같다.

signature SEQUENCE = 

sig

    type 'a t 

    type 'a seq = 'a t 

    exception Range of string 

    (* constructing a sequence *)

    val empty : unit -> 'a seq 

    val singleton : 'a -> 'a seq 

    val tabulate : (int -> 'a) -> int -> 'a seq 

    val fromList : 'a lsit -> 'a seq 

    (* Deconstructing a sequence *)

    val nth : 'a seq -> int -> 'a 

    val null : 'a seq -> bool 

    val length : 'a seq -> int 

    val toList : 'a seq -> 'a list 

    val toString : ('a -> string) -> 'a seq -> string 

    val equal : ('a * 'a -> bool) -> 'a seq * 'a seq -> bool 

    (* Simple transformations *)

    val rev : 'a seq -> 'a seq 

    val append : 'a seq * 'a seq -> 'a seq 

    val flatten : 'a seq seq -> 'a seq 

    val cons : 'a -> 'a seq -> 'a seq 

    (* Combinators and higher-order functions *)

    val filter : ('a -> bool) -> 'a seq -> 'a seq 

    val map : ('a -> 'b) -> 'a seq -> 'b seq 

    val reduce : ('a * 'a -> 'a) -> 'a -> 'a seq -> 'a

    val reduce1 : ('a * 'a -> 'a) -> 'a seq -> 'a

    val mapreduce : ('a -> 'b) -> 'b -> ('b * 'b -> 'b) -> 'a seq -> 'b

    val zip : ('a seq * 'b seq) -> ('a * 'b) seq 

    val zipWith : ('a * 'b -> 'c) -> 'a seq * 'b seq -> 'c seq 

    (* Indexing-related functions *)

    val enum : 'a seq -> (int * 'a) seq

    val mapIdx : (int * 'a -> 'b) -> 'a seq -> 'b seq

    val update : ('a seq * (int * 'a)) -> 'a seq 

    val inject : 'a seq * (int * 'a) seq -> 'a seq 

    val subseq : 'a seq -> int * int -> 'a seq 

    val take : 'a seq -> int -> 'a seq 

    val drop : 'a seq -> int -> 'a seq 

    val split : 'a seq -> int -> 'a seq * 'a seq 

    (* Sorting and Searching *)

    val sort : ('a * 'a -> order) -> 'a seq -> a seq 

    val merge : ('a * 'a -> order) -> 'a seq * 'a seq -> 'a seq 

    val search : ('a * 'a -> order) -> 'a -> 'a seq -> int option

    (* ... *)

end

이것 외에도 시퀀스 인터페이스는 정말 다양한 함수를 지원한다. 많다고 놀라지 말자. 대부분은 리스트도 할 수 있는 것들이다.

다만 우리가 알고 있는 리스트 버전의 함수들과 차이점이 있다. 바로 시간복잡도이다. 시퀀스는 병렬화가 가능하기 때문에 시간복잡도가 다르다.

예를 들어 리스트에 담겨있는 정수의 합을 구할때 O(n)보다 빠르게 할 수 없다. 리스트가 x::y::rest의 형태라면 x를 접근하기 전에 y를 접근할 수 없기 때문이다.

하지만 시퀀스는 가능하다! n개의 프로세서가 주어진다면 정수의 합을 O(1)만에 구할 수 있다. 더 나아가 f가 O(1) 걸리는 함수라면 Seq.map f 도 O(1)에 구할 수 있다.

다만 패턴 매칭은 할 수 없다. 아래와 같이 리스트로 간편하게 했던 것들이,

case L of 

  [] => (* A *)

| x::xs => (* B *)

시퀀스로는 다음과 같이 구현해야 한다.

case Seq.length S of

  0 => (* A *)

| _ => 

let

    val (x, xs) = (Seq.nth S 0, Seq.drop S 1)

in

    (* B *)

end

또한 시퀀스의 맨 앞에 원소를 추가하는 연산(cons라고 부른다)이 더 오래 걸린다. 리스트로는 O(1)이였던게 시퀀스에서는 새로운 시퀀스를 만들어야 하므로 O(n)이나 걸린다.

2. 코스트 그래프

시퀀스에 어떤 연산이 있는지 제대로 알아보기 전에 병렬 연산의 시간복잡도를 계산하는 법을 알아보자.

코스트 그래프(cost graph) 라는 개념을 알아볼 것이다.

코스트 그래프는 다음과 같이 재귀적으로 정의된다. 어떤 함수 f의 계산을 나타내는 노드이거나, 코스트 그래프 두개를 순차적으로 결합한 것이거나, 병렬적으로 결합한 것이다.

모든 코스트 그래프는 위에서 아래로 흐르며, 시작과 끝이 있다.

또한 두번째 병렬결합 그림에서 위에서부터 그래프가 두개로 쪼개질때 포크(fork)라고 하고, 다시 선이 한곳에 모일때를 조인(join)이라고 한다. 이건 실제 프로그램이 병렬적으로 일을 나누고 결합할때를 그림으로 나타낸 것이다.

예를 들어 (1 + 2) * (3 + 4)는 다음의 코스트 그래프를 갖는다.

(1+2) 연산과 (3+4)연산은 독립적이니 동시에 병렬적으로 수행할 수 있기 때문이다.

+와 *는 동시에 처리할 수 없다. *를 하려면 +가 끝나야 하기 때문이다.

코스트 그래프는 다음과 같이 시간복잡도로 환산할수도 있다.

W는 work의 약자로 일반적인 의미에서의 시간복잡도를 나타내고, S는 span의 약자로 병렬성이 지원될때의 시간복잡도를 나타낸다.

코스트 그래프 전체의 work는 각 노드의 work의 합이고, 전체의 span은 시작부터 끝까지 가는 경로중 가장 총 span이 높은 경로의 총 span이다.

병렬성이 지원된다면 독립적인 연산을 수행할때 가장 시간이 많이 걸리는 연산만 총 시간복잡도에 추가하면 되기 때문이다.

3. 대표적인 시퀀스 함수

시퀀스 인터페이스의 함수를 다는 설명하지 못하겠고 대신 중요한 몇몇만 알아보자.

i) tabulate

tabulate : (int -> 'a) -> int -> 'a seq

tabulate f n 은 <f 0, f 1, …, f (n - 1)>로 계산된다. 리스트를 나타낼때는 []를 썼는데, 앞으로 시퀀스를 나타낼 때 <>를 쓸 것이다.

예를 들어 tabulate (fn x => x * x) 5 ⇒ <1, 4, 9, 16, 25>이고 tabulate (fn x => 0) 5 ⇒ <0, 0, 0, 0, 0>이다.

tabulate의 코스트 그래프는 다음과 같다.

f i와 f j는 독립적이므로 병렬화 될 수 있다. 따라서 f가 O(1)이면 tabulate f n은 O(n) work이고 O(1) span이다.

ii) nth

nth : 'a seq -> int -> 'a

nth S i 는 S의 i번째 원소이다. i가 길이를 벗어나면 Range 예외가 raise된다.

코스트 그래프는 다음과 같고 O(1) work이고 O(1) span이다.

iii) map

map : ('a -> 'b) -> 'a seq -> 'b seq

map은 고차함수 강의에서 다뤘던것과 똑같이, 주어진 함수 f를 시퀀스의 각 원소에 적용한다.

map은 tabulate와 nth를 이용해 다음과 같이 구현할 수 있다.

fun map f S = tabulate (fn i => f (nth S i)) (length S)

코스트 그래프는 다음과 같다.

n개의 노드로 포크하는건 map과 같지만 그 이후에 (fn i => f (nth S i))를 나타내기 위해 점과 선이 각각 하나씩 더 생겼다. 선이 하나 더 생겨도 O(1)이기 때문에 만약 f이 O(1)이라면 map도 tabulate의 work와 span을 따라가서 O(n) work, O(1) span이다.

iv) reduce

시퀀스에도 fold를 할 수 있을까? fold의 정의를 다시 생각해보자.

x2에 대해 연산을 하려면 먼저 g(x1, z)를 먼저 계산해야 해서 각 g 는 독립적이지 않다! 병렬화할 수 없다는 뜻이다. 하지만 fold에 조금의 조건을 추가해 병렬화가 가능하게 할 수 있다.

fold (op+) 0 [1, 2, 3, 4]를 생각해보자. (1 + (2 + (3 + 4)))로 계산된다.

하지만 이건 (1+2) + (3+4)로 계산할 수 도 있다. 덧셈의 결합법칙(associativity) 덕분이다. 두 괄호는 독립적이므로 병렬화할 수 있다!

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 은 ((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8))로, “토너먼트 형식”으로 계산될 수 있다.

이렇게 하면 log 8 = 3, 세번의 병렬 계산 만에 전체 합을 구할 수 있다.

일반적으로 함수 g: t * t -> t에 대해, x g (y g z) = (x g y) g z라면 g는 결합법칙을 만족한다고 한다. (g는 흔히 쓰던 전위표기법 대신 중위표기법을 썼다.)

이제 fold의 강화판(?)인 reduce를 정의하겠다.

reduce : ('a * 'a -> 'a) -> 'a -> 'a seq -> 'a

g가 결합법칙을 만족한다면, reduce g z S는 foldr g z S의 빠른 버전이다.

코스트 그래프는 다음과 같다.

reduce의 work와 span은 뭘까? g가 몇번 호출되는지 살펴보면 약 n번 호출된다. 따라서 g가 O(1)이라면 reduce의 work는 O(n)이다.

하지만 span은 O(log n)이다. 시작에서 끝까지 가는 경로가 g를 약 log n번 호출하기 때문이다.

v) filter

filter : ('a -> bool) -> 'a seq -> 'a seq

filter p S는 S의 원소 중 p를 만족하는 원소만 담긴 시퀀스를 만든다.

filter의 work와 span은 뭘까? work는 O(n)이란게 보이지만 map처럼 span이 O(1)라고 생각했다면 틀렸다.

우리가 만들 시퀀스의 길이를 사전에 알지 못하기 때문에 쉽게 병렬화할 수 없기 때문이다.

이 강의에서 filter가 어떻게 구현되는지는 다루지 않겠지만, span이 O(log n)이란것만 알고 있자.

정확하진 않지만 대충 다음과 같이 구현된다.

각 원소 x를 p를 만족하는지에 따라 <> 또는 <x> 으로 map한다.
이 시퀀스들을 append를 써서 reduce한다. 이러면 자연스럽게 빈 시퀀스는 “버려진다”.

vi) mapreduce

mapreduce : ('a -> 'b) -> 'b -> ('b * 'b -> 'b) -> 'a seq -> 'b

mapreduce f z g는 g가 결합법칙을 만족한다면

이다.

먼저 f를 시퀀스에 map하고, 바로 다음에 reduce하는걸로 생각하면 된다.

work는 map과 reduce 각각의 work를 합쳐 O(n)이다. span도 마찬가지로 O(log n)이다. 물론 f와 g가 O(1)일때만.

궁금하거나 이해 잘 안되는거 있으면 댓글로 물어보면 내가 아는선에서 최대한 답변해줄테니 많이 물어봐라.

다음에는 지연된 연산(lazy evaluation)을 다뤄보도록 하겠다.

7강 : 지연된 연산, 무한 자료구조, 스트림

8강 : 명령형 프로그래밍

9강(完) : 컴파일러와 프로그램 분석

참고자료 1

참고자료 2

참고자료 3