Towards Open-domain
Generation of Programsfrom Natural Language
Graham Neubig@ UT Austin 10/29/2018

Acknowledgements
Based on work w/
Pengcheng Yin,

Bogdan Vasilescu

Bowen Deng, Edgar Chen, Junxian He, Chunting Zhou,
Shirley Hayati, Raphaël Olivier, Pravalika Avvaru, Anthony Tomasic

Supported byCoding =Concept → Implementationsort list x
in descendingorder

x.sort(reverse=True)

The (Famous) Stack
Overflow Cycle
Formulate the Idea

sort my_list in descending order

python sort list in descending order

Search theWeb

Browse thru.
results

Modify the
resultsorted(my_list, reverse=True)

Goal: Assistive Interfaces for
Programmers

Interface by William Qian

Today’s Agenda:
Can Natural Language Help?
•

Syntactic models to create code from natural
language•

Large-scale mining of open-domain datasets forcode generation•

Semi-supervised learning for semantic parsing andcode generation•

Retrieval-based Code Generation

Natural Language vs.
Programming Language

Natural Language vs. CodeNatural Language

Code

Human interpretable

Human and machine interpretable

Ambiguous

Precise in interpretation

Structured, but flexible

Structured w/o flexibility

Note: Good summary in Allamanis et al. (2017)

Structure in Codeif x % 5 == 0:
AST Parser
Can we takeadvantage ofthis for better
NL-code interfaces?

If
Compare
BinOp
Name
x

Load

Num

Num
%

5

==

0

(used in models of Maddison & Tarlow 2014)

A Syntactic Neural Model for Code
Synthesis from Natural Language(ACL 2017)

Joint Work w/ Pengcheng Yin

Previous Work•

Lots of work on rule-based methods for natural
language programming (e.g. see Balzer 1985)•

Lots of work on semantic parsing w/ grammarbased statistical models (e.g. Wong & Mooney
2007)

•

One work on using neural sequence-to-sequencemodels for code generation in Python (Ling et al.
2016)Sequence-to-sequence Models(Sutskever et al. 2014, Bahadanau et al. 2015)•

Neural network models for transducing sequences
sort
RNN

list
RNN

sort
RNN

sort

RNN

(
RNN

(

x

RNN

RNN

x
RNN

x

backwards

,
RNN

,

...

reverse
Proposed Method: Syntactic
Neural Models for Code Synthesis• Key idea: use the grammar of the programming language(Python) as prior knowledge in a neural model
Input Intent

sort my_list in descending order

Generated AST

Deterministictransformation(using Python astor library)Surface Codesorted(my_list, reverse=True)

NOTE: very nice contemporaneous work by Rabinovich et al. (2017)

Generation Process• Factorize the AST into actions:•ApplyRule: generate an internal node in the AST•GenToken: generate (part of) a token

Formulation as a Neural
Model• Encoder: summarize the semantics of the NL intent• Decoder:• Hidden state keeps track of the generation process of the AST• Based on the current state, predict an action to grow the AST
Action Sequence

LSTM Decoder

NL Intent

LSTM Encoder

Action Flow
Parent Feeding (Dong and Lapata, 2016)

Computing Action
Probabilities• ApplyRule[r]: apply a production rule r to the current derivation• GenToken[v]: append a token v to the current terminal node
• Deal with OOV: learning to generate a token or directly copy it from the
input
Generation prob.

Copy prob.

Derivation

Final probability:
marginalize over
the two paths

Experiments••

Natural Language ⟼ Python code:•

HearthStone (Ling et al., 2016): card game
implementation•

Django (Oda et al., 2015): web framework

Natural Language ⟼ Domain Specific Language(Semantic Parsing)•

IFTTT (Quirk et al., 2015): personal task automation
APPDjango Dataset• Description: manually annotated descriptions for 18K lines
of code• Target code: one liners• Covers a wide range of real-world use cases like I/O
operation, string manipulation and exception handling
IntentTargetcall the function _generator, join the result into astring, return the result

HearthStone Dataset• Description: properties/fields of an HS card
• Target code: implementation as a Python class from
HearthBreaker
Intent (Card Property)<name> Divine Favor </name> <cost> 3 </cost> <desc>
Draw cards until you have as many in hand as youropponent </desc>
Target (Python class, extracted from HearthBreaker)[Ling et al., 2016]

IFTTT Dataset• Over 70K user-generated task completion snippets
crawled from ifttt.com• Wide variety of topics: home automation,
productivity, etc.
• Domain-Specific Language (DSL): IF-THIS-THENTHAT structure, much simpler grammar
Intent Autosave your Instagram photos to
DropboxTarget IF Instagram.AnyNewPhotoByYou
THEN Dropbox.AddFileFromURL

https://ifttt.com/applets/1p-autosaveyour-instagram-photos-to-dropbox[Quirk et al., 2015]

Results• Baseline systems (do not model syntax a priori):–Latent Predictor Network [Ling et al., 2016]–Seq2Tree [Dong and Lapata., 2016]–Doubly recurrent RNN [Alvarez-Melis and Jaakkola., 2017]• Take Home Msg:
–Modeling syntax helps for code generation and semantic
parsingExamples
Intentjoin app_config.path and string 'locale' into a file path, substitute it for localedir.

Pred.
Intentself.plural is an lambda function with an argument n, which returns result of boolean expression n
not equal to integer 1

Pred.
Ref.
Intent<name> Burly Rockjaw Trogg </name> <cost> 5 </cost> <attack> 3 </attack> <defense> 5</defense> <desc> Whenever your opponent casts a spell, gain 2 Attack. </desc> <rarity>
Common </rarity> ...

Ref.

tokens copied from input

TranX Parser [Yin+18]•

Transition-based AST parser based on “abstract syntax
description language”•

Can define language flexibly for various types of semantic
parsing•Good results out-of-the-box!

https://github.com/pcyin/tranX

Learning to Mine NL/Code Pairs
from Stack Overflow(MSR 2018)
Joint Work w/
Pengcheng Yin, Bowen Deng, Edgar Chen, Bogdan Vasilescu

Datasets are Important!
•

Our previous work used Django, HearthStone,
IFTTT, manually curated datasets•

It couldn't have been done without these•

But these are extremely specific, and small

StackOverflow is Promising!
• StackOverflow
promises a large
data source for code
synthesis• But code snippets
don’t necessarilyreflect the answer tothe original question

Mining Method

Annotation• ~100 posts for Python/Java

Features (1):Structural Features• "does this look like a valid snippet?"–Position: Is the snippet a full block? The start/end of a block?
The only block in an answer?
–Code Features: Contains import? Starts w/ assignment? Is
value?
–Answer Quality: Answer is accepted? Answer is rank 1, 2, 3?
–Length: What is the number of lines?

Features (2):Correspondence Features• "do the intent and snippet look like they match?"–Train an RNN to predict P(intent | snippet) and P(snippet |intent) given heuristically extracted noisy data
–Use log probabilities and normalized by z score over post,etc.

Main Results• On both Python and Java,better results thanheuristic strategies• Both structural andcorrespondence features
were necessary

Transfer Learning• Can we perform classification w/ no labeled data for that
language?
PythonJavaExamples: Code Naturallanguage Challenge•~2500 mined and manually verified examples•~600k automatically mined examples{"question_id": 36875258,"intent": "copying one file's contents to another in python","rewritten_intent": "copy the content of file 'file.txt' to file 'file2.txt’”,"snippet": "shutil.copy('file.txt', 'file2.txt’)”}{"question_id": 22240602,"intent": "How do I check if all elements in a list are the same?","rewritten_intent": "check if all elements in list `mylist` are the same","snippet": "len(set(mylist)) == 1"}

http://conala-corpus.github.io

StructVAE: Semi-supervised
Learning for Semantic Parsing(ACL 2018)

Joint Work w/
Pengcheng Yin, Junxian He, Chunting Zhou

Motivation
Neural Models are Data Hungry

Data Collection is Costly
Copy the content of file 'file.txt' to file 'file2.txt'
shutil.copy('file.txt','file2.txt')

Get a list of words `words` of a file 'myfile'
words = open('myfile').read().split()

Check if all elements in list `mylist` are the same

Purely supervised neuralsemantic parsing models requirelarge amounts of training datalen(set(mylist)) == 1

Collecting parallel
training data costs
and[Yin et al., 2018] 1700 USD for 3K Python code generation examples[Berant et al., 2013] 3000 USD for 5.7K question-to-logical form
examplesExisting Solutions
Weakly supervised
Learning
Q: Which college did Obama go to?
(and (Type University)(Education BarackObama))
A: Occidental College, Columbia Univ.

Clarke et al. (2010)
Liang et al. (2011)
Berant et al. (2013)
Berant and Liang (2014)
Yih et al. (2015)

Data Augmentation
What states border texas?
is_state(x) andborder(x, texas)
What states border ohio?
is_state(x) andborder(x, ohio)

Jia and Liang, (2016)
Wang et al. (2015)

Zero-Shot Learningand Domain Adaptation
Fan et al. (2017)
Su and Yan, (2017)
Herzig and Berant,(2018)

Semi-supervised Semantic
Parsing
Limited Amount of Labeled Data
Sort my_list in descending order

Extra Unlabeled Utterances
Get a list of words `words` of a file 'myfile'sorted(my_list, reverse=True)
Convert a list of integers into a single integer
Copy the content of file 'file.txt' to file
'file2.txt'
shutil.copy('file.txt’,'file2.txt')
Check if all elements in list `mylist` are
the samelen(set(mylist)) == 1

Format a datetime object `when` toextract date only
Swap values in a tuple/list in list `mylist`
BeautifulSoup search string 'Elsie' inside
tag 'a'Convert string to lowercase

Tree-structured Latent Variables
Structured Latent Semantic Space

Prior

p(

sorted(my_list, reverse=True)
Latent Meaning Representation(Abstract Syntax Trees)

Inference Model
Posteriorinferencecorresponds tosemantic parsing

q (

|

)

Reconstruction Modelp✓ (Sort my_list in descending
order

|

)

)

Semi-supervised Learning w/
StructVAE
Labeled Data{

Unlabeled Data,

Structured Latent Semantic Space

}

{

}

Prior

p(

Supervised Objective(X,

log q (|))

) ∈ Labeled Data

Unsupervised ObjectiveX

log p()∈ Unlabeled Data

Inference Model

q (

|

)

Reconstruction Model

|

p✓ (

Sort my_list in descending
order

p(

)

) = ∫ p(

|

) p(

)

StructVAE: VAEs with
Structured Latent Variables
Inference Model|p✓ (Neural semantic parser

Prior

Reconstruction Model)

Neural sequence-to-sequence model

Neural Language Model(use linearized trees as inputs)

Variational approximation of the marginal likelihood
Unsupervised ObjectiveX

log p()∈ Unlabeled Datalog p(

)

0

X

⇠q (

|

log p✓ (|)

h

KL Divergence q (

|

0

)

)||p(

)

i

[Miao and Blunsom,
2016]How Does Unsupervised Data
Help?

Supervised Objective(X,

log q (|)

) ∈ Labeled Datar =X@ log q (@Training Examples|)

How Does Unsupervised
Data Help?
Unsupervised ObjectiveX

log p(r/)∈ Unlabeled Data

The learning signal

X

Sampled

⇡

Prior

0

⇥

0

@q (
@

|

)

Reconstruction Model

Learning signal acts as the tuning weights of gradients received by different
sampled latent meaning representations from the inference modelHow Does Unsupervised
Data Help?
Sort my_list in descending order

00

Prior

Reconstruction Model

Prior

Reconstruction Model

Prior

Reconstruction Modelsorted(my_list)

1

0
2

0
3

sorted(my_list,
reverse=True)

sorted(my_list,
descending=True)

Learning fevers sampled latent meaning representations that are both:•

Faithfully encode the semantics of the utterance -> highreconstruction score•

Succinct and natural -> high prior probability

The Inference Model:
AST-based Parser
Inference Model

A transition-based parser that transduces natural language
utterances into Abstract Syntax Trees

Grammar Specification
stmt

expr

FunctionDef(identifiler name,arguments args, stmt* body)| Expr(expr value)Call(expr func, expr* args,

Transition System

Abstract Syntax Tree

ApplyConstr(Expr)

Expr

ApplyConstr(Call)Call

keyword* keywords)| Name(identifier id)| Str(string id)

ApplyConstr(Name)
Name

Name

sortedmy_listInput Utterance

Sort my_list in descending order

...

...

GenToken(sorted)

Keyword[Yin and Neubig, 2017;
Rabinovich et al. 2017]

Research Questions•

RQ1 Does StructVAE outperforms purely
supervised semantic parsers with extra unlabeled
data?

•

RQ2 Can we get some empirical evidence about
why StructVAE works?

StructVAE vs. Baselines
Inference model as supervised parser
Self Training (semi-supervised baseline)
StructVAE
The gap is much
more obvious when
we use a mediocre
parser J

all available training utterances as unlabeled dataWhy does StructVAE
Work?
•

For each unlabeled utterance, compute the learning signal
samples and other (imperfect) samples
0

Avg.=-5.12

for gold

Avg.=2.59

0.2
0.1
0.0

30

20

10

0

10

Other Samples

020Gold Samples

Learning Signal
Join p and cmd into a file path, substitute it for f
Parser Score

q (

|

Prior

Reconstruction Score

p✓ (

)

|

Learning Signal)

f = os.path.join(p, cmd)

-1.00

-24.33

-2.00

9.14

p = path.join(p, cmd)

-8.12

-27.89-20.96-9.47

Split string pks by ‘,’ , substitute the result for primary_keys
Parser Score

q (

|

Prior

Reconstruction Score

p✓ (

)

|

Learning Signal)

primary_keys = pks.split(’,’)-2.38-10.24-11.392.05

primary_keys = pks.split + ’,’-1.83-20.41-14.87-2.60

Retrieval-based Neural Code
Generation(EMNLP 2018)
Joint Work w/

Shirley Hayati, Raphaël Olivier, Pravalika Avvaru,
Pengcheng Yin, Anthony Tomasic

The Stack Overflow Cycle
Formulate the Idea

sort my_list in descending order

python sort list in descending order

Search theWeb

Browse thru.
results

Modify the
resultsorted(my_list, reverse=True)

Can we do the same thing in code generation models?!

Reminder: Syntax-based
Generation
Input: params is an empty list
Output: params = [ ]Neural Model: bidirectional EncoderDecoder with Action Embedding,Context Vector, Parent Feeding,
Copying Mechanism
Actions:
Apply Rule
Generate Token
Generate Token with Copy

Action Tree:Neural MachineTranslation + Retrieval[Gu+2018, Zhang+2018]
Input

retrieveparams is an empty list

Retrieved from Train Set
List lst is an empty list

Params adalah list kosong

List lst adalah list kosong

extract

Boostedn-gramprobability

n-gramsn-gramsboost

n-grams

ReCode: Neural Code
Retrieval + Generation
Input

retrieveparams is an empty list
params = [ ]Retrieved from Train Set
List lst is an empty list
lst = [ ]extract

Boostedn-gramprobability

boost

n-gram action
subtreesN-gram Action Subtrees

Name → str
str → [lst][/n]3-Gram Action Subtree

List

lst

is

an

empty

list

N-gram Action Subtrees
w/ Copying
Input
1
Name → str

params

2

3

4

5

is

an

empty

list

str → params[/n]3-Gram Action Subtree

List

lst

is

an

empty

list

1

2

3

4

5

6

Retrieved

COPY Action in GENTOKEN

ReCode Pipeline
NL description: “params is an empty list”
Compute similarity

Train Set
<description,code>
NeuralModel

Extract
N-gram Action
Subtrees

Boost n-gram
subtree probability

Decoding
Step

Code

Results
All improvements are statistically significant with p < 0.001

84.5 84.7
75.8

78.4

Conclusion

Conclusion•

Data-driven language → code within reach!

•

Modeling structure of the PL is important andhelpful•Data is difficult, but we're making progress throughmining•Semi-supervised learning and retrieval to takeadvantage of large datasets

Questions?