[AGI] Program Synthesis - 1

Program Synthesis란, 입력-출력 쌍이 주어졌을 때, 이를 만족하는 프로그램(또는 알고리즘)을 자동으로 생성하는 과정을 의미한다.

 

수업시간에 Program Synthesis와 관련해서 읽어보면 좋은 블로그를 교수님께서 소개해주셨다.

 

오늘은 그 블로그의 글들을 하나씩 정리해보고자 한다.

---

Programming

컴퓨터 이전, 사람들은 무엇을 하던 스스로 해야했고 이는 굉장히 피곤한 일이다.

프로그래밍은 사람이 컴퓨터에게 무언가를 해달라고 요청하는 것이다. 이메일을 만드는 것도, 블로그를 세팅하는 것도 프로그래밍이다. 프로그래밍은 항상 아래의 3가지를 고려해야 한다:

• 프로그래머 : 문제를 프로그램으로 만듬
• 프로그램 : 인터프리터가 이해하는 것
• 인터프리터 : 프로그램을 받아 일을 하는 것

프로그래밍을 하는 것은 컴퓨터가 어려운 작업을 도와주기 때문이다. 사람은 복잡한 일(4GHz의 데이터, 1000개의 이메일 정리)을 할 수 없다.

---

Program Synthesis

program synthesis는 프로그래밍을 쉽게 만들어 준다. 예를 들어 gcc는 어셈블리를 적는 것에서부터 자유롭게 해준다. "이런 이메일을 필터링해줘"를 쓰면 필터를 만들기 더 쉬워진다. Jekyll이 웹사이트를 만든 것은 블로그를 만들기 쉽게 해준 것도 그 예시로 볼 수 있다.

 

이처럼 program synthesis와 함께하면 프로그래머는 "program"보다 쉬운 "program++"를 사용할 수 있다. synthesizer는 중간에 프로그래밍을 도와주며 program++를 program으로 바꿔주는 역할을 한다.

이 synthesizer와 interpreter가 결합하면 더  나은 해석기인 interpreter++가 되어 program++(보통 spec이라고 부름)을 받아 작업을 수행할 수 있게 된다. 이런 구조는 반복적으로 확장이 가능하고 점점 더 사람이 프로그래밍하기 쉬운 방식으로 진화하게 된다.

---

A Brief History of Program Synthesis

맨 처음 synthesizers는 어셈블리 코드를 하이레벨로 바꿔주는 컴파일러였다. 연역적 합성(deductive synthesis)에서는 수학적 규칙을 이용하여 프로그램을 생성한다(ex. merge sort algorithm)

 

대부분의 현대적 synthesis는 inductive synthesis였다. 이는 해결책을 찾기위해 탐색을 진행하는 방식이다. neuro-symbolic program synthesis의 경우 neural-network를 이용하여 탐색을 진행하고 그럴듯한 프로그램을 만든다. 최근(2020+) 발전으로는 자연어를 추가하여 탐색을 더 효과적으로 유도하고 python 코드 생성 등에도 응용하고 있다.

 

최근, 프로그램들은 symbolic knowledge를 표현하는데 방식이 자유롭기 때문에 인지(cognition)를 모델링하는 데도 활용되어 왔다. 이는 일종의 프로그램 귀납(program induction) 과정으로도 볼 수 있다.

---

Where do we stand now?

program synthesis에는 거대한 진입 장벽이 존재한다. 그것은 language design, compiler, constraint-solving, semantic-parsing, neural-network 등을 전부 프로그래밍을 하는 것에 전문성이 필요하다는 것이다. 그러나 최근 foundational model이 발전하면서 더 이상 이런 전문성이 필요가 없어졌다. 

---

What is the end game?

우리는 Joshian의 접근법을 통해 program synthesis의 목표를 인간 개발자를 대체할 수 있는 시스템을 만드는 것이라고 생각한다. Program synthesis의 핵심은, program++/specification을 인간 친화적으로(humane) 만드는 것과, 동시에 그것과 실제 프로그램 사이의 변환을 감당 가능한 수준으로 유지하는 것 사이의 균형을 잡는 데 있다.

 

https://evanthebouncy.github.io/program-synthesis-minimal/what-is-synthesis/

what you will find here