Machine Learning on Code
from n-grams to GGNNs Waren Long
Nantes ML Meetup - July 1st, 2019
Programs as
ā ASTs ā Graphs
Early days
The first language models
Code is bimodal
"Source code is bimodal: it combines a formal algorithmic channel and a natural language channel of identifiers and comments. Because the two channels interact, [...] bimodality is a natural fit for machine learning."
Earl Barr
fMRI scans of skilled programmers show NLP parts of the brain active when reading code
Decoding the representation of code in the brain
... but code is hard to write
"Programming languages are inherently harder to write and read... so programmers deliberately write code as unsurprising as possible."
"Code (in all languages) is more predicatble than natural language because it more technical and difficult to learn."
Prem Devanbu at ML4P
On the natualness of Software
n-gram language model
Use a code corpus to estimate the probability distribution of code sequences.
Markovian assumption: the next token can be predicted using only the previous nā1 tokens
Infinite number of unknown tokens
Smoothing methods e.g. Katz smoothing
On the natualness of Software
Token-based applications
Code completion/suggestion
Coding convention: Naturalize
Code dediplication: CCFinder, SourcererCC
Bug detection: DeepBugs
The unveiling
Syntactical Features
Syntactical representation
Natural Language
Code
I shot an elephant in my pyjamas
Assert.NotNull(clazz)
Different Context
• Token neighbors
• AST-node neighbors
• AST paths
Design tradeoff from code2vec
Gemini
Code deduplication at Scale
Create Public Git Archive , dataset of 180k popular GitHub repos
Extract UASTs and combine various syntactical features
Create a pairwise similarity graph using Locality Sensitive Hashing
Extract connected components from the graph
Perform comunity detection to display highlight clone communities
src-d/gemini , source{d}
1. Public Git Archive
Dataset of 182,014 GitHub repositories with +50*
3TB of Git packfiles i.e. include history
455 distinct programming languages
54 million files
16 billion LoC
Public git archive: a big code dataset for all
2. Feature extraction
Identifiers and literals
Quantized number of children
Graphlets or tree skip gram ⇒
Random walks
AST paths (DFS + limited length)
3. Community detection
Attention mechanism
State of the Art
GGNNs
Programs as graphs
Start from syntax
Assert.NotNull(clazz)
Programs as graphs
Adding data flows
Potentially big graphs
def sum_positive(arr, lim):
sum = 0
for i in range(lim):
if arr[i] > 0:
sum += arr[i]
return sum
~900 nodes/graph
~8k edges/graph
Graph Neural Networks
Extend NNs to process a more general class of graphs (cyclic, directed)
Encode one graph into an dense representation
Suitable for both graph and node focuses applications
Each node of the graph is replaced by a unit computing the function
AST paths (DFS + limited length)
The Graph Neural Network Model
