"Why numbering should start at zero"


1. 인덱스 넘버링


보통 프로그래밍 언어에는 자료구조로 사상되는 어떤 집합을 순회하면서 그 집합에서 꺼내온 원소를 가지고 정해진 연산을 차례대로 수행하기 위한 기능이 있습니다. 소위 반복문(For문)이라고 부르는 표현법입니다.


반복문을 쓸 때에는 집합의 어디서부터 어디까지 훑을 것인가 하는 인덱스의 범위(Range)를 지정하는데, 여기서 컴퓨터 과학자들이 즐겨 쓰는 관습이 하나 있습니다. 이 관습은 이제는 프로그래밍 언어를 겨우 배우기 시작한 사람들에게조차도 익숙할 만큼 대중적인 것으로 자리하고 있습니다.


그것은 두 가지로 구성됩니다.


1) Half-open interval: 인덱스는 시작 수는 포함하고 마지막 수는 제외한다.

2) Zero-based numbering: 첫 번째 인덱스는 0부터 시작한다.


예를 들어 10번 반복하고 싶다면 인덱스의 범위는 이것입니다. (인덱스는 정수입니다.)


0 <= index < 10


이 범위는 수학에서는 구간(Interval)으로 표현하고, 반닫힌 구간(Half-open interval)이라고 부릅니다.


[0, 10) "the half-open interval" (include lower bound, exclude upper bound)

[0, 9] "the closed interval"

(-1, 10) "the open interval"


C에서는 이렇게 씁니다.


for (i = 0; i < 10; ++i);


또 여러 언어에서 선형 자료구조의 부분집합을 취하는 경우에 이 규칙을 똑같이 적용하고 있습니다.


예를 들면 Python이나 Go 같은 언어에서 리스트(배열)를 슬라이싱할 때에도 인덱스가 시작하는 수는 포함하고 경계의 끝을 표시하는 마지막 수는 배제합니다. (슬라이싱이라는 기능도 내부적으로는 C의 반복문 같은 것으로 구현되어 있기 때문에 마찬가지 규칙이 적용되는 것입니다.)


arr[0:10]


그런데 문득 궁금해지는 것은 이렇게 하는 이유가 뭘까 하는 것입니다. 이런 전통을 준수하는 것이 어떤 가치가 있나요? 자문자답. 네. 이유가 있습니다.


2. 다익스트라의 노트


Zero-based Half-open 컨벤션에 관해서 다익스트라가 1982년에 자신의 단상을 산뜻한 자필로 정리한 기가 막힌 노트가 있습니다. '0부터 시작하고 마지막 수는 포함하지 않는 인덱스 넘버링'이 프로그래밍에 왜 가장 좋은 표현법인지에 대해 설명하는 내용입니다.


저는 이것을 웹에서 우연히 발견했어요. 다익스트라가 교수로 재직했던 텍사스 대학교에 이 서한이 남아있습니다. 아래는 링크입니다.



다익스트라가 누구냐. 엄청 멋있는 영향력 있는 사람이에요. 운영체제, 네트워크, 알고리즘 같은 굵직굵직한 과목의 전공서를 펼쳐 보면 (특히 운영체제) 온갖가지 논의에 관해서 이 분의 이름이 찍혀 있습니다. 전공 수업 들으면서 이 사람이 연구 안 해 본 게 뭘까 싶었어요. 컴퓨터 과학의 발전에 아주 많은 공헌을 하고 크게 기여하신 분입니다.



다음은 원고 본문입니다.





3. 해설 (Why numbering should start at zero)


다익스트라의 주장을 요약하면 다음과 같습니다.


  1. 인덱스의 구간을 표현할 때 이러저러한 이유로 [a,b) 컨벤션이 가장 보기 좋다.
    - Remark: 프로그래밍할 때도 이 컨벤션이 실제로 유익하다는 것이 실험적으로 증명된 사례가 있다.

  2. [a,b) 컨벤션을 쓸 때에는 0부터 시작해야 마지막 수가 N이 되어서 깔끔하다.
    - Remark: 포트란, 알골, 파스칼 같은 언어들은 이런 디테일을 놓치고 있다. 완전 별로다.

  3. 내가 이걸 설명하는 이유는 비전공자들이 우리의 표현 방식을 이해하지 못하기 때문이다.
    - 동료 교수가 컴퓨터 1도 모르는 수학과인데 우리 학생들이 습관적으로 0부터 넘버링하는 거 보고 쓸 데 없이 허세 부린다고 까더라.


평이하면서도 교양 있는 표현을 사용하는 이분의 언어를 제 식대로 풀이해 봤습니다.


1. 인덱스의 구간을 표현할 때 이러저러한 이유로 [a,b) 컨벤션이 가장 보기 좋다. Remark: 프로그래밍할 때도 이 컨벤션이 실제로 유익하다는 것이 실험적으로 증명된 사례가 있다.


왜 그런지 설명해 줌. 구간 나타낼 때 (a,b] [a,b) [a,b] (a,b) 네 가지 표현법이 있음.


근데 딱 봐도 반닫힌 구간이라고 하는 (a,b] [a,b) 이 둘이 기본적으로 가장 좋아 보임. 그 이유는 둘임.


1) 시작 수와 마지막 수의 차랑 집합의 크기가 같은 것은 반닫힌 구간임. 그러니까 (a,b] [a,b) 두 경우에 |a-b| = 크기 N임. 하지만 [a,b]는 |a-b| = N - 1이고 (a,b)는 |a-b| = N + 1임.


2) 그리고 집합을 붙일 때도 반닫힌 구간이 좋음. 인접한 두 집합을 붙였을 때 마지막 수와 시작 수가 같아서 깔끔함. [a,b) [a,b) [a,b) 이렇게 기차처럼 붙일 수 있음.


여기서 말하는 반닫힌 구간이 두 개가 있는데 [a,b) 이거랑 (a,b] 이거 중에 그럼 뭐가 더 좋은지 한 번 보자.


3) (a,b]이나 (a,b)처럼 인덱스가 시작 수를 포함하지 않는 컨벤션의 경우에, 가장 작은 자연수부터 시작하려면 가장 작은 자연수보다도 작은 수를 넣어야 해서 깔끔하지가 않음.


(주: 예를 들어 자연수가 0부터 시작한다면 0을 포함하는 집합을 표현하기 위해서 -1 < i 이 따위로 써야 함. 보기 싫음.)


4) (a,b]이나 [a,b]처럼 인덱스가 마지막 수를 포함하는 컨벤션의 경우에 가장 작은 자연수부터 시작한다면, 공집합을 표현하기 위해서 마지막 수에 가장 작은 자연수보다도 작은 수를 넣어야 해서 깔끔하지가 않음.


(주: 예를 들어 자연수가 0부터 시작한다면 공집합을 표현하기 위해서 i < -1 이 따위로 써야 함. 보기 싫음.)


그래서 1), 2), 3), 4)에 의해서 [a,b) 방식이 제일 좋음.


내가 이렇게만 말하면 너네 안 믿지.


Xerox PARC에서 Mesa라는 프로그래밍 언어 만들어서 사람들이 썼거든.


이 언어에는 (a,b] [a,b) [a,b] (a,b) 이 네 가지 컨벤션을 지원하는 특별한 문법이 있음.


근데 사람들이 이 언어 써 보다가 [a,b) 빼고 나머지가 지속적으로 오류를 유발하는 원인이라는 걸 결국 깨달음.


이를 계기로 Mesa 프로그래머들이 나머지 3개 문법을 쓰지 말자고 하고 사장시킴.


[a,b)가 제일 좋다는 게 실험으로 증명된 거임.


2. [a,b) 컨벤션을 쓸 때에는 0부터 시작해야 마지막 수가 N이 되어서 깔끔하다. Remark: 포트란, 알골, 파스칼 같은 언어들은 이런 디테일을 놓치고 있다. 완전 별로다.


[a,b) 이게 제일 좋다고 했잖아.


근데 시작 수가 1이라고 해 봐, 범위가 1 ≤ i < N+1이지.


하지만 시작 수가 0이면 0 ≤ i < N이 되어서 딱 떨어지고 깔끔하지.


즉 인덱스가 0부터 시작해야 마지막 수가 집합의 크기랑 같아져서 좋다는 거임.


여기서 알 수 있는 것 그러니까 결론은 0이야말로 가장 '자연스러운 수'고 자연수로 취급해야 한다는 사실이다. 사람들은 이걸 깨닫는 데에 수 세기가 걸렸음.


3. 내가 이걸 설명하는 이유는 비전공자들이 우리의 표현 방식을 이해하지 못하기 때문이다. 동료 교수가 컴퓨터 1도 모르는 수학과인데 우리 학생들이 습관적으로 0부터 넘버링하는 거 보고 쓸 데 없이 허세 부린다고 까더라.


자기 빡치게 하려고 일부러 그러는 줄 알던데 오해임.


그거 현학이 아니라 실제로 쓸 데가 있어서 그렇게 하는 거임.


난 우리 학생 편임.


"어떤 집단이 신봉하는 종교로부터 이단자가 추방되어야 하는 이유는 어디에서나 그렇듯이 그 사람이 틀렸을 수 있기 때문이 아니라 그 사람이 맞았을 수 있기 때문이다."[각주:1]는 Antony Jay의 격언에 백번 공감함.


(...)


잘 읽었소이다.


마지막으로 다익스트라의 2.번 주장이 약간 허전한 감이 있으니 C를 예로 들어서 부연설명을 조금 더 하겠습니다.


C에서는 배열의 순차적인 접근시에 포인터(Base)를 기준으로 오프셋을 나타내는 인덱스를 더해서 메모리의 상대적인 주소를 계산합니다.


이 때문에 C는 언어의 설계 단계에서 0부터 시작하는 넘버링이 뿌리를 내렸습니다. (좀 더 자세히는 C의 전신인 B언어와 BCPL로부터 물려받은 것입니다.)[각주:2]


예를 들어 포인터가 p라면 포인터 p로부터 배열의 상대적인 주소를 계산할 때 이렇게 되겠죠.


1번째 요소: p + 0

2번째 요소: p + 1

3번째 요소: p + 2

(...)

N번째 요소: p + (N - 1)


여기서 만약 1번째 요소가 p + 0가 아니라 p + 1이라면 p는 얘는 "OUT OF BOUND"로 가서 대체 뭘 가리키는 걸까 싶고 좀 헷갈릴 거에요.


그렇다고 인덱스 0번 요소의 존재를 인정은 하되 그냥 쓰지 않는다고 해 버리면 공간을 괜히 낭비하는 게 되고요.


그래서 0을 인덱스로 쓰는 건 맞습니다. 가장 자연스럽고 기본적인 수가 0이라는 것도 와닿습니다.


0을 써야 한다면 이 구간을 어떻게 표현하는 것이 좋은지는 정해져 있습니다.


인덱스의 시작하는 수가 가장 작은 자연수인 0이기 때문에 시작하는 수를 포함하는 것이 좋습니다.


그렇지 않은 경우 -1 < i이 되고 고작 -1 하나 때문에 부호 있는(Signed) 자료형을 끌고 올 것입니다. 그것은 메모리의 낭비입니다.


한편 인덱스가 시작하는 수를 포함하기 때문에 마지막 수는 포함하지 않는 것이 좋습니다.


배열의 마지막 요소가 집합의 크기 N보다 1 작은 수(N - 1)이기 때문에 N으로 딱 맞아 떨어질 수 있게 하는 것입니다.


이 경우 어떤 한 배열의 마지막 수가 그 배열에 인접한 바로 다음 배열의 시작 수가 되므로 여러 배열을 이어붙인 다차원 배열을 다룰 때에 편리합니다.


또 공집합을 표현하기 위해서 0 <= i < 0처럼 표현할 수 있는 이점이 있죠.


마지막 수를 포함하는 경우에는 공집합의 구간 표현이 0 <= i <= -1가 되어서 음수를 끌고 옵니다.


그러니까 [0,N)의 컨벤션을 사용하는 것이 가장 자연스럽다.


다익스트라가 하는 말이 그런 뜻입니다.


지금 포트란, 알골, 파스칼 다 망하고 C만 살아남았는데 이 과학자께서 그 이유를 예견했다고도 볼 수 있겠습니다.


참고: https://stackoverflow.com/questions/11364533/why-are-slice-and-range-upper-bound-exclusive


  1. "In corporate religions as in others, the heretic must be cast out not because of the probability that he is wrong but because of the possibility that he is right." 다익스트라가 좋아하고 즐겨 쓰는 인용 문구. [본문으로]
  2. https://en.wikipedia.org/wiki/Zero-based_numbering [본문으로]
Top