2024-02-20프로그래밍

[번역] 프로그래머를 위한 카테고리 이론 - 4. 크라이슬리 카테고리

우리는 지금까지 타입과 순수 함수들을 카테고리로 모델링하는 방법을 살펴봤다. 앞서 필자는 카테고리 이론에서 사이드 이펙트나 순수하지 않은 함수를 모델링하는 방법이 있다고 이야기했었는데, 어떠한 실행과정을 추적하거나 로깅하는 함수를 예시로 들어 이 방법에 대해 한번 살펴보도록 하자.

우리가 명령형 언어를 사용하여 무언가를 구현할 때는 일반적으로 전역 상태를 선언하고 변경해가며 구현하게 된다.

string logger;
bool negate(bool b) {
     logger += "Not so! ";
     return !b;
}

이 함수는 자신의 외부 세계에 선언되어있는 logger를 변경한다는 사이드이펙트를 가지고 있기 때문에 순수함수가 아니다.

모던 프로그래밍의 세계에서는 가급적이면 변경 가능한 전역 상태를 사용하지 않기 위해 노력하는데, 다른 것은 둘째치고 동시성의 복잡성때문에라도 이러한 행위는 최대한 피해야 한다. 아마 독자 여러분도 이런 코드를 라이브러리에 넣고 싶지는 않을 것이라 생각한다.

다행히도 이 함수는 순수함수로 변경될 수 있는 가능성이 있다. 그저 함수에게 logger를 명시적으로 전달하기만 하면 된다. 즉, 함수에 하나의 문자열 인수를 추가함으로써 함수의 출력과 로그가 포함된 문자열을 짝지어볼 수 있는 것이다.

pair<bool, string> negate(bool b, string logger) {
    return make_pair(!b, logger + "Not so! ");
}

이제 이 함수는 사이드 이펙트를 발생시키지 않기 때문에 순수하다. 동일한 인수가 주어졌을 때 항상 동일한 값의 쌍을 출력하며, 이러한 특성으로 인해 필요한 경우에는 메모이제이션 할 수도 있다. 그러나 메모이제이션을 할 경우 이전 값을 토대로 다음 값을 생성한다는 누산적인 로그의 특성으로 인해, 결국은 이 함수가 호출되기까지의 모든 이력을 메모이제이션해야 할 것이다.

negate(true, "It was the best of times. ");
// 또는
negate(true, "It was the worst of times. ");

💡 역주

여기서 작가는 누산적인 연산을 한다는 로그의 특성으로 인해 메모이제이션을 하나마나라는 이야기를 하고 있다. negate 함수는 “이전 로그”를 받아 “Not so! “라는 문자열을 이어붙히는 방식으로 새로운 로그 문자열을 생성하여 반환하는데, 이는 결국 negate 함수가 반환하는 로그 문자열이 negate 함수가 호출되기 이전의 로그 상태의 영향을 받는다는 의미이다.

아무리 negate 함수가 참조 투명성을 보장하는 순수함수라도, 결국 함수의 호출 맥락이라는 것은 상황에 따라 달라질 수 있기 때문에 negate 함수가 반환하는 로그 문자열 또한 매번 달라질 가능성이 크다. 그로 인해 이를 메모이제이션하는 것은 큰 의미가 없어지는 것이다.

이러한 설계는 라이브러리 함수로써 좋은 설계라고 볼 수도 없다. 함수 호출자는 이 함수가 반환하는 로그 문자열을 무시할 수 있으니 출력 형태에 대해서는 큰 문제가 없겠지만, 입력에 대해서는 다르다. 로그가 필요없는 상황에도 매번 호출자가 특정한 로그 문자열을 함수에게 직접 전달해줘야 하기 때문이다.

그렇다면 관심사를 분리하는 방법을 통해 이 함수를 조금 더 편하게 호출할 수 있는 방법은 없을까? 결국 위 예시에서 negate 함수의 주 목적은 인수로 받은 하나의 Boolean 값을 다른 Boolean 값으로 변환하는 것이며, 로깅은 그저 보조적인 역할만 수행한다. 물론 이 로그에 기록되는 메세지가 함수의 목적에 특화되어 있기는 하지만, 결국 어떠한 메세지를 하나의 로그로 통합하는 작업 자체는 negate 함수의 주 목적과는 별개의 관심사이다. 즉, 우리는 로깅에 대한 관심사를 분리해야 한다.

그렇다면 이런 방법으로 타협을 볼 수 있을 것 같다.

pair<bool, string> negate(bool b) {
    return make_pair(!b, "Not so! ");
}

결국 이 아이디어는 함수가 호출될 때마다 로그를 계속 쌓는다는 컨셉에서 출발한다. 이제 이 아이디어를 어떻게 구현할 수 있을지 알아보기 위해 약간 더 현실적인 예제를 보도록하자.

여기 어떤 문자열을 받아 소문자를 대문자로 변경하는 함수가 있다.

string toUpper(string s) {
    string result;
    int (*toupperp)(int) = &toupper; // toupper is overloaded
    transform(begin(s), end(s), back_inserter(result), toupperp);
    return result;
}

그리고 두번째 함수는 인수로 받은 문자열을 공백을 기준으로 나누어 벡터를 반환한다.

vector<string> toWords(string s) {
    return words(s);
}

toWords 함수의 실제 동작은 words 함수에서 수행된다.

vector<string> words(string s) {
    vector<string> result{""};
    for (auto i = begin(s); i != end(s); ++i)
    {
        if (isspace(*i))
            result.push_back("");
        else
            result.back() += *i;
    }
    return result;
}

우리는 toUpper 함수와 toWords 함수를 수정하여 문자열 메세지를 이 함수들의 반환값과 함께 묶어 표현하고 싶다.

우리는 이제 이 함수들의 반환값을 아름답게 꾸며볼 것이다. 가장 먼저 임의의 타입 A인 값이 첫 번째 요소이고 문자열이 두 번째 요소인 쌍을 캡슐화하는 템플릿 Writer를 정의함으로써 이 문제를 일반화하겠다.

template<class A>
using Writer = pair<A, string>;

이제 Writer를 사용하여 각 함수들을 꾸며줄 차례이다.

Writer<string> toUpper(string s) {
    string result;
    int (*toupperp)(int) = &toupper;
    transform(begin(s), end(s), back_inserter(result), toupperp);
    return make_pair(result, "toUpper ");
}

Writer<vector<string>> toWords(string s) {
    return make_pair(words(s), "toWords ");
}

이제 이 두 함수를 조합하여 문자열을 대문자로 변환하고 공백을 기준으로 나눠주는 함수를 꾸며보자. 바로 이 과정에서 이 작업에 대한 로그를 생성할 것이다.

Writer<vector<string>> process(string s) {
		auto p1 = toUpper(s);
		auto p2 = toWords(p1.first);
		return make_pair(p2.first, p1.second + p2.second);
}

이제 처음의 목표를 달성했다. 각각의 로그를 합치는 것은 이제 더 이상 개별 함수들의 관심사가 아니다. 각 함수들은 자체적으로 자신과 관련된 메세지를 생성할 뿐이고, 이 개별 함수들의 외부에서 이러한 메세지들을 합쳐 더 큰 로그를 만들어낸다.

이제 이러한 스타일로 작성된 거대한 프로그램을 한번 상상해보자. 아마 이러한 패턴을 계속해서 반복하게되면 오류가 발생하기 쉬운 악몽과도 같은 코드가 될 것이다. 하지만 우리는 프로그래머이기 때문에 이런 반복적인 코드를 추상화를 사용하여 우아하게 해결하는 일에 이미 익숙하다. 그러나 이것은 우리가 지금까지 알던 추상화와는 약간 다르다. 바로 함수의 합성이라는 개념 자체를 추상화해야하기 때문이다.

결국 합성이라는 개념은 카테고리 이론의 본질이니, 코드를 더 작성하기 전에 일단 카테고리 이론의 관점에서 이 문제를 한번 분석해보자.

4.1 Writer 카테고리

함수들의 반환 타입을 꾸며 추가 기능을 끼워넣을 수 있다는 아이디어는 우리에게 큰 가치를 가져다준다. 이제 이에 대한 더 많은 예제를 한번 보도록 하자. 대상을 타입으로 가지고 사상은 우리가 꾸며주었던 함수로 가지는 일반적인 카테고리에서부터 시작해보는 것이 좋겠다.

예를 들어 int 타입에서 bool 타입으로 향하는 isEven 함수를 꾸며본다고 생각해보자. 가장 먼저 카테고리의 사상을 우리가 앞서 꾸며보았던 함수로 다시 표현해볼 것이다. 여기서 중요한 점은 이 함수가 비록 pair<bool, string> 타입을 반환한다고 해도 카테고리 내에서는 여전히 int 대상과 bool 대상 사이의 화살표로 간주된다는 것이다.

pair<bool, string> isEven(int n) {
    return make_pair(n % 2 == 0, "isEven ");
}

카테고리 법칙에 의하면 우리는 이 사상을 다른 사상과 합성하여 대상 bool에서 다른 대상으로 향하는 사상을 만들 수 있어야 한다. 여기서는 앞서 정의했던 negate 함수와 합성하는 상황을 한번 보도록 하겠다.

pair<bool, string> negate(bool b) {
    return make_pair(!b, "Not so! ");
}

물론 isEven 함수와 negate 함수는 서로의 입력과 출력 타입이 일치하지 않기 때문에 이 두 개의 사상을 일반적인 함수와 같은 방식으로 합성할 수는 없다. 이 두 사상의 합성은 아래와 같이 표현해줘야 할 것이다.

pair<bool, string> isOdd(int n) {
    pair<bool, string> p1 = isEven(n);
		pair<bool, string> p2 = negate(p1.first);
		return make_pair(p2.first, p1.second + p2.second);
}

이 카테고리에서 두 개의 사상을 합성하는 과정은 다음과 같다.

첫 번째 사상에 해당하는 함수를 실행시킨다. 위 예시에서는 isEven(n)에 해당한다.
첫 번째 함수가 반환한 값의 쌍에서 첫 번째 요소를 추출하고, 이 요소를 두 번째 사상에 해당하는 함수에 전달한다. 위 예시에서는 negate(p1.first)에 해당한다.
첫 번째 사상과 두 번째 사상이 반환한 로그 문자열, 즉 각 함수가 반환한 쌍에서 두 번째 요소를 추출하여 직접 연결해준다.
위 과정을 통해 얻어낸 값과 연결한 로그 문자열을 사용하여 새로운 쌍을 만들어 반환한다. 위 예시에서는 make_pair(p2.first, p1.second + p2.second)에 해당한다.

만약 이 과정을 C++의 고차함수로 추상화하려면 이 카테고리가 가진 세 개의 대상을 타입 변수로 표현한 템플릿을 사용해야한다. 그리고 결과값과 로그 문자열 쌍을 반환하는 두 개의 함수를 가져와 합성하고, 마지막으로 새로운 쌍을 만드는 함수를 반환하면 된다.

template<class A, class B, class C>

function<Writer<C>(A)> compose(function<Writer<B>(A)> m1,
                               function<Writer<C>(B)> m2)
{
		return [m1, m2](A x) {
				auto p1 = m1(x);
				auto p2 = m2(p1.first);
				return make_pair(p2.first, p1.second + p2.second);
		};
}

여기까지 왔으면 이제 거의 끝났다. 이제 이 템플릿을 사용하여 원래 우리가 합성하려고 했던 toUpper 함수와 toWords 함수의 합성을 구현할 수 있다.

Writer<vector<string>> process(string s) {
		return compose<string, string, vector<string>>(toUpper, toWords)(s);
}

하지만 아직도 compose 템플릿에 타입을 전달하는 과정이 번거로워 보인다. 이는 C++14 호환 컴파일러에서 지원하는 반환 타입 추론 기능을 지원하는 람다 함수를 사용함으로써 해결해볼 수 있다. (아래 코드의 작성자는 Eric Niebler이다.)

auto const compose = [](auto m1, auto m2) {
		return [m1, m2](auto x) {
				auto p1 = m1(x);
				auto p2 = m2(p1.first);
				return make_pair(p2.first, p1.second + p2.second);
		};
};

이제 타입 추론을 지원하도록 정의된 compose 함수를 사용하여 함수를 더 간단하게 합성해보자.

Writer<vector<string>> process(string s) {
		return compose(toUpper, toWords)(s);
}

아직 끝난 것이 아니다. 우리는 지금까지 카테고리 내 사상의 합성만 정의한 것이고 아직 항등 사상에 대한 것은 정의하지 않았다. 이 항등 사상은 일반적인 항등 함수와는 약간 다르다. 이들은 타입 A로부터 다시 타입 A로 돌아가는 사상이기 때문에 아래와 같은 타입 선언을 가질 것이다.

Writer<A> identity(A);

이 항등 사상은 합성에 대한 항등원처럼 작동해야한다. 우리가 정의해놓은 로직의 합성 과정에 의하면 이 항등 사상은 자신이 인수로 받은 값을 변경하지도 않고, 로그에는 빈 문자열만 기록하는 방식으로 정의해야 할 것 같다.

template<class A> Writer<A> identity(A x) {
    return make_pair(x, "");
}

이렇게 정의한 카테고리는 카테고리가 지켜야하는 모든 조건들을 만족하고 있다. 특히 이 카테고리의 합성은 명확하게 결합법칙을 만족하고 있다. 각 함수들이 반환하는 값의 쌍 중 첫 번째 요소만 보면 일반적인 함수의 합성으로 바라볼 수 있으며, 이 연산은 결합법칙을 만족한다. 또한 두 번째 요소인 로그 문자열에 대한 연산은 그저 문자열의 연결일 뿐이니 이 또한 결합법칙을 만족한다.

여기서 영리한 독자라면 우리가 이 구조를 문자열 모노이드 뿐 아니라 어떤 모노이드에던 일반화해서 적용할 수 있다는 사실을 알아차렸을 것이다. compose 함수에서 + 연산자 대신 mappend를, 그리고 identity 함수에서는 ""라는 값 대신에 mempty를 사용하기만 하면 된다.

반드시 문자열을 다룰 때에만 한해서 로깅을 한다는 법은 없다. 좋은 라이브러리 작성자는 라이브러리가 동작하는 데 필요한 최소한의 제약 조건을 식별할 수 있어야 한다. 우리가 만든 로깅 라이브러리의 유일한 요구 사항은 그저 로그라는 개념이 모노이드적인 특성을 가져야 한다는 것이다.

4.2 하스켈의 Writer

앞서 구현했던 것들을 Haskell에서는 조금 더 간결하게 작성할 수 있고 컴파일러로부터 더 많은 도움을 받을 수 있기도 하다.

일단 Writer 타입을 정의하는 것부터 시작해보자.

type Writer a = (a, String)

여기서는 단순히 타입 별칭(Type Alias)을 정의하고 있으며, 이것은 C++의 typedef 또는 using과 동일한 기능이다. Writer 타입은 타입 변수 a를 받아 a 타입과 String 타입의 쌍을 반환한다. 이 문법은 쌍을 의미하는 괄호 안에 두 개의 요소가 존재하고, 이 요소들이 쉼표로 부분되는 최소한의 형태로만 이루어져있다.

이 카테고리에서의 사상은 임의의 타입에서 다른 타입을 매개변수로 가지는 Writer 타입으로 나아가는 함수라고 볼 수 있다.

a -> Writer b

이제 “fish”라고도 불리는 재미있는 중위 연산자(Infix Operator)를 사용하여 합성을 정의할 차례이다.

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)

이 연산자는 두 개의 인수를 받아 합성하는 함수이며, 이 인수들은 합성의 대상이 되는 함수들이고 최종적으로는 합성된 함수를 반환한다. 첫 번째 인수는 (a -> Writer b) 타입, 두 번째 인수는 (b -> Writer c) 타입이며, 최종 반환 결과는 (a -> Writer c) 타입을 가진다.

아래 예시는 m1 이라는 인수와 m2라는 인수를 받았을 때 이 중위 연산자가 어떻게 작동하는지를 보여준다.

m1 >=> m2 = \x ->
    let (y, s1) = m1 x
        (z, s2) = m2 y
    in (z, s1 ++ s2)

연산의 결과는 x라는 하나의 인수를 받는 람다 함수이다. 람다 함수는 역슬래시(\)로 표현할 수 있다. 기억하기 어렵다면 다리를 하나 잃은 그리스 문자 λ(Lambda)라고 생각하자.

let 표현을 사용하면 함수 내의 지역변수를 선언할 수 있다. 여기서 m1 함수의 호출 결과는 (y, s1) 변수에 담기고, 이 변수에서 가져온 y 인자를 사용하여 호출된 m2 함수의 호출 결과는 (z, s2) 변수에 담긴다.

이처럼 Haskell에서는 C++에서 p1.first 같이 접근자를 사용했던 것과는 다르게, (y, s1) = m1 x 처럼 패턴 매칭하여 쌍을 분해하는 방법을 주로 사용한다. 이 외에도 두 언어의 기능 간에는 이렇게 직관적으로 대응해볼 수 있는 관계가 꽤 존재한다.

위 함수의 let 표현식에서 선언된 변수들은 함수 동작의 구현을 의미하는 in절에서 접근할 수 있다. 즉 in절 내부에서 접근한 변수들은 let 표현식 내부에서 선언된 값들이며, 최종적으로 첫 번째 요소는 z 이고, 두 번째 요소는 두 문자열의 연결인 s1 ++ s2로 구성된 쌍을 만들어내고 이쓴 것이다.

이런 합성 외에도 우리의 카테고리 내부에 존재해야하는 항등 사상도 정의를 해야하겠지만 이건 조금 이따 보도록 하겠다. 일단 항등사상은 return 이라고 네이밍하자.

return :: a -> Writer a
return x = (x, "")

자 이제 원래 합성하려고 했던 대상인 upCase 와 toWords 함수의 Haskell 버전을 추가하면 거의 다 완성된다.

upCase :: String -> Writer String
upCase s = (map toUpper s, "upCase ")

toWords :: String -> Writer [String]
toWords s = (words s, "toWords ")

map 함수는 C++의 transform에 해당한다. 이 함수는 문자열 s 에 toUpper 함수를 적용한다. 그리고 words 함수는 표준 Prelude 라이브러리에 이미 정의되어있다.

최종적으로 이 두 함수의 합성은 앞서 정의했던 fish 연산자를 사용하여 간단하게 표현할 수 있다.

process :: String -> Writer [String]
process = upCase >=> toWords

4.3 크라이슬리 카테고리(Kleisli Categories)

사실 이러한 카테고리는 필자가 직접 고안해낸 것이 아니다. 이는 모나드라는 개념에서 기반한 크라이슬리 카테고리(Kleisli Category)의 한 예시이다. 아직 우리가 모나드에 대해 자세히 논의하기에는 조금 이르긴 하지만, 모나드가 어떤 역할을 하는지에 대해서 간략하게 살펴봤다고 생각하면 된다.

크라이슬리 카테고리는 프로그래밍 언어의 타입들을 대상으로 가진다. 그리고 타입 A에서 타입 B로 나아가는 사상은 타입 A에서 특정 “장식(Embellishment)”를 적용하여 B로 나아가는 함수라고 볼 수 있다.

모든 크라이슬리 카테고리는 이러한 사상들을 고유한 방법으로 합성하는 방법을 정의하고, 이러한 합성에 대한 항등 사상 또한 정의할 수 있다. (추후 이 애매한 “장식”이라는 용어가 카테고리의 엔도펑터(Endofunctor)라는 개념을 의미한다는 사실을 설명하겠다.)

이 챕터에서 함수들의 실행 과정을 추적하고 로깅하기 위해 만들었던 Writer 모나드는 순수함수들의 연산 결과에 이펙트를 포함하기 위한 일반적인 매커니즘의 예시이기도 하다.

우리는 이전 챕터에서 프로그래밍 언어에서 bottom을 제외한 일반 타입들과 함수들을 집합으로 구성된 카테고리로 모델링하는 방법에 대해서 알아봤다. 그리고 이번에는 이 모델을 기반으로 함수들의 합성이라는 행위가 단지 한 함수의 출력을 다른 함수의 입력으로 전달하는 것뿐 아니라 조금 더 다양한 기능을 포함할 수 있는 카테고리로 발전시켜보았다.

이제 우리는 함수의 합성을 가지고 놀 때 조금 더 자유로운 아이디어를 표현해볼 수 있게 되었다. 바로 우리가 앞서 알아본 개념들이 지금까지 명령형 언어들이 사이드이펙트를 사용하여 구현해왔던 프로그램에도 표시적 의미론(Denotational Semantics)을 적용할 수 있는 자유를 선물해준 것이다.

4.1 Writer 카테고리

4.2 하스켈의 Writer

4.3 크라이슬리 카테고리(Kleisli Categories)

Evan Moon