2024-01-30프로그래밍

[번역] 프로그래머를 위한 카테고리 이론 - 1. 카테고리: 합성의 본질

카테고리는 놀라울 정도로 단순한 개념이다. 카테고리는 대상과 그 사이를 이어주는 화살표로 구성되기 때문에 그림으로 나타내기도 매우 쉽다. 대상은 원이나 점으로 그리면 되고, 화살표는 그냥 화살표로 그리면 된다. (쉬운 이해를 위해 객체를 돼지 모양으로 그리고 화살표는 폭죽으로 그릴 것이다.)

하지만 카테고리의 본질은 합성(Composition)이다. 취향에 따라서 합성의 본질은 카테고리라고 말할 수도 있겠다. 만약 카테고리 내에 대상 A에서 다른 대상 B로 향하는 화살표와 대상 B에서 다른 대상 C로 향하는 화살표가 존재한다면, 반드시 대상 A에서 대상 C로 향하는 화살표, 즉 A→B와 B→C의 합성이 존재해야한다.

하나의 카테고리에서 A에서 B로 이어지는 화살표와 B에서 C로 이어지는 화살표가 있다면,
반드시 A에서 C로 직접 이어지는 화살표, 즉 A→B 화살표와 A→C 화살표의 합성도 존재해야 한다.
나중에 다시 설명하겠지만 이 다이어그램은 항등 사상이 빠져있기 때문에 완벽한 카테고리는 아니다.

1.1 함수로써의 화살표

벌써부터 너무 추상적이라 잘 이해가 안 가는가? 자 그럼 이제 조금 더 구체적인 이야기를 해보자. 화살표를 사상(Morphisms)이라고 불리는 함수라고 한번 생각해보는 것이다.

자 여기 두 개의 함수 f와 g가 있다. 함수 f는 A 타입의 인자를 받아 B 타입의 값을 반환하며, 함수 g는 B 타입의 인자를 받아 C 타입의 값을 반환한다. 그럼 이제 우리는 함수 f의 결과를 함수 g에 전달하여 이 두 개의 함수를 합성할 수 있다. 우리는 결국 A 타입의 인자를 받아 C 타입의 값을 반환하는 새로운 함수를 정의한 것이다.

수학에서는 이러한 함수들의 합성을 $g\circ f$ 와 같이 함수 사이에 작은 원을 그려 표현하며, 합성된 함수의 실행 순서는 오른쪽에서 왼쪽으로 흘러간다. 아마 Unix의 파이프 표기법이나 F#의 Shevron(>>)에 익숙한 일부 프로그래머들에게는 이게 조금 헷갈릴 수도 있다. 이러한 표기법들은 모두 왼쪽에서 오른쪽으로 진행되기 때문이다.

# Unix의 파이프 표기법
lsof | grep Chrome

그러나 수학과 Haskell에서 함수 합성은 모두 오른쪽에서 왼쪽의 순서로 진행된다. 만약 $g\circ f$ 를 “f 다음에 g”로 읽는다면 앞으로 나오는 설명들을 이해하는데 도움이 될 것이다.

더 명확한 설명을 위해 C 코드를 예시로 들어보겠다. 여기 하나의 A타입의 인자를 받아 B타입의 값을 반환하는 함수 f가 있다.

B f(A a);

그리고 B타입 인자를 받아 C타입의 값을 반환하는 또 다른 함수인 g도 있다.

C g(B b);

이들의 합성은 다음과 같이 나타낼 수 있다.

C g_after_f(A a) {
  return g(f(a));
}

즉, 이렇게 C로 작성된 코드를 통해서도 다시 한번 오른쪽에서 왼쪽으로 진행되며 합성되는 g(f(a));를 확인해볼 수 있다.

C++ 표준 라이브러리에 두 개의 함수를 받아 합성함수를 반환하는 템플릿이 있다면 좋겠지만 그런 템플릿은 존재하지 않는다. 그러면 한번 Haskell로 한번 표현해보면 어떨까?

여기 A를 인자로 받아 B를 반환하는 함수 f가 있다.

f :: A -> B

여기에 이어 B를 인자로 받아 C를 반환하는 함수 g를 선언하겠다.

g :: B -> C

그리고 이 두 함수의 합성 함수는 아래와 같이 나타낼 수 있다.

g.f

이처럼 Haskell에서 함수의 합성에 대한 개념을 간단하게 표현하는 것을 보면, C++에서 직관적인 함수 개념을 표현하지 못하는 것이 당혹스럽기까지 하다. 심지어 Haskell은 유니코드 문자를 사용하여 아래와 같이 합성을 표현하는 기능까지 제공한다.

g◦f

또한 아래와 같이 유니코드 이중 콜론과 화살표 문자도 사용할 수 있다.

f :: A → B

Haskell에서 이중 콜론은 “~의 타입을 가진다”라는 의미이며, 함수 타입은 두 개의 타입 사이에 화살표를 삽입하여 표현한다. 두 개의 함수를 합성하기 위해서는 그 사이에 . 이나 유니코드 ◦ 기호를 사용할 수 있다. 이것이 바로 내가 여러분에게 제공하는 첫 번째 Haskell 수업이다.

1.2 합성의 속성

어떤 카테고리든 상관없이, 합성이라는 개념이 만족시켜야하는 매우 중요한 두 가지 특성이 있다.

1. 합성에는 결합법칙이 성립해야 한다.

만약 세 개의 사상인 f, g, h가 있고 이들이 합성될 수 있다면, 괄호 여부, 위치와 상관없이 항상 같은 결과를 반환해야 한다. 수학 표기법에서는 다음과 같이 표현할 수 있다.

h◦(g◦f) = (h◦g)◦f = h◦g◦f

Haskell에서의 의사(Pseudo) 코드는 다음과 같다.

f :: A -> B
g :: B -> C
h :: C -> D

h.(g.f) == (h.g).f == h.g.f
-- 함수에 대해서는 비교 연산 정의가 없기 때문에 Pseudo 코드라고 이야기 했다.
-- 함수의 결합법칙은 꽤나 당연하고 명확해보이지만, 다른 카테고리에서는 이렇게 명확한 정의가 안 될수도 있다.

2. 모든 대상 A에는 항등의 개념을 가진 화살표가 존재해야 한다.

이 화살표는 해당 대상에서 나와 다시 해당 대상으로 되돌아가는 루프라고 볼 수 있으며, 항등 화살표가 되기 위해서는 이 화살표를 대상 A에서 시작하거나, 또는 대상 A에서 끝나는 어떤 화살표와 합성하더라도 항상 같은 화살표가 나와야 한다. 대상 A에 대한 항등 화살표는 idA(항등사상. identity on A.)이라고 불린다. 만약 f가 A에서 B로 나아가는 경우 수학 표기로는 아래와 같이 표현할 수 있다.

f◦idA = f
idB◦f = f

이를 함수로 다룰 때, 항등 화살표는 받은 인자를 그대로 반환하는 항등 함수로 구현된다. 이러한 특성은 모든 타입에 대해 동일하기 때문에 이 함수는 보편적인 다형성(Universally polymorphic)을 가지고 있다고 볼 수 있다.

C++에서는 아래와 같은 Template으로 정의해볼 수 있겠다.

template<class T> T id(T x) {
  return x;
}

물론 C++에서는 인자의 타입 뿐만 아니라 By reference, By const, By value 등 인자를 전달하는 방식도 함께 고려해야하기 떄문에 실제로는 이렇게 간단하지 않다.

Haskell에서는 Prelude라고 불리는 표준 라이브러리에 항등함수의 정의가 선언되어있고, 그 정의는 다음과 같다.

id :: a -> a
id x = x

이처럼 Haskell에서는 타입을 타입 변수로 대체하기만 하면 되기 때문에 다형성을 만족시키는 함수를 정의하기가 매우 쉬운 편이다. 위 예시에서 주의해야 할 점이 하나 있는데, Haskell에서 구체적인 타입의 이름은 항상 대문자로 시작하고 타입 변수의 이름은 소문자로 시작한다는 것이다. 즉, 위 예시의 a는 타입 변수이며 모든 타입을 의미한다.

Haskell의 함수 정의는 함수 이름 다음에 Formal Paramter가 따라오도록 작성한다. (위 예시에서의 Formal Paramter는 x 하나이다.) Haskell 초보자들에게 이러한 간결함은 익숙하지 않을 수도 있지만 금방 이 표현이 말이 된다는 것은 이해할 수 있을 것이다.

함수형 프로그래밍에서 함수를 정의하는 것과 호출하는 것은 빠질 수 없는 필수요소이므로 관련된 문법을 최소한으로 줄인 것이다. 인수 목록에는 괄호가 없을 뿐만 아니라 인수들 간의 쉼표 조차도 없다. (추후 여러 인수를 가진 다인수 함수를 정의할 때 쉼표가 나올 것이다.)

함수의 본문은 항상 표현식(Expression)이며, 문(Statement)은 존재하지 않는다. 함수의 결과는 바로 이 표현식이며 위 예시에서는 x일 것이다. 이게 바로 나의 두 번째 Haskell 레슨이다.

앞서 언급했던 항등사상에 대한 조건은 Haskell 의사 코드로 다음과 같이 작성해볼 수 있다.

f.id == f
id.f == f

이쯤 되면 아마 “왜 아무런 기능도 없는 항등 함수 같은 개념이 필요한지”에 대한 질문이 나올 수 있다. 하지만 잘 생각해보자. 그러면 우리는 왜 0이라는 숫자에 관심을 가질까? 0은 아무것도 없음을 나타내는 기호이지 않은가? 심지어 고대 로마인들은 0이 없는 수 체계를 가졌지만 그들은 훌륭한 도로와 수로를 건설할 수 있었으며, 그 중 일부는 오늘날까지도 남아있다.

사실 0이나 id와 같은 중립적인 값들은 기호로 이루어진 변수들을 다룰 때 매우 유용하다. 그래서 로마인들은 대수학을 잘 하는 편이 아니었지만, 이미 0이라는 개념에 익숙했던 아랍과 페르시아인들은 대수학을 잘 했다. 어쨌든 항등함수는 고차함수(Higher Ordered Function)의 인수로 사용하거나 반환값으로 사용할 때 매우 편리하며, 이러한 고차함수들은 함수를 일종의 기호로써 바라보고 조작하는 것을 가능하게 해준다. 즉, 함수를 사용한 대수학이 가능해지는 것이다.

요약해보자면, 하나의 카테고리는 대상과 화살표(사상)으로 이루어져 있다. 이러한 화살표들은 합성이 가능하며, 이 합성에는 결합법칙이 성립되어야 한다. 모든 대상들은 항등화살표(항등사상)을 가지고 있으며 이는 합성에 대한 항등원 역할을 한다.

1.3 합성은 프로그래밍의 본질이다.

함수형 프로그래머들은 상당히 독특한 방식으로 문제에 접근한다. 이들은 가장 먼저 철학적인 질문을 던지며 접근을 시작하는데, 예를 들어 인터렉티브 프로그램을 만들어야 한다면 가장 먼저 “상호작용(Interactive)란 무엇인가?”라는 질문을 던지는 식이다.

콘웨이의 생명 게임(Conway’s Game of Life)을 구현할 때는 아마 인생의 의미에 대해 생각할지도 모르겠다. 그렇다면 이러한 맥락에 따라 나는 이런 질문을 던져보고자 한다.

“프로그래밍이란 무엇인가?”

가장 기본적인 수준에서 이야기해보자면 프로그래밍은 결국 컴퓨터에게 어떠한 행위를 하기 위한 명령을 내리는 것이다. “메모리 주소 x가 가리키는 내용을 EAX 레지스터에 더해라”처럼 말이다.

그러나 우리가 어셈블리어로 프로그래밍을 할 때조차도 우리가 컴퓨터에게 내리는 명령들은 이것보다는 좀 더 많은 의미를 가지고 있다. 우리는 매우 크고 복잡한 문제를 풀기 위해 컴퓨터를 사용하며, 애초에 그 정도 수준의 문제가 아니었다면 컴퓨터를 사용하지도 않았을 것이다.

그렇다면 우리는 문제들을 어떻게 해결하는가? 우선 우리는 큰 하나의 문제를 작은 여러 개의 문제들로 쪼갠다. 그래도 여전히 이 문제가 너무 크다면 이를 다시 더 작은 문제들로 쪼개고, 계속 이 과정을 계속 반복하며, 최종적으로 우리는 이러한 작은 문제들을 해결할 수 있는 코드를 작성한다.

그리고 바로 이때 프로그래밍의 본질이 나타난다. 바로 작은 문제들을 해결하는 코드 조각들을 합성하여 더 큰 문제에 대한 해결책을 만들어낸다는 것이다. 만약 문제를 쪼갤 수만 있고 이들을 다시 합칠 수 없다면 애초에 문제를 분할해서 해결한다는 의미도 없었을 것이다.

이러한 계층적인 분해와 재조립 과정은 컴퓨터가 우리에게 강제한 사고방식이 아니며, 이는 결국 인간의 사고력에 대한 한계를 반영한 것이다. 우리의 뇌는 한 번에 처리할 수 있는 개념의 수가 제한적이다. 심리학에서 많이 인용되는 논문 중 하나인 “The Magical Number Seven, Plus or Minus Two”에서는 우리가 한 번에 7±2개의 정보 청크(Chunk)만을 기억할 수 있다고 이야기하고 있다.

물론 인간의 단기기억 능력에 대한 개념들과 주장들은 시간이 지남에 따라 조금씩 변하기는 하지만, 인간의 단기기억 능력이 제한적이라는 사실 하나만큼은 변하지 않는다. 결국 우리는 너무 많은 객체들이 버무려져있는 스파게티 코드를 처리할 수 없다는 것이다.

우리는 단지 잘 설계된 프로그램이 멋있어 보이기 때문에 설계를 하는 것이 아니라, 제대로 설계를 하지 않으며 우리의 뇌가 코드를 효율적으로 읽기 어렵기 때문에 하는 것이다. 우리는 종종 어떤 코드를 보고 우아하다거나 아름답다고 이야기하지만, 이런 표현들은 결국 우리의 제한된 두뇌를 사용하여 이 코드를 이해하기가 쉽다는 것을 의미한다. 즉, 우아한 코드는 우리의 뇌가 처리할 수 있는 적절한 크기, 그리고 적절한 개수의 청크들을 만들어내는 것이라고 볼 수 있다.

그렇다면 프로그램을 구성하는 데에 있어 적합한 청크는 무엇일까? 일단 청크의 면적은 청크의 부피보다 느리게 증가해야 한다. (나는 이 비유를 좋아하는데, 기하학적 대상의 면적이 길이의 제곱에 비례하여 증가한다는 직관 때문이다. 길이의 세제곱에 비례해서 증가하는 부피보다는 느린 속도로 증가한다.)

여기서 면적이라는 것은 우리가 하나의 청크를 합성하는 데에 필요한 정보이며, 부피는 우리가 청크를 구현하는 데에 필요한 정보이다. 즉, 하나의 청크를 구현하고 나면 그 구현의 세부 정보는 모두 잊어버리고 다른 청크와의 상호작용에만 집중할 수 있도록 하자는 것이다.

객체지향 프로그래밍에서의 면적은 클래스 선언이나 추상 인터페이스이지만, 함수형 프로그래밍에서는 함수의 선언이라고 볼 수 있다. (조금 단순화해서 설명했지만, 결국 이게 핵심이다.)

카테고리 이론은 각 대상의 내부를 살피는 것을 적극적으로 막기 때문에 극단적인 예시라고 볼 수도 있다. 카테고리 이론에서의 대상은 굉장히 추상적인 객체이다.

어떤 대상에 대해서 알 수 있는 것은 그저 다른 대상과의 관계, 즉 화살표를 사용하여 어떤 식으로 연결되어있는지 뿐이다. 이는 인터넷 검색 엔진이 서로 연결되어있는 링크를 분석하여 각 웹사이트들의 순위를 매기는 방식과 동일하다. 객체지향 프로그래밍에서의 이상적인 객체는 추상적인 인터페이스(면적에 대한 특성만 가지고 부피가 없는 녀석)를 통해서만 볼 수 있으며, 메소드는 카테고리 내 화살표의 역할을 수행한다. 만약 객체를 다른 객체와 합성하기 위해 객체의 구현을 까봐야 하는 순간 이 프로그래밍 패러다임의 장점은 사라지게 된다.

원문 보기

👉 Category Theory for Programmers