Equality-based flow analysis versus recursive types
- 1 November 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 20 (6) , 1251-1264
- https://doi.org/10.1145/295656.295662
Abstract
Equality-based control-flow analysis has been studied by Henglein, Bondorf and Jørgensen, DeFouw, Grove, and Chambers, and others. It is faster than the subset-based-0-CFA, but also more approximate. Heintze asserted in 1995 that a program can be safety checked with an equality-based control-flow analysis if and only if it can be typed with recursive types. In this article we falsify Heintze's assertion, and we present a type system equivalent to equality-based control-flow analysis. The new type system contains both recursive types and an unusual notion of subtyping. We have s ≤ t if s and t unfold to the same regular tree, and we have ⊥≤t≤⊤ where t is a function type. In particular, there is no nontrivial subtyping between function types.Keywords
This publication has 10 references indexed in Scilit:
- Fast interprocedural class analysisPublished by Association for Computing Machinery (ACM) ,1998
- From polyvariant flow information to intersection and union typesPublished by Association for Computing Machinery (ACM) ,1998
- Linear-time subtransitive control flow analysisPublished by Association for Computing Machinery (ACM) ,1997
- Fast and accurate flow-insensitive points-to analysisPublished by Association for Computing Machinery (ACM) ,1997
- Points-to analysis in almost linear timePublished by Association for Computing Machinery (ACM) ,1996
- A practical and flexible flow analysis for higher-order languagesPublished by Association for Computing Machinery (ACM) ,1996
- A type system equivalent to flow analysisACM Transactions on Programming Languages and Systems, 1995
- Closure analysis in constraint formACM Transactions on Programming Languages and Systems, 1995
- Subtyping recursive typesACM Transactions on Programming Languages and Systems, 1993
- Efficient analyses for realistic off-line partial evaluationJournal of Functional Programming, 1993