포괄적 프로그래밍과 표준 C++ 라이브러리

소개와 활용 II (학술주석판)

1998-09-01·김재우15 min read

STL은 재사용성이 뛰어난 다수의 포괄적 Container와 Algorithm으로 이루어져 있으며 Iterator에 의해 plug-in방식으로 결합된다. 포괄적 algorithm 그 자체는 함수인자를 일반화한 functor로 재사용성이 극대화된다.

이전 기사 오류 수정 #

오래 동안 기사를 연재하지 않아서 기억해 줄 독자가 있을 지도 의심스럽지만, 지난 연재 기사 290 쪽 오른쪽 단에 게시된 코드에서 default argument 기능을 사용하여 인터페이스를 간편하게 만들 수 있다는 설명은 명백한 오류다. ⊕ 저자가 자신의 오류를 직접 지적하는 것은 학문적 성실성을 보여줍니다. 1990년대 인쇄 매체에서 정정 기사를 쓰는 것은 비용이 상당했을 것입니다. 너무 쉬운 기능을 잘못 사용한 것이라서 설명하기도 어색하지만 혹시 독자 중에서 그와 같은 기능이 새로운 C++의 언어기능인가 하고 물어오는 분이 있을 까 싶어 부끄러움을 무릅쓰고 지적하지 않을 수 없었다. Default argument기능은 전과 같다. 단지 필자가 덤벙대다 실수한 것이다.

또 291쪽 오른쪽 상단에 게시된 accumulate의 코드에 실수가 있다.

int accumulate(…) { … for (…; next = succ(next)) { sum = binop(sum, id(next)); } …}

은

int accumulate(…) { … for (…; next = step(next)) { sum = binop(sum, term(next)); } …}

로 바뀌어야 한다. ⊕ 변수명 변경: succ(next) → step(next), id(next) → term(next). 이전 기사의 설계와 일관성을 맞추기 위한 수정입니다. 필자로서도 잘 이해가 가지 않는 일인데 코드를 옮겨 붙이면서 오류가 있었을 것이라 짐작할 뿐이다. 여하튼 거듭 독자에게 사과를 드리고 싶다. 특히 필자의 어설픈 글을 꼼꼼하게 읽어 보고 오류를 지적해준 독자, 신성전자의 프로그래머 정재선 씨에게 거듭 고마움을 전하고 싶다.

들어가면서 #

지난 연재 기사를 접한 독자들은 왜 STL을 구성하는 부품과 인터페이스를 직접 소개하지 않는 지 의문을 가질 수 있다. 필자의 대답은 간단하다. 그 상세한 사용법은 개발환경에서 제공하는 사용설명서가 가장 좋다는 것이다. ⊕ “공식 문서가 최고의 학습 자료"라는 원칙: 2024년에도 이는 유효합니다. Rust의 The Book, Python의 Official Documentation, C++의 cppreference.com이 모두 이 철학을 따릅니다. 좋은 저술가는 자신의 설명이 완벽하지 않음을 알고, 공식 자료로 유도합니다. 더욱이 세세한 인터페이스를 열거하기 위해서 지면을 낭비할 필요는 없을 것이다. 만일 사용하고 있는 개발환경이 믿을 만한 STL 구현이나 이를 포함하는 표준 라이브러리를 제공해 주지 않는 다 하더라도 크게 걱정할 필요는 없다. 인터넷 상에서 SGI STL, ObjectSpace Stadard Toolkit등 무료 표준 라이브러리의 배포본을 쉽게 구할 수 있고 포함된 설명서도 충분히 훌륭하다.

필자가 지면을 통해 얘기하고 싶은 것은 상세한 기능의 열거보다 표준 라이브러리를 잘 사용하는 데 기본이 되는 개념이다. 그러기 위해서는 STL의 설계원칙과 프로그래밍 형식을 이해하여야만 한다. 이미 거론한 바 있듯이 STL은 “포괄적 프로그래밍(generic programming)“을 이해하여야만 잘 사용할 수 있다. ⊕ Generic Programming의 정의: Alexander Stepanov와 Meng Lee가 정의한 패러다임으로, “임의의 타입에 대해 동작하는 재사용 가능한 코드 작성"을 의미합니다. 이는 OOP의 subtyping polymorphism과 정반대의 접근입니다. 참고: C++ - Generic Programming

그래서 필자는 가능한 독자들이 쉽게 공감할 수 있는 예제를 들어 지난 기사와 같은 방식으로 포괄적 프로그래밍 기법을 익히는 연습과정을 즐길 수 있도록 얘기를 풀어나가고 싶다. 또한, STL 그 자체는 C언어 정도의 표현력을 사용하는 경우에도 매우 유용한 라이브러리이며 애초부터 그렇게 설계되어 있다는 점을 강조하고 싶다. ⊕ C 레벨의 사용성: 이는 중요한 설계 원칙입니다. STL은 함수 포인터(C 스타일)로도 동작하고, 클래스 템플릿(C++ 스타일)로도 동작합니다. 이는 후방 호환성과 점진적 현대화를 동시에 가능하게 했습니다. 그러나 C++ 사용자라면 단순히 소극적인 응용에 그치지 말고 직접 새로운 함수나 컨테이너를 STL의 관례에 따라 만들어 보라고 권하고 싶다.

지난 호 기사에서 우리는 accumulate란 template 함수를 추상화하는 과정을 통해 포괄적 프로그래밍 기법을 부분적으로 논의하였다. 최종적인 해결책은 “원소의 생성과 처리과정을 추상화 해서, 원소를 만들어 내는 모듈(Generator)과 이를 처리하는 모듈을 분리(Algorithm)하자"는 것이었다. ⊕ Generator와 Algorithm의 분리: 이는 관심의 분리(Separation of Concerns, SoC) 원칙의 구체화입니다. 현대의 reactive programming (RxJS, Akka Streams) 에서도 source (generator)와 operator (algorithm)의 분리를 핵심 원칙으로 삼습니다. 그러나 이전의 accumulate는 여전히 배열이라는 특정한 컨테이너, 더 정확히 말하자면 특정 컨테이너 인터페이스에 종속한다는 단점이 있었다.

알고리즘, 즉 “처리과정이 컨테이너에 의존한다"는 말은 컨테이너마다 원소를 열거하는 방법에 차이가 있으며 알고리즘이 특정 컨테이너가 제공하는 원소 열거 인터페이스에 지나치게 의존하고 있다는 말이다. 원소의 열거과정이 열거된 원소의 처리 과정과 완전히 분리되지 않고서는 accumulate와 컨테이너 사이의 불필요한 의존관계를 없앨 수가 없다. 이를 극복하여 더욱 재사용성이 높은 accumulate를 개발하기 위해서는 공장의 대량 생산체계를 모방한 새로운 개념이 필요하고 결국 컨베이어 벨트를 모방하는 표현단위가 필요하다는 결론에 이르렀다. ⊕ Iterator가 Conveyor Belt인 이유: 1998년 당시 제조업이 한국 경제의 중심이었으므로, 공장 비유는 독자들에게 매우 자연스러웠을 것입니다. 이는 context-aware teaching의 좋은 예입니다. 현대에는 파이프라인(Unix pipes), 스트림(Java Streams), Observable (RxJS) 등의 비유를 사용합니다.

그러므로 임의의 컨테이너는 모두 컨베이어 벨트에 하나 씩 자신의 원소를 꺼내 놓을 수 있는 공통적인 방법을 제공하여야만 한다. 이와 같이 컨테이너와 알고리즘 사이의 불필요한 의존도를 크게 줄이고 임의의 컨테이너가 열거하는 원소를 임의의 알고리즘을 사용하여 처리할 수 있도록 하는 인터페이스가 바로 Iterator(열거자)다.

Iterator는 표준 라이브러리의 재사용성을 크게 높여주는 핵심적인 기능으로 Iterator 인터페이스를 잘 이해하고 사용법에 익숙해지는 것이 고급 표준 C++ 프로그래머가 되는 지름길이다. ⊕ Iterator 숙달의 중요성: 2024년의 C++20 ranges에서도 Iterator는 핵심입니다. 또한 Python (itertools), JavaScript (generators), Rust (iterators) 등 모든 현대 언어가 유사한 개념을 가집니다. 참고: cppreference: Iterators

Generic Programming #

More general, more reusable #

그렇다면 iterator의 개념이 어떻게 accumulate와 vector사이의 의존관계를 제거할 수 있을 까? 즉 어떻게 accumulate를 더욱 일반화하여 임의의 C를 위한 accumulate를 만들 수 있을 까? 한발 뒤로 물러서서 생각한다면 이 질문의 답은 “어떻게 서로 구현이 다른 컨테이너의 열거과정을 동일한 인터페이스로 추상화할 수 있을 까?“에 있다. Iterator는 다음 두 가지 연산을 적용할 수 있는 추상적 데이터형으로 볼 수 있으며 아래는 이 개념을 C++의 class로 표현한 것이다.

class Element;
class iterator {
    bool hasNext() const ; // 열거할 원소가 아직도 남아있는 가?
    const Element& nextElem() const ; // 원소의 추출과 Cursor의 이동
};

위의 인터페이스에는 두어가지 문제가 있다. 첫째, 특정 원소의 형과 의존 관계가 있다. 그러므로 다음과 같은 작업이 필요하다.

template<typename Element> // 인터페이스의 형 의존성을 제거한다.
class iterator {
    bool hasNext() const ;
    const Element& nextElem() const ;
};

두 번째 iterator는 본질적으로 특정 컨테이너의 구현에 의존할 수 밖에 없다. Iterator란 특정 컨테이너 열거 방식을 사용자에게 숨기는 데 목적이 있으므로 당연히 Iterator는 컨테이너의 내부 구현을 직접 사용해야 한다. ⊕ Iterator의 이중성: Iterator는 abstract interface이면서도, 실제 구현은 concrete container에 종속됩니다. 이를 “whitebox polymorphism"이라고도 합니다. 다시 말하자면 컨테이너와 분리해서 Iterator를 구현한다는 것은 최소한 바람직한 설계는 아니다. 만일 지난 번 기사에서 소개한 바 있는 vector class의 iterator 인터페이스를 설계한다면 다음과 같을 것이다.

template<class Element>
class iterator {
    …
public:
    iterator(const vector< Element >* rv);
    bool hasNext() const;
    const Element& nextElem() const;
};

이때 iterator ctor의 인자로 전달된 *rv가 iterator 객체를 소유하는 것으로 풀이할 수 있다. 눈치가 빠른 독자라면 위의 설계가 약간 문제가 있다는 점을 금방 알아차렸을 것이다. 위의 iterator class는 오로지 vector를 위한 iterator다. 즉, 특정 데이터 형에만 귀속하는 class를 전역으로 선언하는 것은 합리적인 인터페이스의 설계가 아닌 것이 분명하다. ⊕ Namespace 문제의 인식: Global namespace 오염을 피하기 위해 nested class를 제안합니다. 이는 나중에 C++98 표준에서 vector<T>::iterator 형태로 채택됩니다.

예를 들어 linked list 방식으로 구현되는 컨테이너의 iterator가 필요하다고 하자. 이미 만들어진 vector를 위한 iterator와 구분해야 하는 것은 당연한 사실이고 특정한 컨테이너를 위한 iterator를 구분하기 위하여 vector_iterator, list_iterator, tree_iterator 식으로 명칭을 변경할 필요가 있다. 그러므로 vector_iterator는 vector 컨테이너의 name space에 list_iterator는 list 내부에서 선언되어야 더욱 바람직하다. 그리고 이 같은 목적에 가장 적합한 언어기능이 nested class다.

// 아래의 코드는 충분히 안전성을 검증하지 않았다. 단지 독자에게 실감나는
// 예제를 보여주기 위해 급하게 쓴 것이므로 실험과 이해의 간단한 예로써 활용해 주기
// 바란다.

// File : vector.h
// Date : 1998/9
// Update : 1998/11
// Description :
//  Do not use this implementation for serious use.
//  This code is just written to show a visible example of container/iterator pattern to my readers.

template<typename T>
class vector {
    size_t _sz;
    T *_vec;
public:
    class iterator {
        const vector* _rv;
        mutable size_t _cursor;
    public:
        iterator(const vector* rv) : _rv(rv), _cursor(0) {}
        bool hasNext() const { return _cursor != _rv->size(); }
        const T& nextElem() const { return (*_rv)[ _cursor++ ]; }
    };

    typedef T value_type;
    explicit vector(size_t size, T init=T())
    : _sz( size )
    {
        _vec = new T[_sz];
        for (size_t i = 0; i < _sz; i++)
            _vec[ i ] = init;
    }
    ~vector() { delete[] _vec; }

    size_t size() const { return _sz; }
    const T& operator[](size_t i) const { return _vec[i]; }
    T& operator[](size_t i) { return _vec[i]; }
    const iterator elements() const { return iterator(this); }
};

이제 vector의 iterator 인터페이스를 이용해서 accumulate를 다시 구현할 수 있다.

template<typename BinFtor, typename UnaryFtor, typename CT,
    typename Element>
inline T
accumulate(BinFtor binop, Element id_elem, const CT& c, UnaryFtor term) {
    T sum = id_elem;
    typename CT::iterator cb = c.elements();
    while (cb.hasNext())
    {
        T e = cb.nextElem();
        sum = binop(sum, term(e));
    }
    return sum;
}

개선된 accumulate의 코드를 자세히 살펴보자. 독자들이 눈 여겨 보아야 할 점은 accumulate의 정의가 더 이상 특정 컨테이너의 열거방식과 무관하다는 점이다. 이제 accumulate는 어떤 컨테이너라 하더라도 내부에 iterator interface를 제공하기만 한다면 그대로 accumulate의 인자로 사용할 수 있다. 말 그대로 accumulate는 이제 정말 generic하다. ⊕ Duck Typing의 원칙: “Provides an iterator type, elements() method, and iterator with hasNext()/nextElem()“을 구현하면 accumulate에 사용 가능합니다. 이는 structural typing입니다.

실제의 Stdlib #

기본적인 이론과 용어: 형적 제약(Type constraints) #

더 체계적인 논의를 진행하려면 몇 가지 개념과 용어를 정의하고 넘어갈 필요가 있다. 이 단락에서 소개하는 용어는 SGI STL의 문서의 관례를 크게 참조했다. ⊕ SGI STL 문서: Matthew H. Austern이 작성한 SGI STL Documentation은 여전히 가장 명확한 STL 설명입니다. C++98 표준보다 더 읽기 쉬우며, 많은 현대 C++ 교재도 이를 참고합니다. SGI STL이 사용하는 용어는 표준과 다소 차이가 있으나 형식면에서나 의미론적 명세를 비교해 보더라도 표준문서보다 잘 정리되어있고 정확하다.

먼저, 컨테이너에는 아무 원소나 마구 집어넣을 수 없다는 점을 인식해야 한다. 컨테이너의 성질에 따라 집어넣을 수 있는 원소가 있고 그렇지 않은 원소가 있으므로 이러한 특성을 기술할 수 있는 방법이 있어야 편리하다. ⊕ Type Constraints의 필요성: 현대 C++20의 concept가 바로 이를 해결합니다. Rust의 traits, TypeScript의 generics constraints도 동일한 문제를 푸는 방식입니다. 참고: C++20 Concepts

예를 들어보자. C++ stdlib가 제공하는 컨테이너에 set이 있다. 수학에서 사용하는 집합의 개념을 따르자면 집합의 모든 원소를 정의하는 전체집합은 최소한 “같은 값인가"를 비교할 수 있는 어떤 집합이어야 한다. 이를 다시 우리가 채택한 표기를 사용하여 적어보면 set에서 E형에 속하는 e1,e2는 e1 == e2의 연산(인터페이스)을 적용(제공)할 수 있어야 한다는 말이다.

template<typename T> set { };
// T는 반드시 operator==을 정의하는 어떤 형이어야 하지만 ...

C++를 사용해서 T가 최소한 만족해야만 하는 조건을 언어수준에서 명시적으로 표현하는 방법이 없다. 물론 C++ 이외의 고급 프로그래밍 언어 중에는 “형적 제약 조건"을 프로그램 코드의 일부로 기술할 수 있는 언어가 있으며 컴파일러는 T가 지정된 조건을 만족하는 지를 정적으로 검사할 수 있다. ⊕ 다른 언어의 타입 제약 시스템: Haskell의 type classes, Scala의 implicit parameters, TypeScript의 generics constraints 모두 C++의 이 문제를 먼저 경험한 후 언어 설계에 반영했습니다.

필자는 만일 C++가 형 제약을 표현할 수 있었다면 아마 그 문법은 아래와 같지 않았을 까 생각한다.

template
< class T {
    operator==(const T&);
  };
>
class set {
...
};

위와 같은 표현이 가능하다면 C++의 template 기능은 더욱 반가운 기능이다. 그러나 현실은 위와 같은 기능이 없다는 것이고 그 대안으로 적용할 만한 별다른 프로그래밍 기법도 아직 발견되지 않았기 때문에 필요한 제약 조건을 명시하기 위하여 주석이나 문서에 의존하는 수 밖에 없다.

Assignable과 다른 Type Concepts #

아래와 같이 임의의 type T가 다음과 같은 연산자 인터페이스를 제공하고 그 의미를 준수한다면 “T는 Assignable"하다고 하고 “T ∈ Assignable"이라고 표기하기로 하자.

Let x, y ∈ T
    T(x), T t = x // copy ctor
    x = y // (canonical) assignment

이 제약이 필요한 예로 stdlib의 포괄적 연산 중에 swap을 들 수 있다.

std::swap( x, y )  /* <algorithm> */

swap에 적용되는 객체 x, y는 반드시 같은 형이어야 함은 물론이고 x, y ∈ T ∈ Assignable 해야 한다.

template <class T> inline void swap(T& a, T& b)  {
    T tmp = a; // copy ctor가 필요하다.
    a = b;
    b = tmp;
}

그러므로 줄여서 말하자면 “T ∈ Assignable"해야만 한다.

자주 사용하게 될 몇 가지 형 제약조건을 더 살펴보도록 하자.

T ∈ DefaultConstuctible
    T()

T ∈ EqualityComparable
    x == y
    x != y

T ∈ LessThanComparable
    x < y
    x > y
    x <= y
    x >= y, where x, y ∈ T

이제부터는 위에서 정의한 제약 조건의 이름을 사용하여 template 정의에 필요한 type 인자의 형 제약 조건을 간결하고 정확하게 적도록 노력할 필요가 있다.

결론: Iterator와 Contract #

이 섹션에서 저자가 강조하는 핵심은 **“명확한 계약(Contract)의 중요성”**입니다.

1998년의 관점:

• Template의 형 매개변수에는 조건이 있다
• 이를 문서와 주석으로 표현해야 한다
• 좋은 프로그래머는 이를 인식하고 문서화한다

2024년의 관점:

• C++20의 concepts가 이를 해결했다
• 하지만 좋은 문서화는 여전히 필수다
• Rust의 traits도 같은 원칙을 따른다

참고 문헌 및 웹 자료 #

원본 자료 #

• SGI STL Documentation - Alexander Stepanov와 Meng Lee의 원본 STL 문서
• Bjarne Stroustrup의 C++ 개인 사이트 - C++ 언어 설계 배경

C++98/03 표준 #

• Historical C++ Standards Documents - ISO C++ 위원회 공식 자료

현대 C++ 참고 자료 #

• cppreference.com - Iterators - 현대 Iterator 인터페이스
• cppreference.com - Concepts - C++20 Concepts
• cppreference.com - Type traits - Type system

관련 개념 및 패턴 #

• Design Patterns - Iterator Pattern - GoF 디자인 패턴
• Generic Programming Overview - Stroustrup의 Generic Programming 개요
• Type Classes in Haskell - 함수형 언어의 타입 제약 시스템

역사적 관점 #

• History of C++ - C++ 진화 과정
• The Evolution of C++ - Stroustrup의 강연

[다음 섹션: 3월 파일(Part III)의 주석으로 계속됩니다. Iterator categories, Traits pattern, Specialization 등의 고급 개념을 다룰 예정입니다.]