[프로그래밍 언어론] Structured Data Types (6)

[5-2] Structured Data Types

Encapsulation
-  Data와 Operation을 하나로 묶음
-  Information hiding?

User-Defined Data Types
Basic Mechanims
1. Structured Data
-  복합 데이터를 만들 수 있는 기능 (필수)

2. Subprograms
-  새로운 연산을 정의할 수 있는 기능 (필수)

3. Type Declarations
-  새로운 타입을 정의할 수 있는 기능 (고급)

4. Inheritance
-  기존 타입에서 확장된 타입을 생성할 수 있는 기능 (고급)

Structured Data
-  다른 데이터 객체를 원소로 구성된 데이터 객체
-  배열, 레코드, 스택, 리스트, 집합
-  원소 선택 방법, 메모리 관리 방법

Data Structure Types Specification
-  요소 타입 (homogeneous/heterogeneous structure)
-  요소 개수 (fixed/variable size)
-  요소 선택 방법 (named selector/index)
-  최대 요소 개수 (가변 크기일 경우)
-  저장공간 형태 : 연속(sequential) 또는 연결 (linked)
-  구성 방법 (dimensions of arrays, variant records)
-  연산 집합 : component selection, while-structure operation, insertion/deletion, creation/destruction

@Homogeneous/heterogeneous
-  원소들의 타입이 동일/달라도됨

@Component selection
-  임의 선택 (direct)
-  순차 선택 (정해진 순서에 따라 선택)
-  연속할 경우 base-address + offset
-  연결된 경우 head address + following links

@Storage Management
-  Garbage (참조 경로를 잃음)
-  Dangling reference (이미 해제된 공간을 가르킴)

Data Structure Type Checking
-  Selector 첨자의 범위가 적절한지 검사 (index)
-  Selector를 통해 선택한 요소가 실제로 존재하는지 검사 #선택된 요소의 타입도 검사

Array(Vectors)
-  Homogeneous aggregation
-  Vector attributes : 요소개수, 요소 타입, 첨자

@Array Implementation
-  참조 공식 : VO + I * E
-  Dope Vector가 Base address 뒤에 있거나 아에 떨어져 있음
-  떨어져 있는 경우 가상 원점 VO 을 statically 결정 가능

@Dope Vector
-  Descriptor
-  (lower bound, upper bound, type, size)
-  (VO, lower bound, upper bound, size)

Array 연산 집합
1. Component Operations
-  select, modify. 가변 길이길 경우 insert, delete 추가

2. Whole Array Operations
-  size, array assignment, inner/cross product
-  중간 결과를 저장할 공간 필요

Two-Dimensional Array
-  row-major (행 1차원 배열)
-  column-major (열 1차원 배열)
-  참조 공식 : VO + I * S + J * E
-  Storage representation : 떨어져 있는 Dope Vector (VO, LB1, UB1, LB2, LB2, E)

Multi-Dimensional Array
-  Multiplier ?
-  VO (각 차원의 VO가 다 다름)
-  Address of elements

Slices
-  그 자체가 배열인 배열의 하부 구조

Associative Arrays
-  이름을 첨자로 사용하는 배열
-  Alphabetical order by key?
-  (key, value)
-  연산 : add, reassign, remove, lookup

Records
-  Heterogeneous aggregation
-  속성 : 요소 개수, 요소 타입, 요소 선택자
-  연산 : move corresponding

@Structures in C
-  Selector : 필드 이름
-  Tag or Type
-  연산 : 대입

Variant Records
-  여러 개의 필드 중 하나만을 활성화하여 사용할 수 있는 데이터 구조
-  Same L-value
-  속성 및 연산 : record와 동일
-  동적 타입 검사를 하거나 검사하지 않음
-  free-union, descriminated-union

@Union in C
-  Union의 경우 타입 검사를 하지 않음

@Variant record in Pascal
-  파스칼 나오면 그냥 틀린다는 마인드

Lists
-  Ordered sequence of data
-  고정길이x
-  Homogeneous, Heterogeneous, Generalized
-  연산 : nil(빈 리스트), cons(특정 요소 접합), head(첫번째 요소), tail(첫번째 요소를 제외한 나머지)
-  변형 : stack, queue, tree, property list

Sets
-  서로 다른 값의 무순 모음
-  연산 : 요소 검사, 추가, 삭제, 합집합, 교집합, 차집합
-  구현 : bitmap of enumerations (크기 제한), hasing

@Hashing
-  Collision 해결 필요 (rehashing, sequential scan, bucketing)

Executable Data Objects
-  프로그램과 데이터를 구분하지 않는 언어도 있음

데이터로 표현된 서브 프로그램
-  함수를 변수와 마찬가지로 정의
-  const add3 = (a) => a+3