프로그래밍에서 ‘대수적’이란 무엇을 의미하는지, 추상대수의 구조와 법칙, CRDT와 반격자, 모나드와 대수적 효과의 합성 관점을 통해 직관적으로 설명하고, 효과에 부여할 수 있는 등식 공리와 그 실용적 가치에 대해 논한다.
프로그래밍 언어 맥락에서 "algebraic"이라는 단어는 무엇을 의미하나요?
저도 “대수적 효과(Algebraic Effects)”의 “대수적”이 궁금했고, 유튜브에서 What’s Algebraic About Algebraic Effects and Handlers?라는 발표를 찾아 무척 기대했습니다. 유감스럽게도 제 대상층은 아니더군요. 수학을 마다하지 않는 엔지니어인 저에게도 난이도가 높았습니다.
지난 봄, 대수적 효과를 좀 들여다볼 시간이 있었고, 이제는 그 질문에 제법 괜찮은 답을 할 수 있을 것 같습니다.
프로그래밍에서 “대수(Algebra)”를 저는 특정한 종류의 합성성(compositionality)—즉 구조가 있는 합성—으로 봅니다.
대조적으로, 주류 개발자들이 말하는 합성은 종종 동일한 인터페이스 덕분에 두 객체/함수가 상호 운용 가능하다는 정도에 그치며, 그 상호 운용의 성질에 대해 더 많은 것을 추론하기는 어렵습니다.
그래서 흔히, 어떤 객체/함수들의 모음이 작성자의 취향에 따라 임의로 엮여 있습니다. 잘 만든 코드라면 직관적으로 느껴지기도 하지만, 대부분은 임의적이라고 느껴집니다. 코드베이스를 들여다보면 그 효과가 커집니다. 신입의 눈에는, 돌을 그냥 높이 쌓아 올린 집처럼 지저분하게 느껴집니다. 눈에 띄는, 쉽게 인지되는 구조가 없기 때문이죠.
추상대수에서 구조란, 어떤 수학적 객체 𝛂(정수나 행렬 같은 것)를 하나의 연산(+, * 같은 것)과 짝지어, “정수는 + 연산으로 합성할 수 있고, 그 조합에서 어떤 성질—혹은 법칙—을 함께 추론할 수 있다”고 말하는 데서 자주 등장합니다.
우리가 익숙한 예를 하나 들면: 정수(ℤ)와 덧셈(+)에는 항상 성립하는 암묵적 성질들이 있습니다. 원소(ℤ), 연산(+), 그리고 그 성질들이 함께 결과를 제약하고, 이것이 구조를 제공합니다. 구조가 있는 집은 돌무더기가 아니라 아치로 지어진 집처럼 느껴집니다. (ℤ)와 (+)의 성질은 무엇일까요? ℤ와 +의 정의로부터 다음이 나옵니다:
가끔 개발자들은 같은 것을 돌려주지 않는 코드를 씁니다.
초등학교 때부터 익히 배운 것들이죠. 하지만 이런 성질을 만족시키지 않는 코드를 개발자들이 종종 씁니다.
나머지 둘은 다음과 같습니다:
여기서는 0이죠: a + 0 = a
이들을 함께 묶어 수학자들은 이런 구조에 이름을 붙였습니다: 군(Group). 누군가가 [어떤 집합]과 [어떤 연산]이 함께 군을 이룬다고 말하면, 저는 자동으로 위 성질들을 가정할 수 있습니다. 일종의 약속어죠.
ℤ와 +의 행동에 더 많은 제약/성질을 추가하면 또 다른 대수적 구조가 됩니다. 이런 구조에는 아주 다양한 족과 계보가 있습니다. 예컨대 제약을 하나 더 추가하면 아벨 군(Abelian Group)이 됩니다:
왜 데이터 구조와 연산을 제약해 짝지어야 할까요? 시스템이 특정한 성질을 반드시 갖도록 보장하고 싶을 때 매우 유용합니다. 예컨대, 동기화(sync)는 악명 높게 어렵습니다. 분산 시스템의 8가지 착각 때문이죠.
이는 네트워크로 보낸 데이터가 순서가 뒤바뀐 채 도착할 수 있음을 의미합니다. 더 나쁘게는, 시계가 서로 맞지 않아 마치 데이터가 미래에서 온 것처럼 보일 수도 있습니다. 이런 신뢰할 수 없는 기반을 어떻게 길들이죠? 우리의 데이터와 연산에 성질을 부여하도록 제약함으로써요.
CRDTs는 요즘 결국 일관성(eventual consistency)을 보장하는 동기화에 쓰입니다. 데이터 구조를 병합 연산과 짝지워, 반격자(semi-lattice)라는 대수적 구조를 이루게 함으로써 이루어집니다. 반격자의 성질은 다음과 같습니다:
💡
∘는 merge op(병합 연산)을, ∈는 집합의 원소를 의미합니다.
이것들만으로도, 네트워크가 데이터를 뒤섞는 문제를 상쇄하기에 충분합니다. 이에 대해서는 여기에서 다뤘습니다:
그러니 우리의 코드가 할 수 있는 힘을 제약함으로써, 신뢰할 수 없는 네트워크에서 데이터를 동기화하는 목표를 달성하는 데 꼭 필요한 성질들을 시스템이 갖도록 보장할 수 있습니다. 즉, “이런 종류의 데이터 구조를, 이런 제약된 방식으로, 이런 종류의 병합 함수와 합성하면, 우리는 이런 성질들이 항상 성립한다고 보장할 수 있다. 그리고 이런 구조를 가지면, 우리의 데이터는 다른 동기화자들과 신뢰할 수 없는 네트워크를 거쳐도 살아남을 수 있다”고 말할 수 있게 되는 것입니다.
그래서 사람들이 모나드를 좋아합니다. 모나드는 코드를 어떻게 합성할지에 관한 것이지만, 특정한 성질(모나드 법칙)을 갖도록 하여 합성 방식에서 어떤 목표를 달성하게 해 줍니다. 여기서 자세히 다루지는 않겠지만, 핵심은 그렇습니다.
하지만 모든 종류의 모나드가 서로 잘 합성되지는 않습니다. 이 부분은 제 전문 밖이지만, 그래서 모나드 변환기(Monad Transformer)가 있어 서로 다른 도메인의 모나드를 끼워 맞출 수 있다고 읽었고 들었습니다.
그래서 어떤 이들은 모나드와는 다른 방식으로 동일한 합성 능력을 얻기 위해 대수적 효과(Algebraic Effects)를 살펴보기 시작했습니다. 대수적 효과에 대한 설명은 대개 algebraic 부분을 무시합니다. effects만 설명해도 이미 큰 도약이기 때문이죠.
효과 부분은 흔히 “재개 가능한 예외(resumable exceptions)”로 설명됩니다. 이 관점에서 대수적 효과가 무엇인지 짧게 적은 글이 있으니, 여기서는 더 늘어놓지 않겠습니다.
하지만 대수적 효과의 ‘대수적’인 부분은, “재개 가능한 예외”로써 올린(effect를 raise한) 효과들을 서로 합성할 수 있다는 점입니다! 아무렇게나가 아니라, 합성했을 때 위에서 본 것처럼 어떤 성질이 ‘보장’되도록 효과를 설계하는 것입니다!
예를 들어, get과 put으로 인터페이스하는 키/값 저장소가 있다면, 우리가 기대하는 바를 몇 가지 대수적 성질로 표현할 수 있습니다.
이는 두 번 연속 get이 단일 get과 기능적으로 동등하다는 뜻입니다. 이는 get이 _순수 관찰(pure observation)_임을 보장합니다. 즉, 무언가를 소비하거나 커서를 전진시키지 않습니다. 이 법칙이 성립하지 않는다면, 읽기가 어떤 숨은 커서를 “소모”하거나 “전진”시킬 수 있겠죠. 이를 법칙으로 못박음으로써, 사용자들이 나중에 이 성질과 어긋나는 가정을 하다가 놀라운 버그를 맞는 일을 줄입니다.
간단합니다. 두 번의 put은 마지막 것 하나만 실행하는 것과 기능적으로 같습니다. 따라서 마지막 put이 키 k에 현재 들어 있는 값이 됩니다. 이것은 _덮어쓰기语义(오버라이트语义)_를 인코딩합니다. 이게 없다면, put이 이어붙이거나 병합하거나 누적할지도 모릅니다. 사용자가 기대하는 동작이 아니겠죠.
put을 실행한 다음 즉시 get을 실행하는 것은, 사실상 put만 실행하고, get을 또 실행하지 말고 이미 손에 쥔 값 v를 그냥 반환하는 것과 같습니다. 이는 쓰기 직후 읽기의 _일관성_을 보장하는 데 중요합니다. 이게 없으면 v를 썼는데 곧바로 v가 보이지 않을 수 있고, 키/값 저장소의 직관적 상태 모델을 깨뜨리게 됩니다.
키의 값을 읽은 다음 곧바로 바꾸지 않고 다시 쓰는 것은, 아무 일도 하지 않는 것(단위값을 반환)과 기능적으로 같습니다.
💡
>>=는 “그리고 나서(and then) ...”라고 생각하면 됩니다. 그러니 규칙 4를 자바스크립트 의사코드로 쓰면 다음과 같겠죠:
get(store, key).andThen((val) => put(store, key, val))
💡
return ()에서 ()는 unit(단위값)이라 부르는데, 함수형 프로그래머들이 “의미 있는 값이 없음”을 나타내는 방식입니다. C 프로그래머가 쓰는 void와 효과상 비슷합니다. 기술적으로는 다르지만, 실무에서는 유사한 목적으로 쓰입니다.
Interjected Future Wil Chung 
Interjected Future Wil Chung 
k1 ≠ k2일 때:put k1 v1; put k2 v2 ≡ put k2 v2; put k1 v1
get k1; get k2 ≡ get k2; get k1
put k1 v; get k2 ≡ get k2; put k1 v
서로 다른 키에 대한 연산은 서로 교환 가능하며, 저장소는 각 키를 독립된 셀처럼 다룹니다. 이것이 이 구조가 어떤 뒤엉킨 자료구조가 아니라 키/값 저장소임을 만들어 줍니다.
따라서, 효과를 쓴다고 해서 그것이 자동으로 대수적이 되지는 않습니다. 사용자가 가져가길 바라는 성질이나 보장을 제공하도록 의식적으로 대수적으로 설계해야 합니다. 현재 대부분의 프로그래밍 언어는 이런 등식 공리를 강제할 방법이 없어, 대수적 효과를 제공하는 다소 특이한 언어들조차 이를 강제하려 들지 않습니다.
Coq, Agda, Idris 2, Lean 같은 종속 타입(dependent types) 언어만이 이런 등식 공리를 명시적으로 인코딩하고, 그 타당성을 증명할 수 있습니다. 보통 이런 언어는 수학자들이 수학적 증명을 하는 데 사용합니다. 흥미롭게도 Lean은 최근 큰 모멘텀을 얻고 있고, C로 컴파일할 수도 있습니다. 실무에 들여오는 실용적 진입로가 될 수 있죠.
그리고 제 말로 요약하면, 그것이 바로 대수적 효과에서 ‘대수적’인 부분입니다.
앨런 케이(Alan Kay)는 코드베이스에 100만 줄이 있는 것은 용납할 수 없다고 한 것으로 유명합니다. 그건 마천루라기보다 돌무더기에 가깝다고요. 종종 구조가 없기 때문입니다. 우리는 결국 아치를 알아냈습니다. 더 적은 재료로 강도를 주는 구조죠.
그래서 더 많은 재료 없이도 더 높이 지을 수 있게 되었습니다. 비유하자면, 우리는 소프트웨어에서 그런 구조가 무엇인지를 이제 막 발견하기 시작했습니다. 그리고 그것은 수학처럼 보입니다. 여기에 대한 저항은 많고, 앞으로도 한동안 그럴 것입니다.
아마 LLM이 등장한 지금, 많은 응용 분야에서는 큰 상관이 없을지도 모릅니다. 그래도 이 방향으로의 진전은 계속되고 있고, 순수 함수형 프로그래밍이나 수학적인 아이디어들이 더 주류 언어들로 스며들고 있습니다.