Comparing approaches to the versatile idea of ‘programming by example’, which has relevance in various different fields and contexts, and designing interdisciplinary new techniques.
Haik Manukian and Judith Clymo
Adria Gascon, Turing Research Fellow, University of Edinburgh
Nathanaël Fijalkow, Turing Research Fellow, University of Warwick
Brookes Paige, Turing Research Fellow, University of Cambridge
Programming by example is a very natural and simple approach to programming: instead of writing a programme, give the computer a desired set of inputs and outputs, and hope that the programme will write itself out of these examples. In general, nothing prevents the computer from relying on training data, initiating an interactive dialogue with the user to resolve uncertainties, or even relying on the Internet, e.g. StackOverflow, to produce a solution that realises the user’s intent.
A typical application is for an excel sheet: you write 2,4,6, and click on “continue”. You hope that the computer will output 8,10,12… Another application is for robotics, where Programming by Example is often called Programming by demonstration. The goal there is to teach robots complicated behaviours, not by hard-coding them, which would be too costly and complicated, but by showing a few examples and asking the robot to imitate.
Automated program synthesis, namely having programs write correct programs, is a problem with a rich history in computer science that dates back to the origins of the field itself. In particular, the simple paradigm of “Programming by Example” has been independently developed within several sub-fields (at least formal verification, programming languages, and learning) under different names and with different approaches. This project is about understanding the trade-offs between these techniques, comparing them, and possibly devising one to beat them all.