아프니까 개발자다

얼마전 일입니다.

소스코드를 외부에 오픈하기 전, C코드를 위한 코딩 컨벤션을 정리하였습니다.

코딩 컨벤션은 비교적 의사소통이 잘되는 국내 개발자 뿐만 아니라-

상대적으로 소통이 적었던 해외 개발자에게도 전달되었습니다.

대부분의 규약들은 구렁이 담 넘어가듯 모두가 동의하였습니다.

하지만...

헝가리안 표기법 일부를 차용한 코딩 컨벤션에서,

해외 개발자의 문제제기를 시작으로 수많은 개발자들의 격렬한 논쟁이 시작되었습니다.

'70년대 감성을 갖고 있는 구닥다리 프로그래머'라든가

'읽기 힘든 코드를 끊임없이 양산해내는 두뇌파괴자'라는 식의 설전이 오고간 후,

우리는 헝가리안 표기법을 갖다버리기로 거국적으로 합의하였습니다.

그리고 아주 제한적인 경우에만 사용하기로 하였습니다.

목차격으로 마인드맵을 하나 붙입니다.

헝가리안 표기법이 혜성처럼 어느날 문득 시야에 나타난 것은 아닙니다.

타입시스템이 없는 BCPL(Before C Programming Language)과 같은 고대 언어에서는,

변수명으로 변수의 타입을 명시하여 사용하였습니다.

그러한 흐름이 자연스럽게 이어져,

70년대에 등장한 언어에서도 변수명에 타입이 함께 기입되었습니다.

설사 타입시스템이 있는 언어라 할지라도,

에디터나 컴파일러가 고도화되지 않은 환경에서는 변수명만으로 타입을 확정지을 수 있는 방식이 여러므로 유용하였습니다.

그 중 Smalltalk라는 객체지향언어에서는,

타입을 변수의 뒤에 붙여 기입하는 방식을 사용하였는데,

이는 유럽인들의 이름 뒤에 성이 오는 방식에서는 지극히 자연스러운 현상이었습니다.

타입은 일종의 가문과 같은 집단이라 볼 수 있으므로 변수고유의 이름과 타입이 순서대로 배치됩니다.

하지만, 유럽에서도 특이하게 성이 이름 앞에 오는 관습을 지닌 헝가리에서 온 청년-

Charles Simonyi이 타입을 앞에 붙이는 방식을 시전하게 됩니다.

80년대 마이크로소프트의 아키텍트가 된 Charles Simonyi은,

마이크로소프트에서 개발하는 앱의 기본 코딩컨벤션으로 자신이 제창한 헝가리안 표기법을 선정합니다.

컴파일러나 에디터가 아직은 조악했던 시절,

변수명만 가지고 타입을 확정지어 사용할 수 있는 방법은 여러므로 유용하였습니다.

코드작성자와 코드독해자가 동일한 헝가리안 표기법을 숙지하고 있다면,

변수의 타입을 해석하는데는 아무런 불편이 없습니다.

bBusy, chInitial, wCount, dwLength 등의 변수명만 보고도,

각각 bool, char, word, double word인 것을 파악할 수 있기에,

변수에 엉뚱한 값을 할당하는 실수를 예방할 수 있습니다.

이러한 점을 높이 사서,

마이크로소프트에서는 21세기 초반까지 헝가리안 표기법을 사용하고 지속적으로 권장하였습니다.

1999, "Hungarian notation... easier to write, and easier to read."^[각주:1]

그 결과,

헝가리안 표기법은 유행처럼 전세계 프로그래머들에게 퍼져나갔습니다.

학부 프로그래밍 강좌에서도 시험문제로 단골출제되었고,

전문프로그래머 사이에서는 지극히 당연한 교양처럼 여겨졌습니다.

80~90년대 격동의 학번을 경험한 중장년층 프로그래머들에게는 헝가리가 일종의 마음의 성지였죠.

하지만, 컴파일러는 더욱 똑똑해져서 컴파일 중에 수많은 warnings으로 개발자의 실수를 찾아주고,

에디터는 변수에 마우스 포인터를 갖다대는 것만으로 변수의 타입을 친절하게 팝업으로 보여주게 됩니다.

이러한 환경의 변화로 헝가리안 표기법에 대한 사람들의 인식도 바뀌어 갑니다.

2008, "Do not use Hungarian notation"^[각주:3]

2009, "vUsing adjHungarian nNotation vMakes nReading nCode adjDifficult."^[각주:4]

"변수명에 굳이 타입을 prefix로 붙여야만 할까요?"

2005년, <조엘 온 소프트웨어>로 유명세를 타고 있는 조엘 스폴스키는 자신의 블로그에서 포문을 열었습니다.

헝가리안 표기법의 창시자인 Charles Simonyi의 논문을 언급하며,

본래의 헝가리안 표기법은 단순히 타입을 반복하여 적는 것이 아니라고 주장했습니다.

단순히 타입을 반복하는 표기법을 시스템 헝가리안 표기법이라고 말하며,

그 대신 필수적으로 명시해야할 변수의 의미를 prefix로 표기하는 앱 헝가리안 표기법을 사용하라고 권장하였습니다.

이를테면,

count에 사용하는 변수엔 'n',

index에 사용하는 변수엔 'i',

두 변수값의 차이를 가지는 변수엔 difference의 약자인 'd',

database의 각 row에 해당하는 변수엔 row의 약자인 'rw',

code injection 등의 공격을 받을 수 있는 스트링 변수에는 unsafe의 약자인 'us'를 붙입니다.

앱 헝가리안 표기법은 통일된 prefix가 없습니다.

(혹은 모두가 합의하여 정리된 prefix가 없습니다.)

한 쪽에서는 치밀한 분석과 고민으로 prefix를 썼지만,

다른 쪽에서는 공유되지 않은 semantics로 해석하기 힘든 변수가 될 수 있습니다.

이에 따라 2008년에는 헝가리안 표기법을 널리 퍼뜨렸던 마이크로 소프트가,

.NET Framework 4.5 General coding conventions 에서 헝가리안 표기법을 사용하지 말라고 합니다.

그리고 온라인에서는 서서히 헝가리안 표기법을 조롱하며 웃는 분위기가 조성됩니다.

"vUsing adjHungarian nNotation vMakes nReading nCode adjDifficult."

위의 문장은 제법 유명세를 탔는데,

각 단어 앞에 헝가리안 표기법에 따라 동사, 부사, 명사 등을 나타내는 prefix를 붙였습니다.

읽기... 쉬운가요?

이런 상황에서 해외 개발자에게 헝가리안 표기법을 사용하자고 제안했으니,

'두뇌파괴자(brain breaker)'라는 소리를 들을만 했죠.

하지만, 그 와중에도 살아남아 고이 간직하게 된 헝가리안 표기법이 있습니다.

바로 변수의 scope를 나타내는 prefix.

local 변수에는 'l_'을,

argument 변수에는 'a_'를,

member 변수에는 'm_'을,

global 변수에는 'g_'를,

클래스 스태틱 변수에는 's_'를,

함수 스태틱 변수에는 'c_'를 붙입니다.

로컬변수와 아규먼트변수에 사용하는 prefix는 거의 사용하지 않지만,

나머지 것들은 아직도 코드에 살아남아 그 명맥을 유지하고 있습니다.

코딩 컨벤션이 뭐라고 조선시대에 벌인 예송논쟁처럼 수많은 개발자들이 핏대를 높였지만,

시대와 환경에 따라 유연하게 대처하며 사용하면 됩니다.

끝_

성격을 도무지 종잡을 수 없다고 하여,

'세 쌍둥이'로 불린 한 임원 분이 계셨습니다.

세 쌍둥이 중 첫째 분은 언제나 매우 인자한 미소로 '훌륭하다', '잘했다'를 연발하셨습니다.

둘째는 잔혹하고 포악하여 물건을 던지거나 육두문자를 섞어가며 인신공격을 하셨습니다.

셋째는 조울기가 다분하여 '분'단위로 성격이 바뀌어 어느 장단에 춤춰야할지 갈피를 잡을 수 없었습니다.

문제는 같은 내용의 보고를 해도,

어느 분을 만나느냐에 따라 결과가 달라진다는데 있었습니다.

그런 임원분에게 과감히 반론을 제기했다가 소리 소문도 없이 퇴직한 용자가 계셨습니다.

용자는 퇴직하기 직전,

한 책을 열심히 홍보하고 다니셨죠.

바로- <조엘 온 소프트웨어>

지금은 어디서 무얼 하고 있을지 모르는 용자를 기리며,

<조엘 온 소프트웨어>의 한 챕터에서 제시한 7가지 간단한 코딩문제를 풀어보겠습니다.

1. 원래 저장위치에서 문자열을 역순으로 변환하기

문자열을 역순으로 변환하려면,

- 문자열의 길이를 알아낸 후,

- 문자열의 첫번째 문자와 마지막 문자를 서로 교환하고,

- 문자열의 두번째 문자와 마지막 문자 - 1을 서로 교환하고...

위의 절차를 반복하면 됩니다.

int strrev(char *src)
{
    char *end_pointer = NULL;

    if (!src) return -1;
    if (!*src) return -1;

    end_pointer = src + strlen(src) - 1;

    while (src < end_pointer) {
        char tmp = *src;
        *src = *end_pointer;
        *end_pointer = tmp;
        src++;
        end_pointer--;
    }

    return 0;
}

$ ./test
origin word : (Hello)
reverse word : (olleH)

하지만, strrev는 바이트 단위로 swap하고 있기 때문에,

ASCII처럼 바이트당 한 글자가 지정된 코드페이지에서만  원하는 결과값을 얻을 수 있습니다.

유니코드 한글을 입력하면 아래처럼 엉뚱한 값이 찍히게 됩니다.

$ ./test
origin word : (안녕하세요.)
reverse word : (.��츄옕핅눕�)

이를 해결하기 위해서는 유니코드계열 함수를 사용하면 됩니다.

유니코드 관련 함수는 차후에 다시 다루기로 하죠. :)

2. 연결 리스트를 역순으로 만들기

연결리스트에 삽입된 n개의 노드를 모두 순회하기 위해서는 최소 n번 동안 한 노드에서 다음 노드로 이동해야 합니다.

총 3개의 노드로 이뤄진 아래 그림의 linked list를 보면,

first 노드에서 last 노드까지 3번의 노드간 이동으로 3개의 노드를 탐색하였습니다.

(first 노드에 다다르는 것도 한 번이라 셈함)

위의 linked list를 역순으로 배치하려면,

리스트를 순회하기 위해 소요되는 최소한의 횟수인-

'n'번(!) 이상 노드를 거치면서 loop를 돌아야합니다.

그렇게 하여 아래 그림처럼 next가 가리키는 노드의 방향을 바꿔야 합니다.

prev -> cur -> next로 이동하며 각각의 노드의 next 값을 아래의 루틴처럼 변경합니다.

다음에 탐색하여 나갈 다음 노드를 next 변수에 저장해두고,

현재(cur) node의 next를 이전(prev) 노드로 저장하고,

다음 순회 때에는 현재 노드가 이전(prev) 노드가 되고,

이전(prev) 노드가 현재(cur) 노드가 되어야 합니다.

typedef struct {
    void *data;
    node *next;
} node;

node *reverse_list(node *first)
{
    node *cur = first;
    node *prev = NULL;
    node *next = NULL;

    if (!first) return NULL;
    if (!first->next) return NULL;

    do {
        next = cur->next;
        cur->next = prev;

        prev = cur;
        cur = next;
    } while (next);

    return prev;
}

O(n)의 복잡도로 순회를 하며 리스트를 역순으로 변경합니다.

3. 한 바이트에서 1인 비트 세기

한 바이트 곧 8비트에서 1인 비트를 세려면,

비트를 하나씩 오른쪽으로 옮겨서 1과 &연산을 해보면 됩니다.

위의 옅은 파랑 영역이 1과 &연산을 하는 구역이다.

이를 코딩해보면 아래와 같습니다.

unsigned char count_bit(unsigned char number)
{
    unsigned char count = 0;

    while (number) {
        count += number & (unsigned char) 1;
        number = number >> 1;
    }

    return count;
}

'unsigned'는 오른쪽으로 shift 시에 가장 왼쪽에 있는 비트가 '0'으로 채워지게 합니다.

'signed' 타입은 가장 왼쪽의 비트가 '1'일 때,

오른쪽으로 shift시키면 다시 1로 채웁니다.

signed로 변수의 타입을 지정하고 while 루프를 돌리면,

'>>' 연산의 결과가 계속 1로 채워지기 때문에 무한루프에 빠지게 됩니다.

여기서 한 걸음 더 나아가-

비교적 작은 배열을 하나 만들어 캐싱을 해도 됩니다.

#define MAXIMUM 256
static struct {
    unsigned char count[MAXIMUM];
} s_info;

unsigned char count_bit(unsigned char number)
{
    unsigned char count = 0;

    while (number) {
        count += number & (unsigned char) 1;
        number = number >> 1;
    }

    return count;
}

void cache_bit(void)
{
    int i = 0;

    for (; i < MAXIMUM; i++) {
        s_info.count[i] = count_bit(i);
    }
}

최초 실행 직후 caching을 위한 배열을 구성합니다.

그 이후로는 캐싱된 배열에 접근하여 O(1)로 비트 개수를 얻습니다.

캐시를 한꺼번에 하지 않고 필요할 때마다 하나씩 할 수도 있을 것입니다.

어느 쪽이든 자기 상황에 맞게 구성하면 됩니다.

4. 이진 검색

이진검색은 O(logn)으로 데이타를 검색할 수 있습니다.

n개의 데이타 중에 검색하고자 하는 데이타를 순차적으로 찾으려면,

평균 n/2번 검색을 수행하고 나서야 데이타를 얻을 수 있습니다.

하지만, 순차탐색 대신 데이타가 속한 영역을 반씩 줄여가며 검색하고자 합니다.

이를 위해서는 먼저  데이타가 정렬되어 있어야만 합니다.

데이타가 삽입, 삭제, 갱신되는 시점에 데이타들은 reordering을 합니다.

그리고 검색하게 되면,

이진검색은 정렬된 n개의 데이타 중에 n/2번째에 위치한 데이타를 꺼내와서 찾고자 하는 데이타 value와 크기를 비교합니다.

if (value < (n/2)), value는 0과 n/2 사이에 있을테고,

else 라면, value은 n/2와 n 사이에 있겠죠.

위의 그림은 나름 worst case를 준비한 것입니다.

9개의 데이타 중 3번을 검색하여 1을 찾아내는 과정을 보여줍니다.

순차탐색에서는 한 번에 1을 찾아냈을 것입니다.

하지만, 이러한 극단적인 일부 케이스에서는 순차탐색이 더 좋을지는 몰라도 n의 갯수가 늘어날수록 이진검색의 위력이 세집니다.

int binary_search(int array[], int size, int value)
{
    int first = 0;
    int last = size - 1;
    int mid = 0;
    int i = 0;

    if (!array) return -1;
    if (size < 0) return -1;

    while (first != last) {
        mid = (first + last) / 2;
        if (array[mid] > value) {
            last = mid - 1;
        } else if (array[mid] < value) {
            first = mid + 1;
        } else {
            return mid;
        }
    }

    if (array[first] == value) return first;

    return -1;
}

이 함수에서는 검색한 값이 없을 경우 -1을 리턴하게 하였습니다.

5. 문자열에서 '연속적으로 문자가 반복되는 길이 run-length'가 가장 긴 부분문자열 찾기

첫번째 문자부터 마지막 문자까지 한 번만 훑는 평이한 알고리즘을 짜보았습니다.

이전 문자와 비교하여 같으면 count를 하나씩 올리도록 하였습니다.

O(n)보다 나은 알고리즘이 있을까요?

unsigned int count_longest_run_length(const char *string)
{
    unsigned int count = 1;
    unsigned int max = 0;
    char cur = 0;
    char pre = 0;
    
    if (!string) return 0;
    if (!*string) return 0;

    while (cur = *string) {
        if (cur == pre) {
            count++;
            if (max < count) max = count;
        } else {
            count = 1;
        }
        pre = cur;
        string++;
    }   

    return max;
}

6. atoi

ascii to integer. 아스키 문자열을 integer로 변환해주는 함수입니다.

문자열을 앞 부분부터 한 글자씩 읽어서 아스키 숫자값이 아니면 리턴합니다.

아스키 숫자인 경우에만 자릿수를 고려하여 더해줍니다.

int _atoi(const char *a)
{
    int i = 0;
    char tmp = 0;

    if (!a) return 0;
    if (!*a) return 0;

    while (tmp = *a) {
        tmp -= '0';
        if (tmp < 0 || tmp > 9) return 0;
        i = i * 10 + tmp;
        a++;
    }

    return i;
}

7. itoa (스택이나 strrev를 써야 하기 때문에 좋은 문제임)

integer to ascii. 정수형 integer를 radix 진수 문자열로 변환하는 간단한 함수를 만들어 보았습니다.

itoa는 (integer % 10) 나누어 최하위 자리부터 문자로 변환합니다.

따라서 최하위 -> 최상위로 변환작업을 마친 후 스택이나 strrev로 문자열을 뒤집어줘야 합니다.

아래 코드에서 strrev는 위의 1번에서 만들어둔 strrev를 그대로 사용하였습니다.

char *itoa(int integer, char *buf, int buf_size, int radix)
{
    int i = 0;

    if (!buf) return NULL;
    if (!buf_size) return NULL;
    if (radix <= 0) return NULL;

    for (; integer; i++, buf_size--) {
        if (!buf_size) return NULL;
        buf[i] = integer % radix + '0';
        integer /= radix;
    }   

    if (strrev(buf) < 0) {
        return NULL;
    }   

    return buf;
}