Back to search

Georgia Institute of Technology

Demand-Driven Type Inference with Subgoal Pruning

Abstract

dc:description.abstract

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.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Spoon, Steven Alexander
Advisor dc:contributor.advisor
  • Shivers, Olin
Committee members dc:contributor.committeemember
  • Agesen, Ole
  • Harrold, Mary Jean
  • Rugaber, Spencer
  • Smaragdakis, Yannis

Subjects

dc:subject × 11

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/7486

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Spoon, Steven Alexander. Demand-Driven Type Inference with Subgoal Pruning. Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/7486