Exploiting Type Hints in Method Argument Names to Improve Lightweight Type Inference Nevena Milojković, Mohammad Ghafari, Oscar Nierstrasz To cite this version: Nevena Milojković, Mohammad Ghafari, Oscar Nierstrasz. Exploiting Type Hints in Method Argu- ment Names to Improve Lightweight Type Inference. International Conference on Program Compre- hension, May 2017, Buenos Aires, Argentina. ￿hal-01519632￿ HAL Id: hal-01519632 https://hal.inria.fr/hal-01519632 Submitted on 8 May 2017 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. Exploiting Type Hints in Method Argument Names to Improve Lightweight Type Inference Nevena Milojkovic´, Mohammad Ghafari, Oscar Nierstrasz Software Composition Group, University of Bern Bern, Switzerland {nevena, ghafari}@inf.unibe.ch scg.unibe.ch Abstract—The lack of static type information is one of the Simpleapproaches,intendedtobeusedbythedeveloperfor main obstacles to program comprehension in dynamically-typed comprehension purposes, usually analyse variable usage only languages. While static type inference algorithms try to remedy within its scope of availability, thus they are intraprocedural, this problem, they usually suffer from the problem of false and not interprocedural [17]. The problem with such algo- positives or false negatives. rithms is that they suffer from false positives, i.e., classes that In order to partially compensate for the lack of static type information, a common practice in dynamically-typed languages understand the interface of the variable, but do not represent istonameorannotatemethodargumentsinsuchawaythatthey its run-time type. Hence, they over-approximate the results. reveal their expected type, e.g., aString, anInt, or string: String. Otherapproachestrytomodelsoftwareexecution,thusthey Recent studies confirmed that these type annotations are indeed are sensitive to either control flow or data flow or both [13]. frequently used by developers in dynamically-typed languages. In any case, even these more complex static analyses tend We propose a lightweight heuristic that uses these hints from methodargumentnamestoaugmenttheperformanceofastatic to produce faulty results [20]. In the presence of reflection, type inference algorithm. The evaluation through a proof-of- ordynamicclassloading,thesealgorithmsunder-approximate concept prototype implemented in Pharo Smalltalk shows that the set of possible types for a variable, rather than over- the augmented algorithm outperforms the basic algorithm, and approximating them [20]. This causes certain types to be correctly infers types for 81% more method arguments. missed, thus introducing the problem of false negatives, i.e., Keywords-type-inference,dynamically-typedlanguages,heuris- theclassesthatarenotinferredaspossibletypesforavariable, tic, type hints yet represent the variable type at run time. A recent study showed that developers in dynamically-typed languages often I. INTRODUCTION use dynamic and reflective features [21], [22], [23], [24], as While dynamically-typed languages offer a more flexible well as in statically-typed languages [25]. For instance, a way to write source code [1] and allow developers to be more reflective method invocation is used in more than 60% of the expressive [2], [3], it is unquestionable that they pose cer- analysed projects, and for almost all of them it is not possible tain difficulties for program comprehension [4]. Even though todiscovertheactualmethodbeinginvokedonlyusingsimple developing in dynamically-typed languages cuts in half the static analyses [24]. time needed to write the code [5], static type information In our experience, many developer communities strongly has proven to be of crucial importance to developers during adheretocertainnamingconventions.Forexample,acommon software maintenance [6]. This is even of greater significance idiom in dynamically-typed languages is to name method when we bear in mind that around 70% of the software life arguments (i.e., formal parameters to methods) after their cycleisspentonsoftwaremaintenance[7].Whileworkingina expectedtype[26],[27],[28].Typehintsinmethodarguments dynamically-typed environment, developers spendmost of the have a positive impact on program comprehension [9]. This time on reasoning about software and making a mental model is mainly intended to support the developer’s reasoning about of software behaviour [8]. Static type information constitutes the variable, but it is also used by some development tools, the core needed by the developer to understand the control e.g., code completion [29]. The usage of identifier names has flowofthesystem[4].Alreadypuretypeinformationwithout beenexploredtosuggestanewidentifiername[30],[31],and static type checking has a significant impact on developer’s study differences and similarities between method parameter productivity [9]. and method argument names [32]. A recent study revealed Type inference has been of research interest for the last that this naming pattern is not strictly followed, but it may be several decades [10], [11], [12], [13], [14], [15], [16], [17], successfully upgraded with simple heuristics for about a half [18], [19]. Some approaches rely purely on static informa- of the explored method arguments [33], [34], [35]. tion [10], [13], [11], [17], while others exploit information Webelievethatthesehintscanbeofcrucialimportancefor collected during software execution [12], [14], [18]. However, type inference in cases where the type of the variable cannot in order to collect run-time information, a fully (and usually be statically inferred by traditional approaches. We propose a instrumented) running program must be available [18]. heuristic that combines an existing type inference algorithm Preprint* with type hints from method argument names. Even though classThreePhaseButtonMorph.Thisclassisapartofthe thesehintsmaybeusedbyanytraditionaltypeinferencealgo- packageMorphic,aUserInterfaceconstructionkit[40]used rithm, we chose the Cartesian Product Algorithm (CPA) [13], for graphical representations in Pharo Smalltalk. Morphic is which aims to precisely infer types for method arguments. based on the idea that each object (a graphical component) is CPA is a traditional type inference algorithm that was used detachablefromitsparent,andcanbemanipulatedonitsown. as the base approach for several other algorithms [36], [37]. The class PluggableThreePhaseButtonMorph allows We employ an extension of the algorithm that is proposed by the construction of a button that has three different images: Spasojevic´ et al. [33] in order to obtain the type information one image for when the button is in on state, another when it from type hints in method argument names. isinoff stateandthethirdforwhenthebuttonisjustpressed. We have implemented a proof-of-concept prototype in Let us imagine that the developer wants to understand the Pharo,1 which is a dialect of Smalltalk [38], a highly reflec- control flow of the class, and how to manipulate one such tive dynamically-typed language that enables fast and easy morph. This class has a field named pressedImage (line implementation of analysis tools [39]. We have used this 3 in Listing 1). In order to understand the implementation of prototypetoevaluateourhypothesis.ForCPA,whichdepends a button, the developer wants to statically infer types of the on the control flow analysis, this heuristic showed significant expressions in the class. Since she does not want an over- improvementinthenumberofmethodargumentsforwhichwe approximation of the possible types, she decides to use the were able to correctly infer types, as compared with the types CPA. It tracks the control flow of the code and the flow of recorded at run time. In particular, the combination of CPA typesfromoneexpressiontoanother,andpropagatesthetypes with type hints from method argument names, which we call throughconnectionsbetweenexpressions.CPAneedsanentry CPA∗, is able to increase the size of the correct call graph by point — a main method — and for that purpose one of the 30%,toanalyse52%moremethodarguments,andtocorrectly factory methods can be used. These methods are defined on infer types of up to 81% more of the method arguments. the class side of a class. Since everything in Smalltalk is Structure of the Paper. First we motivate our approach considered to be an object, classes are objects, too. Thus the in section II. We present the traditional algorithm that we class side of a class defines methods that may be invoked on used for the evaluation, and we explain the proposed heuristic the class object. Pharo Smalltalk does not force a developer in the section III. We explain our prototype implementation to write and use a main method in order to start a program in section IV. Next we evaluate the approach in section V. execution.Anymethodintheprojectmaybeusedasanentry We discuss possible threats to validity in section VI, before point.TheusualpracticeinSmalltalkincludesusingclassside we present the related work in section VII and conclude methods as main methods. in section VIII. This factory method will first create an instance of the class PluggableThreePhaseButtonMorph, thus CPA II. MOTIVATION will infer the type of this construction call to be of that While type hints in identifiers are used in dynamically- class. The field pressedImage is not defined during object typed languages, they are mostly intended to support human creation in the constructor, thus its value will be null at the reasoning about the software at hand [29], [9]. On the other beginning of the analysis. hand, traditional type inference algorithms usually depend class PluggableThreePhaseButtonMorph{ 7 only on the analysis of language constructs, rather than on method updatePressedImage(){ 8 naming conventions. However, in the situations where the use this.setPressedImage( 9 ofreflectionisinvolved,thesealgorithmslacktheinformation10 target.perform(pressedImageSelector)); } needed to infer types [20]. In the continuation of this section,11 } we emphasise the advantage of type hints for type inference12 through a real code example taken from Smalltalk,2 however Listing2. Anexamplewherestaticanalysiscannotdeterminethetypeofa methodargument. for the sake of generalisability of our discussion we present CPA will continue to analyse the control flow, and, this example in pseudo-code. concurrently, to infer the types of the expressions. class PluggableThreePhaseButtonMorph During its evaluation, CPA will encounter the method 1 extends ThreePhaseButtonMorph{ 2 named updatePressedImage() in the class var pressedImage; 3 PluggableThreePhaseButtonMorph, presented var target; 4 in Listing 2. This method has one line of code, and it var pressedImageSelector; 5 } invokes the setter method for the field pressedImage 6 (line 9 in Listing 2). The supposed value of the field Listing1. Asubclassdefinitionwiththreefields. pressedImageisthereturnvalueofthemethodinvocation Consider lines 1-6 in Listing 1 that define a class named target.perform(pressedImageSelector). Both PluggableThreePhaseButtonMorph,asubclassofthe target and pressedImageSelector are also fields of the class. 1http://www.pharo.org The code perform(var) is a reflective way to in- 2http://www.smalltalkhub.com/#!/~Pharo/Pharo60/packages/ Morphic-Widgets-Basic voke a method on the target object with the method name supplied as an argument to perform(var). In this case fromwhichtheexampleistaken,willrevealthattheexpected a method with the name equal to the value of the vari- type of the argument is represented by the class Form. It able pressedImageSelector is invoked on the variable is an object used for holding images. Thus, with this small target. Let us suppose that CPA was able to determine improvement, the analysis is able to assign the Form class to that the type of the variable pressedImageSelector is the set of possible types for the field pressedImage, and String. String is the expected type of the argument of the to continue the analysis with this information. method perform(var). However, even if CPA knows the Asaresult,thedeveloperwillbeissuedwiththeinformation type of pressedImageSelector, it does not know its that the field pressedImage can have the class Form actual value. Thus, the analysis is not able to compute which as its type. The actual type of the variable at run time is method will be invoked on the variable target. Recent ColorForm, which is a subclass of Form. However, this studies revealed that invoking a method in this manner is is a common situation in object-oriented languages, due to a quite common in Smalltalk code [24], as well as in other heavy use of polymorphism [41]. dynamically-typed languages [21], [23] and for almost all of Wearguethatitispossibletointroduceaccurateinformation theoccurrences, itisnoteasy todeterminethe actualvalueof about the type of a variable with such a heuristic, and that the parameter statically. thiswillprovidemoreinsightfulinformationtodevelopersfor In this case two scenarios are possible: either to assign program comprehension. the type Object to the return value of the method invoca- tion target.perform(pressedImageSelector), or III. ALGORITHM to leave the set of inferred types for this expression empty. A. Cartesian Product Algorithm A usual practice in these situations is to under-approximate the results, in the case when the concrete value cannot be The Cartesian Product Algorithm is a type inference algo- determined by the analysis [20]. This means that the set of rithm developed by Agesen et al. [13]. It is implemented on possible types for the return value of the method invoca- topoftheBasicTypeInferenceAlgorithm[42]whichstatically tiontarget.perform(pressedImageSelector)will modelsthecontrolflowatruntime.Ithasbeendevelopedand be empty. Hence, in its next step, when the setter method implemented for Self [43], a prototype-based programming setPressedImage(var) (in the Listing 3) is entered, language. CPA will not know the type of its argument aForm. The The program under analysis is depicted as a graph whose method implementation consists of one line of code in which nodes represent program expressions, and directed edges por- themethodargumentisassignedtothefieldpressedImage trayrun-timetypeflow.Eachnodeholdsthetypeinformation, (line 15 in Listing 3). CPA works in such a way that it i.e., the set of classes, representing the possible types of propagates all the inferred types of the right-hand side of the evaluation of a corresponding expression. For example, an assignment to the variable on the left-hand side of the the node that represents a constructor call for the class assignment. Since it did not infer types for the argument OrderedCollection will hold as possible types the set named aForm, subsequently, it will not be able to infer with one element, namely the class OrderedCollection. the types of the field pressedImage. Closer investigation If there is an assignment x:=1 of value 1 to the variable of the class definition by the authors reveals that the field namedx,thenodeforthisvariablewillhaveaclassInteger pressedImage is only assigned through this setter method, as a possible type. Furthermore, if there is an assignment thus this loss of information will highly impact further analy- y:=x, the algorithm will propagate all the types from the sis. node representing variable x to the node representing variable y. Hence, the node for variable y will also hold the class class PluggableThreePhaseButtonMorph{ method setPressedImage(var aForm){ 13Integer as a possible type. 14 pressedImage := aForm; Thealgorithmintheoriginalpaper[13]isexplainedforthe 15 } 16Self language. Even though its implementation is language- } 17independent, we will follow Agesen’s terminology. Listing3. Thetypehintfromtheargumentnamecanhelptodetectthetypeof Let us denote by E the set of possible expressions in the themethodargumentandsubsequentlythetypeofthefieldpressedImage. project. As defined in Equation 1, it consists, respectively, We propose to exploit type hints in method argument of literals (the set of literals is denoted by L), variables namestohighlightwhichclassesareexpectedtorepresentthe (V), blocks (B), assignments, method invocations and return argument type(s) at run time. We argue that these hints may statements. A block is a lexical closure [44], [29], present in improve analysis precision. In the example in Listing 3 the many programming languages. name of the method argument is aForm. A Smalltalk idiom istoembedatypehintinmethodargumentname,i.e.,toprefix the name of the expected class with the undefined article. For E =L∪V ∪B∪ {v :=exp|v ∈V,exp∈E}∪ (1) example, if the expected type is String, the corresponding {xmsg:y|x,y ∈E}∪{ˆexp|exp∈E} argument name should be aString. TheanalysisofmethodargumentnamesembeddedinPharo The algorithm has three main steps: 1) create a node in the graph for each expression in the type of exp, the expression that constitutes the statement. program, e.g., variable named x, or an assignment x:=1 Block closure. A block is a lexical closure [44], [29], used 2) initially seed the types to the nodes for which the type to postpone the execution of the enclosing expressions. A can be determined before the analysis starts, e.g., if there block can access all the variables in the method in which it is isanassignmentx:=1,wecanseedthenodeforvariable defined, i.e., method temporaries and fields of the enclosing x with the type Integer. class. It can also define its own arguments and temporaries. Thenodesthatrepresentliteralsareseededwiththeclass As for the method invocation, edges are constructed from thatrepresentsthetypeofthevalueheldbyaliteral,e.g., the expressions supplied as arguments, to the corresponding thenodefortheliteral’string’isseededwiththetype block parameters. The return value of the block object is String. the type of the last expression in the block. Implementation 3) propagate types along the edges between nodes, e.g., if issuesconcerninglexicalclosuresarediscussedintheoriginal there is an assignment y:=x, we can propagate all the paper [13]. possible types from the node representing variable x to Since types are only propagated in the direction indicated the node representing variable y, thus y will also hold by an edge, and never removed from the nodes, an inclusive the type Integer relation,e.g.,types(x) ⊆ types(y)willalwaysholdfor The algorithm infers types for expressions based on the a node x with a direct edge to node y. Whenever a type is constraints it creates during the analysis. propagated down an edge, the propagation continues onward Assignment. During the analysis of an assignment expres- untilitreachesthenodethatalreadycontainedthattype,sono sion v:=exp the algorithm infers the type for the expression further propagation is required. This ensures that the analysis expontheright-handsideoftheassignment,andconstructsa will eventually halt. Analysis continues until a fixed point is directed edge from the node representing the expression exp reached, and no more propagation is needed. tothenoderepresentingvariablev,indicatingthatallthetypes B. Type hints from method argument names inferredforexpshouldalsobelongtothesetofpossibletypes of variable v. A common practice when writing dynamically-typed code Method invocation. When it encounters a method invo- istonamemethodargumentstoprovideahintoftheexpected cation x msg: y, CPA creates edges from the arguments of type. This practice differs from one language to another: themethodinvocation,totheformalparametersofthemethod while in Smalltalk the practice is to prefix the expected class that is supposed to be invoked, indicating a possible data flow name with an article, e.g., aString, in Python the practice at run time. If any of the argument expressions has more than is to annotate a method argument in a specific manner4, one possible type, CPA creates a Cartesian product of the sets e.g., string: String to indicate that a method argument of possible types for the arguments, and analyses each of the named string expects an object of type String. As a combinations separately. Thus, whenever the algorithm enters consequencedifferentmannersofextractingthetypehintfrom a new method during the analysis, its formal parameters have a variable name are needed for distinct languages: while in uniquelyidentifiedtypes.Afterthemethodhasbeenanalysed, Smalltalk this involves parsing text, in Python this would CPA caches the information about method argument types require annotation analysis. (including the type of the object on which method is invoked) For this reason, we leave this part of the algorithm as and return types. Thus, if at any time in the future the same abstract, supposing that in the specific language there is an method needs to be analysed with the same argument types, implementationofafunctionreturningtheinferredtypebased it can just collect the set of the return types from the cached on the argument, i.e., method argument name. We explain in information, without the need to analyse it again. That is how detail the implementation of this function used for evaluation it preserves speed with accuracy [13]. in section IV. The set of possibly invoked methods is constructed based C. Upgraded CPA - CPA∗ on the possible types of the method call receiver. If there is more than one possibly invoked method, edges from the WehaveimplementedCPAwithoneadditionalstep.When- messageargumentsareconstructedtoallofthecorresponding ever CPA would encounter a method to analyse, just before formal method parameters, to ensure that the entire possible creatingtheCartesianproductofthesetsofpossibletypesfor dataflowiscovered.Foreachmethod,thecorrespondingtype thearguments,thenewalgorithmwouldinferargumenttype(s) of the receiverof method call isseeded as the valueof this. for each of the arguments, based on the type hints from the Correspondingly, the type of the method call is the union of argument name. Then, for each argument, it would take the thereturntypesofallmethodsthatcanbeinvokedatthatcall union of two sets: the set of inferred types by CPA, and the site. set of types inferred from the argument name. The algorithm Returnstatement.Thereturntypeofamethodistheunion would then continue as usual, to create a Cartesian product of of the return types of all return statements ˆexp3 within the the sets of types, and to analyse each combination separately. method.Thetypeofthereturnstatement ˆexpisequaltothe We call the new algorithm CPA∗. 3Selfsyntaxforreturnstatementisˆ. 4https://www.python.org/dev/peps/pep-0484/#acceptable-type-hints Expression Inferredtype x=y x==y x∼=y x>y x>=y x<y x<=y {True, False} xmsg,wherexisaclassandmsgisanyoftheselectorsfromtheset{new, new:, x basicNew, basicNew:} TABLEI HEURISTICSUSEDTOINFERTHETYPEOFTHEEXPRESSION IV. IMPLEMENTATION have the type String, but also an argument named whateverString would have the type String Inthissectionweexplainindetailtheprototypeimplemen- 3) if the argument name is spec, its supposed type is tation in Smalltalk. MetacelloAbstractVersionConstructor. A. CPA spec is commonly used to name specifications of Metacello versions. Metacello is a package management In order to initially seed the types to the nodes, we have system for Monticello, a distributed version control used a couple of heuristics to guess the type of the expression system used for Smalltalk resultassignedtothevariable,aspresentedintheTableI.The 4) if the argument name matches the regex method for identity comparison (i.e., ==) is implemented as a primitive method. Primitive methods are performed directly “.*(b|B)lock.*”, its type is BlockClosure (this class represents a lexical closure object in by the interpreter rather than by evaluating expressions in the Smalltalk) method.Essentialprimitivescannotbeperformedinanyother 5) if the argument name matches the regex way. For example, Smalltalk without primitives can move values from one variable to another, but it cannot add two “.*(o|O)rderedCollection.*”, its type is OrderedCollection Integers together. Thus, there is no other way to handle these 6) if the argument name matches the regex methods. Without the use of these heuristics, the analysis would lose precision. For example, the inferred return type “.*(a|A)rray.*”, its type is Array 7) if the argument name matches the regex for method == would be the type of the object on which the method is invoked, rather than an instance of the Boolean “.*(d|D)ictionary.*”, its type is Dictionary 8) if the argument name matches the regex class. The second row in the Table I refers to the primitive methods used to create new instances of a class. “.*(s|S)et.*”, its type is Set 9) if the argument name matches the regex B. Type Hints in Smalltalk “.*(b|B)ag.*”, its type is Bag 10) if the argument name matches the regex A recent study on the quality and usage prevalence of type hintsfrommethodargumentnamesinSmalltalk[33]revealed “.*(c|C)ollection.*”, its type is Collection 11) if the argument name matches the regex that type hints are provided only in around 36% of cases. If theexpectedtypeofaSmalltalkmethodargumentisString, “.*(s|S)tring.*”, its type is String the corresponding argument should be named aString. The 12) if the argument name matches the regex authors of the study proposed a couple of heuristics in order “.*(s|S)ymbol.*”, its type is Symbol. Symbols in Smalltalk represent Strings that are created uniquely. to improve the algorithm used for type hints. They managed to successfully guess the type for about half of the method The algorithm in the study performed by Spasoje- arguments throughout the ecosystem. To guess the type of vic´ et al. did not include steps 5-9. Thus, for any the argument named arg, we have used a slightly improved method argument whose name matches regular expres- versionofthealgorithmproposedinthisstudy.Itisimportant sion “.*(c|C)ollection.*” the inferred type would be to emphasise that the algorithm includes the following steps Collection. However, since the Collection class is an inthesameorder,andthatthealgorithmwouldproceedtothe abstract superclass of the classes OrderedCollection, following step only if the previous step would fail to provide Array, Dictionary, Set and Bag, and, based on our a type: analysis of the current Pharo image, these subclasses are the 1) ifthereisaclassinthePharoimage5withnamematching most commonly used subclasses of the Collection class, arg (by ignoring upper and lower case differences), that we decided to treat them separately. class represents the type of the argument, e.g., argument It is important for the algorithm to follow the steps named string would have the type String in the indicated order, for the sake of the argu- 2) remove everything in the argument name before the ment names like aBlockAnsweringAString, which first upper case, and match the rest with a class is clearly a BlockClosure and not a String, or name, e.g., an argument named aString would aCollectionOfStringwhichisaCollectionandnot a String [33]. 5Theterm“Pharoimage”isusedtodenotesnapshotoftherunningPharo system. If a method argument can expect an object of the type #ofmethods #of Projectname #ofmethods The overall results are represented in Figure 1. In total, witharguments arguments Roassal2 1371 483 745 CPA∗ analysed 31% more methods, which increased the Glamour 189 188 229 number of analysed arguments by 52%. Consequently, the Morphic 677 675 935 number of method arguments that contain type hints was also TOTAL 2237 1346 1909 increased by 63%. However, 22 out of 212 method arguments containedfalsetypeinformation,thatisthetypeinferredfrom TABLEII RUN-TIMEINFORMATION the argument name did not correspond to its run-time type. CPA∗ is nevertheless able to correctly infer types for 81% more of the method arguments. More detailed information regarding CPA and CPA∗ sepa- BlockClosure or Symbol, the convention is to name the rately are presented in Table III and Table IV. When we exe- argument e.g., aBlockOrSymbol. The usual approach is cutedtheCPAanalysisinitsbasicform,inourimplementation to use the conjunction Or starting with a capital letter and it managed to cover 316 out of 1371 methods in the Roassal2 followed by a capital letter, due to the Camel Case notation package, or one quarter of the actual call graph. As for the [45]. While this is a convention in Smalltalk, a different Glamour package, analysis covered 62 methods, i.e., around approach might be taken in other languages [46]. In order 33% of the executed methods. We were surprised by the low nottolosetypehints forthesearguments,wewouldfirstsplit numberofstaticallyanalysedmethodsintheMorphicproject. the argument name based on the appearances of conjunction CPAmanagedtoreachonly3%oftheexecutedmethods.The Orfollowedbyanuppercaseletter,andthenapplysteps1-12 Morphic project takes advantage of the reflection usage. It from the algorithm on each of the substrings. The type(s) of invokestheObject»#perform:8 methodin29ofitsmeth- the argument would be represented by the union of type(s) of ods. The method Object»#perform: provides a reflective each of the substrings. way to invoke a method on the target object with the method Theproposedalgorithmheavilydependsoncorrectlynamed name supplied as an argument to Object»#perform:. method arguments. We match regular expressions that contain After having a closer look at the analysis, we discovered that the expected class name with the method argument name. 12 of these 29 methods were traversed during static analysis Hence, if the method argument name contains an error and, and that they were traversed in total a bit more than 3000 for example, is named aStrong instead of aString, the times. This puts them in the hotspot of the analysis. Two of algorithm will miss its type. these twelve methods do not have any method argument, thus V. EVALUATION there is no space for improvement. As for ten other methods, almost no type hints may be found in their argument names. For the evaluation we have used three open-source Pharo The same applies for the methods that are being traversed projects for which we were able to collect run-time infor- right after the Object»#perform: methods, hence room mation that closely depicts their real usage: Glamour6 [47], for improvement in this case is limited. Roassal27 [48], and Morphic [40]. Glamour is a framework These399methodsaccountfor253methodarguments.For for specifying the navigation flow of browsers. Roassal2 is an 45% of these arguments, i.e., for 114 out of 253, all types agile visualisation engine that graphically renders objects and seen at run time were also inferred by CPA (this is presented Morphic is a User Interface construction kit. in the column named “# of covered arguments” in Table III). Each project provides a set of example methods that reflect Hence, CPA did not underestimate types for a bit less than their real usage: Glamour has 83 of these methods, Mor- half of the arguments. The proportion of arguments with type phic 29, and Roassal2 952. These methods are created by hints in their name is quite different in all three packages: project developers to demonstrate the potential usage of the from 40% in Roassal2 to 83% in Morphic. corresponding project. They serve as a main method and When we inferred types with the CPA∗ algorithm, we were whenexecutedprovideanexampleofhowtheprojectmaybe able to cover 123 more methods, i.e., 31% (Table IV). This employed. We have executed these methods, and the recorded indicates that 130 arguments in CPA analysis with type hints run-timedataservesasgroundtruthtowhichresultsprovided in their name managed to augment the size of analysed call by static type inference are compared. graphforaroundonemethodperargumentwithtypehint.We As can be seen in Table II, the execution of these examples deem this important, since it increases the size and precision covered in total 2237 methods from all three projects, out of of the traversed call graph. which 1346 methods have at least one argument. It traversed Accordingly, the number of analysed method arguments in total 1909 method arguments. We have recorded run-time increased by 52%. The number of arguments for which all informationonlyforthemethodsinthepackages,i.e.,wehave run-time types were also inferred by static analysis increased excluded the library methods. to 53.5%. The augmented algorithm therefore outperforms Wehaveusedthesameexamplemethodsasmainmethods, the basic algorithm, and correctly infers types for 81% more i.e., the entry points to start the Cartesian product analysis. method arguments. 6http://www.smalltalkhub.com/#!/~Moose/Glamour 7http://smalltalkhub.com/#!/~ObjectProfile/Roassal2 8Theperform:methodoftheObjectclass Table 1 # of methods # of arguments # of arguments # of covered with type hints arguments CPA 399 253 130 114 CPA* 522 385 212 206 Table 1-1 CPA CPA* # of arguments with false type hints #of methods 399 0 0 600 #of methods 0 522 0 # of arguments 253 0 0 522 # of arguments 0 385 0 450 # of arguments 130 0 0 with type hints 399 # of arguments 0 190 22 385 with type hints # of covered 114 0 0 300 arguments # of covered 0 206 0 253 22 arguments 206 190 150 130 114 0 #of metho d s # of argum e n t s # of argume n t s 
 # of covered
 with type h i n t s arguments Fig.1. CPAandCPA∗ results #ofmethods #of #ofarguments #ofcovered Projectname #ofmethods witharguments arguments withtypehints arguments Roassal2 316 114 155 63 63 Glamour 62 62 75 48 41 Morphic 21 21 23 19 10 TOTAL 399 197 253 130 114 TABLEIII CPABASIC #ofarguments Project #of #ofmethods #of #ofarguments #ofcovered withfalse name methods witharguments arguments withtypehints arguments typehints Roassal2 383 146 224 95 21 133 Glamour 66 66 80 50 0 46 Morphic 73 73 81 67 1 27 TOTAL 522 285 385 212 22 206 TABLEIV CPAWITHTYPEHINTS-CPA∗ The column named “# of arguments with false type hints" the run-time type is actually RTShape, which is not related in Table IV provides information about misleading type hints. to the Shape class even though it has a similar name. Most of them are due to the name aCollection for which ThereareacoupleofsituationswhereCPA∗ wouldinferas onlytheclassCollectioncanbeinferredastype,andsince possible types for a method argument both BlockClosure Collectionisanabstractclass,itisnotusedasobjecttype and Symbol, while at run time only one of them is recorded atruntime.AlsotheargumentnameaShapeismisleading,as as the actual type. This would happen if a method argument theShapeclasswillbeinferredasthepossibletype,although is named e.g., aBlockOrASymbol. Such variables often �1 Project Time-CPA Time-CPA on top of which a graphical representation is built; while in name andtypehints Roassal2 11.5 12.1 Glamour and Morphic it is mostly used as a name of a setter- Glamour 0.7 0.9 method argument. Morphic 1 1.6 Glamour. Beside anObject the most common argu- ment names for which the algorithm was not able to TABLEV TIMENEEDEDFORTHEANALYSISINSECONDS provide a type hint are aPort, aPortReference, aPane and aPresentation. These names correspond to types from the Glamour project, respectively, GLMPort, GLMPortReference,GLMPaneandGLMPresentation reflect a form of duck typing [49]. In this specific case, for (GLM stands for Glamour), which indicates that this kind of example, Symbol is duck-typed in Smalltalk to behave like heuristic would greatly benefit from the input related to the a block in certain idiomatic scenarios. We therefore do not project under analysis. Based on the examples from the Roas- consider CPA∗ to be wrong just because only one of the sal2 and Glamour packages, the simple heuristic of removing two types is observed in practice. Also, if CPA∗ would infer the project-related prefix from class names and then inferring as possible types for a method argument more classes than a type from the argument name would definitely improve the recorded at run-time, but the argument name clearly reveals results. However, the improvement heavily depends on the that any of the inferred classes is expected at run time, e.g., practice of developers involved in the development of certain aBlockOrANumber, we do not count it as false type hint. project. In these particular projects, we suspected that the We choose to believe in the developer’s suggestions, even improvementwouldbesignificant,sinceabout30%ofmethod though not all of the hinted classes are recorded during the argumentswithouttypehintsinRoassal2and50%ofthosein execution run. Glamour would provide a type hint by using this heuristic. This data shows that the combination of CPA with type Further investigation revealed that these classes are mostly hintsfrommethodargumentnamessignificantlyincreasedthe abstract.Ifwehaveaboundedsetofpossibleconcreteclasses size of the analysed call graph, which forms a part of call inthiscase,inferringtheactualtypeofsuchargumentswould graph recorded at run time, thus does not belong to false be feasible by applying an approach similar to the one we positives.Thisindicatesthattypehintsfrommethodargument followed to detect the type for collections, as was explained namescanincreasetheprecisionofCPAindynamically-typed in subsection IV-B. languages. Morphic. An argument named anImage, which would sug- In order to evaluate whether or not this combination is gestthatanobjectofclassImageisexpected,actuallyexpects still usable for program comprehension purpose, beside the an object of class Form which represents an array of pixels, precision, we have measured the time needed for both types usedforholdingimages.NoclassImageexistsintheversion of the analysis. On all three projects, we have found that of Pharo used for the experiment. A method argument named the introduced overhead is quite divergent: from 5% to 60% aFont indicates that some kind of font is expected at (Table V). The most overhead was introduced in the Morphic run time. While there is no class Font, there is an abstract project,whichisunderstandable,sincethenumberofanalysed classnamedAbstractFont,whichdefinestheinterfacefor methods more than tripled. This also indicates that Morphic fonts. contains method arguments with the largest number of type Findings in the Glamour project cause us to suppose that hints among the three analysed packages. giving precedence to classes from the same package when analysing a method would improve the results. For example, A. Argument names without inferred type hint a method argument anAnnouncer clearly indicates that it In all three projects, we have investigated the set of argu- expects some kind of the announcer at run time. While the ment names for which the algorithm was not able to provide used algorithm for inferring the type from method argument a hint. In this subsection, we elaborate on our findings. namewouldconcludethatitstypeisAnnouncer,inGlamour Roassal2. The most used names are, in order, elements, package its expected type is actually GLMAnnouncer, a objects, anElement, anObject, element. Even subclass of the Announcer class. though the analysis was not able to infer types from these names,ahumancandeducethatthefirsttwoargumentsexpect VI. DISCUSSIONANDTHREATSTOVALIDITY somekindofCollectionobject.Eventhoughwethinkthat We have chosen the Roassal2, Glamour and Morphic this can be introduced as a rule, more research is needed to projects to evaluate our heuristic since we were able to run verifyourassumption.Asforthethirdname,thereisnoclass theseprojectsinawaythatcloselyresemblestheirrealusage. named Element, but there is a class in the Roassal2 project Nevertheless,itisanopenquestionwhetherwehavecollected named RTElement, so a developer may guess the expected all possible run-time types for variables. type of the argument. The same applies for the argument Another threat to validity comes from the quality of type named element. The name anObject is used as a method hints in method argument names. While we have evaluated argument name in all three projects: in Roassal2 it is mostly our heuristic in Smalltalk, exploring its performance in other used to indicate a member of a collection, or as an object dynamically-typed languages remains future work. Recent studies revealed that type annotations are commonly used in values of different types. It was used to check the correctness Python[34]andDart[35].Hence,webelievethatworksimilar of downcasts in Java programs. Ecstatic [37] is an implemen- to ours may be performed at least in these two languages. tation of type inference for the Ruby programming language Moreover, we have used the results provided by a study based on CPA, and adapted for various Ruby programming on a large set of Smalltalk projects [33], but it is an open idioms, for example block usage, as there are seven distinct question whether an arbitrary project will provide the same block syntaxes. quality of type hints. As is presented in the section V, some One of the simplest type inference algorithms, RoelTyper, argument names have misleading type hints, while others which is mainly intended for the purpose of program compre- provideatypehintforanabstractclass,butitisobviousthata hension, was developed by Roel Wuyts and later improved by subclass will actually represent an argument type. Due to this Frédéric Pluquet [17]. The algorithm is intraprocedural, and it problem,wehaveenrichedthealgorithmusedtoobtainatype infers types for a variable based on its interface and possible from an argument name by steps 5-9 (subsection IV-B). The assignments to it. Even though it is very simple, it correctly same kind of work is possible e.g., for the argument name infers types for just under 60% of variables. anAbstractFont (this name indicates an abstract class, One improvement of RoelTyper was presented by Spaso- while the usual run-time type is one represented by one of jevic´ et al. [52]. It collects information from the language thesubclasses),butwedidnothaveanyfindingsonthelarger ecosystem, hence the name Ecosystem-Aware Type Inference set of projects to support this. (EATI). Based on the collected information, EATI sorts possi- The final threat comes from our choice of the basic al- ble typesfor a variable andincreases the likelihoodof putting gorithm. We chose CPA since its precision heavily depends the correct type at the top of the list of possible types. on the correctly inferred types for method arguments and we RoelTyperwasimprovedbyheuristicsthatderivedatafrom thinkthatitwouldgreatlybenefitfromtheproposedheuristic. staticanddynamicanalysisofclassusagefrequency[53],[54]. However, we believe that this heuristic may be also combined These heuristics more than doubled the number of correctly with other simple type inference algorithms, for example inferred types when compared to the underlying approach. RoelTyper [17]. The heuristic is simple and fast enough not Another related field of work is optional typing. It grants to endanger the speed of the underlying algorithm, yet we a developer the opportunity to annotate types, but does not assume it would improve its precision. enforce static type checking, hence does not prevent run-time VII. RELATEDWORK type errors [55]. Optional typing is present in many language communities: Smalltalk [56], [57], [58], [59], Groovy [60], Tothebestofourknowledge,thisisthefirststudythattries Dart [35], JavaScript [61], Python [62], Ruby [63] and tocombineanexistingtypeinferencealgorithmwithtypehints Lua [64]. from method argument names. These type annotations usually serve as a kind of docu- The first type inference algorithm, “Algorithm W”, was mentation and they are often exercised by developers [35], developed by Milner [10]. It was developed for ML program- [65]. Developers with less background in dynamically-typed ming language, and focused on parametric types rather than languages tend to use type annotations more often, mostly subtyping.Typesareconsideredtobehierarchiesoffunctional in method definitions. Furthermore, types are less used in types over a set of basic types. frequentlychangedcode.Asseen,typeannotationsmayserve Another approach that treats types as sets of expressions, as input for improvement of type inference algorithms, as rather than as sets of values was developed for the FL func- presented in this paper. tionallanguage[11].Wefocusourattentiononalgorithmsthat employ nominal types, since structural types burden program comprehension [50]. VIII. CONCLUSION One of the most precise type inference algorithms, Chuck was developed by Alexander Spoon et al. [16], [51]. It is Statictypeinformationprovestobeusefulwhenperforming a demand-driven algorithm that uses subgoal pruning. That programcomprehensiontasksindynamically-typedlanguages. means that if the type inference for an expression, i.e., the Current type inference algorithms usually suffer from the goal, would depend on many other complex expressions, i.e., problems of false positives or false negatives. However, they typeinferenceofsubgoals,thealgorithmmaydecidetoprune mainly analyse language constructs, not naming conventions. some of the subgoals in order to simplify the calculations. Ontheotherhand,topartiallyremedythelackofstatictype The Cartesian Product Algorithm [13], which we used as information in dynamically-typed languages, developers tend theunderlyingalgorithminourimplementation,wasoriginally to provide type hints in the method argument names. These developed for Self, a prototype-based language [43]. It has hints are mostly intended for human comprehension, but are been used as the basic algorithm for a couple of other type also exploited by the IDE, for example, for code completion. inference techniques [15], [36], [37]. Starkiller represents a We have performed a study to assess the possible impact type inferencer and compiler for Python, based on CPA [15]. of these hints on the results of a type inference algorithm Another extension of CPA is DCPA [36], which focuses on calledCPA.Theobtainedresultsarepromising;theaugmented data polymorphism, i.e., when a variable may have assigned algorithm outperforms the basic one significantly.