Inductive program synthesis in Javascript
Any compiler or transpiler is doing some form of program synthesis. But “proper” program synthesis usually means generation of high level programs from scratch, given only high level problem descriptions.
This post is about one of the most simple and straightforward methods of automatic program synthesis: inductive synthesis based on input-output examples specification and brute-force enumerative search.
How to formulate this task for the automatic program generator? One option is to just describe it in natural language. But it would be quite hard to automatically parse and understand. A simpler way is to provide examples of inputs and expected outputs:
How to find a program that satisfies some input-output examples? There are several possible search strategies, but the simplest one is just with a brute force enumeration.
The idea is to generate all programs (within some size liimts and a limited language subset), and pick the first one that works correctly for all specified examples.
