Entry VanHentenryck: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{VanHentenryck: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",
  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 =      "Thu May 13 12:37:27 MDT 1999",
  bibsource =    "http://www.acm.org/pubs/contents/proceedings/pldi/178243/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/178243/p337-van_hentenryck/",
  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,
  annote =       "Published as part of the Proceedings of PLDI'94.",
  classification = "C4240 (Programming and algorithm theory); C6110L
                 (Logic programming); C6120 (File organisation); C6140D
                 (High level languages)",
  conflocation = "Orlando, FL, USA; 20-24 June 1994",
  conftitle =    "ACM SIGPLAN '94 Conference on Programming Language
                 Design and Implementation (PLDI)",
  corpsource =   "Brown Univ., Providence, RI, USA",
  keywords =     "abstract interpretation; algorithms; built-in
                 predicates; compact representation; computation;
                 computation time; data structures; disjunctive rational
                 trees; equality constraints; generic fixpoint
                 algorithm; generic pattern domain; high-performance
                 compilers; languages; logic programming; medium-sized
                 programs; performance; PROLOG; Prolog; recursive types;
                 sophisticated type inference system; structural
                 information; structural information equality
                 constraints; type analysis; type analysis system; type
                 graphs; type theory",
  sponsororg =   "ACM",
  subject =      "{\bf D.3.4} Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4} Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 F.3.3} Theory of Computation, LOGICS AND MEANINGS OF
                 PROGRAMS, Studies of Program Constructs, Type
                 structure. {\bf F.4.1} Theory of Computation,
                 MATHEMATICAL LOGIC AND FORMAL LANGUAGES, Mathematical
                 Logic. {\bf D.3.2} Software, PROGRAMMING LANGUAGES,
                 Language Classifications, Prolog.",
  treatment =    "P Practical",
}

Related entries