모든 공학은 기초 과학에 뿌리를 두고 있습니다. 따라서 해당 학문의 뼈대를 구성하는 기초 과학을 잘 이해하는 것이 엔지니어링을 잘하는 가장 빠른 지름길이기도 합니다. 프로그래밍도 예외는 아니어서 프로그래밍을 잘하기 위해서는 컴퓨터 과학, 더 나아가서 논리학과 수학에 대한 이해가 필수입니다.
저는 게임 개발자를 뽑을 때 주로 컴퓨터공학과(혹은 컴퓨터과학과) 학부에서 배우는 전공 지식에 대해 주로 질문하였습니다. 게임 프로그래밍 경험이 아무리 출중해도 알고리즘의 시간/공간 복잡성(time/space complexity)에 대한 개념도 이해를 못 하고 있다면 개발자로서 앞으로의 발전을 기대하기는 힘들다고 생각하기 때문입니다.
컴퓨터 과학이 수학과 논리학에서 출발학 학문임에도 불구하고 개발자들은 수학과 프로그래밍의 상관 관계를 피부로 체감하지 못하는 경우가 많은 것 같습니다. 저 또한 대학을 수학과로 입학했음에도 불구하고, 대수학 같은 추상적인 수학을 공부하면서 지루해 했고 결국 컴퓨터공학과로 전과 후에는 수학 공부를 멀리 했었습니다. 오히려, 졸업 후에 프로그래밍을 더 공부하다 보니 다시 수학의 필요성을 절감하고 뒤늦게 수학 공부하느라 진땀을 빼고 있는 중입니다.
이번 글에서는 수학 공부에 대한 흥미를 유발하기 위해 수학과 프로그래밍의 재미있는 상관 관계 하나를 보여드리고자 합니다. 일단 우리가 알고 있는 간단한 덧셈부터 시작해 보겠습니다.
1 + 2 = 3
이런 수식의 구성 요소는 숫자(1, 2, 3 등)과 연산자(+, – 등)이 있고, 숫자 대신 변수(x, y, z 등)을 사용할 수도 있습니다. 또한 다음과 같은 법칙들도 존재합니다.
0 + x = x
1 * x = x
위 예에서 알 수 있듯이 대수학이란 크게 3가지 요소로 구성됩니다.
- 오브젝트(object) – 대수학이 다루는 것.
- 연산자(operation) – 오브젝트로 새로운 오브젝트를 만드는 것.
- 법칙(law) – 오브젝트와 연산자들의 상관 관계
여기까지 복습을 했으면 이제 프로그래밍으로 돌아가 봅시다. 1+1=2라는 사실과 프로그래밍이 어떤 관계가 있을까요? C# 타입 시스템을 예로 들어 설명해 보겠습니다.
일단 C# 타입 시스템으로 숫자 0, 1, 2를 만들어 보겠습니다. 타입 시스템과 숫자를 연결시키기 위해 어떤 타입이 가지는 인스턴스의 수를 세는 방법을 사용하겠습니다.
우리가 가장 사랑하는 디자인 패턴인 싱글톤(singletone)은 하나의 인스턴스만 만들 수 있으므로 숫자 1이라고 생각할 수 있습니다. 다음과 같이 Unit이라는 싱글톤 클래스를 선언하였습니다.
class Unit
{
public static Unit Instance = new Unit();
private Unit()
{
}
}
숫자 0은 어떻게 만들 수 있을까요? 클래스는 있지만 인스턴스를 전혀 만들 수 없는 클래스를 만들면 됩니다.
class Void
{
private Void()
{
}
}
숫자 2는 어떻게 만들 수 있을까요? 해당 타입의 인스턴스를 단 2개만 만들 수 있어야 하는데, 우리는 이런 타입을 이미 알고 있습니다. 바로 bool이죠. 아니면 Unit과 유사한 방식이지만 인스턴스가 2개 있는 타입을 만들 수도 있습니다.
class Bool
{
public static Bool True = new Bool();
public static Bool False = new False();
private Bool()
{
}
}
자 이제 숫자는 충분히 있으니 덧셈을 만들어 보겠습니다.
abstract class Sum
{
}
sealed class SumLeft : Sum
{
private readonly TL value;
public SumLeft(TL left)
{
this.value = left;
}
}
sealed class SumRight : Sum
{
private readonly TR value;
public SumRight(TR right)
{
this.value = right;
}
}
</tl,></tl,></tl,></tl,></tl,>
Sum이라는 클래스는 SumLeft와 SumRight라는 두 개의 서브클래스만이 존재하는 추상 클래스입니다. 바꿔 말해 Sum은 반드시 SumLeft이거나 SumRight입니다.
이게 왜 덧셈이 되는 걸까요? Sum 타입의 인스턴스를 나열해 보면 알 수 있습니다. 예를 들어, Sum[bool, Unit] 타입의 인스턴스는 SumLeft(true), SumLeft(false), SumRight(Unit) 세 개의 인스턴스를 만들 수 있습니다. bool은 2, Unit은 1이므로 Sum[bool, Unit]은 2+1을 뜻하고 실제로 인스턴스의 수도 3인 것을 확인할 수 있습니다.
곱셈은 더 간단합니다. C#의 클래스 자체가 곱셈을 표현하는 타입이기 때문입니다.
class Product
{
private readonly TL left;
private readonly TR right;
public TL Left { get { return left; } }
public TR Right { get { return right; } }
public Product(TL left, TR right)
{
this.left = left;
this.right = right;
}
}
</tl,>
Product[TL, TR]은 left와 right 2개의 필드를 가지고 있습니다. 이게 곱셈이 되는 이유는 Product[bool, Unit]의 인스턴스 수를 세어 보면 알 수 있습니다. 이 타입은 Product(true, Unit)과 Product(false, Unit) 두 개의 값을 가집니다. left 값 하나에 대해서 모든 right 값이 반복되므로 Cartesian product이라고 생각할 수도 있습니다.
이제 오브젝트(Void, Unit, bool 등)와 연산자(Sum, Product)를 모두 정의했으므로 우리가 알고 있는 대수학의 법칙이 그대로 적용되는지도 확인해 보겠습니다.
0 + x = x
위 식을 C#의 타입으로 풀어보면 Sum[Void, X] = X가 됩니다. Void는 인스턴스가 존재하지 않는 타입으므로 SumLeft[Void]의 인스턴스는 존재할 수가 없습니다. 따라서 모든 인스턴스는 SumRight[X] 타입이 되고, 전체 인스턴스의 수는 X 타입의 인스턴스 수와 일치하게 됩니다. 0은 덧셈에 대한 항등원이고, Void는 Sum 연산에 대한 항등원임을 확인할 수 있습니다.
x+y=y+x
위 식도 C# 타입으로 풀어보면 Sum[X, Y] = Sum[Y, X]가 됩니다. Sum[X, Y]의 의미는 인스턴스가 SumLeft[X]이거나 SumRight[Y]라는 뜻이므로 X 타입의 인스턴스 수 + Y 타입의 인스턴스의 수가 됩니다. 반대로 Sum[Y, X]는 인스턴스가 SumLeft[Y]이거나 SumRight[X]라는 뜻이므로 마찬가지로 X 타입의 인스턴스 수 + Y 타입의 인스턴스의 수가 됩니다. C# 타입 시스템에서 Sum[X,Y]와 Sum[Y,X]는 엄밀히 말해 다른 타입이긴 하지만, 덧셈으로서 의미는 일치함을 알 수 있습니다.
곱셈도 마찬가지 방식으로 법칙을 확인할 수 있습니다.
0 * x = 0
Product[Void, X] 타입의 인스턴스는 존재할 수 없습니다. Void의 인스턴스가 존재하지 않기 때문입니다. 인스턴스의 수가 0이므로 이 타입은 0을 뜻하는 Void와 의미가 일치함을 알 수 있습니다.
1 * x = x
Product[Unit, X] 타입의 인스턴스는 Product(Unit, X)가 됩니다. Unit은 인스턴스가 1개밖에 없으므로 이 타입의 인스턴스 수는 X 타입의 인스턴스 수와 동일합니다.
x * y = y * x
Product[X, Y]와 Product[Y, X]는 모두 X 타입의 인스턴스 수 * Y 타입의 인스턴스 수를 가지므로 곱셈으로서 의미가 일치한다는 사실도 쉽게 확인할 수 있습니다.
같은 방법으로 배분 법칙(distributive law)과 같은 좀 더 복잡한 법칙도 성립함을 알 수 있습니다.
x * (y + z) = x * y + x * z
이번에 반대 방향으로 C#의 함수 타입이 우리가 알고 있는 대수학과 어떤 관계가 있는지 살펴봅시다. bool -> bool 함수 타입은 C# 타입으로 Func[bool, bool]입니다. 이 타입의 인스턴스 수는 몇 개일까요? bool은 true 혹은 false 두 개의 값을 가지므로 Func[bool, bool]은 2 * 2, 즉 4개의 값을 가집니다. 이렇게 보면 곱셈과 비슷한 것 같기도 한데, 확인을 위해 인스턴스가 3개인 타입을 정의해서 다시 한 번 확인해 봅시다. (enum 타입은 임의의 int로 만들어 낼 수 있으므로 엄밀하 말해 인스턴스가 3개는 아니지만, 여기서는 편의를 위해 인스턴스가 3개라고 가정합니다.)
enum Num
{
One,
Two,
Three
}
Func[Num, bool] 타입의 인스턴스 수는 Num의 인스턴스 각각에 대해 true, false 두 개의 값을 가질 수 있으므로 2 * 2 * 2 = 8개임을 알 수 있습니다. 곱셈이 여러 번 반복되는 것은 지수이므로 2^3 = 8로 표현할 수도 있습니다. 바꿔 말해, 인스턴스의 수가 각각 a, b인 Func[A,B]의 값은 b^a이 됩니다.
함수 타입에서도 몇 가지 법칙을 확인할 수 있습니다. 예를 들어, Func[Unit, X]은 X와 같습니다. Unit 값 하나에 대해 X 타입 인스턴스 수만큼 인스턴스가 존재하기 때문입니다. 반대로 Func[X, Unit]은 Unit과 같습니다. X의 값에 상관 없이 Unit이 나오기 때문입니다. 이는 우리가 아는 대수학으로 표현하면 각각 a^1 = a, 1^a = 1이 됩니다. 이처럼 함수와 지수는 그 수학적 성질이 같기 때문에 타입 이론에서는 함수 타입을 지수 타입(exponential type)이라고도 부릅니다.
이런 상관 관계를 이용하면 재미있는 사실을 하나 발견할 수 있습니다. 우리가 함수 언어에서 말하는 currying은 인자 여러 개의 함수를 인자 하나짜리 함수로 표현하는 것을 말합니다. 예를 들어, (A, B) => C 타입의 함수는 A => B => C 타입으로 표현될 수 있습니다. C#의 람다 표현식(lamba expression)으로 적어보면 다음과 같습니다.
Func add = (x, y) => x + y;
int a = add(2, 3); // a = 5
Func<int, func> curriedAdd = x => y => x + y;
int b = curriedAdd(2)(3); // b = 5
</int,></int,>
add 함수는 인자 x, y를 받아서 x+y를 계산하는 함수입니다. curriedAdd 함수는 인자 ‘x’를 받아서 인자 y를 받아 x+y를 리턴하는 함수를 리턴합니다. 여기에 인자 2,3을 차례대로 호출하면 add와 마찬가지로 5가 리턴되는 것을 확인할 수 있습니다.
참고로 (int, int)가 인자인 함수는 Product[int, int] 타입을 받는 인자 하나짜리 함수로 생각할 수 있습니다. 따라서 (A, B) => C 타입의 함수를 지수로 쓰면 c^(ab)가 됩니다. 이는 c^(ba)와 같고 (c^b)^a와 같습니다. 여기서 다시 함수 타입으로 돌아가면 A => (B => C)가 나옵니다. 인자 여러 개를 받는 함수를 인자 하나를 받는 함수를 반복해서 표현할 수 있다는 currying을 지수로 표현하면 이미 우리가 알고 있는 간단한 연산만으로 유도할 수 있는 셈입니다.
한 발 더 나가서 이번에는 재귀적 데이터 타입인 리스트(List)를 정의해 보겠습니다. C#에서 리스트는 여러 방식으로 구현할 수 있는데, 여기서는 함수 언어에서 사용하는 전통적인 방식의 리스트를 정의하겠습니다. List[T]는 두 가지 경우의 수가 있는데, 빈 리스트를 뜻하는 Nil이거나 T 타입의 tail과 List[T] 타입의 tail로 구성된 Cons가 있습니다.
이를 우리가 앞서 정의한 Sum과 Product 타입으로 표현해 보면 List[T]는 Sum[Unit, Product[T, List[T]]]가 됩니다. 풀어서 설명하면 리스트는 빈 리스트를 뜻하는 SumLeft[Unit]이거나 T와 List[T]로 이루어진 SumRight[Product[T, List[T]]]입니다.
Sum과 Product는 각각 덧셈과 곱셈, Unit은 1로 대체할 수 있으므로 위 리스트 타입을 대수학으로 표현하면 다음과 같이 됩니다.
L(T) = 1 + T * L(T)
수식을 풀어보면 다음과 같습니다.
L(T) – T * L(T) = 1
(1 – T) * L(T) = 1
L(T) = 1 / (1 – T)
여기까지는 간단한 계산입니다. 1 / (1 – T)를 테일러 시리즈(Taylor Series)로 풀어보면 다음과 같습니다.
L(T) = 1 + T + T^2 + T^3 + T^4 + …
이 수식을 다시 타입으로 들고 와서 해석해 보면 List[T]란 Unit이거나 T이거나 Product[T, T]이거나 Product[T, T, T]이거나… 라는 식으로 해석이 되고 이는 정확히 리스트 타입이 의미하는 바를 나타냅니다. T에 int를 대입해보면 각각의 타입이 [], [1], [1,2], [1,2,3]와 같은 리스트의 값을 표현하고 있기 때문입니다.
여기서 가장 재미있는 점은 우리가 타입에 대해서는 뺄셈이나 나눗셈 연산을 전혀 정의하지 않았음에도 불구하고, 타입을 대수로 옮긴 다음에 뺄셈, 나눗셈 및 테일러 시리즈까지 수행한 결과를 다시 타입으로 들고 와도 여전히 유효하다는 사실입니다. 단순히 우연일까요? 이게 가능한 이유는 타입과 대수가 모두 semiring이라는 수학적 구조를 따르고 있기 때문입니다.
설명이 길어졌는데, 우리가 매일 매일 사용하는 프로그래밍 언어에도 우리가 생각치 못한 수많은 수학적 원리들이 숨어 있습니다. 앞서 살펴본 것처럼 우리가 늘 사용하는 간단한 사칙 연산조차도 프로그래밍 언어의 타입 시스템과 깊은 관계가 있음을 알 수 있습니다. 따라서 프로그래밍을 좀 더 깊이 있게 공부하려면 이런 수학, 논리학과 같은 기초에 관심을 가지고 조금 더 공부해 볼 것을 권합니다.
참고로 이 내용은 헤스켈로 설명한 The Algebra of Algebraic Data Types 강연 내용을 이해하기 쉽게 C#으로 정리하였습니다. 좀 더 깊이 있는 내용을 원하시면 해당 강연을 들어보시기 바랍니다.
Kwang Yul Seo 