Program synthesis in Javascript: benchmarking on a list processing dataset

In my previous post, I described inductive program synthesis of simple JS programs. It was more of a toy example, demonstrating solutions for only a few pre-selected fine-tuned problems.

Next, I was interested to find out how program synthesis in JS would compare to other approaches, tested on a larger, reasonably challenging dataset.

A dataset of list processing tasks used in several recent papers (EC² [1], and DreamCoder [2]), that demonstrate state of the art results for several synthesis problems seems like a good fit.

Of course, my demo implements only the first step of algorithms described in [1,2]. They push it further by adding probabilistic modes, library learning, and deep learning on top. But still, getting reasonable performance on just the first step is good for learning more about program synthesis.

I used the dataset included with EC²/DreamCoder source, which contains 217 list processing tasks. I applied a program search algorithm described previously, with a DSL similar to described in EC² paper [1]. The main difference is that EC² is using a lisp-like language and functional programming, while I'm using imperative JS code, with static single assignment of variables.

Search is done in several passes, with an increasing allowed number of variables on each pass (which increases program complexity, and search time).

The results are: 80/217 problems solved (37%), with average ~40s search time. This is (accidentally) very close to results in [1], which reports 37% tasks solved with average 20s search time, when only enumeration part of the algorithm is used (see Table 3 in [1]).

Results can be reproduced in the demo below, press "generate all" to see generation progress. Many solutions are found within the first few minutes, but later search for harder problems can take almost 2 hours (up to 40s per each of 217 tasks).

References

1. Kevin Ellis, Lucas Morales, Mathias Sable-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. ´
   Library learning for neurally-guided bayesian program induction. In NeurIPS, 2018.
2. Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales,
   Luke Hewitt, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: Growing
   generalizable, interpretable knowledge with wake-sleep bayesian program learning, 2020.