waashk/acm huggingface dataset:
object-oriented programming in smalltalk and ada  though ada and modula-2 are not object-oriented languages, an object-oriented viewpoint is crucial for effective use of their module facilities. it is therefore instructive to compare the capabilities of a modular language such as ada with an archetypal object-oriented language such as smalltalk. the comparison in this paper is in terms of the basic properties of encapsulation, inheritance and binding, with examples given in both languages. this comparison highlights the strengths and weaknesses of both types of languages from an object- oriented perspective. it also provides a basis for the application of experience from smalltalk and other object-oriented languages to increasingly widely used modular languages such as ada and modula-2.  ed seidewitz
assessing the quality of abstract data types written in ada  as software systems have become more complex, a search for better abstraction mechanisms has led to the use of abstract data types (adts). to more appropriately use adts, however, it is imperative that their properties and characteristics be understood. in this paper we present a method of assessing the quality of adts in terms of cohesion and coupling. we argue that an adt that contains and exports only one domain and exports only operations that pertain to that domain has the best cohesive properties, and we argue that adts that make neither explicit nor implicit assumptions about other adts in the system have the best coupling properties. formal definitions are presented for each of the cohesion and coupling characteristics discussed. their application to ada® packages is also investigated, and we show how a tool can be developed to assess the quality of an ada package that represents an adt. we analyzed nearly one hundred ada adt packages found in ada text books, articles about ada, and student projects and discovered that more than half of them had inferior cohesive characteristics and almost half of them allowed inferior coupling characteristics.  d. w. embley s. n. woodfield
automated data-member layout of heap objects to improve memory-hierarchy performance  we present and evaluate a simple, yet efficient optimization technique that improves memory-hierarchy performance for pointer- centric applications by up to 24% and reduces cache misses by up to 35%. this is achieved by selecting an improved ordering for the data members of pointer- based data structures. our optimization is applicable to all type-safe programming languages that completely abstract from physical storage layout; examples of such languages are java and oberon. our technique does not involve programmers in the optimization process, but runs fully automatically, guided by dynamic profiling information that captures which paths through the program are taken with that frequencey. the algorithm first strives to cluster data members that are accessed closely after one another onto the same cache line, increasing spatial locality. then, the data members that have been mapped to a particular cache line are ordered to minimize load latency in case of a cache miss.  thomas kistler michael franz
computer aided hand tuning (caht): "applying case-based reasoning to performance tuning"  for most parallel and high performance systems, tuning guides provide the users with advices to optimize the execution time of their programs. execution time may be very sensitive to small program changes. such modifications may be local (on loop) or global (data structures and layout).  in this paper, we propose to help end-users with the tuning process through an interactive tool complementary to existing compilers and automatic parallelizers. our goal is to provide a _live tuning guide_ capable of detecting optimization opportunities that are not caught by existing tools. our first prototype, called caht (computer aided hand tuning), targets smp architectures for openmp programs. caht relies on a very general technique, case based reasoning. this technique is adequate to experiment and build an easily expandable and flexible system. our first implementation applies to scientific codes written in fortran 77.  antoine monsifrot françois bodin
supporting dynamic data structures on distributed-memory machines  compiling for distributed-memory machines has been a very active research area in recent years. much of this work has concentrated on programs that use arrays as their primary data structures. to date, little work has been done to address the problem of supporting programs that use pointer-based dynamic data structures. the techniques developed for supporting spmd execution of array- based programs rely on the fact that arrays are statically defined and directly addressable. recursive data structures do not have these properties, so new techniques must be developed. in this article, we describe an execution model for supporting programs that use pointer-based dynamic data structures. this model uses a simple mechanism for migrating a thread of control based on the layout of heap-allocated data and introduces parallelism using a technique based on futures and lazy task creation. we intend to exploit this execution model using compiler analyses and automatic parallelization techniques. we have implemented a prototype system, which we call olden, that runs on the intel ipsc/860 and the thinking machines cm-5. we discuss our implementation and report on experiments with five benchmarks.  anne rogers martin c. carlisle john h. reppy laurie j. hendren
distributed algorithms in tla (abstract)  tla (the temporal logic of actions) is a simple logic for describing and reasoning about concurrent systems. it provides a uniform way of specifying algorithms and their correctness properties, as well as rules for proving that one specification satisfies another. tla+ is a formal specification language based on tla, and tlc is a model checker for tla+ specifications. tla+ and tlc have been used to specify and check high-level descriptions of real, complex systems. because tla+ provides the full power of ordinary mathematics, it permits simple, straightforward specifications of the kinds of algorithms presented at podc.  this tutorial will try to convince you to describe your algorithms in tla+. you will then be able to check them with tlc and use tla to prove their correctness as formally or informally as you want. (however, tla proofs do have one disadvantage that is mentioned below.) the tutorial will describe tla+ through examples and demonstrate how to use tlc. no knowledge of tla is assumed.  tla does have the following disadvantages:  it can describe only a real algorithm, not a vague, incomplete sketch of an algorithm.  you can specify an algorithm's correctness condition in tla only if you understand what the algorithm is supposed to do.  tla makes it harder to cover gaps in a proof with handwaving.  some researchers may find these drawbacks insurmountable.  leslie lamport
et++ - an object oriented application framework in c++  et++ is an object-oriented application framework implemented in c++ for a unix† environment and a conventional window system. the architecture of et++ is based on macapp and integrates a rich collection of user interface building blocks as well as basic data structures to form a homogeneous and extensible system. the paper describes the graphic model and its underlying abstract window system interface, shows composite objects as a substrate for declarative layout specification of complex dialogs, and presents a model for editable text allowing the integration of arbitrary interaction objects.  andre weinand erich gamma rudolf marty
a system for parallel programming  the programming of efficient parallel software typically requires extensive experimentation with program prototypes. a programming system that supports rapid prototyping of parallel programs should provide high-level primitives with which programs can be explicitly, statically or dynamically tuned with respect to performance and reliability. when using such primitives, programmers should not need to interact explicitly or even be aware of the software tools involved in program construction and tuning, such as compilers, linkers, and loaders. in addition, programmers should be provided with the information about the executing program and the parallel hardware required for tuning. such information may include monitoring data about the current or previous program or even hints regarding appropriate tuning decisions.  a programming system that includes primitives and tools for program tuning is presented in this paper. the system has been implemented, and has been tested with a variety of parallel applications on a network of unix workstations.  k. schwan r. ramnath s. vasudevan d. ogle
extendable, dispatchable task communication mechanisms the addition of object- oriented features to ada has left a disconnection between the object-oriented paradigm and the intertask communication and synchronisation paradigms. the lack of extensibility of tasks and protected types as well as the task synchronisation inheritance anomaly has made design of systems that use them with object oriented features more difficult. this paper proposes ada language changes that would make protected types and tasks partners in object oriented programming and would cure the inheritance anomaly. stephen michell kristina lundqvist
a comparison of cost estimation tools (panel session)  there are only a handful of software cost estimation tools that are in general use today. the authors, or representatives, of the most "popular" tools were presented with a common problem to analyze as basis for comparison. in this context, each was asked to address their analysis approach, input parameters used, parameters not used, and results generated. this paper contains the statement of the problem and a summary of the results which will be discussed at the panel session.  b. kitchenbaum howard a. rubin a. jensen l. putnam p. rook
structured assembly language programming  for those of us who are essentially high level programmers, the intricacies and lack of structure in assembly language programs are often an insurmountable barrier to effective assembly language programming. this paper attempts to show a way to overcome this barrier. structured pseudocode is used to solve the problem just as if the solution were to be coded in pl/i, pascal, ada, or some other structured high level language. then the structured pseudocode is "compiled" into assembly language using appropriate labels to show the structure of the assembly language program.  robert n. cook
static type inference for parametric classes  central features of object-oriented programming are method inheritance and data abstraction attained through hierarchical organization of classes. recent studies show that method inheritance can be nicely supported by ml style type inference when extended to labeled records. this is based on the fact that a function that selects a field of a record can be given a polymorphic type that enables it to be applied to any record which contains a field . several type systems also provide data abstraction through abstract type declarations. however, these two features have not yet been properly integrated in a statically checked polymorphic type system.  this paper proposes a static type system that achieves this integration in an ml-like polymorphic language by adding a class construct that allows the programmer to build a hierarchy of classes connected by multiple inheritance declarations. moreover, classes can be parameterized by types allowing "generic" definitions. the type correctness of class declarations is statically checked by the type system. the type system also infers a principal scheme for any type correct program containing methods and objects defined in classes.  a. ohori p. buneman
hint-based cooperative caching  this article presents the design, implementation, and measurement of a hint- based cooperative caching file system. hints allow clients to make decisions based on local state, enabling a loosely coordinated system that is simple to implement. the resulting performance is comparable to that of existing tightly coordinated algorithms that use global state, but with less overhead. simulations show that the block access times of our system are as good as those of the existing algorithms, while reducing manager load by more than a factor of seven, block lookup traffic by nearly a factor of two-thirds, and replacement traffic a factor of five. to verify our simulation results in a real system with real users, we implemented a prototype and measured its performance for one week. although the simulation and prototype environments were very different, the prototype system mirrored the simulation results by exhibiting reduced overhead and high hint accuracy. furthermore, hint-based cooperative caching reduced the average block access time to almost half that of nfs.  prasenjit sarkar john h. hartman
a practical tool kit for making portable compilers  the amsterdam compiler kit is an integrated collection of programs designed to simplify the task of producing portable (cross) compilers and interpreters. for each language to be compiled, a program (called a front end) must be written to translate the source program into a common intermediate code. this intermediate code can be optimized and then either directly interpreted or translated to the assembly language of the desired target machine. the paper describes the various pieces of the tool kit in some detail, as well as discussing the overall strategy.  andrew s. tanenbaum hans van staveren e. g. keizer johan w. stevenson
genoa - a customizable, front-end-retargetable source code analysis framework  code analysis tools provide support for such software engineering tasks as program understanding, software metrics, testing, and reengineering. in this article we describe genoa, the framework underlying application generators such as aria and gen++ which have been used to generate a wide range of practical code analysis tools. this experience illustrates front-end retargetability of genoa; we describe the features of the genoa framework that allow it to be used with different front ends. while permitting arbitrary parse tree computations, the genoa specification language has special, compact iteration operators that are tuned for expressing simple, polynomial-time analysis programs; in fact, there is a useful sublanguage of the genoa language that can express precisely all (and only) polynomial-time (ptime) analysis programs on parse trees. thus, we argue that the genoa language is a simple and convenient vehicle for implementing a range of analysis tools. we also argue that the "front-and reuse" approach of genoa offers an important advantage for tools aimed at large software projects: the reuse of complex, expensive build procedures to run generated tools over large source bases. in this article, we describe the genoa framework and our experiences with it.  premkumar t. devanbu
fusion-based register allocation  the register allocation phase of a compiler maps live ranges of a program to registers. if there are more candidates than there are physical registers, the register allocator must spill a live range (the home location is in memory) or split a live range (the live range occupies multiple locations). one of the challenges for a register allocator is to deal with spilling and splitting together. fusion-based register allocation uses the structure of the program to make splitting and spilling decisions, with the goal to move overhead operations to infrequently executed parts of a program. the basic idea of fusion-based register allocation is to build up the interference graph. starting with some base region (e.g., a basic block, a loop), the register allocator adds basic blocks to the region and incrementallly builds the interference graph. when there are more live ranges than registers, the register allocator selects live ranges to split; these live ranges are split along the edge that was most recently added to the region. this article describes fusion-based register allocation in detail and compares it with other approaches to register allocation. for programs from the spec92 suite, fusion-based register allocation can improve the execution time (of optimized programs, for the mips architecture) by up to 8.4% over chaitin-style register allocation.  guei-yuan lueh thomas gross ali-reza adl-tabatabai
management of disk space with rebate  the past decade has witnessed a proliferation of respositories whose workload consists of queries that retrieve information. these repositories provide on- line access to vast amount of data and serve as an integral component of many application domains (e.g., library information systems, scientific applications, entertainment industry). their storage subsystem is expected to be hierarchical consisting of memory, disk drives, and one or more tertiary storage devices. the database resides permanently on the tertiary storage devices and objects are swapped onto the magnetic disk drives on demand (and deleted once the disk storage capacity is exhausted). this may fragment the disk space over a period of time, resulting in a non-contiguous layout of an object across the surface of a disk drive. this is undesirable because, once the object is referenced, the disk drive is required to reposition its read head multiple times (incur seek operations) when retrieving the object, resulting in a low performance.  this paper presents the design of rebate. rebate ensures the contiguous layout of each object across the surface of a disk drive by partitioning the available disk space into regions where each region manages objects of approximately the same size. we describe the tradeoffs of using rebate and its possible limitations.  shahram ghandeharizadeh douglas j. ierardi
on the effect of different counting rules for control flow operators on software science metrics in fortran  halstead in his theory of software science, proposed that in the fortran language, each occurrence of a goto i for different label i's be counted as a unique operator. several writers have questioned the wisdom of this method of counting goto's. in this paper, we investigate the effect of counting goto's as several occurrences of a single unique operator on various software science metrics. some 412 modules from the international mathematical and statistical libraries (imsl) are used as the data base for this study.  s. d. conte v. y. shen k. dickey
imax  the intel iapx 432 is an object-based microcomputer which, together with its operating system imax, provides a multiprocessor computer system designed around the ideas of data abstraction. imax is implemented in ada and provides, through its interface and facilities, an ada view of the 432 system. of paramount concern in this system is the uniformity of approach among the architecture, the operating system, and the language. some interesting aspects of both the external and internal views of imax are discussed to illustrate this uniform approach.  kevin c. kahn william m. corwin t. don dennis herman d'hooge david e. hubka linda a. hutchins john t. montague fred j. pollack
automatic translation of fortran programs to vector form  the recent success of vector computers such as the cray-1 and array processors such as those manufactured by floating point systems has increased interest in making vector operations available to the fortran programmer. the fortran standards committee is currently considering a successor to fortran 77, usually called fortran 8x, that will permit the programmer to explicitly specify vector and array operations.  although fortran 8x will make it convenient to specify explicit vector operations in new programs, it does little for existing code. in order to benefit from the power of vector hardware, existing programs will need to be rewritten in some language (presumably fortran 8x) that permits the explicit specification of vector operations. one way to avoid a massive manual recoding effort is to provide a translator that discovers the parallelism implicit in a fortran program and automatically rewrites that program in fortran 8x.  such a translation from fortran to fortran 8x is not straightforward because fortran do loops are not always semantically equivalent to the corresponding fortran 8x parallel operation. the semantic difference between these two constructs is precisely captured by the concept of dependence. a translation from fortran to fortran 8x preserves the semantics of the original program if it preserves the dependences in that program.  the theoretical background is developed here for employing data dependence to convert fortran programs to parallel form. dependence is defined and characterized in terms of the conditions that give rise to it; accurate tests to determine dependence are presented; and transformations that use dependence to uncover additional parallelism are discussed.  randy allen ken kennedy
smalltalk  smalltalk is an object-oriented programming environment developed at the xerox palo alto research center over the last twelve years. all components of the smalltalk environment are represented as objects that communicate by exchanging messages. this includes all of the common data types and operating system features found in a typical programming environment. for example, smalltalk includes objects representing numbers, arrays, text, disk files, and independent processes. messages are exchanged to initiate arithmetic calculation, data storage and retrieval, text editing, file access and process scheduling.  david robson
how to define a language using prolog  there have been many papers, conferences and theses concerned with the task of defining programming languages. yet, twenty years after mccarthy's (1962) seminal paper there is still no widely accepted method which will deal with all parts of a language clearly and concisely. everyone who invents a language writes a bnf definition and the more theoretically minded will attempt a denotational semantics. for a complete definition of the syntax, attribute grammars are gaining increasing acceptance while more practically minded language designers will use one of the compiler definition languages such as meta4 or cdl.  at the same time as the prolog language was defined, a grammar system called metamorphosis grammar (m-grammar for short) was invented by colmerauer (1978). this has been shown to be suitable (moss 1981) for defining both the full syntax and semantics of programming languages. the present paper attempts to give an overview of this method in the form of a practical guide to writing a language definition. this includes the context sensitive syntax, and semantics using denotational, relational or axiomatic methods.  this definition is not simply of theoretical interest. since prolog is a practical programming language, though with a sound theoretical basis (warren, pereira, pereira 1977), the definition can be used as a prototyping tool for a new language. with the addition of plan-formation techniques one might form a prolog based compiler generator and by adding other axioms form a program proving system.  chris d.s. moss
class-is-type is inadequate for object reuse it is well known that class and type are two different concepts in object-oriented programming languages (oopls). however, in many popular oopls, classes are used as types. in this paper, we argue that the class-is-type principle is a major obstacle to software reuse, especially to object reuse. the concepts of the basic entities, i.e., objects, object classes, object types, and object kinds, in the type hierarchy of oopls are revisited. the notion of object reuse is defined and elaborated. in addition, we show that parameterized types and generic functions are better served by used kind-bounded quantification than universal quantification and other mechanisms. sheng yu