Program Synthesis

Program Synthesis is a search problem. It’s about generating a program that functions as intended without writing the actual content of the program. Instead, we generate the program by describing the output of the program through one of the following methods:

1. By Formal Specifications.
2. By Examples, mostly input / output.
3. By Implementation traces
4. Hybrid models using Machine Learning, (mainly neural nets), and other existing induction and reasoning methods for (guided a search + input / output)

• it’s certainly not related to neural networks, even though that’s what it looks like according to ML-twitter.
• it’s also not purely all about Programs as code, the word “Program” here is more among the lines of mathematical instructions or rather program in dynamic programming.

Get started now

Getting started

Introduction

Program Synthesis is not a new field, however it’s still at early days of research. Some researchers in the field compare the current state of Program Synthesis to the 1990s state of research for Neural Networks.

There have been great attempts at providing a survey, tutorial and introduction. However, most of them are out dated and don’t offer a wide review of the various domains that Program Synthesis.

This is an attempt to bring all those existing research efforts done related to the subject in one place.

Why Program Synthesis?

1. It’s new have a lot of room for research.

2. Lower computation required, no need to get a mortgage out like Deep Learning

3. Program synthesis is not function approximation, it’s rather the guarantee program we intended to write generated by the specifications given.

Comparison:

# programming by writing code:
def magicNumber(parameter):
    result = parameter + 2
    return result

magicNumber(2)

# programming by example code:
def magicNumber(parameter):
    return result
magicNumber(2)

import some_deep_learning_library

def magicNumber(parameter):
    train, test = some_deep_learning_library.split_data(parameter)
    result = some_deep_learning_library.model.fit(train, test)
    # 3 days and 20 hours later
    return result

magicNumber(parameter) = ~result

Thank you to the contributors of Program Synthesis Pub!

Code of Conduct

Program Synthesis Pub is committed to fostering a welcoming community.

View our Code of Conduct on our GitHub repository.