Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Traditional flow analysis techniques, such as the ones typically employed by optimising Fortran compilers, do not work for Scheme-like languages. This paper presents a flow analysis technique --- control flow analysis --- which is applicable to Scheme-like languages. As a demonstration application, the information gathered by control flow analysis is used to perform a traditional flow analysis problem, induction variable elimination. Extensions and limitations are discussed.The techniques presented in this paper are backed up by working code. They are applicable not only to Scheme, but also to related languages, such as Common Lisp and ML.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: J. Michael Ashley , R. Kent Dybvig, A practical and flexible flow analysis for higher-order languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.845-868, July 1998 [doi>10.1145/291891.291898]
• 3: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 4: Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
• 5: Alain Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications (extended version). Research Report LIX/RR/90/11, LIX, Ecole Polytechnique, 91128 Palaiseau Cedex, France.
• 6: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States [doi>10.1145/155090.155113]
• 7: Nevin Heintze , David McAllester, Linear-time subtransitive control flow analysis, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.261-272, June 16-18, 1997, Las Vegas, Nevada, United States [doi>10.1145/258915.258939]
• 8: Neil D. Jones, Flow Analysis of Lambda Expressions (Preliminary Version), Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.114-128, July 13-17, 1981
• 9: Richard Andrews Kelsey, Compilation by program transformation, 1989
• 10: Richard A. Kelsey, A correspondence between continuation passing style and static single assignment form, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.13-22, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/202529.202532]
• 11: David Andrew Kranz , Paul Hudak, Orbit: an optimizing compiler for scheme, 1988
• 12: George C. Necula , Peter Lee, Safe kernel extensions without run-time checking, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.229-243, October 29-November 01, 1996, Seattle, Washington, United States [doi>10.1145/238721.238781]
• 13: Flemming Nielson , Hanne R. Nielson , Chris Hankin, Principles of Program Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 14: Jens Palsberg , Patrick O'Keefe, A type system equivalent to flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.4, p.576-599, July 1995 [doi>10.1145/210184.210187]
• 15: Amr Sabry , Matthias Felleisen, Is continuation-passing useful for data flow analysis?, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.1-12, June 20-24, 1994, Orlando, Florida, United States [doi>10.1145/178243.178244]
• 16: David A. Schmidt, Data flow analysis is model checking of abstract interpretations, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.38-48, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268950]
• 17: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 18: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 19: Mitchell Wand , Igor Siveroni, Constraint systems for useless variable elimination, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.291-302, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292567]
• 20: J. B. Wells , Allyn Dimock , Robert Muller , Franklyn Turbak, A calculus with polymorphic and polyvariant flow types, Journal of Functional Programming, v.12 n.3, p.183-227, May 2002 [doi>10.1017/S0956796801004245]
• 21: Andrew K. Wright , Suresh Jagannathan, Polymorphic splitting: an effective polyvariant flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.166-207, Jan. 1998 [doi>10.1145/271510.271523]
• 22: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 23: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 24: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 25: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 26: {Rabbit} Guy L. Steele. Rabbit: A Compiler for Scheme. AI-TR-474. MIT AI Lab (Cambridge, May 1978).
• 27: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States [doi>10.1145/12276.13333]
• 28: {LetS} Waters, Richard C. LETS: an Expressional Loop Notation. AI Memo 680. MIT AI Lab (Cambridge, October 1982).
• 29: {YLoop} Online documentation for the T3 implementation of the Yloop package is distributed by its current maintainer: Prof. Chris Riesbeck, Yale CS Dept. ([e-mail]).
• 30: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• 31: {Hudak2} Hudak, Paul. Collecting Interpretations of Expressions (Preliminary Version). Research Report YALEU/DCS/RR-497. Yale University (August 1986).
• 32: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]