2024-12-25프로그래밍

[번역] 프로그래머를 위한 카테고리 이론 - 11. 선언적 프로그래밍

필자는 이 책의 첫 번째 파트에서 카테고리 이론과 프로그래밍이 모두 합성 가능성(Composability)에 대한 것이라는 주장을 하였다.

프로그래밍에서는 문제를 조금씩 세분화해나가며 다룰 수 있는 세부 수준으로 분해한 다음, 각 하위 문제를 해결하고, 하위 문제의 해결책들을 다시 합성하여 전체 문제를 해결하는 방식을 사용한다.

이를 수행하는 방법에는 크게두 가지 정도가 있다. 하나는 컴퓨터에게 무엇을 해야 하는지 알려주는 방법, 그리고 다른 하나는 어떻게 해야 하는 지를 알려주는 방법이다. 이때 전자는 선언형(Declarative), 후자는 명령형(Imperative)이라고 한다.

이 두 가지 방법의 차이는 가장 기본적인 수준에서도 확인이 가능하다. 먼저 선언적으로 h를 함수 f가 실행된 이후 g를 적용한 합성이라고 정의해보면 이렇게 된다.

h = g.f

혹은 명령적으로 정의해볼 수도 있다. 즉, 먼저 f를 호출하고 그 호출의 결과를 기억한 뒤, 그 결과를 사용해서 다시 g를 호출하는 것이다.

명령형 방식의 프로그램은 일반적으로 시간 순서대로 정렬된 일련의 작업들로 표현된다. 특히 이 방식에서는 명시적으로 g의 호출이 f의 실행이 완료되기 전에는 절대 발생할 수 없음이 표현된다. 그러나 지연 평가(lazy evaluation)와 call-by-need 방식의 인수 전달을 사용하는 언어에서는 실제 실행 순서가 다를 수 있다.

사실, 컴파일러의 최적화 수준에 따라 선언적 코드와 명령적 코드의 실행 방식에는 거의 차이가 없을 수도 있다. 하지만 이 두 가지 방법론은 때로 문제 해결 접근 방식과 결과 코드의 유지보수성 및 테스트 가능성에서 극명하게 다르다.

여기서 중요한 질문은 “우리가 문제를 풀 때 항상 선언적인 접근 방식과 명령적인 접근 방식 중 하나를 선택할 수 있는가? 그리고 만약 선언적인 해결책이 있다면 항상 컴퓨터 코드로 변환할 수 있는 것인가?”이다. 사실 이 질문에 대한 답은 아직 명확하게 나오지 않았으며, 만약 그 답을 찾을 수 있다면 아마 우리 우주에 대한 이해를 혁신적으로 바꿀 수 있을 것이다.

설명을 덧붙이자면, 물리학에서도 이와 유사한 이중성이 존재한다. 이는 심오한 근본 원칙을 가리키거나, 우리의 사고방식에 대해 무언가를 말해주는 것일 수 있다. 리처드 파인만은 자신의 양자 전기역학 연구에서 이 이중성이 영감의 원천이 되었다고 언급한 바 있다.

물리 법칙을 표현하는 데에는 두 가지 방식이 있다. 하나는 국소적(local) 또는 미소적(infinitesimal) 접근 방식을 사용하는 것이다. 이 접근 방식은 먼저 시스템의 작은 근방에서의 상태를 관찰하고, 다음 순간에 그것이 어떻게 변화할 지를 예측한다. 이러한 변화는 보통 미분 방정식을 사용하여 표현되며, 이를 일정 시간 동안 적분하거나 합산하여 최종 결과를 표현한다.

이는 이전 단계의 결과에 의존하는 각각의 작은 단계들을 거쳐 최종 해결책에 도달하는 명령형 사고방식과 유사하다.

실제로 물리적 시스템의 컴퓨터 시뮬레이션은 미분 방정식을 차분 방정식으로 변환하고 이를 반복 실행하는 방식으로 구현하는 경우가 많다. Asteroids 게임에서 우주선이 애니메이션화 되는 방식도 이와 동일하다.

각 시간 단계마다 우주선의 위치는 속도와 시간 델타를 곱하여 계산된 작은 증분을 더해가면서 변경된다. 속도는 다시 가속도에 비례하는 작은 증분을 더해 변경되며, 가속도는 힘을 질량으로 나눈 값이다.

이것은 사실 뉴턴의 운동 법칙에 해당하는 미분 방정식을 직접적으로 구현한 것이다.

F=m\frac{dv}{dt}\\ v=\frac{dx}{dt}

이외에도 맥스웰 방정식을 사용하여 전자기장의 전파를 분석하거나, 격자 양자색역학(lattice QCD)을 사용하여 양성자 내부에서 쿼크와 글루온의 행동을 설명하는 등 더 복잡한 문제에도 국소적 사고방식이 적용될 수 있다.

이러한 국소적 사고방식은 디지털 컴퓨터를 사용하여 공간과 시간을 이산화(discretization)하는 시도와 결합되어, 우주의 모든 복잡성을 간단한 셀룰러 오토마타 시스템으로 축소하려는 스티븐 울프람(Stephen Wolfram)과 같은 영웅이 등장하기도 했다.

💡 역주

셀룰러 오토마타는 격자 내부에 위치한 여러 개의 셀들이 간단한 규칙에 따라 유한 개의 상태로 변화할 수 있는 시스템이다. 대표적인 셀룰러 오토마타 중 하나로는 콘웨이의 생명 게임이 있으며, 이러한 시스템은 간단한 규칙이 생명과 같은 복잡한 패턴을 표현할 수 있음을 보여준다.

다른 접근법은 전역적(global) 접근 방법이다. 시스템의 초기 상태와 최종 상태를 확인한 뒤, 에너지, 시간, 거리와 같은 물리량을 최소한으로 사용하여 이 상태들을 연결할 수 있는 최적의 경로를 계산한다. 가장 간단한 예는 페르마의 최소 시간 원리이다.

이 원리는 빛이 비행 시간을 최소화하는 경로를 따라 전파된다는 것을 나타낸다. 그래서 반사나 굴절이 없는 경우, A 지점에서 B 지점으로 가는 빛은 가장 짧은 경로인 A와 B 사이의 직선 경로를 선택한다.

그러나 빛은 물이나 유리와 같은 밀도가 높은 투명 물질에서는 속도가 느려진다. 따라서 빛의 시작 지점이 공기 중에 있고 도착 지점이 물속에 있을 경우, 빛이 공기 중에서 이동하는 거리보다 물 속에서 이동하는 거리가 더 짧아져야 한다.

최소 시간을 따르는 경로는 빛이 공기와 물의 경계에서 굴절되도록 하며, 이는 스넬의 굴절 법칙(Snell’s Law of Refraction)으로 이어진다.

\frac{\sin(\theta_1)}{\sin(\theta_2)} = \frac{v_1}{v_2}

여기서 $v_1$ 은 공기 중에서의 빛의 속도이고, $v_2$ 는 물속에서의 빛의 속도이다.

고전 역학의 모든 법칙은 최소 작용 원리로부터 도출될 수 있다. 작용은 라그랑지안(Lagrangian)을 경로에 따라 적분하여 계산할 수 있으며, 라그랑지안은 운동 에너지와 위치 에너지의 차이를 나타낸다 (참고로 합(sum)이 아니라 차이(difference)다. 합은 총 에너지를 나타낸다).

우리가 특정 목표를 맞추기 위해 박격포를 발사하면, 포탄은 먼저 중력으로 인해 위치 에너지가 더 높은 곳으로 올라가고, 그 과정 속에서 점점 작용에 음의 기여를 축적한다. 그 후 포탄은 포물선의 꼭대기에서 속도를 줄여 운동 에너지를 최소화하고, 최종적으로는 위치 에너지가 낮은 구간을 빠르게 통과하기 위해 속도를 높인다.

리처드 파인만의 주요 기여 중 한 가지는 최소 작용 원리가 양자역학으로 일반화될 수 있음을 보여준 것이다. 이 경우에도 문제는 초기 상태와 최종 상태로 구성되며, 두 상태 사이의 전이 확률을 계산하기 위해 파인만 경로 적분(Feynman path integral)이 사용된다.

중요한 점은 물리 법칙을 설명하는 방식에 우열을 가리기 어려운 이중성이 존재한다는 것이다. 우리는 하나의 물리적 결과를 설명할 때 작은 일들이 순차적인 여러 단계로 나누어져 발생하는 국소적인 관점을 사용할 수도 있고, 초기 조건과 최종 조건을 선언한 뒤 그 사이에 무슨 일이 있었는지를 설명하는 전역적인 관점을 사용할 수도 있다.

전역적 접근법은 프로그래밍에서도 사용될 수 있다. 예를 들어 레이 트레이싱(ray tracing)을 구현할 때, 우리는 눈의 위치와 광원의 위치를 선언하고, 이들을 연결하는 광선의 경로를 계산한다. 이때 우리가 각 광선의 비행 시간을 명시적으로 최소화하지 않더라도, 스넬의 법칙(Snell’s law)과 반사의 기하학을 이용하여 동일한 효과를 얻을 수 있다.

국소적 접근법과 전역적 접근법의 가장 큰 차이점은 공간, 그리고 더 중요한 시간에 대한 처리 방식이다. 국소적 접근법은 “지금 이 순간”의 즉각적인 결과를 중시하지만, 전역적 접근법은 마치 미래가 이미 정해져 있는 것처럼 장기적이고 정적인 관점을 취하며, 우리가 영원한 우주의 속성을 분석하는 것과 같다.

이 점이 가장 잘 드러나는 곳은 사용자 상호작용에 대한 함수형 반응형 프로그래밍(Functional Reactive Programming, FRP) 접근법이다. FRP는 모든 이벤트에 대해 개별 핸들러를 작성하고 이들이 공유되는 가변 상태에 접근하도록 만드는 대신, 이벤트를 무한 리스트로 간주하고 이 이벤트에 대해 반응하는 특정한 변환을 적용한다.

이론적으로 미래에 발생할 모든 동작을 담은 무한 리스트는 프로그램의 입력 데이터로 사용할 수 있다. 사실 프로그램 관점에서는 𝜋의 숫자 리스트, 의사 난수(pseudo-random number) 리스트, 또는 컴퓨터 하드웨어를 통해 전달되는 마우스 위치 리스트나 큰 차이가 없다. 데이터의 출처가 뭐든 간에 결국 리스트의 n번째 항목을 가져오려면 먼저 𝑛 − 1개의 항목을 통과해야 한다는 사실은 동일하기 때문이다. 이러한 속성이 시간적 이벤트에 적용될 때 이를 인과성(causality)이라고 부른다.

그렇다면 이것이 카테고리 이론과 어떤 관련이 있다는 것일까? 필자는 카테고리 이론이 전역적 접근법을 장려하고, 따라서 선언적 프로그래밍을 지원한다는 이야기를 하려고 한다.

첫 번째로, 미적분학과 달리 카테고리 이론에는 거리(distance), 이웃(neighborhood), 시간(time)과 같은 개념이 없다. 우리가 다루는 것은 그저 추상적인 대상과 대상들 간의 추상적인 연결뿐이다. 만약 A에서 B로 여러 단계를 통해 이동할 수 있다면, 한 번에 도달할 수도 있다.

게다가 카테고리 이론의 주요 도구인 보편적 구성(universal construction)은 전역적 접근법의 정수이다. 우리는 이를 카테고리적 곱(categorical product)의 정의에서 확인했다. 이는 그저 해당 대상의 속성을 명시함하는 것만으로도 충분히 정의할 수 있었으며, 이는 매우 선언적인 접근이다. 곱은 두 투영(projection)을 갖춘 대상이며, 다른 대상들의 투영을 인수분해하는 특성을 최적화하는 가장 적합한 대상이다.

이런 특성을 페르마의 최소 시간 원리 또는 최소 작용 원리와 비교해보면 꽤 유사하다는 것을 알 수 있다.

반대로 카테고리적 곱을 전통적인 데카르트 곱의 정의와 비교해보자. 데카르트 곱은 훨씬 더 명령적인 접근을 보여주고 있다. 이 방법은 하나의 집합에서 원소를 선태갛고 다른 집합에서 또 다른 원소를 선택하여 최종적으로 곱의 원소를 생성하는 방법을 보여주고 있다.

Haskell과 같은 프로그래밍 언어에서 곱 타입, 합 타입, 그리고 함수 타입은 보편적 구성을 통해 정의되는 것이 아니라 이미 내장되어있는 경우가 대부분이다. (물론 카테고리적 프로그래밍 언어를 만드려는 시도는 있었으며, 타츠야 하기노의 논문에 그 내용이 잘 나와있다.)

하지만 프로그래밍 언어에 카테고리적인 정의가 직접적으로 사용되던 아니던, 결국 카테고리적 정의는 기존의 프로그래밍 구조를 정당화하고 새로운 구조를 만들어낼 수 있는 토대가 된다. 가장 중요한 점은 카테고리 이론이 컴퓨터 프로그램을 선언적인 수준에서 추론하기 위한 메타 언어를 제공한다는 것이다. 또한 문제를 코드로 구현하기 전에 명세에 대해 논리적으로 사고하는 것에도 많은 도움을 준다.

원문 보기

👉 Category Theory for Programmers