waashk/acm huggingface dataset:
rt prolog: a real time prolog written in ada  prolog is a very powerful language and its declarative nature lends itself quite well to the development of expert systems and natural language interfaces. there are many laboratory situations in which an expert system could help technicians or operators accomplish their task. however, in these same situations there is usually need for a real time capability. a possible scenario would be to have an expert system executing in prolog which must respond to some external interrupt, either from a sensor or an operator.  the expert system should be able to suspend its current processing and service the interrupt. the interrupt might need to be serviced in a procedural manner or it might entail the answering of a different question by the expert system. after the interrupt request has been serviced, the expert system should return to its previous task. the above capability is difficult to obtain in prolog as it is not designed to be a real time language. it is also difficult for an expert system to stop the search for one answer, answer a second question, and then resume the first quest.  we are performing investigative research in the development of a real time prolog, called rt prolog, which would have the above capabilities. an expert system written in rt prolog would have the capability of responding to external interrupts and then resuming its original task. the interrupt can be serviced either in a procedural manner or by another copy of the expert system.  to accomplish this, the rt prolog interpreter will be developed as a task in ada. an interrupt then can activate another task as a service routine. this task can be a normal procedural service routine or even another copy of the prolog interpreter. this scheme should provide the needed flexibility to handle both the expert system and real time aspects of the problem.  rt prolog is being developed on an ibm at using the janus/ada compiler from rr software. the first step in the development was to build a small prolog interpreter in ada. this interpreter will then be made into a task type, so that other copies can be spawned, if needed. the last step will be to test the interrupt capability of the system by using a data acquisition system.  g. scott owen
a parallel `make' utility based on linda's tuple-space  we describe a prototype of a parallel `make' utility that executes on multiple workstations and achieves a significant real-time speedup. this utility is implemented by means of logically shared memory based on the linda system's tuple space. it makes work with distributed computing easy to conduct, since it can be built on top of an existing operating systems without modifying it, and since it permits easy experimentation with strategies for distributing the work.  c. j. fleckenstein d. hemmendinger
efficient object sampling via weak references  the performance of automatic memory management may be improved if the policies used in allocating and collecting objects had knowledge of the lifetimes of objects. to date, approaches to the pretenuring of objects in older generations have relied on profile-driven feedback gathered from trace runs. this feedback has been used to specialize allocation sites in a program. these approaches suffer from a number of limitations. we propose an alternative that through efficient sampling of objects allows for on-line adaption of allocation sites to improve the efficiency of the memory system. in doing so, we make use of a facility already present in many collectors such as those found in java virtual machines: weak references. by judiciously tracking a subset of allocated objects with weak references, we are able to gather the necessary statistics to make better object-placement decisions.  ole agesen alex garthwaite
structured programming in macintosh assembly language (abstract)  ever since dijkstra first pointed out the harmfulness of the goto twenty years ago, programmers in high-level language have become more and more accustomed to writing structured programs. no such development has taken place in assembly language due to the lack of such constructs as the if-then, if-then- else, while-do, and repeat-until statements of pascal.  it is possible, however, to achieve the same effect by the exercise of programming discipline if all branching in the program is made to follow the rules of structured programming. for example, an if-then statement such as if x = 0 then y := 1 else y := 2 endif may be implemented in macintosh assembly language as if1 tst.w x(a5) ;if x < then goto; else1 bne else1 move.w #1,y(a5) ;y := 1 bra endif1 ;goto endif1 else1 move.w #2,y(a5) ;y :=2 endif1  while such programs may appear somewhat strange at first, consistent application of the discipline makes it very easy to convert any algorithm expressed as a structured high-level language program to macintosh assembly language completely mechanically and, therefore, correctly.  a textbook on macintosh assembly language incorporating these principles is under development by the author.  clint foulk
new methods for dynamic storage allocation (fast fits)  the classical methods for implementing dynamic storage allocation can be summarized thus  first fit and best fit  the available blocks of storage are linked together in address order. storage is allocated from the first available block of sufficient length, or from a block with the minimum excess length. storage can be allocated or released in multiples of two words. in the long run, if numerous pieces of storage of more-or-less random lengths are allocated and released at more-or-less random intervals, the storage becomes fragmented, and a number of uselessly small blocks develop, particularly near the beginning of the list. although these fragments usually comprise a small proportion of the storage (typically around 10 per cent), a lot of time can be wasted chaining through them.  buddy methods  here the task of managing the storage is reduced in size by constraining the way in which the storage can be divided up, e.g. into blocks with lengths which are powers of 2. this eliminates chaining through long lists of uselessly small blocks; on the other hand, space is wasted in rounding up the length requested to an allowable size, and typically about 40 per cent more storage is required to satisfy the same allocations than when using first fit or best fit.  the methods presented in this paper are externally compatible with first fit and best fit, and require roughly the same amount of storage for a given sequence of allocations. they use, however, a completely different internal data structure, one effect of which is to reduce the number of blocks that have to be visited to perform a typical allocation or release operation. these new methods exhibit roughly the same space performance as first fit, and a time performance which falls between those of first fit and buddy.  c. j. stephenson
binding performance at language design time  an important research goal in software engineering and programming languages is the development of principles underlying the specification of computable problems, the translation of these problems into efficient and correct programs, and the performance analysis of these programs. this paper uncovers some of these principles, which are used to design a problem specification language l1 restricted to problems that can be compiled automatically into programs whose worst case asymptotic time and space complexities are linear in the input/output space. any problem expressible in l1 can be compiled into a linear cost program. a compiler for l1 has been implemented in the rapts transformational programming system.  j. cai r. paige
software architecture based on communicating residential environments  this paper describes an alternative approach to software architecture, where the classical division of responsibilities between operating systems, programming languages and compilers, and so forth is revised. our alternative is organized as a set of self-contained environments which are able to communicate pieces of software between them, and whose internal structure is predominantly descriptive and declarative. the base structure within each environment (its diversified shell) is designed so that it can accomodate such arriving software modules.  the presentation of that software architecture is done in the context of an operational implementation, the screen system (system of communicating residential environments).  erik sandewall claes strömberg henrik sörensen
error repair in shift-reduce parsers  local error repair of strings during cfg parsing requires the insertion and deletion of symbols in the region of a syntax error to produce a string that is error free. rather than precalculating tables at parser generation time to assist in finding such repairs, this article shows how such repairs can be found during shift-reduce parsing by using the parsing tables themselves. this results in a substantial space saving over methods that require precalculated tables. furthermore, the article shows how the method can be integrated with lookahead to avoid finding repairs that immediately result in further syntax errors. the article presents the results of experiments on a version of the lalr(1)-based parser generator bison to which the algorithm was added.  bruce j. mckenzie corey yeatman lorraine de vere
an annotation language for optimizing software libraries  this paper introduces an annotation language and a compiler that together can customize a library implementation for specific application needs. our approach is distinguished by its ability to exploit high level, domain- specific information in the customization process. in particular, the annotations provide semantic information that enables our compiler to analyze and optimize library operations as if they were primitives of a domain- specific language. thus, our approach yields many of the performance benefits of domain-specific languages, without the effort of developing a new compiler for each domain.  this paper presents the annotation language, describes its role in optimization, and illustrates the benefits of the overall approach. using a partially implemented compiler, we show how our system can significantly improve the performance of two applications written using the plapack parallel linear algebra library.  samuel z. guyer calvin lin
cellular disco: resource management using virtual clusters on shared-memory multiprocessors despite the fact that large-scale shared-memory multiprocessors have been commercially available for several years, system software that fully utilizes all their features is still not available, mostly due to the complexity and cost of making the required changes to the operating system. a recently proposed approach, called disco, substantially reduces this development cost by using a virtual machine monitor that leverages the existing operating system technology.in this paper we present a system called cellular disco that extends the disco work to provide all the advantages of the hardware partitioning and scalable operating system approaches. we argue that cellular disco can achieve these benefits at only a small fraction of the development cost of modifying the operating system. cellular disco effectively turns a large-scale shared-memory multiprocessor into a virtual cluster that supports fault containment and heterogeneity, while avoiding operating system scalability bottle-necks. yet at the same time, cellular disco preserves the benefits of a shared-memory multiprocessor by implementing dynamic, fine- grained resource sharing, and by allowing users to overcommit resources such as processors and memory. this hybrid approach requires a scalable resource manager that makes local decisions with limited information while still providing good global performance and fault containment.in this paper we describe our experience with a cellular disco prototype on a 32-processor sgi origin 2000 system. we show that the execution time penalty for this approach is low, typically within 10% of the best available commercial operating system for most workloads, and that it can manage the cpu and memory resources of the machine significantly better than the hardware partitioning approach. kinshuk govil dan teodosiu yongqiang huang mendel rosenblum
limitations on the portability of real time ada programs  this paper describes areas of the ada language where transportability is restricted by the fact that implementation choices are allowed. transportability guidelines have been developed previously for ada [2,3,10], but have taken the approach that only features of the language which are guaranteed to be supported by all implementations should be used. the "common intersection" approach rules out use of many features that were included in ada because they are required for real-time applications. this paper addresses the transportability of real-time ada programs from a realistic point of view. specifically, time-critical applications are of little use being transportable if they execute too slowly on all available implementations; and reasonable people will not wish to transport an application to architectures and/or compilation systems that do not support the requirements of the application.  a practical approach to managing these difficulties is presented as a set of transportability guidelines. these guidelines are intended to improve the transportability of programs which must rely on language features that are implementation dependent.  t. griest m. bender
a facility for the downward extension of a high-level language  this paper presents a method whereby a high-level language can be extended to provide access to all the capabilities of the underlying hardware and operating system of a machine. in essence, it is a facility that allows a user to make special purpose extensions to a language without requiring the compiler to be modified for each extension. extensions are specified in an assembler-like language that is used at compile time to produce executable code to be combined with compiler-generated code. this facility has been implemented in a systems-programming language and was designed to provide access to facilities not directly available in the language. the way in which the facility was implemented calls for a minimum of user-visible language changes and is well suited for generating code sequences for any language. the facility provides the extension writer access to information available in the high-level language during compilation, permits the selective generation of user-defined code sequences depending on the context in which they are being used, provides for the integration of this code with compiler-generated code, and provides for the generation of user-understandable error messages when an extension is used incorrectly.  thomas n. turba
an experimental study of people creating spreadsheets  nine experienced users of electronic spreadsheets each created three spreadsheets. although participants were quite confident that their spreadsheets were accurate, 44 percent of the spreadsheets contained user- generated programming errors. with regard to the spreadsheet creation process, we found that experienced spreadsheet users spend a large percentage of their time using the cursor keys, primarily for the purpose of moving the cursor around the spreadsheet. users did not spend a lot of time planning before launching into spreadsheet creation, nor did they spend much time in a separate, systematic debugging stage. participants spent 21 percent of their time pausing, presumably reading and/or thinking, prior to the initial keystrokes of spreadsheet creation episodes.  polly s. brown john d. gould
processor frequency setting for energy minimization of streaming multimedia application  in this paper, we describe a software-controlled approach for adaptively minimizing energy in embedded systems for realtime multimedia processing. energy is optimized by clock speed setting: the software controller dynamically adjusts processor clock speed to the frame rate requirements of the incoming multimedia stream. the speed-setting policy is based on a system model that correlates clock speed with best-case, average- case and worst-case sustainable frame rate, accounting for data-dependency in multimedia streams. experiments on an mp3 decoding application show that computational energy can be drastically reduced with respect to fixed- frequency operation.  andrea acquaviva luca benini bruno riccò
the promise of multiparadigm languages as pedagogical tools  this paper presents a discussion of why languages that support multiple paradigms (i.e. multiparadigm languages) have the potential to be good pedagogical tools for teaching programming skills. several examples are given that demonstrate how different programming paradigms are expressed in a working multiparadigm language. the examples, though brief, provide a glimpse of how much expressiveness a simple multiparadigm design can embody and they suggest that the potential role of multiparadigm languages as teaching tools is promising.  john placer
burs automata generation  a simple and efficient algorithm for generating bottom-up rewrite system (burs) tables is described. a small code- generator generator implementation produces burs tables efficiently, even for complex instruction set descriptions. the algorithm does not require novel data structures or complicated algorithmic techniques. previously published methods for on-the- fly elimination of states are generalized and simplified to create a new method, triangle trimming, that is employed in the algorithm. a prototype implementation, burg, generates burs tables very efficiently.  todd a. proebsting
io-lite: a unified i/o buffering and caching system  this article presents the design, implementation, and evaluation of io -lite, a unified i/o buffering and caching system for general-purpose operating systems. io-lite unifies all buffering and caching in the system, to the extent permitted by the hardware. in particular, it allows applications, the interprocess communication system, the file system, the file cache, and the network subsystem to safely and concurrently share a single physical copy of the data. protection and security are maintained through a combination of access control and read-only sharing. io-lite eliminates all copying and multiple buffering of i/o data, and enables various cross- subsystem optimizations. experiments with a web server show performance improvements between 40 and 80% on real workloads as a result of io- lite.  vivek s. pai peter druschel willy zwaenepoel
lightweight lexical source model extraction  software engineers maintaining an existing software system often depend on the mechanized extraction of information from system artifacts. some useful kinds of information---source models---are well known: call graphs, file dependences, etc. predicting every kind of source model that a software engineer may need is impossible. we have developed a lightweight approach for generating flexible and tolerant source model extractors from lexical specifications. the approach is lightweight in that the specifications are relatively small and easy to write. it is flexible in that there are few constraints on the kinds of artifacts from which source models are extracted (e.g., we can extract from source code, structured data files, documentation, etc.). it is tolerant in that there are few constraints on the condition of the artifacts. for example, we can extract from source that cannot necessarily be compiled. our approach extended the kinds of source models that can be easily produced from lexical information while avoiding the constraints and brittleness of most parser- based approaches. we have developed tools to support this approach and applied the tools to the extraction of a number of different source models (file dependences, event interactions, call graphs) from a variety of system artifacts (c, c++, clos, eiffel. tcl, structured data). we discuss our approach and describe its application to extract source models not available using existing systems; for example, we compute the implicitly-invokes relation over field tools. we compare and contrast our approach to the conventional lexical and syntactic approaches of generating source models.  gail c. murphy david notkin
profile-guided optimization across process boundaries  we describe a profile-driven compiler optimization technique for _inter- process optimization_, which dynamically inlines the effects of sending messages. profiling is used to find optimization opportunities, and to dynamically trigger recompilation and optimization at run-time. we apply the optimization technique on the concurrent programming language erlang, letting recompilation take place in a separate erlang process, and taking advantage of the facilities provided by erlang to dynamically replace code at run-time. we have implemented a prototype inter-process profiler and optimizer, that can handle small programs. measurements on synthetic benchmarks show encouraging speedups of up to 1.8 times.  erik johansson sven-olof nyström
optimizing compilation of clp( r )  constraint logic programming (clp) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or boolean functions. they have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. however, clp languages have mainly been considered as research systems, useful for rapid prototyping, by not really competitive with more conventional programming languages where efficiency is a more important consideration. one promising approach to improving the performance of clp systems is the use of powerful program optimizations to reduce the cost of constraint solving. we extend work in this area by describing a new optimizing compiler for the clp language clp( r ). the compiler implements six powerful optimizations: reordering of constraints, removal of redundant variables, and specialization of constraints which cannot fail. each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. we systematically evaluate the effectiveness of each optimization in isolation and in combination. our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.  andrew d. kelly kim marriott andrew macdonald peter j. stuckey roland yap
towards a discipline of class composition  assembling classes to form systems is a key concept in object-oriented software development. however, in order to be composed, classes have to be compatible in a certain way. in current object-oriented languages the compatibility with a specific behaviour is expressed by inheritance from a class which describes this behaviour. unfortunately inheritance is neither intended to express compatibility nor does it enforce compatibility. this deficiency may lead to inconsistent systems. therefore, in the project "10-- 14" inheritance is restricted to express compatibility between classes. two kinds of compatibilities are distinguished: compatibility required for the integration of subsystems (conformance) and compatibility required for reuse (imitation). a formal basis for the discipline is developed in order to get mathematically precise notions and to enable the verification of object- oriented systems. a design strategy is built on top of these compatibility notions. in actual case studies the discipline has already shown to support a clean design and to promote the reusability of class hierarchies.  franz weber