2000 · 128 citations · 19 references
ComputingComputer ScienceAlgorithmsCompilersProgramming LanguagesAbstract Syntax TreesControl-flow AnalysisData TypesData-flow AnalysisType CheckingType SystemsContext-sensitive AnalysisControl-flow Graph ConstructionData Type InferencePolymorphic Type SystemsPolymorphic TypesStatic PolymorphismType InferenceType Polymorphism
This paper shows that a type graph (obtained via polymorphic type inference) harbors explicit directional flow paths between functions. These flow paths arise from the instantiations of polymorphic types and correspond to call-return sequences in first-order programs. We show that flow information can be computed efficiently while considering only paths with well matched call-return sequences, even in the higher-order case. Furthermore, we present a practical algorithm for inferring type instantiation graphs and provide empirical evidence to the scalability of the presented techniques by applying them in the context of points-to analysis for C programs.
19
A theory of type polymorphism in programming
Robin Milner · Journal of Computer and System Sciences · 1978 · 2.2K citations · Full text
Precise interprocedural dataflow analysis via graph reachability
Thomas Reps, Susan Horwitz, Mooly Sagiv · 1995 · 1.2K citations
Principal type-schemes for functional programs
Robin Milner · 1982 · 1.1K citations
Points-to analysis in almost linear time
Bjarne Steensgaard · 1996 · 1.1K citations · Full text