%%% -*-BibTeX-*-
%%% ====================================================================
%%%  BibTeX-file{
%%%     author          = "Nelson H. F. Beebe",
%%%     version         = "1.07",
%%%     date            = "07 August 2013",
%%%     time            = "08:51:41 MDT",
%%%     filename        = "loplas.bib",
%%%     address         = "University of Utah
%%%                        Department of Mathematics, 110 LCB
%%%                        155 S 1400 E RM 233
%%%                        Salt Lake City, UT 84112-0090
%%%                        USA",
%%%     telephone       = "+1 801 581 5254",
%%%     FAX             = "+1 801 581 4148",
%%%     URL             = "http://www.math.utah.edu/~beebe",
%%%     checksum        = "30237 2145 10950 111439",
%%%     email           = "beebe at math.utah.edu, beebe at acm.org,
%%%                        beebe at computer.org (Internet)",
%%%     codetable       = "ISO/ASCII",
%%%     keywords        = "bibliography, BibTeX, ACM Letters on
%%%                        Programming Languages and Systems, LOPLAS",
%%%     license         = "public domain",
%%%     supported       = "yes",
%%%     docstring       = "This is a COMPLETE bibliography of ACM
%%%                        Letters on Programming Languages and Systems
%%%                        (LOPLAS) (CODEN ALPSE8, ISSN 1057-4514
%%%                        (print), 1557-7384 (electronic)).  That
%%%                        journal was published only in 1992 and 1993:
%%%                        it was merged into ACM Transactions on
%%%                        Programming Languages and Systems (TOPLAS) in
%%%                        the May 1994 issue of the latter.
%%%
%%%                        At version 1.07, the year coverage looked
%%%                        like this:
%%%
%%%                             1992 ( 25)     1993 ( 17)
%%%
%%%                             Article:         42
%%%
%%%                             Total entries:  42
%%%
%%%                        The ACM maintains Web pages with journal
%%%                        tables of contents for 1985--1995 at
%%%
%%%                            http://dl.acm.org/citation.cfm?id=J513
%%%                            http://www.acm.org/pubs/contents/journals/loplas/
%%%
%%%                        Those data have been automatically converted
%%%                        to BibTeX form.
%%%
%%%                        Spelling has been verified with the UNIX
%%%                        spell and GNU ispell programs using the
%%%                        exception dictionary stored in the companion
%%%                        file with extension .sok.
%%%
%%%                        BibTeX citation tags are uniformly chosen
%%%                        as name:year:abbrev, where name is the
%%%                        family name of the first author or editor,
%%%                        year is a 4-digit number, and abbrev is a
%%%                        3-letter condensation of important title
%%%                        words. Citation tags were automatically
%%%                        generated by software developed for the
%%%                        BibNet Project.
%%%
%%%                        In this bibliography, entries are sorted in
%%%                        publication order within each journal,
%%%                        using bibsort -byvolume.
%%%
%%%                        The checksum field above contains a CRC-16
%%%                        checksum as the first value, followed by the
%%%                        equivalent of the standard UNIX wc (word
%%%                        count) utility output of lines, words, and
%%%                        characters.  This is produced by Robert
%%%                        Solovay's checksum utility.",
%%%  }
%%% ====================================================================

@Preamble{
  "\input bibnames.sty " #
  "\input path.sty " #
  "\def \TM {${}^{\sc TM}$} " #
  "\hyphenation{
  }"}

%%% ====================================================================
%%% Acknowledgement abbreviations:

@String{ack-nhfb = "Nelson H. F. Beebe,
                    University of Utah,
                    Department of Mathematics, 110 LCB,
                    155 S 1400 E RM 233,
                    Salt Lake City, UT 84112-0090, USA,
                    Tel: +1 801 581 5254,
                    FAX: +1 801 581 4148,
                    e-mail: \path|beebe@math.utah.edu|,
                            \path|beebe@acm.org|,
                            \path|beebe@computer.org| (Internet),
                    URL: \path|http://www.math.utah.edu/~beebe/|"}

%%% ====================================================================
%%% Journal abbreviations:

@String{j-LOPLAS                = "ACM Letters on Programming Languages and
                                  Systems"}

%%% ====================================================================
%%% Bibliography entries, sorted in publication order with
%%% `bibsort -byvol':

@Article{Briggs:1992:CRP,
  author =       "Preston Briggs and Keith D. Cooper and Linda Torczon",
  title =        "Coloring register pairs",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "3--13",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130617",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130617.html",
  abstract =     "Many architectures require that a program use pairs of
                 adjacent registers to hold double-precision
                 floating-point values. Register allocators based on
                 Chaitin's graph-coloring technique have trouble with
                 programs that contain both single-register values and
                 values that require adjacent pairs of registers. In
                 particular, Chaitin's algorithm often produces
                 excessive spilling on such programs. This results in
                 underuse of the register set; the extra loads and
                 stores inserted into the program for spilling also slow
                 execution.\par

                 An allocator based on an {\em optimistic} coloring
                 scheme naturally avoids this problem. Such allocators
                 delay the decision to spill a value until late in the
                 allocation process. This eliminates the over-spilling
                 provoked by adjacent register pairs in Chaitin's
                 scheme.\par

                 This paper discusses the representation of register
                 pairs in a graph coloring allocator. It explains the
                 problems that arise with Chaitin's allocator and shows
                 how the optimistic allocator avoids them. It provides a
                 rationale for determining how to add larger aggregates
                 to the interference graph.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, performance",
  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,
                 Code generation.",
}

@Article{Burke:1992:PEI,
  author =       "Michael Burke and Jong-Deok Choi",
  title =        "Precise and efficient integration of interprocedural
                 alias information into data-flow analysis",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "14--21",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130618",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130618.html",
  abstract =     "Data-flow analysis is a basis for program optimization
                 and parallelizing transformations. The mechanism of
                 passing {\em reference} parameters at call sites
                 generates {\em interprocedural aliases} which
                 complicate this analysis. Solutions have been developed
                 for efficiently computing interprocedural aliases.
                 However, factoring the computed aliases into data-flow
                 information has been mostly overlooked, although
                 improper factoring results in imprecise (conservative)
                 data-flow information. In this document, we describe a
                 mechanism which, in factoring in interprocedural
                 aliases, computes data-flow information more precisely
                 and with less time and space overhead than previous
                 approaches.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Code generation.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers.",
}

@Article{Cooper:1992:USE,
  author =       "Keith D. Cooper and Mary W. Hall and Linda Torczon",
  title =        "Unexpected side effects of inline substitution: a case
                 study",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "22--32",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130619",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130619.html",
  abstract =     "The structure of a program can encode implicit
                 information that changes both the shape and speed of
                 the generated code. Interprocedural transformations
                 like inlining often discard such information; using
                 interprocedural data-flow information as a basis for
                 optimization can have the same effect.\par

                 In the course of a study on inline substitution with
                 commercial FORTRAN compilers, we encountered unexpected
                 performance problems in one of the programs. This paper
                 describes the specific problem that we encountered,
                 explores its origins, and examines the ability of
                 several analytical techniques to help the compiler
                 avoid similar problems.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "experimentation, languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features.",
}

@Article{Dornic:1992:PTS,
  author =       "Vincent Dornic and Pierre Jouvelot and David K.
                 Gifford",
  title =        "Polymorphic time systems for estimating program
                 complexity",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "33--45",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130620",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130620.html",
  abstract =     "We present a new approach to static program analysis
                 that permits each expression in a program to be
                 assigned an execution time estimate. Our approach uses
                 a {\em time system} in conjunction with a conventional
                 type system to compute both the type and the time of an
                 expression. The {\em time} of an expression is either
                 an integer upper bound on the number of ticks the
                 expression will execute, or the distinguished element
                 long that indicates that the expression contains a
                 loop, and thus may run for an arbitrary length of time.
                 Every function type includes a {\em latent time} that
                 is used to communicate its expected execution time from
                 the point of its definition to the points of its use.
                 Unlike previous approaches, a time system works in the
                 presence of first-class functions and separate
                 compilation. In addition, {\em time polymorphism}
                 allows the time of a function to depend on the times of
                 any functions that it takes as arguments. Time
                 estimates are useful when compiling programs for
                 multiprocessors in order to balance the overhead of
                 initiating a concurrent computation against the
                 expected execution time of the computation. The
                 correctness of our time system is proven with respect
                 to a dynamic semantics.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, performance, verification",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.1.3}: Software,
                 PROGRAMMING TECHNIQUES, Concurrent Programming. {\bf
                 D.3.2}: Software, PROGRAMMING LANGUAGES, Language
                 Classifications, Applicative languages. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf F.1.3}: Theory of Computation,
                 COMPUTATION BY ABSTRACT DEVICES, Complexity Classes.",
}

@Article{Johnson:1992:RLR,
  author =       "Ralph E. Johnson",
  title =        "Reducing the latency of a real-time garbage
                 collector",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "46--58",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130621",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130621.html",
  abstract =     "This paper shows how to make the latency of scanning a
                 page in the Appel-Ellis-Li real-time garbage collector
                 be proportional only to the number of object references
                 on a page (the page size), instead of to the sum of the
                 sizes of the objects referenced by the page. This makes
                 the garbage collection algorithm much more suitable for
                 real-time systems.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, measurement, performance",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Dynamic storage management.
                 {\bf C.3}: Computer Systems Organization,
                 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS,
                 Real-time systems.",
}

@Article{McKenney:1992:GPC,
  author =       "Bruce McKenney and Boleslaw K. Szymanski",
  title =        "Generating parallel code for {SIMD} machines",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "59--73",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130622",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130622.html",
  abstract =     "Massively parallel SIMD machines rely on data
                 parallelism usually achieved by a careful hand coding
                 to support program efficiency. This paper describes
                 parallelization of code generated for SIMD machines by
                 the compiler for the Equational Programming Language,
                 EPL. The language supports architecture-independent
                 scientific programming by recurrent equations. The EPL
                 compiler serves as a programming aid for users of
                 parallel machines by automating data partitioning and
                 computation parallelization based on inherent data
                 dependencies. In support of a Connection Machine
                 architecture, the EPL compiler performs horizontal
                 partitioning of the program, a process that selects a
                 dimension of each data structure to be projected along
                 the processor array. Each processor then holds a single
                 instance of that structure and operations along the
                 projected dimension are done in parallel. The paper
                 describes horizontal partitioning, code generation in
                 MPL and efficiency of programs generated for Maspar
                 SIMD machine.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "design, languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Code generation. {\bf C.1.2}: Computer
                 Systems Organization, PROCESSOR ARCHITECTURES, Multiple
                 Data Stream Architectures (Multiprocessors), Connection
                 machines. {\bf D.1.1}: Software, PROGRAMMING
                 TECHNIQUES, Applicative (Functional) Programming. {\bf
                 D.1.3}: Software, PROGRAMMING TECHNIQUES, Concurrent
                 Programming, Parallel programming. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors, Compilers.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf C.1.2}: Computer Systems
                 Organization, PROCESSOR ARCHITECTURES, Multiple Data
                 Stream Architectures (Multiprocessors),
                 Single-instruction-stream, multiple-data-stream
                 processors (SIMD).",
}

@Article{Netzer:1992:WRC,
  author =       "Robert H. B. Netzer and Barton P. Miller",
  title =        "What are race conditions?: {Some} issues and
                 formalizations",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "74--88",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130623",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130623.html",
  abstract =     "In shared-memory parallel programs that use explicit
                 synchronization, {\em race conditions} result when
                 accesses to shared memory are not properly
                 synchronized. Race conditions are often considered to
                 be manifestations of bugs, since their presence can
                 cause the program to behave unexpectedly.
                 Unfortunately, there has been little agreement in the
                 literature as to precisely what constitutes a race
                 condition. Two different notions have been implicitly
                 considered: one pertaining to programs intended to be
                 deterministic (which we call {\em general races}) and
                 the other to nondeterministic programs containing
                 critical sections (which we call {\em data races}).
                 However, the differences between general races and data
                 races have not yet been recognized. This paper examines
                 these differences by characterizing races using a
                 formal model and exploring their properties. We show
                 that two variations of each type of race exist: {\em
                 feasible} general races and data races capture the
                 intuitive notions desired for debugging and {\em
                 apparent} races capture less accurate notions
                 implicitly assumed by most dynamic race detection
                 methods. We also show that locating feasible races is
                 an NP-hard problem, implying that only the apparent
                 races, which are approximations to feasible races, can
                 be detected in practice. The complexity of dynamically
                 locating apparent races depends on the type of
                 synchronization used by the program. Apparent races can
                 be exhaustively located efficiently only for weak types
                 of synchronization that are incapable of implementing
                 mutual exclusion. This result has important
                 implications since we argue that debugging general
                 races requires exhaustive race detection and is
                 inherently harder than debugging data races (which
                 requires only partial race detection). Programs
                 containing data races can therefore be efficiently
                 debugged by locating certain easily identifiable races.
                 In contrast, programs containing general races require
                 more complex debugging techniques.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "design, languages",
  subject =      "{\bf D.2.5}: Software, SOFTWARE ENGINEERING, Testing
                 and Debugging, Debugging aids. {\bf D.3.3}: Software,
                 PROGRAMMING LANGUAGES, Language Constructs and
                 Features, Concurrent programming structures. {\bf
                 D.4.1}: Software, OPERATING SYSTEMS, Process
                 Management, Concurrency. {\bf D.4.1}: Software,
                 OPERATING SYSTEMS, Process Management, Mutual
                 exclusion. {\bf D.4.1}: Software, OPERATING SYSTEMS,
                 Process Management, Synchronization. {\bf D.3.1}:
                 Software, PROGRAMMING LANGUAGES, Formal Definitions and
                 Theory, Syntax. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Parsing.",
}

@Article{Singh:1992:RGT,
  author =       "Ambuj K. Singh",
  title =        "On reasoning with the global time assumption",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "1",
  pages =        "89--103",
  month =        mar,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/130616.130624",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/130624.html",
  abstract =     "Concurrency in distributed systems is usually modeled
                 by a nondeterministic interleaving of atomic events.
                 The consequences of this interleaving (or global time)
                 assumption on the specifications and proofs of
                 distributed programs are examined in this paper. A
                 construction for atomic registers is presented; this
                 construction has the surprising property that it is
                 correct with respect to a specification based on
                 partial orders but is incorrect with respect to a
                 naively derived specification based on global time.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "theory, verification",
  subject =      "{\bf D.2.1}: Software, SOFTWARE ENGINEERING,
                 Requirements/Specifications. {\bf D.1.3}: Software,
                 PROGRAMMING TECHNIQUES, Concurrent Programming. {\bf
                 F.3.1}: Theory of Computation, LOGICS AND MEANINGS OF
                 PROGRAMS, Specifying and Verifying and Reasoning about
                 Programs. {\bf D.4.2}: Software, OPERATING SYSTEMS,
                 Storage Management.",
}

@Article{Asuru:1992:OAS,
  author =       "Jonathan M. Asuru",
  title =        "Optimization of array subscript range checks",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "2",
  pages =        "109--118",
  month =        jun,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151333.151392",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151392.html",
  abstract =     "Compile-time elimination of subscript range checks is
                 performed by some optimizing compilers to reduce the
                 overhead associated with manipulating array data
                 structures. Elimination and propagation, the two
                 methods of subscript range check optimization, are less
                 effective for eliminating global redundancies
                 especially in while-loop structures with nonconstant
                 loop guards. This paper describes a subscript range
                 check optimization procedure that can eliminate more
                 range checks than current methods. Two transformations
                 called inner-loop guard elimination and conservative
                 expression substitution are introduced to enhance
                 propagation of range checks in nested while-loops and
                 to define a partial order on related range checks.
                 Global elimination is improved by considering range
                 checks performed before control reaches a statement and
                 after control leaves a statement. A unique feature of
                 this method is the simplification of the available
                 range-check analysis system for global elimination.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Optimization. {\bf
                 D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Data types and structures.",
}

@Article{Dietrich:1992:SPA,
  author =       "Suzanne W. Dietrich",
  title =        "Shortest path by approximation in logic programs",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "2",
  pages =        "119--137",
  month =        jun,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151333.151377",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151377.html",
  abstract =     "An approximation paradigm is proposed for logic
                 programming as a simple modification to a complete
                 evaluation strategy. The motivational example
                 illustrates how a straightforward transformation of a
                 declarative specification of the distance between two
                 vertices in a directed graph leads to sophisticated
                 algorithms for computing shortest paths. The goal of
                 the work presented in this paper is {\em not} to
                 provide a more efficient computation of shortest paths
                 but to investigate how the intermediate tables, known
                 as extension tables, generated by the complete
                 evaluation strategy might be used in approximation
                 algorithms. We present the $ET_\mbox{distance}$
                 algorithm in perspective, its execution is compared to
                 those of Dijkstra's single-source and Floyd's all-pairs
                 shortest path algorithms.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, performance, theory",
  subject =      "{\bf F.3.1}: Theory of Computation, LOGICS AND
                 MEANINGS OF PROGRAMS, Specifying and Verifying and
                 Reasoning about Programs, Logics of programs. {\bf
                 F.4.1}: Theory of Computation, MATHEMATICAL LOGIC AND
                 FORMAL LANGUAGES, Mathematical Logic, Logic
                 programming. {\bf G.3}: Mathematics of Computing,
                 PROBABILITY AND STATISTICS, Probabilistic algorithms
                 (including Monte Carlo). {\bf F.2.2}: Theory of
                 Computation, ANALYSIS OF ALGORITHMS AND PROBLEM
                 COMPLEXITY, Nonnumerical Algorithms and Problems,
                 Computations on discrete structures. {\bf G.2.2}:
                 Mathematics of Computing, DISCRETE MATHEMATICS, Graph
                 Theory, Path and circuit problems.",
}

@Article{Goldberg:1992:DFD,
  author =       "David Goldberg",
  title =        "The design of floating-point data types",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "2",
  pages =        "138--151",
  month =        jun,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151333.151373",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151373.html",
  abstract =     "The issues involved in designing the floating-point
                 part of a programming language are discussed. Looking
                 at the language specifications for most existing
                 languages might suggest that this design involves only
                 trivial issues, such as whether to have one or two
                 types of REALs or how to name the functions that
                 convert from INTEGER to REAL. It is shown that there
                 are more significant semantic issues involved. After
                 discussing the trade-offs for the major design
                 decisions, they are illustrated by presenting the
                 design of the floating-point part of the Modula-3
                 language.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "design, languages",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Data types and structures.
                 {\bf G.1.0}: Mathematics of Computing, NUMERICAL
                 ANALYSIS, General, Computer arithmetic. {\bf G.1.0}:
                 Mathematics of Computing, NUMERICAL ANALYSIS, General,
                 Error analysis. {\bf F.3.2}: Theory of Computation,
                 LOGICS AND MEANINGS OF PROGRAMS, Semantics of
                 Programming Languages. {\bf F.3.1}: Theory of
                 Computation, LOGICS AND MEANINGS OF PROGRAMS,
                 Specifying and Verifying and Reasoning about Programs,
                 Specification techniques.",
}

@Article{McConnell:1992:USS,
  author =       "Carl McConnell and Ralph E. Johnson",
  title =        "Using static single assignment form in a code
                 optimizer",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "2",
  pages =        "152--160",
  month =        jun,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151333.151368",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151368.html",
  abstract =     "Static single assignment form represents data
                 dependences elegantly and provides a basis for powerful
                 optimizations. Table-driven techniques for peephole
                 optimization and code generation are straightforward
                 and effective. it is natural to want to use both
                 together in a code optimizer. However, doing so reveals
                 that static single assignment form does not remove all
                 antidependences, and that it conflicts with
                 table-driven code generation for 2-address machines.
                 This paper describes these problems and how to solve
                 them.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, design",
  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,
                 Code generation.",
}

@Article{Tarditi:1992:NAR,
  author =       "David Tarditi and Peter Lee and Anurag Acharya",
  title =        "No assembly required: compiling standard {ML} to {C}",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "2",
  pages =        "161--177",
  month =        jun,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151333.151343",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151343.html",
  abstract =     "C has been used as a portable target language for
                 implementing languages like Standard ML and Scheme.
                 Previous efforts at compiling these languages to C have
                 produced efficient code, but have compromised on
                 portability and proper tail recursion. We show how to
                 compile Standard ML to C without making such
                 compromises. The compilation technique is based on
                 converting Standard ML to a continuation-passing style
                 [lambda]-calculus intermediate language and then
                 compiling this language to C. The code generated by
                 this compiler achieves an execution speed that is about
                 a factor of two slower than that generated by a native
                 code compiler. The compiler generates highly portable
                 code, yet still supports advanced features like garbage
                 collection and first-class continuations. We analyze
                 the performance and determine the aspects of the
                 compilation method that lead to the observed slowdown.
                 We also suggest changes to C compilers that would
                 better support such compilation methods.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "design, languages, performance, theory",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.3.2}: Software,
                 PROGRAMMING LANGUAGES, Language Classifications,
                 Standard ML. {\bf D.3.2}: Software, PROGRAMMING
                 LANGUAGES, Language Classifications, C. {\bf F.4.1}:
                 Theory of Computation, MATHEMATICAL LOGIC AND FORMAL
                 LANGUAGES, Mathematical Logic, Lambda calculus and
                 related systems. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Code generation.",
}

@Article{Weiss:1992:TCC,
  author =       "Michael Weiss",
  title =        "The transitive closure of control dependence: the
                 iterated join",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "2",
  pages =        "178--190",
  month =        jun,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151333.151337",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151337.html",
  abstract =     "We characterize the transitive closure of the control
                 dependence relation and give an application to the
                 theory of control fow guards. We relate our result to
                 characterizations by Beck et al., by Sarkar, and by
                 Cytron et al., and strengthen a result of the latter
                 concerning dominance frontiers and join sets.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, theory",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Control structures. {\bf
                 D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Data types and structures.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf E.1}: Data, DATA
                 STRUCTURES, Graphs.",
}

@Article{Danvy:1992:CAS,
  author =       "Olivier Danvy and John Hatcliff",
  title =        "{CPS}-transformation after strictness analysis",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "195--212",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151641",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151641.html",
  abstract =     "Strictness analysis is a common component of compilers
                 for call-by-name functional languages; the
                 continuation-passing-style (CPS-) transformation is a
                 common component of compilers for call-by-value
                 functional languages. To bridge these two
                 implementation techniques, the authors present a hybrid
                 CPS-transformation E/sub s/ for a language with
                 annotations resulting from strictness analysis. They
                 also address and solve the problem of recursive
                 binding. Finally, they express E/sub s/ in Nielson and
                 Nielson's two-level lambda-calculus, enabling a simple
                 and efficient implementation in a functional
                 programming language.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "design, languages, theory",
  subject =      "{\bf F.3.3}: Theory of Computation, LOGICS AND
                 MEANINGS OF PROGRAMS, Studies of Program Constructs,
                 Functional constructs. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 D.3.4}: Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf F.4.1}: Theory of Computation,
                 MATHEMATICAL LOGIC AND FORMAL LANGUAGES, Mathematical
                 Logic, Lambda calculus and related systems. {\bf
                 I.2.2}: Computing Methodologies, ARTIFICIAL
                 INTELLIGENCE, Automatic Programming, Program
                 transformation. {\bf D.3.1}: Software, PROGRAMMING
                 LANGUAGES, Formal Definitions and Theory, Syntax. {\bf
                 D.3.2}: Software, PROGRAMMING LANGUAGES, Language
                 Classifications, Applicative languages. {\bf D.3.3}:
                 Software, PROGRAMMING LANGUAGES, Language Constructs
                 and Features, Control structures.",
}

@Article{Fraser:1992:ESE,
  author =       "Christopher W. Fraser and David R. Hanson and Todd A.
                 Proebsting",
  title =        "Engineering a simple, efficient code-generator
                 generator",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "213--226",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151642",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Fri Feb 17 18:41:11 2006",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://storage.webhop.net/documents/iburg.pdf;
                 http://www.acm.org/pubs/toc/Abstracts/1057-4514/151642.html;
                 http://www.cs.princeton.edu/software/iburg/",
  abstract =     "Many code-generator generators use tree pattern
                 matching and dynamic programming. This paper describes
                 a simple program that generates matchers that are fast,
                 compact, and easy to understand. It is simpler than
                 common alternatives: 200-700 lines of Icon or 950 lines
                 of C versus 3000 lines of C for Twig and 5000 for burg.
                 Its matchers run up to 25 times faster than Twig's.
                 They are necessarily slower than burg's BURS (bottom-up
                 rewrite system) matchers, but they are more flexible
                 and still practical.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Translator writing systems and compiler
                 generators. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Code generation. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Compilers.",
}

@Article{Hall:1992:ECG,
  author =       "Mary W. Hall and Ken Kennedy",
  title =        "Efficient call graph analysis",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "227--242",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151643",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151643.html",
  abstract =     "We present an efficient algorithm for computing the
                 procedure call graph, the program representation
                 underlying most interprocedural optimization
                 techniques. The algorithm computes the possible
                 bindings of procedure variables in languages where such
                 variables only receive their values through parameter
                 passing, such as Fortran. We extend the algorithm to
                 accommodate a limited form of assignments to procedure
                 variables. The resulting algorithm can also be used in
                 analysis of functional programs that have been
                 converted to Continuation-Passing-Style.\par

                 We discuss the algorithm in relationship to other call
                 graph analysis approaches. Many less efficient
                 techniques produce essentially the same call graph. A
                 few algorithms are more precise, but they may be
                 prohibitively expensive depending on language
                 features.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Procedures, functions, and
                 subroutines. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization.",
}

@Article{Hummel:1992:ADP,
  author =       "Joseph Hummel and Laurie J. Hendren and Alexandru
                 Nicolau",
  title =        "Abstract description of pointer data structures: an
                 approach for improving the analysis and optimization of
                 imperative programs",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "243--260",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151644",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151644.html",
  abstract =     "Even though impressive progress has been made in the
                 area of optimizing and parallelizing array-based
                 programs, the application of similar techniques to
                 programs using pointer data structures has remained
                 difficult. Unlike arrays which have a small number of
                 well-defined properties, pointers can be used to
                 implement a wide variety of structures which exhibit a
                 much larger set of properties. The diversity of these
                 structures implies that programs with pointer data
                 structures cannot be effectively analyzed by
                 traditional optimizing and parallelizing
                 compilers.\par

                 In this paper we present a new approach that leads to
                 the improved analysis and transformation of programs
                 with recursively defined pointer data structures. Our
                 approach is based on a mechanism for the Abstract
                 Description of Data Structures (ADDS). ADDS is a simple
                 extension to existing imperative languages that allows
                 the programmer to explicitly describe the important
                 properties of a large class of data structures. These
                 abstract descriptions may be used by the compiler to
                 achieve more accurate program analysis in the presence
                 of pointers, which in turn enables and improves the
                 application of numerous optimizing and parallelizing
                 transformations. We present ADDS by describing various
                 data structures; we discuss how such descriptions can
                 be used to improve analysis and debugging; and we
                 supply three important transformations enabled by
                 ADDS.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Data types and structures.
                 {\bf E.2}: Data, DATA STORAGE REPRESENTATIONS, Linked
                 representations. {\bf E.1}: Data, DATA STRUCTURES.",
}

@Article{Pugh:1992:DDD,
  author =       "William Pugh",
  title =        "Definitions of dependence distance",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "261--265",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151645",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151645.html",
  abstract =     "Data dependence distance is widely used to
                 characterize data dependences in advance optimizing
                 compilers. The standard definition of dependence
                 distance assumes that loops are normalized (have
                 constant lower bounds and a step of 1); there is not a
                 commonly accepted definition for unnormalized loops. We
                 have identified several potential definitions, all of
                 which give the same answer for normalized loops. There
                 are a number of subtleties involved in choosing between
                 these definitions, and no one definition is suitable
                 for all applications.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, performance, theory",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers.",
}

@Article{Ramkumar:1992:DLC,
  author =       "Balkrishna Ramkumar",
  title =        "Distributed last call optimization for portable
                 parallel logic programming",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "266--283",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151345",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151345.html",
  abstract =     "A difficult but challenging problem is the efficient
                 exploitation of AND and OR parallelism in logic
                 programs without making any assumptions about the
                 underlying target machine(s). In earlier papers, we
                 described the design of a binding environment for AND
                 and OR parallel execution of logic programs on shared
                 and nonshared memory machines and the performance of a
                 compiler (called ROLOG) using this binding environment
                 on a range of MIMD parallel machines.\par

                 In this paper, we present an important optimization for
                 {\em portable} parallel logic programming, namely {\em
                 distributed last-call optimization}, an analog of the
                 tail recursion optimization for sequential Prolog. This
                 scheme has been implemented in the ROLOG compiler,
                 which ports {\em unchanged} on several shared memory
                 and nonshared memory machines. We describe the effect
                 of this optimization on several OR, AND/OR and AND
                 parallel benchmark programs.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, performance",
  subject =      "{\bf D.1.3}: Software, PROGRAMMING TECHNIQUES,
                 Concurrent Programming, Parallel programming. {\bf
                 D.3.4}: Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf D.1.6}:
                 Software, PROGRAMMING TECHNIQUES, Logic Programming.
                 {\bf D.2.7}: Software, SOFTWARE ENGINEERING,
                 Distribution and Maintenance, Portability.",
}

@Article{Walker:1992:MIV,
  author =       "Kenneth Walker and Ralph E. Griswold",
  title =        "The maintenance of intermediate values in
                 goal-directed evaluation",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "3",
  pages =        "284--298",
  month =        sep,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/151640.151341",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/151341.html",
  abstract =     "In programming languages that support goal-directed
                 evaluation to make use of alternative results, an
                 expression can produce a value, suspend, and later be
                 resumed to produce another value. This causes control
                 backtracking to earlier points in a computation and
                 complicates the maintenance of intermediate values.
                 This paper presents a space-efficient algorithm
                 computing the lifetimes of intermediate values that is
                 used by an optimizing compiler for the Icon programming
                 language. The algorithm is applicable to other
                 programming languages that employ goal-directed
                 evaluation.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, design, performance",
  subject =      "{\bf D.3.1}: Software, PROGRAMMING LANGUAGES, Formal
                 Definitions and Theory. {\bf D.3.2}: Software,
                 PROGRAMMING LANGUAGES, Language Classifications. {\bf
                 D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Code generation.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Optimization.",
}

@Article{Fritzson:1992:GAD,
  author =       "Peter Fritzson and Nahid Shahmehri and Mariam Kamkar
                 and Tibor Gyimothy",
  title =        "Generalized algorithmic debugging and testing",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "4",
  pages =        "303--322",
  month =        dec,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/161494.161498",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/161498.html",
  abstract =     "This paper presents a method for semi-automatic bug
                 localization, generalized algorithmic debugging, which
                 has been integrated with the category partition method
                 for functional testing. In this way the efficiency of
                 the algorithmic debugging method for bug localization
                 can be improved by using test specifications and test
                 results. The long-range goal of this work is a
                 semi-automatic debugging and testing system which can
                 be used during large-scale program development of
                 nontrivial programs.\par

                 The method is generally applicable to procedural
                 languages and is not dependent on any ad hoc
                 assumptions regarding the subject program. The original
                 form of algorithmic debugging, introduced by Shapiro,
                 was however limited to small Prolog programs without
                 side-effects, but has later been generalized to
                 concurrent logic programming languages. Another
                 drawback of the original method is the large number of
                 interactions with the user during bug
                 localization.\par

                 To our knowledge, this is the first method which uses
                 category partition testing to improve the bug
                 localization properties of algorithmic debugging. The
                 method can avoid irrelevant questions to the programmer
                 by categorizing input parameters and then match these
                 against test cases in the test database. Additionally,
                 we use program slicing, a data flow analysis technique,
                 to dynamically compute which parts of the program are
                 relevant for the search, thus further improving bug
                 localization.\par

                 We believe that this is the first generalization of
                 algorithmic debugging for programs with side-effects
                 written in imperative languages such as Pascal. These
                 improvements together makes it more feasible to debug
                 larger programs. However, additional improvements are
                 needed to make it handle pointer-related side-effects
                 and concurrent Pascal programs.\par

                 A prototype generalized algorithmic debugger for a
                 Pascal subset without pointer side-effects and a test
                 case generator for application programs in Pascal, C,
                 dBase, and LOTUS have been implemented.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, experimentation, performance",
  subject =      "{\bf D.2.5}: Software, SOFTWARE ENGINEERING, Testing
                 and Debugging, Debugging aids. {\bf D.2.6}: Software,
                 SOFTWARE ENGINEERING, Programming Environments.",
}

@Article{Landi:1992:USA,
  author =       "William Landi",
  title =        "Undecidability of static analysis",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "4",
  pages =        "323--337",
  month =        dec,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/161494.161501",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/161501.html",
  abstract =     "Static analysis of programs is indispensable to any
                 software tool, environment, or system that requires
                 compile-time information about the semantics of
                 programs. With the emergence of languages like C and
                 LISP, static analysis of programs with dynamic storage
                 and recursive data structures has become a field of
                 active research. Such analysis is difficult, and the
                 static-analysis community has recognized the need for
                 simplifying assumptions and approximate solutions.
                 However, even under the common simplifying assumptions,
                 such analyses are harder than previously recognized.
                 Two fundamental static-analysis problems are {\em may
                 alias} and {\em must alias}. The former is not
                 recursive (is undecidable), and the latter is not
                 recursively enumerable (is uncomputable), even when all
                 paths are executable in the program being analyzed for
                 languages with if statements, loops, dynamic storage,
                 and recursive data structures.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, theory",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors. {\bf F.1.1}: Theory of Computation,
                 COMPUTATION BY ABSTRACT DEVICES, Models of Computation,
                 Bounded-action devices. {\bf F.4.1}: Theory of
                 Computation, MATHEMATICAL LOGIC AND FORMAL LANGUAGES,
                 Mathematical Logic, Computability theory.",
}

@Article{Nilsen:1992:COS,
  author =       "Kelvin D. Nilsen and William J. Schmidt",
  title =        "Cost-effective object space management for
                 hardware-assisted real-time garbage collection",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "4",
  pages =        "338--354",
  month =        dec,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/161494.161508",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/161508.html",
  abstract =     "Modern object-oriented languages and programming
                 paradigms require finer-grain division of memory than
                 is provided by traditional paging and segmentation
                 systems. This paper describes the design of an OSM
                 (Object Space Manager) that allows partitioning of real
                 memory on object, rather than page, boundaries. The
                 time required by the OSM to create an object, or to
                 find the beginning of an object given a pointer to any
                 location within it, is approximately one memory cycle.
                 Object sizes are limited only by the availability of
                 address bits. In typical configurations of
                 object-oriented memory modules, one OSM chip is
                 required for every 16 RAM chips. The OSM serves a
                 central role in the implementation of a
                 hardware-assisted garbage collection system in which
                 the worst-case stop-and-wait garbage collection delay
                 ranges between 10 and 500 [mu]sec, depending on the
                 system configuration.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "management, performance",
  subject =      "{\bf B.7.1}: Hardware, INTEGRATED CIRCUITS, Types and
                 Design Styles. {\bf C.1.3}: Computer Systems
                 Organization, PROCESSOR ARCHITECTURES, Other
                 Architecture Styles. {\bf D.3.3}: Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features. {\bf
                 D.3.4}: Software, PROGRAMMING LANGUAGES, Processors.
                 {\bf D.4.7}: Software, OPERATING SYSTEMS, Organization
                 and Design.",
}

@Article{Srivastava:1992:UPO,
  author =       "Amitabh Srivastava",
  title =        "Unreachable procedures in object-oriented
                 programming",
  journal =      j-LOPLAS,
  volume =       "1",
  number =       "4",
  pages =        "355--364",
  month =        dec,
  year =         "1992",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/161494.161517",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/161517.html",
  abstract =     "Unreachable procedures are procedures that can never
                 be invoked. Their existence may adversely affect the
                 performance of a program. Unfortunately, their
                 detection requires the entire program to be present.
                 Using a long-time code modification system, we analyze
                 large, linked, program modules of C++, C, and Fortran.
                 We find that C++ programs using object-oriented
                 programming style contain a large fraction of
                 unreachable procedure code. In contrast, C and Fortran
                 programs have a low and essentially constant fraction
                 of unreachable code. In this article, we present our
                 analysis of C++, C, and Fortran programs, and we
                 discuss how object-oriented programming style generates
                 unreachable procedures.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Abstract data types. {\bf
                 D.3.4}: Software, PROGRAMMING LANGUAGES, Processors,
                 Code generation. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization.",
}

@Article{Ball:1993:WRC,
  author =       "Thomas Ball",
  title =        "What's in a region?: or computing control dependence
                 regions in near-linear time for reducible control
                 flow",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "1--16",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176456",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176456.html",
  abstract =     "Regions of control dependence identify the
                 instructions in a program that execute under the same
                 control conditions. They have a variety of applications
                 in parallelizing and optimizing compilers. Two vertices
                 in a control-flow graph (which may represent
                 instructions or basic blocks in a program) are in the
                 same region if they have the same set of control
                 dependence predecessors. The common algorithm for
                 computing regions examines each control dependence at
                 least once. As there may be O(V x E) control
                 dependences in the worst case, where V and E are the
                 number of vertices and edges in the control-flow graph,
                 this algorithm has a worst-case running time of O(V x
                 D). We present algorithms for finding regions in
                 reducible control-flow graphs in near-linear time,
                 without using control dependence. These algorithms are
                 based on alternative definitions of regions, which are
                 easier to reason with than the definitions based on
                 control dependence.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, theory",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.2.2}: Software, SOFTWARE
                 ENGINEERING, Tools and Techniques. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization.",
}

@Article{Beaven:1993:ETE,
  author =       "Mike Beaven and Ryan Stansifer",
  title =        "Explaining type errors in polymorphic languages",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "17--30",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176460",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176460.html",
  abstract =     "Strongly-typed languages present programmers with
                 compile-time feedback about the type correctness of
                 programs. Errors during polymorphic type checking take
                 the form of a unification failure for two types.
                 Finding the source of the type error in the code is
                 often difficult because the error may occur far from
                 the spot where the inconsistency is detected. As
                 functional languages use more and more complex type
                 systems, the difficulty of interpreting and locating
                 these errors will increase. To locate the source of
                 type errors the programmer must unravel the long chain
                 of deductions and type instantiations made during type
                 reconstruction. This paper describes an approach that
                 maintains the deductive steps of type inference and the
                 reasons for type instantiations. The approach could be
                 used in an interactive system to guide the programmer
                 to the source of a type error or to explain why the
                 compiler assigned a particular type to an expression.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages",
  subject =      "{\bf F.3.3}: Theory of Computation, LOGICS AND
                 MEANINGS OF PROGRAMS, Studies of Program Constructs,
                 Type structure. {\bf D.2.6}: Software, SOFTWARE
                 ENGINEERING, Programming Environments. {\bf D.3.3}:
                 Software, PROGRAMMING LANGUAGES, Language Constructs
                 and Features, Data types and structures.",
}

@Article{Binkley:1993:PEI,
  author =       "David Binkley",
  title =        "Precise executable interprocedural slices",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "31--45",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176473",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176473.html",
  abstract =     "The notion of a {\em program slice}, originally
                 introduced by Mark Weiser, is useful in program
                 debugging, automatic parallelization, program
                 integration, and software maintenance. A slice of a
                 program is taken with respect to a program point {\em
                 p} and a variable {\em x}; the slice consists of all
                 statements of the program that might affect the value
                 of {\em x} at point {\em p}. An interprocedural slice
                 is a slice of an entire program, where the slice
                 crosses the boundaries of procedure calls.\par

                 Weiser's original interprocedural-slicing algorithm
                 produces imprecise slices that are executable programs.
                 A recent algorithm developed by Horwitz, Reps, and
                 Binkley produces more precise (smaller) slices by more
                 accurately identifying those statements that might
                 affect the values of {\em x} at point {\em p}. These
                 slices, however, are not executable. An extension to
                 their algorithm that produces more precise executable
                 interprocedural slices is described together with a
                 proof of correctness for the new algorithm.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, design",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Procedures, functions, and
                 subroutines. {\bf D.3.3}: Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features, Control
                 structures. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization.",
}

@Article{Boehm:1993:IML,
  author =       "Hans-J. Boehm and Alan J. Demers and Chris Uhler",
  title =        "Implementing multiple locks using {Lamport}'s mutual
                 exclusion algorithm",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "46--58",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176479",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176479.html",
  abstract =     "We describe an approach for implementing higher-level
                 mutual-exclusion constructs using Lamport's algorithm.
                 A straightforward implementation of, for example,
                 monitor locks based on Lamport's algorithm requires
                 O({\em n}) space per monitor lock if there are {\em n}
                 processes that may share the lock. It has occasionally
                 been claimed that this makes the algorithm undesirable
                 in practice. The insight presented here is that we only
                 need a (small) constant amount of space per lock, plus
                 O({\em n}) space shared by all locks in the system. For
                 some common applications, this adds no memory
                 references to the implementation of the algorithm.
                 Fully general spin-lock acquisition and release can
                 usually be implemented with the addition of one memory
                 reference to Lamport's algorithm. On particularly
                 unfavorable hardware, three additional memory
                 references may be required in the contention-free
                 case.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, verification",
  subject =      "{\bf D.4.1}: Software, OPERATING SYSTEMS, Process
                 Management, Mutual exclusion. {\bf D.3.3}: Software,
                 PROGRAMMING LANGUAGES, Language Constructs and
                 Features, Concurrent programming structures.",
}

@Article{Briggs:1993:ERS,
  author =       "Preston Briggs and Linda Torczon",
  title =        "An efficient representation for sparse sets",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "59--69",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176484",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/hash.bib;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176484.html",
  abstract =     "Sets are a fundamental abstraction widely used in
                 programming. Many representations are possible, each
                 offering different advantages. We describe a
                 representation that supports constant-time
                 implementations of {\em clear-set, add-member,} and
                 {\em delete-member}. Additionally, it supports an
                 efficient {\em forall} iterator, allowing enumeration
                 of all the members of a set in time proportional to the
                 cardinality of the set.\par

                 We present detailed comparisons of the costs of
                 operations on our representation and on a bit vector
                 representation. Additionally, we give experimental
                 results showing the effectiveness of our representation
                 in a practical application: construction of an
                 interference graph for use during graph-coloring
                 register allocation.\par

                 While this representation was developed to solve a
                 specific problem arising in register allocation, we
                 have found it useful throughout our work, especially
                 when implementing efficient analysis techniques for
                 large programs. However, the new representation is not
                 a panacea. The operations required for a particular set
                 should be carefully considered before this
                 representation, or any other representation, is
                 chosen.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms; experimentation; hashing; measurement",
  subject =      "{\bf E.2}: Data, DATA STORAGE REPRESENTATIONS. {\bf
                 E.1}: Data, DATA STRUCTURES.",
}

@Article{Bumbulis:1993:RMV,
  author =       "Peter Bumbulis and Donald D. Cowan",
  title =        "{RE2C}: a more versatile scanner generator",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "70--84",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176487",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176487.html",
  abstract =     "It is usually claimed that lexical analysis routines
                 are still coded by hand, despite the widespread
                 availability of scanner generators, for efficiency
                 reasons. While efficiency is a consideration, there
                 exist freely available scanner generators such as GLA
                 [Gray 1988] that can generate scanners that are faster
                 than most hand-coded ones. However, most generated
                 scanners are tailored for a particular environment, and
                 retargeting these scanners to other environments, if
                 possible, is usually complex enough to make a
                 hand-coded scanner more appealing. In this paper we
                 describe RE2C, a scanner generator that not only
                 generates scanners that are faster (and usually
                 smaller) than those produced by any other scanner
                 generator known to the authors, including GLA, but that
                 also adapt easily to any environment.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Parsing. {\bf D.3.2}: Software, PROGRAMMING
                 LANGUAGES, Language Classifications, Specialized
                 application languages.",
}

@Article{Cameron:1993:ECG,
  author =       "Robert D. Cameron",
  title =        "Extending context-free grammars with permutation
                 phrases",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "85--94",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176490",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176490.html",
  abstract =     "A {\em permutation phrase} is a grammatical phrase
                 that specifies a syntactic construct as any permutation
                 of a set of constituent elements. Permutation phrases
                 allow for the concise and natural expression of
                 free-order constructs as found in programming languages
                 and notations such as C, Cobol, BibTEX, and Unix
                 command lines.\par

                 The conciseness and clarity of expression that
                 permutation phrase grammars offer over context-free
                 grammars are illustrated through a case study of the
                 declarations in C. The parsing problem for permutation
                 phrase grammars is considered, and it is shown how
                 efficient linear-time parsing can be achieved for
                 permutation phrase grammars satisfying an extended
                 notion of the LL(1) property.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "documentation, languages, theory",
  subject =      "{\bf D.3.1}: Software, PROGRAMMING LANGUAGES, Formal
                 Definitions and Theory, Syntax. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Parsing. {\bf
                 F.4.2}: Theory of Computation, MATHEMATICAL LOGIC AND
                 FORMAL LANGUAGES, Grammars and Other Rewriting Systems,
                 Grammar types. {\bf D.3.3}: Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features.",
}

@Article{Choudhary:1993:UCF,
  author =       "Alok Choudhary and Geoffrey Fox and Seema Hiranandani
                 and Ken Kennedy and Charles Koelbel and Sanjay Ranka
                 and Chau-Wen Tseng",
  title =        "Unified compilation of {Fortran 77D} and {90D}",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "95--114",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176495",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176495.html",
  abstract =     "We present a unified approach to compiling Fortran 77D
                 and Fortran 90D programs for efficient execution of
                 MIMD distributed-memory machines. The integrated
                 Fortran D compiler relies on two key observations.
                 First, array constructs may be {\em scalarized} into
                 FORALL loops without loss of information. Second, {\em
                 loop fusion, partitioning,} and {\em sectioning}
                 optimizations are essential for both Fortran D
                 dialects.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf C.1.2}: Computer Systems
                 Organization, PROCESSOR ARCHITECTURES, Multiple Data
                 Stream Architectures (Multiprocessors),
                 Multiple-instruction-stream, multiple-data-stream
                 processors (MIMD). {\bf C.1.2}: Computer Systems
                 Organization, PROCESSOR ARCHITECTURES, Multiple Data
                 Stream Architectures (Multiprocessors), Parallel
                 processors. {\bf D.3.3}: Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features, Concurrent
                 programming structures. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Code generation.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Preprocessors. {\bf
                 D.3.2}: Software, PROGRAMMING LANGUAGES, Language
                 Classifications, FORTRAN.",
}

@Article{Day:1993:RRM,
  author =       "Mark Day and Barbara Liskov and Umesh Maheshwari and
                 Andrew C. Myers",
  title =        "References to remote mobile objects in {Thor}",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "115--126",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176500",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176500.html",
  abstract =     "Thor is a distributed object-oriented database where
                 objects are stored persistently at highly available
                 servers called object repositories, or ORs. In a large
                 Thor system, performance tuning and system
                 reconfiguration dictate that objects must be able to
                 migrate among ORs. The paper describes two schemes for
                 object references that support object migration, one
                 using location-independent names and the other,
                 location-dependent names. The paper analyzes the
                 performance of the two schemes and concludes that
                 location-dependent names are the right choice for
                 systems like Thor, where we want fast access to objects
                 that have migrated.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "design",
  subject =      "{\bf H.2.4}: Information Systems, DATABASE MANAGEMENT,
                 Systems, Distributed systems. {\bf C.2.4}: Computer
                 Systems Organization, COMPUTER-COMMUNICATION NETWORKS,
                 Distributed Systems, Distributed databases. {\bf
                 D.4.7}: Software, OPERATING SYSTEMS, Organization and
                 Design, Distributed systems. {\bf E.2}: Data, DATA
                 STORAGE REPRESENTATIONS, Linked representations. {\bf
                 H.2.2}: Information Systems, DATABASE MANAGEMENT,
                 Physical Design.",
}

@Article{Eyre-Todd:1993:DDR,
  author =       "Richard A. Eyre-Todd",
  title =        "The detection of dangling references in {C++}
                 programs",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "127--134",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176504",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176504.html",
  abstract =     "The {\em smart pointer} is a programming technique for
                 the C++ language that extends the functionality of the
                 simple pointer. Smart pointers have previously been
                 used to support persistence, distributed objects,
                 reference counting, and garbage collection. This
                 article will show how smart pointers can provide an
                 inexpensive method for detecting dangling pointers to
                 dynamic objects that can be added to any standard C++
                 implementation.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, reliability",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Dynamic storage management.
                 {\bf D.1.5}: Software, PROGRAMMING TECHNIQUES,
                 Object-oriented Programming. {\bf D.2.5}: Software,
                 SOFTWARE ENGINEERING, Testing and Debugging, Debugging
                 aids. {\bf D.3.3}: Software, PROGRAMMING LANGUAGES,
                 Language Constructs and Features, Data types and
                 structures.",
}

@Article{Gupta:1993:OAB,
  author =       "Rajiv Gupta",
  title =        "Optimizing array bound checks using flow analysis",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "135--150",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176507",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176507.html",
  abstract =     "Bound checks are introduced in programs for the
                 run-time detection of array bound violations.
                 Compile-time optimizations are employed to reduce the
                 execution-time overhead due to bound checks. The
                 optimizations reduce the program execution time through
                 {\em elimination} of checks and {\em propagation} of
                 checks out of loops. An execution of the optimized
                 program terminates with an array bound violation if and
                 only if the same outcome would have resulted during the
                 execution of the program containing all array bound
                 checks. However, the point at which the array bound
                 violation occurs may not be the same. Experimental
                 results indicate that the number of bound checks
                 performed during the execution of a program is greatly
                 reduced using these techniques.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, reliability",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.2.5}: Software,
                 SOFTWARE ENGINEERING, Testing and Debugging, Error
                 handling and recovery. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers.",
}

@Article{Kaser:1993:CID,
  author =       "Owen Kaser and C. R. Ramakrishnan and Shaunak Pawagi",
  title =        "On the conversion of indirect to direct recursion",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "151--164",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176510",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176510.html",
  abstract =     "Procedure inlining can be used to convert mutual
                 recursion to direct recursion. This allows use of
                 optimization techniques that are most easily applied to
                 directly recursive procedures, in addition to the
                 well-known benefits of inlining. We present tight
                 (necessary {\em and} sufficient) conditions under which
                 inlining can transform all mutual recursion to direct
                 recursion, and those under which heuristics to
                 eliminate mutual recursion always terminate. We also
                 present a technique to eliminate mutually recursive
                 circuits that consist of only tail calls. From this, we
                 conclude that tail recursion elimination should be
                 interleaved with inlining.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, performance",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Procedures, functions, and
                 subroutines. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Compilers. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization.",
}

@Article{Larus:1993:CSM,
  author =       "James R. Larus",
  title =        "Compiling for shared-memory and message-passing
                 computers",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "165--180",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176514",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176514.html",
  abstract =     "Many parallel languages presume a shared address space
                 in which any portion of a computation can access any
                 datum. Some parallel computers directly support this
                 abstraction with hardware shared memory. Other
                 computers provide distinct (per-processor) address
                 spaces and communication mechanisms on which software
                 can construct a shared address space. Since programmers
                 have difficulty explicitly managing address spaces,
                 there is considerable interest in compiler support for
                 shared address spaces on the widely available
                 message-passing computers.\par

                 At first glance, it might appear that
                 hardware-implemented shared memory is unquestionably a
                 better base on which to implement a language. This
                 paper argues, however, that compiler-implemented shared
                 memory, despite its short-comings, has the potential to
                 exploit more effectively the resources in a parallel
                 computer. Hardware designers need to find mechanisms to
                 combine the advantages of both approaches in a single
                 system.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf B.3.2}: Hardware, MEMORY
                 STRUCTURES, Design Styles, Shared memory. {\bf C.1.2}:
                 Computer Systems Organization, PROCESSOR ARCHITECTURES,
                 Multiple Data Stream Architectures (Multiprocessors),
                 Multiple-instruction-stream, multiple-data-stream
                 processors (MIMD). {\bf C.1.2}: Computer Systems
                 Organization, PROCESSOR ARCHITECTURES, Multiple Data
                 Stream Architectures (Multiprocessors), Parallel
                 processors. {\bf D.1.3}: Software, PROGRAMMING
                 TECHNIQUES, Concurrent Programming, Parallel
                 programming. {\bf D.3.4}: Software, PROGRAMMING
                 LANGUAGES, Processors, Optimization. {\bf D.3.4}:
                 Software, PROGRAMMING LANGUAGES, Processors, Run-time
                 environments.",
}

@Article{Marriott:1993:PEG,
  author =       "Kim Marriott and Harald S{\o}ndergaard",
  title =        "Precise and efficient groundness analysis for logic
                 programs",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "181--196",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176519",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176519.html",
  abstract =     "We show how precise groundness information can be
                 extracted from logic programs. The idea is to use
                 abstract interpretation with Boolean functions as
                 ``approximations'' to groundness dependencies between
                 variables. This idea is not new, and different classes
                 of Boolean functions have been used. We argue, however,
                 that one class, the {\em positive} functions, is more
                 suitable than others. Positive Boolean functions have a
                 certain property which we (inspired by A. Langen) call
                 ``condensation.'' This property allows for rapid
                 computation of groundness information.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, theory",
  subject =      "{\bf F.3.1}: Theory of Computation, LOGICS AND
                 MEANINGS OF PROGRAMS, Specifying and Verifying and
                 Reasoning about Programs, Assertions. {\bf D.1.6}:
                 Software, PROGRAMMING TECHNIQUES, Logic Programming.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Compilers. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Optimization. {\bf
                 F.3.1}: Theory of Computation, LOGICS AND MEANINGS OF
                 PROGRAMS, Specifying and Verifying and Reasoning about
                 Programs, Invariants. {\bf F.3.1}: Theory of
                 Computation, LOGICS AND MEANINGS OF PROGRAMS,
                 Specifying and Verifying and Reasoning about Programs,
                 Logics of programs.",
}

@Article{Marriott:1993:SCL,
  author =       "Kim Marriott and Peter J. Stuckey",
  title =        "Semantics of constraint logic programs with
                 optimization",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "197--212",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176522",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176522.html",
  abstract =     "Many applications of constraint logic programming
                 (CLP) languages require not only testing if a set of
                 constraints is satisfiable, but also finding the
                 optimal solution which satisfies them. Unfortunately,
                 the standard declarative semantics for CLP languages
                 does not consider optimization but only constraint
                 satisfaction. Here we give a model theoretic semantics
                 for optimization, which is a simple extension of the
                 standard semantics, and a corresponding operational
                 semantics, which may be efficiently implemented.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, theory",
  subject =      "{\bf F.4.1}: Theory of Computation, MATHEMATICAL LOGIC
                 AND FORMAL LANGUAGES, Mathematical Logic, Logic
                 programming. {\bf D.1.6}: Software, PROGRAMMING
                 TECHNIQUES, Logic Programming. {\bf F.3.2}: Theory of
                 Computation, LOGICS AND MEANINGS OF PROGRAMS, Semantics
                 of Programming Languages, Operational semantics.",
}

@Article{Metzger:1993:ICP,
  author =       "Robert Metzger and Sean Stroud",
  title =        "Interprocedural constant propagation: an empirical
                 study",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "213--232",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176526",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176526.html",
  abstract =     "Constant propagation is an optimization that
                 substitutes values for names. Interprocedural constant
                 propagation performs this substitution throughout an
                 entire program, propagating constant values across
                 procedure boundaries. CONVEX Computer Corporation has
                 developed an interprocedural optimizer for imperative
                 languages, which is available to users of its C-series
                 supercomputers. An aggressive interprocedural constant
                 propagation algorithm, such as the one implemented in
                 this optimizer, can find many constants to propagate
                 into procedures in scientific FORTRAN applications.
                 Detailed statistics derived from compiling a large set
                 of real scientific applications characterize both the
                 opportunities for interprocedural constant propagation
                 in these codes and the effectiveness of algorithm
                 described. These statistics include the frequency of
                 interprocedural constant propagation, the different
                 types of interprocedural constant propagation, which
                 constants are most frequently propagated, and the
                 relationship between interprocedural constant
                 propagation and other interprocedural optimizations.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "algorithms, languages, performance",
  subject =      "{\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Optimization. {\bf D.3.3}: Software,
                 PROGRAMMING LANGUAGES, Language Constructs and
                 Features, Data types and structures. {\bf D.3.3}:
                 Software, PROGRAMMING LANGUAGES, Language Constructs
                 and Features, Procedures, functions, and subroutines.
                 {\bf D.3.4}: Software, PROGRAMMING LANGUAGES,
                 Processors, Code generation. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 I.2.2}: Computing Methodologies, ARTIFICIAL
                 INTELLIGENCE, Automatic Programming, Program
                 transformation.",
}

@Article{Qian:1993:RON,
  author =       "Xiaolei Qian and Allen Goldberg",
  title =        "Referential opacity in nondeterministic data
                 refinement",
  journal =      j-LOPLAS,
  volume =       "2",
  number =       "4",
  pages =        "233--241",
  month =        mar,
  year =         "1993",
  CODEN =        "ALPSE8",
  DOI =          "http://dx.doi.org/10.1145/176454.176578",
  ISSN =         "1057-4514 (print), 1557-7384 (electronic)",
  ISSN-L =       "1057-4514",
  bibdate =      "Thu May 30 15:54:54 MDT 1996",
  bibsource =    "http://www.acm.org/pubs/toc/;
                 http://www.math.utah.edu/pub/tex/bib/loplas.bib",
  URL =          "http://www.acm.org/pubs/toc/Abstracts/1057-4514/176578.html",
  abstract =     "Data refinement is the transformation in a program of
                 one data type to another. With the obvious
                 formalization of nondeterministic data types in
                 equational logic however, many desirable
                 nondeterministic data refinements are impossible to
                 prove correct. Furthermore, it is difficult to have a
                 monotonic notion of refinement. We propose an
                 alternative formalization of nondeterministic data
                 types, in which the requirement of referential
                 transparency applies only to deterministic operators.
                 We show how the above-mentioned problems can be solved
                 with our approach.",
  fjournal =     "ACM Letters on Programming Languages and Systems
                 (LOPLAS)",
  keywords =     "languages, theory, verification",
  subject =      "{\bf D.3.3}: Software, PROGRAMMING LANGUAGES, Language
                 Constructs and Features, Abstract data types. {\bf
                 D.2.4}: Software, SOFTWARE ENGINEERING, Program
                 Verification, Correctness proofs. {\bf F.3.2}: Theory
                 of Computation, LOGICS AND MEANINGS OF PROGRAMS,
                 Semantics of Programming Languages, Algebraic
                 approaches to semantics.",
}