waashk/acm huggingface dataset:
extending graham-glanville techniques for optimal code generation  we propose a new technique for constructing code-generator generators, which combines the advantages of the graham-glanville parsing technique and the bottom-up tree parsing approach. machine descriptions are similar to yacc specifications. the construction effectively generates a pushdown automaton as the matching device. this device is able to handle ambigious grammars, and can be used to generate locally optimal code without the use of heuristics. cost computations are performed at preprocessing time. the class of regular tree grammars augmented with costs that can be handled by our system properly includes those that can be handled by bottom-up systems based on finite-state tree parsing automata. parsing time is linear in the size of the subject tree. we have tested the system on specifications for some systems and report table sizes.
code analysis of saftey-critical and real-time software using asis the ravenscar profile is a restricted tasking profile that supports applications requiring separate threads of control yet would satisfy the certification requirements of high-integrity (safety-critical) real-time systems. if the ravenscar profile were to be used for systems having safety-critical and real- time requirements, it would be valuable to demonstrate that the application satisfies the restrictions. code analysis is an important technique to support this demonstration. ada semantic interface specification (asis) based tools provide an excellent capability for the automatic identification of violations to that set of the ravenscar profile restrictions, which can be determined through static code analysis. all but one of these restrictions can be identified using static code analysis using asis. this paper provides an approach to building such an asis-based tool. this tool might promote the use of automatic tools for the analysis of the ravenscar profile and other tasking profiles to support safety-critical and real-time requirements. this paper should be viewed as work in progress. william currie colket
local type inference  we study two partial type inference methods for a language combining subtyping and impredicative polymorphism. both methods are local in the sense that missing annotations are recovered using only information from adjacent nodes in the syntax tree, without long-distance constraints such as unification variables. one method infers type arguments in polymorphic applications using a local constraint solver. the other infers annotations on bound variables in function abstractions by propagating type constraints downward from enclosing application nodes. we motivate our design choices by a statistical analysis of the uses of type inference in a sizable body of existing ml code.  benjamin c. pierce david n. turner
an example of process description in hfsp  hfsp considers software activities, in the first approximation, as mathematical functions which map their input objects to output objects and define them though hierarchical functional definition. activity a with input x1, …, xn and output y1, …, ym is denoted by a(x1 , …, xn | y1, …, ym). execution of a is performed functionally and it does nothing other than computing y1, …, ym from x1, …, xn. we call x1, … xn, y1, … ym attributes of a. if the activity is complex and cannot be performed by simply invoking tools, we have to decompose it into subactivities. we continue this decomposition process until every activity resulted from decomposition becomes a primitive one which could be performed by invoking existing tools or performed by human mental activity such as thinking or decision making.  activity decomposition must specify how an activity, say a, is decomposed into subactivities a1, … ak and what relationship e holds among attributes of the activities involved. it also has to specify the condition c when this decomposition can happen. a a1, …, ak when c where e. figure 1 shows a hfsp description of a simplified version jsp process where every step can be completed successfully. it consists of type definition, object and tool definition and activity definition part. the activity definition part defines jsp process as a set of activity decompositions. it also specifies how attributes are bind to the values of objects in the objectbase and this is described in the with section using get and put. for the activities defined here, no decomposition condition is attached as every activity is decomposed uniquely.  explicit definitions for attributes are omitted in this example as we use the following convention: when an output attribute y of an activity ai is given to another activity aj as one of its input attribute x, we omit the attribute definition x = y. instead, we put y for x in aj. we also used the convention that the name of a type is used as the name of an attribute of the type. if there are several attributes of the same type, we distinguish them by attaching modifier of the form `.xxx` to the type, like in `datatree.in` and `datatree.out`.  this process description is only valid for the case that we never make a mistake in performing activities and the specification given is simple enough. redoing is introduced in hfsp to handle the cases when these conditions are not met[2,3]. figure 2 is an example of a redoing decomposition applied to the case where (1) extracting data structure is mistaken in `makeprogtree` step, (2) it is detected in `composetree' and (3) `makeprogtree` has to be redone. in figure 3, redoing is used to cope with structure clash. `ordercarsh` found in `composetree` is handled by redoing `makeprogtree`.  takuya katayama masato suzuki
collaboration and composition: issues for a second generation process language  over the past decade a variety of process languages have been defined and applied to software engineering environments. the idea of using a process language to encode a software process as a "process model", and enacting this using a process-sensitive environment is now well established. many prototype process-sensitive environments have been developed; but their use in earnest has been limited. we are designing a second generation process language which is a significant departure from current conventional thinking. firstly a process is viewed as a set of mediated collaborations rather than a set of partially ordered activities. secondly emphasis is given to how process models are developed, used, and enhanced over a potentially long lifetime. in particular the issue of composing both new and existing model fragments is central to our development approach. this paper outlines these features, and gives the motivations behind them. it also presents a view of process support for software engineering drawing on our decade of experience in exploiting a "first generation" process language, and our experience in designing and exploiting programming languages.  b. c. warboys d. balasubramaniam r. m. greenwood g. n. c. kirby k. mayes r. morrison d. s. munro
improvements to graph coloring register allocation  we describe two improvements to chaitin-style graph coloring register allocators. the first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. the second extends chaitin's treatment of rematerialization to handle a larger class of values. these techniques are complementary. optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilling is unavoidable. rematerialization lowers the cost of spilling some values. this paper describes both of the techniques and our experience building and using register allocators that incorporate them. it provides a detailed description of optimistic coloring and rematerialization. it presents experimental data to show the performance of several versions of the register allocator on a suite of fortran programs. it discusses several insights that we discovered only after repeated implementation of these allocators.  preston briggs keith d. cooper linda torczon
a retro/prospective on apl graphpak this paper suggests two general directions that one could take to modernize apl2 graphpak and revitalize its evolution. one direction springboards off lessons learned during graphpak's first decade and from some thinking that evolved during early (c. 1980) experiments with general arrays. the second direction exploits general arrays and apl2 functionality at a user-level. some experiments are reported relating to both areas walt niehoff
specification-based testing of synchronous software synchronous programming makes the implementation of reactive software easier and safer. automatic formal verification methods based on model-checking have been developed within the synchronous approach to prove the satisfaction by the software of safety properties. but these methods often require huge memory or time amounts. as a solution to that problem we propose a set of formally defined testing techniques allowing for automatic test data generation. these techniques can be used independently or as a complement to formal verification, since they need the same set of specifications. ioannis parissis farid ouabdesselam
efficient high-level iteration with accumulators  accumulators are proposed as a new type of high-level iteration construct for imperative languages. accumulators are user-programmed mechanisms for successively combining a sequence of values into a single result value. the accumulated result can either be a simple numeric value such as the sum of a series or a data structure such as a list. accumulators naturally complement constructs that allow iteration through user-programmed sequences of values such as the iterators of clu and the generators of alphard. a practical design for high-level iteration is illustrated by way of an extension to modula-2 called modula plus. the extension incorporates both a redesigned mechanism for iterators as well as the accumulator design. several applications are illustrated including both numeric and data structure accumulation. it is shown that the design supports efficient iteration both because it is amenable to implementation via in-line coding and because it allows high-level iteration concepts to be implemented as encapsulations of efficient low-level manipulations.  robert d. cameron
an axiomatic approach to information flow in programs  a new approach to information flow in sequential and parallel programs is presented. flow proof rules that capture the information flow semantics of a variety of statements are given and used to construct program flow proofs. the method is illustrated by examples. the applications of flow proofs to certifying information flow policies and to solving the confinement problem are considered. it is also shown that flow rules and correctness rules can be combined to form an even more powerful proof system.  gregory r. andrews richard p. reitman
designing families of data types using exemplars  designing data types in isolation is fundamentally different from designing them for integration into communities of data types, especially when inheritance is a fundamental issue. moreover, we can distinguish between the design of families--- integrated types that are variations of each other---and more general communities where totally different but cohesive collections of types support specific applications (e.g., a compiler). we are concerned with the design of integrated families of data types as opposed to individual data types; that is, on the issues that arise when the focus is intermediate between the design of individual data types and more general communities of data types. we argue that design at this level is not adequately served by systems providing only class-based inheritance hierarchies and that systems which additionally provide a coupled subtype specification hierarchy are still not adequate. we propose a system that provides an unlimited number of uncoupled specification hierarchies and illustrate it with three: a subtype hierarchy, a specialization/generalization hierarchy, and a like hierarchy. we also resurrect a relatively unknown smalltalk design methodology that we call programming-by-exemplars and argue that it is an important addition to a designer's grab bag of techniques. the methodology is used to show that the subtype hierarchy must be decoupled from the inheritance hierarchy, something that other researchers have also suggested. however, we do so in the context of exemplar-based systems to additionally show that they can already support the extensions required without modification and that they lead to a better separation between users and implementers, since classes and exemplars can be related in more flexible ways. we also suggest that class-based systems need the notion of private types if they are to surmount their current limitations. our points are made in the guise of designing a family of list data types. among these is a new variety of lists that havenever been previously published: prefix-sharing lists. we also argue that there is a need for familial classes to serve as an intermediary between users and the members of a family.  wilf r. lalonde
fast mutual exclusion for uniprocessors  in this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as test-and-set) on a uniprocessor. a thread that is suspended within a restartable atomic sequence is resumed by the operating system at the beginning of the sequence, rather than at the point of suspension. this guarantees that the thread eventually executes the sequence atomically. a restartable atomic sequence has significantly less overhead than other software-based synchronization mechanisms, such as kernel emulation or software reservation. consequently, it is an attractive alternative for use on uniprocessors that do no support atomic operations. even on processors that do support atomic operations in hardware, restartable atomic sequences can have lower overhead.  we describe different implementations of restartable atomic sequences for the mach 3.0 and taos operating systems. these systems' thread management packages rely on atomic operations to implement higher-level mutual exclusion facilities. we show that improving the performance of low-level atomic operations, and therefore mutual exclusion mechanisms, improves application performance.  brian n. bershad david d. redell john r. ellis
object structure in the emerald system  emerald is an object-based language for the construction of distributed applications. the principal features of emerald include a uniform object model appropriate for programming both private local objects and shared remote objects, and a type system that permits multiple user-defined and compiler- defined implementations. emerald objects are fully mobile and can move from node to node within the network, even during an invocation. this paper discusses the structure, programming, and implementation of emerald objects, and emerald's use of abstract types.  andrew black norman hutchinson eric jul henry levy
extensions for multi-module records in conventional programming languages  an extended record facility is described that supports multi-module records by providing:  incremental and distributed record type definition, allowing field names of a record to be declared in different modules with different subscopes relative to the root record declaration.  field-level declaration of access to records by modules and procedures.  specification of record representation in terms of the underlying computer memory.  we also describe the uses of records that motivate these extensions as well as the compiler modifications required to implement this extended record facility.  from this work, we conclude that the extended record support can be added as a simple, natural extension to existing programming language designs and its implementation entails only modest additions to the compiler and linker with no significant compilation time cost.  d. r. cheriton m. e. wolf
extensions to static scoping  scope rules are presented as they appear in the language l, which is currently under development at mcgill. these rules permit a programmer to specify explicitly the duration and visibility of all objects. such specification can be used to declare variables or to create data structures which persist from one invocation of a block to the next. in addition, the data may be caused to persist from one run of the program to the next, obviating temporary files which are outside the scope and control of the programming language. the visibility of an object may also be specified to be larger than the block that contains its declaration. this facility allows the programmer to export some objects, yet keep others private. finally, a facility for call-site visibility is presented that provides some of the expressive power of dynamic scoping and macros without their inherent type insecurity.  g. v. cormack
the ctalk programming language: a strategic evolution of apl  this document presents ctalk, which is a new programming language quite different from apl itself. ctalk is an attempt to combine the "best" features of apl, but also of other languages such as lisp [9], and offer a language that looks "satisfactory" according to the criteria of the mainstream of computer science.  the most important features of ctalk are its syntax, which is very close to the one of the c programming language, the adoption of fundamental conceps that were missing in apl, such as lexical binding, but also the integration of a wide range of array operations that are borrowed from apl./par>  it is shown here that ctalk can be implemented more simply and more efficiently than apl, while keeping all the power of apl operations, and being an acceptable alternative to apl itself.  jean-jacques girardot
the effects of symbology and spatial arrangement on the comprehension of software specifications  seventy-two participants were presented with specifications for each of three modular-sized computer programs. nine different specification formats were prepared for each program. these formats varied along two dimensions: type of symbology and spatial arrangement. the type of symbology included natural language, constrained language (pdl), and ideograms (flowchart symbols). the spatial arrangement included sequential, branching, and hierarchical versions. the participants answered a series of comprehension questions on each program using only the program specifications. three types of questions were presented: forward-tracing, backward-tracing, and input-output. both forward- and backward-tracing questions were answered more quickly from specifications presented in pdl or ideograms than in natural language. forward-tracing questions were answered most quickly from a branching arrangement, and backward-tracing questions were answered more quickly from branching and hierarchical arrangements. response times to the input-output questions did not vary significantly as a function of the type of symbology or the spatial arrangement.  sylvia b. sheppard elizabeth kruesi bill curtis
an approach to communication-efficient data redistribution  we address the development of efficient methods for performing data redistribution of arrays on distributed-memory machines. data redistribution is important for the distributed-memory implementation of data parallel languages such as high performance fortran. an algebraic representation of regular data distributions is used to develop an analytical model for evaluating the communication cost of data redistribution. using this algebraic representation and the analytical model, an approach to communication- efficient data redistribution is developed. implementation results on the intel ipsc/860 are reported.  s. d. kaushik c.-h. huang r. w. johnson p. sadayappan
determining the extent of lookahead in syntactic error repair  many syntactic error repair strategies examine several additional symbols of input to guide the choice of a repair; a problem is determining how many symbols to examine. the goal of gathering all relevant information is discussed and shown to be impractical; instead we can gather all information relevant to choosing among a set of "minimal repairs." we show that finding symbols with the property "moderate phrase-level uniqueness" is sufficient to establish that all information relevant to these minimal repairs has been seen. empirical results on the occurrence of such symbols in pascal are presented.  jon mauney charles n. fischer
programming in j/windows  j has been available as shareware for the last four years. the core language has been largely complete from outset, but it is only comparatively recently that the implementation (at least for the pc) has included features needed for serious application development.  the most significant change was the introduction of windows support in release 6, which for the first time allowed full screen applications to be written in j. following the release of 6.2, which included many additions to the windows support and a much better session manager, i started using the windows version of j in small applications, for which i would normally have used apl. since then i have switched over to using j for almost all development, except for client work where apl is specifically required. i believe that j is already comparable to commercial apl's for application development and will soon be superior.  in this paper, i will describe programming the j/windows interface, and discuss some practical considerations in using it.  chris burke
software reliability measurement session  many people think of reliability as a devoutly wished for but seldom present attribute of a program. this leads to the idea that one should make a program as reliable as one possibly can. unfortunately, in the real world software reliability is usually achieved at the expense of some other characteristic of the product such as program size, run or response time, maintainability, etc. or the process of producing the product such as cost, resource requirements, scheduling, etc. one wishes to make explicit trade-offs among the software product and process rather than let them happen by chance. such trade-offs imply the need for measurement. because of mounting development and operational costs, pressures for obtaining better ways of measuring reliability, have been mounting. this session deals with this crucial area.  john d. musa
control system development tools  this paper provides a core of apl algorithms for control system development and demonstrates their use by solving a typical control problem. in doing so it outlines useful numerical techniques for simulating dynamic systems and for solving some of the central equations of control theory.  although some sections of the paper are addressed to apl2 users, the majority of the paper applies to apl. moreover, by doing a little extra work to handle complex numbers and by installing a "callable" compiled eigenvalue-eigenvector routine, all of the material presented can be adapted to any apl system.  while apl is a comfortable environment for control system development, apl2 contains two especially useful enhancements: 1) complex numbers included in a natural way, and 2) the function eigen.  apl2's facility with complex numbers permits the direct and clear coding of frequency domain methods such as root locus, bode plots, and the generation of transfer functions. apl2's facility with complex numbers also makes it possible to include a native eigenvalue-eigenvector utility function, eigen. this function generates the eigenvalues and eigenvectors of general square matrices, which can then be used for root locus studies, for transforming system equations to canonical forms, and for efficiently solving the riccati and lyapunov equations.  non- eigen-based functions are also provided so that all apl users will find enough tools to model, simulate, analyze, and develop regulators, observers, and filters for linear dynamic systems.  scott kimbrough