In his 1977 ACM Turing Award Lecture, John Backus identified the word-at-a-time style of programming, inherited from the underlying hardware and dubbed the "von Neumann bottleneck", as a major obstacle to the advancement of programming. In this keynote, I argue that the functional programming he advocated introduced its own bottleneck: that everything produced by a computation (including nothing) must be encoded as a single value. This "obligation to singularity" is foreign to modelling, where single values sit collegially between no values and two values. Exploring diverse examples, I will argue that adopting a modelling (de facto: relational) style of programming eliminates the functional bottleneck, and with it many of the data-to-control flow escapes that Backus originally sought to avoid.

Google’s Blockly library provides rudimentary support for types that constrain how blocks can be connected to form larger fragments. We argue that Blockly’s current type language does not reach beyond the level of context-freeness, and show how this can be changed — in a non-disruptive way — by adopting elements from attribute grammar and constraint-based typing. We demonstrate the generality of our approach by applying it to different languages, and describe our implementation and integration into Blockly.

Abstract At its core, OCL as currently defined is a first-order functional language: its expressions evaluate to single values, with collections accounting for multitudes of values, and special values and for partiality. By contrast, the data model providing the context of OCL expressions is inherently relational: the associations of UML class diagrams are essentially relations, with uniqueness and order designators extending expressiveness to ordered multirelations. As a result, OCL suffers from a functional/relational impedance mismatch, which is only superficially addressed by its navigation shorthands. At the same time, OCL is inherently unsafe: expressions containing subexpressions evaluating to may be invalid, translating to a runtime error in programming languages. We address this situation by turning OCL into a relational language that retains most of OCL’s original syntax and semantics, yet revises its fundamental design decisions that lead up to the noted problems. In particular, our version of OCL, which we call OCL $${^\sharp }$$ ♯ , is type-safe.

The dominant linguistic theory for specifying the syntax of software languages is Chomsky's phrase-structure grammar. However, for graphical block languages (such as Scratch and other languages defined using Google's Blockly library), we note that a different linguistic theory provides a better fitting model: the theory of dependency grammar. Indeed, as we make clear, there is a close, almost one-to-one correspondence between the specifications of graphical syntax required by Blockly and a classic capture of dependency grammar, which can be perfected by making only small extensions that remain entirely within the linguistic context. Taking the identified correspondence further suggests how Blockly languages can become context-sensitive, a requirement of many software languages that so far, Blockly addresses only in ad hoc ways.

Inside many software languages lives an expression language that caters for the computation of single values from single values. These languages' fixation on single-valuedness is often at odds with their application domains, in which many values, or plurals, regularly occur in the places of single. While the classical mathematical means of dealing with plurals is the set, in computing, other representations have evolved, notably strings and the much lesser known bunches. We review bunch theory in the context of expression languages including non-recursive functions, and show how giving bunches set semantics suggests that evaluating bunch functions amounts to computing with relations. We maintain that the ensuing seamless integration of relations in expression languages that otherwise know only functions makes a worthwhile contribution in a field in which the difference between modeling, with its preference for relations, and programming, with its preference for functions, is increasingly considered accidental.

To let expressions evaluate to no or many objects, most object-oriented programming languages require the use of special constructs that encode these cases as single objects or values. While the requirement to treat these standard situations idiomatically seems to be broadly accepted, I argue that its alternative, letting expressions evaluate to any number of objects directly, has several advantages that make it worthy of consideration. As a proof of concept, I present a core object-oriented programming language, dubbed Num , which separates number from type so that the type of an expression is independent of the number of objects it may evaluate to, thus removing one major obstacle to using no, one, and many objects uniformly. Furthermore, Num abandons null references, replaces the nullability of reference types with the more general notion of countability, and allows methods to be invoked on any number of objects, including no object. To be able to adapt behavior to the actual number of receivers, Num complements instance methods with plural methods, that is, with methods that operate on a number of objects jointly and that replace static methods known from other languages. An implementation of Num in Prolog and accompanying type and number safety proofs are presented.

Collaboration among programmers today mostly relies on file-based version control systems. These systems typically use optimistic locking to enable parallel work, meaning that competing edits (edit conflicts) are detected and have to be resolved at update or commit time. While merging edits can partly be automated, it is an error-prone task that can introduce inconsistencies. Pessimistic locking of the files to be edited does not appear to be a popular alternative, however, and in any case is insufficient to avoid inconsistency, since it does not account for the dependence of (code in) files on others. To address these problems, we show how the notions of atomicity, consistency, and isolation known from transactional databases can be enforced in the context of collaborative programming. We do so by presenting editing as a set of primitive edit operations applied to an abstract syntax graph overlaid by a constraint graph expressing the consistency criteria mandated by the rules of well-formedness of a language, and by deriving for every sequence of primitive edit operations the write- and read-locks sufficient to: perform the edit sequence, either completely or not at all, in isolation from others; and to achieve global consistency before committing.

Constraint-based refactoring generalizes constraint-based type refactoring as introduced by Tip et al. [61] by extending the coverage of change from types to names, locations, accessibilities, and other properties of program elements. Starting with a generic specification of refactoring tools, we systematically develop constraint-based refactoring as a generic solution to a certain class of refactoring problems and provide a condition under which constraint-based refactoring tools are proven correct for any given target language. Although compliance with this correctness condition is hard to prove for target languages whose semantics is not formally defined, we show how the condition gives rise to automated testing procedures. We present a novel algorithm based on constraint-logic programming for the generation of constraints from a program to be refactored, and demonstrate its time and space requirements by using it in the application of refactorings to open source programs. Summarizing earlier work, we show how the principles underlying constraint-based refactoring tools extend to ad hoc refactoring, cross-language refactoring, and model/code co-refactoring.

In the academic literature, many uses of the Object Constraint Language (OCL) have been proposed. By contrast, the utilization of OCL in contemporary modelling tools lags behind, suggesting that leverage of OCL remains limited in practice. We consider this undeserved, and present a scheme for partially evaluating OCL expressions that allows one to capitalize on given OCL specifications for a wide array of purposes using a single implementation: a partial evaluator of OCL.

While contemporary projectional editors make sure that the edited programs conform to the programming language's metamodel, they do not enforce that they are also well-formed, that is, that they obey the well-formedness rules defined for the language. We show how, based on a constraint-based capture of well-formedness, projectional editors can be empowered to enforce well-formedness in much the same way they enforce conformance with the metamodel. The resulting robust edits may be more complex than ordinary, well-formedness breaking edits, and hence may require more user involvement; yet, maintaining well-formedness at all times ensures that necessary corrections of a program are linked to the edit that necessitated them, and that the projectional editor's services are never compromised by inconsistent programs. Robust projectional editing is not a straitjacket, however: If a programmer prefers to work without it, its constraint-based capture of well-formedness will still catch all introduced errors - unlike many other editor services, well-formedness checking and robust editing are based on the same implementation, and are hence guaranteed to behave consistently.

Attribute grammars decorate the nodes of a program's parse tree with attributes whose values are defined by equations encoding the (static) semantics of a programming language. We show how replacing the equations of an attribute grammar with equivalent constraints that can be solved by a constraint solver allows us to compute repairs of a malformed program solely from a specification that was originally designed for checking its well-formedness. We present two repair modes --- shallow and deep fixing --- whose computed repair alternatives are guaranteed to repair every error on which they are invoked. While shallow fixing may introduce new errors, deep fixing never does; to make it tractable, we implement it using neighborhood search. We demonstrate the feasibility of our approach by implementing it on top of ExtendJ, an attribute grammar based Java compiler, and by applying it to an example from the Java EE context, detecting and fixing well-formedness errors (both real and injected) in a body of 14 open-source subject programs.

Programs may contain multiple faults, in which case their debugging can be parallelized. However, effective parallelization requires some guarantees that parallel debugging tasks do not address the same fault, an inherent problem of earlier, clustering-based approaches to parallel debugging. In this paper, we identify a number of fundamental trade-offs to be made when selecting algorithms for parallel debugging, and explore these trade-offs using one clustering algorithm and three algorithms from integer linear programming. Results of an evaluation involving a total of 75,000 faulty versions (with up to 32 injected faults) of 15 subject programs suggest that depending on the number of faults present and the trade-offs one is willing to accept, speed-ups much larger than previously reported can be achieved, even if all derived parallel debugging tasks are handled sequentially.

Resuming past work on coverage-based fault localization, we find that empirical assessments of its accuracy are subject to so many imponderables that they are of limited value. To improve on this situation, we have compiled a comprehensive list of threats to be considered when attempting such assessments in the future. In addition, we propose the establishment of theoretical lower and upper bounds of fault localization accuracy that depend on properties of the subject programs (including their test suites) only. We make a suggestion for a lower bound and show that well-known fault locators do not uniformly perform better.

Model-driven engineering suggests that models are the primary artefacts of software development. This means that models may be refactored even after code has been generated from them, in which case the code must be changed to reflect the refactoring. However, as we show neither re-generating the code from the refactored model nor applying an equivalent refactoring to the generated code is sufficient to keep model and code in sync - rather, model and code need to be refactored jointly. To enable this, we investigate the technical requirements of model/code co-refactoring, and implement a model-driven solution that we evaluate using a set of open-source programs and their structural models. Results suggest that our approach is feasible.

Coverage-based fault localization extends the utility of testing from detecting the presence of faults to their localization. While coverage-based fault localization has shown good evaluation results for the single fault case, its ability to localize several faults at once appears to be limited. In this paper, we show how two partitioning procedures borrowed from integer linear programming can help improve the accuracy of standard coverage-based fault locators in presence of multiple faults by breaking down the localization problem into several smaller ones that can be dealt with independently. Experimental results suggest that our approach is indeed useful, the more so as its cost appears to be negligible.

As with design patterns before, the naming and cataloguing of refactorings has contributed significantly to the recognition of the discipline. However, in practice concrete refactoring needs may deviate from what has been distilled as a named refactoring, and mapping these needs to a series of such refactorings — if at all possible — can be difficult. To address this, we propose a framework of specifying refactorings in an ad hoc fashion, and demonstrate its feasibility by presenting an implementation. Evaluation is done by simulating application through a user on a set of given sample programs. Results suggest that our proposal of ad hoc refactoring is, for the investigated scenarios at least, viable.

Automated tool support for refactoring is now widely available for mainstream programming languages such as Java. However, current refactoring tools are still quite fragile in practice and often fail to preserve program behavior or compilability. This is mainly because analyzing and transforming source code requires consideration of many language features that complicate program analysis, in particular intricate name lookup and access control rules. This paper introduces J_L, a lookup-free, access control-free representation of Java programs. We present algorithms for translating Java programs into J_L and vice versa, thereby making it possible to formulate refactorings entirely at the level of J_L and to rely on the translations to take care of naming and accessibility issues. We demonstrate how complex refactorings become more robust and powerful when lifted to J_L. Our approach has been implemented using the JastAddJ compiler framework, and evaluated by systematically performing two commonly used refactorings on an extensive suite of real-world Java applications. The evaluation shows that our tool correctly handles many cases where current refactoring tools fail to handle the complex rules for name binding and accessibility in Java.

Role objects are a widely recognized design pattern for representing objects that expose different properties in different contexts. By developing a tool that automatically refactors legacy code towards this pattern and by applying this tool to several programs, we have found not only that refactoring to role objects as currently defined produces code that is hard to read and to maintain, but also that the refactoring has preconditions so strong that it is rarely applicable in practice. We have therefore taken a fresh look at role objects and devised an alternative form that solves the exact same design problems, yet is much simpler to introduce and to maintain. We describe refactoring to this new, lightweight form of role objects in informal terms and report on the implementation of our refactoring tool for the JAVA programming language, presenting evidence of the refactoring's increased applicability in several sample programs.

The efficacy of mutation analysis depends heavily on its capability to mutate programs in such a way that they remain executable and exhibit deviating behaviour. Whereas the former requires knowledge about the syntax and static semantics of the programming language, the latter requires some least understanding of its dynamic semantics, i.e., how expressions are evaluated. We present an approach that is knowledgeable enough to generate only mutants that are both syntactically and semantically correct and likely exhibit non-equivalent behaviour. Our approach builds on our own prior work on constraint-based refactoring tools, and works by negating behaviour-preserving constraints. As a proof of concept we present an enhanced implementation of the Access Modifier Change operator for Java programs whose naive implementations create huge numbers of mutants that do not compile or leave behaviour unaltered. While we cannot guarantee that our generated mutants are non-equivalent, we can demonstrate a considerable reduction in the number of vain mutant generations, leading to substantial temporal savings.

Through implicit invocation, procedures are called without explicitly referencing them. Implicit announcement adds to this implicitness by not only keeping implicit which procedures are called, but also where or when—under implicit invocation with implicit announcement, the call site contains no signs of that, or what it calls. Recently, aspect-oriented programming has popularized implicit invocation with implicit announcement as a possibility to separate concerns that lead to interwoven code if conventional programming techniques are used. However, as has been noted elsewhere, as currently implemented it establishes strong implicit dependencies between components, hampering independent software development and evolution. To address this problem, we present a type-based modularization of implicit invocation with implicit announcement that is inspired by how interfaces and exceptions are realized in Java. By extending an existing compiler and by rewriting several programs to make use of our proposed language constructs, we found that the imposed declaration clutter tends to be moderate; in particular, we found that, for general applications of implicit invocation with implicit announcement, fears that programs utilizing our form of modularization become unreasonably verbose are unjustified.

Fault localization helps spotting faults in source code by exploiting automatically collected data. Deviating from other fault locators relying on hit spectra or test coverage information, we do not compute the likelihood of each possible fault location by evaluating its participation in failed and passed test cases, but rather search for each failed test case the set of possible fault locations explaining its failure. Assuming a probability distribution of the number of faults as the only other input, we can compute the probability of faultiness for each possible fault location in presence of arbitrarily many faults. As the main threat to the viability of our approach we identify its inherent complexity, for which we present two simple bypasses. First experiments show that while leaving room for improvement, our approach is already feasible in practical cases.

Because of the strong coupling of classes and the proliferation of unneeded class members induced by inheritance, the suggestion to use composition and delegation instead has become commonplace. The presentation of a corresponding refactoring in the literature may lead one to believe that such a transformation is a straightforward undertaking. However, closer analysis reveals that this refactoring is neither always possible, nor does it necessarily achieve its desired effect. We have therefore identified the necessary preconditions and realizable postconditions of the refactoring, and built a tool that can perform it completely automatically. By applying this tool to all subclasses of several open-source projects, we have collected evidence of the applicability of the refactoring and of its capability to deliver on its promises. The refactoring builds on constraint graphs originally developed for type inference to check the preconditions and to compute the necessary delegation as well as the subtype relationships that must be maintained.

Aspect-oriented programming is considered a promising new technology. As object-oriented programming did before, it is beginning to pervade all areas of software engineering. With its growing popularity, practitioners and academics alike are wondering whether they should start looking into it, or otherwise risk having missed an important development. The author of this essay finds that much of aspect-oriented programming's success seems to be based on the conception that it improves both modularity and the structure of code, while in fact, it works against the primary purposes of the two, namely independent development and understandability of programs. Not seeing any way of fixing this situation, he thinks the success of aspect-oriented programming to be paradoxical.