Highly dynamic languages like Smalltalk do not have much static type
information immediately available before the program runs. Static
types can still be inferred by analysis tools, but historically, such
analysis is only effective on smaller programs of at most a few tens
of thousands of lines of code.
This dissertation presents a new type inference algorithm, DDP,
that is effective on larger programs with hundreds of thousands
of lines of code. The approach of the algorithm borrows from the
field of knowledge-based systems: it is a demand-driven algorithm that
sometimes prunes subgoals. The algorithm is formally described,
proven correct, and implemented. Experimental results show that the
inferred types are usefully precise. A complete program understanding
application, Chuck, has been developed that uses DDP type
inferences.
This work contributes the DDP algorithm itself, the most thorough
semantics of Smalltalk to date, a new general approach for analysis
algorithms, and experimental analysis of DDP including
determination of useful parameter settings. It also contributes
an implementation of DDP, a general analysis framework for
Smalltalk, and a complete end-user application that uses DDP.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/7486 |
| Date | 29 August 2005 |
| Creators | Spoon, Steven Alexander |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation |
| Format | 1450596 bytes, application/pdf |
Page generated in 0.0019 seconds