Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-24T21:58:22.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Projections for polymorphic first-order strictness analysis†

Published online by Cambridge University Press:  04 March 2009

John Hughes  and
John Launchbury
John Hughes
Affiliation:
Department of Computing Science, University of Glasgow, Glasgow G12 8QQ
Get access Rights & Permissions [Opens in a new window]

Abstract

We apply the categorical properties of polymorphic functions to compile-time analysis, specifically projection-based strictness analysis. First we interpret parameterised types as functors in a suitable category, and show that they preserve monics and epics. Then we define “strong” and “weak” polymorphism, the latter admitting certain projections that are not polymorphic in the usual sense. We prove that, under the right conditions, a weakly polymorphic function is characterised by a single instance. It follows that the strictness analysis of one simple instance of a polymorphic function yields results that apply to all. We show how this theory may be applied. In comparison with earlier polymorphic strictness analysis methods, ours can apply polymorphic information to a particular instance very simply. The categorical approach simplifies our proofs, enabling them to be carried out at a higher level, and making them independent of the precise form of the programming language to be analysed. The major limitation of our results is that they apply only to first-order functions.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 2 , Issue 3 , September 1992 , pp. 301 - 326
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Abramsky, S. (1985) Strictness Analysis and Polymorphic Invariance, Workshop on Programs as Data Objects, Copenhagen, Springer Lecture Notes in Computer Science 217.Google Scholar
Abramsky, S. and Jensen, T.P. (1991) A Relational Approach to strictness Analysis for Higher-Order Polymorphic Functions. POPL 91, Orlando, Florida.Google Scholar
Baraki, G. (1991) A Note on Abstract Interpretation of Polymorphic Functions, FPCA 91, Cambridge MA, Springer Lecture Notes in Computer Science 523.Google Scholar
Bjerner, B. and Holmstrø, S. (1989) A Compositional Approach to Time Analysis of First Order Lazy Functional Programs, IFIP Functional Programming Languages and Computer Architecture, London, ACM Press, Addison-Wesley.Google Scholar
Burn, G.L., Hankin, C.L. and Abramsky, S. (1985) The Theory of Strictness Analysis for Higher-order Functions, Workshop on Programs as Data Objects, Copenhagen, Springer Lecture Notes in computer Science 217.Google Scholar
Burn, G. (1990) A Relation between Abstract Interpretation and Projection Analysis, 17th POPL, San-Francisco.Google Scholar
Burn, G. (1991) Lazy Functional Languages: Abstract Interpretation and Compilation, Pitman.Google Scholar
Cousot, P. and Cousot, R. (1977) Abstract interpretation: a unified lattice-theoretic model for static analysis of programs by construction or approximation of fixpoints. Proc. 4th POPL.Google Scholar
Clack, C. and Peyton-Jones, S.L. (1985) Strictness Analysis: a Practical Approach, IFIP Conference on Functional Programming Languages and Computer Architecture, Nancy, France, Springer Lecture Notes in Computer Science 201.Google Scholar
Dybjer, P. (1991) Inverse Image Analysis Generalises Strictness Analysis, J. Inf. and Comp. 90 (2).Google Scholar
Freyd, P.J., Girard, J.Y., Scedrov, A. and Scott, P.J. (1988) Semantic Parametricity in Polymorphic Lambda Calculus, 3rd Annual Symposium on Logic in Computer Science, Edinburgh, Scotland.Google Scholar
Hall, C. and Wise, D.S. (1987) compiling Strictness into Streams, ACM Symposium on Principles of Programming Languages, 1987.CrossRefGoogle Scholar
Hudak, P. and Young, J. (1986) Higher-order Strictness Analysis for Untyped Lambda Calculus, ACM Symposium on Principles of Programming Languages, 1986.Google Scholar
Hughes, J. (1985) Strictness Detection in Non-Flat Domains, Workshop on Programs as Data Objects, Copenhagen, Springer Lecture Notes in Computer Science 217.Google Scholar
Hughes, J. (1987a) Analysing Strictness by Abstract Interpretation of Continuations. In: Abramsky, and , Hankin (eds.), Abstract Interpretation of Declarative Languages, Ellis-Horwood.Google Scholar
Hughes, J. (1987b) Backwards Analysis of Functional Programs. In: Ershov, Bjørner and , Jones (eds.), IFIP Workshop on Partial Evaluation and Mixed Computation, North-Holland.Google Scholar
Hughes, J. (1988) Abstract Interpretation of First-order Polymorphic Function, Proc. Aspenas Worshop on Graph Reduction, University of Gothenburg.Google Scholar
Hughes, J. (1990) compile-time Analysis of Functional Programs. In: Turner, D.A. (ed.), Research Topics in Functional Programming, University of Texas at Austin, Year of Programming Series, Addison-Wesley.Google Scholar
Hughes, J. and Launchbury, J. (1991) Towards Relating Forwards and Backwards Analyses, Proc. Glasgow workshop on Functional Programming, Ullapool, C-V WIC.Google Scholar
Hunt, S. (1991) PERs generalise Projections for Strictness Analysis, Proc. Glasgow workshop on Functional Programming, Ullapool, C-V WIC.Google Scholar
Launchbury, J. (1987) Projections for Specialisation. In: Ershov, Bjørner and , Jones (eds.), IFIP Workshop on Partial Evaluation and Mixed Computation, North-Holland.Google Scholar
Launchbury, J. (1991) Projection Factorisations in Partial Evaluation, Distinguished Dissertation in Computer Science, Vol 1, CUP.Google Scholar
Martin, C. and Hankin, C. (1987) Finding Fixed Points in Finite Lattices, IFIP Conference on Functional Programming Languages and Computer Architecture, Portland, Oregon, Springer Lecture Notes in Computer Science 274.Google Scholar
Mycroft, A. (1980) The Theory and Practice of Transforming Call-by-Need into Call-by-Value, Proc. International Symposium on Programming, Springer Lecture Notes in Computer Science 83.Google Scholar
Reynolds, J.C. (1974) Towards a Theory of Type Structure. In: Robinet, B. (ed.), Proc. Colloque sur la Programmation, Springer Lecture Notes in Computer Science 19.CrossRefGoogle Scholar
Schmidt, D. (1986) Denotational Semantics: A Methodology for Language Development, Allyn and Bacon, Inc.Google Scholar
Scott, D. and Gunter, C. (1989) Semantic Domains, draft version, Handbook in Theoretical Computer Science, North Holland, to appear.Google Scholar
Smith, M. and Plotkin, G. (1982) The Category-Theoretic Solution of Recursive Domain Equations, SIAM J. COMPUT 11 (4) 761–783.Google Scholar
Wadler, P. and Hughes, J. (1987) Projections for Strictness Analysis, IFIP conference on Functional Programming Languages and computer Architecture, Portland, Oregon, Springer Lecture Notes in computer Science 274.Google Scholar
Wadler, P. (1987) Strictness Analysis on Non-flat Domains (by Abstract Interpretation over Finite Domains). In: , Abramsky and , Hankin (eds.), Abstract Interpretation of Declarative Languages, Ellis-Horwood.Google Scholar
Wadler, P. (1988) Strictness Analysis Aids Time Analysis, ACM Symposium on Principles of Programming Languages, 1988.Google Scholar
Wadler, P. (1989) Theorems for Free! ACM conference on Functional Programming Languages and Computer Architecture, London, ACM Press/Addison-Wesley.Google Scholar
Wray, S.C. (1986) Implementation and Programming Techniques for Functional Languages, Ph.D. thesis, University of Cambridge.Google Scholar