닫힘 성질을 충족하는 데이터 구조 설계(1)

데이터 추상화(data abstraction)란?

어떠한 복합 데이터 객체가 쓰이는 방식과 그 복합 데이터를 좀 더 기본적인 데이터 객체들로 구축하는 구체적인 방식을 분리할 수 있게 하는 방법론.
복합 데이터 객체를 사용하는 프로그램이 추상데이터에 대해 작동하도록 프로그램의 구조를 짜는 것이 핵심이다.
구체적 데이터 표현 <-> 데이터를 사용하는 프로그램간의 인터페이스는 선택자 함수와 생성자 함수의 집합으로 구성된다.

데이터 = 선택자함수 + 생성자함수 + 유효한 표현을 위해 그 함수들이 반드시 충족하는 조건들의 집합

데이터 추상화의 이득

• 데이터의 구체적인 표현 방식에 구애받지 않고 프로그램을 설계할 수 있다.
• 여러가지 대안 표현을 자유로이 실험할 수 있는 유연성이 생긴다.

위계적 자료구조

위계적(hierarchical) 자료구조란 그것을 구성하는 부품들 자체가 또 다른 부품들로 구성되며, 그 부품 역시 또 다른 부품들로 구성되는 식으로 이어지는 자료구조를 말한다.

닫힘 성질(closure property)

데이터 객체들을 조합하는 연산이 있을 때, 만일 그 연산으로 조합한 결과들을 다시 그 연산으로 조합할 수 있다면 그 연산은 닫힘 성질을 충족한다.

A구조를 갖는 데이터에 B라는 연산을 적용한 결과가 다시 A구조를 가진다 = A구조의 데이터는 B에 대해 닫힘 성질을 충족한다.

여기서 closure(닫힘)은 추상 대수학의 용어이다. 수학에서 어떤 집합과 어떤 연산이 있을 때, 만일 그 연산을 집합의 원소들에 적용한 결과가 항상 그 집합의 원소이면 그 집합이 그 연산에 대해 닫혀 있다고 말한다.
(참고) 지역범위에서 정의되지 않은 외부변수로의 참조를 가진 함수를 표현하는 구현 기법을 말하는 프로그래밍 언어에서의 closure와는 완전히 무관한 개념이다.

예시 - 쌍 객체

두개의 데이터를 가지는 쌍 객체 pair(a,b)를 생각해 보자.
생성자 : pair(h,t)
선택자 : head(p), tail(p)

function pair(x, y) {
    function dispatch(m) {
        return m === 0 
               ? x
               : m === 1
               ? y
               : error(m, "argument not 0 or 1 -- pair");
    }
    return dispatch;    
}
function head(z) { return z(0); }

function tail(z) { return z(1); }

const x = pair(1, 2);

console.log(head(x)); // 1
console.log(tail(x)); // 2

이처럼 추가적인 자료구조를 사용하지 않고도 원시값과 함수만으로 복합 데이터 객체를 설계할 수 있다.

이런 복합 데이터 객체는 상자-포인터 표기법으로 시각화 할 수 있다.

왼쪽부분은 head, 오른쪽 부분은 tail 이다.

pair(1, 2)의 상자-포인터 표현

이 pair를 수치뿐 아니라 다른 쌍 객체를 조합하는데에도 사용할 수 있다.

다음그림은 pair객체를 이용하여 1,2,3,4를 조합하는 예시를 보여준다.

쌍 객체가 구성요소인 쌍을 생성하는 능력은 pair의 닫힘 성질을 보여준다.

이 닫힘 성질 덕분에 위계적 자료 구조를 생성할 수 있다는 점에서, 닫힘은 모든 조합 수단의 조합 능력에 핵심인 성질이다.

순차열의 표현

쌍 객체로 구축할 수 있는 유용한 자료 구조로 순차열(sequence)이 있다. 순차열은 여러 데이터 객체가 특정 순서로 나열된 구조이다.

각 쌍 객체의 head는 해당 수치, tail은 사슬의 다음 쌍을 가리키도록하며 마지막 쌍의 tail에는 null값이 배치되며 그 쌍이 순차열의 끝임을 나타낼 수 있다.

가령 1, 2, 3, 4의 순차열을 생성하려면 다음같이 중첩된 pair 연산을 사용하여 나타내면 된다.

pair(1, pair(2, pair(3, pair(4, null))));

이처럼 중첩된 pair 적용으로 만든 쌍 객체들의 순차열을 목록(list)이라고 부른다. 이 목록객체의 생성을 돕기 위해서 list() 생성자 함수도 정의해 볼 수 있을 것이다.

list(a, b, c, ...) === pair(a, pair(b, pair(c, ...)...))