SOURCE ARCHIVE
EXTRACTED CONTENT
87,152 charsarXiv:2211.00828v2 [cs.AI] 3 Apr 2023
SYNTHESIZING PROGRAMS WITH C ONTINUOUS OPTIMIZATION
Shantanu Mandal 1 Todd A. Anderson 2 Javier Turek 2 Justin Gottschlich 3 Abdullah Muzahid 1
ABSTRACT
Automatic software generation based on some specification is known as program synthesis. Most existing
approaches formulate program synthesis as a search problem with discrete parameters. In this paper, we present
a novel formulation of program synthesis as a continuous optimization problem and use a state-of-the-art
evolutionary approach, known as Covariance Matrix Adaptation Evolution Strategy to solve it. We then propose a
mapping scheme to convert the continuous formulation into actual programs. We compare our system, called
GENESYS, with several recent program synthesis techniques (in both discrete and continuous domains) and show
that GENESYS synthesizes more programs within a fixed time budget than those existing schemes. For example,
for programs of length 10, GENESYS synthesizes 28% more programs than those existing schemes within the
same time budget.
1 INTRODUCTION have shown promising early results for a simple problem Program synthesis, a subset of the field of machine program- set (e.g., programs similar to simple digital circuits such as ming (MP) (Gottschlich et al., 2018; Ratner et al., 2019), comparator, multiplexer, etc. in case of NPO), they fail to aims to automatically generate a software program from deliver any significant benefit for a complex problem set some specification and has the potential to revolutionize (see Section 5.4). Therefore, in this paper, we set out to how we develop programs. Such systems typically produce investigate how these promising results in the continuous a program as an output that satisfies some input specifica- domain can be extended to more complex problems. tions, classically in the form of input-output examples. At Suppose a program P , consisting of l tokens (instructions or a high level, most existing techniques formulate program functions), is denoted by P = 〈P1, ..., Pl〉, where Pi repre- synthesis as a search problem in the discrete domain. Typ- sents the i-th token for 1 ≤ i ≤ l. Pi can be any token from ically, the search problem is solved either through formal the set of all possible tokens, D. Given some input-output methods (Gulwani et al., 2012; Alur et al., 2015; Bodík & examples as a specification, most existing works find a pro- Jobstmann, 2013; Cheung et al., 2012; Heule et al., 2016; gram P that satisfies the specification by searching through Loncaric et al., 2018; Solar-Lezama et al., 2006) , machine different programs resulting from different combinations learning approaches (Balog et al., 2017; Zohar & Wolf, of various tokens. Since Pi is limited to a fixed number of 2018; Devlin et al., 2017; Reed & de Freitas, 2016; Man- distinct tokens from D, this formulation can be categorized dal et al., 2021; Spector, 2001; Chen et al., 2018c; Bunel as a discrete search problem. Various approaches differ in et al., 2018; Brameier, 2007; Langdon & Poli, 2010; Spector, the ways they prune the search space while still being able to 2001) or a combination of both (Feng et al., 2018; Nye et al., find P (Balog et al., 2017; Zohar & Wolf, 2018; Chen et al., 2019). Also, some prior art (Si et al., 2019; Schkufza et al., 2021; Hong et al., 2021). Recently, NPO proposed convert- 2013) has framed the problem in the continuous domain. ing P into a latent representation in the continuous domain Si et al. (2019) formulates discrete semantics to a continu- using the encoder of an autoencoder model (Liskowski et al., ous one by annotating program rules with different weights 2020). In this paper, we propose a novel formulation where and solve it using Markov Chain Monte Carlo technique. P can be expressed as P = 〈f1(·), f2(·), . . . , fM (·)〉. Here, Recently, Neural Program Optimization (NPO) (Liskowski each fi(·), for 1 ≤ i ≤ M , is a function that takes a number et al., 2020) formulate program synthesis in the continuous of continuous parameters as inputs and maps them into some domain using an autoencoder (Kramer, 1991) generated la- tokens in P . With this formulation, an error function that tent representations. Although these continuous approaches compares the output produced by P (for a specified input) 1Department of Computer Science and Engineering, Texas with the specified output, essentially becomes a function of A&M University, College Station 2Intel Labs 3Merly AI. Corre- continuous parameters. Therefore, the problem of program spondence to: Shantanu Mandal shanto@tamu.edu. synthesis amounts to minimizing the error function but as a continuous optimization problem.
Synthesizing Programs with Continuous Optimization
We propose to solve this continuous optimization prob- program synthesis framework that uses that mapping
lem using Covariance Matrix Adaptation Evolution Strat- scheme. We investigate different restart policies in the
egy (CMA-ES). Commonly used error functions for com- context of GENESYS to escape from local minima.
paring program outputs, such as edit or Manhattan dis-
tance (Mandal et al., 2021; Becker & Gottschlich, 2017; • We compare GENESYS with six prior program synthe-
Spector, 2001), are non-smooth and ill-conditioned, i.e., a sis techniques - DeepCoder (Balog et al., 2017), PC-
small change in the input can produce a large error. There- Coder (Zohar & Wolf, 2018), RobustFill (Devlin et al.,
fore, CMA-ES is perfectly suited to solve such cases. It 2017), NetSyn (Mandal et al., 2021), PushGP (Spector,
is a stochastic derivative-free algorithm for difficult (e.g., 2001), and NPO (Liskowski et al., 2020). These tech-
non-convex, ill-conditioned, multi-modal, rugged, noisy, niques cover a wide spectrum of program synthesis
etc.) optimization problems and considered as one of the approaches from discrete search and learning-based
most advanced optimization algorithms with many success- schemes to continuous optimization. Our results show
ful applications (Hansen, 2009b). We refer to the proposed that GENESYS synthesizes similar or more programs
program synthesis framework as GENESYS. within a fixed time budget than those existing schemes.
GENESYS uses a multivariate normal distribution for gener- Specially at higher length (e.g., 10-length), GENESYS,
ating potential solutions. During each generation, GENESYS on average, synthesizes 28.1% more programs than
takes a number of samples from the distribution. Using those existing schemes.
the proposed novel mapping scheme, GENESYS converts 2 BACKGROUND: CMA-ES
the samples of continuous parameters into actual programs.
These candidate programs are used to evaluate the error
function. If a candidate program has no error, the target CMA-ES was initially proposed in (Hansen & Ostermeier,
program is found. Otherwise, GENESYS starts the next gen- 1996; Hansen & Ostermeier, 2001) with a more recent
eration of evolution. For this generation, a new mean for the version described by (Hansen, 2005). The main goal of
distribution is calculated based on the error from the past CMA-ES is to minimize an objective function f . CMA-
generation. The covariance matrix, which captures depen- ES samples λ points in each generation k from a multi-
dencies among the continuous parameters, is adapted with variate normal distribution N (mk, σk2.Ck) and adapts the
the new mean. GENESYS evaluates the error function with parameters Ck ∈ Rd×d, mk ∈ Rd and σk ∈ R+ by eval-
new samples and the process continues. Since CMA-ES uating f . For a minimization task, λ points are ranked by
is a local policy, GENESYS can converge to a local min- f such that f (x1, k) ≤ f (x2, k) ≤ ... ≤ f (xλ, k). The ima. G distribution mean is set to the weighted average ENESYS restarts the algorithm with new samples to ∑μ mk+1 = escape from the minima. During restarts, GENESYS can i=1 ωixi,k . The weights do not depend on the evaluated restart CMA-ES while retaining some prior information re- function value, rather on the ranking of different λ points. μ ≤ λ/2 and the weights are chosen such that lated to the continuous parameters. GENESYS stops when Typically∑ the target program is found or some maximum time limit μw = 1/ μi=1 wi2 ≈ λ/ 4 (Hansen, 2005). has exceeded. Note that NPO also uses CMA-ES to solve Step size σk is updated using cumulative step-size adaption the optimization problem (similar to GENESYS). However, (CSA), also known as path length control (Hansen, 2005). NPO suffers from poor problem formulation as well as local The evolution path, pσ, is updated first using Equation 1. minima due to the use of autoencoder and absence of any Then, the step size σk+1 is updated using Equation 2. restart policy. In summary, we make the following contributions: pσ =(1 − cσ)p √ √ σ + 1 − (1 − cσ)2 μwCk−1/2 • We investigate how program synthesis can be formu- · mk+1 − mk (1) lated with continuous parameters that can lead to a σk better synthesis algorithm. Towards that end, we pro- σ cσ ( ‖pσ‖ −1). (2) pose a novel formulation of program synthesis as a k+1 =σk · e dσ E‖N (0,I)‖ continuous optimization problem where a program is expressed as a tuple of functions such that each func- Here, c−1 ≈ n/3 is the backward time horizon for the evo- tion maps continuous parameters into one or more lution pathσ p ∑ discrete tokens. σ and larger than one, μw = ( μi=1 wi2)−1 is the variance effective selection mass and 1 ≤ μw ≤ μ holds • We introduce a number of novel mapping schemes to true by the definition of wi, Ck−1/2 is the unique symmetric convert continuous parameters into actual programs square root of the inverse of Ck, dσ is the damping param- (and describe several other less performant mapping eter usually close to one and E is the expected values of schemes). We propose GENESYS, a CMA-ES-based ‖N (0, I)‖.
Synthesizing Programs with Continuous Optimization
Finally the covariance matrix is updated, where again the two components. First, we need a programming language
respective evolution path is updated first. that defines the domain of valid programs. Second, we need
a method to find P from the valid program domain.
√
pc =(1 − cc)pc + 1[0,α√n](‖pσ‖) 1 − (1 − cc)2 4
· √μw mk+1 − mk (3) GENESYS PROGRAM SYNTHESIS
σk FRAMEWORK
Ck+1 =(1 − c1 − cμ + cs)Ck + c1pcpTc
+ cμ ∑μ w xi:λ − mk ( xi:λ − mk )T (4) Here, we describe our choice of programming language,
ous optimization problem followed by various mapping
i=1 i σk σk proposed formulation of program synthesis as a continu-
and restart schemes and finally, the proposed framework,
The parameters used here are as follows: GENESYS.
• Cc−1 ≈ n/4 is the backward time horizon for the evolu- [int] Input:
ORT
• tion path pc and larger than one. MS AP (+1) [5, 0, -3, 1, 4]
α ≈ 1.5. FILTER (EVEN) Output:
• The indicator function 1 √ (‖p ‖) evaluates to REVERSE [6, 2, -2]
• c‖ps σ‖ ∈ [0, α√n]. [0,α n] σ Table 1: An example program of length 4 with an input and
= (1 − 1[0,α√n](‖pσ‖)2)c1cc(2 − cc) makes partly up corresponding output.
for the small variance loss in case the indicator is zero.
• c1 ≈ 2/n2 is the learning rate for the rank-one update
of the covariance matrix and cμ ≈ σw/n2 is the learn- 4.1 Domain Specific Language
ing rate for the rank-μ update of the covariance matrix.
The covariance matrix update tends to increase the likeli- As GENESYS’s programming language, we chose a domain
hood for pc and for (xi:λ − mk)/σk to be sampled from specific language (DSL) used in earlier work, such as Net-
N (0, Ck+1). Syn (Mandal et al., 2021) and DeepCoder (Balog et al.,
CMA-ES is attractive as a powerful black box optimization 2017). This choice allows us to constrain the program space
technique due to the fact that it adjusts all of its parameters by restricting the operations used by our solution. The only
automatically based on the objective function and covari- data types in the language are (i) integers and (ii) lists of inte-
ance matrix. Interested readers should consult (Hansen, gers. The DSL contains 41 functions, each taking one or two
2005) for more details about CMA-ES. arguments and returning one output. We will refer to DSL
functions as Tokens to avoid ambiguity with later terminol-
3 PROBLEM S ogy. We use D = {Di}|D| to indicate the set of all tokens
= 41. Many of the DSL tokens include
TATEMENT in the DSL, with |D| i=1
Let S = {(Ij , Oj )}sj=1 be a set of s input-output pairs, such operations for list manipulation. Likewise, some operations
that the output Oj is obtained by executing the program also require lambda functions. There is no explicit control
P t on the input Ij . Inherently, the set S of input-output flow (conditionals or looping) in the DSL. However, several
examples describes the behavior of the program P t. One of the operations are high-level functions and are imple-
would like to synthesize a program P that recovers the same mented using such control flow structures. A full description
functionality of P t. However, P t is unknown, and we are of the DSL can be found in NetSyn (Mandal et al., 2021).
provided with the set S as the specification. Based on this With these data types and operations, we define a program
assumption, we define equivalency between two programs P as an ordered sequence of DSL tokens i.e., P = 〈Pi〉li=1
as follows: where l is the length and Pi is the i-th token of the program.
Table 1 presents an example of a program of 4 tokens with an
Definition 1 (Program Equivalency). Programs P a and P b input and respective output. This program can be expressed
are equivalent under the set S = {(Ij , Oj )}sj=1 of input- as P = 〈M ap(+1), Sort, F ilter(Even), Reverse〉. output examples if and only if P a(Ij ) = P b(Ij ) = Oj , for 1 ≤ j ≤ s. We denote the equivalency by P a ≡S P b. 4.2 Program Synthesis as a Continuous Optimization Definition 1 suggests that to obtain a program equivalent to Problem - A Novel Formulation P t, we need to synthesize a program that satisfies S. There- We propose to model a program as an l-tuple, where fore, our goal is to find a program P that is equivalent to each element of the tuple is a function of continuous pa- the target program P t (which was used to generate S), i.e., rameters. Intuitively, each function takes one or more P ≡S P t. This task is known as Inductive Program Synthe- continuous parameters and maps them to 0 or more sis. Any solution to this problem requires the definition of DSL tokens in the program. A program P can be
Synthesizing Programs with Continuous Optimization
expressed as P = 〈f1(x11, ..., x1M ), ..., fN (xN1 , ..., xN )〉 program P . We choose l functions to represent the pro- where,0 fi(xi1, ..., xiM ) : RM → DCi for 1 ≤ i ≤MN , gram. Each function takes one continuous parameter. Thus,〈 〉 ≤ Ci ≤ l, and N, M > 0. Namely, each function fi P = f1(x11), f2(x21), . . . , fl(xl1) where fi(xi1) : R → D. maps M continuous random variables into Ci DSL tokens Each function fi must be able to map the continuous param- in the program. When Ci = 0, it indicates the special case eter to one of the DSL tokens. This is shown in Figure 2. when fi does not map its parameters to any DSL token. We conceptually divide the range of each variable into |D| In other words, fi becomes a NULL function. Figure 1(a) bins. That is why, we refer to this scheme as Bin Mapping. shows the mapping from the continuous variables to DSL The size of each bin can be equal (except the bin at each tokens. Since the length of the program P is l, we can infer end) or proportional to the probability of the corresponding ΣiCi = l. token being present in the program P . Prior work (Mandal et al., 2021; Balog et al., 2017) showed how to infer such Area for specific (xj)j=1 to M probability. When GENESYS samples from the continuous Point for specific Ci tokens Minimum error variables to create a candidate program, it takes each real sampled value and determines into which of the bins the value falls. The token used in that position in the candidate program is the one corresponding to the bin number into RM DCi Rs which the sampled value fell. This sampling process occurs fi maps M variables to Ci tokens RM*N for each of the l continuous parameters. Thus, the definition (a) Function Mapping (b) Error Function Mapping of fi and the corresponding selection of program token is Figure 1: Pictorial representation of how (a) each func- as follows: tion maps the continuous parameters to DSL tokens in the program and (b) the error function maps the continuous fi(xi1) = Dj if xi1 ∈ BinDj for 1 ≤ j ≤ |D| parameters. Pi = Dj,
We define an error over the given specification, S = where Bin {(Ij , Oj )} as E(P, S) = 〈E(P (Ij ), Oj )〉sj=1. Here, to token DjD, andʲ represents the range of values corresponding E(P (Ij ), Oj ) could be any commonly used distance func- Pi represents the i-th token of program P . tion in program synthesis such as edit distance, Manhattan This mapping scheme is robust and flexible and it requires distance, etc. (Jurafsky & Martin, 2009). With the formu- the least number of variables to represent a program. This lation of P as an l-tuple, E becomes a function mapping makes the optimization problem easier and helps GENESYS RM×N to Rs. Therefore, program synthesis becomes a to find more programs within a fixed time budget. continuous optimization problem where the goal is to find 4.4 Alternative Mapping Schemes values of M × N continuous random variables that mini- mize E (i.e., the minimum point in the s-dimensional space). To experienced CMA-ES users, bin mapping is perhaps the Figure 1(b) depicts this formulation. most intuitive mapping but initially it was unclear whether other obviously possible mapping schemes like Multi-Group Bin Mapping Mapping might be superior. Thus, we did explore a number of other possible mappings before determining that bin map- ping was the most effective. Each of these other mapping schemes use one or more continuous random variables to map to 0 or more DSL tokens of a program. Table 2 summa- rizes different mapping schemes and their characteristics. fi R D 4.4.1 Single Group Mapping maps 1 variable to 1 token 1 ≤ i ≤ l In this mapping, |D| functions map to l-length program, Figure 2: Representation of the bin mapping scheme. P . Each function represents a DSL token and takes one continuous parameter. Each function will map its parameter to at most one DSL token. 〈 〉 Thus, P = f 1 4.3 Mapping Scheme: Bin Mapping D 1 (x1), f2(x21), . . . , f|D|(x1|D|) where fi(xi1) : R → 0|1 . GENESYS samples each continuous parameter and Based on the problem formulation in the prior Section, then constructs the program by choosing the tokens corre- we propose a mapping scheme to construct an l-length sponding to the l largest sampled values. The token for the
Synthesizing Programs with Continuous Optimization
largest sampled value occurs first in the program. The token 4.4.3 Dynamic Multi-Group Mapping corresponding to the next largest value occurs second, and Dynamic multi-group mapping is a hybrid of the single and so on. This is shown in Table 2. A significant limitation of multi-group mappings in which there are k functions, each this approach is that each DSL token could occur at most taking |D| continuous parameters and choosing l/k DSL once in a program and thus is not applicable if the length of the program, l is larger than |D|. The formal definition of tokens for P . GENESYS randomly chooses k for each pro- fi and the corresponding selection of program token is as gram and treats k as a variable that CMA-ES can evolve, follows: thus allowing GENESYS to evolve to find the optimal k. If k is less than the program length then the continuous parameters corresponding to groups larger than k will be i=1 ) for 1 ≤ j ≤ l unused. However, since k itself may increase, those contin- fi(xi1) = Di if xi1 = T opj({xi1}|D| N one otherwise uous parameters must still be there and hence this scheme Pj = Di when fi(xi1) = Di, requires one more variable (i.e., k) than the Multi-Group Mapping.The formal definition is as follows:
Mapping Domain Range Characteristics { ( )}
Scheme fi(xi1, . . . , xi|D|) = Dj| xij = T op kl {xij}|jD=1|
Single Group R D0|1 fi maps 1 variable to 0 ( )
or 1 token for 1 ≤ i ≤ P(i−1) kl +t = Dj if xij = T opt {xij}|Dj=1|
Multi-Group R|D| D 1|D|.fi maps |D| variables to for 1 ≤ t ≤ k l.
token for 1 ≤ i ≤ l ×
|D|.
Dynamic R|D| Dl/k fi maps |D| variables to
Multi-Group l/k tokens for 1 ≤ i ≤ 4.4.4 Dynamic Bin Mapping
k. It is sometimes possible to find a program of a lower length
Table 2: Characterization summary of different alternative (than the length of the target program) that also satisfies the mapping schemes. given specification. This mapping scheme is the same as bin mapping but tries to take advantage of this property by including a function to choose the length, in other words the 4.4.2 Multi-Group Mapping number of other bin mapping functions to turn into program In this mapping, GENESYS uses l functions, each taking statements. The length function conceptually divides the |D| continuous parameters to express the program P . Each range of x0l+1 into l equal sized bins. When GENESYS sam- position in the program is thus represented by one function. ples this parameter, it determines which bin the parameter’s Each parameter of that function corresponds to a DSL token. value fall into. The length corresponding to that bin is cho- GENESYS samples the continuous parameters of the first sen as the program length. In practice, however, we found it function and selects the largest sampled parameter. The cor- to be more flexible to test all subsets of a generated program responding DSL token becomes the first token in P . Then, of maximum length for correctness rather than evolving the GENESYS samples the parameters of the second function length variable as this length variable is not always accurate. and the token corresponding to the largest sampled parame- The formal definition is as follows: ter becomes the second token in P . This process repeats for each of the l functions. This mapping scheme does allow fi(xi1) = Dj if xi1 ∈ BinDj and xl+11 ∈ Bink the same DSL token to be used multiple times in a program for 1 ≤ j ≤ |D| and 1 ≤ k ≤ l and i ≤ k but since it requires a large number of variables to represent Pi = Dj, a program, it may cause CMA-ES to take a long time to find a solution or may not find a solution. The formal definition of fi and the corresponding selection of program token is as follows: 4.5 Restart Policy GENESYS can stop its evolutionary process when the po- ( ) tential solutions are converging due to some local minima. fi(xi1, . . . , xi|D|) = Dj if xij = T op1 {xij}|D|j=1 This is checked by determining if a change in one or mul- Pi = Dj. tiple axes does not affect the distribution mean, or if the condition number of the covariance matrix is too high (i.e., ill-conditioned), or the evolutionary path’s step size is too
Synthesizing Programs with Continuous Optimization
small to reach the solution (Hansen, 2005). To escape from fore, GENESYS applies the error function E. The error such situation, we investigate several restart policies where function essentially applies inputs from the given specifi- GENESYS restarts with fresh initial parameters. We explore cation to a candidate program and checks if the produced all policies resulting from the combinations of 3 core restart output matches with the given output specification. If the policies: population-based (PB), mean-based (MB), and co- outputs match, the candidate program is returned as the variance matrix-based (CB). For the PB restart, GENESYS solution. Otherwise, GENESYS checks if convergence has doubles the size of the population from its previous size. reached. If not, GENESYS updates the mean, covariance For the MB restart policy, GENESYS resets the mean vector matrix and distribution path based on the error function and to randomly initialized values (using the uniform random starts a new generation. If, on the other hand, convergence distribution) after a restart instead of keeping its current is reached, GENESYS applies a restart policy and repeats value. For the CB restart policy, GENESYS re-initializes the whole process with new parameters. The synthesis pro- the covariance matrix to the identity matrix after a restart cess continues until a maximum time limit has passed or a instead of keeping its current values. Additional restart solution is found. policies can be constructed by any combination of these core restart policies. Some of these combinations have been 5 proposed in earlier work such as IPOP (Auger & Hansen, EVALUATION 2005) and BIPOP (Hansen, 2009a) where they re-initialize 5.1 Methodology mean vector, covariance matrix, and increase population We implemented GENESYS in Python, starting from a size simultaneously. base CMA-ES implementation from https://github. 4.6 Integration with Learning Approaches com/srom/cma-es. We developed an interpreter for our DSL in Section 4.1 to evaluate a DSL program. We ran- Usually, CMA-ES initializes the genes by sampling con- domly generated a total of 600 programs from length 5 tinuous variables from a multivariate normal distribution to 10, with 100 programs from each length. We checked and the bin mapping scheme uses a uniform size for bins those programs extensively to ensure that no program con- to map the continuous variables. We investigated whether tains any token (or sequence of tokens) which does not GENESYS would improve with the integration of a learning- affect the input data at all. For example, the token sequence based approach to bootstrap CMA-ES by means of better M ap(+1), M ap(−1) does not affect the input data at all. gene initialization or improve the core performance of CMA- We performed this checking to ensure a shorter length pro- ES by unequal bin widths based on some learned-attributes gram is unlikely to satisfy the specification of a particular such as token probability. To do so, we used a neural net- length program. We used these 600 programs as test pro- work model similar to that of NetSyn (Mandal et al., 2021). grams that GENESYS tries to synthesize. For each program, The model is a LST M -based network where latent hidden we used s = 5 input-output examples as its specification. To state is generated as, hi = LST M (hi−1, S) where S is evaluate synthesis ability, we used a synthesis time limit of the input-output example from the specification. Multiple 3 hours (10,800 seconds) for each program. If any program input-output examples create different hidden states. These can not be found within that time limit, we conclude that hidden states are aggregated together to get the token proba- the program was “not found”. bility by passing through a Sof tmax layer. Details of the To run all the experiments we used SLURM batch process- model and its training results are presented in Section B.1. ing system. All the experiments are run in a cluster with GENESYS can use the token probabilities from this model Intel(R) Xeon(R) CPU E5-2650 v2 @ 2.60GHz processor when initializing the genes at the beginning of CMA-ES. and 62GB of memory. For implementing various learning- Likewise, GENESYS can use bin widths that are propor- based schemes, we use Nvidia Tesla K80 GPU with 128 tional to the token probabilities from this model for the bin GB RAM to train the neural networks. For training any mapping scheme. learning-based schemes, we used 420,000 randomly gener- 4.7 Putting It All Together ated unique programs of length 5 to train the model. We checked the programs to remove duplicates. For each of GENESYS follows the high level workflow shown in Fig- the program we used 5 IO examples as the specification. ure 3. GENESYS starts by initializing a multivariate nor- For biasing bin width with token probability (Section 5.2.2), mal distribution and the population size. The continuous GENESYS uses a neural network similar to the one used in variables of the distribution are determined based on the Mandal et al. (2021) to predict the probability of various bin mapping scheme in Section 4.3. In each generation, DSL functions in a target program. GENESYS samples λ points from the multivariate distribu- tion and maps each sample to a program. Each of these candidate programs could potentially be the solution. There-
Synthesizing Programs with Continuous Optimization
GENESYS Program Synthesis Workflow
Calculate
covariance matrix and distribution mean Initialization Output of GENESYS specification s No (neural net, Generate output No No Has it Yes Apply a parameters, etc.) Output matches with Sample of candidate specification? Timeout? converged? restart candidate programs policy Start programs Input Yes Yes specification Solution found Terminate without solution
Figure 3: Overview of GENESYS.
5.2 Characterization of GENESYS versus a learned distribution. Thus, we conclude that learned
We first explore the characterization of restart policies, im- attributes like token probabilities are better utilized in bin
pact of applying learning on top of GENESYS followed by width selection as opposed to the gene initialization. This
other setups from different combinations of policies. Our is intuitive since the effect of gene initialization diminishes
main objective is to assess various settings of GENESYS. after a few initial iterations of GENESYS. Thus, the default
GENESYS setup uses Normal Ini + Biased as it had a 88%
5.2.1 Restart Policies synthesis rate compared to Learned Ini + Biased which was
slightly lower at 85%.
The synthesis percentage and time for different combina-
tions of the three core restart policies are presented in Fig- 5.2.3 Characterization of Mapping Schemes
ure 4a. Among all policies, synthesis percentage can be as Although bin mapping is the default scheme for GENESYS,
low as 49% for PB and as high as 88% for PB+CB case.
Without any restart, GENESYS can synthesize 58% of pro- we investigated how other mapping schemes worked. Fig-
grams. Among the individual policies, MB and CB both syn- ure 4d shows the percentage of all programs synthesized
thesize 1.5× more programs than that of PB. On the other and synthesis time for different mapping schemes. For pro-
hand, when we combine PB+CB, GENESYS synthesizes grams of length 10, bin mapping can synthesize up to 88%
88% programs followed by PB+MB+CB with a synthesis programs whereas synthesis percentage is 78%, 19%, 42%
percentage of 86%. Note that PB+MB+CB is essentially and 35% for dynamic bin, single group, multi-group and
the BIPOP policy (Hansen, 2009a). The results suggest dynamic multi-group mapping respectively. In terms of syn-
that it is better to re-initialize the covariance matrix during thesis time, the bin mapping scheme is at least 1.5× faster
restarts. This is because the covariance matrix may become than other mapping schemes. Thus, bin mapping scheme
ill-conditioned and lead to the same local minima. Dou- works the best both in terms of synthesis percentage and
bling the population is generally beneficial because more time. This is because bin mapping has the lowest number of
potential solutions can be checked. Two best performing continuous parameters (i.e., O(l)). Other mapping schemes
policies (i.e., PB+CB and PB+MB+CB) differ by whether require more continuous parameters making the optimiza-
to re-initialize the mean vector or not. PB+CB being the tion domain much larger to find the solution within the given
best policy indicates that keeping the mean vector as it is time limit.
during a restart provides some advantage by accumulating
information about the continuous parameters.
Setup Name Mapping DSL Type Restart Bin Type Check
5.2.2 Impact of Learning Multi-Group Multi-group Regular Yes Biased Full
Grouped DSL Bin Grouped Yes Biased Full
In this section we explore the effects of biasing gene ini- No Restart Bin Regular No Biased Full
tialization and bin widths in the bin mapping scheme as de- Uniform Bin Bin Regular Yes Uniform Full
scribed in Section 4.6. Figure 4b shows results for different Sub Check Bin Regular Yes Biased Sub
Best Setup Bin Regular Yes Biased Full
combinations of gene initialization and bin width selection.
Note from this figure that using biased bin widths is always Table 3: Different configurations for GENESYS framework.
superior in terms of synthesis percentage compared to uni- For restart, we used PB+CB policy.
form bin widths. Also note that there is little difference
between initial gene creation using a normal distribution
Synthesizing Programs with Continuous Optimization
H 100 2100& 80 10°
80
H 2 H we
22 a0 10g iv £
20 100
£2 10° a =
@ 0 01
® ©, 01 sr”\ ae"ᴿ go
(a) Restart policy (b) Impact of learning on GENESYS.
100
g 2
8 8 w_
5 ws ww}
“a0 8 H
100g 40 100g
H H =
Ew i 10° in 10°
© eo eck co?ᵒᵗ ge
Sheet ofO° (ou ue
pry
(c) Different GENESYS setup (d) Mapping scheme
Figure 4: Synthesis percentage and time as functions of (a) restart policies (b) setup choice of learned token probability (c)
other GENESYS setups and (d) mapping schemes. Program synthesis percentages are shown (cross mark with green color)
at the left y-axis and their synthesis times in the right y-axis as box plots for each of the setups. Each boxplot represents
minimum, 25% and 75% quantiles, median and maximum synthesis times. Circles indicate outliers.
5.3 Other Setups convergence. Multi-group setup synthesizes the least pro-
We experimented with additional configurations of grams because a higher number of continuous parameters
GENESYS. Table 3 presents each configuration with a name. lead to higher synthesis time. Therefore, many programs are
The configurations are based on 5 criteria. Mapping and not found within the given time limit. Finally, compared to
Restart indicate the mapping schemes and restart policies. the uniform bin, biased bins increase synthesis percentage
DSL Type indicates whether we used our regular or grouped by 18.9% in the best setup.
DSL. In grouped DSL, similar tokens are grouped into a 5.4 Comparison of Synthesis Ability
single super token in an effort to reduce the optimization do-
main. Bin Type indicates whether the bin size is uniform or 5.4.1 Synthesis Ability of Different Schemes
biased based on token probability. Check indicates whether GENESYS checks for specification after a full-length pro- We compared GENESYS(the best setup) with other program gram or after each token in the program (i.e., sub-program). synthesis techniques mentioned in Table 4 . Figure 5 shows Checking after each token allows GENESYS to find an equiv- ~~ comparative results of these methods for different program alent lower-length program at the expense of more checking ~~ lengths. Synthesis time is measured in seconds as a func- operations. Figure 4c compares synthesis percentages and tion of the percentage of programs synthesized within the times for the different configurations. The best setup synthe- ~~ corresponding time. Lines terminate when an approach fails sizes 88% programs combining bin mapping with regular to synthesize additional programs. Among the approaches, DSL, a restart policy (PB+CB), biased bins, and full pro- some are learning-based while others are not. Keep in mind gram check. Token by token checking and grouped DSL that GENESYS uses a learning model to determine the bin did not provide as much benefit (either in terms of time or ~~ width. For all approaches, except Shgo and NPO, 90% synthesis percentage) as expected due to additional check- of programs can be synthesized within same amount of ing overhead or additional selection requirements for each time for program length 5. However, as program length in- super token (i.e., selecting the exact token within a super ~~ creases, GENESYS synthesizes more programs in less time token). No restart policy performs worse due to premature ~~ compared to other approaches. For example, GENESYS
Synthesizing Programs with Continuous Optimization
(a) Program length = 5 (b) Program length = 7 (c) Program length = 10
(d) Program length = 5 (e) Program length = 7 (f) Program length = 10 Shgo NPO DeepCoder PCCoder RobustFill PushGP NetSyn Genesys
Figure 5: GENESYS’s synthesis ability for different program lengths with respect to Shgo, NPO, DeepCoder, PCCoder, RobustFill, PushGP, and NetSyn.
synthesizes 50% of length-10 programs in less than half programs quickly. That is why, GENESYS synthesizes more of the time for other approaches. Compared to the recent programs within fixed time. techniques (DeepCoder, PCCoder, RobustFill, PushGP, and NetSyn), GENESYS synthesizes at least 1.1% and up to Scheme Main Idea 31.3% more programs across all lengths. For higher length Shgo Simplicial global optimization (e.g., 10-length), GENESYS, on average, synthesizes 28.1% NPO Autoencoder embedding + CMA-ES more programs than those existing schemes. As expected, DeepCoder Function probability (DNN) + DFS search Shgo performs the worst since it is not used in the liter- PCCoder Encoder decoder (DNN) + Beam search ature for program synthesis but is included here to show RobustFill Encoder decoder (LSTM) + Beam search CMA-ES performs better than other black-box optimiza- PushGP Genetic algorithm (GA) NetSyn Fitness function (LSTM) + GA tion techniques. NPO is the closest work to GENESYS. GENESYS Function formulation + CMA-ES + Token However, NPO has a consistently lower synthesis rate than probability (LSTM) GENESYS for all lengths. This is due to the fact that NPO uses autoencoder generated latent variables to represent a Table 4: Different schemes compared. program in the continuous domain. Even a small change 5.4.2 Stability Comparison in one of the latent variables can map the representation to a wildly different program leading to a large error. This The use of autoencoder in NPO makes the problem formu- characteristic makes the continuous optimization a much lation unstable. If an optimization problem is unstable, it harder problem. On the other hand, our mapping scheme becomes less tolerant to random noises leading to a sharp de- is resilient to small changes in continuous variables mak- cline in solutions. In order to compare stability of GENESYS ing the overall optimization problem easier than that of with NPO, we introduce random noises in the continuous NPO. That is why, even uniform bin mapping (a scheme variables. For example, we insert some random noises to that does not rely on any learning model at all) can syn- each of the CMA-ES variable. Similarly, we introduce ran- thesize 73% of all programs, thereby outperforming NPO, dom noises in the latent representations of NPO. Table 5 which synthesizes 58% of all programs. Figure 5 (d) to (f) shows synthesis percentage between GENESYS and NPO shows programs explored before finding the target program. with added noise. It shows that synthesis rate for GENESYS Although GENESYS searches through more programs than drops 10% whereas, it drops 20% for NPO on average across NetSyn, PCCoder, PushGP, and RobustFill, it searches those different length programs. This is expected as the decoder takes the latent representation from CMA-ES with noise
Synthesizing Programs with Continuous Optimization
Noise Baseline 5 Length7 10 ples to predict the probabilities of the functions that are most
likely to be used in a program. Raychev et al. (Raychev
Without GENESYS 89% 87% 87% et al., 2014) take a different approach and use an n-gram
NPO 57% 60% 59% model to predict the functions that are most likely to com-
With GENESYS 79% 79% 78% plete a partially constructed program. Robustfill (Devlin
NPO 51% 45% 42% et al., 2017) encodes input-output examples using a series
Table 5: Stability comparison between GENESYS and NPO of recurrent neural networks (RNN), and generates the the
in terms of synthesis percentage. program using another RNN one token at a time. Bunel et
al. (Bunel et al., 2018) explore a unique approach that com-
added and produces significantly different programs. This bines reinforcement learning (RL) with a supervised model
makes it unstable. On the other hand, adding a little noise to find semantically correct programs. These are only a few
does not make GENESYS wildly jump to the other bins. of the works in the MP space using neural networks (Mandal
Rather it is kept in the same bin and GENESYS becomes et al., 2021; Ye et al., 2020; Reed & de Freitas, 2016; Cai
noise tolerant. et al., 2017; Chen et al., 2018a).
Significant research has been done in the field of genetic
6 RELATED WORK programming (Spector, 2001; Brameier, 2007; Langdon &
Poli, 2010) too, where the goal is to find a solution in the
Machine programming as known as program synthesis has form of a complete or partial program for a given speci-
been widely studied with various applications. Formal pro- fication. Prior work in this field has tended to focus on gram synthesis uses formal and rule based methods to gen- either the representation of programs or operators during erate programs(Manna & Waldinger, 1975; Wang et al., the evolution process. Real et al. (Real et al., 2019) re- 2018). Formal program synthesis usually guarantees some cently demonstrated that genetic algorithms can generate program properties by evaluating a generated program’s accurate image classifiers. Their approach produced a state- semantics against a corresponding specification (Gulwani of-the-art classifier for CIFAR-10 (Krizhevsky, 2009) and et al., 2012; Alur et al., 2015). In (Feng et al., 2018), authors ImageNet (Deng et al., 2009) datasets. Moreover, genetic use a SMT based solver to find different constraints in the algorithms have been exploited to successfully automate the program and learn useful lemma that helps to prune away neural architecture optimization process (Salimans et al., large parts of the search space to synthesize programs faster. 2017; Such et al., 2017; Liu et al., 2017; Labs; Real et al., However, these techniques can often be limited by exponen- 2020). tially increasing computational overhead that grows with the program’s instruction size (Heule et al., 2016; Bodík & However, all these works formulate program synthesis as a Jobstmann, 2013). search problem of discrete parameters. On the other hand, GENESYS tries to formulate program synthesis as a con- Another way to formal methods for MP is to use machine tinuous optimization problem and uses a well established learning (ML). Machine learning differs from traditional for- derivative free method, CMA-ES, to solve it. Previously, mal program synthesis in that it generally does not provide CMA-ES was used in machine learning (Mueller et al., correctness guarantees. Instead, ML-driven MP approaches 1999), aerospace engineering (Lutz et al., 1997), mechani- are usually only probabilistically correct, i.e., their results cal engineering (Sonoda et al., 2004), health (Winter et al., are derived from sample data relying on statistical signifi- 2002) and various other engineering fields (Hansen, 2009b) cance (Murphy, 2012). Such ML approaches tend to explore but not in the field of synthesizing complex programs. software program generation using an objective function. Objective functions are used to guide an ML system’s ex- 7 ploration of a problem space to find a solution. Other deep CONCLUSION learning based program synthesizer (Bunel et al., 2018; In this paper, we presented a novel formulation of program Parisotto et al., 2016; Chen et al., 2020) also tried different synthesis as a continuous optimization problem. Essentially, approaches such as reinforcement learning to solve the prob- it expresses a program with a tuple of functions, each taking lem. Most of these works focus on synthesizing programs in a number of continuous parameters and mapping them to domain specific languages, such as FlashFill (Devlin et al., zero or more DSL tokens. We showed that a state-of-the- 2017; Kalyan et al., 2018) for string transformation prob- art evolutionary approach, CMA-ES, can be used to solve lem, simulated robot navigation, such as Karel (Shin et al., the optimization problem very efficiently. Our proposed 2018; Chen et al., 2018b) or LIST manipulation (Balog framework, GENESYS, consists of a mapping scheme to et al., 2017; Mandal et al., 2021) work. convert the continuous formulation into actual programs Among the ML-based MP, in Deepcoder(Balog et al., 2017), and restart policies for the evolutionary strategy to escape the authors train a neural network with input-output exam- local minima. We compared the proposed framework with
Synthesizing Programs with Continuous Optimization
several recent program synthesis techniques and showed that Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-
GENESYS synthesizes, on average, 28.1% more programs Fei, L. ImageNet: A Large-Scale Hierarchical Image
within a fixed time budget at higher lengths. We envision Database. In CVPR09, 2009.
GENESYS to be a stepping stone towards a completely new
domain of research in program synthesis. Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed,
A., and Kohli, P. RobustFill: Neural Program Learning
REFERENCES under Noisy I/O. In ICML, 2017.
Alur, R., Bodík, R., Dallal, E., Fisman, D., Garg, P., Juniwal, Endres, S. C., Sandrock, C., and Focke, W. W. A simplicial
G., Kress-Gazit, H., Madhusudan, P., Martin, M. M. K., homology algorithm for lipschitz optimisation. Journal
Raghothaman, M., Saha, S., Seshia, S. A., Singh, R., of Global Optimization, 2018.
Solar-Lezama, A., Torlak, E., and Udupa, A. Syntax- Feng, Y., Martins, R., Bastani, O., and Dillig, I. Program Guided Synthesis. In DSSE. 2015. Synthesis Using Conflict-driven Learning. In PLDI, 2018. Auger, A. and Hansen, N. A restart cma evolution strategy Gottschlich, J., Solar-Lezama, A., Tatbul, N., Carbin, M., with increasing population size. IEEE CEC, 2005. Rinard, M., Barzilay, R., Amarasinghe, S., Tenenbaum, Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., J. B., and Mattson, T. The Three Pillars of Machine and Tarlow, D. DeepCoder: Learning to Write Programs. Programming. In MLPL, 2018. In ICLR, 2017. Gulwani, S., Harris, W. R., and Singh, R. Spreadsheet Data Becker, K. and Gottschlich, J. AI Programmer: Au- Manipulation Using Examples. Commun. ACM, 2012. tonomously Creating Software Programs Using Genetic Hansen, N. The CMA Evolution Strategy: A Tutorial. ArXiv Algorithms. CoRR, 2017. e-prints, arXiv:1604.00772, 2016, pp.1-39, 2005. URL Bodík, R. and Jobstmann, B. Algorithmic Program Synthe- https://hal.inria.fr/hal-01297037. sis: Introduction. IJSTTT, 2013. Hansen, N. Benchmarking a bi-population cma-es on the Brameier, M. On Linear Genetic Programming. PhD thesis, bbob-2009 function testbed. GECCO ’09, 2009a. Dortmund, Germany, 2007. Hansen, N. CMA-ES Applications. http: Bunel, R., Hausknecht, M. J., Devlin, J., Singh, R., and //www.cmap.polytechnique.fr/~nikolaus. Kohli, P. Leveraging Grammar and Reinforcement Learn- hansen/cmaapplications.pdf, 2009b. ing for Neural Program Synthesis. In ICLR, 2018. Hansen, N. and Ostermeier, A. Adapting arbitrary normal Cai, J., Shin, R., and Song, D. Making Neural Programming mutation distributions in evolution strategies: the covari- Architectures Generalize via Recursion. In ICLR, 2017. ance matrix adaptation. In ICEC, 1996. Chen, X., Liu, C., and Song, D. Towards synthesizing Hansen, N. and Ostermeier, A. Completely derandomized complex programs from input-output examples. In ICLR, self-adaptation in evolution strategies. 2001. 2018a. Heule, S., Schkufza, E., Sharma, R., and Aiken, A. Stratified Chen, X., Liu, C., and Song, D. Execution-guided neural Synthesis: Automatically Learning the x86-64 Instruction program synthesis. In ICLR, 2018b. Set. 2016. Chen, X., Liu, C., and Song, D. Towards Synthesizing Hong, J., Dohan, D., Singh, R., Sutton, C., and Zaheer, M. Complex Programs From Input-Output Examples. In Latent programmer: Discrete latent codes for program ICLR, 2018c. synthesis. In ICML, 2021. Chen, X., Song, D., and Tian, Y. Latent execution for neu- Jurafsky, D. and Martin, J. H. Speech and language pro- ral program synthesis beyond domain-specific languages. cessing : an introduction to natural language processing, arXiv preprint arXiv:2107.00101, 2021. computational linguistics, and speech recognition. 2009. Chen, Y., Wang, C., Bastani, O., Dillig, I., and Feng, Y. Kalyan, A., Mohta, A., Polozov, O., Batra, D., Jain, P., and Program synthesis using deduction-guided reinforcement Gulwani, S. Neural-guided deductive search for real-time learning. In ICCAV, 2020. program synthesis from examples. arXiv, 2018. Cheung, A., Solar-Lezama, A., and Madden, S. Using Kramer, M. A. Nonlinear principal component analysis Program Synthesis for Social Recommendations. ArXiv, using autoassociative neural networks. AIChE journal, abs/1208.2925, 2012. 37(2):233–243, 1991.
Synthesizing Programs with Continuous Optimization
Krizhevsky, A. Learning Multiple Layers of Features from P. B., Gibson, G. A., Gonzalez, J. E., Gottschlich, J., Han,
Tiny Images. Technical report, 2009. S., Hazelwood, K. M., Huang, F., Jaggi, M., Jamieson,
Labs, S. Evolv Delivers Autonomous Optimization Across K. G., Jordan, M. I., Joshi, G., Khalaf, R., Knight, J.,
Web & Mobile. https://www.evolv.ai/. Konecný, J., Kraska, T., Kumar, A., Kyrillidis, A., Li, J.,
Madden, S., McMahan, H. B., Meijer, E., Mitliagkas, I.,
Langdon, W. B. and Poli, R. Foundations of Genetic Pro- Monga, R., Murray, D. G., Papailiopoulos, D. S., Pekhi-
gramming. Springer Publishing Company, Incorporated, menko, G., Rekatsinas, T., Rostamizadeh, A., Ré, C., Sa,
1st edition, 2010. ISBN 3642076327. C. D., Sedghi, H., Sen, S., Smith, V., Smola, A., Song,
D., Sparks, E. R., Stoica, I., Sze, V., Udell, M., Van-
Li, C. and Wang, B. Principal Components Analysis, 2014. schoren, J., Venkataraman, S., Vinayak, R., Weimer, M.,
Liskowski, P., Krawiec, K., Toklu, N. E., and Swan, J. Pro- Wilson, A. G., Xing, E. P., Zaharia, M., Zhang, C., and gram synthesis as latent continuous optimization: Evolu- Talwalkar, A. SysML: The New Frontier of Machine tionary search in neural embeddings. GECCO, 2020. Learning Systems. CoRR, abs/1904.03257, 2019. URL http://arxiv.org/abs/1904.03257. Liu, H., Simonyan, K., Vinyals, O., Fernando, C., and Raychev, V., Vechev, M., and Yahav, E. Code Completion Kavukcuoglu, K. Hierarchical Representations for Effi- with Statistical Language Models. PLDI ’14, 2014. cient Architecture Search. CoRR, 2017. Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regular- Loncaric, C., Ernst, M. D., and Torlak, E. Generalized Data ized Evolution for Image Classifier Architecture Search. Structure Synthesis. In ICSE, 2018. In AAAI, 2019. Lutz, T., Wagner, S., Lutz, T., and Wagner, S. Drag reduc- Real, E., Liang, C., So, D. R., and Le, Q. V. Automl- tion and shape optimization of airship bodies. In 12th zero: Evolving machine learning algorithms from scratch, Lighter-Than-Air Systems Technology Conference, 1997. 2020. Mandal, S., Anderson, T., Turek, J., Gottschlich, J., Reed, S. E. and de Freitas, N. Neural Programmer- Zhou, S., and Muzahid, A. Learning fitness functions Interpreters. In ICLR, 2016. for machine programming. In Smola, A., Dimakis, Salimans, T., Ho, J., Chen, X., Sidor, S., and Sutskever, I. A., and Stoica, I. (eds.), Proceedings of Machine Evolution Strategies as a Scalable Alternative to Rein- Learning and Systems, volume 3, pp. 139–155, forcement Learning. CoRR, 2017. 2021. URL https://proceedings.mlsys. org/paper_files/paper/2021/file/ Schkufza, E., Sharma, R., and Aiken, A. Stochastic su- 32bb90e8976aab5298d5da10fe66f21d-Paper. peroptimization. In Proceedings of the Eighteenth Inter- pdf. national Conference on Architectural Support for Pro- Manna, Z. and Waldinger, R. Knowledge and Reasoning gramming Languages and Operating Systems, ASPLOS in Program Synthesis. Artificial Intelligence, 6(2):175 – ’13, pp. 305–316, New York, NY, USA, 2013. Associa- 208, 1975. ISSN 0004-3702. tion for Computing Machinery. ISBN 9781450318709. doi: 10.1145/2451116.2451150. URL https://doi. Mueller, S. D., Milano, M., and Koumoutsakos, P. Appli- org/10.1145/2451116.2451150. cation of machine learning algorithms to flow modeling Shin, E. C., Polosukhin, I., and Song, D. Improving neural and optimization. In CTR ARB, 1999. program synthesis with inferred execution traces. NIPS, Murphy, K. P. Machine Learning: A Probabilistic Perspec- 2018. tive. 2012. Si, X., Raghothaman, M., Heo, K., and Naik, M. Synthe- Nye, M., Hewitt, L., Tenenbaum, J., and Solar-Lezama, A. sizing datalog programs using numerical relaxation. pp. Learning to infer program sketches, 2019. 6117–6124, 08 2019. doi: 10.24963/ijcai.2019/847. Solar-Lezama, A., Tancau, L., Bodik, R., Seshia, S., and Parisotto, E., Mohamed, A.-r., Singh, R., Li, L., Zhou, D., Saraswat, V. Combinatorial Sketching for Finite Pro- and Kohli, P. Neuro-symbolic program synthesis. arXiv grams. SIGOPS Oper. Syst. Rev., 2006. preprint arXiv:1611.01855, 2016. Sonoda, T., Yamaguchi, Y., Arima, T., Olhofer, M., Send- Ratner, A., Alistarh, D., Alonso, G., Andersen, D. G., Bailis, hoff, B., and Schreiber, H.-A. Advanced high turn- P., Bird, S., Carlini, N., Catanzaro, B., Chung, E., Dally, ing compressor airfoils for low reynolds number con- B., Dean, J., Dhillon, I. S., Dimakis, A. G., Dubey, P., dition—part i: Design and optimization. Journal of Tur- Elkan, C., Fursin, G., Ganger, G. R., Getoor, L., Gibbons, bomachinery, 2004.
Synthesizing Programs with Continuous Optimization
Spector, L. Autoconstructive evolution: Push, pushgp, and pushpop. In GECCO, 2001. Such, F. P., Madhavan, V., Conti, E., Lehman, J., Stanley, K. O., and Clune, J. Deep Neuroevolution: Genetic Algo- rithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning. CoRR, 2017. Wang, Y., Wang, X., and Dillig, I. Relational program synthesis. Proceedings of the ACM on Programming Languages, 2(OOPSLA):1–27, 2018. Winter, S., Brendel, B., Rick, A., Stockheim, M., Schmieder, K., and Ermert, H. Registration of bone surfaces, ex- tracted from CT-datasets, with 3d ultrasound. Biomedi- zinische Technik/Biomedical Engineering, 2002. Ye, X., Chen, Q., Dillig, I., and Durrett, G. Optimal neural program synthesis from multimodal specifications. CoRR, 2020. Zohar, A. and Wolf, L. Automatic Program Synthesis of Long Programs with a Learned Garbage Collector. CoRR, 2018.
Synthesizing Programs with Continuous Optimization
A OVERVIEW AND METHODOLOGY OF with different network and max pooling is used to aggregate
PREVIOUS SCHEMES the output. Then they are passed through a softmax layer to
Table 4 outlines an overview of each of the schemes we get the probability distribution. We used all 420K programs
reproduced. and trained the model for ∼2 days to converge.
Shgo: Shgo (Endres et al., 2018) is simplicial PushGP: PushGP is a genetic programming based ap-
homology global optimization technique. We proach (Spector, 2001). It works in a stack based evalu-
used Shgo as a blackbox continuous optimiza- ator. Each of the data type has it’s own stack. And recent tion technique to justify our choice of CMA-ES in result is always on top of the stack. Push instruction acts by GENESYS. We used Shgo implementation from https: pushing and popping various elements on and off the stacks. //docs.scipy.org/doc/scipy/reference/ The program interpreter maintain it’s own exec stack that generated/scipy.optimize.shgo.html. maintain the control flow of the program. Our PushGP im- plementation follows the technique mentioned in (Spector, NPO: In NPO (Liskowski et al., 2020), an autoencoder 2001). based neural network model is used to encode and decode NetSyn: NetSyn (Mandal et al., 2021) uses genetic algo- programs to and from latent continuous representations. In rithm with a LSTM based recurrent neural network as fit- one end the encoder takes program and and creates a vector ness function. Fitness function give some score based on the representation of the program. CMA-ES works with such genes from gene pool about how good or bad those genes vectors to find the optimal vector. That vector is passed are. Based on the score, genetic mutation happens and new through a decoder to produce the target program. We used genes are created for next generation. The LSTM model stack based LSTM for the encoder and decoder. The encoder takes IO examples and program traces as input and produce takes the program and tries to produce the same programs fitness score as output. It took ∼3 days to train the model. on the decoder part. We used 420K programs to train the This LSTM model is used in one of the schemes (i.e., bin autoencoder. The model took ∼12 hours to train. mapping with biasing (Section 4.3)) of GENESYS. DeepCoder: In Deepcoder (Balog et al., 2017), a feed for- In summary, we used the same training set to train each ward neural network model is used to predict function prob- of the prior schemes. We trained the models until they ability for a given specification. The model passes IO exam- converged. Thus, we gave the best effort for a faithful ples through an embedding layer and produces a 20 length reproduction of prior schemes. long vector. Then it passes through multiple layer of feed forward block. All the IO examples are passed through their B O individual block and aggregated together with a pooling THERS layer. A softmax function is used to predict the probability Probability Distribution distribution of the functions. We used all the 420K random programs to train the model (Section 5.1). It took ∼2 days Fully for the model to converge. Connected PCCoder: PCCoder (Zohar & Wolf, 2018) is an encoder- Fully Connected decoder based neural network model. It takes the specifica- LSTM LSTM tion and creates state embedding. Those state embedding is passed through the dense block of neural networks (NN). For Hidden Vector Hidden Vector multiple IO examples, it passes through different NN blocks LSTM (H₁) (Hₘ) and max pooling is used to aggregate the result. Then it uses softmax to get the probability distribution. Like DeepCoder, LSTM LSTM LSTM Layers LSTM Layers we used all 420K programs and trained for ∼2 days. Embedding Embedding RobustFill: RobustFill (Devlin et al., 2017) is a seq-to-seq Input₁ Output₁ IO Example₁ … IO Example m neural network model that uses a encoder-decoder archi- tecture where the encoder takes the specification and the IO Example₁ decoder produce the program. It generates the probability (a) (b) distribution of different functions and a beam search is used Figure 6: Neural network design for (a) single and (b) mul- to search for the program. The hidden representation ht is an tiple IO examples. In each figure, layers of LSTM encoders LSTM hidden unit given by Et = Attention(ht−1, e(X )), are used to combine multiple inputs into hidden vectors for ht = LST M (ht−1, Et). Here e(X ) is the sequence of hid- the next layer. Token probability distribution is produced by den states after processing the specification with an LSTM the fully connected layer. encoder. For multiple IO examples, all of them are passed
Synthesizing Programs with Continuous Optimization
10"
asm ge “a³
8 60 10?
7 & <
ZL [=
2 10°
>
wom + pochs = pt Jwᴺ oo wᴺ005aeₓ
Figure 7: Neural network training accuracy
Figure 8: Choice of DSL with Multi group and Bin mapping
B.1 Learning Model Characterization B.3 Restart Number
Figure 6 shows the neural network model that we use to On average GENESYS restarts 5-15 times for different restart
learn function probability. It has two components mainly. policies except PB based. In PB policy, only the population
Figure 6(a) shows how to feed single IO example to the get doubled up but the mean vector and covariance-matrix
network. Input and output is a list of integer values. They remain same. After reaching some local minima, despite
go through embedding layer and each element in the list is the population increase it always stuck in the same min-
represented by 20 length long latent representation. After ima for every restart as mean or covariance doesn’t change.
that, embedded input and output is fed through LSTM layer. Thus, in PB policy once GENESYS reaches some local min-
We use 5 IO examples in the specification. Each of the ima it restarts in every generation and needs to stop as the
IO create their own hidden vector from their LSTM block. increased population make the system out of memory. Those vectors got through a different LSTM block and some fully connected layer before giving the token probability =~ B.4 Characterizing CMA-ES Internals distribution for the given specification. Figure 7 shows the training accuracy of the model across epochs. The model is CMA-ES starts by initializing five major components which trained until it converges. We use same number of training are called state variables. Three of them are related to data as other baselines described in Section A covariance matrix, one is for mean vector and the last one is step size, called sigma. A sample size is pre-determined to B.2 DSL grouping set the number of sampled out genes from the state variables. Now, at the start of each generation, CMA-ES samples Apart from the regular DSL we tried one different DSL out genes. To do that, it first multiplies the eigenvectors grouping approach. In our DSL we have two type of func- and eigenvalues with the sampled out values from normal tions, regular function and higher order function. For exam- distribution. Mean vector is added after multiplying with ple, Map is a higher order function that can have multiple sigma. After getting the fitness score for each of the genes, regular functions like Map(+1), Map(*2) etc. In DSL group these state variables updated based on the weighted fitness mechanism we group such higher order function together score for the next generation. and while constructing program we tried all possible com- Figure 9 shows CMA-ES characteristics for these five major bination of functions from the same group. Although this components. We choose one program to synthesize and run approach might increase the synthesis time, the intuition with G was synthesis rate might also be increased. ENESYS with different random seeds. Then we took 2 runs from found and not found case to see how CMA-ES Figure 8 shows result for two different DSL setup that we behaves internally. As covariance matrix (C), eigenvectors tried. For multi group mapping, synthesis rate is higher (B) and eigenvalues (D) are all squared matrix, for 2d visu- for group DSL compared to regular DSL as 69% vs 42%. alization we convert them into scalar value using principal But when binning mapping is used we get as high as 88% component analysis (PCA) (Li & Wang, 2014). We do the synthesis rate with regular DSL compare to 56% for Group same for the mean vector. Mean vector dimension is same DSL. Synthesis time also follows the same pattern. as the number of variables in CMA-ES. Step size is a scalar
Synthesizing Programs with Continuous Optimization
value. We run GENESYS without any restart policy and took last N generations values for visualization purpose. Fig- ure 9 shows that for the not found cases, different CMA-ES component values become stagnant and hence, GENESYS is not able to find the solution. We notice that the mean vector is the most affected one by the stagnant values in the not found cases. The variance of the mean vector and step size is high for the found cases over generations. However, for the not found cases, it reduces significantly. For both cases, covariance matrix converges guided by the fitness score. Due to the ill fitness scores, it may stuck in a local minima where the solution is not present. This observation motivated us to use the restart mechanism and find the best restart policy for GENESYS.
Program Length Baseline Synthesis Percentage (%) 5 Shgo 46 5 NPO 57 5 DeepCoder 91 5 PCCoder 88 5 RobustFill 90 5 PushGP 90 5 NetSyn 95 5 GeneSys 89 7 Shgo 19 7 NPO 60 7 DeepCoder 75 7 PCCoder 70 7 RobustFill 74 7 PushGP 80 7 NetSyn 85 7 GeneSys 87 10 Shgo 6 10 NPO 59 10 DeepCoder 52 10 PCCoder 73 10 RobustFill 67 10 PushGP 83 10 NetSyn 87 10 GeneSys 87
Table 6: Synthesis percentage with different baselines across multiple program length
Synthesizing Programs with Continuous Optimization
06 3 (True) 1077 05 . os), 04 «run:© 1 (True) | [x3 «run: 3 (False) 03 . 10 . ¥
02 iE . 02 N 00 oof o :. oo 25 so 75 100 135 130 175=200 6 25 s0 75 100 135 150 175ᶠᵃᵐ200| 02 © 25 soha75 100 135 150 175—200 Generation Generation (a) Covariance matrix (b) Eigenvectors (c) Eigenvalues
04 5 200 =
0 7 ws ‘
oat — 150 =
125
oof 7a 100 % ;
075
-02 050
wo
— oz
© 25 so 75 100 135 150 175 200 6 25 50 75 100 135 150 175 200
Generation Generation
(d) Mean (e) Step size
Figure 9: Here we show 5 of the major internal components of CMA-ES. They are 3 squared matrices; Covariance matrix (C), Eigenvectors (B), Eigenvalues (D), mean and step size (sigma). We used PCA to convert the squared matrix into scalar value for plotting purpose. We choose two program cases, found case (True) and not found case (False), two from each; to show their behavior while being synthesized in CMA-ES. We took last N generation values and plot them against corresponding generation number.