DeepCoder: Learning to Write Programs
Authors: Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow
ICLR 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirically, we show that our approach leads to an order of magnitude speedup over the strong non-augmented baselines and a Recurrent Neural Network approach, and that we are able to solve problems of difficulty comparable to the simplest problems on programming competition websites. In this section we report results from two categories of experiments. Our main experiments (Sect. 5.1) show that the LIPS framework can lead to significant performance gains in solving IPS by demonstrating such gains with Deep Coder. |
| Researcher Affiliation | Collaboration | Matej Balog Department of Engineering University of Cambridge Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow Microsoft Research Also affiliated with Max-Planck Institute for Intelligent Systems, T ubingen, Germany. |
| Pseudocode | No | Here we provide a description of the semantics of our DSL from Sect. 4.1, both in English and as a Python implementation. (This Python code describes the DSL semantics, not the pseudocode for the DeepCoder algorithm itself.) |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for their methodology is publicly available. |
| Open Datasets | No | To generate a dataset, we enumerate programs in the DSL, heuristically pruning away those with easily detectable issues such as a redundant variable whose value does not affect the program output, or, more generally, existence of a shorter equivalent program (equivalence can be overapproximated by identical behavior on randomly or carefully chosen inputs). (The paper describes generating its own dataset without providing public access information.) |
| Dataset Splits | No | We trained a neural network as described in Sect. 4.3 to predict used functions from input-output examples and constructed a test set of P = 500 programs, guaranteed to be semantically disjoint from all programs on which the neural network was trained. (No explicit mention of a separate validation set or specific split percentages for training, validation, and testing.) |
| Hardware Specification | No | For λ2, we observed that no solution for a given set of allowed functions was ever found after about 5 seconds (on the benchmark machines), but that λ2 continued to search. (This is the only mention of machines, and it's too vague to be a specific hardware specification.) |
| Software Dependencies | No | Sketch (Solar-Lezama, 2008) is a successful SMT-based program synthesis tool from the programming languages research community. λ2 (Feser et al., 2015) is a program synthesis tool from the programming languages community that combines enumerative search with deduction to prune the search space. (No specific version numbers are provided for these or any other software dependencies.) |
| Experiment Setup | Yes | For the encoder we use a simple feed-forward architecture. First, we represent the input and output types (singleton or array) by a one-hot-encoding, and we pad the inputs and outputs to a maximum length L with a special NULL value. Second, each integer in the inputs and in the output is mapped to a learned embedding vector of size E = 20. (...) Third, for each input-output example separately, we concatenate the embeddings of the input types, the inputs, the output type, and the output into a single (fixed-length) vector, and pass this vector through H = 3 hidden layers containing K = 256 sigmoid units each. (...) We use the negative cross entropy loss to train the neural network described in Sect. 4.3. |