인터페이스를 따르고 표현을 고르고 언어를 합성하세요.
프로그램 열다섯 개로 표현 장벽과 재귀적 데이터, 공유 정체성, 수열 단계, 기호 생성자, 태그 디스패치, 구간과 순서, 부호 트리, 여러 표현, coercion, 희소 대수, 페인터, 프레임, 재귀 그림 합성을 연결합니다.
데이터의 추상 인터페이스와 구조와 정체성과 구체적인 표현과 선언된 변환 규칙과 기하 프레임을 뒤섞지 않고 실행을 설명할 수 있나요?
- 생성자와 선택자 뒤에 표현 숨기기
- 수열의 cdr을 따라가기
- 트리의 두 가지 재귀 따라가기
- 공유 객체와 같은 내용 구분하기
- 수열 파이프라인 단계 연결하기
- 기호 표현식 변환하기
- 타입 태그로 범용 연산 고르기
- 구간 경곗값 전파하기
- 정렬 순서로 불필요한 검색 건너뛰기
- 같은 허프만 트리로 인코딩과 디코딩하기
- 복소수 인터페이스를 유지하며 직교형과 극형 선택하기
- 명시적인 coercion과 올리기 경로로 혼합 수치 타입 맞추기
- 범용 태그 메서드로 희소 다항식 더하고 곱하기
- 단위 정사각형 페인터 하나를 정사각형 또는 기울어진 프레임에 옮기기
- 변환된 페인터를 합성하고 유한한 재귀 선분 집합 만들기
유리수와 구간과 복소수는 구체적인 내용을 생성자와 선택자 뒤에 숨깁니다. 클라이언트는 저장 형태가 아니라 추상적인 성분을 요청합니다.
수열과 트리는 데이터 구조의 모양과 같은 재귀를 사용합니다. 공유 순서쌍에서는 두 경로가 같은 할당을 가리키는지 여부가 따로 관찰됩니다.
파이프라인과 기호 미분은 각 단계의 입력과 출력 표현을 경계로 사용합니다. 태그 디스패치는 표현에 맞는 프로시저를 선택하되 호출자에게 내용 구조를 퍼뜨리지 않습니다.
정렬 집합은 순서 불변식으로 불필요한 꼬리 검색을 건너뜁니다. 허프만 트리는 한 표현으로 기호에서 비트로, 다시 비트에서 기호로 이동합니다. 복소수 연산은 같은 인터페이스 아래에서 각 계산에 편한 표현을 고릅니다.
혼합 타입 프로그램은 변환 규칙을 산술 메서드와 분리합니다. 다항식 패키지는 변수와 내림차순 희소 항 목록을 보존하며 같은 차수를 합치고 0 계수 항을 제거합니다.
그림 언어 프로그램은 같은 추상화 방식을 기하 영역에 적용합니다. 페인터는 단위 정사각형 선분을 나중에 받은 프레임으로 옮깁니다. 변환 조합기는 하위 프레임을 만들고 새 페인터를 반환하며 마지막 paint 호출에서만 SEG 출력이 생깁니다. SVG는 별도 TypeScript 그림 모델이 아니라 그 리스펙스 transcript 줄에서 만들어집니다.
(begin
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(let ((answer (add-rat (make-rat 1 2) (make-rat 1 3))))
(/ (numer answer) (denom answer))))- 출력
- —
- 값
- —
- 진단
- —
각 예제는 대응하는 제2장 수업의 첫 실행 결과와 같습니다. 마지막 두 프로그램은 각각 SEG 줄 여섯 개와 열두 개를 출력하고 (segments 6)과 (segments 12)를 반환하며 그림 시각화는 그 transcript를 렌더링합니다.
선택자, cdr 재귀, 트리 분기, 공유 객체 변경, 수열 중간값, 기호 생성자, 태그 표 조회, 경계 선택, 정렬 비교, 허프만 가지 선택, 복소수 표현 디스패치, coercion 재시도, 다항식 항 병합, 프레임 좌표 변환, 하위 프레임 만들기, 마지막 SEG 출력을 찾아보세요.
데이터 시스템을 생각하는 질문 열다섯 개
추상화 장벽은 어떤 변경에서 우리를 보호해 줄까요?
답 순서쌍은 유용한 구현 장치이지만 공개해야 할 생각 그 자체는 아닙니다. 표현 방식에 대한 지식을 작은 인터페이스 뒤에 두면 나중의 변경이 다른 코드까지 퍼지지 않습니다.
재귀 프로시저는 리스트의 모양을 어떻게 따라갈까요?
답 벡터는 인덱스를 사용하는 수열 약속입니다. vector-ref는 위치로 항목을 고르고 vector-set!은 전체 벡터를 다시 만들지 않고 한 위치를 바꿉니다.
하나의 프로시저가 트리의 모든 깊이에서 어떻게 동작할까요?
답 제어 구조가 데이터 정의와 같은 모양을 가집니다. 그래서 얕은 리스트와 깊게 중첩된 트리를 깊이마다 따로 처리하지 않고 같은 프로시저로 다룰 수 있습니다.
내용이 같은 것과 하나의 객체를 공유하는 것은 왜 다를까요?
답 출력의 #0=는 공유 객체를 처음 소개하고 #0#는 바로 그 객체를 다시 가리킵니다. 이런 표시는 일반 리스트 표기가 감출 수 있는 정체성을 보존합니다.
수열 파이프라인은 중첩된 재귀를 어떻게 이름 붙은 단계로 바꿀까요?
답 accumulate는 +와 초기값 0으로 바뀐 수열을 값 하나에 모읍니다. 전체 프로그램은 여전히 재귀하지만 제어가 하나의 특수 목적 프로시저에 뒤섞이지 않고 다시 쓸 수 있는 단계에 나뉘어 있습니다.
데이터 생성자는 대수 단순화와 미분 규칙을 어떻게 나눌까요?
답 make-sum과 make-product가 표현 정리를 맡습니다. 0을 더하는 경우와 0 또는 1을 곱하는 경우를 없애고 숫자끼리는 계산하므로 미분 분기에서는 수학 규칙을 단순화 세부 사항과 섞지 않아도 됩니다.
연산 표는 서로 다른 표현에서도 하나의 인터페이스를 어떻게 유지할까요?
답 apply-generic은 get이 맞는 프로시저를 고른 뒤에야 태그를 떼고 내용만 넘깁니다. 사용하는 코드는 magnitude와 태그가 붙은 데이터만 주면 되며 어떤 표현인지 직접 묻지 않습니다. 새 표현을 더할 때 바뀌는 곳은 범용 인터페이스가 아니라 표입니다.
산술은 두 경곗값의 저장 방식에 기대지 않고 범위를 어떻게 사용할까요?
답 덧셈은 두 아래 경곗값과 두 위 경곗값을 각각 더합니다. 곱셈은 구간이 0을 지날 때 가장 작거나 큰 결과가 다른 끝점 조합에서 나올 수 있으므로 네 끝점 곱을 모두 비교해야 합니다. 결과는 독립적인 경곗값 안의 가능한 곱을 포함하며 확률 모형이 아닙니다.
집합 표현이 오름차순을 약속할 때 어떤 일을 더 하지 않아도 될까요?
답 union-ordered-set은 두 머리를 비교합니다. 더 작은 값을 남기고 그 리스트만 진행하며 머리가 같으면 값 하나만 남기고 양쪽을 모두 진행합니다. 재귀 단계마다 현재 머리 하나 이상을 소비하므로 처음부터 다시 찾지 않고 정렬 순서를 유지합니다.
가중치가 있는 트리 하나가 우리가 쓰는 비트와 다시 복원하는 기호를 어떻게 함께 결정할까요?
답 인코딩은 다음 기호가 왼쪽 가지에 있는지 오른쪽 가지에 있는지 묻고 아래로 내려가기 전에 0이나 1을 기록합니다. 디코딩은 같은 결정을 반대 방향으로 소비합니다. 잎에 닿으면 그 기호를 내보내고 다음 부호를 읽기 위해 루트로 돌아갑니다. 같은 가중치에는 다른 올바른 트리가 있을 수 있지만 여기서는 명시적인 삽입 규칙이 이번 실행의 트리를 고정합니다.
복소수 인터페이스 하나가 직교형과 극형 표현의 장점을 동시에 보존하려면 어떻게 해야 할까요?
답 첫 프로그램은 3 + 4i를 두 표현으로 각각 만들고 같은 네 선택자로 관찰합니다. close?는 삼각함수를 거친 부동소수점 값이 선언한 허용 오차 안에서 일치한다는 사실을 기록합니다. 두 번째 프로그램은 실수부와 허수부를 더해 직교형 결과를 만들고, 크기를 곱하고 각도를 더해 극형 결과를 만듭니다. 공통 선택자는 어느 결과에서도 내부 내용을 노출하지 않고 추상적인 값을 확인합니다.
범용 산술은 실패한 coercion을 숨기거나 동급 표현 사이에서 무한히 왕복하지 않으면서 공통 타입을 어떻게 고를까요?
답 두 번째 프로그램은 타입 쌍마다 변환을 고르는 대신 순서가 있는 tower를 사용합니다. rank는 정수와 유리수와 복소수의 층을 정하고, raise는 바로 다음 층으로만 이동하며, raise-to는 두 값이 더 높은 입력 층에 닿을 때까지 반복합니다. 정수와 유리수는 유리수 덧셈을 사용하고 유리수와 복소수는 한 번 더 올린 뒤 복소수 덧셈을 사용합니다. 관련 없는 polynomial 태그는 rank가 없으므로 no-common-type을 반환합니다. tower는 이 순서가 있는 타입의 모호성을 줄이지만 모든 데이터 타입이 하나의 계층에 들어간다거나 아래로 내리는 일이 항상 손실 없다는 뜻은 아닙니다.
범용 산술 시스템은 항 목록의 세부 표현을 클라이언트 코드에 퍼뜨리지 않고 다항식 구조를 어떻게 다룰까요?
답 두 번째 프로그램은 한 항을 다른 다항식의 모든 항에 곱하고, 차수는 더하고 계수는 곱한 뒤, 부분 곱을 add-terms로 병합합니다. (x + 1)(x − 1)에서는 가운데 두 항이 상쇄되어 x² − 1만 남습니다. 별도 평가기는 패키지 선택자만 사용해 x = 3에서 8을 보고합니다. 이 수업은 희소 단일 변수 정수 계수 다항식만 모형화하며 조밀 표현과 다변수 정규화, 다항식 gcd, 유리 함수, 완전한 컴퓨터 대수 시스템은 구현하지 않습니다.
페인터 하나가 정사각형과 기울어진 프레임과 크기가 다른 프레임 안에서 같은 그림을 어떻게 설명할까요?
답 첫 실행은 테두리와 대각선 페인터를 정사각형 프레임에 놓습니다. 두 번째 실행은 마름모 페인터를 기울어진 프레임에 적용합니다. 페인터 정의에는 마지막 화면 좌표가 들어 있지 않습니다. 실행은 옮긴 선분마다 SEG 줄 하나를 출력하고 앱 로컬 시각화가 transcript 줄을 흑백 SVG로 읽습니다. 반환되는 (segments n) 값은 별도 관찰로 남습니다.
몇 가지 프레임 변환만으로 재사용할 수 있는 그림 조합 언어를 어떻게 만들까요?
답 첫 실행은 변환한 갈매기 모양 네 개를 한 정사각형에 놓습니다. 두 번째는 right-split을 재귀적으로 정의합니다. 왼쪽 절반에는 원래 페인터를 두고 오른쪽 절반에는 작은 복사본 두 개를 위아래로 쌓습니다. 깊이 3에서 선분 세 개짜리 기본 페인터는 옮긴 선분 45개를 만듭니다. 시각화는 리스펙스가 출력한 SEG 줄만 그리며 브라우저 렌더링 제한은 런타임 자체의 실행 한도와 구분됩니다.