프로그램 합성

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
- 2.1. 초기 연구 (1950년대 ~ 1980년대)
- 2.2. 21세기 이후의 발전
  - 2.2.1. 구문 지향 합성 (Syntax-guided Synthesis, SyGuS)
  - 2.2.2. 카운터 예제 기반 귀납적 합성 (Counter-example Guided Inductive Synthesis, CEGIS)
3. 마나와 월딩거의 프레임워크
- 3.1. 증명 규칙
4. 프로그램 합성의 과제
5. 프로그램 합성 방법
참조

1. 개요

프로그램 합성은 주어진 요구 사항을 충족하는 컴퓨터 프로그램을 자동으로 생성하는 기술이다. 1957년 앨런조 처치의 연구를 시작으로, 인공지능 연구와 수학적 접근 방식을 통해 발전해 왔다. 프로그램 합성의 방법으로는 형식 기법, 입출력 예시, 자연어 이해 등이 있으며, 특히 21세기 이후 형식 검증 커뮤니티의 관심을 받으며 구문 지향 합성(SyGuS)과 카운터 예제 기반 귀납적 합성(CEGIS)과 같은 기술이 개발되었다. 마나와 월딩거의 프레임워크는 1차 논리 명세로부터 함수형 프로그램을 합성하는 접근 방식을 제시했으며, 프로그램 합성은 자동 생성된 프로그램의 최적화, 고수준 추상화, 매개변수 관리 등과 같은 과제를 안고 있다.

더 읽어볼만한 페이지

프로그래밍 패러다임 - 지식 표현
지식 표현은 컴퓨터가 인간의 지식을 이해하고 활용하도록 정보를 구조화하는 기술이며, 표현력과 추론 효율성의 균형, 불확실성 처리 등을 핵심 과제로 다양한 기법과 의미 웹 기술을 활용한다.
프로그래밍 패러다임 - 의도적 프로그래밍
의도적 프로그래밍은 프로그래머의 의도를 명확히 포착하고 활용하여 소프트웨어 개발 생산성을 향상시키기 위한 프로그래밍 패러다임으로, 트리 기반 저장소를 사용해 코드 의미 구조를 보존하고, WYSIWYG 환경에서 도메인 전문가와 협업하며, 코드 상세 수준 조절 및 자동 문서화를 통해 가독성과 유지보수성을 높이는 데 중점을 둔다.

프로그램 합성

2. 역사

프로그램 합성의 역사는 1950년대 후반 앨런조 처치의 연구에서 비롯되며, 1960년대 인공지능(AI) 연구자들에 의해 "자동 프로그래머"라는 개념으로 발전하였다. 현대 고급 프로그래밍 언어의 개발 또한 일종의 프로그램 합성으로 이해할 수 있다.

프로그램 합성 방법은 다음과 같다.

방법	설명
형식 기법	합성하려는 프로그램의 성질을 논리식으로 나타내고, 그것을 자동으로 증명하는 과정에서 프로그램을 합성한다.
입출력 예시	프로그램에 대한 입력과 출력 예를 제시하여, 그러한 입출력을 생성하는 프로그램을 합성한다.
자연어 이해	자연어로 작성된 프로그램 사양을 이해하고, 프로그램을 합성한다.

2. 1. 초기 연구 (1950년대 ~ 1980년대)

앨런조 처치는 1957년 코넬 대학교에서 열린 기호 논리 하계 연구소에서 수학적 요구 사항으로부터 회로를 합성하는 문제를 정의했다.^[3] 이는 프로그램 합성에 대한 초기 설명 중 하나로 간주되며, 일부 연구자들은 프로그램 합성을 "처치의 문제"라고 부르기도 한다. 비록 이 연구는 프로그램이 아닌 회로만을 언급하고 있지만, 프로그램 합성의 초기 개념 중 하나로 여겨진다. 1960년대에는 인공 지능 연구자들이 "자동 프로그래머"에 대한 비슷한 아이디어를 탐구했다.

이후 다양한 연구 커뮤니티에서 프로그램 합성 문제를 고려했다. 주목할 만한 연구로는 1969년 율리우스 리하르트 뷔히와 로렌스 랜드웨버가 제시한 자동 이론적 접근 방식^[4]과 1980년대 조하르 마나와 리처드 월딩거의 연구 등이 있다.

2. 2. 21세기 이후의 발전

21세기 초, 형식 검증 커뮤니티에서 프로그램 합성에 대한 관심이 다시 증가했다. 아르만도 솔라-레사마는 프로그램 합성 문제를 부울 논리로 인코딩하고 부울 만족 문제(SAT) 솔버를 사용하여 프로그램을 자동으로 찾는 방법을 제시했다.^[5]

2. 2. 1. 구문 지향 합성 (Syntax-guided Synthesis, SyGuS)

펜실베이니아 대학교(UPenn), 캘리포니아 대학교 버클리(UC Berkeley), 매사추세츠 공과대학교(MIT)의 연구원들은 2013년에 프로그램 합성 문제에 대한 통일된 프레임워크인 구문 지향 합성(Syntax-guided Synthesis, SyGuS)을 제안했다.^[6] SyGuS 알고리즘의 입력은 유효한 해의 구문을 제한하는 문맥 자유 문법의 표현식과 논리적 명세로 구성된다.^[7] 예를 들어, 두 정수 중 최대값을 반환하는 함수 f^영어를 합성하기 위한 논리적 명세와 문법은 다음과 같을 수 있다.

논리적 명세:

:(''f''(''x'',''y'') ''x'' ∨ ''f''(''x'',''y'') ''y'') ∧ ''f''(''x'',''y'') ≥ x ∧ ''f''(''x'',''y'') ≥ y

문법:

:

::= x | y | 0 | 1 | + | ite(, , )

::= <=

여기서 "ite"는 "if-then-else"를 의미한다. 표현식 ite(x <= y, y, x)은 문법과 명세를 준수하므로 유효한 해가 된다.

2014년부터 2019년까지 매년 열린 구문 지향 합성 경진대회(SyGuS-Comp)는 경쟁 이벤트를 통해 프로그램 합성에 대한 다양한 알고리즘을 비교했다.^[8] 이 대회는 SMT-Lib 2를 기반으로 한 표준화된 입력 형식인 SyGuS-IF를 사용했다. 다음은 두 정수의 최대값을 합성하는 문제를 SyGuS-IF로 인코딩한 예시이다.

:(set-logic LIA)

:(synth-fun f ((x Int) (y Int)) Int

:((i Int) (c Int) (b Bool))

:((i Int (c x y (+ i i) (ite b i i)))

:(c Int (0 1))

:(b Bool ((<= i i)))))

:(declare-var x Int)

:(declare-var y Int)

:(constraint (>= (f x y) x))

:(constraint (>= (f x y) y))

:(constraint (or (= (f x y) x) (= (f x y) y)))

:(check-synth)

호환되는 솔버는 다음을 반환할 수 있다.

:((define-fun f ((x Int) (y Int)) Int (ite (<= x y) y x)))

2. 2. 2. 카운터 예제 기반 귀납적 합성 (Counter-example Guided Inductive Synthesis, CEGIS)

CEGIS는 건전한 프로그램 합성기를 구축하는 효과적인 접근 방식이다.^[9]^[10] CEGIS는 후보 프로그램을 생성하는 ''생성기''와 후보가 명세를 만족하는지 확인하는 ''검증기'', 이 두 가지 구성 요소의 상호 작용을 포함한다.

프로그램 합성의 목표는 입력 집합 I^영어, 가능한 프로그램 집합 P^영어, 명세 S^영어가 주어졌을 때, P^영어에서 모든 입력 i^영어 in I^영어에 대해 S^영어(p^영어, i^영어)가 참이 되도록 하는 프로그램 p^영어를 찾는 것이다. CEGIS는 생성기와 검증기에 대해 다음과 같이 매개변수화된다.

''생성기''는 입력 집합 T^영어를 받아 T^영어의 모든 입력에 대해 올바른 후보 프로그램 c^영어를 출력한다. 즉, 모든 입력 t^영어 in T^영어에 대해 S^영어(c^영어, t^영어)가 참이 되는 후보이다.
''검증기''는 후보 프로그램 c^영어를 받아 프로그램이 모든 입력에 대해 S^영어를 만족하면 ''true''를 반환하고, 그렇지 않으면 ''카운터 예제'' 즉, S^영어(c^영어, e^영어)가 실패하는 입력 e^영어 in I^영어를 반환한다.

CEGIS는 카운터 예제를 누적하면서 생성기와 검증기를 루프에서 실행한다.

'''알고리즘''' cegis '''는'''

'''입력''': 프로그램 생성기 ''generate'',

검증기 ''verify'',

명세 ''spec'',

'''출력''': ''spec''을 만족하는 프로그램 또는 실패

''inputs'' := 빈 집합

'''루프'''

''candidate'' := ''generate''(''spec'', ''inputs'')

'''if''' ''verify''(''spec'', ''candidate'') '''then'''

'''return''' ''candidate''

'''else''' ''verify''는 카운터 예제 ''e''를 생성한다

''e''를 ''inputs''에 추가

'''end if'''

CEGIS의 구현은 일반적으로 SMT 솔버를 검증기로 사용한다.

CEGIS는 카운터 예제 기반 추상화 개선(CEGAR)에서 영감을 받았다.^[11]

3. 마나와 월딩거의 프레임워크

1980년, 마나와 월딩거는 1차 논리 명세로부터 함수형 프로그램을 합성하는 프레임워크를 제시했다.^[12]^[13] 이 프레임워크는 표 형식으로 표현되며, 다음 네 가지 열로 구성된다.

참조를 위한 줄 번호 ("Nr")
공리 및 전제 조건을 포함하여 이미 설정된 공식 ("명제")
아직 증명해야 할 공식, 후제 조건을 포함 ("목표")^[14]
유효한 출력 값을 나타내는 항 ("프로그램")^[15]
현재 줄에 대한 정당성 ("출처")

처음에는 배경 지식, 전제 조건 및 후제 조건이 표에 입력된다. 그 후, 비절 형식 해소, 논리적 변환, 구조적 귀납법 등의 규칙을 사용하여 증명이 수행된다. 증명은 ''목표'' 열에서

\it true

가 파생되거나, ''명제'' 열에서

\it false

가 파생되면 완료된다. 이 접근 방식으로 얻은 프로그램은 ''구성에 의해 정확''하다.^[16] 즉, 시작된 명세 공식을 충족하는 것이 보장된다. 이 프레임워크에서는 조건, 재귀, 산술 및 기타 연산자로 구성된 최소한의 튜링 완전^[17] 순수 함수형 프로그래밍 언어만 지원된다.^[18]

이 프레임워크는 나눗셈, 나머지,^[19] 제곱근,^[20] 항 단일화,^[21] 관계형 데이터베이스 쿼리에 대한 답변,^[22] 여러 정렬 알고리즘^[23]^[24] 등 다양한 프로그램을 합성하는 데 사용되었다.

아래는 마나와 월딩거가 제시한 두 숫자

x

와

y

의 최댓값

M

을 계산하는 함수를 도출하는 예시이다.

최대 함수 예시 합성
번호	명제	목표	프로그램	출처
1	$A=A$			공리
2	$A \leq A$			공리
3	$A \leq B \lor B \leq A$			공리
10		$x \leq M \land y \leq M \land (x = M \lor y = M)$	M	명세
11		$(x \leq M \land y \leq M \land x = M) \lor (x \leq M \land y \leq M \land y = M)$	M	Distr(10)
12		$x \leq M \land y \leq M \land x = M$	M	Split(11)
13		$x \leq M \land y \leq M \land y = M$	M	Split(11)
14		$x \leq x \land y \leq x$	x	Resolve(12,1)
15		$y \leq x$	x	Resolve(14,2)
16		$\lnot (x \leq y)$	x	Resolve(15,3)
17		$x \leq y \land y \leq y$	y	Resolve(13,1)
18		$x \leq y$	y	Resolve(17,2)
19		$\textit{true}$	x? y : x	Resolve(18,16)

3. 1. 증명 규칙

비절 형식 해소는 절 정규형을 요구하지 않고, 임의의 구조와 연결사를 포함하는 공식으로 추론한다. 논리적 변환은 논리적으로 동등한 식으로 변환한다. 결합 명제의 분할 및 분리 목표의 분할도 증명 규칙에 해당한다.^[25] 구조적 귀납법은 재귀 함수 합성을 가능하게 한다. 주어진 사전 조건 및 사후 조건 "Given

x

such that

\textit{pre}(x)

, find

f(x) = y

such that

\textit{post}(x,y)

"와 도메인

x

의 적절한 사용자 지정 정렬 순서

\prec

에 대해, 명제 "

x' \prec x \land \textit{pre}(x') \implies \textit{post}(x',f(x'))

"를 추가하는 것은 항상 유효하다.^[26] 이 명제에 따른 분해는 프로그램 항에

f

에 대한 재귀 호출을 도입할 수 있다.

예를 들어, Manna, Waldinger (1980)는 두 개의 주어진 정수의 몫과 나머지를 계산하는 알고리즘을

0 \leq n' < n

으로 정의된 정렬 순서

(n',d') \prec (n,d)

를 사용하여 합성하였다.

Murray는 이러한 규칙이 1차 논리에 대해 완전함을 보였다.^[27]

1986년에 Manna와 Waldinger는 일반화된 E-분해 및 파라모듈레이션 규칙을 추가하여 등식도 처리했다.^[28] 나중에 이러한 규칙은 불완전한 것으로 판명되었지만 타당했다.^[29]

최대 함수 예시 합성
번호	명제	목표	프로그램	출처
1	$A=A$			공리
2	$A \leq A$			공리
3	$A \leq B \lor B \leq A$			공리
10		$x \leq M \land y \leq M \land (x = M \lor y = M)$	M	명세
11		$(x \leq M \land y \leq M \land x = M) \lor (x \leq M \land y \leq M \land y = M)$	M	Distr(10)
12		$x \leq M \land y \leq M \land x = M$	M	Split(11)
13		$x \leq M \land y \leq M \land y = M$	M	Split(11)
14		$x \leq x \land y \leq x$	x	Resolve(12,1)
15		$y \leq x$	x	Resolve(14,2)
16		$\lnot (x \leq y)$	x	Resolve(15,3)
17		$x \leq y \land y \leq y$	y	Resolve(13,1)
18		$x \leq y$	y	Resolve(17,2)
19		$\textit{true}$	x? y : x	Resolve(18,16)

두 숫자 $x$ 와 $y$ 의 최댓값 $M$ 을 계산하는 함수형 프로그램을 도출하는 예시에서, 1차 공식 $\forall X \forall Y \exists M: X \leq M \land Y \leq M \land (X=M \lor Y=M)$ 은 "최댓값은 주어진 숫자보다 크거나 같고, 주어진 숫자 중 하나이다"라는 요구 사항을 형식적으로 번역한 것이다. 이 공식은 증명되어야 한다. 스콜렘화를 역으로 사용하여, 10행의 명세가 얻어진다.^[30]

11행에서 분배 법칙에 대한 변환 규칙을 적용한 후, 증명 목표는 논리합이 되므로, 두 가지 경우(12행, 13행)로 나눌 수 있다.

12행과 1행을 해소하면 14행에서 프로그램 변수 $M$ 의 인스턴스화가 이루어진다. 비절 규칙을 12행과 1행에 적용하면 다음과 같다.

$p$ 는 $x=x$ 의 공통 인스턴스 $x=x$ 이며, $A=A$ 과 $x=M$ 을 통일하여 얻는다.
$F[p]$ 는 $true ∧ x=x$ 이며, 인스턴스화된 1행에서 얻는다.
$G[p]$ 는 $x ≤ x ∧ y ≤ x ∧ x = x$ 이며, 인스턴스화된 12행에서 얻는다.

결과적으로

\lnot (true ∧ false) ∧ (x ≤ x ∧ y ≤ x ∧ true)

가 되고, 이는

x \leq x \land y \leq x

로 단순화된다.

비슷한 방식으로, 14행은 15행을 생성하고, 그 다음 해소를 통해 16행을 생성한다. 13행도 유사하게 처리되어 18행이 생성된다.

마지막으로, 16행과 18행을 결합하여 58행의 해소 규칙을 사용한다. 18행은 "

x \leq y

의 경우, 출력

y

는 유효하다", 15행은 "

y \leq x

의 경우, 출력

x

는 유효하다"라고 해석할 수 있다. 15행에서 16행으로의 단계는 두 경우 16과 18이 상호 보완적임을 보여준다.^[31] 16행과 18행 모두 프로그램 용어가 있으므로, 조건식이 프로그램 열에 나타난다. 목표 공식

\textit{true}

이 도출되었으므로 증명은 완료되었고, "

\textit{true}

" 행의 프로그램 열에는 프로그램이 포함되어 있다.

4. 프로그램 합성의 과제

자동으로 생성된 프로그램은 종종 요소 정리가 불충분하다고 여겨진다. 불필요하다고 알려진 부분은 그대로 사용하는 것이 아니라, 요소 정리를 하는 것이 바람직하다. 다만 프로그래밍 언어의 제약에 따라 패턴의 반복을 사용할 수밖에 없는 경우도 있다.^[1]

요소 정리의 예시는 다음과 같다.^[1]

요소의 불충분한 정리	요소의 좋은 정리
x = a + a + a + a + a	x = a * 5 (여기서 별표는 곱셈을 나타낸다)

프로그램 합성에서는 위의 예시와 같은 반복을 자동으로 수행하는 경향이 있다. 그러나 더 나은 접근 방식은 곱셈을 사용하여 고수준의 추상화를 수행하는 것으로 보인다. 다른 예시로, 매개변수를 애플리케이션 코드 대신 파일이나 데이터베이스에 넣는 것도 있다.^[1]

5. 프로그램 합성 방법

프로그램 합성 방법은 1960년대에 인공지능(AI)을 활용하여 "자동 프로그래머"를 만들기 위해 수학과 프로그래밍 이론 간의 관계를 연구하면서 시작되었다. AI에 대한 관심이 감소하면서 수학적 접근 방식은 실패했다. 일부 연구자들은 여전히 형식적 접근 방식을 연구하고 있지만, 적용 범위를 제한한 순수 연역적 방법과 강력한 휴리스틱스를 결합한 방식이 성공을 거두었다.

프로그램 합성 방법으로는 형식 기법, 입출력 예시, 자연어 이해 등이 있다.

5. 1. 형식 기법

합성하려는 프로그램의 성질을 논리식으로 표현하고, 그것을 증명하는 과정에서 프로그램을 합성한다.^[1]

5. 2. 입출력 예시

프로그램에 대한 입력과 출력의 예를 몇 가지 제시하여, 그러한 입출력을 생성하는 프로그램을 합성한다.

5. 3. 자연어 이해

자연어로 작성된 프로그램 사양을 이해하고, 프로그램을 합성한다.^[1]

참조

_[1] 서적 Program Development in Computational Logic Springer
_[2] 문서
_[3] 논문 Applications of recursive arithmetic to the problem of circuit synthesis 1957
_[4] 논문 Solving Sequential Conditions by Finite-State Strategies http://docs.lib.purd[...] 1969-04
_[5] 문서
_[6] 학회자료 Syntax-guided Synthesis IEEE 2013
_[7] 문서
_[8] 웹사이트 SyGuS-Comp (Syntax-Guided Synthesis Competition) https://sygus-org.gi[...]
_[9] 문서
_[10] 문서
_[11] 문서
_[12] 논문 A Deductive Approach to Program Synthesis 1980-01
_[13] Technical Note A Deductive Approach to Program Synthesis https://apps.dtic.mi[...] 1978-12
_[14] 문서 The distinction "Assertions" / "Goals" is for convenience only; following the paradigm of [[proof by contradiction]], a Goal $F$ is equivalent to an assertion $\lnot F$ .
_[15] 문서 When $F$ and $s$ is the Goal formula and the Program term in a line, respectively, then in all cases where $F$ holds, $s$ is a valid output of the program to be synthesized. This [[invariant (computer science)|invariant]] is maintained by all proof rules. An Assertion formula usually is not associated with a Program term.
_[16] 문서 See Manna, Waldinger (1980), p.100 for correctness of the resolution rules.
_[17] 기술보고서 A Mechanical Proof of the Turing Completeness of Pure Lisp http://www.cs.utexas[...] 1983-05
_[18] 문서 Only the conditional operator ([[?:]]) is supported from the beginning. However, arbitrary new operators and relations can be added by providing their properties as axioms. In the toy example below, only the properties of $=$ and $\leq$ that are actually needed in the proof have been axiomatized, in line 1 to 3.
_[19] 문서 Manna, Waldinger (1980), p.108-111
_[20] 논문 The Origin of a Binary-Search Paradigm 1987-08
_[21] 논문 Formal Synthesis of a Unification Algorithm by the Deductive-Tableau Method
_[22] 서적 International Workshop on Logic Program Synthesis and Transformation (LOPSTR) Springer
_[23] 서적 Proceedings of the International Conference on Automated Deduction Springer
_[24] 논문 Deductive Synthesis of Sorting Programs 1989-06
_[25] 문서 Manna, Waldinger (1980), p.99
_[26] 문서 Manna, Waldinger (1980), p.104
_[27] 기술보고서 A Proof Procedure for Quantifier-Free Non-Clausal First Order Logic http://surface.syr.e[...] 1979-02
_[28] 논문 Special Relations in Automated Deduction 1986-01
_[29] 서적 Proc. CADE 11 Springer
_[30] 문서 While ordinary Skolemization preserves satisfiability, reverse Skolemization, i.e. replacing universally quantified variables by functions, preserves validity.
_[31] 문서 Axiom 3 was needed for that; in fact, if $\leq$ wasn't a [[total order]], no maximum could be computed for uncomparable inputs $x,y$ .

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com