Abstract
Control flow analysis is a powerful method for analysing which functions are applied to which arguments. However, many users find the information more understandable if the information is presented in the form of types rather than sets of function abstractions. We therefore show how to translate the result of the control flow analysis into the syntax of types (to be called observed types).
To compare our approach with the more traditional approach using type systems (to be called inferred types) we develop the subtyping relations in both approaches; in particular we show that covariant subtyping is the appropriate choice for observed types whereas contravariant subtyping is appropriate choice for inferred types. This serves as a technical underpinning of our main thesis that observed types should merely record how the entity has been used in the program at hand whereas inferred types should indicate how the entity can be used in all possible contexts.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abadi, M., et al.: Dynamic typing in a statically typed language. In: Proc. POPL’89, pp. 213–227. ACM Press, New York (1989)
Amtoft, T., Turbak, F.: Faithul Translations between Polyvariant Flows and Polymorphic Types. In: Smolka, G. (ed.) ESOP 2000 and ETAPS 2000. LNCS, vol. 1782, pp. 26–40. Springer, Heidelberg (2000)
Banerjee, A.: A modular, polyvariant, and type-based closure analysis. In: Proc. ICFP ’97, pp. 1–10. ACM Press, New York (1997)
Cousot, P.: Types as abstract interpretations. In: Proc. POPL ’97, pp. 316–331. ACM Press, New York (1997)
Cousot, P., Cousot, R.: Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In: Proc. POPL ’77, pp. 238–252. ACM Press, New York (1977)
Faxén, K.-F.: Polyvariance, polymorphism, and flow analysis. In: Dam, M. (ed.) LOMAPS-WS 1996. LNCS, vol. 1192, pp. 260–278. Springer, Heidelberg (1997)
Heintze, N.: Control-flow analysis and type systems. In: Mycroft, A. (ed.) SAS 1995. LNCS, vol. 983, pp. 189–206. Springer, Heidelberg (1995)
Henglein, F.: Global Tagging Optimization by Type Inference. In: Proc. LFP ’92, pp. 205–215. ACM Press, New York (1992)
Monsuez, B.: Polymorphic types and widening operators. In: Cousot, P., et al. (eds.) WSA 1993. LNCS, vol. 724, pp. 267–281. Springer, Heidelberg (1993)
Nielson, F., Nielson, H.R., Hankin, C.L.: Principles of Program Analysis. Springer, Heidelberg (1999)
Nielson, F., Seidl, H.: Control-flow analysis in cubic time. In: Sands, D. (ed.) ESOP 2001 and ETAPS 2001. LNCS, vol. 2028, pp. 252–268. Springer, Heidelberg (2001)
Nielson, F., Seidl, H., Riis Nielson, H.: A Succinct Solver for ALFP. Nordic Journal of Computing 9, 335–372 (2002)
Palsberg, J., O’Keefe, P.: A type system equivalent to flow analysis. ACM Transactions on Programming Languages and Systems 17(4), 576–599 (1995)
Palsberg, J., Pavlopoulou, C.: From polyvariant flow information to intersection and union types. In: Proc. POPL’98, pp. 197–208. ACM Press, New York (1998)
Thatte, S.: Type inference with partial types. In: Lepistö, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol. 317, pp. 615–629. Springer, Heidelberg (1988)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this chapter
Cite this chapter
Nielson, F., Nielson, H.R. (2007). Types from Control Flow Analysis. In: Reps, T., Sagiv, M., Bauer, J. (eds) Program Analysis and Compilation, Theory and Practice. Lecture Notes in Computer Science, vol 4444. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71322-7_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-71322-7_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71315-9
Online ISBN: 978-3-540-71322-7
eBook Packages: Computer ScienceComputer Science (R0)