[Program Synthesis #6] Representation-Based Synthesis: 탐색 공간을 압축하는 방법
Program Synthesis 시리즈 6편 – 프로그램을 하나씩 탐색하는 대신, 탐색 공간 자체를 압축하는 Representation-Based Synthesis의 핵심 아이디어 이해하기
들어가며 — 탐색에서 표현으로
지금까지 우리는 Program Synthesis를 “탐색 문제”로 다뤄왔다.
- 가능한 프로그램을 생성하고 (enumeration)
- 불필요한 후보를 제거하며 (pruning)
- 더 가능성 높은 것부터 탐색하는 (prioritization)
방식이었다.
이 접근은 강력하지만, 하나의 근본적인 한계를 가진다.
프로그램을 여전히 “하나씩” 다루고 있다는 점이다
아무리 탐색을 개선해도 다음 구조는 변하지 않는다.
\[e_1, e_2, e_3, \dots\]즉, 프로그램을 개별 객체로 취급한다.
이 방식이 문제가 되는 이유는 간단하다.
- 서로 매우 비슷한 프로그램이 반복되고
- 동일한 의미를 가지는 표현이 많으며
- 구조적으로 겹치는 부분이 존재한다
이건 단순한 비효율이 아니라,
문제를 잘못 표현하고 있다는 신호다.
그래서 다음 단계에서는 관점을 바꾼다.
프로그램을 하나씩 탐색하지 않는다
대신 이렇게 생각한다.
많은 프로그램을 한 번에 다룰 수는 없을까?
이 질문에서 출발한 접근이 바로
Representation-Based Synthesis
이다.
이 방식에서는 탐색 자체를 개선하는 대신,
탐색 공간을 표현하는 방식을 바꾼다
이 글에서는 다음을 다룬다.
- 프로그램 집합을 다루는 기본 개념 (version space)
- 이를 압축해서 표현하는 방법 (VSA)
- 왜 이 방식이 탐색보다 더 강력한지
이 시점부터 synthesis는 더 이상 단순한 탐색 문제가 아니다.
구조를 다루는 문제로 바뀐다
Representation-Based Synthesis — 탐색 공간을 압축하는 방법
앞에서 우리는 프로그램을 하나씩 탐색하는 방식의 한계를 살펴봤다.
이제 그 한계를 조금 더 구체적으로 들여다보자.
문제의 본질
Enumerative 방식에서 우리가 다루는 것은 다음과 같다.
\[e_1, e_2, e_3, \dots\]즉, 프로그램을 하나씩 생성하고 검사한다.
이 방식이 비효율적인 이유는 단순히 “개수가 많아서”가 아니다.
더 근본적인 문제는 다음에 있다.
- 서로 매우 비슷한 프로그램이 반복된다
- 동일한 의미를 가지는 프로그램이 여러 형태로 존재한다
- 구조적으로 동일한 부분이 계속 재사용된다
예를 들어 다음과 같은 프로그램들을 생각해보자.
1
2
3
Concat("4", "25")
Concat("42", "5")
Concat(Concat("4", "2"), "5")
이 프로그램들은 서로 다르지만,
결과는 모두 "425"이다.
즉 우리는 지금
“같은 의미를 가진 프로그램들을 계속 따로따로 탐색하고 있다”
관점 전환
여기서 중요한 아이디어가 나온다.
프로그램을 하나씩 보지 말고
“프로그램들의 집합”을 한 번에 표현하자
즉,
- 기존: 하나의 프로그램 \(e\)
- 변경: 프로그램 집합 \(E\)
이렇게 되면 탐색은 다음처럼 바뀐다.
- 프로그램 하나 생성 → 검사
→ 프로그램 집합 생성 → 집합 단위로 처리
Representation의 역할
이 접근에서 핵심은 representation이다.
많은 프로그램을 “압축해서 표현”하는 방법
좋은 representation은 다음을 만족해야 한다.
- 많은 프로그램을 하나로 묶는다
- 구조를 유지한다
- 효율적으로 연산 가능하다
결과적으로 바뀌는 것
이제 탐색은 더 이상
프로그램을 하나씩 나열하는 과정
이 아니라
프로그램 공간을 구조적으로 탐색하는 과정
이 된다.
다음 단계
이 아이디어를 실제로 구현한 대표적인 방법이 있다.
Version Space Algebra (VSA)
이건
- 프로그램 집합을 symbolic하게 표현하고
- enumeration 없이도 후보를 다룰 수 있게 해준다
Version Space Algebra — 프로그램 집합을 다루는 방식
앞에서 프로그램을 “하나씩” 다루는 대신
“집합으로 다루자”는 아이디어를 봤다.
이걸 실제로 구현한 대표적인 구조가
Version Space Algebra (VSA)이다.
Version Space의 개념
먼저 version space부터 정의하자.
주어진 예제를 만족하는 모든 프로그램의 집합
형식적으로 쓰면 다음과 같다.
\[VS_{H, D} = \{ h \in H \mid \forall (i, o) \in D,\ h(i) = o \}\]- \(H\): 가능한 프로그램 전체 (hypothesis space)
- \(D\): input-output example 집합
즉,
“현재까지의 예제를 모두 만족하는 프로그램들”
을 모아놓은 것이 version space다.
문제: 이 집합은 너무 크다
이 정의는 깔끔하지만 바로 문제가 생긴다.
- \(H\) 자체가 매우 크고
- \(VS\) 역시 엄청난 크기를 가질 수 있다
이걸 naive하게 표현하면:
1
{ program1, program2, program3, ... }
이건 다시 enumeration으로 돌아가는 것과 같다.
집합을 만들었지만, 여전히 “하나씩 나열”하고 있다
그래서 필요한 것이 바로
symbolic representation
이다.
VSA의 핵심 아이디어
VSA는 version space를 다음과 같이 표현한다.
프로그램 집합을 그래프 구조로 압축한다
이 구조는 세 가지 요소로 이루어진다.
1. Direct Set
가장 기본적인 형태다.
1
{ P1, P2, ..., Pk }
단순히 프로그램들의 집합이다.
하지만 이건 여전히 비효율적이다.
그래서 더 중요한 구조가 등장한다.
2. Union (합집합)
두 version space를 합치는 연산이다.
\[VS = VS_1 \cup VS_2\]이건 의미적으로 다음과 같다.
“이 프로그램이거나, 저 프로그램이다”
중요한 점은:
실제로 프로그램을 전부 나열하지 않아도 된다
3. Join (결합)
가장 중요한 연산이다.
형태는 다음과 같다.
\[F(VS_1, VS_2, ..., VS_k)\]이건 의미적으로 다음을 뜻한다.
“각 argument에서 하나씩 선택해서 함수에 넣는다”
예를 들어:
1
Concat(VS1, VS2)
이면,
- VS1에서 하나
- VS2에서 하나
를 선택해서 모든 조합을 만든다.
하지만 중요한 점은:
이 모든 조합을 실제로 만들지 않는다
핵심: “지연된 표현”
VSA의 핵심은 이것이다.
프로그램을 실제로 생성하지 않고
가능한 프로그램들을 상징적으로 표현한다
즉,
- enumeration → explicit
- VSA → symbolic
예시로 보면
문자열 "425"를 만드는 모든 프로그램을 생각해보자.
가능한 프로그램은 많다.
"425"- Concat(“4”, “25”)
- Concat(“42”, “5”)
- Concat(“4”, Concat(“2”, “5”))
이걸 naive하게 표현하면 매우 커진다.
하지만 VSA는 이렇게 표현한다.
1
2
3
4
5
Union(
"425",
Concat(VS("4"), VS("25")),
Concat(VS("42"), VS("5"))
)
이건 수많은 프로그램을 압축해서 표현한 것이다.
왜 중요한가
이 방식의 효과는 매우 크다.
- 중복된 구조 제거
- 공통 부분 공유
- exponential space를 compact하게 표현
즉,
탐색 공간 자체를 줄이는 것이 아니라
표현 방식을 바꿔서 다룰 수 있게 만든다
관점 변화
이 시점에서 synthesis는 완전히 다른 문제가 된다.
기존:
프로그램을 생성하고 검사한다
이제:
프로그램 집합을 구성하고, 그 안에서 선택한다
이 차이는 단순한 최적화가 아니라
문제 자체의 표현 방식이 바뀐 것
이다.
VSA의 효율성 — DAG와 공유 구조
앞에서 VSA가 프로그램 집합을 압축해서 표현한다고 했다.
이게 실제로 왜 효과적인지는 구조를 보면 명확해진다.
Tree가 아니라 DAG
일반적인 program 표현은 tree 구조다.
예를 들어:
1
Concat(Concat("4", "2"), "5")
이건 AST로 보면 완전히 tree다.
문제는 tree 표현에서는 같은 부분 구조가 반복된다는 점이다.
예를 들어:
"4""2""5"
이런 sub-expression이 여러 번 등장한다.
VSA는 이걸 다르게 본다.
동일한 sub-expression을 하나의 노드로 공유한다
즉 구조가 이렇게 바뀐다.
- Tree → DAG (Directed Acyclic Graph)
Sharing의 의미
DAG에서는 같은 의미를 가진 sub-program이 한 번만 저장된다.
예를 들어:
1
2
3
VS("4")
VS("2")
VS("5")
이 노드들은 여러 프로그램에서 공통으로 사용된다.
이걸 통해 얻는 효과는 명확하다.
- 중복 제거
- 메모리 절약
- 연산 공유
Join 연산의 실제 의미
VSA에서 가장 중요한 연산은 Join이었다.
\[F(VS_1, VS_2)\]이걸 naive하게 생각하면:
- 모든 조합 생성
- 프로그램 수 폭발
하지만 실제로는 다르다.
조합을 생성하지 않고 “가능성”만 표현한다
즉 Join은 다음과 같다.
- explicit enumeration ❌
- implicit representation ✅
이 차이가 핵심이다.
복잡도 관점
일반 enumeration에서는:
- 프로그램 수 = exponential
하지만 VSA에서는:
- 노드 수 = 훨씬 작음
- 구조 공유로 압축됨
즉,
exponential space를 polynomial 구조로 표현할 수 있다
물론 완전히 polynomial로 떨어지는 것은 아니지만,
실제 문제에서는 엄청난 차이를 만든다.
왜 가능한가
이게 가능한 이유는 프로그램 공간의 특성 때문이다.
프로그램들은 완전히 독립적이지 않다.
- 같은 sub-expression을 공유하고
- 같은 패턴이 반복되며
- 구조적으로 겹친다
VSA는 이 “겹침”을 활용한다.
핵심 정리
- Enumeration → 프로그램을 하나씩 나열
- VSA → 프로그램들을 하나의 구조로 압축
이 차이는 단순한 최적화가 아니다.
탐색 공간을 표현하는 방식 자체가 바뀐다
다음 단계로 자연스럽게 이어지는 질문
이제 중요한 질문이 하나 남는다.
이 구조를 실제로 어떻게 만들 것인가?
즉,
- VSA를 어떻게 생성하고
- 어떻게 업데이트하며
- 어떻게 정답을 선택하는가
이걸 다음에서 다룬다.
VSA를 실제로 만드는 방법 — Top-down과 Bottom-up의 결합
앞에서 VSA는 프로그램 집합을 압축해서 표현한다고 했다.
이제 중요한 질문은 이것이다.
이 구조를 실제로 어떻게 만들 것인가?
다시 문제로 돌아가자
우리는 다음 문제를 풀고 있다.
\[VS_{H, D} = \{ h \in H \mid \forall (i, o) \in D,\ h(i) = o \}\]즉,
주어진 예제를 만족하는 모든 프로그램을 구하는 것
이걸 naive하게 하면:
- 모든 프로그램 생성
- 하나씩 검사
하지만 VSA에서는 다르게 접근한다.
조건을 만족하는 프로그램 집합을 “직접 구성한다”
핵심 아이디어
VSA 생성은 다음 두 가지 아이디어의 결합이다.
- Top-down: 출력으로부터 가능한 구조를 제한
- Bottom-up: 작은 프로그램부터 조합
이 둘을 결합하면:
불필요한 프로그램을 애초에 만들지 않는다
Step 1 — 출력으로부터 역추론 (Top-down)
예제를 하나 보자.
1
2
input: x
output: "425"
이제 질문을 바꾼다.
어떤 프로그램이 “425”를 만들 수 있는가?
가능한 형태는 제한된다.
예:
- “425”
- Concat(“4”, “25”)
- Concat(“42”, “5”)
이 단계에서 이미 많은 프로그램이 제거된다.
output을 만들 수 없는 구조는 고려하지 않는다
Step 2 — 부분 문제로 분해
Concat(“4”, “25”)를 생각해보자.
이건 다음 조건으로 나뉜다.
- 왼쪽 부분 → “4”
- 오른쪽 부분 → “25”
즉 문제는 다음처럼 분해된다.
- VS₁: “4”를 만드는 프로그램 집합
- VS₂: “25”를 만드는 프로그램 집합
이걸 재귀적으로 적용한다.
Step 3 — Bottom-up으로 조합
이제 각 부분에 대한 version space를 만들었으면,
\[VS = Concat(VS_1, VS_2)\]형태로 결합한다.
여기서 중요한 점:
실제 프로그램을 만들지 않고
구조만 연결한다
전체 흐름
이 과정을 정리하면 다음과 같다.
- 원하는 output으로부터 가능한 연산을 추론한다
- 문제를 subproblem으로 분해한다
- 각 subproblem에 대한 VSA를 만든다
- Join으로 결합한다
왜 효율적인가
이 방식의 핵심은 이것이다.
정답이 될 수 없는 프로그램은 애초에 생성하지 않는다
Enumeration에서는:
- 모든 프로그램 생성
- 나중에 버림
VSA에서는:
- 가능한 구조만 생성
- 나머지는 처음부터 배제
CEGIS와의 연결
이제 이 구조를 CEGIS와 연결해보자.
- Generator → VSA 생성
- Checker → counterexample 생성
즉 iteration마다:
- version space가 점점 줄어든다
이건 매우 중요한 성질이다.
탐색 공간이 점진적으로 수렴한다
핵심 정리
VSA 기반 synthesis는 다음과 같이 볼 수 있다.
- enumeration → 후보 생성
- VSA → 후보 집합 구성
- CEGIS → 집합 축소
즉 전체 구조는:
\[\text{Synthesis} = \text{Symbolic Space} + \text{Refinement}\]이 시점에서 synthesis는 완전히 다른 문제로 바뀐다.
프로그램을 찾는 문제가 아니라
가능한 프로그램 집합을 점점 좁히는 문제
정리 — 탐색을 넘어서, 구조를 다루는 문제로
지금까지 Program Synthesis를 “탐색 문제”로 다뤄왔다.
- 가능한 프로그램을 생성하고
- 불필요한 후보를 제거하며
- 더 가능성 높은 것부터 탐색하는 방식이었다
이 접근은 효과적이지만, 하나의 근본적인 한계를 가진다.
프로그램을 여전히 “개별 객체”로 다룬다는 점이다
VSA는 이 관점을 바꾼다.
- 프로그램을 하나씩 생성하지 않고
- 가능한 프로그램들의 집합을 구성하고
- 그 집합을 구조적으로 표현한다
이 변화는 단순한 최적화가 아니다.
탐색 방식 자체가 다음처럼 바뀐다.
- explicit enumeration → symbolic representation
- 개별 후보 → 프로그램 집합
- 생성 → 구성
이제 synthesis는 더 이상
프로그램을 찾는 과정
이 아니라
가능한 프로그램 공간을 점점 좁혀가는 과정
으로 이해할 수 있다.
이 관점은 이후의 모든 기법의 기반이 된다.
- 더 복잡한 representation
- 더 강력한 constraint 결합
- 더 정교한 탐색 전략
다음 글에서는 이 흐름을 이어서,
VSA 외의 다른 representation 방식들
을 살펴본다.
각 접근이 어떤 문제에 적합한지,
그리고 서로 어떻게 다른지를 비교해볼 것이다.