왜 번호 매기기는 0부터 시작해야 하는가

한 페이지 반짜리 메모. 그러나 오늘날 C, Java, Python을 비롯한 거의 모든 언어가 배열을 0번부터 세는 이유가 여기 들어 있다.

발단은 사소한 다툼이었다. 다익스트라의 한 수학자 동료가 "감정적 폭발" 속에서 젊은 컴퓨팅 과학자들이 0부터 번호를 매긴다며 그들을 "현학적"이라고 비난했다. 다익스트라는 이 비난에 정면으로 답한다 — 0-기반 번호 매기기는 현학이 아니라, 가장 합리적인 관례의 의식적 채택이라고.

그의 논증은 두 단계로 진행된다. 먼저, 자연수의 부분 수열을 표기하는 네 가지 방법 중 어느 것이 우아한가? 그는 a) 2 ≤ i < 13 형태 — 하한은 포함하고 상한은 배제하는 반열린구간 — 이 최선임을 보인다. 두 가지 이유에서다. 첫째, 이 형태에서는 두 경계의 차이가 곧 수열의 길이다. 둘째, 가장 작은 자연수에서 시작하는 수열이나 빈 수열에서도 경계가 "부자연수"의 영역으로 밀려나지 않는다 — 보기 흉함이 없다.

그다음, 길이 N의 수열에 첨자를 붙일 때 시작 첨자를 무엇으로 할 것인가? 1로 시작하면 범위는 1 ≤ i < N+1이라는 어색한 모양이 된다. 0으로 시작하면 0 ≤ i < N이라는 깔끔한 모양이 된다. 그리고 가장 아름다운 한 줄 — 요소의 첨자는 그것 앞에 오는 요소의 개수와 같다.

이 짧은 글이 보여주는 것은 다익스트라의 방법론 그 자체다. 취향이나 관습이 아니라, "보기 흉함(ugliness)"을 명시적 기준으로 삼아 네 후보를 차례로 탈락시키고, 단 하나의 우아한 선택에 도달한다. 그는 Mesa 언어의 경험적 증거 — 다른 세 관례가 "투박함과 실수의 지속적 원천"이었다 — 까지 인용한다. 그리고 마지막으로 앤터니 제이를 빌려 쏘아붙인다. "이단자는 그가 틀렸다는 가능성 때문이 아니라, 그가 옳다는 가능성 때문에 추방되어야 한다."

자연수 2, 3, ..., 12의 부분 수열을 나타내기 위해 (교활한 점 세 개 없이) 네 가지 관례가 우리에게 열려 있다:

어떤 관례를 다른 것보다 선호할 이유가 있을까? 그렇다, 있다. a)와 b) 관례가 언급된 경계 사이의 차이가 부분 수열의 길이와 같다는 장점을 가진다는 관찰이 있다. 결과적으로, 이 두 관례 중 하나에서는 두 부분 수열이 인접한다는 것은 한 쪽의 상한이 다른 쪽의 하한과 같다는 것을 의미한다. 이러한 관찰들이 타당하기는 하지만, a)와 b) 중에서 선택하는 데는 도움이 되지 않는다. 그러니 다시 시작해 보자.

가장 작은 자연수가 있다. 하한의 배제 — b)와 d)에서처럼 — 는 가장 작은 자연수에서 시작하는 부분 수열에 대해 언급된 하한을 부자연수의 영역으로 강제한다. 그것은 보기 흉하므로, 하한에 대해서는 a)와 c)에서처럼 ≤를 선호한다.

이제 가장 작은 자연수에서 시작하는 부분 수열을 고려해 보자. 상한의 포함은 수열이 빈 것으로 축소될 때까지 후자를 부자연스럽게 만들 것이다. 그것은 보기 흉하므로, 상한에 대해서는 a)와 d)에서처럼 < 를 선호한다. 우리는 관례 a)가 선호되어야 한다고 결론짓는다.

비고. Xerox PARC에서 개발된 프로그래밍 언어 Mesa는 네 가지 관례 모두에서 정수 구간에 대한 특별한 표기법을 가지고 있다. Mesa에 대한 광범위한 경험은 다른 세 가지 관례의 사용이 투박함과 실수의 지속적인 원천이었음을 보여주었고, 그 경험을 바탕으로 Mesa 프로그래머들은 이제 후자의 세 가지 기능을 사용하지 말 것을 강력히 권고받고 있다. 나는 이 실험적 증거를 언급한다 — 그것이 가치 있는 것을 위해 — 실제로 확인되지 않은 결론에 사람들이 불편함을 느끼기 때문이다.

길이 N의 수열을 다룰 때, 우리가 아래 첨자로 구별하고자 하는 요소들에 대해, 다음으로 성가신 질문은 그 시작 요소에 어떤 아래 첨자 값을 할당할 것인가이다. 관례 a)를 고수하면, 아래 첨자 1로 시작할 때 아래 첨자 범위 1 ≤ i < N+1이 생긴다. 그러나 0으로 시작하면 더 좋은 범위 0 ≤ i < N이 생긴다.

그러므로 우리의 서수를 0에서 시작하게 하자. 요소의 서수(아래 첨자)는 수열에서 그것 앞에 오는 요소의 수와 같다. 그리고 이야기의 교훈은 우리가 — 그 모든 세기들이 지난 후에! — 0을 가장 자연스러운 수로 간주하는 것이 더 낫다는 것이다.

비고. 많은 프로그래밍 언어들이 이 세부사항에 대한 적절한 주의 없이 설계되었다. FORTRAN에서는 아래 첨자가 항상 1에서 시작한다. ALGOL 60과 PASCAL에서는 관례 c)가 채택되었다. 더 최근의 SASL은 FORTRAN 관례로 되돌아갔다 — SASL에서 수열은 동시에 양의 정수에 대한 함수이다. 이런!

위의 내용은 최근의 사건에 의해 촉발되었다. 감정적 폭발 속에서, 대학의 한 수학 동료 — 컴퓨팅 과학자가 아닌 — 가 많은 젊은 컴퓨팅 과학자들을 "현학적"이라고 비난했다 — 그들이 습관적으로 하는 것처럼 — 그들이 0에서 번호 매기기를 시작했기 때문이다. 그는 도발로서 가장 합리적인 관례를 의식적으로 채택한 것을 이용했다.

나는 앤터니 제이(Antony Jay)가 "기업의 종교에서 다른 종교들처럼, 이단자는 그가 틀렸다는 가능성 때문이 아니라 그가 옳다는 가능성 때문에 추방되어야 한다"고 말할 때 옳다고 생각한다.

다익스트라의 논증을 눈으로 확인해 보자. 네 가지 표기 관례를 같은 수열에 적용하면, a) 형태 a ≤ i < b만이 세 가지 우아한 성질을 동시에 갖는다 — 경계의 차이가 곧 길이이고, 인접한 두 수열이 경계 하나를 공유하며, 빈 수열에서도 경계가 "부자연수"로 밀려나지 않는다. 아래 모션은 이 세 성질을 차례로 보여준다.