ea46da91db
Software Design for Flexibility (Hanson & Sussman 2021) 전문을 wiki/sources/ 아래 챕터별 한국어 wiki 페이지로 컴파일 - SDF-overview: 전체 개요, 챕터 관계도, 공통 테마 - SDF-ch1: 가산적 프로그래밍 철학, 퇴화성, 유연성 비용 - SDF-ch2: 컴비네이터, DSL, 래퍼, 도메인 모델 - SDF-ch3: 제네릭 프로시저, 자동 미분, 트라이 디스패치 - SDF-ch4: 패턴 매칭, 항 재작성, 단일화, 타입 추론 - SDF-ch5: eval/apply, lazy eval, amb, call/cc - SDF-ch6: 레이어드 데이텀/프로시저, 단위 산술, 의존성 추적 - SDF-ch7: 전파 모델, 부분 정보 결합, 의존성 지향 백트래킹 wiki/index.md Sources 섹션 등록, wiki/log.md 기록 Co-Authored-By: Claude Sonnet 4.6 <noreply@anthropic.com>
152 lines
5.8 KiB
Markdown
152 lines
5.8 KiB
Markdown
---
|
|
title: "Ch5: Evaluation"
|
|
tags: [source, SDF]
|
|
source: "Software Design for Flexibility, Hanson & Sussman (2021)"
|
|
chapter: 5
|
|
updated: 2026-04-30
|
|
---
|
|
|
|
# Ch5: Evaluation
|
|
|
|
## 핵심 아이디어
|
|
|
|
문제 해결의 가장 강력한 방법 중 하나는 그 해법을 쉽게 표현할 수 있는 도메인 특화 언어를 만드는 것이다. 이 장은 인터프리터를 점진적으로 발전시키면서 **lazy evaluation**, **컴파일(분석/실행 분리)**, **비결정적 평가(amb)**, **연속(continuations)** 등 언어 설계의 핵심 기법을 보여준다.
|
|
|
|
## 주요 개념
|
|
|
|
### 5.1 제네릭 eval/apply 인터프리터
|
|
|
|
인터프리터의 핵심: `eval`과 `apply`의 상호 재귀.
|
|
|
|
- `eval`: 표현식 + 환경 → 값 (표현식의 타입별로 제네릭 프로시저로 처리)
|
|
- `apply`: 프로시저 + 인수 → 값 (프로시저 본문을 새 환경에서 eval)
|
|
|
|
**g:eval을 제네릭 프로시저로 구현**하는 이유: 새 표현식 타입을 핸들러 추가만으로 도입 가능.
|
|
|
|
```scheme
|
|
(define g:eval
|
|
(simple-generic-procedure 'eval 2 default-eval))
|
|
|
|
;; 기본 케이스: 적용(application)
|
|
(define (default-eval expression environment)
|
|
(cond ((application? expression)
|
|
(g:apply (g:advance (g:eval (operator expression)
|
|
environment))
|
|
(operands expression)
|
|
environment))
|
|
(else (error "Unknown expression type" expression))))
|
|
```
|
|
|
|
**g:advance**: 지연된 평가를 재개하는 제네릭 프로시저. 기본적으로 항등함수이나, lazy evaluation 도입 시 활성화됨.
|
|
|
|
**비평가 피연산자(unevaluated operands)를 apply에 전달**: applicative-order와 normal-order 평가 모두를 나중에 지원할 수 있게 하는 유연한 설계 결정.
|
|
|
|
각 표현식 타입에 대한 핸들러:
|
|
- 자기 평가 표현식(숫자, 불리언, 문자열): 그대로 반환
|
|
- 인용(quote): 보호된 부분식 반환
|
|
- 변수: 환경에서 조회
|
|
- if: 술어 평가 후 귀결 또는 대안 평가
|
|
- lambda: 프로시저 객체 생성 (환경 포함)
|
|
- define, set!: 환경 수정
|
|
|
|
### 5.2 Lazy Evaluation (지연 평가)
|
|
|
|
형식 매개변수에 **선언(declaration)**을 추가하여 평가 전략을 지정:
|
|
|
|
```scheme
|
|
(lambda ((lazy x) y) ; x는 필요할 때만 평가
|
|
...)
|
|
|
|
(lambda ((lazy-memo x) y) ; x는 필요할 때 평가하고 결과를 메모이즈
|
|
...)
|
|
```
|
|
|
|
**thunk**: 아직 평가되지 않은 표현식 + 환경의 묶음. g:advance가 필요 시 강제 평가.
|
|
|
|
선언은 타입, 단위 등 다른 정보에도 활용 가능.
|
|
|
|
### 5.3 분석/실행 분리 (Analysis/Execution Separation)
|
|
|
|
인터프리터의 비효율: 동일한 표현식을 만날 때마다 반복 분석.
|
|
|
|
해결책: 해석을 두 단계로 분리:
|
|
1. **분석 단계**: 표현식을 검사하여 **실행 프로시저** 생성
|
|
2. **실행 단계**: 실행 프로시저를 환경에 적용
|
|
|
|
```scheme
|
|
;; 분석: 표현식 → 실행 프로시저
|
|
(define (analyze-if expression)
|
|
(let ((p (analyze (if-predicate expression)))
|
|
(c (analyze (if-consequent expression)))
|
|
(a (analyze (if-alternative expression))))
|
|
(lambda (env succeed fail) ; 실행 프로시저
|
|
...)))
|
|
```
|
|
|
|
실행 프로시저들은 모두 동일한 형태를 가지며, **컴비네이터 시스템**을 이룬다.
|
|
|
|
### 5.4 비결정적 평가 (Nondeterministic Evaluation, amb)
|
|
|
|
**amb 연산자**: 여러 선택지 중 하나를 비결정적으로 선택. 선택이 실패하면 자동으로 다음 선택지로 백트래킹.
|
|
|
|
```scheme
|
|
;; 피타고라스 세 쌍 찾기
|
|
(let ((a (amb 1 2 3 4 5))
|
|
(b (amb 1 2 3 4 5)))
|
|
(require (= (* a a) (+ (* b b) 1)))
|
|
(list a b))
|
|
```
|
|
|
|
**구현**: 실행 프로시저를 **연속 전달 스타일(CPS, continuation-passing style)**로 재표현.
|
|
|
|
분석 단계는 변경 없음. 실행 프로시저가 `succeed`와 `fail` 두 연속을 인수로 받음:
|
|
- `succeed(value, fail-again)`: 값이 있을 때 성공 연속 호출
|
|
- `fail()`: 실패 시 실패 연속 호출로 백트래킹
|
|
|
|
**amb 분석**:
|
|
|
|
```scheme
|
|
(define (analyze-amb expression)
|
|
(let ((cfns (map analyze (amb-choices expression))))
|
|
(lambda (env succeed fail)
|
|
(let loop ((cfns cfns))
|
|
(if (null? cfns)
|
|
(fail)
|
|
((car cfns) env succeed
|
|
(lambda () (loop (cdr cfns)))))))))
|
|
```
|
|
|
|
### 5.5 연속의 노출 (call/cc)
|
|
|
|
CPS 구조는 연속을 명시적으로 사용하게 만든다. Scheme의 `call/cc`(call-with-current-continuation)는 현재 연속을 캡처하여 제공한다.
|
|
|
|
`call/cc`만으로 amb를 직접 Scheme에서 구현 가능:
|
|
|
|
```scheme
|
|
(define (amb . choices)
|
|
(call/cc
|
|
(lambda (k)
|
|
(for-each (lambda (choice)
|
|
(call/cc (lambda (next)
|
|
(set! *fail* next)
|
|
(k choice))))
|
|
choices)
|
|
(*fail*))))
|
|
```
|
|
|
|
이는 인터프리터/컴파일러 시스템 없이 Scheme 자체 기능으로 amb의 능력을 얻는 방법이다.
|
|
|
|
## 핵심 인용
|
|
|
|
> "One of the best ways to attack a problem is to make up a domain-specific language in which the solution is easily expressed... We believe that programmers should know how to escape the confines of whatever programming language they must use by making an interpreter for a language that is more appropriate for expressing the solution to the current problem."
|
|
|
|
> "Remarkably, [adding amb] requires no change to the analysis part of the evaluator. The only change required is in the format of the execution procedures, which are re-expressed in continuation-passing style."
|
|
|
|
## 관련 개념
|
|
|
|
- [[SDF-ch2-dsl]] — DSL 구축의 궁극적 도구로서의 인터프리터
|
|
- [[SDF-ch3-generic-procedures]] — g:eval이 제네릭 프로시저로 구현됨
|
|
- [[SDF-ch4-pattern-matching]] — 패턴 매처가 인터프리터 분석 단계에 활용
|
|
- [[SDF-ch7-propagation]] — amb의 의존성 지향 백트래킹으로 발전
|
|
- [[SDF-overview]]
|