[edu] 인덱스 넘버링: 0부터 시작하고 마지막을 제외하는 이유

[인덱스 넘버링]

보통 프로그래밍 언어에서는 자료구조로 사상되는 어떤 집합을 순회하면서 그 집합에서 꺼내온 원소를 가지고

정해진 연산을 차례대로 수행하기 위한 기능이 있다.

소ㅜ이 반복문(for) 이라고 부르는 표현.

반복문을 쓸 때에는 집합의 어디서부터 어디까지 훓을 것인가 하는 인덱스의 범위(range)를 지정하는데

여기서 컴퓨터 과학자들이 즐겨 쓰는 관습이 하나 있다.

이것은 이제는 프로그래밍 언어를 처음 배우기 시작한 사람들에게 조차 익숙할 만큼 대중적인 것으로 자리 잡고 있다.

그것은 두가지로 구성된다.

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

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

예를 들어 10번 박복하고 싶다면 인덱스의 범위는 이렇게 된다.(인덱스는 정수)

0 <= index < 10

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

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

그럼 이렇게 하는 이유가 있는 것일까?

이유가 있다.

[다익스타르의 노트]

Zero-based Half-open 컨벤션에 관해서 다익스트라가 1982년에 자신의 단상을 산뜻한 자필로 정리한 기가 막힌 노트가 있다.

'0부터 시작하고 마지막 수는 포함하지 않는 인덱스 넘버링' 이 프로그래맹에 왜 가장 좋은 표현법인지 설명하는 내용이다.

관련링크

http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF

http://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

https://en.wikipedia.org/wiki/Edsger_W._Dijkstra

[다익스트라의 주장]

1. 인덱스 구간을 표현할 때 여러가지 이유로 [a, b) 컨벤션이 가장 보기 좋다.

> 프로그래밍할 때도 이 컨벤션이 실제로 유익하다는 것이 실험적으로 증명된 사례가 있다.

2. [a, b) 컨벤션을 쓸 때에는 0부터 시작해야 마지막 수가 N 이 되어서 깔끔하다.

> 포트란, 알골, 파스칼 같은 언어들은 이런 디테일을 놓치고 있다. 완전 별로다.

3. 비전공자들이 우리의 표현을 이해하지 못하기 때문이다.

> 동료교수가 컴퓨터 1도 모르는 수학과인데 우리 학생들이 습관적으로 0부터 넘버링 하는 거 보고 쓸데없이 허세부린다고 한다

1. 인덱스 구간을 표현할 때 여러가지 이유로 [a, b) 컨벤션이 가장 보기 좋다.

구간을 나타낼 때 (a,b][a,b)[a,b](a,b) 네가지 표현법이 있다.

이중 (a,b][ab) 둘이 기본적으로 좋아 보인다. 그 이유는 다음과 같다.

1) 시작 수와 마지막 수의 차랑 집합의 크기가 같은 것은 반닫힌 구간이다.

|a-b| = N 이기 때문이다. 다른건 |a-b|=N-1 이거나 |a-b|=N+1 이다.

2) 그리고 집합을 붙일 때도 반닫힌 구간이 좋다. 인접한 두 집합을 붙였을 때 마지막 수와 시작 수가 같아서 깔금하다.

0<= x < 5, 5<=y<10

이것처럼 두가지 집합을 붙여도 나란히 이어진다.

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

0 을 포함하려면, -1<i

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

0 부터 시작한다면 공집합을 표현하기 위해서 i<-1 이렇게 

Xerox PARC 에서 Mesa 라는 프로그래밍 언어 만들어서 사람들이 썻었다.

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

그런데 이 언어를 쓰다가 보니 [a,b) 빼고 나머지는 지속적으로 오류를 유발하는 원인이라는 걸 결국 깨달음

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

이것으로 [a,b) 가 게일 좋다는게 실험으로 증명됨.

2. [a, b) 컨벤션을 쓸 때에는 0부터 시작해야 마지막 수가 N 이 되어서 깔끔하다.

시작수가 예를 들어서 1이라고 하면

1 <= i < N+1

이것은 간결하지가 않다.

하지만 시작수가 0 이면

0 <= i < N

은 딱 떨어저서 간결하고 깔끔하다.

즉 인덱스가 0부터 시작해야 마지막 수가 집합의 크기랑 같아저서 가독성도 좋음

여기서 알 수 있는것 그러니까 결론은 0 이야말고 가장 자연스러운 수 이고 자연수로 취급해야 한다.

사람들은 이것을 깨닫는 데에 수 세기가 걸렸음.

3. 비전공자들이 우리의 표현을 이해하지 못하기 때문이다.

어떤 집단이 신봉하는 종교로부터 이단자가 추방되어야 하는 이유는 어디에서나 그렇듯이 그 사람이 틀렸을 수 있기 때문이 아니라 그 사람이 맞을 수 있기 때문이다. (Antony Jay의 격언) 

마지막으로 10진수도 0~9 의 숫자 2진수도 0~1 의 숫자를 사용한다.