OptTyper: Probabilistic Type Inference by Optimising Logical and Natural Constraints

By Irene Vlassi Pandi, Earl T. Barr, A. Gordon, Charles Sutton. 2020

33 citations recorded by the source corpus.

We present a new approach to the type inference problem for dynamic languages. Our goal is to combine logical constraints, that is, deterministic information from a type system, with natural constraints, that is, uncertain statistical information about types learnt from sources like identifier names. To this end, we introduce a framework for probabilistic type inference that combines logic and learning: logical constraints on the types are extracted from the program, and deep learning is applied to predict types from surface-level code properties that are statistically associated, such as variable names. The foremost insight of our method is to constrain the predictions from the learning procedure to respect the logical constraints, which we achieve by relaxing the logical inference problem of type prediction into a continuous optimisation problem. As proof of concept, we build a tool called OptTyper to predict missing types for TypeScript files. OptTyper combines a continuous interpretation of logical constraints derived by a simple program transformation and static analysis of TypeScript code, with natural constraints obtained from a deep learning model, which learns naming conventions for types from a large codebase. By evaluating OptTyper, we show that the combination of logical and natural constraints yields a large improvement in performance over either kind of information individually and achieves a 3% improvement over the state-of-the-art.

Subfields: Artificial Intelligence, Information Systems, Information Systems and Management, Evaluation & Benchmarks, Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Information Systems and Management

In Evaluation & Benchmarks

In Program Analysis & Verification

Citations in the corpus

Program Synthesis with Large Language Models (2021, methodology): “Several methods have been proposed to do machine learning for type inference, for example, to add types to untyped code, such as when converting Javascript to Typescript [Hellendoorn et al., 2018, Pandi et al., 2020, Pradel et al., 2020, Wei et al., 2020].”
Contrastive Code Representation Learning (2020, background): “Other authors have explored summarization [52, 5, 33] and type inference [11, 55, 70, 4, 58] with different languages and datasets.”
Type4Py: Practical Deep Similarity Learning-Based Type Inference for Python (2021, methodology): “[64] PGM DeepTyper [26] 10K+ biRNN NL2Type [41] 1K LSTM TypeWriter [51] 1K HNN (3x RNNs) LAMBDANET [62] 100a GNN OptTyper [47] 100 LSTM Typilus [12] Unlimited GNN TypeBert [29] 40K BERT”
Learning type annotation: is big data enough? (2021, unknown): “Following LambdaNet[25] and OPTTyper, we only use the human annotated locations for evaluation but include the compiler-inferred types in training data.”
Learning to Predict User-Defined Types (2023, methodology): “TypeBert, like other ﬁxed type vocabulary models [8], [9], [11], [12], ignores new types.”