Account: please sign in
AA

값과 타입

간혹 수학이나 논리학 관련 문서에서

  • v : T

라고 쓰여있는 것을 본 일이 있을 것입니다. 이것은 "v는 T라는 타입을 갖는다" 혹은 간단히 "v의 타입은 T다"라는 뜻이며, 그렇게 읽습니다. 때로는 다음과 같이 두 줄이 동시에 쓰여있는 경우도 있는데:

  • v : T
    v = 3

이것은 "v의 타입은 T고 값은 3이다"라는 뜻입니다.

집합으로서의 타입

타입은 집합과는 전혀 무관한 별개의 개념이지만, 타입을 직관적으로 빠르고 쉽게 이해하려면 집합에 빗대어 생각하는 것도 한 가지 방법입니다. 즉, 위 표기는 "v는 T라는 집합의 원소인 3이다"라는 뜻으로 해석할 수 있으며, 다음과 같은 표기와 맥이 상통합니다:

  • v ∈ T
    v = 3

즉, T라는 집합에는 적어도 3이라는 원소 하나 만큼은 반드시 들어있다는 뜻입니다. 예를 들어, T는 다음과 같은 집합이었을 수도 있습니다:

  • T = { 1, 2, 3, 4, 5 }

위 내용 중 "=" 기호로 이어진 것들은 서로 바꿔서 쓸 수도 있습니다. (물론 엄밀히 따지면 의미가 조금씩 달라지긴 합니다만, 이 문서의 범위를 벗어나는 차이이므로 넘어갑니다.) 예를 들어,

  • v : { 1, 2, 3, 4, 5 }
    v = 3

이라고 쓸 수도 있고,

  • 3 : T

라고 쓸 수도 있이며, 아예

  • 3 : { 1, 2, 3, 4, 5 }

라고 쓸 수도 있습니다.

이렇게 타입을 집합에 빗대어 생각하는 방식은 깊게 따지고 들어가다보면 다소 문제가 발생하는 위험한 방식이긴 합니다만, 당장 기본적인 개념을 잡는 데에는 큰 문제가 없으니 이 문서에서는 이 방식으로 설명하겠습니다. 앞으로는 원소-집합 소속 관계를 나타내는 기호 "∈"를 거의 사용하지 않고 값-타입 대응을 나타내는 기호 ":"를 주로 사용할텐데, 그때마다 이 기호를 집합 소속 관계로 해석하시면 큰 문제가 없습니다.

다만, 중요한 개념적 차이 하나는 미리 짚고 넘어가겠습니다: 거의 대부분의 집합론 문서에서, 기호 "∈"는 원소 하나와 집합 하나를 인자(피연산자)로 받아서 명제를 돌려주는 이항 중위 연산자입니다. 즉,

  • v ∈ T

이라는 표기는 그 자체가 명제로 평가되는 표현식expression이며, 따라서 (명제니까) 부정negation도 가능하고:

  • ¬(v ∈ T)

이 부정문과 동치인 식을 나타내기 위한 연산자도 있습니다:

  • v ∉ T

반면에, 거의 대부분의 유형론type theory 문서와 함수형 프로그래밍 언어에서, 기호 ":"는 이항 중위 연산자가 아니며, 기호 ":" 왼쪽에 변수variable나 값value(혹은 텀term)이 있고 오른쪽에 타입이 있는

  • v : T

라는 표기는 평가가 가능한 표현식이 아니라 일종의 문statement인 타입 선언문입니다.

선언과 정의

위 소절에서 소개했던 나란히 쓰여진 두 줄

  • v : T
    v = 3

중에서, 윗 줄인

  • v : T

를 v의 타입 선언type declaration 혹은 타입 서명type signature 혹은 간단히 "선언"이나 "서명"이라고 하고, 아랫줄인

  • v = 3

을 v의 정의definition라고 합니다. 그다지 필수적으로 아셔야할 사항은 아니고 문서마다 조금씩 다른 용어를 쓰는 경우도 있으니 항상 이렇다고 단정하기도 곤란하지만, 이 문서에서는 몇 번 더 쓰일 용어이므로 미리 소개해둡니다.

프로그래밍 언어에서의 타입

흔히 사용하는 C 언어에서 다음과 같은 구문을 보신 적이 있을겁니다:

int x;
x = 3;

이것은 앞서 보여드렸던 수학 및 논리학의

  • v : T
    v = 3

라는 표기와 의미가 거의 상통하는 구문입니다. C 언어에서도 윗줄 "int x;"를 변수 x의 "선언"이라고 부릅니다. 아랫줄 "x = 3;" 부분은 x의 정의가 아니라 "대입"이라고 부릅니다만, 이는 C 언어의 설계 방식이 이 문서에서 소개하려는 내용과는 방향이 조금 다르기 때문입니다.

반면에, 앞서 표기했던 타입 선언 및 정의와 완전히 똑같은 의미의 구문을 거의 비슷한 기호로 기재하는 프로그래밍 언어도 실제로 있습니다. Haskell 언어는

 x :: Int
 x = 3

이라고 표기하며, 두번째 줄은 변수 x에 3을 대입하는 것이 아니라 실제로 수학처럼 x를 3이라고 "정의"하는 것입니다. 대입과 정의의 차이는 일단 이렇게만 알아두면 됩니다: 대입은 순차적인 '재대입'이 가능하지만, 정의는 재정의/중복정의가 불가능하며 한 스코프 내에서 서로 충돌하는 둘 이상의 정의는 무조건 오류입니다.

함수의 타입

정의역과 공변역

어떤 함수 f가 D로부터 C로의 함수라는 뜻은, 이 함수는 반드시 D 타입인 값(인자)에만 적용될 수 있고, D 타입의 값들 중 어떤 값에 적용되더라도 반드시 그에 상응하는 어떤 C 타입의 값으로 환원된다는 뜻입니다. 즉,

  • d : D

인 모든 d에 대해서, 항상

  • f d : C

라는 뜻입니다.

아직 함수형 언어와 유형론적 용어에 충분히 익숙하지 않은 단계임을 감안하여, 절차형 언어와 집합론적 용어로 다시 설명하면 이렇게 됩니다:

어떤 함수 f가 D로부터 C로의 함수라는 뜻은, 이 함수에는 반드시 D 집합의 원소가 인자로 주어져야 하며, D 집합의 원소들 중 어떤 원소가 인자로 주어지더라도 반드시 그에 상응하는 어떤 C 집합의 원소를 함수값으로 돌려준다(return)는 뜻입니다. 즉,

  • d ∈ D

인 모든 d에 대해서, 항상

  • f(d) ∈ C

라는 뜻입니다.

이때 D를 정의역domain이라고 하며 C를 공변역codomain이라고 합니다.1 수학 관련 문서에서는 이를 관례적으로 다음과 같이 표기하는데:

  • f : D → C

이 표기는 전술했던 타입 선언과 완전히 같은 의미의 표기입니다. 즉, 함수 f의 타입이 바로 "D → C"라는 뜻입니다. 다만, 전술했던 바와 같이, 이 문장은 어디까지나 함수 f의 타입만을 선언하고 있을 뿐 f가 정확히 어떤 값인지(즉, 정확히 어떤 값을 어떤 값에 대응시키는 함수인지)는 말(정의)하고 있지 않습니다.

함수 정의

함수 f의 정의definition는 타입 선언과는 별개로 따로 기술하는데, 관례적으로 함수의 정의를 기술하는 방식은 여러가지가 있습니다.

가장 단순한 방법으로는 (특히, 정의역이 유한 집합일 경우) 대응 관계를 일일이 순서쌍으로 표기할 수 있습니다. 만일 두 집합 A와 B가 각각 다음과 같다면:

  • A = { 10, 20 }
    B = { 1, 2 ,3 }

A의 원소 10을 B의 원소 3에, A의 원소 20을 B의 원소 1에 각각 대응시키는 함수 f는 다음과 같이 표기할 수 있습니다:

  • f : A → B
    f = { (10↦3), (20↦1) }

집합으로서의 이항 관계

먼저, 이항 관계가 일종의 집합임을 확인해보겠습니다.

만일 어떤 집합 R이 두 집합 X와 Y의 데카르트 곱Cartesian product의 부분집합이면 (R ⊆ X×Y), 이 집합 R은 X와 Y 사이의 이항 관계입니다.

예를 들어, 두 집합 A = {a1, a2, a3}, B = {b1, b2}가 있을 때 다음과 같은 집합들 각각은 모두 A와 B 사이의 이항 관계들입니다:

  • ∅   {a1, b2}   {(a1,b1), (a1,b2), (a3,b1)}

어떤 순서쌍 (x,y)가 이항 관계 R의 원소일 때 ((x,y)∈R), 이를

  • xRy   혹은   R(x,y)

라고 표기하며, "x와 y는 R 관계에 있다 (x is R-related to y)"고 말합니다.

관계로서의 함수

이번엔, 함수가 일종의 이항 관계임을 확인해봅니다.

두 집합 D, C 사이의 이항 관계들 중 functionality와 totality를 모두 만족시키는 관계 f를 D로부터 C로의 전체 함수total function 혹은 간단히 함수라고 합니다

  • f : D → C

또한, 두 집합 D, C 사이의 이항 관계들 중 functionality를 만족시키지만 totality를 만족시키지 않는 관계 p를 D로부터 C로의 부분 함수partial function라고 합니다.

  • p : D ⇸ C

예를 들어, 두 집합 A = {a1, a2, a3}, B = {b1, b2}가 있을 때,

  • 관계 {(a1,b2), (a2,b1), (a3,b2)}는 A로부터 B로의 (전체) 함수이고

  • 관계 {(a1,b2), (a3,b2)}는 A로부터 B로의 부분 함수며

  • 관계 {(a1,b2), (a2,b1), (a2,b2), (a3,b2)}는 A로부터 B로의 함수도 부분함수도 아닙니다.

이 노트의 요점은 결국 함수도 일종의 집합으로 볼 수 있다는 점입니다. 단, 다음 절에서 설명할 '함수들의 집합'과 혼동하시면 안됩니다: 이 노트에서 말하는 것은 각각의 함수 하나하나가 각각 집합이라는 이야기입니다.

참고

우향 화살표의 왼쪽 끝에 짧은 세로 선이 붙어있는 기호 "↦"의 (유니코드 차트에 등재된) 정식 명칭은 "Rightwards arrow from bar"로서 간단히 "maps to"라고 읽기도 하며, 수학에서는 전통적으로 값의 단방향 대응mapping 관계를 나타냅니다. 함수를 대응 관계들의 집합으로 표기할 때에도 이 기호가 흔히 쓰이지만, 문서에 따라 조금씩 다른 경우도 있습니다.

어떤 문서에서는 괄호를 빼고 f = { 10↦3, 20↦1 }이라고 쓰기도 하고, 그냥 순서쌍으로 f = { (10,3), (20,1) }이라고 쓰는 경우도 있으며, 때로는 일반 괄호와의 혼동을 피하기 위해 순서쌍을 둘러싸는 괄호를 "각괄호angle bracket"로 바꿔서 f = { 〈10,3〉, 〈20,1〉 }이라고 쓰기도 합니다. 어떻게 표기하든 한 문서 내에서 일관성 있게 표기되기만 하면 틀린 표기는 아니니, 여러가지로 표기된다는 사실만 참고 삼아 기억해두시기 바랍니다.

지금 이 문서에서는 f = { (10↦3), (20↦1) } 표기로 통일하겠습니다.

정의역과 공변역이 모두 수(數)들의 집합일 경우엔 수식으로 표기하는 경우가 많고:

  • f : RR
    f(x) = 3x2 -5x + 8

조건 분기가 필요한 경우엔 약간의 자연어를 섞어서 표기하거나:

  • f : NN
    f(n) = 1 if n = 0, n × f(n-1) otherwise

아예 인자에 따라 나눠서 정의하기도 합니다:

  • f : NN
    f(0) = 1
    f(n) = n × f(n-1)

바로 위의 예 처럼 인자의 경우에 따라 나눠서 정의하는 경우에는 관례적으로 먼저 쓰여있는 문장부터 우선적으로 확인합니다. 즉, 첫번째 문장에 의해 인자가 0인지 먼저 확인해보고 그렇지 않은 경우에만 두번째 문장으로 넘어가므로, 자동적으로 두번째 문장은 "인자가 0이 아닌 임의의 자연수 n일 때"인 것으로 해석됩니다. 이 "순서"는 시시각각 상태를 바꾸는 순차적 대입과는 다른 개념으로서, 오히려 중첩된 if-then-else 문을 해석하는 순서 규칙에 더 가깝습니다.

참고: 관례적 집합 표기 문자들

관례적으로 '모든 자연수들만의 집합'을 흔히 로마자 대문자 N의 blackboard bold 형태인 $\mathbb{N}$이라고 표기하곤 하며, 유니코드 영역에도 별도의 문자(U+2115, 'ℕ')로 정의되어 있습니다.

단, LaTeX 수식 조판용 Computer Modern 글꼴이나 Latin Modern 글꼴로는 이 글자가 항상 일관성 있는 형태로 표시되지만, 다른 글꼴로는 표시되는 실제 형태가 글꼴마다 제각각일 수 있어서, 어떤 글꼴이 사용될지 모르는 웹 문서에 사용하기에는 적절하지 않습니다. 따라서, LaTeX을 사용할 수 없는 많은 경우에 이 문자 대신 그냥 로마자 N을 굵게 강조한 'N'이라고 표기하기도 합니다. 이 문서에서도 앞으로 간혹 정수들의 집합 $\mathbb{Z}$를 ℤ나 Z로, 실수들의 집합 $\mathbb{R}$을 ℝ이나 R표기할 수 있으니 참고로 알아두기 바랍니다.

함수들의 집합

그런데, 타입의 개념은 집합에 빗대어 생각할 수 있다고 했었습니다. 따라서, 앞 소절에서 소개했던 함수들의 타입도 일종의 집합이라는 뜻입니다. 즉, A → B가 일종의 집합이라는 뜻입니다. 어떤 집합일까요? 먼저 A와 B가 어떤 집합이었는지 다시 한 번 상기해드립니다:

  • A = { 10, 20 }
    B = { 1, 2 ,3 }

이제 다음 표기를 다시 잘 봅시다:

  • f : A → B
    f = { (10↦3), (20↦1) }

타입을 일종의 집합으로 생각한다면, 다음과 같이 바꿔서 쓸 수도 있어야합니다:

  • f ∈ A → B
    f = { (10↦3), (20↦1) }

즉, 최소한 함수 f 만큼은 반드시 원소로 갖는 집합이라는 뜻입니다. 여기서 가만히 생각해보면, A로부터 B로의 (즉, 타입이 A → B인) 함수는 f 말고 다른 함수도 있을 수 있습니다. 예를 들어, 아래에서 소개하는 g도 역시 A로부터 B로의 함수입니다:

  • g ∈ A → B
    g = { (10↦2), (20↦3) }

이런 식으로 생각해보면, A → B라는 집합은 A로부터 B로의 함수들을 모두 다 원소로 갖고있다는 뜻이고, 또한 그런 함수들만을 원소로 갖고 있다는 뜻입니다. A의 원소의 갯수 |A|=2이고 B의 원소의 갯수 |B|=3이므로, A로부터 B로의 함수는 |B||A|=32=9 종류가 가능합니다. 즉, A → B라는 집합은 다음과 같이 총 9개의 함수들을 원소로 갖는 집합입니다:

  • A → B = { {(10↦1), (20↦1)}, {(10↦1), (20↦2)}, {(10↦1), (20↦3)},
          {(10↦2), (20↦1)}, {(10↦2), (20↦2)}, {(10↦2), (20↦3)},
          {(10↦3), (20↦1)}, {(10↦3), (20↦2)}, {(10↦3), (20↦3)} }

도식화를 간단하게 하기 위한 좀 더 작은 예로서, X = {x1, x2}이고 Y = {y1, y2}라고 할 때 X → Y라는 집합은 다음과 같고:

  • X → Y = {{(x1,y1), (x2,y1)}, {(x1,y1), (x2,y2)}, {(x1,y2), (x2,y1)}, {(x1,y2), (x2,y2)}}

밴다이어그램으로 도식화하면 다음과 같습니다:
fromXtoY.png

이항 이상의 함수

위에서 살펴본 함수들은 모두 단항 함수였습니다. 그럼 이항 함수나 삼항 함수 등등의 타입은 어떻게 될까요?

예를 들어, 유한 집합 X, Y, Z가 있고 반드시 X 타입의 값 하나와 Y 타입의 값 하나를 모두 받아야만 작동하는 이항 함수 b는 다음과 같은 타입을 갖는다고 설명할 수 있습니다:

  • b : X × Y → Z
    b = { ((100,10)↦3), ((100,20)↦1), ..., ((300,50)↦2) }

즉, 이 함수 b는 정의역이 X와 Y의 데카르트 곱인 X × Y이고 공변역이 Z인 셈입니다. 삼항 함수도 마찬가지로 L×M×N을 정의역으로 갖는다는 식으로 설명할 수 있습니다.

사실 이 문제는, 언급하고 있는 문서마다 자신이 설정한 환경("setting"이라고 부릅니다)에 맞게 각각 적절히 조정해서 정하고 있습니다. 즉, "이항 함수의 타입은 반드시 이렇게만 표현된다"라고 단언할만한 유일한 정답 같은 것은 없으며, 그저 해당 문서 전체를 통털어 모순이 일어나지 않도록 잘 조정해서 약속해두기만 하면 그만입니다. 당장 위의 설명만 보아도, 누군가가 다음과 같이 문제를 삼을 여지가 충분히 있습니다:

  • "b가 X 타입의 값 하나랑 Y 타입의 값 하나, 이렇게 총 두 개의 인수를 받는 이항 함수라고? 글쎄? 내가 보기엔 여전히 그저 "X×Y 타입"의 값, 즉 "순서쌍" 하나를 받은 단항 함수인데?"

실제로, "모든 함수는 항상 고차 함수고, 모든 값은 항상 무항 상수 함수다"라고 설정(setting)되어있는 Haskell 같은 프로그래밍 언어에서는 위의 함수 b는 순서쌍 하나를 받는 단항 함수가 맞을 뿐만 아니라, 오히려 Haskell에는 단항 함수와 무항 함수만 있고 이항 이상의 함수는 존재하지 않습니다.

하지만 이런 세부 사항은 일단 현재로서는 "그런 경우도 있다더라"라고 참고로만 알아두시고, 지금 이 문서에서는 일단 이항 함수의 타입을 위와 같이 데카르트 곱을 이용해서 설명하는 것으로 약속하기로 합니다. 함수형 계산 모델과 함수형 프로그래밍 언어에 흔히 사용되는 고차 함수를 이해하는 데에는 이 정도 설명이면 현재로서는 충분합니다.

  1. 공변역 C의 값들 중에는 함수 f에 의한 대응에 참여하는 (f의 결과 값으로 리턴되는) 값들도 있고 그렇지 않은 값들도 있는데, 대응에 참여하는 값들만 모아놓은 집합은 함수 f의 치역range이라고 부릅니다. (1)