Entry Sabry:1994:CPU from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Sabry:1994:CPU,
  author =       "Amr Sabry and Matthias Felleisen",
  title =        "Is Continuation-Passing Useful for Data Flow
                 Analysis?",
  journal =      j-SIGPLAN,
  volume =       "29",
  number =       "6",
  pages =        "1--12",
  month =        jun,
  year =         "1994",
  CODEN =        "SINODQ",
  DOI =          "http://doi.acm.org/10.1145/178243.178244",
  ISBN =         "0-89791-598-4",
  ISBN-13 =      "978-0-89791-598-4",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Wed Jun 18 16:26:55 MDT 2008",
  bibsource =    "http://portal.acm.org/;
                 http://www.acm.org/pubs/contents/proceedings/pldi/178243/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/178243/p1-sabry/",
  abstract =     "The widespread use of the continuation-passing style
                 (CPS) transformation in compilers, optimizers, abstract
                 interpreters, and partial evaluators reflects a common
                 belief that the transformation has a positive effect on
                 the analysis of programs. Investigations by Nielson
                 [13] and Burn/Filho [5,6] support, to some degree, this
                 belief with theoretical results. However, they do not
                 pinpoint the source of increased abstract information
                 and do not explain the observation of many people that
                 continuation-passing confuses some conventional data
                 flow analyses. To study the impact of the CPS
                 transformation on program analysis, we derive three
                 canonical data flow analyzers for the core of an
                 applicative higher-order programming language. The
                 first analyzer is based on a direct semantics of the
                 language, the second on a continuation-semantics of the
                 language, and the last on the direct semantics of CPS
                 terms. All analyzers compute the control flow graph of
                 the source program and hence our results apply to a
                 large class of data flow analyses. A comparison of the
                 information gathered by our analyzers establishes the
                 following points: 1. The results of a direct analysis
                 of a source program are {\em incomparable\/} to the
                 results of an analysis of the equivalent CPS program.
                 In other words, the translation of the source program
                 to a CPS version may increase or decrease static
                 information. The gain of information occurs in
                 non-distributive analyses and is solely due to the {\em
                 duplication\/} of the analysis of the continuation. The
                 loss of information is due to the confusion of distinct
                 procedure returns. 2. The analyzer based on the
                 continuation semantics produces more accurate results
                 than both direct analyzers, but again only in
                 non-distributive analyses due to the {\em
                 duplication\/} of continuations along every execution
                 path. However, when the analyzer explicitly accounts
                 for looping constructs, the results of the semantic-CPS
                 analysis are no longer computable. In view of these
                 results, we argue that, in practice, a direct data flow
                 analysis that relies on some amount of duplication
                 would be as satisfactory as a CPS analysis.",
  acknowledgement = ack-nhfb,
  annote =       "Published as part of the Proceedings of PLDI'94.",
  classification = "C6110 (Systems analysis and programming); C6150G
                 (Diagnostic, testing, debugging and evaluating
                 systems)",
  conflocation = "Orlando, FL, USA; 20-24 June 1994",
  conftitle =    "ACM SIGPLAN '94 Conference on Programming Language
                 Design and Implementation (PLDI)",
  corpsource =   "Dept. of Comput. Sci., Rice Univ., Houston, TX, USA",
  keywords =     "algorithms; applicative higher-order programming
                 language; canonical data flow analyzers;
                 continuation-passing style; continuation-semantics;
                 data flow analysis; design; direct semantics;
                 languages; program compilers; program testing; systems
                 analysis",
  sponsororg =   "ACM",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4} Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 D.3.4} Software, PROGRAMMING LANGUAGES, Processors,
                 Interpreters. {\bf D.3.2} Software, PROGRAMMING
                 LANGUAGES, Language Classifications, Applicative
                 (functional) languages. {\bf F.4.1} Theory of
                 Computation, MATHEMATICAL LOGIC AND FORMAL LANGUAGES,
                 Mathematical Logic, Lambda calculus and related
                 systems.",
  treatment =    "T Theoretical or Mathematical",
}

Related entries