Entry Hentenryck:1994:TAP 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{Hentenryck:1994:TAP,
  author =       "P. Van Hentenryck and A. Cortesi and B. Le Charlier",
  title =        "Type analysis of {Prolog} using type graphs",
  journal =      j-SIGPLAN,
  volume =       "29",
  number =       "6",
  pages =        "337--348",
  month =        jun,
  year =         "1994",
  CODEN =        "SINODQ",
  DOI =          "http://doi.acm.org/10.1145/178243.178479",
  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/",
  abstract =     "Type analysis of Prolog is of primary importance for
                 high-performance compilers, since type information may
                 lead to better indexing and to sophisticated
                 specializations of unification and built-in predicates
                 to name a few. However, these optimizations often
                 require a sophisticated type inference system capable
                 of inferring disjunctive and recursive types and hence
                 expensive in computation time. The purpose of this
                 paper is to describe a type analysis system for Prolog
                 based on abstract interpretation and type graphs (i.e.
                 disjunctive rational trees) with this functionality.
                 The system (about 15,000 lines of C) consists of the
                 combination of a generic fixpoint algorithm, a generic
                 pattern domain, and a type graph domain. The main
                 contribution of the paper is to show that this approach
                 can be engineered to be practical for medium-sized
                 programs without sacrificing accuracy. The main
                 technical contributions to achieve this result are (1)
                 a novel widening operator for type graphs which appears
                 to be accurate and effective in keeping the sizes of
                 the graphs, and hence the computation time, reasonably
                 small; (2) the use of the generic pattern domain to
                 obtain a compact representation of equality constraints
                 between subterms and to factor out sure structural
                 information.",
  acknowledgement = ack-nhfb,
}

Related entries