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

research-article

FlowSpec: declarative dataflow analysis specification

Authors:

Eelco VisserAuthors Info & Claims

SLE 2017: Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering

Pages 221 - 231

https://doi.org/10.1145/3136014.3136029

Published: 23 October 2017 Publication History

Abstract

We present FlowSpec, a declarative specification language for the domain of dataflow analysis. FlowSpec has declarative support for the specification of control flow graphs of programming languages, and dataflow analyses on these control flow graphs. We define the formal semantics of FlowSpec, which is rooted in Monotone Frameworks. We also discuss a prototype implementation of the language, built in the Spoofax Language Workbench. Finally, we evaluate the expressiveness and conciseness of the language with two case studies. These case studies are analyses for Green-Marl, an industrial, domain-specific language for graph processing. The first case study is a classical dataflow analysis, scaled to this full language. The second case study is a domain-specific analysis of Green-Marl.

References

[1]

Martin Bravenboer and Yannis Smaragdakis. 2009. Strictly declarative specification of sophisticated points-to analyses. In Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2009, Shail Arora and Gary T. Leavens (Eds.). ACM, 243–262.

Digital Library

[2]

Martin Bravenboer, Arthur van Dam, Karina Olmos, and Eelco Visser. 2006. Program Transformation with Scoped Dynamic Rewrite Rules. Fundamenta Informaticae 69, 1-2 (2006), 123–178.

Digital Library

[3]

Torbjörn Ekman and Görel Hedin. 2007. The JastAdd system - modular extensible compiler construction. Science of Computer Programming 69, 1-3 (2007), 14–26.

Digital Library

[4]

J. Gosling, B. Joy, G. Steele, and G. Bracha. 2005. The Java Language Specification (third edition ed.). Prentice Hall PTR, Boston, Mass.

[5]

Görel Hedin. 2000. Reference Attributed Grammars. Informatica (Slovenia) 24, 3 (2000).

[6]

Mark Hills. 2014. Streamlining Control Flow Graph Construction with DCFlow. In Software Language Engineering - 7th International Conference, SLE 2014, Västeras, Sweden, September 15-16, 2014. Proceedings (Lecture Notes in Computer Science), Benoît Combemale, David J. Pearce, Olivier Barais, and Jurgen J. Vinju (Eds.), Vol. 8706. Springer, 322–341.

[7]

Sungpack Hong, Hassan Chafi, Eric Sedlar, and Kunle Olukotun. 2012. GreenMarl: a DSL for easy and efficient graph analysis. In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2012, London, UK, March 3-7, 2012, Tim Harris and Michael L. Scott (Eds.). ACM, 349–362.

Digital Library

[8]

Susan Horwitz, Alan J. Demers, and Tim Teitelbaum. 1987. An Efficient General Iterative Algorithm for Dataflow Analysis. Acta Informatica 24, 6 (1987), 679–694.

Digital Library

[9]

Martin Jourdan and Didier Parigot. 1990. Techniques for Improving Grammar Flow Analysis. In ESOP 90, 3rd European Symposium on Programming, Copenhagen, Denmark, May 15-18, 1990, Proceedings (Lecture Notes in Computer Science), Neil D. Jones (Ed.), Vol. 432. Springer, 240–255.

[10]

John B. Kam and Jeffrey D. Ullman. 1976. Global Data Flow Analysis and Iterative Algorithms. J. ACM 23, 1 (1976), 158–171.

Digital Library

[11]

John B. Kam and Jeffrey D. Ullman. 1977. Monotone Data Flow Analysis Frameworks. Acta Informatica 7 (1977), 305–317.

Digital Library

[12]

Lennart C. L. Kats, Anthony M. Sloane, and Eelco Visser. 2009. Decorated Attribute Grammars: Attribute Evaluation Meets Strategic Programming. In Compiler Construction, 18th International Conference, CC 2009, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2009, York, UK, March 22-29, 2009. Proceedings (Lecture Notes in Computer Science), Oege de Moor and Michael I. Schwartzbach (Eds.), Vol. 5501. Springer, 142–157.

Digital Library

[13]

Lennart C. L. Kats and Eelco Visser. 2010. The Spoofax language workbench: rules for declarative specification of languages and IDEs. In Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2010, William R. Cook, Siobhán Clarke, and Martin C. Rinard (Eds.). ACM, Reno/Tahoe, Nevada, 444–463.

Digital Library

[14]

Gary A. Kildall. 1973. A Unified Approach to Global Program Optimization. In POPL. 194–206.

Digital Library

[15]

Paul Klint, Tijs van der Storm, and Jurgen J. Vinju. 2009. EASY Metaprogramming with Rascal. In Generative and Transformational Techniques in Software Engineering III - International Summer School, GTTSE 2009, Braga, Portugal, July 6-11, 2009. Revised Papers (Lecture Notes in Computer Science), Joao M. Fernandes, Ralf Lämmel, Joost Visser, and João Saraiva (Eds.), Vol. 6491. Springer, 222–289.

[16]

Donald E. Knuth. 1968. Semantics of Context-Free Languages. Theory Comput. Syst. 2, 2 (1968), 127–145.

[17]

Gabriël D. P. Konat, Lennart C. L. Kats, Guido Wachsmuth, and Eelco Visser. 2012. Declarative Name Binding and Scope Rules. In Software Language Engineering, 5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers (Lecture Notes in Computer Science), Krzysztof Czarnecki and Görel Hedin (Eds.), Vol. 7745. Springer, 311–331.

[18]

Magnus Madsen, Ming-Ho Yee, and Ondrej Lhoták. 2016. From Datalog to flix: a declarative language for fixed points on lattices. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2016, Santa Barbara, CA, USA, June 13-17, 2016, Chandra Krintz and Emery Berger (Eds.). ACM, 194–208.

Digital Library

[19]

Eva Magnusson, Torbjorn Ekman, and Gorel Hedin. 2007. Extending Attribute Grammars with Collection Attributes–Evaluation and Applications. Source Code Analysis and Manipulation, IEEE International Workshop on 0 (2007).

Digital Library

[20]

Eva Magnusson and Görel Hedin. 2007. Circular reference attributed grammars - their evaluation and applications. Science of Computer Programming 68, 1 (2007), 21–37.

Digital Library

[21]

Flemming Nielson, Hanne Riis Nielson, and Chris Hankin. 2005. Principles of program analysis (2. corr. print) . Springer.

Digital Library

[22]

Pierre Néron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. 2015. A Theory of Name Resolution. In Programming Languages and Systems - 24th European Symposium on Programming, ESOP 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015. Proceedings (Lecture Notes in Computer Science), Jan Vitek (Ed.), Vol. 9032. Springer, 205–231.

[23]

Anthony M. Sloane, Matthew Roberts, and Leonard G. C. Hamey. 2014. Respect Your Parents: How Attribution and Rewriting Can Get Along. In Software Language Engineering - 7th International Conference, SLE 2014, Västeras, Sweden, September 15-16, 2014. Proceedings (Lecture Notes in Computer Science), Benoît Combemale, David J. Pearce, Olivier Barais, and Jurgen J. Vinju (Eds.), Vol. 8706. Springer, 191–210.

[24]

Yannis Smaragdakis and George Balatsouras. 2015. Pointer Analysis. Foundations and Trends in Programming Languages 2, 1 (2015), 1–69.

Digital Library

[25]

Jeff Smits. 2016. The Static Semantics of the Green-Marl Graph Analysis Language . Master’s thesis. Delft University of Technology. Advisor(s) Guido Wachsmuth. Available at http://resolver.tudelft.nl/uuid: 4f07cbbb-d017-41e8-aba6-8ff0c19f258d .

[26]

Tamás Szabó, Simon Alperovich, Markus Völter, and Sebastian Erdweg. 2016a. An extensible framework for variable-precision data-flow analyses in MPS. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, ASE 2016, Singapore, September 3-7, 2016, David Lo, Sven Apel, and Sarfraz Khurshid (Eds.). ACM, 870–875.

Digital Library

[27]

Tamás Szabó, Sebastian Erdweg, and Markus Völter. 2016b. IncA: a DSL for the definition of incremental program analyses. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, ASE 2016, Singapore, September 3-7, 2016, David Lo, Sven Apel, and Sarfraz Khurshid (Eds.). ACM, 320–331.

Digital Library

[28]

Emma Söderberg, Torbjörn Ekman, Görel Hedin, and Eva Magnusson. 2013. Extensible intraprocedural flow analysis at the abstract syntax tree level. Science of Computer Programming 78, 10 (2013), 1809–1827.

Digital Library

[29]

Hendrik van Antwerpen, Pierre Néron, Andrew P. Tolmach, Eelco Visser, and Guido Wachsmuth. 2016. A constraint language for static semantic analysis based on scope graphs. In Proceedings of the 2016 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2016, St. Petersburg, FL, USA, January 20 - 22, 2016, Martin Erwig and Tiark Rompf (Eds.). ACM, 49–60.

Digital Library

[30]

Eelco Visser, Guido Wachsmuth, Andrew P. Tolmach, Pierre Néron, Vlad A. Vergu, Augusto Passalaqua, and Gabriël D. P. Konat. 2014. A Language Designer’s Workbench: A One-Stop-Shop for Implementation and Verification of Language Designs. In Onward! 2014, Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, part of SPLASH ’14, Portland, OR, USA, October 20-24, 2014, Andrew P. Black, Shriram Krishnamurthi, Bernd Bruegge, and Joseph N. Ruskiewicz (Eds.). ACM, 95–111.

Digital Library

[31]

Harald Vogt, S. Doaitse Swierstra, and Matthijs F. Kuiper. 1989. HigherOrder Attribute Grammars. In PLDI. 131–145.

[32]

Eric Van Wyk, Derek Bodin, Jimin Gao, and Lijesh Krishnan. 2010. Silver: An extensible attribute grammar system. Science of Computer Programming 75, 1-2 (2010), 39–54.

Digital Library

Cited By

Deknop CFabry JMens KZaytsev V(2022)Generating Customised Control Flow Graphs for Legacy Languages with Semi-Parsing2022 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME55016.2022.00072(523-532)Online publication date: Oct-2022
https://doi.org/10.1109/ICSME55016.2022.00072
Misteli PAguiar AChiba SBoix E(2020)Towards language-parametric refactoringsCompanion Proceedings of the 4th International Conference on Art, Science, and Engineering of Programming10.1145/3397537.3398476(213-214)Online publication date: 23-Mar-2020
https://dl.acm.org/doi/10.1145/3397537.3398476
Cerny TSvacina JDas DBushong VBures MTisnovsky PFrajtak KShin DHuang J(2020)On Code Analysis Opportunities and Challenges for Enterprise Systems and MicroservicesIEEE Access10.1109/ACCESS.2020.30199858(159449-159470)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3019985

Index Terms

FlowSpec: declarative dataflow analysis specification
1. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Domain specific languages

Recommendations

On development of static analysis tools for string-embedded languages
CEE-SECR '15: Proceedings of the 11th Central & Eastern European Software Engineering Conference in Russia

Some programs can produce string expressions with embedded code in other programming languages while running. This embedded code should be syntactically correct as it is typically executed by some subsystem. A program in Java language that builds and ...
Declarative specification of indentation rules: a tooling perspective on parsing and pretty-printing layout-sensitive languages
SLE 2018: Proceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering

In layout-sensitive languages, the indentation of an expression or statement can influence how a program is parsed. While some of these languages (e.g., Haskell and Python) have been widely adopted, there is little support for software language ...
An Applicative Control-Flow Graph Based on Huet's Zipper

We are using ML to build a compiler that does low-level optimization. To support optimizations in classic imperative style, we built a control-flow graph using mutable pointers and other mutable state in the nodes. This decision proved unfortunate: the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SLE 2017: Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering

October 2017

267 pages

ISBN:9781450355254

DOI:10.1145/3136014

General Chair:
Benoit Combemale
University of Rennes 1, France
,
Program Chairs:
Marjan Mernik
University of Maribor, Slovenia
,
Bernhard Rumpe
RWTH Aachen University, Germany

Copyright © 2017 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 the author(s) 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].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGAda: ACM Special Interest Group on Ada Programming Language

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '17

Sponsor:

SIGPLAN

SPLASH '17: Conference on Systems, Programming, Languages, and Applications: Software for Humanity

October 23 - 24, 2017

BC, Vancouver, Canada

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
289
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Deknop CFabry JMens KZaytsev V(2022)Generating Customised Control Flow Graphs for Legacy Languages with Semi-Parsing2022 IEEE International Conference on Software Maintenance and Evolution (ICSME)10.1109/ICSME55016.2022.00072(523-532)Online publication date: Oct-2022
https://doi.org/10.1109/ICSME55016.2022.00072
Misteli PAguiar AChiba SBoix E(2020)Towards language-parametric refactoringsCompanion Proceedings of the 4th International Conference on Art, Science, and Engineering of Programming10.1145/3397537.3398476(213-214)Online publication date: 23-Mar-2020
https://dl.acm.org/doi/10.1145/3397537.3398476
Cerny TSvacina JDas DBushong VBures MTisnovsky PFrajtak KShin DHuang J(2020)On Code Analysis Opportunities and Challenges for Enterprise Systems and MicroservicesIEEE Access10.1109/ACCESS.2020.30199858(159449-159470)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3019985

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents