PaperlayerView exact revision on arXiv

Source-linked AI summary

Typilus: Neural Type Hints

Miltiadis Allamanis, Earl T. Barr, Soline Ducousso, Zheng Gao

arXiv:2004.10657v1cs.PLcs.LGstat.ML

TL;DR

Type inference in dynamically typed languages must handle incomplete contexts and open-ended, rare type vocabularies. Typilus uses graph-based probabilistic reasoning and a learned TypeSpace, confidently predicts types for 70% of annotatable symbols with 95% optional type-checking accuracy, and finds accepted annotation fixes.

  • Problem

    Type prediction is difficult in dynamic languages because partial contexts reduce traditional analysis precision and real-world code contains many rare, domain-specific types.

  • Method

    Typilus combines a graph-based neural network with deep similarity learning to embed symbol type properties in a TypeSpace and predict open-vocabulary types.

  • Results

    70% of annotatable symbols receive confident predictions, and predicted types optionally type check 95% of the time; Typilus also identified errors whose fixes were accepted in fairseq and allennlp.

  • Takeaways & Limitations

    Learning from identifiers and coding idioms provides an approximate, high-precision alternative to defaulting to Any in dynamically typed languages.

  • Takeaways & Limitations

    Typilus commonly confuses variables with collections and underpredicts Union types, indicating that its TypeSpace does not fully represent unions.

Abstract

from arXiv · show

Type inference over partial contexts in dynamically typed languages is challenging. In this work, we present a graph neural network model that predicts types by probabilistically reasoning over a program's structure, names, and patterns. The network uses deep similarity learning to learn a TypeSpace -- a continuous relaxation of the discrete space of types -- and how to embed the type properties of a symbol (i.e. identifier) into it. Importantly, our model can employ one-shot learning to predict an open vocabulary of types, including rare and user-defined ones. We realise our approach in Typilus for Python that combines the TypeSpace with an optional type checker. We show that Typilus accurately predicts types. Typilus confidently predicts types for 70% of all annotatable symbols; when it predicts a type, that type optionally type checks 95% of the time. Typilus can also find incorrect type annotations; two important and popular open source libraries, fairseq and allennlp, accepted our pull requests that fixed the annotation errors Typilus discovered.

1 Introduction

Typilus addresses the difficulty of inferring types in incomplete, dynamically typed programs by learning from code patterns rather than treating types as a fixed classification vocabulary. Its graph-based, metric-learning approach supports rare and unseen types, achieving high-confidence predictions and finding annotation errors in real libraries.

  • 32% of type annotations are rare, so closed-vocabulary type prediction faces a performance ceiling.
  • Typilus embeds symbol type properties in a learned TypeSpace, keeping same-type symbols close and different-type symbols apart.
  • A graph neural network models source-code syntax and semantics, producing 7.6% more exact matches for common types than a sequence-based model.
  • Typilus detected incorrect annotations in fairseq and allennlp, and both submitted fixes were accepted.
  • The approach combines graph-based learning, deep similarity loss, and adaptation to rare or unseen types without retraining.

2 Overview

Typilus targets open-vocabulary type prediction by learning a continuous TypeSpace from code context and linking embeddings to concrete types. Its inference pipeline retrieves nearby type candidates and uses type checking to filter predictions.

  • Typilus targets an open type vocabulary, including types unseen during training, and uses a type checker to verify useful predictions.
  • The overall architecture trains embeddings from annotated code, then applies the learned type map to unannotated code during inference.
  • The GNN maps variables, parameters, and functions into a learned real-valued TypeSpace using identifiers, syntax, control flow, and data flow.
  • For a query symbol, Typilus retrieves nearby concrete types through k-nearest-neighbour search and returns a probability distribution over candidates.
  • A type checker examines the highest-probability predictions and suggests them only when no type errors are found.

3 Background

Prior probabilistic type-inference systems exploit program structure, token sequences, or documentation, but neural and statistical approaches remain connected to the challenge of predicting types in dynamic languages. The background motivates Typilus’s use of richer code signals and attention to rare types.

  • Probabilistic type inference assigns types under uncertainty, unlike traditional inference that commonly requires soundness.
  • JSNice represents JavaScript as a graph and uses a conditional random field to predict variable types from inferred relationships.
  • DeepTyper models source code as token sequences with a biLSTM, while combining it with JSNice improves overall performance.
  • Documentation-based prediction extracts type information from comments, but like other prior methods it suffers from the rare-type problem.
  • Other work exploits variable names and static interprocedural data flow to refine nominal types such as strings into domain-specific categories.

4 The Deep Learning Model

The model learns a continuous TypeSpace with deep similarity learning, combining pairwise similarity and classification objectives to support robust, open-vocabulary type prediction. At inference, it maps known type embeddings and uses nearest neighbours to predict types, including newly added ones without retraining.

  • Type Space: Classification partitions embeddings into a fixed vocabulary, whereas similarity learning represents an open vocabulary that can include rare and previously unseen types.Classification relies on prototype vectors for known types; similarity learning instead maps types into a continuous real space.
  • Type Space: Triplet loss pulls embeddings of similarly typed symbols together and pushes differently typed symbols apart by a margin.The model uses L1 distance in its similarity objective and generalises triplet loss to multiple positive and negative symbols.
  • Typilus Loss: Typilus combines similarity and classification losses because classification provides prototype anchors while similarity learning handles rare types but can scatter embeddings.The combined objective includes type erasure and a learned projection to obtain coarse relations among parametric types.
  • Adaptive Type Prediction: The learned embedding maps known typed symbols to type markers, then predicts a query type from its k nearest embedding neighbours.Neighbour distances are converted into probabilities, with a temperature parameter interpolating between uniform neighbour weighting and the single-nearest-neighbour rule.
  • Adaptive Type Prediction: An adaptive type map accepts bindings for previously unseen symbols, allowing Typilus to add new candidate types without retraining the embedding function.A developer or type inference engine can add such bindings before test time.

5 Typilus: A Python Implementation

Typilus represents Python files as graphs combining tokens, syntax, data flow, symbol-table information, and identifier subtokens. A graph neural network uses typed nodes and labelled edges to learn representations for symbols and predict their types.

  • Graph Representation: Typilus extracts per-file Python graphs that encode tokens, syntax trees, data flow, and symbol-table information.The construction is a feature-extraction design choice rather than a uniquely optimal graph representation.
  • Graph Representation: The graph contains token, syntax-tree, vocabulary-subtoken, and symbol nodes, with symbol nodes representing variables or parameters.Function parameters and returns receive separate symbol nodes that are combined to recover a function signature.
  • Graph Neural Network: Symbol type embeddings are taken from the hidden state of each symbol node, with separate parameter and return representations supporting signature recovery.The graph neural network updates node states using messages received from directly connected neighbours.
  • Graph Representation: Graph edges encode relationships among nodes, including syntactic, token-order, and other code-pattern information used by the GNN.NEXT_TOKEN can be predictive despite being redundant for traditional program analysis.
  • Graph Representation: Subtoken edges connect identifiers to vocabulary nodes, capturing textual similarities between names even when identifiers are previously unseen.Identifiers are split on CamelCase or underscore conventions to obtain subtokens.

6 Quantitative Evaluation

Typilus is evaluated on real-world Python projects using type-annotation agreement, optional type checking, ablations, confidence filtering, and computational comparisons. The results show strongest gains for rare types, high-confidence coverage, and graph-based efficiency, while cross-language comparisons and annotation ground truth remain qualified.

  • 6.1 Quantitative Evaluation: Meta-learning methods significantly improve prediction of rare types while remaining only slightly worse than classification models on common types, and combining both objectives yields the best results.Table 2 covers common types seen at least 100 times and rare types seen fewer than 100 times.
  • 6.1 Quantitative Evaluation: 70% coverage reaches about 95% type neutrality for high-confidence predictions, and optional type checking further removes obviously incorrect suggestions.The confidence threshold allows the precision-recall trade-off to be adjusted before type-checker filtering.
  • Relating Results to JavaScript: Performance is numerically worse than reported JavaScript results, plausibly because of dataset differences, possible duplication in prior corpora, and Python’s more expressive type system.The paper states that Python’s detailed and sparse type hierarchies make annotation prediction harder than in JavaScript.
  • 6.1 Quantitative Evaluation: The GNN trains in 86 seconds per epoch versus 5,255 seconds for the biRNN and runs inference about 29 times faster, at 7.3 seconds per epoch.The speed advantage is attributed to parallelizable graph computation while preserving explicit long-range information.
  • 6.2 Ablation Analysis: Removing symbol names reduces exact match to 37.6%, while removing syntactic edges also harms performance; data-flow-use edges have negligible impact.The ablation indicates that identifiers and syntactic patterns provide useful predictive information, whereas use ordering adds little.
  • 6.3 Correctness Modulo Type Checker: 89% of Typilus predictions avoid type errors in mypy and 83% avoid them in pytype, indicating that predictions are commonly compatible with optional typing.These results come from applying the checkers to top predictions.

7 Qualitative Evaluation

The qualitative evaluation examines complex inferred types, confident errors, and disagreements with human or tool-generated annotations. Typilus handles some specific types well but struggles with deeply nested, union, and user-defined types.

  • Typilus cannot predict deeply nested parametric types that occur only in the test set, and it finds user-defined types difficult to infer.About 30% of annotations are parametric; among these, 80% have depth one and 19% depth two, while deeper types mostly appear once.
  • Typilus commonly confuses T with Optional[T] and predicts subsets of Union types, suggesting that its TypeSpace does not adequately represent unions.One example predicts Optional[int] instead of Optional[Union[float, int, str]].
  • Typilus identified human annotation errors in fairseq and allennlp, and both submitted pull requests were merged.The fairseq examples involved tensor dimensions annotated as float but predicted as int with 99.8% confidence.
  • Typilus sometimes predicts a correct, more specific type than an annotation or pytype, such as Dict[str, Any] instead of dict.The authors associate this disagreement with pytype’s conservative approximations.
  • Other disagreements include confusing str with bytes and confusing conceptually related user-defined tensor types from different machine-learning frameworks.An example maps mx.nd.NDArray to torch.Tensor.

8 Related Work

Related work applies machine learning to code tasks and program analysis, while code representations have progressed from token sequences to syntax-based and graph-based structures. Optional typing combines annotations with pluggable checking but provides no soundness guarantees.

  • Machine learning captures fuzzy code patterns for tasks such as completion, name prediction, documentation generation, and bug detection.
  • Code representations evolved from token sequences to ASTs and graphs that encode complex relationships among program elements.
  • Optional typing combines optional annotations with pluggable type checking while remaining an unsound form of gradual typing.

9 Conclusion

The paper presents a machine-learning method for predicting types in dynamically typed languages with optional annotations and realizes it for Python. It argues that learning from identifiers and coding idioms provides an approximate, high-precision alternative to frequent reliance on Any.

  • Typilus predicts types in dynamically typed languages with optional annotations and is realized for Python.
  • Learning from identifiers and coding idioms provides an approximate, high-precision alternative to relying on Any in many dynamic-language type-inference settings.
Loading 2004.10657v1…