Onward! 2016 – Proceedings

Message from the Chairs
Welcome to Onward!.
Onward! is a premier multidisciplinary conference focused on everything to do with programming and software, including processes, methods, languages, communities, and applications. Onward! is more radical, more visionary, and more open than other conferences to ideas that are well-argued but not yet proven. Onward! welcomes different ways of thinking about approaching and reporting on programming language and software engineering research. Onward! 2016 is part of SPLASH 2016 and we are thrilled to be gathering in Amsterdam, The Netherlands, October 30–November 4, 2016, to break new ground in software research.

ONWARD Papers

Papers I

Lightweight Programming Experiments without Programmers and Programs: An Example Study on the Effect of Similarity and Number of Object Identifiers on the Readability of Source Code using Natural Texts
Tim Marter, Paul Babucke, Philipp Lembken, and Stefan Hanenberg
(University of Duisburg-Essen, Germany)
It is often said that controlled experiments should check the effect of programming languages or styles on programming. But it is also often said that running controlled experiments is a very time consuming and error prone task – that's why a lot of researchers do not run such experiments. Both arguments are plausible, but there is potentially an alternative: lightweight experiments where the effort to run such experiments is low and which (still) fulfill the requirements of controlled experiments with two exceptions: First, these experiments do not use programmers as subjects, and second, the experiments do not contain programming tasks. Instead, such experiments try to find analogies from other domains where the topic to be studied is (still) close enough to the original target domain but where it is easier to find participants and experimental setups. This paper illustrates such a lightweight experiment by introducing a study on the effect of number of identifiers and similarity of identifiers on (code) readability – without using source code and without programmers as subjects. The result of the experiment is comparable to other experimental results which gives a first indicator that it is possible to run such lightweight experiments that approximate the results of full-blown experiments. This paper argues that such lightweight experiments could be useful in the process of experimentation – they cannot and should not supersede full-blown experiments, but they can help in early stages of experimentation.

Emergent Software Services
Nicolás Cardozo
(University of Los Andes, Colombia)
Services are normally composed following a structured model, or based on a particular goal that needs to be fulfilled. Such model is problematic for pervasive environments, since service components deployed in the environment are unknown beforehand. As a result, services may never execute due to the unavailability of one of the pre-specified components, or components missing to fulfill the service goal. This paper posits a new vision for service composition by inverting the control flow of service-oriented applications between users and the environment. Rather than having to request a particular service, services emerge from the environment based on interactions between available service components, and are pushed to be utilized by users. We present the architecture required to fulfill our vision in enabling service emergence in a pervasive environment. This vision architecture is realized by an initial prototype framework for software service emergence called Mordor. Early results of this vision are obtained from two examples demonstrating the feasibility of services emergence from previously unknown service components, and a case study demonstrating Mordor's usability in real world scenarios.

Nez: Practical Open Grammar Language
Kimio Kuramitsu
(Yokohama National University, Japan)
Nez is a PEG(Parsing Expressing Grammar)-based open grammar language that allows us to describe complex syntax constructs without action code. Since open grammars are declarative and free from a host programming language of parsers, software engineering tools and other parser applications can reuse once-defined grammars across programming languages.
A key challenge to achieve practical open grammars is the expressiveness of syntax constructs and the resulting parser performance, as the traditional action code approach has provided very pragmatic solutions to these two issues. In Nez, we extend the symbol-based state management to recognize context-sensitive language syntax, which often appears in major programming languages. In addition, the Abstract Syntax Tree constructor allows us to make flexible tree structures, including the left-associative pair of trees. Due to these extensions, we have demonstrated that Nez can parse many grammars of practical programming languages.
Nez can generate various types of parsers since all Nez operations are independent of a specific parser language. To highlight this feature, we have implemented Nez with dynamic parsing, which allows users to integrate a Nez parser as a parser library that loads a grammar at runtime. To achieve its practical performance, Nez operators are assembled into low-level virtual machine instructions, including automated state modifications when backtracking, transactional controls of AST construction, and efficient memoization in packrat parsing. We demonstrate that Nez dynamic parsers achieve very competitive performance compared to existing efficient parser generators.

Exploring Cheap Type Inference Heuristics in Dynamically Typed Languages
Nevena Milojković and Oscar Nierstrasz
(University of Bern, Switzerland)
Although dynamically typed languages allow developers to be more productive in writing source code, their lack of in- formation about types of variables is one of the main obstacles during program comprehension. Static type information helps developers to decrease software maintenance time. Inference of types of variables requires complex algorithms to avoid false positives or negatives. Their main aim is to shorten the list of possible types for a variable. We have developed a couple of cheap heuristics that use easily accessible information about the presence of each class in the available source code to promote the correct type towards the top of the list of possible types for a variable. Our evaluation of a proof-of-concept prototype, implemented in Pharo Smalltalk, shows that both for domain- specific types and standard libraries these heuristics tend to work well. The evaluated heuristics prove to be reasonably precise, promoting the correct types of a variable towards the top of the list in 50.67% up to 89.09% of cases on average, depending on the applied heuristic. The heuristic that has proved to be the best was compared with one existing type inference algorithm and the best heuristic yields significantly better results with less effort.

Papers II

Bloqqi: Modular Feature-Based Block Diagram Programming
Niklas Fors and Görel Hedin
(Lund University, Sweden)
Automation programming is typically done using blocks and dataflow connections, in diagram languages that support user-defined block types. Often, these types are intended to be instantiated and connected to other blocks in common patterns, corresponding to anticipated variability. We present the new language mechanisms of wirings and recommendations that allow these intentions to be encoded as features in libraries. A wiring describes how a given block is typically connected to other blocks, and a recommendation describes where such a wiring is typically applied as a feature. This allows feature-based wizards to be generated for user-defined libraries, making it easy to construct applications that make use of the encoded patterns.

Building White-Box Abstractions by Program Refinement
Mehrdad Afshari and Zhendong Su
(University of California at Davis, USA)
Abstractions make building complex systems possible. Many facilities provided by a modern programming language are directly designed to build a certain style of abstraction. Abstractions also aim to enhance code reusability, thus enhancing programmer productivity and effectiveness.
Real-world software systems can grow to have a complicated hierarchy of abstractions. Often, the hierarchy grows unnecessarily deep, because the programmers have envisioned the most generic use cases for a piece of code to make it reusable. Sometimes, the abstractions used in the program are not the appropriate ones, and it would be simpler for the higher level client to circumvent such abstractions. Another problem is the impedance mismatch between different pieces of code or libraries coming from different projects that are not designed to work together. Interoperability between such libraries are often hindered by abstractions, by design, in the name of hiding implementation details and encapsulation. These problems necessitate forms of abstraction that are easy to manipulate if needed.
In this paper, we describe a powerful mechanism to create white-box abstractions, that encourage flatter hierarchies of abstraction and ease of manipulation and customization when necessary: program refinement.
In so doing, we rely on the basic principle that writing directly in the host programming language is as least restrictive as one can get in terms of expressiveness, and allow the programmer to reuse and customize existing code snippets to address their specific needs.

Function Passing: A Model for Typed, Distributed Functional Programming
Heather Miller, Philipp Haller, Normen Müller, and Jocelyn Boullier
(EPFL, Switzerland; KTH, Sweden; Trivadis, Germany)
The most successful systems for “big data” processing have all adopted functional APIs. We present a new programming model we call function passing designed to provide a more principled substrate on which to build data-centric distributed systems. A key idea is to build up a persistent functional data structure representing transformations on distributed immutable data by passing well-typed serializable functions over the wire and applying them to this distributed data. Thus, the function passing model can be thought of as a persistent functional data structure that is distributed, where transformations to data are stored in its nodes rather than the distributed data itself. The model simplifies failure recovery by design–in the event of a failure, data is recovered by replaying function applications atop immutable data loaded from stable storage. Deferred evaluation is also central to our model; by incorporating deferred evaluation into our design only at the point of initiating network communication, the function passing model remains easy to reason about while remaining efficient in time and memory. We formalize our programming model using small-step operational semantics, and we provide an open-source implementation of our model in and for the Scala programming language, along with a case study of several example frameworks and end-user programs written atop of this model.

Extracting Code from Programming Tutorial Videos
Shir Yadid and Eran Yahav
(Technion, Israel)
The number of programming tutorial videos on the web increases daily. Video hosting sites such as YouTube host millions of video lectures, with many programming tutorials for various languages and platforms. These videos contain a wealth of valuable information, including code that may be of interest. However, two main challenges have so far prevented the effective indexing of programming tutorial videos: (i) code in tutorials is typically written on-the-fly, with only parts of the code visible in each frame, and (ii) optical character recognition (OCR) is not precise enough to produce quality results from videos. We present a novel approach for extracting code from videos that is based on: (i) consolidating code across frames, and (ii) statistical language models for applying corrections at different levels, allowing us to make corrections by choosing the most likely token, combination of tokens that form a likely line structure, and combination of lines that lead to a likely code fragment in a particular language. We implemented our approach in a tool called ACE, and used it to extract code from 40 Android video tutorials on YouTube. Our evaluation shows that ACE extracts code with high accuracy, enabling deep indexing of video tutorials.

Papers III

Object Spreadsheets: A New Computational Model for End-User Development of Data-Centric Web Applications
Matt McCutchen, Shachar Itzhaky, and Daniel Jackson
(Massachusetts Institute of Technology, USA)
Spreadsheets offer many advantages as the computational and data-storage engine for applications that are authored by end users. Paradoxically, however, their main failing in this regard is their computational model. Despite being used in almost all cases to represent data that is essentially relational (with some hierarchical structuring), the spreadsheet model treats the two-dimensional grid as largely unstructured, with formulas linking cells in an ad hoc way.
This paper reports on a quest to rethink the spreadsheet model. The model we propose supports not only conventional flat tables, but also nested variable-size lists and object references. It includes a formula language suited to the data model and procedures to specify updates.
The model has been implemented in a tool called Object Spreadsheets, which is intended for the development of data-centric web applications. We describe several example applications we built using the tool to demonstrate its applicability.

Info

Moldable, Context-Aware Searching with Spotter
Andrei Chiş, Tudor Gîrba, Juraj Kubelka, Oscar Nierstrasz, Stefan Reichhart, and Aliaksei Syrel
(University of Bern, Switzerland; feenk.com, Switzerland; University of Chile, Chile)
Software systems involve many different kinds of domain-specific and interrelated software entities. A common strategy employed by developers to deal with this reality is to perform exploratory investigations by means of searching. Nevertheless, most integrated development environments (IDEs) support searching through generic and disconnected search tools. This impedes search tasks over domain-specific entities, as considerable effort is wasted by developers locating and linking data and concepts relevant to their application domains.
To tackle this problem we propose Spotter, a moldable framework for supporting contextual-aware searching in IDEs by enabling developers to easily create custom searches for domain objects. In this paper we motivate a set of requirements for Spotter and show, through usage scenarios, that Spotter improves program comprehension by reducing the effort required to find and search through concepts from a wide range of domains. Furthermore, we show that by taking code into account, Spotter can provide a single entry point for embedding search support within an IDE.

Info

Papers IV

Exploring the Role of Sequential Computation in Distributed Systems: Motivating a Programming Paradigm Shift
Ivan Kuraj and Daniel Jackson
(Massachusetts Institute of Technology, USA)
Despite many advances in programming models and frameworks, writing distributed applications remains hard. Even when the underlying logic is inherently sequential and simple, addressing distributed aspects results in complex cross-cutting code that undermines such simplicity.
This paper analyzes different programming models to motivate a new paradigm that leverages the sequential computation model, while gaining the expressiveness for distribution. The paper argues for an adoption of the paradigm shift by exhibiting a programming model that allows easier reasoning about the conceptual aspects of distributed systems' behavior. The newly proposed programming model provides a clean separation of concerns and retains the simplicity of sequential computation, using it as a basis onto which distributed aspects are added without corrupting the essential sequential structure, while offloading much of the complexity of implementing distributed concerns to the compiler. We demonstrate the feasibility of this model on a case study, identifying key improvements over existing approaches.

Gramada: Immediacy in Programming Language Development
Patrick Rein, Robert Hirschfeld, and Marcel Taeumel
(HPI, Germany; SAP Labs, USA; Viewpoints Research Institute, USA)
Domain-specific languages (DSLs) improve software maintainability and programmer productivity by making domain concepts more explicit in the code. However, developing syntax and semantics of DSLs is often challenging and as a result developers seldom take advantage of the benefits of DSLs. One way to lower the entry barrier to DSL development is to give developers immediate and continuous feedback on modifications to a language. We propose Gramada, an environment for developing DSLs in Squeak/Smalltalk which is designed to provide such a live programming experience. It is based on a language development framework with additional support for incremental compilation to improve system response times and a set of tools which creates a steady frame and allows programmers to quickly explore changes to the syntax of a language. Our benchmarks and discussion illustrate how Gramada can give visual feedback on most changes to the language in a way that supports live programming. We conclude that Gramada’s feedback is fast and consistent enough to make exploring the effects of changes a lively and productive activity during the interactive development of DSLs.

Video

Helping Johnny Encrypt: Toward Semantic Interfaces for Cryptographic Frameworks
Soumya Indela, Mukul Kulkarni, Kartik Nayak, and Tudor Dumitraş
(University of Maryland at College Park, USA)
Several mature cryptographic frameworks are available, and they have been utilized for building complex applications. However, developers often use these frameworks incorrectly and introduce security vulnerabilities. This is because current cryptographic frameworks erode abstraction boundaries, as they do not encapsulate all the framework-specific knowledge and expect developers to understand security attacks and defenses. Starting from the documented misuse cases of cryptographic APIs, we infer five developer needs and we show that a good API design would address these needs only partially. Building on this observation, we propose APIs that are semantically meaningful for developers, we show how these interfaces can be implemented consistently on top of existing frameworks using novel and known design patterns, and we propose build management hooks for isolating security workarounds needed during the development and test phases. Through two case studies, we show that our APIs can be utilized to implement non-trivial client-server protocols and that they provide a better separation of concerns than existing frameworks. We also discuss the challenges and potential approaches for evaluating our solution. Our semantic interfaces represent a first step toward preventing misuses of cryptographic APIs.

Leveraging a Corpus of Natural Language Descriptions for Program Similarity
Meital Zilberstein and Eran Yahav
(Technion, Israel)
Program similarity is a central challenge in many programming-related applications, such as code search, clone detection, automatic translation, and programming education.
We present a novel approach for establishing the similarity of code fragments by: (i) obtaining textual descriptions of code fragments captured in millions of posts on question-answering sites, blogs and other sources, and (ii) using natural language processing techniques to establish similarity between textual descriptions, and thus between their corresponding code fragments.
To improve precision, we use a simple static analysis that extracts type signatures, and combine the results of textual similarity with similarity of the signatures. Because our notion of code similarity is based on similarity of textual descriptions, our approach can determine semantic relatedness and similarity of code across different libraries and even across different programming languages, a task considered extremely difficult using traditional approaches. To evaluate our approach, we use data obtained from the popular question-answering site, Stackoverflow. To obtain a ground-truth to compare against, we developed a crowdsourcing system, Like2Drops, that allows users to label the similarity of code fragments. We used the system to collect similarity classifications for a massive corpus of 6,500 program pairs. Our results show that our technique is effective in determining similarity, and achieves more than 85 percent precision, recall and accuracy.

ONWARD Essays

Essays I

How Are Programs Found? Speculating about Language Ergonomics with Curry-Howard
Johannes Emerich
Functional languages with strong static type systems have beneficial properties to help ensure program correctness and reliability. Surprisingly, their practical significance in applications is low relative to other languages lacking in those dimensions. In this paper, the programs-as-proofs analogy is taken seriously to gain speculative insights by analysis of creation habits in the proof-centric discipline of mathematics. Viewed in light of this analogy, a sampling of mathematicians’ attitudes towards formal proof suggests that the crucial role of intuition and experimentation in programming tasks may be under appreciated, hinting at a possible explanation of the challenges rigorously disciplined languages face in practical applications.

The Left Hand of Equals
James Noble, Andrew P. Black, Kim B. Bruce, Michael Homer, and Mark S. Miller
(Victoria University of Wellington, New Zealand; Portland State University, USA; Pomona College, USA; Google, USA)
When is one object equal to another object? While object identity is fundamental to object-oriented systems, object equality, although tightly intertwined with identity, is harder to pin down. The distinction between identity and equality is reflected in object-oriented languages, almost all of which provide two variants of “equality”, while some provide many more. Programmers can usually override at least one of these forms of equality, and can always define their own methods to distinguish their own objects.
This essay takes a reflexive journey through fifty years of identity and equality in object-oriented languages, and ends somewhere we did not expect: a “left-handed” equality relying on trust and grace.

Essays II

A World of Active Objects for Work and Play: The First Ten Years of Lively
Daniel Ingalls, Tim Felgentreff, Robert Hirschfeld, Robert Krahn, Jens Lincke, Marko Röder, Antero Taivalsaari, and Tommi Mikkonen
(Y Combinator Research, USA; HPI, Germany; Nokia, Finland; Tampere University of Technology, Finland)
The Lively Kernel and the Lively Web represent a continuing effort to realize a creative computing environment in the context of the World Wide Web. We refer to that evolving system simply as "Lively". Lively is a live object computing environment implemented using JavaScript and other techniques available inside the browser. When first built in 2006, it was a grand accomplishment to have created such a system that would run in any web browser. Since that time we have learned a lot about the goals we had, the challenges and opportunities that come with life in the browser, and the exciting possibilities that still lie ahead.