More Web Proxy on the site http://driver.im/

article

Free access

An equational framework for the flow analysis of higher order functional programs

Authors:

Dan Stefanescu,

Yuli ZhouAuthors Info & Claims

ACM SIGPLAN Lisp Pointers, Volume VII, Issue 3

Pages 318 - 327

https://doi.org/10.1145/182590.182497

Published: 01 July 1994 Publication History

Abstract

We present a simple method for the general flow analysis of high-order functional programs. The method computes an abstraction of the program's runtime environment via a system of monotonic equations. As the environment can grow unbounded, we exploit patterns in the program's control structure (i.e., the call-tree) to determine some static partition of the environment, and merge points in the environment belonging to the same equivalent-class. High order functions are handled by embedding control information into closures. The method is proven correct with respect to a rewriting system based operational semantics. Various implementation issues are also considered.

References

[1]

Alfred V. Aho and Ravi Sethi and Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools. Addison- Wesley Publishing Company, 1987.

Digital Library

[2]

Andor~ Rond~rf Automatic autoprotection of higher Order Recursive Equations Proc. ESOP'90, Springer Verlag, 1990

Digital Library

[3]

Zena M. Ariola and Arvind A Syntactic Approach to Program Transj:ormat,ons. Proc. of the Symposium on Partial Evaluation and Semantic-Based Program Manipulation PEPM'91. SIGPLAN Notices, Vol 26 No. 9, 116-129.

Digital Library

[4]

Gebreselassie Baraki. A Note on Abstract Interpretation of Polymorphic Functions. 5th ACM Conference on FunctionM Languages and Computer Architecture. Lecture Notes in Computer Science Vol 523, August 1991.

Digital Library

[5]

Francois Bourdoncle Interprocedural Abstract Interpretation of Block Structured Languages with Nested Procedures, Ahaszng and Recurszvity. Proc. International Workshop PLILP'90. Lecture Notes in Computer Science Vol. 456, Springer-Verlag.

Digital Library

[6]

Francois Bourdoncle Abstract Interpretation by Dynamic Partitioning. J. Functional Programming 2 (4): 407-435, October 1992.

[7]

Francois Bourdoncle Efficient chaotic iteration strategies with widenings Proceedings of the International Conference on Formal Methods in Programming and their Applications, Lecture Notes in Computer Science 735, Springer Verlag, 1993

[8]

G. Burns and C. Hankin and S. Abramsky. StrzctheSS Analysis for Higher-Order Functions. In Science of Computer Programming, 7:249-278, 1986.

[9]

T. Cheatham, H. Gao, and D. Stefanescu A Suite of Analysis Tools Based on a General Purpose Abstract Interpreter, Proceedings of the International Conference on Compiler Construction, Edinburgh, April 1994

Digital Library

[10]

Thomas E. Cheatham, Jr. and Dan Stefanescu A Suite of Optimizers Based on Abstract Interpretatgon, PEPM'92, San Francisco, June 1992

[11]

Charles Consel Polyvariant Binding-Time Analysis For Applicative Languages, PEPM'93, Copenhagen, June 1993

Digital Library

[12]

Patrick Cousot and Radhia Cousot Abstract interpretation: a unified lattice model for statzc analysis of programs by construction of approximate fixpoints, Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, pages 238-252, 1977.

Digital Library

[13]

Patrick Cousot and Radhia Cousot Static determination of dynamic properties of recursive procedures IFIP Conference on Formal Description of Programming Concepts, vol 1, pages 237-277, Saint Andrews, 1977

[14]

Patrick Cousot Asynchronous iterative methods for solving a fixed point system monotone equations in a complete lattice, Rapport de Recherche No. 88, Laboratoire IMAG, Grenoble, Sept. 1977.

[15]

Patrick Cousot and Radhia Cousot Systematic design of program analysis frameworks Conference Record of the Sixth ACM Symposium on Principles of Programming Languages, San Antonio, 1979

Digital Library

[16]

Patrick Cousot Semantic foundations o/program analysis In S.S.Muchnick and N.D.Jones, editors, Program Flow Analysis: Theory and Applications, chapter 10, pg. 303-342, Prentice-Hall, 1981

[17]

Alain Deutsch. On Determining Lzfetzme and Ahaszng of Dynamically Allocated Data in Higher. Order Functional Applications. Proc. 17th Annum ACM Symp. on Principles of Programming Languages, 157-168, San Francisco, Jan. 1990.

Digital Library

[18]

AlaJn Deutsch. A Storeless Model o/Aliasing and Its Abstractions Using Finite Representations o/ Right- Regular Equivalence Relations Proceedings of the 1992 International Conference on Computer Languages, 2- 13, Oakland, California, April, 1992.

[19]

Samuel Eilenberg Automata, Languages and Machines, volume A, Academic Press, 1974

Digital Library

[20]

John Hughes. Abstract Interpretat,on of First-order Polyrnorphic Functions. Technical Report 89/R4, University of Glasgow, Dept. of Computing Science, 1988.

[21]

S. Hunt and C. Hanldn. Fixed Points and Frontiers: A New Perspective. J. of Functional Programming, 1:91- 120, 1991.

[22]

Neff Jones and Steven Muchnick A Flexible Approach to intraprocedural Data Flow Analysis and Programs with Recursive Data Structures, Conference l~ecord of the Ninth ACM Symposium on Principles of Programming Languages, pages 66-74, 1982.

Digital Library

[23]

Nell Jones and Alan Mycroft Data Flow Analysis of Applicative Programs Using Minimal Functions Graphs: Abridged Version, Conference Record of the Thirteenth ACM Symposium on Principles of Programming Languages, pages 296-306, 1986.

Digital Library

[24]

Atty Kanamori and Daniel Weise An Empirical study of an Abstract Interpretation o/ Scheme Programs,Technical Report, Stanford University, April 1992.

Digital Library

[25]

T. Koo and P. Mishra. Strictness Analys~s: A New Perspective Based on Type inference. Proc. of the ACM Conference on Functional Programming Languages and Computer Architecture, 260-272, 1989.

Digital Library

[26]

Alan Mycroft Abstract Interpretations and Optimizing Transformatzons /or Applicative Programs, Ph.D. Thesis, University of Edinburgh, Scotland, 1981.

[27]

Jens Palsberg and Michael I. Schwartzbach Binding Time Analysis: Abstract Interpretation versus Type Inference, Technical Report, Aarhus University, 1992.

[28]

M. $harir and A. Pnueli. Two Approaches to Interprocedural Data Flow Analysis. In: Muchnick and Jones (eds), Program Flow Analysis, Theory and Applications. Prentice-Hall, 189-233, 1981.

[29]

Olin Shivers Control Flow Analysis in Scheme ACM SIGPLAN '88 Conference on Programming Language Design and Implementation, Atlanta CA, June 22-24, 1988.

Digital Library

[30]

Olin Shivers Control Flow Analysis of Higher Order Languages or Taming Lambda, Technical Report CMU- CS-91-145, Carnegie Mellon University, May 1991.

[31]

Dan Stefanescu and Yuli Zhou An Equational Framework for the Abstract Flow Analysis of Functional Programs, Technical Report, Harvard University, J~nuary 1993.

[32]

Mitchell Wand and Paul Steclder Selective and Lightweight Closure Conversion,Conference Record of the 21st ACM Symposium on Principles of Program~ ming Languages, pages 435-445, 1994.

Digital Library

Cited By

Midtgaard J(2012)Control-flow analysis of functional programsACM Computing Surveys (CSUR)10.1145/2187671.218767244:3(1-33)Online publication date: 14-Jun-2012
https://dl.acm.org/doi/10.1145/2187671.2187672
Midtgaard J(2012)Control-flow analysis of functional programsACM Computing Surveys10.1145/2187671.218767244:3(1-33)Online publication date: 14-Jun-2012
https://dl.acm.org/doi/10.1145/2187671.2187672
Jones NAndersen N(2007)Flow analysis of lazy higher-order functional programsTheoretical Computer Science10.1016/j.tcs.2006.12.030375:1-3(120-136)Online publication date: 20-Apr-2007
https://dl.acm.org/doi/10.1016/j.tcs.2006.12.030
Show More Cited By

Index Terms

An equational framework for the flow analysis of higher order functional programs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Control structures
      2. Language types
        Functional languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics
      1. Operational semantics

Recommendations

An equational framework for the flow analysis of higher order functional programs
LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programming

We present a simple method for the general flow analysis of high-order functional programs. The method computes an abstraction of the program's runtime environment via a system of monotonic equations. As the environment can grow unbounded, we exploit ...
Flow analysis of lazy higher-order functional programs

In recent years much interest has been shown in a class of functional languages including HASKELL, lazy ML, SASL/KRC/MIRANDA, ALFL, ORWELL, and PONDER. It has been seen that their expressive power is great, programs are compact, and program manipulation ...
Verifying higher-order functional programs with pattern-matching algebraic data types
POPL '11

Type-based model checking algorithms for higher-order recursion schemes have recently emerged as a promising approach to the verification of functional programs. We introduce pattern-matching recursion schemes (PMRS) as an accurate model of computation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Lisp Pointers

ACM SIGPLAN Lisp Pointers Volume VII, Issue 3

July-Sept. 1994

327 pages

ISSN:1045-3563

DOI:10.1145/182590

Editor:
Robert R. Kessler
Univ. of Utah, Salt Lake City

Issue’s Table of Contents

LFP '94: Proceedings of the 1994 ACM conference on LISP and functional programming
July 1994
327 pages
ISBN:0897916433
DOI:10.1145/182409
Chairman:
Robert R. Kessler
Univ. of Utah, Salt Lake City

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1994

Published in SIGPLAN-LISPPOINTERS Volume VII, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
416
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)7

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Midtgaard J(2012)Control-flow analysis of functional programsACM Computing Surveys (CSUR)10.1145/2187671.218767244:3(1-33)Online publication date: 14-Jun-2012
https://dl.acm.org/doi/10.1145/2187671.2187672
Midtgaard J(2012)Control-flow analysis of functional programsACM Computing Surveys10.1145/2187671.218767244:3(1-33)Online publication date: 14-Jun-2012
https://dl.acm.org/doi/10.1145/2187671.2187672
Jones NAndersen N(2007)Flow analysis of lazy higher-order functional programsTheoretical Computer Science10.1016/j.tcs.2006.12.030375:1-3(120-136)Online publication date: 20-Apr-2007
https://dl.acm.org/doi/10.1016/j.tcs.2006.12.030
Cheatham TFahmy AStefanescu D(2005)General purpose optimization technologyLanguages and Compilers for Parallel Computing10.1007/BFb0014215(422-433)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0014215
Schmidt D(2005)Natural-semantics-based abstract interpretation (preliminary version)Static Analysis10.1007/3-540-60360-3_28(1-18)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-60360-3_28
Cheatham T(2005)Models, languages, and compiler technology for high performance computersMathematical Foundations of Computer Science 199410.1007/3-540-58338-6_55(1-26)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-58338-6_55
Cheatham TGao HStefanescu D(2005)A suite of analysis tools based on a general purpose abstract interpreterCompiler Construction10.1007/3-540-57877-3_13(188-202)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57877-3_13
Palsberg JPavlopoulou C(2001)From Polyvariant flow information to intersection and union typesJournal of Functional Programming10.1017/S095679680100394X11:3(263-317)Online publication date: 1-May-2001
https://dl.acm.org/doi/10.1017/S095679680100394X
Tip FPalsberg J(2000)Scalable propagation-based call graph construction algorithmsACM SIGPLAN Notices10.1145/354222.35319035:10(281-293)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1145/354222.353190
Tip FPalsberg JRosson MLea D(2000)Scalable propagation-based call graph construction algorithmsProceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications10.1145/353171.353190(281-293)Online publication date: 1-Oct-2000
https://dl.acm.org/doi/10.1145/353171.353190
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents