Exact Programming by Examples
- Dana Drachsler-Cohen, Ph.D. Thesis Seminar
- Thursday, 16.3.2017, 11:00
- Taub 601
- Prof. E. Yahav
The vast majority of computer users do not know how to code. Programming by examples (PBE) has flourished in recent years to address exactly this problem. PBE enables users to write their own programs by describing their intent through examples, without writing or examining a single piece of code. An inherent problem of PBE is that examples under-specify the full intent of the user. Thus, current PBE algorithms have to synthesize a program after obtaining a partial description of the user intent, and cannot guarantee to meet the user intent. In this talk, I will describe three results on learning user intent from examples in a PBE setting. First, I will show an exact learning algorithm that learns user intent from examples, where intent is modelled as a conjunctive formula over arbitrary predicates. I will then show how to extend this algorithm to learn intents modelled as DNF formulas. Finally, I introduce the notion of abstract examples, which can reduce the number of examples required to learn. I show how to extend current PBE algorithms with the ability to communicate with the user through abstract examples and thereby guarantee that the final program meets the user intent. Throughout the talk, I will show applications of these results on various domains including technical analysis patterns, commutative specifications of concurrent data structures, and string and bit vector programs.