Deepcoder
Pure python 3 implementation of DeepCoder (https://arxiv.org/pdf/1611.01989.pdf)
Usage
quickstart
- Install requirements
pip install -r requirements.txt
- Download dataset
wget https://storage.googleapis.com/deepcoder/dataset.tar.gz
tar xvf dataset.tar.gz # extracts to folder dataset
- Run solver
python -m deepcoder.scripts.solve-problems dataset/T=2_test.json --T 2 --mode dfs --gas 1000
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 100/100 [00:00<00:00, 147.26it/s]
summary:
solved 53/100 (53.0%)
nb_steps wall_ms
count 100.000000 100.000000
mean 628.420000 50.401287
std 412.020181 32.888645
min 1.000000 0.053883
25% 175.500000 15.448511
50% 830.000000 70.028543
75% 1000.000000 77.140987
max 1002.000000 102.509022
(gas is a limit on the number of nodes explored per problem)
- Train neural net
python -m deepcoder.scripts.train-nn --in dataset/T=2_train.json --out model.h5 --epochs 10
- Run solver with neural net
python -m deepcoder.scripts.solve-problems dataset/T=2_test.json --T 2 --mode dfs --gas 1000 --predictor model.h5
100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 100/100 [00:00<00:00, 175.35it/s]
summary:
solved 68/100 (68.0%)
nb_steps wall_ms
count 100.000000 100.000000
mean 475.280000 41.453178
std 409.670626 35.350695
min 1.000000 0.050783
25% 69.000000 6.203175
50% 389.000000 31.166434
75% 1000.000000 78.977406
max 1003.000000 102.050066
data generation
Dataset format:
[
{
"program": "LIST|LIST|COUNT,>0,0|ZIPWITH,+,1,0|ACCESS,2,3",
"examples": [
{
"inputs": [
[-46, -23, -78, 10],
[125, 105, -69]
],
"output": 82
},
{
"inputs": [
[90, 103, -57, 13, -45, 28, -30, 68, -113, 60, -71, 48, -117, 79, -42, -43, 37, -96],
[13, -52, 48, 6, -8, -55, 35, 75]
],
"output": null
},
...
],
"attribute": [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0]
},
...
]
(borrowed from HiroakiMikami and should be compatible). each dataset file is valid json and directly loadable like json.loads(open('dataset_file.json').read())
generate paper's datasets
To generate datasets used in the paper, use this script. Note it will take a long time (~1d). Also dataset.tar.gz was generated from this script.
./deepcoder/scripts/gen-datasets.sh
generate programs
python -m deepcoder.scripts.gen-programs \
--nb_inputs $NB_INPUTS --nb_train $NB_TRAIN --nb_test $NB_TEST \
--prog_len $PROG_LEN --train_out $TRAIN_PROG --test_out $TEST_PROG \
--enforce_disjoint
Enforcing semantic disjoint will increase the runtime substantially.
generate problems from programs
python deepcoder.scripts.gen-problems --infile $PROGRAM_FILE \
--outfile $PROBLEM_FILE
Because the constraint propagation is not perfect, some amount of resampling must be done so generating examples for each problem takes a long time.
tests
python -m unittest
Notes
- [-256,256] is the int range like in the paper.
nullis 513 - embedding vector encodes int range as [1,514]
- model construction uses keras dict input functionality heavily (see nn/encoding.py)
- caching intermediate results by prefix optimization is not implemented
- performance is much slower than what they reported. this explores about 10k nodes/s and is about 100x slower than theirs. solving all T=3 test problems takes about 10^6 steps -> 100s vs 1s they reported. authors had a c++ implementation with intermediate result caching which may account for speed difference
terminology
- problem: a set of input, output examples for a program
- gas: an optional limit on the max number of nodes explored in a search while solving a single problem (term inspired by ethereum)
constraint propagation
The constraint propagation code is hairy and I have not yet figured out all the cases. The paper doesn't provide much detail on this part.
In this implementation, each list constraint has a range of possible lengths and an integer range constraint for each possible length. This makes it possible to have a more accurate constraint for SCAN1L. For instance, for SCAN1L with *, the constraint is [-log 256/L, log 256/L] where L is the length of the list.
The paper does not specify how to handle ACCESS with a null input. It can arise in a program such as this LIST|FILTER,>0,0|ACCESS,0,2. What seems right is to find constraints such that ACCESS with a null argument never happens. I think it can be done by attaching a set of constraints like (>0,even) and (<0,odd) to each length slot in the list constraint but it's tricky.
For example, consider the (long) program
a <- List
b <- Filter(>0, a)
c <- Filter(even,b)
d <- Filter(<0, a)
e <- Filter(odd, d)
f <- Head(c)
g <- Head(e)
h <- Access(f,a)
i <- Access(g,a)
The Access statements would propagate (>0,even) and (<0,odd) to the list constraint for a and this would restrict the list length to >=2. However, the Head calls also impose an integer range constraint where each element must be in [0,L-1] where L is the candidate length of the list- this violates the (<0,odd) constraint on a so we should throw the program out.
As of now, example generation samples a few times and just throws out examples that yield out of bounds or null input errors.
program representation
Programs in the deepcoder dsl can be completely specified by a string format that is easily parsed.
| delimits each statement
, delimits a function call and its arguments
The general format is
INPUT_0_TYPE|...|INPUT_K_TYPE|FUNCTION_CALL_0|...|FUNCTION_CALL_N
Types of each statement are recoverable since we know the output type of each function.
As an example, consider the program
a <- [1,2,3,4]
b <- 5
c <- f(a)
d <- g(b)
e <- h(c, d)
This would be encoded as
LIST|INT|f,0|g,1|h,2,3