Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

For a better support of static data flow

  • Conference paper
  • First Online:
Functional Programming Languages and Computer Architecture (FPCA 1991)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 523))

Abstract

This paper identifies and solves a class of problems that arise in binding time analysis and more generally in partial evaluation of programs: the approximation and loss of static information due to dynamic expressions with static subexpressions. Solving this class of problems yields substantial binding time improvements and thus dramatically better results not only in the case of partial evaluation but also for static analyses of programs—this last point actually is related to a theoretical result obtained by Nielson. Our work can also be interpreted as providing a solution to the problem of conditionally static data, the dual of partially static data.

We point out which changes in the control flow of a source program may improve its static data flow. Unfortunately they require one to iterate earlier phases of partial evaluation. We show how these changes are subsumed by transforming the source program into continuation-passing style (CPS). The transformed programs get specialized more tightly by a higher-order partial evaluator, without iteration. As a consequence, static values get frozen according to the specialization strategy and not due to the structure of the source programs.

Our approach makes it possible to get better results without changing our partial evaluator, by using its higher-order capabilities more thoroughly. By construction, transforming source programs into CPS makes it yield better results, even in the particular case of self-application. New problems can even be tackled such as static deforestation by partial evaluation, specialization of contexts, and conditionally static data.

This development concerns applicative order, side-effect free functional languages because we consider existing self-applicable partial evaluators. We conjecture a similar improvement for lazy functional languages, based on the normal order CPS transformation.

This research was supported by DARPA under grant N00014-88-k-0573. Part of it was carried out while visiting Kansas State University in 1990.

Part of this work was carried out while visiting Yale University in 1990.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. W. Appel and T. Jim. Continuation-passing, closure-passing style. In ACM Symposium on Principles of Programming Languages, pages 293–302, 1989.

    Google Scholar 

  2. D. Bjørner, A. P. Ershov, and N. D. Jones, editors. Partial Evaluation and Mixed Computation. North-Holland, 1988.

    Google Scholar 

  3. A. Bondorf and O. Danvy. Automatic autoprojection of recursive equations with global variables and abstract data types. DIKU Research Report 90/04, University of Copenhagen, Copenhagen, Denmark, 1990. To appear in Science of Computer Programming.

    Google Scholar 

  4. W. Burge. An optimizing technique for high level programming languages. Research Report RC 5834 (# 25271), IBM Thomas J.W atson Research Center, Yorktown Heights, New York, New York, 1976.

    Google Scholar 

  5. W. N. Chin. Automatic Methods for Program Transformation. PhD thesis, University of London, Imperial College of Science, Technology and Medecine, London, UK, 1990.

    Google Scholar 

  6. C. Consel. Analyse de Programmes, Evaluation Partielle et Génération de Compilateurs. PhD thesis, Université de Paris VI, Paris, France, June 1989.

    Google Scholar 

  7. C. Consel. Binding time analysis for higher order untyped functional languages. In ACM Conference on Lisp and Functional Programming, pages 264–272, 1990.

    Google Scholar 

  8. C. Consel. The Schism Manual. Yale University, New Haven, Connecticut, USA, 1990. Version 1.0.

    Google Scholar 

  9. C. Consel and O. Danvy. Partial evaluation of pattern matching in strings. Information Processing Letters, 30(2):79–86, 1989.

    Google Scholar 

  10. C. Consel and O. Danvy. From interpreting to compiling binding times. In N. D. Jones, editor, ESOP'90, 3 rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 88–105. Springer-Verlag, 1990.

    Google Scholar 

  11. C. Consel and O. Danvy. Static and dynamic semantics processing. In ACM Symposium on Principles of Programming Languages, pages 14–23, 1991.

    Google Scholar 

  12. C. Consel and S. C. Khoo. Semantics-directed generation of a Prolog compiler. In PLILP'91, 3 rd International Symposium on Programming Language Implementation and Logic Programming, 1991. To appear.

    Google Scholar 

  13. P. Cousot. Semantic foundations of program analysis: Theory and applications. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-Hall, 1981.

    Google Scholar 

  14. O. Danvy. Semantics-directed compilation of non-linear patterns. Information Processing Letters, 37:315–322, March 1991.

    Google Scholar 

  15. O. Danvy and A. Filinski. Representing control, a study of the CPS transformation. Technical Report CIS-91-2, Kansas State University, Manhattan, Kansas, USA, 1991.

    Google Scholar 

  16. H. Dybkjær. Parsers and partial evaluation: An experiment. Diku student report 85-7-15, University of Copenhagen, Copenhagen, Denmark, 1985.

    Google Scholar 

  17. A. Filinski. Declarative continuations: An investigation of duality in programming language semantics. In D.H. Pitt et al., editors, Category Theory and Computer Science, number 389 in Lecture Notes in Computer Science, pages 224–249, Manchester, UK, September 1989.

    Google Scholar 

  18. Y. Futamura. Partial evaluation of computation process — an approach to a compiler-compiler. Systems, Computers, Controls 2, 5, pages 45–50, 1971.

    Google Scholar 

  19. C. Hanson. Efficient stack allocation for tail-recursive languages. In ACM Conference on Lisp and Functional Programming, pages 106–118, 1990.

    Google Scholar 

  20. C. K. Holst. Improving full laziness. In Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors, Functional Programming, Glasgow 1990. Workshops in Computing, pages 71–82. Springer-Verlag, August 1990.

    Google Scholar 

  21. C. K. Holst and C. K. Gomard. Partial evaluation is fuller laziness. In Proceedings of the first ACM SIGPLAN and IFIP Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New Haven, Connecticut, June 1991. To appear in the SIGPLAN Notices.

    Google Scholar 

  22. C. K. Holst and J. Hughes. Towards binding time improvement for free. In Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors, Functional Programming, Glasgow 1990. Workshops in Computing, pages 83–100. Springer-Verlag, August 1990.

    Google Scholar 

  23. J. Hughes and J. Launchbury. Towards relating forward and backwards analyses. In Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors, Functional Programming, Glasgow 1990. Workshops in Computing, pages 101–113. Springer-Verlag, August 1990.

    Google Scholar 

  24. T. Johnsson. Lambda lifting: Transforming programs to recursive equations. In J.-P. Jouannaud, editor, Conference on Functional Programming Languages and Computer Architecture, volume 201 of Lecture Notes in Computer Science, pages 190–203. Springer-Verlag, 1985.

    Google Scholar 

  25. N. D. Jones, P. Sestoft, and H. Søndergaard. An experiment in partial evaluation: the generation of a compiler generator. In J.-P. Jouannaud, editor, Rewriting Techniques and Applications, Dijon, France, volume 202 of Lecture Notes in Computer Science, pages 124–140. Springer-Verlag, 1985.

    Google Scholar 

  26. N. D. Jones, P. Sestoft, and H. Søndergaard. Mix: a self-applicable partial evaluator for experiments in compiler generation. LISP and Symbolic Computation, 2(1):9–50, 1989.

    Google Scholar 

  27. J. Jørgensen. Generating a pattern matching compiler by partial evaluation. In Simon L. Peyton Jones, Graham Hutton, and Carsten Kehler Holst, editors, Functional Programming, Glasgow 1990. Workshops in Computing, pages 177–195. Springer-Verlag, August 1990.

    Google Scholar 

  28. U. Jørring and W. L. Scherlis. Compilers and staging transformations. In ACM Symposium on Principles of Programming Languages, pages 86–96, 1986.

    Google Scholar 

  29. J. B. Kam and J. D. Ullman. Monotone data flow analysis frameworks. Acta Informatica, 7:305–317, 1977.

    Google Scholar 

  30. D. A. Kranz, R. Kelsey, J. A. Rees, P. Hudak, J. Philbin, and N. I. Adams. Orbit: an optimizing compiler for Scheme. SIGPLAN Notices, ACM Symposium on Compiler Construction, 21(7):219–233, 1986.

    Google Scholar 

  31. J. Launchbury. Projection Factorisation in Partial Evaluation. PhD thesis, Department of Computing Science, University of Glasgow, Scotland, January 1990.

    Google Scholar 

  32. T. Mogensen. Partially static structures in a self-applicable partial evaluator. In D. Bjørner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Computation, pages 325–348. North-Holland, 1988.

    Google Scholar 

  33. T. Mogensen. Binding Time Aspects of Partial Evaluation. PhD thesis, DIKU, University of Copenhagen, Denmark, March 1989.

    Google Scholar 

  34. T. Mogensen. Separating binding times in language specifications. In FPCA'89, 4 th International Conference on Functional Programming Languages and Computer Architecture, pages 12–25. ACM Press, 1989.

    Google Scholar 

  35. P. Mosses. Action Semantics. Cambridge University Press, 1991. draft textbook, in preparation.

    Google Scholar 

  36. F. Nielson. A denotational framework for data flow analysis. Acta Informatica, 18:265–287, 1982.

    Google Scholar 

  37. H. R. Nielson and F. Nielson. Eureka definitions for free! or disagreement points for fold/unfold transformations. In N. D. Jones, editor, ESOP'90, 3 rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 291–305. Springer-Verlag, 1990.

    Google Scholar 

  38. G. D. Plotkin. Call-by-name, call-by-value and the λ-calculus. Theoretical Computer Science, 1:125–159, 1975.

    Google Scholar 

  39. J. Rees and W. Clinger, eds. Revised3 report on the algorithmic language Scheme. SIGPLAN Notices, 21(12):37–79, December 1986.

    Google Scholar 

  40. J. Reynolds. Definitional interpreters for higher order programming languages. In ACM National Conference, pages 717–740, 1972.

    Google Scholar 

  41. P. Sestoft. Automatic call unfolding in a partial evaluator. In D. Bjørner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Computation. North-Holland, 1988.

    Google Scholar 

  42. O. Shivers. The semantics of Scheme control-flow analysis. In Proceedings of the first ACM SIGPLAN and IFIP Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New Haven, Connecticut, June 1991. To appear in the SIGPLAN Notices.

    Google Scholar 

  43. D. A. Smith. Partial evaluation of pattern matching in CLP domains. In Proceedings of the first ACM SIGPLAN and IFIP Symposium on Partial Evaluation and Semantics-Based Program Manipulation, New Haven, Connecticut, June 1991. To appear in the SIGPLAN Notices.

    Google Scholar 

  44. G. L. Steele, Jr. Rabbit: A compiler for Scheme. Technical Report AI-TR-474, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1978.

    Google Scholar 

  45. V. F. Turchin. The concept of a supercompiler. ACM Transactions on Programming Languages and Systems, 8(3):292–325, 1986.

    Google Scholar 

  46. P. Wadler. Deforestation: Transforming programs to eliminate trees. In H. Ganzinger, editor, ESOP'88, 2 nd European Symposium on Programming, volume 300 of Lecture Notes in Computer Science. Springer-Verlag, 1988.

    Google Scholar 

  47. P. Wadler. Theorems for free! In FPCA'89, 4 th International Conference on Functional Programming Languages and Computer Architecture, pages 347–359. ACM Press, 1989.

    Google Scholar 

  48. M. Wand. Continuation-based program transformation strategies. Journal of the ACM, 27(1):164–180, January 1980.

    Google Scholar 

  49. M. Wand. From interpreter to compiler: A representational derivation. In H. Ganzinger and N. D. Jones, editors, Programs as Data Objects, volume 217 of Lecture Notes in Computer Science, pages 306–324, 1985.

    Google Scholar 

  50. D. Weise and E. Ruf. Computing types during program specialization. Technical Report 441, Stanford University, Stanford, USA, August 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Yale University, P.O. Box 2158, 06520, New Haven, CT, USA

    Charles Consel

  2. Department of Computing and Information Sciences, Kansas State University, 66506, Manhattan, KS, USA

    Olivier Danvy

Authors
  1. Charles Consel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Olivier Danvy
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

John Hughes

Rights and permissions

Reprints and permissions

Copyright information

© 1991 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Consel, C., Danvy, O. (1991). For a better support of static data flow. In: Hughes, J. (eds) Functional Programming Languages and Computer Architecture. FPCA 1991. Lecture Notes in Computer Science, vol 523. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3540543961_24

Download citation

  • DOI: https://doi.org/10.1007/3540543961_24

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-54396-1

  • Online ISBN: 978-3-540-47599-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation