추상 자료형
컴퓨터 과학에서 추상 자료형(abstract data type, ADT)은 자료형에 대한 수학적 모델이며, 데이터 사용자의 관점에서 동작(의미론)에 따라 정의된다. 특히 가능한 값, 이 유형의 데이터에 대한 가능한 연산, 그리고 이러한 연산의 동작 측면에서 정의된다. 이 수학적 모델은 데이터의 구체적인 표현이며 사용자가 아닌 구현자의 관점인 자료 구조와 대조된다. 예를 들어, 스택은 후입선출 규칙을 따르는 푸시/팝 연산을 가지며, 리스트나 배열을 사용하여 구체적으로 구현될 수 있다. 또 다른 예로는 어떠한 특정 순서 없이 값을 저장하고, 반복되는 값이 없는 집합이 있다. 값 자체는 집합에서 검색되지 않고, 오히려 값의 멤버십을 테스트하여 부울 "포함" 또는 "미포함"을 얻는다.
ADT는 공식 의미론 및 프로그램 형식 검증에 사용되는 이론적 개념이며, 덜 엄격하게는 알고리즘, 자료 구조 및 소프트웨어 시스템의 설계 및 분석에 사용된다. 대부분의 주류 컴퓨터 언어는 ADT를 공식적으로 지정하는 것을 직접적으로 지원하지 않는다. 그러나 다양한 언어 기능은 ADT 구현의 특정 측면과 관련되어 있으며, 추상형, 불투명 자료형, 프로토콜, 계약에 의한 설계를 포함하여 ADT 자체와 쉽게 혼동될 수 있다. 예를 들어, 모듈 프로그래밍에서 모듈은 ADT 연산에 해당하는 프로시저를 선언하며, 종종 제약 조건을 설명하는 주석과 함께 사용된다. 이 정보 은닉 전략은 클라이언트 프로그램을 방해하지 않고 모듈의 구현을 변경할 수 있도록 하지만, 모듈은 ADT를 비공식적으로만 정의한다. 추상 자료형의 개념은 객체 지향 프로그래밍 및 소프트웨어 공학을 위한 계약에 의한 설계 방법론에서 중요한 데이터 추상화 개념과 관련이 있다.[1]
역사
[편집]ADT는 1974년 바바라 리스코프와 스티븐 N. 질레스가 CLU 언어 개발의 일환으로 처음 제안했다.[2] 대수적 명세는 1980년경 컴퓨터 과학 연구의 중요한 주제였으며 그 당시 추상 자료형과 거의 동의어였다.[3] 이는 보편대수학에 수학적 기반을 두고 있다.[4]
정의
[편집]형식적으로, ADT는 수학의 대수 구조와 유사하며,[5] 도메인, 연산들의 모음, 그리고 연산들이 만족해야 하는 제약 조건 집합으로 구성된다.[6] 도메인은 종종 암시적으로 정의되며, 예를 들어 ADT 연산 집합에 대한 자유 대상이다. ADT의 인터페이스는 일반적으로 도메인 및 연산, 그리고 연산에 대한 일부 제약 조건(예: 사전 조건 및 사후 조건)만을 참조하지만, 동작으로 간주되는 연산 간의 관계와 같은 다른 제약 조건은 참조하지 않는다. 동작에 대한 형식적 명세에는 공리적 의미론과 동작적 의미론이라는 두 가지 주요 스타일이 있다.[7]
인터페이스의 일부는 아니지만, 제약 조건은 ADT 정의에 여전히 중요하다. 예를 들어, 스택과 큐는 유사한 요소 추가/요소 제거 인터페이스를 가지고 있지만, 후입선출과 선입선출 동작을 구분하는 것은 제약 조건이다. 제약 조건은 fetch(store(S,v))=v와 같은 방정식뿐만 아니라 논리식으로도 구성된다.
동작적 의미론
[편집]명령형 프로그래밍의 정신에서, 추상 자료 구조는 가변적인 엔티티로 간주된다. 즉, 시간의 개념이 있으며 ADT는 다른 시점에 다른 상태에 있을 수 있다. 그러면 연산은 시간 경과에 따라 ADT의 상태를 변경한다. 따라서 연산이 평가되는 순서가 중요하며, 동일한 엔티티에 대한 동일한 연산이라도 다른 시점에 실행되면 다른 효과를 가질 수 있다. 이는 컴퓨터의 명령어 또는 명령형 언어의 명령 및 프로시저와 유사하다. 이러한 관점을 강조하기 위해, 추상 알고리즘을 설명할 때 자주 사용되는 명령형 스타일과 유사하게, 연산이 평가되기보다는 실행되거나 적용된다고 말하는 것이 관례이다. 제약 조건은 일반적으로 산문으로 지정된다.
보조 연산
[편집]ADT의 표시는 종종 핵심 연산으로만 범위가 제한된다. 더 자세한 표시는 종종 ADT에 대한 보조 연산을 지정한다. 예를 들면:
create(): ADT의 새 인스턴스를 생성한다.compare(s, t): 두 인스턴스의 상태가 어떤 의미에서 동일한지 테스트한다.hash(s): 인스턴스의 상태에서 일부 표준 해시 함수를 계산한다.print(s)또는show(s): 인스턴스의 상태를 사람이 읽을 수 있는 형태로 출력한다.
이러한 이름은 예시적인 것이며 저자마다 다를 수 있다. 명령형 스타일 ADT 정의에서는 종종 다음도 찾을 수 있다.
initialize(s): 새로 생성된 인스턴스s를 추가 연산을 위해 준비하거나, 일부 "초기 상태"로 재설정한다.copy(s): 인스턴스s를t와 동일한 상태로 만든다.clone(t):s←create(),copy(s, t)를 수행하고s를 반환한다.free(s)또는destroy(s):s가 사용한 메모리 및 기타 리소스를 해제한다.
free 연산은 일반적으로 관련성이 없거나 의미가 없다. ADT는 "메모리를 사용하지 않는" 이론적 엔티티이기 때문이다. 그러나 ADT를 사용하는 알고리즘이 사용하는 저장 공간을 분석해야 할 때 필요할 수 있다. 이 경우, 각 ADT 인스턴스가 상태의 함수로 얼마나 많은 메모리를 사용하는지, 그리고 free에 의해 얼마나 많은 메모리가 풀로 반환되는지 지정하는 추가 공리가 필요하다.
제한된 유형
[편집]ADT의 정의는 종종 인스턴스에 저장된 값을 해당 변수의 범위라고 불리는 특정 집합 X의 멤버로 제한한다. 예를 들어, 추상 변수는 정수만 저장하도록 제약될 수 있다. 프로그래밍 언어에서와 마찬가지로 이러한 제한은 설명 및 알고리즘 분석을 단순화하고 가독성을 향상시킬 수 있다.
별칭
[편집]동작적 스타일에서는 여러 인스턴스가 어떻게 처리되는지, 그리고 하나의 인스턴스를 수정하는 것이 다른 인스턴스에 영향을 미칠 수 있는지 여부가 종종 불분명하다. ADT를 정의하는 일반적인 스타일은 알고리즘 실행 중에 하나의 인스턴스만 존재하고 모든 연산이 해당 인스턴스에 적용되는 것처럼 연산을 작성한다. 예를 들어, 스택에는 유일하게 존재하는 스택에 대해 작동하는 push(x) 및 pop() 연산이 있을 수 있다. 이 스타일의 ADT 정의는 암시적 인스턴스를 사용하거나 수정하는 모든 연산에 명시적 인스턴스 매개변수(아래 스택 예제의 S와 같은)를 추가하여 여러 동시 인스턴스를 허용하도록 쉽게 재작성할 수 있다. 일부 ADT는 여러 인스턴스를 허용하지 않고는 의미 있게 정의될 수 없다. 예를 들어, 단일 연산이 ADT의 두 가지 다른 인스턴스를 매개변수로 취하는 경우(예: 집합에 대한 union 연산 또는 리스트에 대한 compare 연산)이다.
다중 인스턴스 스타일은 때때로 별칭 공리와 결합되는데, 이는 create()의 결과가 알고리즘에서 이미 사용 중인 다른 인스턴스와는 구별된다는 것이다. ADT 구현은 여전히 메모리를 재사용하고 create() 구현이 이전에 생성된 인스턴스를 생성하도록 허용할 수 있다. 그러나 그러한 인스턴스가 "재사용"된다고 정의하는 것은 ADT 형식론에서는 어렵다.
더 일반적으로, 이 공리는 다른 인스턴스와의 부분적 별칭을 제외하도록 강화될 수 있으므로 복합 ADT(예: 트리 또는 레코드) 및 참조 스타일 ADT(예: 포인터)는 완전히 분리된 것으로 가정할 수 있다. 예를 들어, 추상 변수의 정의를 추상 레코드를 포함하도록 확장할 때, 레코드 변수 R의 필드 F에 대한 연산은 분명히 F를 포함하며, F는 R과 구별되지만 R의 일부이기도 하다. 부분적 별칭 공리는 하나의 레코드 변수의 필드를 변경하는 것이 다른 레코드에 영향을 미치지 않는다고 명시한다.
복잡도 분석
[편집]일부 저자들은 알고리즘 분석을 돕기 위해 각 연산의 계산 복잡도(연산 계산을 위한 시간과 값 표현을 위한 공간 모두)를 포함하기도 한다. 예를 들어, 각 연산이 ADT의 상태에 관계없이 동일한 시간을 소비하고 각 값이 동일한 공간을 소비한다고 지정하거나, ADT의 "크기"가 있으며 연산이 ADT 크기에 선형적, 이차적 등으로 지정할 수 있다. C++ 표준 템플릿 라이브러리의 설계자인 알렉산더 스테파노프는 STL 명세에 복잡도 보장을 포함하며 다음과 같이 주장했다.
추상 자료형의 개념을 도입한 이유는 교환 가능한 소프트웨어 모듈을 허용하기 위함이었습니다. 이 모듈들이 유사한 복잡도 동작을 공유하지 않으면 교환 가능한 모듈을 가질 수 없습니다. 만약 동일한 기능적 동작을 가지지만 다른 복잡도 트레이드오프를 가진 다른 모듈로 하나의 모듈을 교체한다면, 이 코드의 사용자는 불쾌하게 놀랄 것입니다. 저는 데이터 추상화에 대해 무엇이든 말할 수 있지만, 그는 여전히 코드를 사용하고 싶지 않을 것입니다. 복잡도 주장은 인터페이스의 일부여야 합니다.
— 알렉산더 스테파노프[8]
다른 저자들은 연산 비용의 차이에도 불구하고 스택 ADT는 연결 리스트로 구현되든 배열로 구현되든 동일하며, ADT 명세는 구현과 독립적이어야 한다고 주장하며 동의하지 않는다.
예시
[편집]추상 변수
[편집]추상 변수는 가장 단순한 비자명 ADT로 간주될 수 있으며, 명령형 변수의 의미론을 가진다. 이 변수는 fetch와 store의 두 가지 연산을 허용한다. 동작적 정의는 종종 추상 변수의 관점에서 작성된다. 공리적 의미론에서 를 추상 변수의 유형으로, 를 내용의 유형으로 놓으면, fetch는 함수이고 store는 유형의 함수이다. 주요 제약 조건은 fetch가 항상 동일한 변수 V에 대한 가장 최근 store 연산에 사용된 값 x를 반환한다는 것이다. 즉, fetch(store(V,x)) = x이다. 또한 store가 값을 완전히 덮어쓰도록 요구할 수도 있다. 즉, store(store(V,x1),x2) = store(V,x2)이다.
동작적 의미론에서, fetch(V)는 위치 V에 있는 현재 값을 반환하는 프로시저이고, store(V, x)는 void 반환 유형을 가진 프로시저로, 위치 V에 값 x를 저장한다. 제약 조건은 읽기가 쓰기와 일치한다고 비공식적으로 설명된다. 많은 프로그래밍 언어에서와 같이, store(V, x) 연산은 종종 V ← x (또는 유사한 표기법)로 작성되며, 값 X가 필요한 컨텍스트에서 변수 V가 사용될 때마다 fetch(V)가 암시된다. 따라서, 예를 들어 V ← V + 1은 일반적으로 store(V,fetch(V) + 1)의 단축 표기로 이해된다.
이 정의에서는 이름이 항상 고유하다고 암묵적으로 가정한다. 즉, 변수 U에 값을 저장하는 것은 다른 변수 V의 상태에 영향을 미치지 않는다. 이 가정을 명시적으로 하기 위해 다음 제약 조건을 추가할 수 있다.
- U와 V가 서로 다른 변수일 경우, 시퀀스 {
store(U, x);store(V, y) }는 {store(V, y);store(U, x) }와 동일하다.
이 정의는 V가 초기화되지 않은 경우, 즉 V에 대한 store 연산을 수행하기 전에 fetch(V)를 평가한 결과에 대해서는 아무것도 말하지 않는다. 저장하기 전의 가져오기는 허용되지 않거나, 특정 결과를 가지도록 정의되거나, 지정되지 않을 수 있다. 일부 알고리즘의 효율성은 그러한 fetch가 합법적이며 변수의 범위 내에서 임의의 값을 반환한다는 가정에 따라 달라진다.
추상 스택
[편집]추상 스택은 후입선출 구조이다. 일반적으로 세 가지 주요 연산으로 정의된다. 데이터 항목을 스택에 삽입하는 push, 스택에서 데이터 항목을 제거하는 pop, 스택 상단의 데이터 항목을 제거하지 않고 접근하는 peek 또는 top이다. 완전한 추상 스택 정의에는 불리언 값 함수 empty(S)와 초기 스택 인스턴스를 반환하는 create() 연산도 포함된다.
공리적 의미론에서, 를 스택 상태의 유형으로, 를 스택에 포함된 값의 유형으로 놓으면, 이들은 , , , , 그리고 유형을 가질 수 있다. 공리적 의미론에서 초기 스택을 생성하는 것은 "사소한" 연산이며, 항상 동일한 특수 상태를 반환한다. 따라서 종종 Λ 또는 "()"와 같은 특별한 기호로 지정된다. empty 연산 술어는 간단히 또는 로 작성될 수 있다.
제약 조건은 다음과 같다. pop(push(S,v))=(S,v), top(push(S,v))=v,[9] empty(create) = T (새로 생성된 스택은 비어 있음), empty(push(S, x)) = F (스택에 무언가를 푸시하면 비어 있지 않게 됨). 이 공리들은 s가 push에 의해 반환된 스택 상태가 아닌 한, top(s) 또는 pop(s)의 효과를 정의하지 않는다. push는 스택을 비어 있지 않게 하므로, 이 두 연산은 s = Λ일 때 유효하지 않도록 정의될 수 있다. 이 공리들(및 부작용 없음)로부터, push(Λ, x) ≠ Λ임을 추론할 수 있다. 또한, push(s, x) = push(t, y)는 x = y이고 s = t일 때만 성립한다.
수학의 다른 분야에서와 마찬가지로, 스택 상태는 유한한 단계로 공리로부터 존재가 증명될 수 있는 것들만 가정하는 것이 관례이다. 이 경우, 모든 스택은 유한한 값의 시퀀스이며, 유한한 수의 pop 후에 빈 스택(Λ)이 된다는 것을 의미한다. 그 자체로 위의 공리들은 무한 스택(영원히 pop될 수 있으며, 매번 다른 상태를 생성)이나 순환 스택(유한한 수의 pop 후에 동일한 상태로 돌아옴)의 존재를 배제하지 않는다. 특히, pop(s) = s 또는 push(s, x) = s인 상태를 배제하지 않는다. 그러나 이러한 스택 상태는 주어진 연산으로 초기 스택 상태에서 얻을 수 없으므로 "존재하지 않는" 것으로 가정된다.
추상 스택의 동작적 정의에서, push(S, x)는 아무것도 반환하지 않고 pop(S)는 값을 결과로 반환하지만 스택의 새 상태는 반환하지 않는다. 그러면 모든 값 x와 모든 추상 변수 V에 대해 연산 시퀀스 { push(S, x); V ← pop(S) }가 V ← x와 동일하다는 제약 조건이 있다. 정의상 할당 V ← x는 S의 상태를 변경할 수 없으므로, 이 조건은 V ← pop(S)가 S를 push(S, x) 이전의 상태로 복원한다는 것을 의미한다. 이 조건과 추상 변수의 속성으로부터, 예를 들어 다음 시퀀스가
- {
push(S, x);push(S, y); U ←pop(S);push(S, z); V ←pop(S); W ←pop(S) }
여기서 x, y, z는 임의의 값이고 U, V, W는 서로 다른 변수이며, 다음 시퀀스와 동일하다.
- { U ← y; V ← z; W ← x }
공리적 의미론과 달리, 동작적 의미론은 별칭 문제에 시달릴 수 있다. 여기서 스택 인스턴스에 대한 연산이 다른 스택을 포함한 다른 ADT 인스턴스의 상태를 수정하지 않는다고 암묵적으로 가정한다. 즉:
- 모든 값 x, y와 서로 다른 스택 S와 T에 대해, 시퀀스 {
push(S, x);push(T, y) }는 {push(T, y);push(S, x) }와 동일하다.
붐 계층 구조
[편집]더 복잡한 예시는 이진 트리, 리스트, 중복집합 및 집합 추상 자료형의 붐 계층 구조이다.[10] 이 모든 자료형은 세 가지 연산으로 선언될 수 있다. 빈 컨테이너를 구성하는 null, 단일 요소에서 컨테이너를 구성하는 single, 그리고 동일한 유형의 두 컨테이너를 결합하는 append이다. 네 가지 자료형에 대한 완전한 명세는 이러한 연산에 대해 다음 규칙을 차례로 추가하여 제공할 수 있다.
null은 트리에 대해 왼쪽 및 오른쪽 항등원이다. append(null,A) = A, append(A,null) = A. 리스트는 append가 결합법칙을 따른다. append(append(A,B),C) = append(A,append(B,C)). 가방은 교환법칙을 따른다. append(B,A) = append(A,B). 마지막으로, 집합은 또한 멱등법칙을 따른다. append(A,A) = A.
데이터 접근은 세 가지 연산에 대한 패턴 매칭을 통해 지정할 수 있다. 예를 들어, 이 컨테이너에 대한 멤버 함수는 다음과 같다.
member(X,single(Y)) = eq(X,Y) member(X,null) = false member(X,append(A,B)) = or(member(X,A), member(X,B))
함수가 데이터 유형에 대한 관련 규칙에 따라 불변임을 보장하도록 주의해야 한다. 선택된 방정식 부분 집합에 의해 암시되는 각 동치 클래스 내에서, 모든 멤버에 대해 동일한 결과를 산출해야 한다.
일반적인 ADT
[편집]다양한 응용 분야에서 유용하게 입증된 몇 가지 일반적인 ADT는 다음과 같다.
이러한 ADT 각각은 반드시 동등하지는 않은 여러 가지 방식과 변형으로 정의될 수 있다. 예를 들어, 추상 스택은 푸시되었지만 아직 팝되지 않은 항목 수를 알려주는 count 연산을 가질 수도 있고 가지지 않을 수도 있다. 이 선택은 클라이언트뿐만 아니라 구현에도 차이를 만든다.
- 추상 그래픽 자료형
컴퓨터 그래픽을 위한 ADT의 확장은 1979년에 제안되었다.[11] 추상 그래픽 자료형 (AGDT)이라고 불린다. 이는 나디아 마그네나 탈만과 다니엘 탈만이 도입했다. AGDT는 구조화된 방식으로 그래픽 객체를 구축할 수 있는 기능을 제공하며 ADT의 장점을 제공한다.
구현
[편집]추상 자료형은 (다른 용도 외에도) 추상 알고리즘의 설명을 단순화하고, 자료 구조를 분류하고 평가하며, 프로그래밍 언어의 자료형 체계를 형식적으로 설명하는 데 사용되는 이론적 엔티티이다. 그러나 ADT는 구현될 수 있다. 이는 각 ADT 인스턴스 또는 상태가 일부 구체적인 자료형 또는 자료 구조로 표현되고, 각 추상 연산에 대해 해당하는 프로시저 또는 함수가 있으며, 이러한 구현된 프로시저가 ADT의 명세 및 공리를 어떤 표준까지 만족시킨다는 의미이다. 실제로는 구현이 완벽하지 않으므로 사용자는 표현 및 구현된 프로시저의 한계로 인한 문제점을 인지해야 한다.
예를 들어, 정수는 ADT로 지정될 수 있으며, 구별되는 값 0과 1, 덧셈, 뺄셈, 곱셈, 나눗셈(0으로 나누는 경우 주의), 비교 등의 연산으로 정의되며, 보편대수학에서 익숙한 수학적 공리(예: 결합 법칙, 교환 법칙 등)에 따라 동작한다. 그러나 컴퓨터에서 정수는 대부분 32비트 또는 64비트 이진수의 고정 너비로 표현된다. 사용자는 산술 오버플로와 같이 이 표현과 관련된 문제를 인지해야 한다. ADT는 유효한 결과를 지정하지만 표현은 이 값을 수용할 수 없다. 그럼에도 불구하고, 많은 목적으로 사용자는 이러한 불성실함을 무시하고 마치 추상 자료형인 것처럼 구현을 사용할 수 있다.
일반적으로 동일한 ADT를 여러 가지 다른 구체적인 자료 구조를 사용하여 구현하는 방법은 여러 가지가 있다. 따라서, 예를 들어 추상 스택은 연결 리스트 또는 배열로 구현될 수 있다. 동일한 속성 및 기능을 모두 갖는 ADT의 다른 구현은 의미적으로 동등한 것으로 간주될 수 있으며, ADT를 사용하는 코드에서 어느 정도 교체하여 사용할 수 있다. 이는 일종의 추상화 또는 캡슐화를 제공하며, 다양한 상황에서 ADT 객체를 사용할 때 상당한 유연성을 제공한다. 예를 들어, ADT의 다른 구현은 다른 상황에서 더 효율적일 수 있다. 각 구현은 선호되는 상황에서 사용될 수 있으므로 전반적인 효율성을 높일 수 있다. 인터페이스에 따라 ADT 구현을 사용하는 코드는 ADT 구현이 변경되더라도 계속 작동한다.
클라이언트가 구현에 의존하는 것을 방지하기 위해 ADT는 종종 불투명 자료형 또는 일종의 핸들로 모듈 하나 이상에 패키징된다.[12] 해당 모듈의 인터페이스는 연산의 서명(매개변수 및 결과의 수와 유형)만 포함한다. 그러면 모듈의 구현(즉, 프로시저의 본문 및 사용된 구체적인 자료 구조)은 모듈의 대부분 클라이언트로부터 숨겨질 수 있다. 이를 통해 클라이언트에 영향을 주지 않고 구현을 변경할 수 있다. 구현이 노출되면 이를 투명한 자료형이라고 한다.
C++ 및 자바와 같은 최신 객체 지향 언어는 추상 자료형의 한 형태를 지원한다. 클래스가 유형으로 사용될 때, 이는 숨겨진 표현을 참조하는 추상 유형이다. 이 모델에서 ADT는 일반적으로 클래스로 구현되며, ADT의 각 인스턴스는 일반적으로 해당 클래스의 객체이다. 모듈의 인터페이스는 일반적으로 생성자를 일반 프로시저로 선언하고, 대부분의 다른 ADT 연산은 해당 클래스의 메서드로 선언한다. C++ 및 자바와 같은 많은 최신 프로그래밍 언어는 이 스타일로 수많은 ADT를 구현하는 표준 라이브러리와 함께 제공된다. 그러나 이러한 접근 방식은 ADT에서 발견되는 여러 표현 변형을 쉽게 캡슐화하지 못한다. 또한 객체 지향 프로그램의 확장성을 훼손할 수 있다. 인터페이스를 유형으로 사용하는 순수 객체 지향 프로그램에서는 유형이 표현이 아닌 동작을 참조한다.
일부 프로그래밍 언어의 명세는 특정 내장 자료형의 표현에 대해 의도적으로 모호하게 작성되어, 해당 자료형에 대해 수행할 수 있는 연산만 정의한다. 따라서 이러한 유형은 "내장 ADT"로 간주될 수 있다. 예를 들어 Awk, 루아, 펄과 같은 많은 스크립팅 언어의 배열이 있으며, 이는 추상 리스트의 구현으로 간주될 수 있다.
형식 명세 언어에서 ADT는 공리적으로 정의될 수 있으며, 언어는 이러한 ADT의 값을 조작할 수 있으므로 간단하고 직접적인 구현을 제공한다. 예를 들어 OBJ 계열 프로그래밍 언어는 명세를 위한 방정식을 정의하고 이를 실행하기 위한 재작성을 허용한다. 그러나 이러한 자동 구현은 일반적으로 전용 구현만큼 효율적이지 않다.
예시: 추상 스택의 구현
[편집]예를 들어, 위에 있는 추상 스택의 C 프로그래밍 언어 구현은 다음과 같다.
명령형 스타일 인터페이스
[편집]명령형 스타일 인터페이스는 다음과 같을 수 있다.
// type: stack instance representation (opaque record)
typedef struct {
// implementation here
} Stack;
// type: value stored in stack instance (arbitrary address)
typedef void* Item;
// creates a new empty stack instance
Stack* stack_create(void);
// adds an item at the top of the stack
void stack_push(Stack* s, Item x);
// removes the top item from the stack and returns it
Item stack_pop(Stack* s);
// checks whether stack is empty
bool stack_is_empty(Stack* s);
이 인터페이스는 다음과 같이 사용될 수 있다.
#include <stack.h>
int main() {
Stack* s = stack_create(); // creates a new empty stack instance
int x = 17;
// adds the address of x at the top of the stack
stack_push(s, &x);
// removes the address of x from the stack and returns it
Item y = stack_pop(s);
if (stack_is_empty(s)) {
// does something if stack is empty
printf("Stack is empty!");
}
}
이 인터페이스는 여러 가지 방식으로 구현될 수 있다. 구현은 임의로 비효율적일 수 있는데, ADT의 공식 정의는 스택이 사용할 수 있는 공간의 양이나 각 연산에 걸리는 시간을 지정하지 않기 때문이다. 또한 스택 상태 s가 호출 x ← pop(s) 이후에도 계속 존재하는지도 지정하지 않는다.
실제로 형식 정의는 푸시되었지만 아직 팝되지 않은 항목 수에 비례하는 공간과 위 연산 각각이 그 수와 관계없이 일정한 시간 내에 완료되어야 함을 명시해야 한다. 이러한 추가 명세를 준수하기 위해 구현은 연결 리스트를 사용하거나 (동적 크기 조절이 가능한) 배열과 두 개의 정수(항목 수 및 배열 크기)를 함께 사용할 수 있다.
함수형 스타일 인터페이스
[편집]함수형 스타일 ADT 정의는 함수형 프로그래밍 언어에 더 적합하며, 그 반대도 마찬가지이다. 그러나 C와 같은 명령형 언어에서도 함수형 스타일 인터페이스를 제공할 수 있다. 예를 들어:
// type: stack instance representation (opaque record)
typedef struct {
// implementation here
} Stack;
// type: value stored in stack instance (arbitrary address)
typedef void* Item;
// returns the empty stack state
Stack* stack_is_empty(void);
// adds an item at the top of the stack state and returns the resulting stack state
Stack* stack_push(Stack* s, Item x);
// removes the top item from the stack state and returns the resulting stack state
Stack* stack_pop(Stack* s);
// returns the top item of the stack state
Item stack_top(Stack* s);
같이 보기
[편집]각주
[편집]- ↑ “Reading 10: Abstract Data Types”. MIT.
- ↑ Liskov & Zilles 1974.
- ↑ Ehrig, H. (1985). 《Fundamentals of Algebraic Specification 1 - Equations and Initial Semantics》. Springer-Verlag. ISBN 0-387-13718-1.
- ↑ Wechler, Wolfgang (1992). 《Universal Algebra for Computer Scientists》. Springer-Verlag. ISBN 0-387-54280-9.
- ↑ Rudolf Lidl (2004). 《Abstract Algebra》. Springer. ISBN 978-81-8128-149-4., Chapter 7, section 40.
- ↑ Dale & Walker 1996, 3쪽.
- ↑ Dale & Walker 1996, 4쪽.
- ↑ Stevens, Al (March 1995). 《Al Stevens Interviews Alex Stepanov》. 《닥터 돕스 저널》. 2015년 1월 31일에 확인함.
- ↑ Black, Paul E. (2005년 8월 24일). “axiomatic semantics”. 《Dictionary of Algorithms and Data Structures》. 2023년 11월 25일에 확인함.
- ↑ Bunkenburg, Alexander (1994). 〈The Boom Hierarchy〉. 《Functional Programming, Glasgow 1993》. Workshops in Computing. 1–8쪽. CiteSeerX 10.1.1.49.3252. doi:10.1007/978-1-4471-3236-3_1. ISBN 978-3-540-19879-6.
- ↑ D. Thalmann, N. Magnenat Thalmann (1979). 《Design and Implementation of Abstract Graphical Data Types》. IEEE. doi:10.1109/CMPSAC.1979.762551., Proc. 3rd International Computer Software and Applications Conference (COMPSAC'79), IEEE, Chicago, USA, pp.519-524
- ↑ Robert Sedgewick (1998). 《Algorithms in C》. Addison/Wesley. ISBN 978-0-201-31452-6., definition 4.4.
참고 자료
[편집]- Liskov, Barbara; Zilles, Stephen (1974). 〈Programming with abstract data types〉. 《Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages》. SIGPLAN Notices. 50–59쪽. CiteSeerX 10.1.1.136.3043. doi:10.1145/800233.807045.
- Dale, Nell; Walker, Henry M. (1996). 《Abstract Data Types: Specifications, Implementations, and Applications》. Jones & Bartlett Learning. ISBN 978-0-66940000-7.
더 읽어보기
[편집]- Mitchell, John C.; Plotkin, Gordon (July 1988). 《Abstract Types Have Existential Type》 (PDF). 《ACM Transactions on Programming Languages and Systems》 10. 470–502쪽. doi:10.1145/44501.45065. S2CID 1222153. 2022년 10월 9일에 원본 문서 (PDF)에서 보존된 문서.
