---
title: 전파 모델
tags: [concept, SDF]
sources: [SDF-ch1-flexibility, SDF-ch5-evaluation, SDF-ch6-layering, SDF-ch7-propagation]
updated: 2026-04-30
---

# 전파 모델

## 한 줄 정의

공유 셀로 연결된 자율적 전파기들이 부분 정보를 단조적으로 축적·전파하는 다방향 계산 모델로, 의존성 추적과 결합하면 지능적 백트래킹이 가능한 비결정적 탐색 엔진이 된다.

## 핵심 내용

### 폰 노이만 모델에서의 이탈

전통적 프로그래밍은 폰 노이만 모델을 따른다: 변수는 값 하나를 담고, 표현식은 트리 구조를 타고 올라가며 평가되며, 제어 흐름은 순차적·방향성을 가진다.

이 모델의 근본적 한계: **단방향성**. `v = a * b`는 `v`를 계산하지만, `a`나 `b`를 역으로 구하려면 별도의 수식이 필요하다. 물리 법칙 `F = G*m1*m2/r²`는 6개의 역방향 관계를 함께 담고 있지만, 코드로는 하나의 방향만 표현된다.

전파 모델은 이 단방향성을 깬다:

> "The propagator model is built on the idea that the basic computational elements are propagators, autonomous independent machines interconnected by shared cells through which they communicate."

### 셀과 전파기: 두 기본 요소

**셀(cell)**: 정보를 축적하는 공유 저장소.
- 하나의 값 대신 *현재까지 알려진 최선의 정보*를 담는다
- 새 정보가 도착하면 기존 정보와 **병합(merge)**: 단조적, 정보를 잃지 않음
- 모순이 감지되면 신호를 보냄

**전파기(propagator)**: 셀들을 연결하는 자율 기계.
- 입력 셀들의 값을 읽어 계산하고 출력 셀에 정보를 추가
- 입력이 변하면 자동으로 재실행
- 독립적: 다른 전파기의 존재를 모른다

```scheme
;; 곱셈 제약: a * b = c (세 방향 모두)
(define-c:prop (c:* a b c)
  (p:* a b c)    ; c = a * b
  (p:/ c a b)    ; b = c / a (a가 알려지면)
  (p:/ c b a))   ; a = c / b (b가 알려지면)
```

### 배선도 언어

전파 네트워크는 **배선도(wiring diagram)**로 표현된다. 표현식 트리가 아니라 셀(와이어)과 전파기(게이트)로 이루어진 회로도다. 이 비유는 매우 자연스럽다:
- 회로의 와이어는 셀
- 회로의 게이트는 전파기
- 회로 구성 = 전파 네트워크 구성

배선도의 특성:
- **다방향**: 와이어는 양방향. 신호가 어느 방향으로도 흐를 수 있음
- **병렬적**: 여러 게이트가 독립적으로 활성화
- **부분 결과 즉시 사용**: 전체 완료를 기다릴 필요 없음
- **확장 가능**: 새 게이트를 연결하면 기능 추가

### 부분 정보와 구간 산술

셀은 숫자 하나 대신 구간을 값으로 가질 수 있다:

```scheme
(make-interval 2.5 3.1)  ; "2.5 이상 3.1 이하"
```

두 측정이 같은 셀에 정보를 제공할 때 교집합을 취한다:
```
구간 [2.5, 3.1] ∩ [2.8, 3.5] = [2.8, 3.1]  ; 더 정확해짐
구간 [2.5, 3.1] ∩ [4.0, 5.0] = ∅           ; 모순!
```

퇴화성 원칙의 구현: 여러 독립 소스가 동일한 셀에 구간 정보를 제공하고, 시스템이 자동으로 병합하여 더 정확한 답을 낸다.

### 의존성 추적과 전제

레이어링(Ch6)의 의존성 레이어를 전파 모델에 통합하면, 각 셀의 값이 어떤 전제(premise)에서 유래했는지를 추적한다:

```scheme
(tell! Vega-parallax interval 'FGWvonStruve1837)
;; 이 값의 전제: FGWvonStruve1837
```

파생된 값의 전제 집합 = 모든 기여 전제들의 합집합. 전파되는 값에 의존성 정보가 자동으로 따라간다.

이를 통해 두 가지 능력이 생긴다:
1. **설명(explanation)**: "이 결론이 어떤 데이터에서 유래했는가?"
2. **지능적 백트래킹**: 모순의 원인을 파악하여 관련 없는 선택지를 재탐색하지 않음

### 의존성 지향 백트래킹

Ch5의 amb는 실패하면 직전 선택지로 돌아가는 연대기적(chronological) 백트래킹을 사용한다. 이는 이미 검증된 부분을 불필요하게 재탐색하는 비효율이 있다.

의존성 지향 백트래킹(dependency-directed backtracking):

1. 각 결정(hypothesis)이 전제 레이블을 가짐
2. 모순 발생 → 모순을 일으킨 전제들의 집합(nogood set) 파악
3. 이 전제들 중 하나를 번복하는 선택지로 직접 점프
4. 관련 없는 선택지들은 건너뜀

예: 100개의 선택지 중 1번과 50번이 모순을 일으킨다면, 2~49번은 탐색하지 않고 바로 1번 또는 50번을 번복하는 선택지를 찾는다.

### 가산적 확장의 완성형

전파 네트워크는 가산적 프로그래밍의 이상에 가장 가깝다:

> "The structure is additive: new ways to contribute information can be included just by adding new parts to a network, whether simple propagators or entire subnetworks."

새 추정 방법은 새 전파기 추가. 새 제약은 새 제약 전파기 추가. 기존 네트워크는 전혀 수정하지 않는다.

## SDF에서의 등장

- [[SDF-ch1-flexibility]]: 탐색적 행동, 퇴화성, 생성-검증 메커니즘으로 동기 부여. 전파 모델의 철학적 선구자
- [[SDF-ch5-evaluation]]: amb가 연대기적 백트래킹을 구현. 전파 모델이 이를 의존성 지향으로 업그레이드한다는 관계
- [[SDF-ch6-layering]]: 의존성 레이어가 전파 시스템의 핵심 재료. 없으면 의존성 지향 백트래킹 불가
- [[SDF-ch7-propagation]]: 핵심 챕터. 셀/전파기 구조, 구간 산술, 전제를 가진 값, 의존성 지향 백트래킹, 배선도 언어

## 실천 시 주의점

**수렴 보장**: 전파기 네트워크가 무한 루프 없이 고정점(fixed point)에 수렴한다는 보장이 필요하다. 단조적 병합이 이를 보장하는 핵심 조건이다. 비단조적 업데이트(값을 번복하거나 구간을 넓히는 것)가 있으면 수렴이 보장되지 않는다.

**디버깅의 어려움**: 다방향 전파는 "이 값이 어디서 왔는가?"를 추적하기 어렵게 만들 수 있다. 의존성 추적이 이 문제를 부분적으로 해결하지만, 복잡한 네트워크에서는 여전히 어렵다.

**순환 의존성**: 셀 A의 값이 전파기를 통해 셀 B에 영향을 주고, 셀 B가 다시 셀 A에 영향을 줄 때 순환이 발생한다. 이것이 의미 있는 제약(예: `x + y = z, x - y = w`)인지 아니면 실수인지 구분이 필요하다.

**확장의 위험**: "새 전파기를 추가만 하면 된다"는 가산성이 실제로는 기존 네트워크의 동작을 변경할 수 있다. 새 전파기가 기존 셀에 더 좁은 구간을 강요하면 이전에 유효했던 값이 모순이 될 수 있다.

## 관련 개념

- [[additive-programming]] — 배선도에 전파기 추가가 가장 순수한 형태의 가산적 확장
- [[partial-information]] — 셀은 부분 정보를 단조적으로 축적하는 저장소
- [[degeneracy]] — 여러 전파기가 동일 셀에 독립적 추정값을 제공하는 퇴화적 구조
- [[layered-data]] — 의존성 레이어가 전파 시스템의 지능적 백트래킹을 가능하게 함
- [[domain-specific-language]] — 배선도 언어 자체가 제약 기반 DSL