%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "1.08", %%% date = "14 October 2017", %%% time = "10:23:59 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 = "52096 2145 10952 111368", %%% 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.08, 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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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}, {\em 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 = "https://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 = "https://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 = "https://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}, {\em 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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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 = "https://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.", }