2025년 6월 21일 약 8분 프로그래밍 언어론

Structured Data Types

Photo by Merve Sehirli Nasir / Unsplash

프로그램이란?

: 프로그램 == 알고리즘(Algorithms) + 자료구조(Data Structures)

프로그래밍?

내가 해결할 문제의 해결 방법이 해당 언어에서 제공된다면, 그걸로 충분하다 (잘 활용하기)
그렇지 않다면 뭔가 만들어야 함

Encapsulation: Data와 Operation을 하나의 묶음(Capsule)으로 묶을 수 있는 장치, 방법

Four Basic Mechanisms

Structured Data: 복합 데이터를 만들 수 있는 기능
Subprograms: 새로운 연산을 정의할 수 있는 기능(함수 또한 연산으로 볼 수 있다)
Type Declarations: 특정 부류의 데이터와, 이와 관련된 연산을 하나로 묶어 새로운 데이터 타입을 저으이할 수 있는 기능
Inheritance: 기존 데이터타입의 기능을 모두 포함하며 더욱 확장된 데이터 타입을 생성할 수 있는 기능

Structured Data + Subprogram 은 필수 기능,
Type Declaration + Inheritance 는 고급 기능으로 본다 (optional)

Data Structure(Structured Data)

다른 데이터 객체를 원소(Elements)나 요소(Components)로 가지는 데이터 객체
배열(Array), 레코드(Record or Structure), 스택(Stack), 리스트(List) 등

Specification of Data Structure Types

원소의 개수
- 고정 크기(Fixed Size): Array, Record
- 가변 크기(Variable Size): List, Set, Tables, Files
  - 언어에 따라 가변 크기 배열(Array)이 가능할 수 있음
원소의 타입
- 동형 구조(Homogeneous Structure): Array, Set
- 이형 구조(Heterogeneous Structure): Record, List
  - 언어에 따라 List의 원소를 동형으로 제한하기도 함
원소 선택 방법
- 임의 선택(Random Selection): 임의의 순서로 선택
- 순차 선택(Sequential Selection): 정해진 순서에 따라 선택
최대 원소 개수
- 가변 크기 구조의 경우에도, 최대 원소 개수가 지정될 수 있음

Operations on Data Structures

원소 선택(Component Selection): 임의 선택, 순차 선택
전체 구조에 대한 연산(Whole-Structure Operation)
- Assignments, Union of Sets, Transpose of a Matrix, ...
원소의 삽입 및 삭제(Insertion and Deletion of Components)
데이터 구조의 생성 및 소멸(Construction and Destruction of Data Structures)

Implementation of Data Structures

저장공간의 형태(Storage Representation)
- 연속된 형태(Sequential Representation, Continuous Block)
- 연결된 형태(Linked Representation)
연산의 구현(Implementations of Operations)
- 연속된 형태일 경우 Selection: Base Address + Offset
- 연결된 형태일 경우 Selection: Head Address + Following Links
저장공간 관리
- 객체의 지속시간(Lifetime) 관리
- Lifetime: Storage Binding이 유지되는 시간.
  즉, 해당 객체의 공간이 존재하는 시간

Problems in Storage Management

Garbage Object
- 참조 경로(Access Path)를 잃어버린 객체
- 객체의 할당 해제(Deallocation)가 너무 늦음
- Dangling Object라고도 부름
- 위험하지는 않지만, 공간이 낭비됨 <- 메모리 누수(Memory Leak)
Dangling Reference
- 이미 할당이 해제된 객체를 가리키는 참조 경로
- 객체의 할당 해제가 너무 빠름
- 굉장히 위험하다!!! <- 다른 용도의 공간을 훼손할 수 있음

Type Checking for Data Structures

C언어 선언문 예시:
float a[20];
- 배열이군
- 1차원 배열
- 요소의 개수는 20개
- 인덱스는 0번부터 19번까지 사용 가능
- 각각의 원소들의 타입은 float
Structured Type의 타입 검사를 복잡하게 하는 요인?
- Selector를 통해 선택한 원소가 실제로 존재하는지를 검사해야 함
  - 배열의 경우, 첨자 범위에 대한 검사 필요
- 선택된 원소의 타입도 다시 고려해야 함 (?)

Array (배열)

: 같은 타입의 유한한 개체들이 일렬로 나열된 것, Homogeneous Aggregation

Attributes of a Array:
- 원소의 개수(Number of Components)
- 원소의 타입(Type of Each Components)
- 첨자(Subscript): 통상적으로 자연수이지만, 임의의 enumeration일 수 있다
  - Pascal: V: array [-5 .. 5] of real;
  - type class = (Fresh, Soph, Junior, Senior)
  - var ClassAverage: array [class] of real;
Array Operations
- 원소 선택(Selector): 일반적으로 첨자 연산[]으로 처리
- 원소 갱신(Modifier): 역시 일반적으로 첨자 연산으로 처리
- 원소 삽입 및 삭제: Variable Size Array일 경우에만 허용됨
Whole Array Operations
- 크기(Size)
- 배열 대입(Array Assignment)
- 내적(Inner Product)
- 외적(Outer Product)
Whole Array Operations의 문제점?
: 중간 결과(Array일 수 있음)를 저장할 별도의 공간이 필요
Array Implementation
- 일차원 배열의 경우:
- 참조 공식(Accessing Formula)
  - 배열에 할당된 첫 번째 원소의 주소가 a, 원소의 크기가 E일 때
  - i번째 원소의 주소(lvalue) A[i]
  - = a + (I-LB) * E
  - = (a - LB * E) + I * E
  - = VO + I * E
- VO(Virtual Origin)은 컴파일 타임에 정적으로(statically) 결정될 수 있다
- + 참조가 올바른지를 검사하기 위해서는, 배열의 UB(Upper Bound)도 알아야 한다!
- Dope Vector
  - (VO, LB, UB, E) 정보를 가지고 있음 - E는 각각의 원소가 차지하는 메모리 크기
  - 이녀석 덕분에 배열 접근이 빠르게 이루어질 수 있는 것
Two-Dimensional Array
- Row-Major: 행들의 1차원 배열
- Column-Major: 열들의 1차원 배열
- 일반적으로 2차원 배열의 경우 row-major 방식으로 구현하지만, FORTRAN은 column-major 방식으로 구현됨
- C언어에는 2차원 배열이 없음! 배열의 배열로 다차원 배열을 지원함
- 이차원 배열의 참조 공식(Accessing Formula):
  - 배열에 할당된 첫 번째 원소의 주소가 a, 원소의 크기가 E, 한 행의 크기가 S일 때
  - [i][j]번째 원소의 주소(lvalue) A[i][j]
  - = a + (I-LB1) * S + (J-LB2) * E
  - = (a - LB1 * S - LB2 * E) + I * S + J * E
  - = VO + I * S + J * E
    결국 Virtual Origin + (해당 인덱스 이전 원소의 개수 * 원소의 메모리 크기)
Slice
- 그 자체가 또다른 배열이 되는 배열의 하위 구조(substructure)

1 2 3
4 5 6
7 8 9

---

(1:4, 2) -> [2, 5, 8, 11]
(3, 1:3) -> [7, 8, 9]

Associative Array

: 연관 배열, 이름을 첨자로 사용하는 배열

(key, value)로 이루어진 참조 표로 볼 수도 있다
lookup table 또는 dictionary 라고도 부른다
연산들:
- 첨가(Add): 새로운 (key, value)를 추가
- 변경(Reassign): 기존 key의 value를 변경
- 삭제(Remove): 기존 (key, value)를 삭제
- 참조(lookup): 특정 key의 value를 참조

Record

: (일반적으로) 서로 다른 타입의 원소들을 하나로 묶은 것

Heterogeneous Aggregation
속성:
- 원소의 개수(Number of Components)
- 원소의 타입(Type of Each Component)
- 원소 선택자(Selector for Each Component)
연산:
- Move Corresponding
- ex) MOVE CORRESPONDING INPUTSEC TO EMPLOYEE
C언어에서는 Structure (via struct)
- 필드명이 Selector
- Tag와 Type을 구분함

typedef struct _A { // 이 `_A`는 Tag
  int x;
  int y;
} A; // 이 `A`는 Type (typedef를 통해 `struct _A`에 대한 별칭을 만들어준것)

Variant Record

: 여러 다른 타입 중 하나가 올 수 있지만, 한 번에 하나의 타입만을 가지는 구조

모든 필드가 동일한 주소(L-value)를 공유함
- 즉, 한 번에 하나의 값만을 저장할 수 있다
단순히 공간(메모리) 효율성을 위해 존재하는 타입!
속성 및 연산은 Record와 동일하다
타입 검사를 어렵게 만든다
- 동적으로 타입 검사를 수행하거나
- 타입을 아예 검사하지 않기도 한다
구분자(Discriminator) 존재 유무에 따라 구분됨:
- free-union (non-discriminated variant record)
- discriminated-union (discriminated variant record)
C언어에서는 Union

typedef union {
  int x;
  float y;
  char Z[4];
} U;

U.x = 142;
printf("%d\n", U.Z[3]); // 컴파일 타임에 타입 검사를 할 수 없다는 문제점이 있다!

List

: 순차 목록(Ordered Sequence of Elements)

배열과의 차이점:
- 고정 길이가 아니다
- 동형 원소가 아닐 수 있다 (하지만 언어에 따라 동형 원소로 제한하기도 함)
- 암시적 선언을 사용하는 경우가 많다. 별도의 선언 없이 리스트를 생성(?)
연산:
- nil: 빈 리스트 생성
- cons: 리스트에 특정 원소를 덧붙임
- head: 리스트의 첫 번째 원소 (LISP의 CAR)
- tail: 리스트의 첫 번째 요소를 제외한 나머지 원소 (LISP의 CDR)
리스트의 원소로 다른 리스트를 포함할 수 있는 리스트를 Generalized List라 부른다
- 사실상 Tree인 셈!
Stack, Queue, Tree, Property List(원소의 개수가 가변인 레코드) 등은 List의 변형

Set

: 서로 다른 값들의 모음 (Unordered Collection of Distinct Elements)

연산:
- 원소 검사(Membership)
- 원소 추가(Insertion), 원소 삭제(Deletion)

합집합(Union), 교집합(Intersection), 차집합(Difference)

구현 방식:
- Bitmap of Enumerations
  - 집합의 크기가 제한됨
- Hashing
  - 충돌(Collision) 해결이 필요함
    - Rehashing
    - Sequential Scan
    - Bucketing

Executable Data Object

: 데이터로 표현된 부프로그램

프로그램을 데이터 객체로 나타냄
- 일반적으로 프로그램과 데이터는 구분하지만, 구별하지 않는 언어도 있다
함수형 언어에서는 자연스럽다!
scheme

(define (double1 x) (+ x x))
(define double2 (lambda (x) (+ x x)))
;; lambda 부프로그램 객체를 double2 변수에 대입

haskell

addOne = \x -> x + 1