Optimizing Type Inference Algorithms: Analyzing Complexity and Proposing Improvements

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

Final Year Thesis Oral Defense

Title: "Optimizing Type Inference Algorithms: Analyzing Complexity and 
Proposing Improvements"

by

SIN Tsz Yin

Abstract:

Type inference algorithms automatically determine types from code with 
minimal or no explicit type annotations, enabling flexible and concise code 
while maintaining type safety, which is essential in statically typed 
programs. However, formal analyses of the complexity of such algorithms are 
not readily available in the literature. This final year thesis begins by 
examining current algorithms, with a particular focus on their time 
complexity, and then proposes improvements by reformulating type inference as 
CFL reachability. For monomorphic programs, an algorithm derived from CFL 
reachability was adapted, resulting in an improvement over the cubic 
complexity of existing type inference algorithms. Framing type inference as 
CFL reachability also opens avenues for future work to further enhance the 
efficiency of type inference algorithms.


Date            : 3 May 2025 (Saturday)

Time            : 11:30 - 12:10

Venue           : Room 2128C (near lift 19), HKUST

Advisor         : Dr. PARREAUX Lionel

2nd Reader      : Prof. YI Ke