Demand-Driven Type Inference with Subgoal Pruning

Program understanding;Types;Smalltalk;Programming tools;Program analysis;Data flow;Type inference

Spoon, Steven Alexander ; Computing

University:Georgia Institute of Technology

Department:Computing

关键词: Program understanding;    Types;    Smalltalk;    Programming tools;    Program analysis;    Data flow;    Type inference;   

Others  :  https://smartech.gatech.edu/bitstream/1853/7486/1/spoon_steven_a_200512_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Highly dynamic languages like Smalltalk do not have much static typeinformation immediately available before the program runs.Statictypes can still be inferred by analysis tools, but historically, suchanalysis is only effective on smaller programs of at most a few tensof thousands of lines of code.This dissertation presents a new type inference algorithm, DDP,that is effective on larger programs with hundreds of thousandsof lines of code.The approach of the algorithm borrows from thefield of knowledge-based systems: it is a demand-driven algorithm thatsometimes prunes subgoals.The algorithm is formally described,proven correct, and implemented.Experimental results show that theinferred types are usefully precise.A complete program understandingapplication, Chuck, has been developed that uses DDP typeinferences.This work contributes the DDP algorithm itself, the most thoroughsemantics of Smalltalk to date, a new general approach for analysisalgorithms, and experimental analysis of DDP includingdetermination of useful parameter settings.It also contributesan implementation of DDP,a general analysis framework forSmalltalk, and a complete end-user application that uses DDP.