waashk/acm huggingface dataset:
remark on algorithm 622: a simple macroprocessor  a number of updates to the macroprocessor are described that bring the code into line with the fortran 77 standard. this is followed by an outline of how the macroprocessor was used for the rapid porting of geophysical software from a 64-bit supercomputer environment to a number of different unix workstations. finally a number of deficiencies remaining in the macroprocessor are noted and workarounds suggested where possible.  stewart a. levin
the a+ programming language, a different apl  this paper introduces a+, which is an array oriented programming language derived from apl, and explains the motivations for creating such a language.  after discussing of some problems of current apl system, like the lack of control structures, the usage of dynamic binding, and the difficulty of handling functions, we present how these problems are solved in a+.  the most important feature of a+ is that it uses lexical binding rather than dynamic binding as apl does, which solves some old problems of apl while making it a safer language, and offers a new kind of programming style.  jean-jacques girardot
polymorphic effect systems  we present a new approach to programming languages for parallel computers that uses an effect system to discover expression scheduling constraints. this effect system is part of a 'kinded' type system with three base kinds: types, which describe the value that an expression may return; effects, which describe the side-effects that an expression may have; and regions, which describe the area of the store in which side-effects may occur. types, effects and regions are collectively called descriptions.  expressions can be abstracted over any kind of description variable -- this permits type, effect and region polymorphism. unobservable side-effects can be masked by the effect system; an effect soundness property guarantees that the effects computed statically by the effect system are a conservative approximation of the actual side-effects that a given expression may have.  the effect system we describe performs certain kinds of side-effect analysis that were not previously feasible. experimental data from the programming language fx indicate that an effect system can be used effectively to compile programs for parallel computers.  j. m. lucassen d. k. gifford
higher-order distributed objects  we describe a distributed implementation of scheme that permits efficient transmission of higher-order objects such as closures and continuations. the integration of distributed communication facilities within a higher-order programming language engenders a number of new abstractions and paradigms for distributed computing. among these are user-specified load-balancing and migration policies for threads, incrementally linked distributed computations, and parameterized client-server applications. to our knowledge, this is the first distributed dialect of scheme (or a related language) that addresses lightweight communication abstractions for higher-order objects.  henry cejtin suresh jagannathan richard kelsey
beg, borrow, or steal (workshop session): using multidisciplinary approaches in empirical software engineering research  the goal of this workshop is to provide an interactive forum for software engineers and empirical researchers to investigate the feasibility of applying proven methods from other research disciplines to software engineering research. participants submitted position papers describing problems that might benefit from a multidisciplinary approach. expert guest speakers from software engineering and other disciplines will address the issues highlighted in the papers with the goal of encouraging more multidisciplinary research.  janice singer margaret-anne storey susan elliott sim
a system for computer music performance  a computer music performance system (cmps) is a computer system connected to input devices (including musical keyboards or other instruments) and to graphic and audio output devices. a human performer generates input events using the input devices. the cmps responds to these events by computing and performing sequences of output actions whose intended timing is determined algorithmically. because of the need for accurate timing of output actions, the scheduling requirements of a cmps differ from those of general-purpose or conventional real-time systems.  this paper describes the scheduling facilities of formula, a cmps used by many musicians. in addition to providing accurate timing of output action sequences, formula provides other basic functions useful in musical applications: (1) per-process virtual time systems with independent relationships to real time; (2) process grouping mechanisms and language-level control structures with time-related semantics, and (3) integrated scheduling of tasks (such as compiling and editing) whose real-time constraints are less stringent than those of output action computations.  david p. anderson ron kuivila
modules and type checking in pl/ll  the type system of a programming language system pl/ll is described. pl is a simple object oriented programming language and ll is a language for composing pl modules into programs. the goals of the pl/ll system are to enable the programming of efficient object- oriented computations and to provide the powerful linking language ll for facilitating the construction of large programs. the goal of the type system is to ensure efficient and secure object handling through a combination of static and dynamic type checking, and to preserve this property across module boundaries. the solution is based on (i) the module and linking concepts of ll, (ii) a language construct in pl for the safe creation of linked data structures, and (iii) a limited form of type polymorphism and type unification.  lars-erik thorelli
constraint-based array dependence analysis  traditional array dependence analysis, which detects potential memory aliasing of array references is a key analysis technique for automatic parallelization. recent studies of benchmark codes indicate that limitations of analysis cause many compilers to overlook large amounts of potential parallelism, and that exploiting this parallelism requires algorithms to answer new question about array references, not just get better answers to the old questions of aliasing. we need to ask about the flow of values in arrays, to check the legality of array privatization, and about the conditions under which a dependence exists, to obtain information about conditional parallelism. in some cases, we must answer these questions about code containing nonlinear terms in loop bounds or subscripts. this article describes techniques for phrasing these questions in terms of systems of contstraints. conditional dependence analysis can be performed with a constraint operation we call the "gist" operation. when subscripts and loop bounds are affine, questions about the flow of values in array variables can be phrased in terms of presburger arithmetic. when the constraints describing a dependence are not affine, we introduce uninterpreted function symbols to represent the nonaffine terms. our constraint language also provides a rich language for communication with the dependence analyzer, by either the programmer or other phases of the compiler. this article also documents our investigations of the praticality of our approach. the worst-case complexity of presburger arithmetic indicates that it might be unsuitable for any practical application. however, we have found that analysis of benchmark programs does not cause the exponential growth in the number of constraints that could occur in the worst case. we have studied the constraints produced during our aanalysis, and identified characteristics that keep our algorithms free of exponential behavior in practice.  william pugh david wonnacott
data abstraction mechanisms in sina/st  this paper describes a new data abstraction mechanism in an object-oriented model of computing. the data abstraction mechanism described here has been devised in the context of the design of sina/st language. in sina/st no language constructs have been adopted for specifying inheritance or delegation, but rather, we introduce simpler mechanisms that can support a wide range of code sharing strategies without selecting one among them as a language feature. sina/st also provides a stronger data encapsulation than most of the existing object-oriented languages. this language has been implemented on the sun 3 workstation using smalltalk.  mehmet aksit anand tripathi
a naming system for feature-based service specification in distributed operating systems  the paper describes a naming system that allows a service to evolve or reconfigure in functionality by adding and removing features and still co- exist with its previous versions. the underlying naming model has two aspects: (1) (attribute-name attribute- value) pair based characterization of service features which allows the meta information on a service to be represented as a collection of such pairs (as in x.500 and universal naming protocol). at low level, the name server provides parse and match operations on the (attribute, value) pairs using which high level name binding operations, viz., name registration and name resolution, are constructed. (2) data-driven communication paradigm which enables different versions of a client and server to communicate with one another. in this paradigm, a server matches the attributes requested by a client with those it supports, and invokes service specific functions named by the attributes. since attributes refer to orthogonal features, client and server can evolve independently by adding or removing attributes and still communicate. with this model of specifying services, name server functions may be factorized from service specific functions and implemented in a generic fashion in terms of parse and match operations and function invocations. the paper also describes language support for the naming system and implementation issues.  k. ravindran k. k. ramakrishnan
distributed programming with intermediate idl several heterogeneous-language distributed programming systems have been developed which either use an explicit interface definition language (idl) for the specification of distributed objects or which directly translate server language specifications to corresponding client language representations. in this paper, we present a new approach which combines the advantages of these prior systems. our approach uses an idl as an implicit intermediate step in the translation from server to client language rather than as an explicit user-provided definition. gary w. smith richard a. volz
functions as objects in a data flow based visual language  data flow based visual programming languages are an active area of research in visual programming languages. some recent data flow visual programming languages have implemented higher order functions, allowing functions to be passed to/from functions. this paper describes a data flow visual programming language in which the first class citizenship of programs have been taken a step further, and programs can be manipulated as data with the same kind of flexibility that lisp offers in manipulating programs as data.  alex fukunaga wolfgang pree takayuki dan kimura
an empirical study of static call graph extractors  informally, a call graph represents calls between entities in a given program. the call graphs that compilers compute to determine the applicability of an optimization must typically be conservative: a call may be omitted only if it can never occur in any execution of the program. numerous software engineering tools also extract call graphs with the expectation that they will help software engineers increase their understanding of a program. the requirements placed on software engineeringtools that compute call graphs are typically more relaxed than for compilers. for example, some false negatives---calls that can in fact take place in some execution of the program, but which are omitted from the call graph---may be acceptable, depending on the understanding task at hand. in this article, we empirically show a consequence of this spectrum of requirements by comparing the c call graphs extracted from three software systems (mapmaker, mosaic, and gcc) by nine tools (cflow, cawk, cia, field, gct, imagix, lsme, mawk, and rigiparse). a quantitative analysis of the call graphs extracted for each system shows considerable variation, a result that is counterintuitive to many experienced software engineers. a qualitative analysis of these results reveals a number of reasons for this variation: differing treatments of macros, function pointers, input formats, etc. the fundamental problem is not that variances among the graphs extracted by different tools exist, but that software engineers have little sense of the dimensions of approximation in any particular call graph. in this article, we describe and discuss the study, sketch a design space for static call graph extractors, and discuss the impact of our study on practitioners, tool developers, and researchers. although this article considers only one kind of information, call graphs, many of the observations also apply to static extractors of other kinds of information, such as inheritance structures, file dependences, and references to global variables.  gail c. murphy david notkin william g. griswold erica s. lan
an approach for exploring code improving transformations  although code transformations are routinely applied to improve the performance of programs for both scalar and parallel machines, the properties of code- improving transformations are not well understood. in this article we present a framework that enables the exploration, both analytically and experimentally, of properties of code-improving transformations. the major component of the framework is a specification language, gospel, for expressing the conditions needed to safely apply a transformation and the actions required to change the code to implement the transformation. the framework includes a technique that facilitates an analytical investigation of code- improving transformations using the gospel specifications. it also contains a tool, genesis, that automatically produces a transformer that implements the transformations specified in gospel. we demonstrate the usefulness of the framework by exploring the enabling and disabling properties of transformations. we first present analytical results on the enabling and disabling properties of a set of code transformations, including both traditional and parallelizing transformations, and then describe experimental results showing the types of transformations and the enabling and disabling interactions actually found in a set of programs.  deborah l. whitfield mary lou soffa
ada debugging and testing support environments  this paper presents analysis and design considerations for ada programming support environments (apses) to support interactive debugging and testing of embedded, real time software at the ada source code level. the analysis is based on the "stoneman" requirements specification for apses (1). important factors in the analysis and design of ada debugging and testing support systems include the requirement for a source level system, the host machine- target machine configurations, the real time and concurrent nature of target software, and the kapse virtual machine interface to the apse data base. although this paper is specifically concerned with debugging and testing issues, the methods utilized and the results obtained are of general applicability.  the following sections of the paper address general analysis considerations, source level support environments, design considerations for an interactive source level debugger, and kapse design considerations.  richard e. fairley
equivalence analysis: a general technique to improve the efficiency of data- flow analyses in the presence of pointers existing methods to handle pointer variables during data-flow analyses can make such analyses inefficient both in time and space because the data-flow analyses must store and propagate large sets of data facts that are introduced by dereferences of pointer variable. this paper presents _equivalence analysis,_ a general technique to improve the efficiency of data-flow analyses in the presence of pointers. the technique identifies equivalence relations among the memory locations accessed by a procedure and ensures that two equivalent memory locations share the same set of data facts in a procedure and in the procedures that are called by that procedure. thus, a data-flow analysis needs to compute the data-flow information only for a representative memory location in an equivalence class. the data-flow information for other memory locations in the equivalence class can be derived from that of the representative memory location. our empirical studies indicate that equivalence analysis may effectively improve the efficiency of many data-flow analyses. donglin liang mary jean harrold
shared functions and variables as an aid to applications design  analogic apl incorporates true sharing of named objects into apl for the first time. both functions and variables may be shared. true shared variables are variables which are visible and accessible to multiple tasks without the aid of any intervening processor. they fill roles traditionally taken by shared file systems and (@@@@)svo-style shared variables. their straightforward design allows an apl programmer to develop whatever sharing protocol is most appropriate to the application. one could, for example, build a complete shared file system or (@@@@)svo-style shared variable processor written in apl. all of the features of analogic apl discussed in this paper have been fully specified. the system is now being implemented. a substantial subset of these features will be demonstrable in helsinki in june, 1984.  michael j.a. berry
the architecture of montana: an open and extensible programming environment with an incremental c++ compiler montana is an open, extensible integrated programming environment for c++ that supports incremental compilation and linking, a persistent code cache called a codestore, and a set of programming interfaces to the codestore for tool writers. codestore serves as a central source of information for compiling, browsing, and debugging. codestore contains information about both the static and dynamic structure of the compiled program. this information spans files, macros, declarations, function bodies, templates and their instantiations, program fragment dependencies, linker relocation information, and debugging information.montana allows the compilation process to be extended and modified [11]. montana has been used as the basis of a number of tools [1,7], and is also used as the infrastructure of a production compiler, ibm's visual age c++ 4.0 [8]. michael karasick
data abstraction, controlled iteration, and communicating processes  iterators provide access to elements of an abstract structured object in some sequence. it is argued that parallel composition of iterators should be achieved implicitly by means of a generalized for loop rather than by use of mutually interacting coroutines. the generalized for loop employs controlled iteration, which is shown to be a powerful yet inexpensive construct. the generalized for loop is consistent with block structure, and, for program proof purposes, is much more tractable than an unrestricted loop. concrete programming examples are used extensively.  alfs t. berztiss
the design and application of a retargetable peephole optimizer  peephole optimizers improve object code by replacing certain sequences of instructions with better sequences. this paper describes po, a peephole optimizer that uses a symbolic machine description to simulate pairs of adjacent instructions, replacing them, where possible, with an equivalent single instruction. as a result of this organization, po is machine independent and can be described formally and concisely: when po is finished, no instruction, and no pair of adjacent instructions, can be replaced with a cheaper single instruction that has the same effect. this thoroughness allows po to relieve code generators of much case analysis; for example, they might produce only load/add-register sequences and rely on po to, where possible, discard them in favor or add-memory, add-immediate, or increment instructions. experiments indicate that naive code generators can give good code if used with po.  jack w. davidson christopher w. fraser
the click modular router click is a new software architecture for building flexible and configurable routers. a click router is assembled from packet processing modules called _elements._ individual elements implement simple router functions like packet classification, queueing, scheduling, and interfacing with network devices. complete configurations are built by connecting elements into a graph; packets flow along the graph's edges. several features make individual elements more powerful and complex configurations easier to write, including _pull processing,_ which models packet flow driven by transmitting interfaces, and _flow- based router context,_ which helps an element locate other interesting elements.we demonstrate several working configurations, including an ip router and an ethernet bridge. these configurations are modular---the ip router has 16 elements on the forwarding path---and easy to extend by adding additional elements, which we demonstrate with augmented configurations. on commodity pc hardware running linux, the click ip router can forward 64-byte packets at 73,000 packets per second, just 10% slower than linux alone. robert morris eddie kohler john jannotti m. frans kaashoek
a mobility-aware file system for partially connected operation the advent of affordable off-the-shelf wide-area wireless networking solutions for portable computers will result in partial (or intermittent) connectivity becoming the common networking mode for mobile users. this paper presents the design of pfs, a mobility-aware file system specially designed for partially connected operation.pfs supports the extreme modes of full connection and disconnection gracefully, but unlike other mobile file systems, it also provides an interrace for mobility-aware applications to direct the file system in its caching and consistency decisions in order to fully exploit intermittent connectivity. using pfs, it is possible for an application to maintain consistency on only the critical portions of its data files. since pfs provides adaptation at the file system level, even unaware applications can 'act' mobile-aware as a result of the transparent adaptation provided by pfs. dane dwyer vaduvur bharghavan
m.h. halstead's software science - a critical examination  karl popper has described the scientific method as "the method of bold conjectures and ingenious and severe attempts to refute them". software science has made "bold conjectures" in postulating specific relationships between various 'metrics' of software code and in ascribing psychological interpretations to some of these metrics.  this paper describes tests made on the validity of the relationships and interpretations which form the foundations of software science. the results indicate that the majority of them represent neither natural laws nor useful engineering approximations.  peter g. hamer gillian d. frewin
structured requirements definition in the 80s  in the last few years, structured programming and structured systems design have become increasingly popular. recently, there has been considerable application of structuring to the front-end of the systems life cycle, in particular to the requirements definition process. this paper discusses the experience with one methodology the langston, kitch structured systems development methodology (ssd), and forecasts what the major developments in requirements development will be in the 1980s.  kenneth t. orr