과연 버그없는 완벽한 프로그램이 존재할 수 있을까요?
요즘 임백준님의 '뉴욕의 프로그래머'라는 소설을 읽고 있습니다.
그 책에서 한 가지 실례를 들어서 소개된 부분을 이용해 블로그를 작성합니다.
이 코드에 오류가 있었다고 합니다. 여러분도 한번 찾아보세요.어디일까요?
java.util.Arrays 포함된 이진검색 알고리즘.
01:public static int binarySearch(int[] a, int key) {
02: int low = 0;
03: int high = a.length - 1;
04:
05: while (low <= high) {
06: int mid = (low + high) / 2;
07: int midVal = a[mid];
08:
09: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; //key found
15: }
16: return -(low + 1); //key not found.
17:}
조슈아 블로흐를 아십니까? [효과적인 자바(Effective Java)]를 쓴 사람이랍니다.
존 벤틀리는 교수이면서 [프로그래밍 펄(Programing Pearl)]의 저자 이구요.
위 코드는 조슈아 블로흐가 작성한 이진 검색(binary search) 프로그램입니다.
존 벤틀리 교수가 이진 검색(binary search)알고리즘을 유사코드(pseudo code)로 작성해 놓은 것을 참조하여 작성되었다고 합니다. 그런데 이 코드에 지금까지 밝혀지지 않았던 오류가 있었다고 하더군요.
여기서 잠깐 이진 검색(binary search)에 대해서 간단히 알아보겠습니다.
이진 검색은 정렬된 연속 리스트에서 원하는 값을 빠르게 찾기 위한 검색 알고리즘의 하나입니다. 즉 찾고자 하는 값(Key)을 가지고 리스트의 처음과 끝을 찾아내서 그 가운데 값(Value)과 비교합니다.
키보다 비교값이 크면 작은 쪽 리스트의 가운데로 이동합니다.
키보다 비교값이 작으면 보다 큰 쪽 리스트의 가운데로 이동합니다.
두 값이 같을 때까지 반복 작업을 수행합니다.
이 방법은 순차적으로 찾는 법보다 빠른 방법입니다.
벤틀리는 실제로 카네기멜론 대학 컴퓨터 공학 박사 과정에서 학생들에게 이진 검색 코드를 작성해보라는 과제를 낸 적이 있다고 합니다. 프로그램 바닥에서 날고 기는 전문가들이 코웃음을 치며 작성했던 코드는 온통 버그 투성이였다고 하더군요..
프로그래밍 펄에서 벤틀리가 했던 말입니다.
"프로그래머들은 이진 검색 알고리즘의 개요를 듣고 나면 그것을 실제로 프로그래밍을 하는 것은 어렵지 않다고 생각한다. 천만에 말씀이다. 내 말이 믿기지 않거든 이 책을 당장 내려놓고, 이진검색 코드를 작성해보라. 지금 당장 진짜로 해보라."
전산과 출신들은 잘 아시겠지만 알고리즘 시간이나 자료구조 시간에 늘상 듣던 게 바이너리 검색입니다. 정말 얘기를 듣는 동안엔 금방 만들 수 있을 것처럼 느껴지죠. 하지만 실제로 해보면 그렇게 쉽지만은 않습니다.
아래는 존 벤틀리 교수의 이진 검색(binary search) 유사코드(pseudo code)입니다.
l = 0; u = n-1
loop
{ mustbe(l, u) }
if l > u
p = -1; break
m = (l + u) / 2
case
x[m] < t; l = m + l
x[m] == t; p = m; break
x[m] > t; u = m - 1
이진 검색에 대한 소개는 이 정도로 하고 위 질문의 답을 적어야 하는 시간이 됐군요.
여러분은 찾으셨나요? 저는 설명을 듣고 나서야 알게 되었습니다.
답은 6번째 라인에 있었습니다. 잘 아시다시피 정수형 변수의 크기가 문제가 됩니다.
정수(int)형 변수 32bit 최대값은 -1, 혹은 2,147,483,647입니다. 20억을 조금 넘습니다.
지금까지는 그런 값이 들어갈만한 일이 없어서 아무도 모르고 지나갔던 것입니다.
그런데 밀리언단위에 빌리언단위로 바뀌고 기가바이트를 넘어 테라바이트로 가는 세상에선 그 배열의 mid값에 정수형 범위를 넘는 숫자가 배당되어질 때가 되어 버린 겁니다.
프로그램에서 overflow가 발생해서 음수 값이 할당되므로
a[mid] 에서 ArrayIndexOutOfBoundException이 발생합니다.
정말 아무도 코드를 보고는 찾아내지 못한 버그입니다. 누군가가 그런 값이 들어가는 검색을 돌렸고 거기서 버그의 존재가 나타난 겁니다. 아무도 그 상황이 되기 까지는 생각도 해보지 않은 일입니다. 정말 날고 기는 천재들인데도 말입니다.
이제 최초의 질문에 대한 답변을 해야 할 때가 왔군요. 정답은 "없다"입니다.
세상에 완벽한 그림, 음악, 소설이 없듯이 좀 더 비약하자면 완벽한 몸, 건물, 우주가 없듯이 세상에는 완벽이란 것이 존재하지 않습니다. 다만 우리에게는 완벽에의 의지와 모든 것이 변한다는 진행성의 진리만이 있을 뿐입니다.
이런 상황에서 우리가 할 수 있는 일은 무엇일까요?
더 많은 단위 테스트와 변경에 대한 시나리오. 완벽할 순 없지만 최대한 가능성이 높은 테스트 시나리오의 작성과 철저한 테스트가 아닐까 합니다.
사실 귀찮고 기간도 짧아서 특히 개발을 하기도 바쁜 일정에서는 테스트는 형식적인 부분이 대부분인 게 사실입니다만 다시 한번 테스트의 특히 단위 테스트의 중요성에 대해서 한 번 더 생각해 봐야 할 것 같습니다.
프로젝트 설계 단계에서 될 수 있으면 유닛 테스트의 단계를 프레임워크에 포함하고 자동화하여 쉽게 이용할 수 있게 한다면 더욱 좋겠지요.
결과 데이터가 나왔다고 다가 아닙니다. 어제 본 결과는 맞다고 생각하고 가볍게 넘겼는데 오늘 아침에 다시 본 결과값엔 오류가 숨어있었던 경험 있으실 겁니다.
역시 테스트! 테스트!
한 번 더 돌려보고 확인해 보고.
완벽할 수는 없지만 최소한으로 버그를 줄여나가는 노력.
그것이 우리가 할 수 있는 일이겠지요.
요즘 임백준님의 '뉴욕의 프로그래머'라는 소설을 읽고 있습니다.
그 책에서 한 가지 실례를 들어서 소개된 부분을 이용해 블로그를 작성합니다.
이 코드에 오류가 있었다고 합니다. 여러분도 한번 찾아보세요.어디일까요?
java.util.Arrays 포함된 이진검색 알고리즘.
01:public static int binarySearch(int[] a, int key) {
02: int low = 0;
03: int high = a.length - 1;
04:
05: while (low <= high) {
06: int mid = (low + high) / 2;
07: int midVal = a[mid];
08:
09: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; //key found
15: }
16: return -(low + 1); //key not found.
17:}
조슈아 블로흐를 아십니까? [효과적인 자바(Effective Java)]를 쓴 사람이랍니다.
존 벤틀리는 교수이면서 [프로그래밍 펄(Programing Pearl)]의 저자 이구요.
위 코드는 조슈아 블로흐가 작성한 이진 검색(binary search) 프로그램입니다.
존 벤틀리 교수가 이진 검색(binary search)알고리즘을 유사코드(pseudo code)로 작성해 놓은 것을 참조하여 작성되었다고 합니다. 그런데 이 코드에 지금까지 밝혀지지 않았던 오류가 있었다고 하더군요.
여기서 잠깐 이진 검색(binary search)에 대해서 간단히 알아보겠습니다.
이진 검색은 정렬된 연속 리스트에서 원하는 값을 빠르게 찾기 위한 검색 알고리즘의 하나입니다. 즉 찾고자 하는 값(Key)을 가지고 리스트의 처음과 끝을 찾아내서 그 가운데 값(Value)과 비교합니다.
키보다 비교값이 크면 작은 쪽 리스트의 가운데로 이동합니다.
키보다 비교값이 작으면 보다 큰 쪽 리스트의 가운데로 이동합니다.
두 값이 같을 때까지 반복 작업을 수행합니다.
이 방법은 순차적으로 찾는 법보다 빠른 방법입니다.
벤틀리는 실제로 카네기멜론 대학 컴퓨터 공학 박사 과정에서 학생들에게 이진 검색 코드를 작성해보라는 과제를 낸 적이 있다고 합니다. 프로그램 바닥에서 날고 기는 전문가들이 코웃음을 치며 작성했던 코드는 온통 버그 투성이였다고 하더군요..
프로그래밍 펄에서 벤틀리가 했던 말입니다.
"프로그래머들은 이진 검색 알고리즘의 개요를 듣고 나면 그것을 실제로 프로그래밍을 하는 것은 어렵지 않다고 생각한다. 천만에 말씀이다. 내 말이 믿기지 않거든 이 책을 당장 내려놓고, 이진검색 코드를 작성해보라. 지금 당장 진짜로 해보라."
전산과 출신들은 잘 아시겠지만 알고리즘 시간이나 자료구조 시간에 늘상 듣던 게 바이너리 검색입니다. 정말 얘기를 듣는 동안엔 금방 만들 수 있을 것처럼 느껴지죠. 하지만 실제로 해보면 그렇게 쉽지만은 않습니다.
아래는 존 벤틀리 교수의 이진 검색(binary search) 유사코드(pseudo code)입니다.
l = 0; u = n-1
loop
{ mustbe(l, u) }
if l > u
p = -1; break
m = (l + u) / 2
case
x[m] < t; l = m + l
x[m] == t; p = m; break
x[m] > t; u = m - 1
이진 검색에 대한 소개는 이 정도로 하고 위 질문의 답을 적어야 하는 시간이 됐군요.
여러분은 찾으셨나요? 저는 설명을 듣고 나서야 알게 되었습니다.
답은 6번째 라인에 있었습니다. 잘 아시다시피 정수형 변수의 크기가 문제가 됩니다.
정수(int)형 변수 32bit 최대값은 -1, 혹은 2,147,483,647입니다. 20억을 조금 넘습니다.
지금까지는 그런 값이 들어갈만한 일이 없어서 아무도 모르고 지나갔던 것입니다.
그런데 밀리언단위에 빌리언단위로 바뀌고 기가바이트를 넘어 테라바이트로 가는 세상에선 그 배열의 mid값에 정수형 범위를 넘는 숫자가 배당되어질 때가 되어 버린 겁니다.
프로그램에서 overflow가 발생해서 음수 값이 할당되므로
a[mid] 에서 ArrayIndexOutOfBoundException이 발생합니다.
정말 아무도 코드를 보고는 찾아내지 못한 버그입니다. 누군가가 그런 값이 들어가는 검색을 돌렸고 거기서 버그의 존재가 나타난 겁니다. 아무도 그 상황이 되기 까지는 생각도 해보지 않은 일입니다. 정말 날고 기는 천재들인데도 말입니다.
이제 최초의 질문에 대한 답변을 해야 할 때가 왔군요. 정답은 "없다"입니다.
세상에 완벽한 그림, 음악, 소설이 없듯이 좀 더 비약하자면 완벽한 몸, 건물, 우주가 없듯이 세상에는 완벽이란 것이 존재하지 않습니다. 다만 우리에게는 완벽에의 의지와 모든 것이 변한다는 진행성의 진리만이 있을 뿐입니다.
이런 상황에서 우리가 할 수 있는 일은 무엇일까요?
더 많은 단위 테스트와 변경에 대한 시나리오. 완벽할 순 없지만 최대한 가능성이 높은 테스트 시나리오의 작성과 철저한 테스트가 아닐까 합니다.
사실 귀찮고 기간도 짧아서 특히 개발을 하기도 바쁜 일정에서는 테스트는 형식적인 부분이 대부분인 게 사실입니다만 다시 한번 테스트의 특히 단위 테스트의 중요성에 대해서 한 번 더 생각해 봐야 할 것 같습니다.
프로젝트 설계 단계에서 될 수 있으면 유닛 테스트의 단계를 프레임워크에 포함하고 자동화하여 쉽게 이용할 수 있게 한다면 더욱 좋겠지요.
결과 데이터가 나왔다고 다가 아닙니다. 어제 본 결과는 맞다고 생각하고 가볍게 넘겼는데 오늘 아침에 다시 본 결과값엔 오류가 숨어있었던 경험 있으실 겁니다.
역시 테스트! 테스트!
한 번 더 돌려보고 확인해 보고.
완벽할 수는 없지만 최소한으로 버그를 줄여나가는 노력.
그것이 우리가 할 수 있는 일이겠지요.