![[Program Synthesis #14] Program Synthesis in the Wild: ์ค์ ์์คํ
๊ณผ ์์ฉ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps14.png)
[Program Synthesis #14] Program Synthesis in the Wild: ์ค์ ์์คํ ๊ณผ ์์ฉ
Program Synthesis ์๋ฆฌ์ฆ 14ํธ โ Superoptimization, Program Repair, LLM ๊ธฐ๋ฐ ์ฝ๋ ์์ฑ๊น์ง ์ค์ ํ๊ฒฝ์์์ synthesis ์์ฉ ์ดํดํ๊ธฐ
AI Security Researcher ยท Creative Developer
![[Program Synthesis #14] Program Synthesis in the Wild: ์ค์ ์์คํ
๊ณผ ์์ฉ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps14.png)
Program Synthesis ์๋ฆฌ์ฆ 14ํธ โ Superoptimization, Program Repair, LLM ๊ธฐ๋ฐ ์ฝ๋ ์์ฑ๊น์ง ์ค์ ํ๊ฒฝ์์์ synthesis ์์ฉ ์ดํดํ๊ธฐ
![[Program Synthesis #14] Program Synthesis in the Wild: ์ค์ ์์คํ
๊ณผ ์์ฉ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps14.png)
Program Synthesis ์๋ฆฌ์ฆ 14ํธ โ Superoptimization, Program Repair, LLM ๊ธฐ๋ฐ ์ฝ๋ ์์ฑ๊น์ง ์ค์ ํ๊ฒฝ์์์ synthesis ์์ฉ ์ดํดํ๊ธฐ
![[Program Synthesis #13] Deductive Synthesis: Specification์์ ํ๋ก๊ทธ๋จ์ ์ ๋ํ๊ธฐ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps13.png)
Program Synthesis ์๋ฆฌ์ฆ 13ํธ โ specification์ผ๋ก๋ถํฐ transformation rule์ ํตํด ํ๋ก๊ทธ๋จ์ ์ง์ ์ ๋ํ๋ Deductive Synthesis ์ดํดํ๊ธฐ
![[Program Synthesis #12] Type-Guided Synthesis: ํ์
์ผ๋ก ํ์ ๊ณต๊ฐ์ ์ค์ด๋ ๋ฐฉ๋ฒ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps12.png)
Program Synthesis ์๋ฆฌ์ฆ 12ํธ โ ํ์ ์ ๋ณด๋ฅผ ํ์ฉํด ํ๋ก๊ทธ๋จ ํ์ ๊ณต๊ฐ์ ๊ตฌ์กฐ์ ์ผ๋ก ์ ํํ๋ Type-Guided Synthesis ์ดํดํ๊ธฐ
![[Program Synthesis #11] ์ค์ ์์คํ
์ผ๋ก ๋ณด๋ Synthesis: FlashFill, Sketch, STOKE](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps11.png)
Program Synthesis ์๋ฆฌ์ฆ 11ํธ โ FlashFill, Sketch, STOKE๋ฅผ ํตํด ์ค์ ์์คํ ์ด ๋ค์ํ synthesis ๊ธฐ๋ฒ์ ์ด๋ป๊ฒ ๊ฒฐํฉํ๋์ง ์ดํดํ๊ธฐ
![[Program Synthesis #10] Constraint-Based Synthesis: ๋
ผ๋ฆฌ๋ก ํ๋ก๊ทธ๋จ์ ๋ง๋๋ ๋ฐฉ๋ฒ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps10.png)
Program Synthesis ์๋ฆฌ์ฆ 10ํธ โ SAT/SMT ๊ธฐ๋ฐ์ผ๋ก ํ๋ก๊ทธ๋จ์ ์ ์ฝ ๋ฌธ์ ๋ก ๋ณํํ์ฌ ํด๊ฒฐํ๋ Constraint-Based Synthesis ์ดํดํ๊ธฐ
![[Program Synthesis #9] Stochastic Search: ํ๋ฅ ๋ก ํ๋ก๊ทธ๋จ์ ์ฐพ๋ ๋ฐฉ๋ฒ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps09.png)
Program Synthesis ์๋ฆฌ์ฆ 9ํธ โ ํ๋ฅ ๊ธฐ๋ฐ ํ์๊ณผ local search๋ฅผ ํตํด ๋์ ํ๋ก๊ทธ๋จ ๊ณต๊ฐ์ ํจ์จ์ ์ผ๋ก ํ์ํ๋ ๋ฐฉ๋ฒ ์ดํดํ๊ธฐ
![[Program Synthesis #8] Bidirectional Search: Top-down๊ณผ Bottom-up์ ๊ฒฐํฉ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps08.png)
Program Synthesis ์๋ฆฌ์ฆ 8ํธ โ Top-down๊ณผ Bottom-up ํ์์ ๊ฒฐํฉํ์ฌ search space๋ฅผ ํจ๊ณผ์ ์ผ๋ก ์ค์ด๋ Bidirectional Search ์ดํดํ๊ธฐ
![[Program Synthesis #7] Representation์ ํ์ฅ: FTA์ E-graph๋ก ๋ณด๋ ํ๋ก๊ทธ๋จ ๊ณต๊ฐ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps07.png)
Program Synthesis ์๋ฆฌ์ฆ 7ํธ โ Version Space Algebra๋ฅผ ๋์ด, Finite Tree Automata์ E-graph๋ฅผ ํตํด ๋ค์ํ ํ๋ก๊ทธ๋จ ํํ ๋ฐฉ์ ๋น๊ตํ๊ธฐ
![[Program Synthesis #6] Representation-Based Synthesis: ํ์ ๊ณต๊ฐ์ ์์ถํ๋ ๋ฐฉ๋ฒ](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps06.png)
Program Synthesis ์๋ฆฌ์ฆ 6ํธ โ ํ๋ก๊ทธ๋จ์ ํ๋์ฉ ํ์ํ๋ ๋์ , ํ์ ๊ณต๊ฐ ์์ฒด๋ฅผ ์์ถํ๋ Representation-Based Synthesis์ ํต์ฌ ์์ด๋์ด ์ดํดํ๊ธฐ
![[Program Synthesis #5] Search Prioritization: ์ด๋ค ํ๋ก๊ทธ๋จ๋ถํฐ ๋ณผ ๊ฒ์ธ๊ฐ?](https://cdn.statically.io/img/nahyun27.github.io/assets/img/posts/program-synthesis/ps05.png)
Program Synthesis ์๋ฆฌ์ฆ 5ํธ โ Enumerative Synthesis์ ํ๊ณ๋ฅผ ๊ทน๋ณตํ๊ธฐ ์ํ Search Prioritization๊ณผ ํ๋ฅ ๊ธฐ๋ฐ ํ์ ์ ๋ต ์ดํดํ๊ธฐ