Search

Traditional quantitative research methods of data collection in programming, such as questionnaires and interviews, are the most common approaches for researchers in this field. However, in recent years, eye-tracking has been on the rise as a new method of collecting evidence of visual attention and the cognitive process of programmers. Eye-tracking has been used by researchers in the field of programming to analyze and understand a variety of tasks such as comprehension and debugging. In this article, we will focus on reporting how experiments that used eye-trackers in programming research are conducted, and the information that can be collected from these experiments. In this mapping study, we identify and report on 63 studies, published between 1990 and June 2017, collected and gathered via manual search on digital libraries and databases related to computer science and computer engineering. Among the five main areas of research interest are program comprehension and debugging, which received an increased interest in recent years, non-code comprehension, collaborative programming, and requirements traceability research, which had the fewest number of publications due to possible limitations of the eye-tracking technology in this type of experiments. We find that most of the participants in these studies were students and faculty members from institutions of higher learning, and while they performed programming tasks on a range of programming languages and programming representations, we find Java language and Unified Modeling Language (UML) representation to be the most used materials. We also report on a range of eye-trackers and attention tracking tools that have been utilized, and find Tobii eye-trackers to be the most used devices by researchers. [ABSTRACT FROM AUTHOR]

In 1990, Manber and Myers proposed suffix arrays as a space-saving alternative to suffix trees and described the first algorithms for suffix array construction and use. Since that time, and especially in the last few years, suffix array construction algorithms have proliferated in bewildering abundance. This survey paper attempts to provide simple high-level descriptions of these numerous algorithms that highlight both their distinctive features and their commonalities, while avoiding as much as possible the complexities of implementation details. New hybrid algorithms are also described. We provide comparisons of the algorithms' worst-case time complexity and use of additional space, together with results of recent experimental test runs on many of their implementations. [ABSTRACT FROM AUTHOR]

The construction of natural language interfaces to computers continues to be a major challenge. The need for such interfaces is growing now that speech recognition technology is becoming more readily available, and people cannot speak those computer-oriented formal languages that are frequently used to interact with computer applications. Much of the research related to the design and implementation of natural language interfaces has involved the use of high-level declarative programming languages. This is to be expected as the task is extremely difficult, involving syntactic and semantic analysis of potentially ambiguous input. The use of LISP and Prolog in this area is well documented. However, research involving the relatively new lazy functional programming paradigm is less well known. This paper provides a comprehensive survey of that research. [ABSTRACT FROM AUTHOR]

The article focuses on the editorial policy of the periodical "acm computing surveys." In the late 1960's members of the Association for Computing Machinery (ACM) perceived a need among its members for a journal that would help practitioners stay abreast of the rapidly evolving field. The periodical began publication in March 1969 with professor Bill Dorn as the editor in chief, responsible for refereeing and accepting papers. In 1973 an informal editorial panel was established and two years later this panel was formalized as an editorial board. There have since been special issues on programming, computer architecture, database management, software reliability, parallel processors, queuing network models of computer system performance, graphic standards, encryption, microprogramming, user psychology and computer music. The periodical has established a surveyors forum to allow readers to note errors and comment on papers published. The periodical publishes any survey or tutorial paper of work on any topic of interest to ACM, subject to the editorial board's reviewing standards.

The purpose of this paper is to show that logic provides a convenient formalism for studying classical database problems. There are two main parts to the paper, devoted respectively to conventional databases and deductive databases. In the first part, we focus on query languages, integrity modeling and maintenance, query optimization, and data dependencies. The second part deals mainly with the representation and manipulation of deduced facts and incomplete information. [ABSTRACT FROM AUTHOR]

Much has been learned in the last decade about concurrent programming. This paper identifies the major concepts of concurrent programming and describes some of the more important language notations for writing concurrent programs. The roles of processes, communication, and synchronization are discussed. Language notations for expressing concurrent execution and for specifying process interaction are surveyed. Synchronization primitives based on shared variables and on message passing are described. Finally, three general classes of concurrent programming languages are identified and compared. Much has been learned in the last decade about concurrent programming. This paper identifies the major concepts of concurrent programming and describes some of the more important language notations for writing concurrent programs. The roles of processes, communication, and synchronization are discussed. Language notations for expressing concurrent execution and for specifying process interaction are surveyed. Synchronization primitives based on shared variables and on message passing are described. Finally, three general classes of concurrent programming languages are identified and compared. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to indicate something of the nature of "good programming." In this context, programming is taken to mean the entire process of communication between humans and computers. The programming process is sub- divided into nine tasks, and an elementary discussion of each of these tasks is presented. Although the paper is primarily directed to the student or novice programmer, more experienced people may find it a worthwhile aid in codifying or reinforcing their experience. [ABSTRACT FROM AUTHOR]

Time and time again software projects, though undertaken by people of considerable intellectual ability, fail. This will doubtless be a continuing phenomenon, because software production is indeed a difficult task requiring wide-ranging skills. Certainly, no single paper can suddenly solve all the problems of software writing and eliminate the failures. The scope of this paper is limited to four stages in the execution of software projects, namely the planning, coding, testing, and final usage. These four crucial areas contain pitfalls that have been responsible for a large proportion of software failures, and it is hoped this paper will help avoid some of them. [ABSTRACT FROM AUTHOR]

The concept of "process" has come to play a central role in many efforts to master the complexity of large computer systems. The purpose of this paper is to discuss useful methods of structuring complex processes, and to relate these to the problems of improving the quality of large computer systems. Two distinct ways of structuring systems are presented, namely, process combination, and process abstraction; these are then used to discuss such topics as concurrency, synchronization, multiprogramming, interpreters, and programmable processors. This discussion is based on a set of precise definitions for such concepts as "process," "processor," "computation," "combination," and "abstraction." The paper relates these definitions to both current research and practical applications, with particular concern for the problems of the performance, reliability, and modifiability of computer systems. [ABSTRACT FROM AUTHOR]

The article presents computing survey's electronic symposium on the theory of computation. The 25th anniversary of the European Association for the Theoretical Computing Science (EATCS) was celebrated during the 24th session of the "International Colloquium on Automata, Languages and Programming (ICALP) Bologna, Italy, from July 7-11, 1997. More than 300 scientists participated in the conference and its satellite events. There were many stimulating discussing about the role of theory in computer science. Papers of the symposium are divided into subareas such as algorithms, analysis, concurrency, formal methods, syntax and semantics and complexity of cognitive models. Algorithms area includes papers on approximate algorithms, algorithm engineering and online algorithms. The analysis area includes papers on program analysis based on game semantics and on abstract interpretation. The two papers on the complexity of cognitive models deal with simulating free will and simulating the mind.

The article presents an overview of papers presented in the December 1974 issue of the periodical "acm computing surveys." All papers selected for publication in this issue cover a range of viewpoints about good programming. There is no fixed set of rules according to which clear, understandable and provable programs can be constructed. There are guidelines ofcourse but the individual programmer's style, his clarity of thought and creativity contribute significantly to the outcome. The first two papers in the issue deal with the relationship between better programming and environment.

The Vehicle Routing Problem (VRP) is a well-known research line in the optimization research community. Its different basic variants have been widely explored in the literature. Even though it has been studied for years, the research around it is still very active. The new tendency is mainly focused on applying this study case to real-life problems. Due to this trend, the Rich VRP arises: combining multiple constraints for tackling realistic problems. Nowadays, some studies have considered specific combinations of real-life constraints to define the emerging Rich VRP scopes. This work surveys the state of the art in the field, summarizing problem combinations, constraints defined, and approaches found. [ABSTRACT FROM AUTHOR]

Collaborative systems evaluation is always necessary to determine the impact a solution will have on the individuals, groups, and the organization. Several methods of evaluation have been proposed. These methods comprise a variety of approaches with various goals. Thus, the need for a strategy to select the most appropnate method for a specific case is clear. This research work presents a detailed framework to evaluate collaborative systems according to given variables and performance levels. The proposal assumes that evaluation is an evolving process during the system lifecycle. Therefore, the framework, illustrated with two examples, is complemented with a collection of guidelines to evaluste collaborative systems according to product development status. [ABSTRACT FROM AUTHOR]

Program code compression is an emerging research activity that is having an impact in several production areas such as networking and embedded systems. This is because the reduced-sized code can have a positive impact on network traffic and embedded system costs such as memory requirements and power consumption. Although code-size reduction is a relatively new research area, numerous publications already exist on it. The methods published usually have different motivations and a variety of application contexts. They may use different principles and their publications often use diverse notations. To our knowledge, there are no publications that present a good overview of this broad range of methods and give a useful assessment. This article surveys twelve methods and several related works appearing in some 50 papers published up to now. We provide extensive assessment criteria for evaluating the methods and offer a basis for comparison. We conclude that it is fairly hard to make any fair comparisons of the methods or draw conclusions about their applicability. [ABSTRACT FROM AUTHOR]

Well adapted to the loosely coupled nature of distributed interaction in large-scale applications, the publish/subscribe communication paradigm has recently received increasing attention. With systems based on the publish/subscribe interaction scheme, subscribers register their interest in an event, or a pattern of events, and are subsequently asynchronously notified of events generated by publishers. Many variants of the paradigm have recently been proposed, each variant being specifically adapted to some given application or network model. This paper factors out the common denominator underlying these variants: full decoupling of the communicating entities in time, space, and synchronization. We use these three decoupling dimensions to better identify commonalities and divergences with traditional interaction paradigms. The many variations on the theme of publish/subscribe are classified and synthesized. In particular, their respective benefits and shortcomings are discussed both in terms of interfaces and implementations. [ABSTRACT FROM AUTHOR]

Concurrent programming is conceptually harder to undertake and to understand than sequential programming, because a programmer has to manage the coexistence and coordination of multiple concurrent activities. To alleviate this task several high-level approaches to concurrent programming have been developed. For some high-level programming approaches, prototyping for facilitating early evaluation of new ideas is a central goal. Prototyping is used to explore the essential features of a proposed system through practical experimentation before its actual implementation to make the correct design choices early in the process of software development. Approaches to prototyping concurrent applications with very high-level programming systems intend to alleviate the development in different ways. Early experimentation with alternate design choices or problem decompositions for concurrent applications is suggested to make concurrent programming easier. This paper presents a survey of programming languages and systems for prototyping concurrent applications to review the state of the art in this area. The surveyed approaches are classified with respect to the prototyping process. [ABSTRACT FROM AUTHOR]

Structuring database records by considering data item usage can yield substantial efficiencies in the operating cost of database systems. However, since the number of possible physical record structures for database of practical significance is enormous, and their evaluation is extremely complex, determining efficient record structures by full enumeration is generally infeasible. This paper discusses the techniques of mathematical clustering, iterative grouping refinement, mathematical programming, and hierarchic aggregation, which can be used to quickly determine efficient record structures for large, shared databases. [ABSTRACT FROM AUTHOR]

Microcode compaction is an essential tool for the compilation of high-level language microprograms into microinstructions with parallel microoperations. Although guaranteeing minimum execution time is an exponentially complex problem, recent research indicates that it is not difficult to obtain practical results. This paper, which assumes no prior knowledge of microprogramming on the part of the reader, surveys the approaches that have been developed for compacting microcode. A comprehensive terminology for the area is presented, as well as a general model of processor behavior suitable for comparing the algorithms. Execution examples and a discussion of strengths and weaknesses are given for each of the four classes of local compaction algorithms: linear, critical path, branch and bound, and list scheduling. Local compaction, which applies to jump-free code, is fundamental to any compaction technique. The presentation emphasizes the conceptual distinction between data dependency and conflict analysis. [ABSTRACT FROM AUTHOR]

B-trees have become, de facto, a standard for file organization. File indexes of users, dedicated database systems, and general-purpose access methods have all been proposed and implemented using B-trees. This paper reviews B-trees and shows why they have been so successful. It discusses the major variations of the B-tree, especially the W-tree, contrasting the relative merits and costs of each implementation. It illustrates a general purpose access method which uses a B-tree. [ABSTRACT FROM AUTHOR]

This paper is a survey of parallel machine organizations and programming. Parallelism is defined in a broad sense, on the bit level, operation level, and algorithm level. A number of abstract and practical questions are discussed. First, fast techniques for evaluating arithmetic expressions and linear recurrences are treated. Next, whole programs are discussed, and some experimental results are presented. Finally, various aspects of machine organization are discussed, including processors, memories, and alignment networks. [ABSTRACT FROM AUTHOR]

This paper explains, in an introductory fashion, the method of specifying the correct behavior of a program by the use of input/output assertions and describes one method for showing that the program is correct with respect to those assertions. An initial assertion characterizes conditions expected to be true upon entry to the program and a final assertion characterizes conditions expected to be true upon exit from the program. When a program contains no branches, a technique known as symbolic execution can be used to show that the truth of the initial assertion upon entry guarantees the truth of the final assertion upon exit. More generally, for a program with branches one can define a symbolic execution tree. If there is an upper bound on the number of times each loop in such a program may be executed, a proof of correctness can be given by a simple traversal of the (finite) symbolic execution tree. However, for most programs, no fixed bound on the number of times each loop is executed exists and the corresponding symbolic execution trees are infinite. In order to prove the correctness of such programs, a more general assertion structure must be provided. The symbolic execution tree of such programs must be traversed inductively rather than explicitly. This leads naturally to the use of additional assertions which are called "inductive assertions." [ABSTRACT FROM AUTHOR]

New direction in Artificial Intelligence research have led to the need for certain novel features to be embedded in programming languages. This paper gives an overview of the nature of these features, and their implementation in four principal families of AI languages: SAIL; PLANNER/CONNIVER; QLISP/INTERLISP; AND POPLER/POP-2. The programming features described include: new data types and accessing mechanisms for stored expressions; more flexible control structures, including multiple processes and backtracking; pattern matching to allow comparison of data item with a template, and extraction of labeled subexpressions; and deductive mechanisms which allow the programming system to carry out certain activities including modifying the data base and deciding which subroutines to run next using only constraints and guidelines set up by the programmer. [ABSTRACT FROM AUTHOR]

This paper describes the evolution of language features for multiprogramming from event queues and semaphores to critical regions and monitors. It suggests that the choice of language concepts should be guided by two simple principles: First, it should be possible to understand a concurrent program in time- independent terms by an effort proportional to its size; secondly, it should be possible to state assumptions about invariant relationships among program components and have these assumptions checked automatically. The central problems of multiprogramming are illustrated by annotated algorithms written in a well-structured programming language. [ABSTRACT FROM AUTHOR]

This paper aims at discussing and classifying the various ways in which the object paradigm is used in concurrent and distributed contexts. We distinguish among the library approach, the integrative approach, and the reflective approach. The library approach applies object-oriented concepts, as they are, to structure concurrent and distributed systems through class libraries. The integrative approach consists of merging concepts such as object and activity, message passing, and transaction, etc. The reflective approach integrates class libraries intimately within an object-based programming language. We discuss and illustrate each of these and point out their complementary levels and goals. [ABSTRACT FROM AUTHOR]

This article presents an overview of the program transformation methodology. It focuses attention on the so-called "rules + strategies" approach in the case of functional and logic programs. The paper is intended to offer an introduction to the subject. The various techniques are illustrated via simple examples. It contents, transformation rules for functional programs, transformation strategies for functional programs, examples of transformations of functional programs; transformation rules and strategies for logic programs, transformation strategies for logic programs, examples of transformations of logic programs; other techniques for transforming functional and logic programs, schemata approach, partial evaluation, finite differencing and related techniques for program development. The transformation methodology is based on the kind of rules, it has some intrinsic complexity limitations in the sense that there exists a bound on the efficiency improvements that can be obtained via those rules. [ABSTRACT FROM AUTHOR]

Fringe analysis is a technique used to study the average behavior of search trees. In this paper we survey the main results regarding this technique, and we improve a previous asymptotic theorem. At the same time, we present new developments and applications of the theory that allow improvements in several bounds on the behavior of search trees. Our examples cover binary search trees, AVL-trees, 2-3 trees, and B-trees. [ABSTRACT FROM AUTHOR]

The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. The basic ideas presented here have been abstracted from this body of work, and the best algorithms known are given as examples. As the algorithms are explained, references to related algorithms and mathematical or experimental analyses are given. Suggestions are then made for choosing the algorithm best suited to a given situation. [ABSTRACT FROM AUTHOR]

The author comments on the paper "Concepts and Notations for Concurrent Programming," written by Gregory Andrews and Fred B. Schneider. In their paper, Andrews and Schneider define various chronization primitives based on message passing. They, however, neglected to mention the Send-Receive-Reply Inter-process Communication primitives available in Thoth and its derivatives. These Send-Receive-Reply primitives are similar to the remote procedure call but there is an important difference. With Send-Receive-Reply primitives, the server can multiplex calls and can make out of order replies if necessary. Additional case studies implementing these primitives are described. The author points out that the Send-Receive-Reply primitives of Thoth differ from remote procedures call primitives in allowing server to multiplex calls and to make out of order replies. Thoth style primitives are a nice combination of message passing and remote procedure calls. The versatility of the primitive derives largely from the fact that they are low level.

The article focuses on the papers published in the March 1983 issue of the periodical, "acm computing surveys." The papers in this issue describe the details of a level of abstraction. The concept of levels of abstraction is integral to work in system str

To program parallel systems efficiently and easily, a wide range of programming models have been proposed, each with different choices concerning synchronization and communication between parallel entities. Among them, the actor model is based on loosely coupled parallel entities that communicate by means of asynchronous messages and mailboxes. Some actor languages provide a strong integration with object-oriented concepts; these are often called active object languages. This article reviews four major actor and active object languages and compares them according to carefully chosen dimensions that cover central aspects of the programming paradigms and their implementation. [ABSTRACT FROM AUTHOR]

Security isolation is a foundation of computing systems that enables resilience to different forms of attacks. This article seeks to understand existing security isolation techniques by systematically classifying different approaches and analyzing their properties. We provide a hierarchical classification structure for grouping different security isolation techniques. At the top level, we consider two principal aspects: mechanism and policy. Each aspect is broken down into salient dimensions that describe key properties. We break the mechanism into two dimensions, enforcement location and isolation granularity, and break the policy aspect down into three dimensions: policy generation, policy configurability, and policy lifetime. We apply our classification to a set of representative articles that cover a breadth of security isolation techniques and discuss tradeoffs among different design choices and limitations of existing approaches. [ABSTRACT FROM AUTHOR]

Behavioural type systems, usually associated to concurrent or distributed computations, encompass concepts such as interfaces, communication protocols, and contracts, in addition to the traditional input/output operations. The behavioural type of a software component specifies its expected patterns of interaction using expressive type languages, so types can be used to determine automatically whether the component interacts correctly with other components. Two related important notions of behavioural types are those of session types and behavioural contracts. This article surveys the main accomplishments of the last 20 years within these two approaches. [ABSTRACT FROM AUTHOR]

The Partitioned Global Address Space (PGAS) model is a parallel programming model that aims to improve programmer productivity while at the same time aiming for high performance. The main premise of PGAS is that a globally shared address space improves productivity, but that a distinction between local and remote data accesses is required to allow performance optimizations and to support scalability on large-scale parallel architectures. To this end, PGAS preserves the global address space while embracing awareness of nonuniform communication costs. Today, about a dozen languages exist that adhere to the PGAS model. This survey proposes a definition and a taxonomy along four axes: how parallelism is introduced, how the address space is partitioned, how data is distributed among the partitions, and finally, how data is accessed across partitions. Our taxonomy reveals that today's PGAS languages focus on distributing regular data and distinguish only between local and remote data access cost, whereas the distribution of irregular data and the adoption of richer data access cost models remain open challenges. [ABSTRACT FROM AUTHOR]

This article focuses on September 1984 issue of "ACM Computing Surveys." Two articles in this issue explore efforts to improve system performance through parallelism. The articles examine parallel sorting algorithms. They present historical developments in parallel sorting, emphasizing feasibility of algorithms rather than their theoretical aspects. Most of these algorithms employ main memory, and are, therefore, internal sorting approaches, as contrasted with external sorting, where the size of the file to be sorted makes it impossible to use main memory exclusively. Another article discusses parallel algorithms and data structures for graph processing. Graphs are widely used, both in computer science and in related science and engineering fields. The paper gives attention to the feasibility of implementation of these algorithms on parallel processors. Much of the information in this article is very compactly presented in tabular form, showing the principal results by method, model, and complexity.

This article presents reply of authors in response to comments made by writer M. Stella Atkins on their paper entitled "Concepts and Notations for Concurrent Programming. Atkins points out that Send-Receive-Reply primitives of Thoth differ from remote procedures call primitives in allowing a server to multiplex calls and to make out of order replies. Actually, a server process can multiplex calls, for example, by nesting accept statements in Ada. In Distributed Processes, calls can be multiplexed because a new process is created to service each call and these processes can synchronize using a variant of conditional critical regions. Thoth-style primitives are a nice combination of message passing remote procedure calls. The versatility of the primitive derives largely from the fact that they are low level. The authors agree with Atkins that it is regrettable that proof rules for the Thoth primitives have not been developed. Lack of structure of Thoth primitives relative to remote procedures will make their proof rules more complex than those for remote procedures.

The article presents a brief summary of the articles published in the September 1980 issue of the journal ACM Computing Surveys, vol. 12, no. 3. This issue is about microprocessors, how they are fabricated and how, at one level, they are programmed. The first two papers comprise a special section on microprogramming edited by Stanley Habib. It discusses a different aspect of the problems involved in programming microprocessors at the level of extending the hardware interface. Programming, in all its many forms, is the acknowledged forte of the computer. Of course, computer scientists study theoretical aspects of software and hardware architectures, and delve into the mysteries of how the uninitiated user copes with programmed applications. They also analyze the information structures of social, psychological, or emotional systems, often in a search for appropriate application designs. All computer scientists share a need to realize and test their theoretical or practical ideas. And they can do so by programming or by having a system programmed for them.

Various research communities have independently arrived at stream processing as a programming model for efficient and parallel computing. These communities include digital signal processing, databases, operating systems, and complex event processing. Since each community faces applications with challenging performance requirements, each of them has developed some of the same optimizations, but often with conflicting terminology and unstated assumptions. This article presents a survey of optimizations for stream processing. It is aimed both at users who need to understand and guide the system's optimizer and at implementers who need to make engineering tradeoffs. To consolidate terminology, this article is organized as a catalog, in a style similar to catalogs of design patterns or refactorings. To make assumptions explicit and help understand tradeoffs, each optimization is presented with its safety constraints (when does it preserve correctness?) and a profitability experiment (when does it improve performance?). We hope that this survey will help future streaming system builders to stand on the shoulders of giants from not just their own community. [ABSTRACT FROM AUTHOR]

In the last two decades, the continuous increase of computational power has produced an overwhelming flow of data which has called for a paradigm shift in the computing architecture and large-scale data processing mechanisms. MapReduce is a simple and powerful programming model that enables easy development of scalable parallel applications to process vast amounts of data on large clusters of commodity machines. It isolates the application from the details of running a distributed program such as issues on data distribution, scheduling, and fault tolerance. However, the original implementation of the MapReduce framework had some limitations that have been tackled by many research efforts in several followup works after its introduction. This article provides a comprehensive survey for a family of approaches and mechanisms of large-scale data processing mechanisms that have been implemented based on the original idea of the MapReduce framework and are currently gaining a lot of momentum in both research and industrial communities. We also cover a set of introduced systems that have been implemented to provide declarative programming interfaces on top of the MapReduce framework. In addition, we review several large-scale data processing systems that resemble some of the ideas of the MapReduce framework for different purposes and application scenarios. Finally, we discuss some of the future research directions for implementing the next generation of MapReduce-like solutions. [ABSTRACT FROM AUTHOR]

Slicing is a technique, traditionally applied to programs, for extracting the parts of a program that affect the values computed at a statement of interest. In recent years authors have begun to consider slicing at model level. We present a detailed review of existing work on slicing at the level of finite-state-machine-based models. We focus on state-based modeling notations because these have received sufficient attention from the slicing community that there is now a coherent body of hitherto unsurveyed work. We also identify the challenges that state-based slicing presents and how the existing literature has addressed these. We conclude by identifying problems that remain open either because of the challenges involved in addressing them or because the community simply has yet to turn its attention to solving them [ABSTRACT FROM AUTHOR]

Reactive programming has recently gained popularity as a paradigm that is well-suited for developing event-driven and interactive applications. It facilitates the development of such applications by providing abstractions to express time-varying values and automatically managing dependencies between such values. A number of approaches have been recently proposed embedded in various languages such as Haskell, Scheme, JavaScript, Java, .NET, etc. This survey describes and provides a taxonomy of existing reactive programming approaches along six axes: representation of time-varying values, evaluation model, lifting operations, multidirectionality, glitch avoidance, and support for distribution. From this taxonomy, we observe that there are still open challenges in the field of reactive programming. For instance, multidirectionality is supported only by a small number of languages, which do not automatically track dependencies between time-varying values. Similarly, glitch avoidance, which is subtle in reactive programs, cannot be ensured in distributed reactive programs using the current techniques [ABSTRACT FROM AUTHOR]

A large class of applications need to execute the same workflow on different datasets of identical size. Efficient execution of such applications necessitates intelligent distribution of the application components and tasks on a parallel machine, and the execution can be orchestrated by utilizing task, data, pipelined, and/or replicated parallelism. The scheduling problem that encompasses all of these techniques is called pipelined workflow scheduling, and it has been widely studied in the last decade. Multiple models and algorithms have flourished to tackle various programming paradigms, constraints, machine behaviors, or optimization goals. This article surveys the field by summing up and structuring known results and approaches. [ABSTRACT FROM AUTHOR]

The most critical component of any adaptive numerical quadrature routine is the estimation of the integration error. Since the publication of the first algorithms in the 1960s, many error estimation schemes have been presented, evaluated, and discussed. This article presents a review of existing error estimation techniques and discusses their differences and their common features. Some common shortcomings of these algorithms are discussed, and a new general error estimation technique is presented. [ABSTRACT FROM AUTHOR]

Behavioral interface specification languages provide formal code-level annotations, such as preconditions, postconditions, invariants, and assertions that allow programmers to express the intended behavior of program modules. Such specifications are useful for precisely documenting program behavior, for guiding implementation, and for facilitating agreement between teams of programmers in modular development of software. When used in conjunction with automated analysis and program verification tools, such specifications can support detection of common code vulnerabilities, capture of light-weight application-specific semantic properties, generation of test cases and test oracles, and full formal program verification. This article surveys behavioral interface specification languages with a focus toward automatic program verification and with a view towards aiding the Verified Software Initiative—a fifteen-year, cooperative, international project directed at the scientific challenges of large-scale software verification. [ABSTRACT FROM AUTHOR]

The lack of memory safety in C/C++ often leads to vulnerabilities. Code injection attacks exploit these vulnerabilities to gain control over the execution flow of applications. These attacks have played a key role in many major security incidents. Consequently, a huge body of research on countermeasures exists. We provide a comprehensive and structured survey of vulnerabilities and countermeasures that operate at runtime. These countermeasures make different trade-offs in terms of performance, effectivity, compatibility, etc., making it hard to evaluate and compare countermeasures in a given context. We define a classification and evaluation framework on the basis of which countermeasures can be assessed. [ABSTRACT FROM AUTHOR]

This article surveys previous work on program slicing-based techniques. For each technique, we describe its features, its main applications, and a common example of slicing using such a technique. After discussing each technique separately, all of them are compared in order to clarify and establish the relations between them. This comparison gives rise to a classification of techniques which can help to guide future research directions in this field. [ABSTRACT FROM AUTHOR]

Programs are implemented in a variety of languages and contain serious vulnerabilities which might be exploited to cause security breaches. These vulnerabilities have been exploited in real life and caused damages to related stakeholders such as program users. As many security vulnerabilities belong to program code, many techniques have been applied to mitigate these vulnerabilities before program deployment. Unfortunately, there is no comprehensive comparative analysis of different vulnerability mitigation works. As a result, there exists an obscure mapping between the techniques, the addressed vulnerabilities, and the limitations of different approaches. This article attempts to address these issues. The work extensively compares and contrasts the existing program security vulnerability mitigation techniques, namely testing, static analysis, and hybrid analysis. We also discuss three other approaches employed to mitigate the most common program security vulnerabilities: secure programming, program transformation, and patching. The survey provides a comprehensive understanding of the current program security vulnerability mitigation approaches and challenges as well as their key characteristics and limitations. Moreover, our discussion highlights the open issues and future research directions in the area of program security vulnerability mitigation. [ABSTRACT FROM AUTHOR]

We present a survey of control-flow analysis of functional programs, which has been the subject of extensive investigation throughout the past 30 years. Analyses of the control flow of functional programs have been formulated in multiple settings and have led to many different approximations, starting with the seminal works of Jones, Shivers, and Sestoft. In this article, we survey control-flow analysis of functional programs by structuring the multitude of formulations and approximations and comparing them. [ABSTRACT FROM AUTHOR]

Aspect-orientation provides a new way of modularization by clearly separating crosscutting concerns from noncrosscutting ones. While aspect-orientation originally has emerged at the programming level, it now stretches also over other development phases. There are, for example, already several proposals for Aspect- Oriented Modeling (AOM), most of them pursuing distinguished goals, providing different concepts as well as notations, and showing various levels of maturity. Consequently, there is an urgent need to provide an indepth survey, clearly identifying commonalities and differences between current AOM approaches. Existing surveys in this area focus more on comprehensibility with respect to development phases or evaluated approaches rather than on comparability on bases of a detailed evaluation framework. This article tries to fill this gap focusing on aspect-oriented design modeling. As a prerequisite for an in-depth evaluation, a conceptual reference model is presented as the article's first contribution, centrally capturing the basic design concepts of AOM and their interrelationships in terms of a UML class diagram. Based on this conceptual reference model, an evaluation framework has been designed, resembling the second contribution, by deriving a detailed and well-defined catalogue of evaluation criteria, thereby operationalizing the conceptual reference model. This criteria catalogue is employed together with a running example in order to evaluate a carefully selected set of eight design-level AOM approaches representing the third contribution of the article. This per approach evaluation is complemented with an extensive report on lessons learned, summarizing the approaches' strengths and shortcomings. [ABSTRACT FROM AUTHOR]

Wireless sensor networks (WSNs) are attracting great interest in a number of application domains concerned with monitoring and control of physical phenomena, as they enable dense and untethered deployments at low cost and with unprecedented flexibility. However, application development is still one of the main hurdles to a wide adoption of WSN technology. In current real-world WSN deployments, programming is typically carried out very close to the operating system, therefore requiring the programmer to focus on low-level system issues. This not only distracts the programmer from the application logic, but also requires a technical background rarely found among application domain experts. The need for appropriate high-level programming abstractions, capable of simplifying the programming chore without sacrificing efficiency, has long been recognized, and several solutions have hitherto been proposed, which differ along many dimensions. In this article, we survey the state of the art in programming approaches for WSNs. We begin by presenting a taxonomy of WSN applications, to identify the fundamental requirements programming platforms must deal with. Then, we introduce a taxonomy of WSN programming approaches that captures the fundamental differences among existing solutions, and constitutes the core contribution of this article. Our presentation style relies on concrete examples and code snippets taken from programming platforms representative of the taxonomy dimensions being discussed. We use the taxonomy to provide an exhaustive classification of existing approaches. Moreover, we also map existing approaches back to the application requirements, therefore providing not only a complete view of the state of the art, but also useful insights for selecting the programming abstraction most appropriate to the application at hand. [ABSTRACT FROM AUTHOR]

Object-oriented programming represents an original implementation issue due to its philosophy of making the program behavior depend on the dynamic type of objects. This is expressed by the late binding mechanism, aka message sending. The underlying principle is that the address of the actually called procedure is not statically determined at compile-time, but depends on the dynamic type of a distinguished parameter known as the receiver. A similar issue arises with attributes, because their position in the object layout may also depend on the object's dynamic type. Furthermore, subtyping introduces another original feature (i.e., runtime subtype checks). All three mechanisms need specific implementations and data structures. In static typing, late binding is generally implemented with so-called virtual function tables. These tables reduce method calls to pointers to functions via a small fixed number of extra indirections. It follows that object-oriented programming yields some overhead, as compared to the usual procedural languages. The different techniques and their resulting overhead depend on several parameters. First, inheritance and subtyping may be single or multiple, and even a mixing is possible, as in Java and NET which present single inheritance for classes and multiple subtyping for interfaces. Multiple inheritance is a well-known complication. Second, the production of executable programs may involve various schemes, from global compilation, which implies the closed-world assumption (CWA), as the whole program is known at compile time, to separate compilation and dynamic loading, where each program unit is compiled and loaded independently of any usage, hence under the open-world assumption (OWA). Global compilation is well-known to facilitate optimization. This article reviews the various implementation techniques available in static typing and in the three cases of single inheritance, multiple inheritance, and multiple subtyping. This language-independent survey focuses on separate compilation and dynamic loading, as they represent the most commonly used and the most demanding framework. However, many works have been undertaken in the global compilation framework, mostly for dynamically typed languages, but also applied to the EIFFEL language. Hence, we also examine global techniques and how they can improve implementation efficiency. Finally, mixed frameworks that combine open and closed world assumptions are considered. For instance, just-in-time (JIT) compilers work under provisional CWA, at the expense of possible recompilations. In contrast, we present an experimental compiler-linker, where separate compilation implies the OWA, whereas the whole program is finally linked under the CWA. [ABSTRACT FROM AUTHOR]