[SICP 스터디] Ch2. 데이터를 이용한 추상화

배경

일명 '마법사책'으로 불리는 SICP(컴퓨터 프로그램의 구조와 해석)의 JS버전을 스터디하며 발제를 맡은 부분을 정리한 내용입니다. 연습문제는 일부만 별도 포스트로 다룰 예정입니다. 

---

내용

서론

ㅇ복합 데이터를 이용한 추상화 방식을 탐구

ㅇ이점?

- 접착제 제공: 복잡한 개념(유리수)을 단일 객체로 다룰 수 있게됨(분자 + 분모 연결)

- 모듈성 향상: 표현부와 연산부를 분리(<-> 추상화)

ㅇ순서

1) 유리수 산술 시스템 구현

2) 닫힘(closure), 접착제를 이용한 복합 데이터 구성 (그래픽 언어 예시)

3) 기호 표현식(symbolic expression)

4) 일반적 연산(generic operation)의 구현과 데이터 지향적 프로그래밍

---

2.1 데이터 추상화

ㅇ데이터추상화: 하나의 복합적인 대상(복잡한 데이터 객체) -> 단순한 대상들(기본적인 데이터 객체들)로 구축하는 방법론

ㅇ선택자와 생성자로 구성됨

2.1.1 유리수 산술 연산

ㅇ선택자: numer, denom

ㅇ생성자: make_rat

ㅇ쌍 자료 구조: pair(head(), tail())

- pair를 통해 유리수가 만들어짐(접착제 역할)

- 이름을 붙이거나 다른 쌍 객체를 포함함으로써 목록 구조 데이터 형성 가능

ㅇ유리수의 표현: print_rat

2.1.2 추상화 장벽

ㅇ개념: 추상화 수준에 따른 수준(level) 발생으로, 각 수준별 함수가 장벽 역할을 함

ㅇ장점: 의존성 감소, 수정 유연성(gcd 호출 예시) 증가 -> 유지보수 용이성 증가

2.1.3 데이터란 무엇인가?

ㅇ선택자와 생성자가 반드시 충족되는 조건들의 집합(한 마디로 정의하기 어려움)

ㅇ함수로 자료구조를 대체하는 예시(p.155)

-> 함수를 객체로 다루는 프로그래밍 스타일: 메시지 전달(message passing)

2.1.4 skip

---

2.2 위계적 데이터와 닫힘 성질

ㅇ상자-포인터 표기법: head + tail로 구성, 화살표로 가리킴

ㅇ닫힘 성질(closure property)

- 개념:  데이터 객체의 조합 연산 결과를 같은 연산으로 조합할 수 있으면 닫힘 성질을 충족함

*JS의 클로저와는 다름

2.2.1 순차열(sequence)의 표현 - 리스트

ㅇ개념: 데이터가 특정 순서로 나열된 구조

ㅇpair의 중첩으로 순차열 생성 가능 -> 목록(list)으로 명명

ㅇ상자(box) 표기법, 목록(list) 표기법 소개

ㅇ목록 연산: list_ref(), length(), append()

ㅇ목록 매핑: scale_list(), map()

- map() : 고차함수, 틀을 유지하면서 세부사항을 변경하는 유연성 제공(추상화 장벽의 예시)

2.2.2 위계적 구조 - 트리

ㅇpair()와 list()의 조합을 통한 트리의 표현(그림 2.5, 2.6)

ㅇ재귀를 이용한 트리 다루기(p.177~178): count_leaves(), length()

Q. length()는 3, count_leaves()는 4인 이유를 이해했는지?

ㅇ트리에 대한 매핑(p.181~182)

- 재귀 + map() 을 이용한 scale_tree()의 구현

- 순차열 연산(부분트리를 순차열로 간주) + map()을 이용한 scale_tree()의 또다른 구현 방법

2.2.3 합의된 인터페이스로서의 시퀀스 

ㅇ합의된 인터페이스: 공통적으로 적용되는 패턴들을 빼서 모아놓은 것

ㅇsum_odd_squares()와 even_fibs()의 비교 및 합의된 인터페이스 도출(p.184~194)

- 열거, 맵, 필터, 누산의 조합임

- 신호 흐름의 처리와 비슷한 개념

- 각 단계를 모듈화 가능해짐: 모듈식 설계(modular design)

- (내 생각) 앞 단계에서 이미 각 함수의 구현을 봤기때문에, 여기 예시들에서는 그냥 함수 이름들의 조합만으로 어떤 목적을 가졌는지 파악할 수 있음

ㅇ중첩된 매핑 (nested mappings)

- 1부터 n 사이의 i + j가 소수인 순서쌍 구하기 예시

1) 범위 내의 (p.195) 모든 순서쌍 생성

*accumulate + append -> 누산을 append로 함 -> 결과값을 순차열로 -> flatmap()으로 정의

2) 합이 소수여부인지 판정

3) 세값 쌍 만들기 (i, j, i+j)

ㅇ순열(permutation) 구하기 예시: skip

2.2.4 예제: 그림 언어 

ㅇ그림 언어의 요소는 한 종류임: 화가

ㅇ화가는 주어진 틀(frame)에 따라 이미지를 기울이거나 비례시킴

ㅇ연산: beside, below, flip_ver, flip_horiz 등

ㅇ화가의 조합 예시(~p.207)

ㅇ화가 연산의 조합 예시

---

2.3 기호 데이터

2.3.1 문자열

ㅇ수치 이외에 문자열 데이터도 다루겠음. member() 함수 소개

2.3.2 예제: 기호 미분

ㅇ기호미분 함수

- input: 대수식, 변수

- output: 도함수(derivative)

ㅇ추상데이터에 기초한 미분 프로그램

- 대수식의 구성과 구축에 필요한 함수들이 이미 주어졌다고 가정하고 미분프로그램 구성

ㅇ대수식의 표현

- 기호를 목록으로 나열 (전위 표기법)

- 함수 구현: is_variable부터 make_product까지 (JS 책에는 make_product 안 보임)

- 문자열의 나열로 끝나버리는 문제 -> 둘 다 숫자이면 연산결과를 리턴하도록 변경 -> 조금 단순해짐

2.3.3 예제: 집합의 표현

ㅇ순서 없는 목록으로 표현한 집합

- 각 함수의 구현: is_element, adjoin, intersection

- adjoin과 intersection은 is_element를 포함, 복잡도가 is_element에 의해 결정됨

- 복잡도: is_element, adjoin은 O(n), intersection은 O(n^2)

ㅇ순서 있는 목록으로 표현한 집합

- is_element의 복잡도가 반으로 줄어듦 (n/2) -> 여전히 O(n)이나 intersection의 경우 O(n)으로 줄어듦

ㅇ이진 트리로 표현한 집합

- 항목(entry)을 기준으로 왼쪽은 더 작은, 오른쪽은 더 큰 항목이 담아야함

- 트리에서의 검색은 단계별 복잡도가 n/2 이므로 증가 차수는 O(logn)이 됨

- 표현: 요소가 세 개인 목록(list)으로 표현: make_tree(entry, left, right)

- is_element, adjoin 복잡도 O(logn)

- 균형 문제를 해결하기 위한 연산이 추가되는게 일반적임

ㅇ집합과 정보 검색

- 효율적인 탐색에는 key가 필수: 순서 없는 목록에 쓰이는 lookup 함수 예시

- random access가 많기 때문에 바이너리 트리 기반 데이터구조가 더 적합

2.3.4 허프만 부호화 트리

- 가변 길이 부호임. 부호의 시작과 끝을 구분하는 전략이 중요. -> 상대 도수 활용(relative frequency)

---

2.4 추상 데이터의 다중 표현

ㅇ한 종류의 데이터 객체를 두 가지 이상의 방식으로 표현할 수도 있어야하며, 각 표현 방식에 대응되는 시스템 구축이 필요한 경우가 있음

ㅇ키워드: 가산적(additive), 일반적 함수(generic function), 형식 태그(type tag), 데이터 지향적 프로그래밍(data-directed programming)

ㅇ예제: 복소수

- 표현: 직교좌표, 극좌표

- 동작: 산술 연산(add, sub, mul, div)

2.4.1 복소수의 여러 표현

ㅇ덧셈과 뺄셈에서는 직교좌표 형태가, 곱셈과 나눗셈에서는 극좌표 형태가 자연스럽지만, 결국에는 사용자 입장에서 표현 방식 두 가지 경우에 대해 모든 연산이 동작되어야 함

ㅇ추상 데이터로서의 구현

- 생성자 2개: make_from_real_img, make_from_mag_ang

- 연산자 4개: add, sub, mul, div

ㅇ벤: 직교좌표

- 실수(real), 허수(imag) 를 값으로 가지고 있고, 기울기(magnitude)와 각도(angle)를 연산

ㅇ알리사: 극좌표

- 기울기, 각도를 값으로 가지고 있고, 삼각함수 관계식으로 실수와 허수를 연산

-> 두 표현방식 모두에 대응할 수 있게 됨 

-> 추상화 원칙에 따라 산술 연산 동작도 잘 동작할 것

2.4.2 태그된 데이터

ㅇ데이터 추상화 = 사전 결정 최소화의 원리

- 선택자와 생성자 설계를 통해 추상화 장벽을 세우고나서 나중에 구체적인 표현방식을 결정

- 형식태그(type tag)를 사용한다면 선택자와 생성자 설계 이후에도 선택권을 가질 수 있음(둘 중 어떤 방식으로 동작하게 할 지에 대한 선택권)

ㅇ형식태그 부여: attach_tag(type_tag, contents)

ㅇ타입 해당 여부 반환: is_rectangular, is_polar

ㅇ이제 벤과 알리사의 방식이 공존 가능하나 수정되어야할 것들이 있음

1) 생성자: 형식태그 기입 (attach_tag)

2) 선택자: 함수 이름에 접미사로 형식 기입

-> 합쳐서 다시 상위 함수로 real, imag, mag, angle_part 를 도출함

-> 산술 연산은 이전과 동일하게 동작함

2.4.3 데이터 지향적 프로그래밍과 가산성

ㅇ직전에 한 것(타입으로 함수를 선택) = 형식 기반 디스패치(dispatching on type)의 약점 2개

1) 형식이 추가되면 형식을 점검하는 조건절도 추가되어야 한다는 제약

2) 함수 이름 중복을 피해야한다는 제약

-> 가산성(additivity)이 없어 추가되는 내용이 있을 때마다 계속 수정해야한다는 문제점 발생

-> 데이터 지향적 프로그래밍으로 해결 가능

ㅇ데이터 지향적 프로그래밍?

- 연산 이름-인수 형식 테이블을 활용하여 함수 사용

- 테이블 조작 함수(일단 제공됨): put(연산, 형식, 항목), get(연산, 형식)

- 패키지 형태로 각 표현에 따른 함수들을 묶고(동일한 이름으로), 이를 테이블에 등록하는 연산을 패키지 내부에서 수행함

- apply_generic(op, args) 함수를 통해 테이블에 접근하여 복소수 표현방식에 따른 함수가 선택적으로 적용되게 함

-> 연산-형식 테이블의 행 분해임

ㅇ메시지 전달(= 연산-형식 테이블의 열 분해)

- 연산 이름 기반 디스패치 전략

- 3장에서 자세하게 다룰 예정

 

---

2.5 (다른 발제자)

---

Note

TBU