LambdaNet: Probabilistic Type Inference using Graph Neural Networks
Authors: Jiayi Wei
Maruth Goyal
Greg Durrett
Isil Dillig
Venue:  (2020)
Keywords: Type inference
Graph neural network
Programming languages
Pointer network

Abstract: As gradual typing becomes increasingly popular in languages like Python and TypeScript, there is a growing need to infer type annotations automatically. While type annotations help with tasks like code completion and static error catching, these annotations cannot be fully inferred by compilers and are tedious to annotate by hand. This paper proposes a probabilistic type inference scheme for TypeScript based on a graph neural network. Our approach first uses lightweight source code analysis to generate a program abstraction called a type dependency graph, which links type variables with logical constraints as well as name and usage information. Given this program abstraction, we then use a graph neural network to propagate information between related type variables and eventually make type predictions. Our neural architecture can predict both standard types, like number or string, as well as user-defined types that have not been encountered during training. Our experimental results show that our approach outperforms prior work in this space by 14% (absolute) on library types, while having the ability to make type predictions that are out of scope for existing techniques. 

Published as a conference paper at ICLR 2020
LAMBDANET: PROBABILISTIC TYPE INFERENCE USING GRAPH NEURAL NETWORKS
Jiayi Wei, Maruth Goyal, Greg Durrett, Isil Dillig
Department of Computer Science University of Texas at Austin {jiayi, maruth, gdurrett, isil) (sis) wtw.as.edeeeeee
ABSTRACT
As gradual ryping becomes increasingly popular in languages like Python and TypeScript, there is a growing need to infer type annotations automatically. While type annotations help with tasks like code completion and static error catching, these annotations cannot be fully determined by compilers and are tedious to an- notate by hand. This paper proposes a probabilistic type inference scheme for TypeScript based on a graph neural network. Our approach first uses lightweight source code analysis to generate a program abstraction called rype dependency graph, which links type variables with logical constraints as well name and usage information. Given this program abstraction, we then use graph neural network to propagate information between related type variables and eventually make type predictions. Our neural architecture can predict both standard types, like number or string, well as user-defined types that have not been en- countered during training. Our experimental results show that our approach out- performs prior work in this space by 14% (absolute) library types, while having the ability to make type predictions that are out of scope for existing techniques.
INTRODUCTION
Dynamically typed languages like Python, Ruby, and Javascript have gained enormous popularity over the last decade, yet their lack of a static type system comes with certain disadvantages in terms of maintainabilityy (Hanenberg et al. 2013). the ability to catch errors at compile time, and code completion support (Gao al.] 2017). Gradual ryping can address these shortcomings: program variables have optional type annotations so that the type system can perform static type checking whenever possible (Siek Taha |007| Chung et al. 2018). Support for gradual typing now exists in many popular programming languages (Bierman et al. 2014 Vitousek et al.) 2014), but due their heavy use of dynamic language constructs and the absence of principal types (Ancona & Zucca 2004], compilers cannot perform type inference using standard algorithms from the programming languages community (Bierman et al. 2014] Traytel et al. 2011 [Pierce & Turner) 2000), and man- ually adding type annotations existing codebases is tedious and error-prone task. As result, legacy programs in these languages do not reap all the benefits of gradual typing.
To reduce the human effort involved in transitioning from untyped to statically typed code, this work focuses on a learning-based approach to automatically inferring likely type annotations for un- typed (or partially typed) codebases. Specifically, we target TypeScript, gradually-typer variant of Javascript for which plenty of training data is available in terms of type-annotated programs, While there has been some prior work on inferring type annotations for TypeScript using machine learning (Hellendoom et al. 2018 Raychev et al. 2015), prior work in this space has several shortcomings. First, inference is restricted to a finite dictionary of types that have been observed during train- ing time-i.e., they cannot predict any user-defined data types. Second, even without considering user-defined types, the accuracy of these systems is relatively low, with the current ofate-of-the- art achieving 56.9% accuracy for primitive/library types (Hellendoom et al.] 2018). Finally, these techniques can produce inconsistent results in that they may predict different types for different token-level occurrences of the same variable.

---

Published as a conference paper at ICLR 2020
class MyNetwork
2
name: string; time: number;
3
forward (x: Tensor, y: Tensor) Tensor {
4
return x. concat (y) x 2;
// more classes ...
function restore (network: MyNetwork); : void network. readNumber ("time.txt") // more code...
Figure A motivating example: Given unannotated version of this TypeScript program, traditional rule-based type inference algorithm cannot soundly deduce the true type annotations (shown in green).
In this paper, we propose new probabilistic type inference algorithm for TypeScript to address these shortcomings using graph neural network architecture (GNN) (Veličković al.) 2018 et al.) 2016 Mou et al.] (016). Our method uses lightweight source code analysis to transform the program into a new representation called a type dependency graph, where nodes represent type variables and labeled hyperedges encode relationships between them. In addition expressing logical constraints (e.g., subtyping relations) as traditional type inference, a type dependency graph also incorporates contextual hints involving naming and variable usage.
Given such a type dependency graph, our approach uses a GNN to compute a vector embedding for each type variable and then performs type prediction using pointer-network-like architec- ture (Vinyals et al., 2015). The graph neural network itself requires handling a variety of hyper- edge types- some with variable numbers of arguments- for which we define appropriate graph propagation operators. Our prediction layer compares the vector embedding of type variable with vector representations of candidate types, allowing to flexibly handle user-defined types that have not been observed during training. Moreover, our model predicts consistent type assignments by construction because it makes variable-level rather than token-level predictions.
We implemented our new architecture as tool called LAMBDANET and evaluated its performance on real-world TypeScript projects from Github. When only predicting library types, LAMBDANET has top1 accuracy of 75.6%, achieving a significant improvement over DeepTyppr (61.5%). In terms of overall accuracy (including user-defined types), LAMBDANET achieves topl accuracy of around 64.2%, which is 55.2 55.2% (absolute) higher than the TypeScript compiler.
Contributions. This paper makes the following contributions: (1) We propose probabilistic type inference algorithm for TypeScript that uses deep learning make predictions from the type de- pendency graph representation of the program. (2) We describe a technique for computing vector embeddings of type variables using GNNs and propose nointer-network-llie method to predict user-defined types. (3) We experimentally evaluate our approach on hundreds of real-world Type- Script projects and show that method significantly improves upon prior work.
2 MOTIVATING EXAMPLE AND PROBLEM SETTING
Figure I shows a (type-annotated) TypeScript program. Our goal in this work is infer the types shown in the figure, given an mnannttated version of this code. We now justify various aspects of our solution using this example.
Typing constraints. The use of certain functions/operatoors in Figure imposes hard constraints on the types that can assigned to program variables. For example, in the forward function, vari- ables x, y must be assigned type that supports concat operation; hence, x, y could have types like string, array, or Tensor, but not, for example, boolean. This observation motivates us to incorporate typing constraints into our model.
Typing constraints are not always sufficient for determining the intended type of a variable. For example, for variable ne network in function restore, the typing constraints require net work'ss 's type to class with a field called time, but there can be many classes that have such attribute (e.g., Date). However, the similarity between the variable network
Contextual hints.
2

---

Published as a conference paper at ICLR 2020
cl: 78 class MyNetwork {
name: Ti time: T27
var ml 73
var vl: function forward (x: 73, y: :4)
c.ncat;; var v2: v1 (y)
v3: T12 22.TIMES O?; v4: mh v3 (NUMBER)
return v4;
7
// more classes...
var f1:714 function restore (network: Te): v3: TIs network.time
11
var v4: Ti6 readNumber (STRING) network.time v4; // more code...
12
Figure 2: An intermediate representation of the (unannotated version) program from Figure The Ti represent type variables, among which Tg-Tio are newly introduced for intermediate expressions.
α
12
Subtype
Object
Name
F6
a
(time)
a1
P
α
name
time
Lorward
Usage
F15 8
13
TS
22
14
A
B
D
Figure 3: Example hyperedges for Figure 2 Edge labels in gray (resp. red) are positional arguments (resp. identifiers). (A) The return statement at line 6 induces subtype relationship between Tia and T5. (B) MyNetwork т declares attributes name тi and t time T2 and method forward Ty- (C) Tı4 is associated with variable whose named is restore. (D) Usage hyperedge for line 10 connects Ta and Ti5 to all classes with time attribute.
and the class name MyNetwort hints that network might have type MyNetwork. Based this belief, we can further propagate the return type of the library function readNumber (assuming we know is number) r) infer that the type of the time field in MyNetwork is likely to be number.
Need for type dependency graph. There are many ways to view programs-e.g- as token se- quences, abstract syntax trees, control flow graphs, etc. However, particularly helpful for inferring the most likely type annotations. Thus, our method uses static anal- ysis infer set of predicates that are relevant the type inference problem and represents these predicates using program abstraction called the rype dependency graph.
of these representations is
Handling user-defined types. As mentioned Section I prior techniques can only predict types seen during training. However, the code from Figure Figure[ddeiinee its own class called MyNet rk and later uses variables of type MyNetwork the restore method. successful model for this task therefore must dynamically make inferences about user-defined types based on their definitions.
2.1 PROBLEM SETTING
Our goal train type inference model that can take input an entirely (or partially) unannotated TypeScript project g and output a probability distribution of types for each missing annotation. The prediction space }(g) = Vib J Viseer)) (g), where (g)e(() is the set of all user-defined types (classes/interfaces, declared within g. and Vib is fixed set of commonly-used library types.
Following prior work in this space (Hellendoomn et al. 2018 Raychev et al. 2015 Xu et al.) 2016), we limit the scope of our prediction to non-polymorphic and non-function types. That is, we do not distinguish between types such as List<T>, List<number>: List<strince etc., and consider them all be of type List. Similarly, also collapse function types like number + string and st string + stringg into a single type called Punct ion. We leave the extension of predicting structured types future work.
3

---

Published as a conference paper at ICLR 2020
Table I: Different types of hyperedges used in a type dependency graph.
Type
Edge
Description
Logical
FIXED
Bool(a:)
is used as boolcan
FIXED
Subtype(a, ())
a a subtype of B
FIXED
Assign(a, 8)
3 is assigned to a
NARY
Function(a, B1, ........ 8k, 8*)
(3 (B...... 3x) 8
NARY
Call(a, 8" .I..... Bc)
3r ................................ Bn) a [4 8
NARY
Object, (a, .1.......... Bx)
Bx)
FIXED
Accessi(as
3.1
Contextual
FIXED
Namer
a has name a, B have similar names usages involving name
FIXED
NameSimilar(a, 8) (sag ,8"), (a1, Bz),................. (ax, Bx))
NPAIRS
Although assignment is a special case of a subtype constraint, we differentiate them because these edges appear in different contexts and having uncoupled parameters for these two edge types is beneficial.
TYPE DEPENDENCY GRAPH
type dependency graph 9 (N, E) is hypergraph where nodes N represent type variables and labeled hy hyperedges E encode relationships between them. We extract the type dependency graph of a given TypeScript program by performing static analysis on an intermediate representation of its source code, which allows us associate unique variable with each program sub- cub-expression. As an illustration, Figure shows the intermediate representation of the code from Figure
Intuitively, type dependency graph encodes properties of type variables as well relationships between them. Each hyperedge corresponds to one of the predicates shown in Table We partition predicates (i.e., hyperedges) into two classes, namely Logical and Contextual, where the for- mer category can be viewed as imposing hard constraints on type variables and the latter category encodes useful hints extracted from names of variables, functions, and classes.
Figure 3 shows some of the hyperedges in the type dependency graph G extracted from the in- termediate represennation in Figure 2 As shown in Figure A), analysis extracts a predicate Subtype(TIa, T3) from this code because the type variable associated with the returned expression v4 must subtype of the enclosing function's return type. Similarly, as shown in FigureB[BB B), our analysis extracts a predicate Object nbme,tname,timee firmerorward (Ts. T1, 72, T9) because тs is an object type whose name, time, and forward members are associated with type variables 71, 72, Tg, respectively.
In contrast to the Subtype and Object predicates that impose hard constraints on type variables, the next two hyperedges shown in Figure encode contextual clues obtained from variable names. Figure ()C) indicates that type variable
is associated with an expression named restore. While this kind of naming information is invisible to TypeScript's structural type system (?), serves useful input feature for our GNN architecture described in Section 4
In addition to storing the unique variable name associated with each type variable, the type depen- dency graph also encodes similarity between variable and class names. The names of many program variables mimic their types: for example, instances of a class called MyNetwork might often be called network or nerkor.1. To capture this correspondence, our type dependency graph also contains a hyperedge called NameSimilar that connects type variables a and /3 if their corresponding tokenized names have non-empty intersection
As shown in Table D there a final type of hyperedge called Usage that facilitates type inference of object types. In particular, if there an object access var y x.1, 1, extract the predicate Usage, ((T.,, Ty); (1),31),. B.),..., (ak, Bx)) to connect x and y's type variables with all classes o; that contain an attribute/method B, whose name is Figure 3 shows a Usage hyperedge extracted from the code in Figure 2 As we will see in the next section, our GNN architecture utilizes a special attention mechanism to pass information along these usage edges.
During tokenization, split identifier names into tokens hased on underscores and camel case naming. More complex schemes possible, but we found this simple method to he effective.
4

---

Published as a conference paper at ICLR 2020
4 NEURAL ARCHITECTURE
Our neural architecture for making type predictions consists of two main parts. First, a graph neural network passes information along the type dependency graph to produce vector-valued embedding for each type variable based its neighbors. Second, pointer network compares each variable's type embedding to the embedding vectors of candidate types (both computed from the previous phase) to place distribution over possible type assignments.
Given a type dependency graph 9 = (N, E), we first to compute a vector embedding v,, for cach N such that these vectors implicitly encode type information. Because our program abstraction is a graph, a natural choice is to use a graph neural network architecture. From a high level, this architecture takes in initial vectors vn, for each node n, performs K rounds of message-passing in the graph neural network, and returns the final representation for each type variable.
In more detail, let v,, denote the vector representation of node at the /th step, where each round consists of message passing and an aggregation step. The message passing step computes a vector- valued update send to the jth argument of each hyper-edge e E E' connecting nodes P...... ......a.... Pa-
Then, once all the messages have been computed, the aggregation step computes new embedding vi, for each n by combining all messages sent to Y2:
m eP
Msgg., (v v
v = Aggr(v (v 1-1 (m'i. E (n)))
Here, .' is the neighborhood function, and Msg. denotes a particular neural operation that depends on the type of the edge (FIXED, NARY, NPAIRS), which we will describe later.
Initialization. In our GNN, nodes correspond to type variables and each type variable is associ- ated either with program variable or a constant. We refer to nodes representing constants (resp. variables) as constant (resp. variable) nodes, and our initialization procedure works differently de- pending whether or not set the initial embedding for each constant node of type T (e.g. string) to be a trainable vector C, and do not update it during GNN iterations (i.e., Vt, vf. C,). On the other hand, if is a variable node, then we have no information about its type during initialization; hence, we initialize all variable nodes using generic trainable initial vector (i.e., they are initialized to the same vector but updated to different values during GNN iterations).
constant node. Since the types of each constant are known, we
Message passing. Our Msg operator depends on the category of edge it corresponds to (see Ta- ble I however, weights are shared between all instances of the same hyperedge type. In what follows, we describe the neural layer that is used to compute messages for each type of hyperedge:
Since these edges correspond to fixed arity predicates (and the position of each argument matters). we compute the message of the jth argument by first concatenating the embedding vector of all arguments and then feed the result vector to 2-layer MLP for the jth argument. In addition, since hyperedges of type Access have an identifier, we also embed the identifier as a vector and treat it as an extra argument. (We describe the details of identifier embedding later in this section.)
FIXED:
Since NARY edges connect variable number of nodes, we need an architecture that can deal with this challenge. In our current implementation of LAMBDANET, we use a simple archi- tecture that is amenable batching. Specifically, given an NARY edge Eig..... (a, Bi,..... 3x) (for Function and Call, the labels 1, are argument positions), the set of messages for a is computed as {MLP& a (vi, ([v,,)
NARY:
1....A }., and the message for each 8, computed as MLP (Vi, va Observe that we compute & different messages for a, and the message for each 33 only depends on the vector embedding of and its position j. but not the vector embeddings of other B
NPAIRS:
This is special category associated with Usa"e,((a", ((**, (a,,B1,,.... BI)...., (ak, Bx)). Re- call that this kind of edge arises from expressions of the form b b= a.l and is used to connect a and b's type variables with all classes o; that contain attribute/method 33 with label l. Intuitively, if a's type embedding is very similar to type C, then b's type will likely be the same as C.I's type. Following this reasoning, use dot-product based attention compute the messages for a and 3r. Specifically, we use a" and aj 's as attention keys and By 's as attention values to compute the
In our current implementation, this is reducible to multiple FIXED edges. However, NARY edges could generally use more complex pooling over their arguments send more sophisticated messages.
5

---

Published as a conference paper at ICLR 2020
message for 3 (and switch the key-value roles to compute the message for a
m
Σ wyy 1 6
w softmax(a)
aj = Vay Vo*
Aggregation. Recall that the aggregation step combines all messages sent to node n to compute the new embedding of To achieve this goal, operator proposed in graph attention networks (Veličković et al. 2018).
variant of the iicettin-bbssee aggregation
0 = Aggr( (mminle ((m))) = v. +
Σ (EN(m)
W. w.M.mi..
(1)
where we is the attention weight for the message coming from edge e. Specifically, the weights we are computed as softmax(a)) (a), where a LeakyReLu(v -Mmm and M1 and M2 trainable matrices. Similar to the original GAT architecture, we set the slope of the LeakyReLu to be 0.2, but
dot-proe dot-product compute the attention weights instead of linear model.
Identifier embedding. Like in Allamanis et al. (2017). we break variable names into word tokens according camel case and underscore rules and assign trainable vector for all word tokens that appear more than once in the training set. For all other tokens, unlike Allamanis et al. (017)) which maps them all into one single <Ünknown> token, we randomly mapped them into one of the <Unknown- i> tokens, where ranges from 0 to 50 in our current implementation. This mapping is randomly constructed every time we run the GNN and hence helps our neural networks distinguish different tokens even if they are rare tokens. We train these identifier embeddings end-to-end along with the rest of our architecture.
Prediction Layer. For each type variable and each candidate type E V(gg), we use a MLP compute a compatibility score Sn,c .MM((v,, (v,,, uz), where u, the embedding vector for c. If Vibb. V. is trainable vector for each library type if e E (g) then it corresponds to a node ne the type dependency graph of g, so we just use the embedding vector for ne and set u Vnn. Formally, this approach looks like a pointer network (Vinyals et al. 2015), where use the embeddings computed during the forward pass to predict "pointers" to those types.
Given these compatibility scores, we apply softmax layer to turn them into a probability distribu- tion. i..,, (clg) exp(sn.e)) Ee exp(sn.c'). During test time, we max over the probabilities to compute the most likely (or top-N) type assignments.
5 EVALUATION
In this section, we describe the results of our experimental evaluation, which is designed to answer the following questions: (I) How does our approach compare to previous work? (2) How well can model predict user-defined types? (3) How useful is each of our model's components?
Dataset. Similar to Hellendoorn et al. (0018) we train and evaluate our model on popular open- source TypeScript projects taken from Github. Specifically, we collect 300 popular TypeScript projects from Github that contain between 500 to 10, 000 lines of code and where at least 10% of type annotations are user-defined types. Note that each project typically contains hundreds to thousands of type variables to predict, and these projects in total contain about 1.2 million lines of TypeScript code. Among these 300 projects, use 60 for testing, 40 for validation, and the remainder for training.
3 Code Duplication. We ran jscpe on our entire data and found that only 2.7% of the code is duplicated. Furthermore, most of these duplicates are intra-project. Thus, we believe that code duplication is not severe problem our dataset.
Preprocessing. Because some of the projects in our benchmark suite are only sparsely type an- notated, we augment our labeled training data by using the forward type inference functionality provided by the TypeScript compiler!") The compiler cannot infer the type of every variable and leaves many labeled as any during failed inference; thus, we exclude any labels in our data set.
popular code duplication detection tool, available athttps: http//ttttuuu.ee/e wwwp://wwwww.ccccccccccoooooo//e jscpd
'I LLike in many modern programming languages with forward type inference (e.g., Scala, C#. Swift), TypeScript programmer does not need annotate every definition in order fully specify the types of

---

Published as a conference paper at ICLR 2020
Furthermore, at test time, evaluate technique only annotations that manually added by developers. This is the same methodology used by [Heleendoom et al. (2018), and, since develop- often add annotations where code is most unclear, this constitutes challenging setting for type prediction.
Prediction Space. As mentioned in Section 2.1 our approach takes entire TypeScript project g as its input, and the corresponding type prediction space is (g)) = Vis U (g) In our ex- periments, we set (g)er(g) be all classes/interfaces defined in g (except when comparing with Deep'yyper where we set Vuser(g) to be empty), and for Vis. we select the top-100 most common types in our training set. Note that this covers 98% (resp. 97.5%) of the non-any annotations for the training (resp. test) set.
Hyperparameters We selected hyperparameters by tuning on a validation set as we were develop- ing our model. We use 32-dimensional type embedding vectors, and all MLP transformations in our model use one hidden layer of 32 units, except the MLP for computing scores in the prediction layer, which uses three hidden layers of sizes 32,16, and 8 (and size for output). GNN message-passing layers from different time steps have independent weights.
We train our model using Adam (Kingma & Ba 2014) with default parameters (a = 0.9, 3 = 0.999) and set the learning rate to be 10- initially but linearly decrease it to 10-1 until the 30th epoch. We use weight decay of 10 for regularization and stop the training once the loss on validation set starts to increase (which usually happens around 30 epochs). We use the type annotations from a single project as minibatch and limit the maximal batch size (via downsampling) to be the median of our training set to prevent any single project from having too much influence.
Implementation Details. We implemented LAMBDANET in Scala, building on top of the Java high-performance Tensor library Nd4j(nd4), and used a custom automatic differentiation library to implement our GNN. Our GNN implementation does not use an adjacency matrix to represent GNN layers; instead, we build the hyperedge connections directly from our type dependency graph and perform batching when computing the messages for all hyperedges of the same type.
Code Repository.
We have made our code publicly available on Github 5
5.1 COMPARISON WITH DEEPTYPER
In this experiment, we compare LAMBDANET's performance with DeepTTyper (Hellendoorn et al.) 2018), which treats programs as sequences of tokens and uses bidirectional RNN to make type pre- dictions. Since Deep'Typer can only predict types from a fixed vocabulary, we fix both LAMBDANE: NET and DeepTyper's prediction space to Vibb and measure their corresponding top-1 accuracy.
The original DeepTyper model makes predictions for each variable occurrence rather than decla- ration. In order to conduct meaningful comparison between DeepTyper and LAMBDANET, we implemented a variant of Deep'Typer that makes a single prediction for each variable (by averaging over the RNN internal states of all occurrences of the same variable before making the prediction). Moreover, for fair comparison, we made sure both Deep'Typer and LAMBDANET are using the same improved naming feature that splits words into tokens.
Our main results are summarized below, where the Declaration (resp. Occurrence) column shows ac- curacy per variable declaration (resp. token-level occurrence). Note that obtain occurrence-level accuracy from declaration-Ieve accuracy by weighting each variable by its number of occurrences.
Model
Topl Accuracy (%) Declaration Occurrence
DeepTyper LAMBDANETHa (K=6)
61.5 75.6
67.4
77.0
program. Instead, they only need annotate some key places (e.g.. function parameters and return types, class members) and let the forward inference algorithm figure the rest of the types. Therefore, in our training set, we can keep the user annotations on these key places and run the TS compiler to recover these implicitly specified types as additional labels.
"ee wttptttt/////ttt http://tthuuu.coo///////////a//a http://wwww..eeeee/aaaaaeeeeeee

---

Published as a conference paper at ICLR 2020
Table 2: Accuracy when predicting all types.
Model
Topl
Accuracy (%)
Top5 Accuracy (%)
Vuser
Vib
Overall
Vuser
Vib
Overall
TS COMPILER
2.66
14.39
8.98
SIMILARNAME
24.1
0.78
15.7
42.5
3.19
28.4
LAMBDANET (K=6)
53.4
66.9
64.2
77.7
86.2
84.5
Table 3: Performance of different GNN iterations (left) and ablations (right).
K
Top1 Accuracy (%)
Ablation
Top1 Accuracy (%)
Vuser
Vib
Overall
(K 4)
y Vuser
Vibb
Overall
53.4
66.9
64.2
LAMBDANET
48.4
65.5
62.0
48.4
65.5
62.0
No Attention in NPAIR
44.1
57.6
54.9
47.3
61.7
58.8
No Contextual
27.2
52.6
47.5
16.8
48.2
41.9
No Logical"
24.7
39.2
36.2
0.0
17.0
13.6
Simple Aggregation
40.2
66.9
61.5
Training was unstable and experienced gradient explosion.
As we can see from the table, LAMBDANET achieves significantly better results compared to Deep- Typer. In particular, LAMBDANET outperforms DeepTyper by 14.1% (absolute) for declaration- level accuracy and by 9.6 9.6% for occurrence-level accuracy.
Note that the accuracy report for Deer (67.4%) is not directly comparable the original accuracy reported in Hellendoorn et al. (2018) 8) (56.9%) for the following reasons. While we perform static analysis and have strict distinction of library vs. user-defined types and only evaluate both tools on library type annotations in this experiment, their implementation treat types as tokens and does have this distinctions. Hence, their model also considers much larger prediction space consisting of many user-defined types most of which are never used outside of the project in which they are defined and is also evaluated on different of annotations than ours.
5.2 PREDICTING
TYPES
As mentioned earlier, approach differs from prior work in that it is capable of predicting user- defined types; thus, in our second experiment, we extend LAMBDANET'S prediction space to also include user-defined types. However, since such types not in the prediction space of prior work (Hellendoorn et al. 2018), we implemented two simpler baselines that can be used to cali- brate our model's performance. Our first baseline is the type inference performed by the TypeScript compiler, which is sound but incomplete (i.e., if it infers a type. it is guaranteed to be correct, but infers type any for most variables) [ Our second baseline, called SIMILARNAME, is inspired by the similarity between variable names and their corresponding types; it predicts the type of each variable be the type whose name shares the most number of common word tokens with v.
The results of this experiment are shown in Table 2 which shows the top-1 and top-5 accuracy for both user-defined and library types individually as well as overall accuracy. terms of overall prediction accuracy. LAMBDANET achieves 64.2% for top-1 and 84.5% for top-5, significantly out- performing both baselines. Our results suggest that our fusion of logical and contextual information to predict types is far more effective than rule-based incorporation of these in isolation.
5.3 ABLATION STUDY
Table 3 shows the results of an ablation study in which (a) we vary the number of message-passing iterations (left) and (b) disable various features of our architecture design (right). As we can see from the left table, accuracy continues to improve as we increase the number of message passing iterations as high as 6; this gain indicates that our network learns to perform inference over long distances. The right table shows the impact of several of our design choices on the overall result.
'For inferring types from the TypeSeript compiler, the code provided by Hellendoom al. 2018 We found this method had slightly lower accuracy than reported their work.
8

---

Published as a conference paper at ICLR 2020
For example, if do not use Contextual edges (resp. Logical edges), overall accuracy drops by 14.5% (resp. 25.8%). These drops indicate that both kinds of predicates are crucial for achieving good accuracy. We also that the attention layer for NPAIR makes significant difference for both library and user-defined types. Finally, Simple Aggregation is a variant of LAMBDANET that uses simpler aggregation operation which replaces the attention-based weighed sum in Eq | with a simple average. As indicated by the last row of Table attention- aggregation makes a substantial difference for user-defined types.
5.4 COMPARISON WITH JSNICE
Since JSNice (Raychev et al. 2015) cannot properly handle class definitions and user-defined types, for meaningful comparison, we compared both tools' performance on top-level functions randomly sampled from our test set. We filtered out functions whose parameters are not library types and man- ually ensured that all all the dependency definitions are also included. In this way, we constructed small benchmark suite consisting of 41 functions. Among the 107 function parameter and return type annotations, LAMBDANET correctly predicted 77 of them, while JSNice only got 48 of them right. These results suggest that LAMBDANET outperforms JSNice, even when evaluated only the places where JSNice is applicable.
RELATED WORK
Type Inference using Statistical Methods. There are several previous works on predicting likely type annotations for dynamically typed languages: |aaychev et al. (2015) and Xu et al., (2016) use structured inference models for Javascript and Python, but their approaches do not take advantage of deep learning and are limited to very restricted prediction space. Hellendoorn et al. (2018)
and Jangda & Anand| (219)) model programs as sequences and AST trees and apply deep learning models (RRNs and Tree- Tree-RNNs) for TypeScript and Python programs. Malik et al. (2019) make use of a different source of information and take documentation strings as part of their input. However, all these previous works are limited predicting types from fixed vocabulary.
Graph Embedding of Programs. Allamanis et al. (017) are the first to use GNNs to obtain deep embedding of programs, but they focus predicting variable names and misuses for CF and rely on static type information to construct the program graph. Wang et al. (0117) use GNNs to encode mathematical formulas for premise selection in automated theorem proving. The way we encode types has some similarity to how they encode quantified formulas, but while their focus is on higher- order formulas, our problem requires encoding object types. Veličković et al. (2018) are the first to use an attention mechanism in GNNs. While they use attention to compute node embeddings from messages, we use attention to compute certain messages from node embeddings.
Predicting from an Open Vocabulary. Predicting unseen labels at test time poses challenge for traditional machine learning methods. For computer vision applications, solutions might involve looking object attributes (Farhadi et al. 2017) or label similarity WWng et al. (2018); for natu- ral language, similar techniques are applied to generalize across semantic properties of utterances (Duphhin et al. 2013), entities (Eshel et al. 2017), or labels (Ren al., 2016). Formally, most of these approaches compare an embedding of an imput to some embedding of the label; what makes our approach a pointer network (Vinyals et al. 2015) is that our type encodings are derived during the forward pass on the input, similar to unknown words for machine translation (Gulcehre et al, 2016).
7 CONCLUSIONS
We have presented LAMBDANET, neural architecture for type inference that combines the strength of explicit program analysis with graph neural networks. LAMBDANET not only outperforms other state-of-the-a -frt tools when predicting library types, but can also effectively predict user-defined types that have not been encountered during training. Our ablation studies demonstrate the usefulness of proposed logical and contextual hyperedges.
For future work, there are several potential improvements and extensions to our current system. One limitation of our current architecture is the simplified treatment of function types and generic types

---

Published as a conference paper at ICLR 2020
(i.e., collapsing them into their non-generic counterparts). Extending the prediction space to also include structured types would allow us to make full use the rich type systems many modern languages such TypeScript provide. Another important direction is to enforce hard constraints during inference such that the resulting type assignments are guaranteed to be consistent.
ACKNOWLEDGMENTS
We would like to thank Deep'Typer authors, Vincent J. Hellendoorn, Christian Bird, Earl T. Barr, and Miltiadis Allamanis, for sharing their data and helping us set up our experimental compar- isons. We also thank the ICLR reviewers for their insightful comments and constructive suggestions. Finally, we would also like to thank Shankara Pailoor, Yuepeng Wang. Jocelyn Chen, and other UToPiA group members for their kind support and useful feedback. This project was supported in part by NSF grant CCF-1762299.
REFERENCES
Deeplearning4j.
Accessed: 2019-
09-24.
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning represent programs with graphs. ICLR, 2017.
Davide Ancona and Elena Zucca. Principal typings for java-like languages. In ACM SIGPLAN Notices, volume 39, pp. 306-317. ACM, 2004.
Gavin Bierman, Martín Abadi, and Mads Torgersen. Understanding typescript. In Richard Jones (ed.), ECOOP 2014 Object-Orient Oriented Programming, pp. 257-281, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. ISBN 978-3-662-44202-9
Benjamin Chung, Paley Li. Francesco Zappa Nardelli, and Jan Vitek. Kafka: Gradual typing for objects. In ECOOP 2018-2018 European Conference on Object-Oriented Programming, 2018.
Yann Dauphin, Gokhan Tur, Dilck Z. Hakkani-Tun -ur,, and Larry P. Heck. Zero-shot learning for semantic utterance classification. ICLR, 2013.
Yotam Eshel, Noam Cohen, Kira Radinsky, Shaul Markovitch, Iuya Yamada, and Omer Levy. Named entity disambiguation for noisy text. In CoNLJ, 2017.
Ali Farhadi, Ian Endres. Derek Hoiem, and David Forsyth. Describing objects by their attributes. In CVPR, 2017.
Zheng Gao, Christian Bird, and Earl T. Barr. To type not type: Quantifying detectable bugs in javascript. In Proceedings of the 39th International Conference on Software Engineering, ICSE 17, pp. 758-769, Piscataway, NJ, USA, 2017. IEEE Press. ISBN 777-1-5338--868-1
doi:
10. N0.1109/CSSE.2017.5.. URL https: /oo i or orrg /10 11..11110 1109 ICSE. 2017.75
Caglar Gulcehre, Sungjin Ahn, Ramesh Nallapati, Bowen Zhou, and Yoshua Bengio. Pointing the unknown words. Proceedings of the ACL, 2016.
Stefan Hanenberg, Sebastian Kleinschmager, Romain Robbes, Éric Tanter, and Andreas Stefik. An empirical study on the impact of static typing on software maintainability. Empirical Software Engineering, 19:1335-132 1382, 2013.
Vincent Hellendoom, Christian Bird, Earl T. Barr, and Miltiadis Allamanis. Deep learning type inference. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium the Foundations of Software Engineering, ESEC/FSE 2018. pp. 152-1622, New York, NY, USA, 2018. ACM. ISBN 4503-5533-----33--55 doi: 10. 10.1145/3236024, 3236051. URL http:tttttddee. acm. org /10 1005/..114333366 3236051
Abhinav Jangda and Gaurav Anand. Predicting variable types in dynamically typed programming languages. arXiv preprint arXiv: arXiv:1901.088 05588, 2019.
10

---

Published as a conference paper at ICLR 2020
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2014.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. ICLR, 11s/15111.549,, 2016.
Rabee Sohail Malik, Jibesh Patra, and Michael Pradel. N12type: inferring javascript function types from natural language information. Proceedings of the 4/st International Conference on Soft- ware Engineering, pp.
IEEE Press, 2019.
Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. Convolutional neural networks tree structures for programming language processing. In AAAI, volume 2, pp. 4, 2016.
Benjamin C Pierce and David N Turner. Local type inference. ACM Transactions on P Programming
Languages and Systems (TOPLAS); 22(1):1-44, 2000.
Veselin Raychev, Martin Vechev, and Andreas Krause. Predicting program properties from "big code". In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Progrumming Languages, POPL '1, pp. 111-124, New York, NY, USA, 2015. ACM.
Xiang Ren, Wenqi He, Meng Qu, Clare R Voss, Heng Ji, and Jiawei Han. Label noise reduction in entity typing by heterogeneous partial-label embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1825-1834. ACM, 2016.
Jeremy G. Siek and Walid Taha. Gradual typing for objects. In ECOOP, 2007.
Dmitriy Traytel, Stefan Berghofer, and Tobias Nipkow. Extending hindley-milner type inference with coercive structural subtyping. In Asian Symposium on Programming Languages and Systems, pp. 89-104. Springer, 2011.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. accepted as poster.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NeurlPS, 2015.
Michael M Vitousek, Andrew M Kent, Jeremy G Siek, and Jim Baker. Design and evaluation of gradual typing for python. In ACM SIGPLAN Notices, volume 50, pp. 45-56. ACM, 2014.
Mingzhe Wang, Yihe Tang, Jian Wang, and Jia Deng. Premise selection for theorem proving by deep graph embedding. In Advances in Neural Information Processing Systems, pp. 9786-27960 2017.
Xiaolong Wang, Yufei Ye, and Abhinav Gupta. Zero-shot recognition via semantic embeddings and knowledge graphs. In CVPR, 2018.
Zhaogui Xu, Xiangyu Zhang, Lin Chen, Kexin Pei, and Baowen Xu. Python probabilistic type infer- ence with natural language support. In Proceedings of the 2016 24th ACM SIGSOFT Internationl Symposium on Foundations of Software Engineering, pp. 607-618. ACM, 2016.


Reviews:
[{"review_id": "Sklm0w_6tr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed to use Graph Neural Networks (GNN) to do type inference for dynamically typed languages. The key technique is to construct a type dependency graph and infer the type on top of it. The type dependency graph contains edges specifying hard constraints derived from the static analysis, as well as soft relationships specified by humans. Experiments on type predictions for TypeScript have shown better performance than the previous methods, with or without user specified types. \n\nOverall this paper tackles a nice application of GNN, which is the type prediction problem that utilizes structural information of the code. Also the proposed type dependency graph seems interesting to me. Also the pointer mechanism used for predicting user specified types is a good strategy that advances the previous method. However, I have several concerns below:\n\nAbout formulation:\n1) I’m not sure if the predicted types for individual variable would be very helpful in general. Since the work only cares about individual predictions while no global consistency is enforced, it is somewhat limited. For example, in order to (partially) compile a program, does it require all the variable types to be correct in that part? If so, then the predicted types here might not be that helpful. I’m not sure about this, so any discussion would be appreciated. \n\n\nAbout type dependency graph:\n1) Comparing to previous work (e.g, Allamanis et.al, ICLR 18), it seems the construction of the task specific graph is the major contribution, where the novelty is a bit limited. \n2) The construction of the dependency graph is heuristic. For example, why the three contextual constraints are good? Would there be other good ones? Also why only include such limited set of logical constraints. For example, would expression like (x + y) induce some interesting relationships? Because such hand-crafted graph is lossy (unlike raw source code), all the questions here lead to the concern of such design choices. \n3) The usage of graph is somewhat straightforward to me. For example, although the hard-constraints are there, there’s no such constraints reflected in the prediction. Adding the constraints on the predictions would be more interesting. \n\nAbout experiments:\n1) I think one ablation study I’m most interested in is to simply run GNN on the AST (or simply use Allamanis et.al’s method). This is to verify and support the usage of proposed type dependency graph. \n2) As the authors claimed in Introduction, ‘plenty of training data is available’. However in experiment only 300 projects are involved. Also it seems that these are not fully annotated, and the ‘forward type inference functionality from TypeScript’ is required to obtain labels. It would be good to explain such discrepancy. \n3) Continue with 2), as the experiment results shown in Table 2, TS compiler performs poorly. So how would it be possible to train with poor annotations, while generalize much better? Some explanations would be helpful here.\n4) I think only predicting non-polymorphic types is another limitation. Would it be possible to predict structured types? like nested list, or function types with arguments? \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "ByxVe3vnOS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a GNN-based method for predicting type annotations in JavaScript and TypeScript code. By constructing a \"type dependency graph\" that encodes the relationships among variables and appropriately modifying GNNs to the hypergraph setting, the authors show that the good performance improvements can be made.\n\nOverall, this paper is well-written, the experiments are quite convincing and the methods are reasonable and interesting. I believe that there are a few things that need to be clarified within the evaluation, but I would argue that this paper should be accepted.\n\n* It is unclear to me what is the scope of the type dependency graph construction. Is it a whole file? Is it a single function/class? A whole project? \n\n* The DeepTyper paper seems to suggest that it predicts type annotations one function at a time. Does the comparison (in 5.1) use the same granularity as LambdaNet? If for example, LambdaNet looks at whole files, then the comparison is not exact. Could you please clarify? Performing the comparison on equal-sized samples would make sense.\n\n* If my reading of DeepTyper is correct, it processes all identifiers as a single unit. In contrast, this work (correctly, in my opinion), breaks the identifiers into \"word tokens\". This may be an important difference between the two methods. To test this, an ablation where LambdaNet does *not* split the identifiers, would provide a better comparison among the sequential representation of DeepTyper and the type constraint graph of LambdaNet.\n\n* Some comparison with JSNice is missing (Raychev et al. 2015). The DeepTyper paper suggests that the two approaches are somewhat complementary. It would be useful to know how LambdaNet compares to JSNice too.\n\n* There is some literature that suggests that code duplication exists in automatically scraped corpora and that it hurts the evaluation of machine learning models [a,b]. At the very least, the authors should report the percent of duplicates (if any) in their corpus. Another option would be to _not_ evaluate predictions in any duplicated file.\n\n## Secondary question:\n\n* I do not understand why a separate edge is needed for Subtype() and Assign(). Isn't Assign (a,b) == Subype(a,b)?\n\n* The authors correctly exclude the `any` annotations produced by the TypeScript compiler. Do they also exclude any other annotations? For example, functions that do not return a value (i.e. their return value is `void`) would also need to be excluded. What about `object`?\n\n* I would encourage the authors to make the dataset (source code and extracted graphs), and the LambdaNet code public upon acceptance.\n\n## Minor\n\n* Please capitalize GitHub, TypeScript, etc throughout the paper?\n\n* Sec 4: \"we first to compute\" -> \"we first compute\"\n\n\n\n[a] Lopes, Cristina V., et al. \"DéjàVu: a map of code duplicates on GitHub.\" Proceedings of the ACM on Programming Languages 1.OOPSLA (2017): 84.\n[b] Allamanis, Miltiadis. \"The Adverse Effects of Code Duplication in Machine Learning Models of Code.\" arXiv preprint arXiv:1812.06469 (2018).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BJgF7g7jFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "= Summary\nA method to predict likely type of program variables in TypeScript is presented. It consists of a translation of a program's type constraints and defined objects into a (hyper)graph, and a specialised neural message passing architecture to learn from the generated graphs. Experiments show that the method substantially outperforms sound typing in the TypeScript compiler, as well as a recent method based on deep neural networks.\n\n= Strong/Weak Points\n+ The graph representation of the problem is novel, and draws both on core ideas from Hindley-Milner typing (in the subtyping/assignment graph bits) as well as neural ideas (in name similiarity)\n+ The neural message passing architecture is adapted to the problem, handling features not present in the standard GNN literature (hyperedges, ...)\n+ Experiments compare with relevant baselines and consider interesting ablations, studying the effect of the GNN extensions in detail.\n- The hyperparameter selection regime (and the experiments used to find them) is not described\n\n= Recommendation\nThis is an application-driven paper with nice practical results. The fact that standard neural architectures are extended and adapted to the task, and the way domain knowledge is used to design the graph representation makes this interesting even to people outside the task-specific audience, and hence I strongly recommend acceptance.\n\n= Minor Comments\n- page 2: \"network's type to be class\" -> \"to be a class\"\n- Evaluation Datasets: Did you take duplication in the crawled datasets into account? (Lopes et al. 2017 (DéjàVu: a map of code duplicates on GitHub) suggests that this is particularly problematic for JavaScript/TypeScript)\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an approach to type inference in dynamically typed languages using graph neural networks. The reviewers (and the area chair) love this novel and useful application of GNNs to a practical problem, the presentation, the results. Clear accept.
Decision: Accept (Poster)