waashk/acm huggingface dataset:
experience and evolution of concurrent smalltalk  concurrentsmalltalk is an object-oriented concurrent programming language/system which has been running since late 1985. concurrentsmalltalk has the following features:  upper-compatibility with smalltalk-80.  asynchronous method calls and cbox objects yield concurrency.  atomic objects have the property of running one at a time so that it can serialize the many requests sent to it.  through experience in writing programs, some disadvantages have become apparent related to concurrency control and the behavior of a block context. in this paper, these issues are re-examined in detail, and then the evolution of the solutions for overcoming these shortcomings is described along with the model of computation in concurrentsmalltalk. new features are explained with an example program. the implementation of the concurrentsmalltalk virtual machine is also presented along with the evaluation of it.  yasuhiko yokote mario tokoro
adaptive storage control for page frame supply in large scale computer systems  a real storage management algorithm called adaptive control of page- frame supply (acps) is described. acps employees three strategies: prediction of the demand for real page frames, page replacement based on the prediction, and working set control. together, these strategies constitute the real page frame allocation method, and contribute to short and stable response times in conversational processing environments.  acps is experimentally applied to the vos3 operating system. evaluation of acps on a real machine shows that tss response times are not affected too strongly by king-size jobs and acps is successful in avoiding paging delay and thrashing. acps prevents extreme shortages of real storage in almost all cases.  y. yoshizawa t. arai
type resolution in ada: an implementation report  various features of ada [ichbiah 79, honeywell 80] make type resolution an interesting and difficult as implemented in a semantic analyzer for ada built in 1979-80.  first, a straightforward algorithm, similar to that of ganzinger and ripken [ganzinger 80], is discussed. next an optimized version of this algorithm is presented.  the optimization is based on the idea that, in a tree-walking analysis in which the information developed on one branch can affect the analysis elsewhere, and where the difficulty of analysis is not uniform, analysis should be performed a little at a time wherever it is most likely to be useful rather than according to any data-independent, pre-planned method such as bottom-up or top-down. this raises the likelihood that the analysis of "simple" branches will occur early and so ease the computational cost of analyzing the more difficult branches.  peter a. belmont
interactive verification of communication software on the basis of cil  the cil-approach for the development of communication services is based on the programming language cil (communication service implementation language) and a cil-compatible theory of program execution. the theory contains a first-order predicate calculus and an event-oriented model of program execution. the verification of programs written in cil is supported by the automated generation of program axioms and by an interactive theorem prover tailored to the predicate calculus. interactive verification during the design phase leads to early detection and localization of design errors and helps to reduce the efforts for debugging and testing. the paper describes the principles of the language, the theory, and the interactive verification tool. the design of a program realizing a transport service exemplifies the cil- approach.  h. krumm o. drobnik
reuse: where to begin and why  the software engineering institute (sei) is interested in identifying the costs and benefits of software reuse to the mission critical computer resource (mccr) community. in fulfilling this role, we were faced with the need to investigate reuse without making a large investment. this paper examines where to start a reuse activity by describing our initial view of reuse, our decisions on where to begin, what lessons we learned, and finally, our current view.  the reuse life cycle described in our final view gives more insight on how and where to implement reuse. it defines the phases of a reuse life cycle that begin with business planning and shows their relationships. for each phase of the reuse life cycle, we give the goals, the outputs, and an approach for achieving the goals. each organization that is interested in obtaining the benefits of reuse must evaluate reuse in terms of business goals and objectives. once this evaluation has been made, the life cycle described in the paper provides one approach to achieving the benefits of reuse.  r. holibaugh s. cohen k. kang s. peterson
data transfer between java applets and legacy apl systems the rise of internet technologies (particularly java) provides many benefits for the development and deployment of user interfaces. in many cases, however, the back end system is behind the times: internet hostile, no object orientation, etc. how can data be transferred between the new generation front end and the old generation back end without compromising the strengths or integrity of either? this paper discusses the use of customised java data serialisation to achieve this goal against a large ibm mvs sharp apl system. b. amos g. disney d. sorrey
writing applications for uniform operation on a mainframe or pc: a metric conversion program  the metric system of measurement is the primary standard in all countries except the usa and two others. use of the metric system is becoming more important to the usa for trade and commerce in the world economy. a metric conversion program was developed to convert 350 measurement units between inch-pound (or usa customary) and metric systems for engineering design and documentation. the program follows the primary national metric standard with its conversion factors and special rules for arithmetic, rounding, accuracy, formatting, and terminology. it was first developed in apl on a vm cms mainframe system, but subsequent demand warranted a pc version. the program has been presented at national metric meetings and is briefly described here.  the portability of apl2 under vm cms and pc dos was exploited in moving the mainframe program to the pc, maintaining much of the code in identical form, thus giving advantages in testing, verification, and user experience. differences between the environments fell mainly in the user and file interface areas, which led to a matched set of cover functions for system dependent operations. these functions and differences between the two systems are described for file operations, pop-up windows, printing, stack and host system commands.  the capability and portability of apl enabled this application to become the first internally written example at this company of ibm's new user interface guidelines working on both a central mainframe and a pc.  charles a. schulz
shuffle languages, petri nets, and context-sensitive grammars  flow expressions have been proposed as an extension of the regular expressions designed to model concurrency. we examine a simplification of these flow expressions which we call shuffle expressions. we introduce two types of machines to aid in recognizing shuffle languages and show that one such machine may be equivalent to a petri net. in addition, closure and containment properties of the related language classes are investigated, and we show that one machine type recognizes at least a restricted class of shuffle languages. finally, grammars for all shuffle languages are generated, and the shuffle languages are shown to be context- sensitive.  jay gischer
the evolution of a language standard: mumps in the 1980s  in 1977 the mumps language standard was approved as an american national standard (x11.1-1977) by ansi. the specification of the mumps standard was carried out by the mumps development committee, which continues to direct the evolution of the language. this paper traces the standardization process from its inception in 1973 to the present, stressing the enhancements made to mumps since 1977. features which will be included in the proposed 1982 mumps standard are discussed, as well as other extensions currently being considered. a number of areas in which future changes may be made are also mentioned. these include not only simple additional functional capabilities, but also possible fundamental revisions needed to keep mumps in step with the technology of the 1980s. finally, some of the lessons learned about the process of language standardization are described.  david d. sherertz
dynamic variables  most programming languages use static scope rules for associating uses of identifiers with their declarations. static scope helps catch errors at compile time, and it can be implemented efficiently. some popular languages--- perl, tel, tex, and postscript---offer dynamic scope, because dynamic scope works well for variables that "customize" the execution environment, for example. programmers must simulate dynamic scope to implement this kind of usage in statically scoped languages. this paper describes the design and implementation of imperative language constructs for introducing and referencing dynamically scoped variables---dynamic variables for short. the design is a minimalist one, because dynamic variables are best used sparingly, much like exceptions. the facility does, however, cater to the typical uses for dynamic scope, and it provides a cleaner mechanism for so-called thread- local variables. a particularly simple implementation suffices for languages without exception handling. for languages with exception handling, a more efficient implementation builds on existing compiler infrastructure. exception handling can be viewed as a control construct with dynamic scope. likewise, dynamic variables are a data construct with dynamic scope.  david r. hanson todd a. proebsting
simple but effective techniques for numa memory management  multiprocessors with non-uniform memory access times introduce the problem of placing data near the processes that use them, in order to improve performance. we have implemented an automatic page placement strategy in the mach operating system on the ibm ace multiprocessor workstation. our experience indicates that even very simple automatic strategies can produce nearly optimal page placement. it also suggests that the greatest leverage for further performance improvement lies in reducing false sharing, which occurs when the same page contains objects that would best be placed in different memories.  w. bolosky r. fitzgerald m. scott
on subtyping and matching  a relation between recursive object types, called matching, has been proposed as a generalization of subtyping. unlike subtyping, matching does not support subsumption, but it does support inheritance of binary methods. we argue that matching is a good idea, but that it should not be regarded as a form of f-bounded subtyping (as was originally intended). we show that a new interpretation of matching as higher-order subtyping has better properties. matching turns out to be a third-order construction, possibly the only one to have been proposed for general use in programming.  martín abadi luca cardelli
dplab: an environment for distributed programming this paper describes the software package dplab which implements an integrated gui environment for developing distributed programs. the environment includes a text editor, a compiler, and a runtime system that establishes communications between networked computers and provides primitives for message passing between the computers. the source language is pascal extended with these primitives and with constructs for concurrent programming. the package is implemented in java and swing for portability. mordechai ben-ari shawn silverman
register allocation for banked register file  a banked register file is a register file partitioned into banks. a register in a banked register file is addressed with the register number in conjunction with the active bank number. a banked register file may be employed to reduce the number of bits for register operands in the instruction encoding at the cost of bank changes and inter-bank data transfers. although a banked register file is introduced to provide sufficient registers and reduce memory traffic, it may on the other hand inflate code by unwanted bank hanges and excessive inter-bank data movements. in this context, code quality heavily depends on the register allocator that decides the location of each variable. this paper addresses a heuristic approach to register allocation for exploiting two register banks. it performs global register allocation with the primary bank registers, while reducing the register pressure by doing local register allocation with the secondary bank registers. experimental results show that the proposed register allocator eliminates a significant amount of memory traffic while achieving smaller code size compared to an allocator that utilizes the primary bank only.  jinpyo park je-hyung lee soo-mook moon
synthesis of resource invariants for concurrent programs  owicki and gries have developed a proof system for conditional critical regions. in their system, logically related variables accessed by more than one process are grouped together as resources, and processes are allowed access to a resource only in a critical region for that resource. proofs of synchronization properties are constructed by devising predicates called resource invariants which describe relationships among the variables of a resource when no process is in a critical region for the resource. in constructing proofs using the system of owicki and gries, the programmer is required to supply the resource invariants.  methods are developed in this paper for automatically synthesizing resource invariants. specifically, the resource invariants of a concurrent program are characterized as least fixpoints of a functional which can be obtained from the text of the program. by the use of this fixpoint characterization and a widening operator based on convex closure, good approximations may be obtained for the resource invariants of many concurrent programs.  edmund clarke
experience with topaz telebugging  the topaz teledebug (ttd) facility provides a remote debugging capability supporting software development in the topaz environment. topaz is a software environment providing rich support for programming in modula2+, and extended version of modula 2. ttd allows uniform use of the same high level source language debugger for all debugging (both local and remote) of software at all levels of the system. special care has been taken to maximize ttd's reliability and robustness. our experience suggests that such a facility can be extremely useful, very dependable and quite inexpensive. it also suggests that the implementation issues can be somewhat subtle, and that correct choices in this area are vital if the promise of such a scheme is to be fully realized. this paper focuses on those implementation issues in a fair amount of detail, analyzing the limitations of our first ttd implementation and the redesign that produced a second, improved version. our main conclusion is that the target (debuggee) end of such a facility should be implemented at the lowest possible level in the operating system, and that a uniformly applicable remote invocation (e.g. remote procedure call) facility is key to enabling this approach. we also conclude that strict adherence to layered information hiding can lead to serious difficulties in the implementation of a remote debugging protocol.  the discussion should be of particular interest to others designers of remote debugging facilities. while the paper does not devote much attention to higher level issues (e.g. novel user interfaces for debugging concurrent or distributed programs) most of the ideas discussed should be applicable to a wide class of debuggers, including those with higher aspirations for debugging such programs.  david d. redell
on the design of the amoeba configuration manager  the program amoeba make, or amake, is being designed to fulfil the need of a make-like configuration manager capable of exploiting the potentials of the amoeba distributed operating system. the major design goal is to create a software configuration manager that is both easy to use and efficient. the specification and maintenance of a large configuration should be easy, and should be automated as much as possible. furthermore, the build process should exploit amoeba's capabilities and resources when creating or updating a target. in this paper we show how a smart file server can contribute to amake's efficiency. we also show how a declarative configuration description allows amake to take full advantage of parallelism and to determine the commands needed for building and maintaining targets.  e. h. baalbergen k. verstoep a. s. tanenbaum
on the performance of balanced hashing functions when the keys are not equiprobable  the cost (expected number of accesses per retrieval) of hashing functions is examined without the assumption that it is equally probable for all keys to be present in the table. it is shown that the obvious strategy---trying to balance the sums of probabilities of the keys mapped to any given address--- may be suboptimal; however, the difference from the exactly optimal distribution cannot be large.  christos h. papadimitriou philip a. bernstein
the trellis programming environment  the trellis programming environment supports programming in trellis/owl, an object-based language with multiple inheritance and compile-time type- checking. trellis is composed of a number of integrated tools that share a common programming environment database. it is a highly interactive, easy-to- use programming environment, providing various programming aids, incremental compilation, and good debugging support. trellis is both integrated and open- ended.  trellis was specifically designed to support the object-oriented programming methodology. thus it provides tools to manage the use of types and inheritance. trellis takes advantage of the strong-typing features of the trellis/owl language to provide more support for the programmer by keeping track of cross-references and inconsistencies in code.  patrick d. o'brien daniel c. halbert michael f. kilian
an equational language for data-parallelism  data-parallelism provides a clean conceptual framework for parallel programming. we are developing two programming languages: a high level equational language, called el*, and a low-level implementation language. both languages exploit data-parallelism instead of control-parallelism. el* is a declarative data-parallel language. el* programs are high-level equational specifications that use extensive pattern-matching and recursion. the language's syntax and semantics are intended to be clear and simple. recursive forms are restricted to enable translation to efficient data-parallel operations. el* programs are compiled into fp*, a variant of backus's fp, where parallel operations are more explicit and low-level. the target language has a rich set of functions for performing communication, and computation. it also has a powerful set of combining forms that generate large highly-parallel functions from smaller program units. prototype compilers have been implemented for both languages, and they demonstrate good performance. several linear algebra and non-numeric problems have been programmed with relative ease using el*. we are currently developing compilation techniques for a wider range of scientific problems that have more complex parallel solutions, and are continuing to expand the language's scope.  pushpa rao clifford walinsky
specification-based prototyping for embedded systems  specification of software for safety critical, embedded computer systems has been widely addressed in literature. to achieve the high level of confidence in a specification's correctness necessary in many applications, manual inspections, formal verification, and simulation must be used in concert. researchers have successfully addressed issues in inspection and verification; however, results in the areas of execution and simulation of specifications have not made as large an impact as desired.  in this paper we present an approach to specification-based prototyping which addresses this issue. it combines the advantages of rigorous formal specifications and rapid systems prototyping. the approach lets us refine a formal executable model of the system requirements to a detailed model of the software requirements. throughout this refinement process, the specification is used as a prototype of the proposed software. thus, we guarantee that the formal specification of the system is always consistent with the observed behavior of the prototype. the approach is supported with the nimbus environment, a framework that allows the formal specification to execute while interacting with software models of its embedding environment or even the physical environment itself (hardware-in- the-loop simulation).  jeffrey m. thompson mats p. e. heimdahl steven p. miller
centaur: the system  this paper describes the organization of the centaur system and its main components. the system is a generic interactive environment. when given the formal specification of a particular programming language-including syntax and semantics --- it produces a language specific environment. this resulting environment includes a structure editor, an interpreter/debugger and other tools, all of which have graphic interfaces. centaur is made of three parts: a database component, that provides standardized representation and access to formal objects and their persistent storage; a logical engine that is used to execute formal specifications; an object-oriented man-machine interface that gives easy access to the system's functions. centaur is essentially written in lisp (le_lisp). the logical engine is prolog (mu-prolog). the man-machine interface is built on top of the virtual graphics facility of le_lisp, itself primarily implemented on top of x-windows.  p. borras d. clement th. despeyroux j. incerpi g. kahn b. lang v. pascual
instruction reference patterns in data flow programs  instruction reference patterns in data flow environments differ from those in conventional systems. because execution is data driven in data flow environments, patterns of instruction references depend on data references. also, instruction reference patterns are two-dimensional because execution is parallel. in this paper, models of instruction reference patterns are presented to illustrate program behavior and to provide insight into the potential usefulness of an instruction cache or virtual memory in data flow environments. the results establish that locality exists and is exploitable in some data flow environments.  s. a. thoreson a. e. oldehoeft