Splitting source code identifiers using BiLSTM

Naming conventions

            UpperCamelCase
            lowerCamelCase
            lower_underscore
            UPPER_UNDERSCORE
        

Problem

            FooBarBaz = [foo, bar, baz]
            foobarbaz = ?
        

Applications

• Core vocabulary size reduction
  • e.g. in topic modeling, identifier embeddings
• Automatic naming fix
  • e.g. FoobarBaz → FooBarBaz
• Typing without "Shift"

Processing

1. Extract distinct identifiers from big code
2. Split them by naming convention heuristics
3. Use the resulting sequencies as labels

Public Git Archive (PGA)

• 182,014 GitHub top-starred repos
• 3 TB on disk
• 54,5 million files in HEAD
• 15,9 billion lines of code in HEAD
• 455 programming languages

Identifiers extraction

• sourced-ml
• sourced-engine
• Babelfish - AST parser
• Pygments - regexp parser

Labels

• Use the naming conventions
• 7.5% of the identifiers cannot be split
• Other 20% are split to the same sequence

Example

FooBarBaz -> [foo, bar, baz]

X: foobarbaz

Y: [foo, bar, baz]

Length threshold

• We exclude too long samples
• Actual threshold: 40 chars when merged

Why 40?

Heuristics

• UpperCamelCase -> [upper, camel, case]
• camelCase -> [camel, case]
• FRAPScase -> [fraps, case]
• SQLThing -> [sqlt, hing]
• _Astra -> [astra]
• CAPS_CONST -> [caps, const]
• _something_SILLY_ -> [something, silly]
• blink182 -> [blink]
• FooBar100500Bingo -> [foo, bar, bingo]
• Man45var -> [man, var]
• method_name -> [method, name]
• Method_Name -> [method, name]
• 101dalms -> [dalms]
• 101_dalms -> [dalms]
• 101_DalmsBug -> [dalms, bug]
• 101_Dalms45Bug7 -> [dalms, bug]
• wdSize -> [wd, size, wdsize]
• Glint -> [glint]
• foo_BAR -> [foo, bar]

Released

• 49.2 raw identifiers after extraction and filtering
• Raw identifiers per language, filtered
  • Java, C#, C, C++, Go, Python, Ruby, Objective-C, Javascript, PHP, Shell

Per language

Unsmoothed character-level model

• Use the maximum likelihood to estimate the probabilities $$P(\underline{\mbox{ }}|foo) = \frac{count(foo\underline{\mbox{ }})}{count(foo*)}$$
• The char-level LM makes the Markov assumption
• 2 models are trained independently in both directions, (AND, OR) combined
• Depth is set to 11
• Implementation based on CharStatModel

Dynamic programming

• Training :
• Wikipedia corpus
• Our dataset


• Assuming Zipf's law prior or posterior
• Implementation based on wordninja

Gradient boosting on decision trees

Gradient boosting on decision trees

• XGBoost
• Window length is 10
• Tree depth is 30
• Number of trees is 50
• 80% negative samples

Character-level Convolutional Neural Network

• One-hot encoding
• 3 stacked 1D Inception layers (ReLU)
• Time-distributed fully-connected layer with binary outputs (sigmoid)

Character-level Convolutional Neural Network

Single layer

Architecture

• CharRNN
• Prediction based on the two reading directions
• Two layers
• 256 neurons each

Training performance

• 10 epochs: ~15 hours
• 2 NVIDIA GTX 1080 cards

How we evaluated

• 80% train, 20% validation
• Precision, Recall and F1

Comparison

Comparison

Core vocabulary size

What we did

• Extracted 49.2 million distinct identifiers from PGA
• Used heuristics to generate the labeled dataset of 34.4 million samples
• Trained several ML models to split identifiers
• Found that the character-level bidirectional LSTM performed the best
• Reduced the core vocabulary size by 2 times

Future work

• Bootstrap the training
  • Apply the first generation model after splitting with heuristics
  • Train the second generation model on the new dataset
  • ...repeat?
• Do not completely discard non-alpha characters

Thank you

• vadim@sourced.tech
• vadimlearning
• vmarkovtsev
• blog.sourced.tech
• Awesome #MLonCode