DROPS

Document

DOI: 10.4230/LIPIcs.ECOOP.2016.19

Higher-Order Demand-Driven Program Analysis

Authors: Zachary Palmer and Scott F. Smith

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract

We explore a novel approach to higher-order program analysis that brings ideas of on-demand lookup from first-order CFL-reachability program analyses to higher-order programs. The analysis needs to produce only a control-flow graph; it can derive all other information including values of variables directly from the graph. Several challenges had to be overcome, including how to build the control-flow graph on-the-fly and how to deal with non-local variables in functions. The resulting analysis is flow- and context-sensitive with a provable polynomial-time bound. The analysis is formalized and proved correct and terminating, and an initial implementation is described.

Cite as

Zachary Palmer and Scott F. Smith. Higher-Order Demand-Driven Program Analysis. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 19:1-19:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{palmer_et_al:LIPIcs.ECOOP.2016.19,
  author =	{Palmer, Zachary and Smith, Scott F.},
  title =	{{Higher-Order Demand-Driven Program Analysis}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{19:1--19:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.19},
  URN =		{urn:nbn:de:0030-drops-61132},
  doi =		{10.4230/LIPIcs.ECOOP.2016.19},
  annote =	{Keywords: functional programming, program analysis, polynomial-time, demand-driven, flow-sensitive, context-sensitive}
}

Document

DOI: 10.4230/DARTS.2.1.9

Higher-Order Demand-Driven Program Analysis (Artifact)

Authors: Leandro Facchinetti, Zachary Palmer, and Scott F. Smith

Published in: DARTS, Volume 2, Issue 1, Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract

This artifact is a proof-of-concept implementation of DDPA, an on-demand program analysis for higher-order functional programs. The implementation, written in OCaml, includes a parser, evaluator, and DDPA analysis for the language defined in the companion paper (including the proper record semantics extension). The analysis may be performed using different levels of precision as specified by the user and is capable of rendering the control flow graphs and pushdown systems using the GraphViz language DOT. This artifact was used to verify the conclusions of the companion paper and produces visualizations matching those figures in the companion paper's overview.

Cite as

Leandro Facchinetti, Zachary Palmer, and Scott F. Smith. Higher-Order Demand-Driven Program Analysis (Artifact). In Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016). Dagstuhl Artifacts Series (DARTS), Volume 2, Issue 1, pp. 9:1-9:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{facchinetti_et_al:DARTS.2.1.9,
  author =	{Facchinetti, Leandro and Palmer, Zachary and Smith, Scott F.},
  title =	{{Higher-Order Demand-Driven Program Analysis (Artifact)}},
  pages =	{9:1--9:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2016},
  volume =	{2},
  number =	{1},
  editor =	{Facchinetti, Leandro and Palmer, Zachary and Smith, Scott F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.2.1.9},
  URN =		{urn:nbn:de:0030-drops-61304},
  doi =		{10.4230/DARTS.2.1.9},
  annote =	{Keywords: program analysis, polynomial, demand-driven, flow-sensitive, context-sensitive}
}

Search Results

Documents authored by Palmer, Zachary

Higher-Order Demand-Driven Program Analysis

Abstract

Cite as

Higher-Order Demand-Driven Program Analysis (Artifact)

Abstract

Cite as

Thanks for your feedback!

Could not send message