title: Forge: generating a high performance DSL implementation from a declarative specification

authors:
Arvind K. Sujeeth
Austin Gibbons
Kevin J. Brown
HyoukJoong Lee
Tiark Rompf
Martin Odersky
Kunle Olukotun

abstract: Domain-specific languages provide a promising path to automatically compile high-level code to parallel, heterogeneous, and distributed hardware. However, in practice high performance DSLs still require considerable software expertise to develop and force users into tool-chains that hinder prototyping and debugging. To address these problems, we present Forge, a new meta DSL for declaratively specifying high performance embedded DSLs. Forge provides DSL authors with high-level abstractions (e.g., data structures, parallel patterns, effects) for specifying their DSL in a way that permits high performance. From this high-level specification, Forge automatically generates both a naïve Scala library implementation of the DSL and a high performance version using the Delite DSL framework. Users of a Forge-generated DSL can prototype their application using the library version, and then switch to the Delite version to run on multicore CPUs, GPUs, and clusters without changing the application code. Forge-generated Delite DSLs perform within 2x of hand-optimized C++ and up to 40x better than Spark, an alternative high-level distributed programming environment. Compared to a manually implemented Delite DSL, Forge provides a factor of 3-6x reduction in lines of code and does not sacrifice any performance. Furthermore, Forge specifications can be generated from existing Scala libraries, are easy to maintain, shield DSL developers from changes in the Delite framework, and enable DSLs to be retargeted to other frameworks transparently.


venue: gpce

title: Compiling a reflective language using MetaOCaml

abstract: A reflective language makes the language semantics open to user programs and allows them to access, extend, and modify it from within the same language framework. Because of its high flexibility and expressiveness, it can be an ideal platform for programming language research as well as practical applications in dynamic environments. However, efficient implementation of a reflective language is extremely difficult. Under the circumstance where the language semantics can change, a partial evaluator is required for compilation. This paper reports on the experience of using MetaOCaml as a compiler for a reflective language. With staging annotations, MetaOCaml achieves the same effect as using a partial evaluator. Unlike the standard partial evaluator, the run mechanism of MetaOCaml enables us to use the specialized (compiled) code in the current runtime environment. On the other hand, the lack of a binding-time analysis in MetaOCaml prohibits us from compiling a user program under modified compiled semantics.


title: Specialization through dynamic staging

authors:
Piotr Danilewski
Marcel Köster
Roland Leißa
Richard Membarth
Philipp Slusallek

abstract: Partial evaluation allows for specialization of program fragments. This can be realized by staging, where one fragment is executed earlier than its surrounding code. However, taking advantage of these capabilities is often a cumbersome endeavor. In this paper, we present a new metaprogramming concept using staging parameters that are first-class citizen entities and define the order of execution of the program. Staging parameters can be used to define MetaML-like quotations, but can also allow stages to be created and resolved dynamically. The programmer can write generic, polyvariant code which can be reused in the context of different stages. We demonstrate how our approach can be used to define and apply domain-specific optimizations. Our implementation of the proposed metaprogramming concept generates code which is on a par with templated C++ code in terms of execution time.


title: Extensible language implementation with object algebras (short paper)

authors:
Maria Gouseti
Chiel Peters
Tijs van der Storm

abstract: Object Algebras are a recently introduced design pattern to make the implementation of recursive data types more extensible. In this short paper we report our experience in using Object Algebras in building a realistic domain specific language (DSL) for questionnaires, called QL. This experience has led to a simple, yet powerful set of tools for the practical and flexible implementation of highly extensible languages.


title: Automatic locality-friendly interface extension of numerical functions

authors:
Benjamin Hess
Thomas R. Gross
Markus Püschel

abstract: Raising the level of abstraction is a key concern of software engineering, and libraries (either used directly or as a target of a program generation system) are a successful technique to raise programmer productivity and to improve software quality. Unfortunately successful libraries may contain functions that may not be general enough. For example, many numeric performance libraries contain functions that work on one- or higher-dimensional arrays. A problem arises if a program wants to invoke such a function on a non-contiguous subarray (e.g., in C the column of a matrix or a subarray of an image). If the library developer did not foresee this scenario, the client program must include explicit copy steps before and after the library function call, incurring a possibly high performance penalty. A better solution would be an enhanced library function that allows for the desired access pattern. Exposing the access pattern allows the compiler to optimize for the intended usage scenario(s). As we do not want the library developer to generate all interesting versions manually, we present a tool that takes a library function written in C and generates such a customized function for typical accesses. We describe the approach, discuss limitations, and report on the performance. As example access patterns we consider those most common in numerical applications: striding and block striding, general permutations, as well as scaling. We evaluate the tool on various library functions including filters, scans, reductions, sorting, FFTs, and linear algebra operations. The automatically generated custom version is in most cases significantly faster than using individual steps, offering speed-ups that are typically in the range of 1.2-1.8x.


title: Pin++: an object-oriented framework for writing pintools

authors:
James H. Hill
Dennis C. Feiock

abstract: This paper presents a framework named Pin++. Pin++ is an object-oriented framework that uses template metaprogramming to implement Pintools, which are analysis tools for the dynamic binary instrumentation tool named Pin. The goal of Pin++ is to simplify programming a Pintool and promote reuse of its components across different Pintools. Our results show that Pintools implemented using Pin++ can have a 54% reduction in complexity, increase its modularity, and up to 60% reduction in instrumentation overhead.


title: A domain-specific language for building self-optimizing AST interpreters

authors:
Christian Humer
Christian Wimmer
Christian Wirth
Andreas Wöß
Thomas Würthinger

abstract: Self-optimizing AST interpreters dynamically adapt to the provided input for faster execution. This adaptation includes initial tests of the input, changes to AST nodes, and insertion of guards that ensure assumptions still hold. Such specialization and speculation is essential for the performance of dynamic programming languages such as JavaScript. In traditional procedural and objectoriented programming languages it can be tedious to write selfoptimizing AST interpreters, as those languages fail to provide constructs that would specifically support that. This paper introduces a declarative domain-specific language (DSL) that greatly simplifies writing self-optimizing AST interpreters. The DSL supports specialization of operations based on types of the input and other properties. It can then use these specializations directly or chain them to represent the operation with the minimum amount of code possible. The DSL significantly reduces the complexity of expressing specializations for those interpreters. We use it in our high-performance implementation of JavaScript, where 274 language operations have an average of about 4 and a maximum of 190 specializations. In addition, the DSL is used in implementations of Ruby, Python, R, and Smalltalk.


title: Specializing planners for hierarchical multi-way dataflow constraint systems

authors:
Jaakko Järvi
Gabriel Foust
Magne Haveraaen

abstract: A constraint system consists of variables and a set of constraints on those variables. To solve a constraint system is to find a valuation that satisfies all constraints; or the "best" subset of constraints if not all can simultaneously be satisfied. In a multi-way dataflow constraint system, solving requires selecting a set of user-defined functions which, when executed, will enforce the constraints. The task of selecting these functions is called planning. The planner has two kinds of input: the specification of the constraints and an order of priority for those constraints. The former typically changes seldom, while the latter frequently, making constraint planning a potential application for program specialization. This paper shows how to generate specialized planners for hierarchical multi-way dataflow constraint systems when the constraints are known in advance. The specialized planners are DFAs; they can be an order of magnitude or more faster than a general purpose planner for the same system. Our applications for constraint systems are in user interface programming, where constraint systems determine how a GUI should react to user interaction---specialized planners can help to ensure that GUIs' responses to user interaction are instantaneous.


title: Yin-yang: concealing the deep embedding of DSLs

authors:
Vojin Jovanovic
Amir Shaikhha
Sandro Stucki
Vladimir Nikolaev
Christoph Koch
Martin Odersky

abstract: Deeply embedded domain-specific languages (EDSLs) intrinsically compromise programmer experience for improved program performance. Shallow EDSLs complement them by trading program performance for good programmer experience. We present Yin-Yang, a framework for DSL embedding that uses Scala macros to reliably translate shallow EDSL programs to the corresponding deep EDSL programs. The translation allows program prototyping and development in the user friendly shallow embedding, while the corresponding deep embedding is used where performance is important. The reliability of the translation completely conceals the deep em- bedding from the user. For the DSL author, Yin-Yang automatically generates the deep DSL embeddings from their shallow counterparts by reusing the core translation. This obviates the need for code duplication and leads to reliability by construction.


title: Optimization by runtime specialization for sparse matrix-vector multiplication

authors:
Sam Kamin
María Jesús Garzarán
Baris Aktemur
Danqing Xu
Buse Yilmaz
Zhongbo Chen

abstract: Runtime specialization optimizes programs based on partial information available only at run time. It is applicable when some input data is used repeatedly while other input data varies. This technique has the potential of generating highly efficient codes. In this paper, we explore the potential for obtaining speedups for sparse matrix-dense vector multiplication using runtime specialization, in the case where a single matrix is to be multiplied by many vectors. We experiment with five methods involving runtime specialization, comparing them to methods that do not (including Intel's MKL library). For this work, our focus is the evaluation of the speedups that can be obtained with runtime specialization without considering the overheads of the code generation. Our experiments use 23 matrices from the Matrix Market and Florida collections, and run on five different machines. In 94 of those 115 cases, the specialized code runs faster than any version without specialization. If we only use specialization, the average speedup with respect to Intel's MKL library ranges from 1.44x to 1.77x, depending on the machine. We have also found that the best method depends on the matrix and machine; no method is best for all matrices and machines.


title: Efficient testing of software product lines via centralization (short paper)

authors:
Lei Ma
Cyrille Artho
Cheng Zhang
Hiroyuki Sato

abstract: Software product line~(SPL) engineering manages families of software products that share common features. However, cost-effective test case generation for an SPL is challenging. Applying existing test case generation techniques to each product variant separately may test common code in a redundant way. Moreover, it is difficult to share the test results among multiple product variants. In this paper, we propose the use of centralization, which combines multiple product variants from the same SPL and generates test cases for the entire system. By taking into account all variants, our technique generally avoids generating redundant test cases for common software components. Our case study on three SPLs shows that compared with testing each variant independently, our technique is more efficient and achieves higher test coverage.


title: Emergent gummy modules: modular representation of emergent behavior

authors:
Somayeh Malakuti
Mehmet Aksit

abstract: Emergent behavior is generally defined as the appearance of complex behavior out of multiplicity of relatively simple interactions. Nowadays, there are various kinds of software systems that deal with detecting the emergence of certain behavior in environment, representing it in the software and providing means to manipulate the behavior. Where significant amount of research has been dedicated to develop algorithms for detecting emergent behavior, there is no dedicated attempt to provide suitable linguistic abstractions to modularize emergent behavior and its related concerns. This results in implementations that are complex and hard to maintain. In this paper, we identify three characteristic features of emergent behavior, and outline the shortcomings of current languages to properly program and modularize emergent behavior. We introduce emergent gummy modules as dedicated linguistic abstractions, which facilitate defining the appearance and disappearance conditions of emergent behavior as well as its utilization operations as one holistic module. We explain the implementation of emergent gummy modules in the GummyJ language, and illustrate that they improve the modularity of implementations. We represent the event processing semantics of GummyJ programs in UPPAAL model checker and verify their correctness.


title: Automatic feature selection in large-scale system-software product lines

authors:
Andreas Ruprecht
Bernhard Heinloth
Daniel Lohmann

abstract: System software can typically be configured at compile time via a comfortable feature-based interface to tailor its functionality towards a specific use case. However, with the growing number of features, this tailoring process becomes increasingly difficult: As a prominent example, the Linux kernel in v3.14 provides nearly 14 000 configuration options to choose from. Even developers of embedded systems refrain from trying to build a minimized distinctive kernel configuration for their device – and thereby waste memory and money for unneeded functionality. In this paper, we present an approach for the automatic use-case specific tailoring of system software for special-purpose embedded systems. We evaluate the effectiveness of our approach on the example of Linux by generating tailored kernels for well-known applications of the Rasperry Pi and a Google Nexus 4 smartphone. Compared to the original configurations, our approach leads to memory savings of 15–70 percent and requires only very little manual intervention.


title: LibDSL: a library for developing embedded domain specific languages in d via template metaprogramming

authors:
Masato Shioda
Hideya Iwasaki
Shigeyuki Sato

abstract: This paper presents a library called LibDSL that helps the implementer of an embedded domain specific language (EDSL) effectively develop it in D language. The LibDSL library accepts as input some kinds of ``specifications'' of the EDSL that the implementer is going to develop and a D program within which an EDSL source program written by the user is embedded. It produces the front-end code of an LALR parser for the EDSL program and back-end code of the execution engine. LibDSL is able to produce two kinds of execution engines, namely compiler-based and interpreter-based engines, either of which the user can properly choose depending on whether an EDSL program is known at compile time or not. We have implemented the LibDSL system by using template metaprogramming and other advanced facilities such as compile-time function execution of D language. EDSL programs developed by means of LibDSL have a nice integrativeness with the host language.


title: A transformational approach to data visualization

authors:
Karl Smeltzer
Martin Erwig
Ronald A. Metoyer

abstract: Information visualization construction tools generally tend to fall in one of two disparate categories. Either they offer simple but inflexible visualization templates, or else they offer low-level graphical primitives which need to be assembled manually. Those that do offer flexible, domain-specific abstractions rarely focus on incrementally building and transforming visualizations, which could reduce limitations on the style of workflows supported. We present a Haskell-embedded DSL for data visualization that is designed to provide such abstractions and transformations. This DSL achieves additional expressiveness and flexibility through common functional programming idioms and the Haskell type class hierarchy.


title: Code specialization for memory efficient hash tries (short paper)

authors:
Michael J. Steindorfer
Jurgen J. Vinju

abstract: The hash trie data structure is a common part in standard collection libraries of JVM programming languages such as Clojure and Scala. It enables fast immutable implementations of maps, sets, and vectors, but it requires considerably more memory than an equivalent array-based data structure. This hinders the scalability of functional programs and the further adoption of this otherwise attractive style of programming. In this paper we present a product family of hash tries. We generate Java source code to specialize them using knowledge of JVM object memory layout. The number of possible specializations is exponential. The optimization challenge is thus to find a minimal set of variants which lead to a maximal loss in memory footprint on any given data. Using a set of experiments we measured the distribution of internal tree node sizes in hash tries. We used the results as a guidance to decide which variants of the family to generate and which variants should be left to the generic implementation. A preliminary validating experiment on the implementation of sets and maps shows that this technique leads to a median decrease of 55% in memory footprint for maps (and 78% for sets), while still maintaining comparable performance. Our combination of data analysis and code specialization proved to be effective.


title: Projectional editing of variational software

authors:
Eric Walkingshaw
Klaus Ostermann

abstract: Editing the source code of variational software is complicated by the presence of variation annotations, such as #ifdef statements, and by code that is only included in some configurations. When editing some configurations and not others, it would be easier to edit a simplified version of the source code that includes only the configurations we currently care about. In this paper, we present a projectional editing model for variational software. Using our approach, a programmer can partially configure a variational program, edit this simplified view of the code, and then automatically update the original, fully variational source code. The model is based on an isolation principle where edits affect only the variants that are visible in the view. We show that this principle has several nice properties that are suggested by related work on bidirectional transformations.


title: Towards tool support for spreadsheet-based domain-specific languages

authors:
Sorin Adam
Ulrik Pagh Schultz

abstract: Spreadsheets are commonly used by non-programmers to store data in a structured form, this data can in some cases be considered to be a program in a domain-specific language (DSL). Unlike ordinary text-based domain-specific languages, there is however currently no formalism for expressing the syntax of such spreadsheet-based DSLs (SDSLs), and there is no tool support for automatically generating language infrastructure such as parsers and IDE support. In this paper we define a simple notion of two-dimensional grammars for SDSLs, and show how such grammars can be used for automatically generating parsers that extract structured data from a spreadsheet in the form of an AST. We demonstrate automatic generation of parsers for a number of examples, including the questionnaire DSL from LWC2014 and a DSL for writing safety specifications.


title: Migrating large object-oriented Applications into component-based ones: instantiation and inheritance transformation

authors:
Zakarea Alshara
Abdelhak-Djamel Seriai
Chouki Tibermacine
Hinde-Lilia Bouziane
Christophe Dony
Anas Shatnawi

abstract: Large object-oriented applications have complex and numerous dependencies, and usually do not have explicit software architectures. Therefore they are hard to maintain, and parts of them are difficult to reuse. Component-based development paradigm emerged for improving these aspects and for supporting effective maintainability and reuse. It provides better understandability through a high-level architecture view of the application. Thereby migrating object-oriented applications to component-based ones will contribute to improve these characteristics (maintainability and reuse). In this paper, we propose an approach to automatically transform object-oriented applications to component-based ones. More particularly, the input of the approach is the result provided by software architecture recovery: a component-based architecture description. Then, our approach transforms the object-oriented source code in order to produce deployable components. We focus in this paper on the transformation of source code related to instantiation and inheritance dependencies between classes that are in different components. We experimented the proposed solution in the transformation of a collection of Java applications into the OSGi framework. The experimental results are discussed in this paper.


title: Native-2-native: automated cross-platform code synthesis from web-based programming resources

authors:
Antuan Byalik
Sanchit Chadha
Eli Tilevich

abstract: For maximal market penetration, popular mobile applications are typically supported on all major platforms, including Android and iOS. Despite the vast differences in the look-and-feel of major mobile platforms, applications running on these platforms in essence provide the same core functionality. As an application is maintained and evolved, the resulting changes must be replicated on all the supported platforms, a tedious and error-prone programming process. Existing automated source-to-source translation tools prove inadequate due to the structural and idiomatic differences in how functionalities are expressed across major platforms. In this paper, we present a new approach---Native-2-Native---that automatically synthesizes code for a mobile application to make use of native resources on one platform, based on the equivalent program transformations performed on another platform. First, the programmer modifies a mobile application's Android version to make use of some native resource, with a plugin capturing code changes. Based on the changes, the system then parameterizes a web search query over popular programming resources (e.g., Google Code, StackOverflow, etc.), to discover equivalent iOS code blocks with the closest similarity to the programmer-written Android code. The discovered iOS code block is then presented to the programmer as an automatically synthesized Swift source file to further fine-tune and subsequently integrate in the mobile application's iOS version. Our evaluation, enhancing mobile applications to make use of common native resources, shows that the presented approach can correctly synthesize more than 86% of Swift code for the subject applications' iOS versions.


title: Analysing the Kconfig semantics and its analysis tools

authors:
Sascha El-Sharkawy
Adam Krafczyk
Klaus Schmid

abstract: The Linux kernel is often used as a real world case study to demonstrate novel Software Product Line Engineering research methods. An important point in this is often the analysis of the Kconfig semantics. However, we detected that the semantics of Kconfig is rather unclear and has many special cases, which are not documented in its short specification. We performed a systematic analysis to uncover the correct behaviour of Kconfig and present the results, which are necessary for applying semantically correct analyses. Further, we analyse existing analysis tools of the research community whether they are aware of the correct semantics of Kconfig. These analyses can be used for improving existing analysis tools as well as decision support for selecting an appropriate tool for a specific analysis. In summary we contribute to a better understanding of Kconfig in the research community to improve the validity of evaluations based on Linux.


title: POP-PL: a patient-oriented prescription programming language

authors:
Spencer P. Florence
Burke Fetscher
Matthew Flatt
William H. Temps
Tina Kiguradze
Dennis P. West
Charlotte Niznik
Paul R. Yarnold
Robert Bruce Findler
Steven M. Belknap

abstract: Medical professionals have long used algorithmic thinking to describe and implement health care processes without the benefit of the conceptual framework provided by a programming language. Instead, medical algorithms are expressed using English, flowcharts, or data tables. This results in prescriptions that are difficult to understand, hard to debug, and awkward to reuse. This paper reports on the design and evaluation of a domain-specific programming language, POP-PL for expressing medical algorithms. The design draws on the experience of researchers in two disciplines, programming languages and medicine. The language is based around the idea that programs and humans have complementary strengths, that when combined can make for safer, more accurate performance of prescriptions. We implemented a prototype of our language and evaluated its design by writing prescriptions in the new language and administering a usability survey to medical professionals. This formative evaluation suggests that medical prescriptions can be conveyed by a programming language's mode of expression and provides useful information for refining the language. Analysis of the survey results suggests that medical professionals can understand and correctly modify programs in POP-PL.


title: Addressing metamodel revisions in model-based software product lines

authors:
Jaime Font
Lorena Arcega
Øystein Haugen
Carlos Cetina

abstract: Metamodels evolve over time, which can break the conformance between the models and the metamodel. Model migration strategies aim to co-evolve models and metamodels together, but their application is not fully automatizable and is thus cumbersome and error prone. We introduce the Variable MetaModel (VMM) strategy to address the evolution of the reusable model assets of a model-based Software Product Line. The VMM strategy applies variability modeling ideas to express the evolution of the metamodel in terms of commonalities and variabilities. When the metamodel evolves, the models continue to conform to the VMM, avoiding the need for migration. We have applied both the traditional migration strategy and the VMM strategy to a retrospective case study that includes 13 years of evolution of our industrial partner, an induction hobs manufacturer. The comparison between the two strategies shows better results for the VMM strategy in terms of model indirection, automation, and trust leak.


title: Generating reactive programs for graphical user interfaces from multi-way dataflow constraint systems

authors:
Gabriel Foust
Jaakko Järvi
Sean Parent

abstract: For a GUI to remain responsive, it must be able to schedule lengthy tasks to be executed asynchronously. In the traditional approach to GUI implementation--writing functions to handle individual user events--asynchronous programming easily leads to defects. Ensuring that all data dependencies are respected is difficult when new events arrive while prior events are still being handled. Reactive programming techniques, gaining popularity in GUI programming, help since they make data dependencies explicit and enforce them automatically as variables' values change. However, data dependencies in GUIs usually change along with its state. Reactive programming must therefore describe a GUI as a collection of many reactive programs, whose interaction the programmer must explicitly coordinate. This paper presents a declarative approach for GUI programming that relieves the programmer from coordinating asynchronous computations. The approach is based on our prior work on "property models", where GUI state is maintained by a dataflow constraint system. A property model responds to user events by atomically constructing new data dependencies and scheduling asynchronous computations to enforce those dependencies. In essence, a property model dynamically generates a reactive program, adding to it as new events occur. The approach gives the following guarantee: the same sequence of events produces the same results, regardless of the timing of those events.


title: Modular interpreters for the masses: implicit context propagation using object algebras

authors:
Pablo Inostroza
Tijs van der Storm

abstract: Modular interpreters have the potential to achieve component-based language development: instead of writing language interpreters from scratch, they can be assembled from reusable, semantic building blocks. Unfortunately, traditional language interpreters are hard to extend because different language constructs may require different interpreter signatures. For instance, arithmetic interpreters produce a value without any context information, whereas binding constructs require an additional environment. In this paper, we present a practical solution to this problem based on implicit context propagation. By structuring denotational-style interpreters as Object Algebras, base interpreters can be retroactively lifted into new interpreters that have an extended signature. The additional parameters are implicitly propagated behind the scenes, through the evaluation of the base interpreter. Interpreter lifting enables a flexible style of component-based language development. The technique works in mainstream object-oriented languages, does not sacrifice type safety or separate compilation, and can be easily automated. We illustrate implicit context propagation using a modular definition of Featherweight Java and its extension to support side-effects.


title: Orchestrating masses of sensors: a design-driven development Approach

authors:
Milan Kabác
Charles Consel

abstract: This paper proposes a design-driven development approach that is dedicated to the domain of orchestration of masses of sensors. The developer declares what an application does using a domain-specific language (DSL). Our compiler processes domain-specific declarations to generate a customized programming framework that guides and supports the programming phase.


title: Contract-based general-purpose GPU programming

authors:
Alexey Kolesnichenko
Christopher M. Poskitt
Sebastian Nanz
Bertrand Meyer

abstract: Using GPUs as general-purpose processors has revolutionized parallel computing by offering, for a large and growing set of algorithms, massive data-parallelization on desktop machines. An obstacle to widespread adoption, however, is the difficulty of programming them and the low-level control of the hardware required to achieve good performance. This paper suggests a programming library, SafeGPU, that aims at striking a balance between programmer productivity and performance, by making GPU data-parallel operations accessible from within a classical object-oriented programming language. The solution is integrated with the design-by-contract approach, which increases confidence in functional program correctness by embedding executable program specifications into the program text. We show that our library leads to modular and maintainable code that is accessible to GPGPU non-experts, while providing performance that is comparable with hand-written CUDA code. Furthermore, runtime contract checking turns out to be feasible, as the contracts can be executed on the GPU.


title: Shallow embedding of DSLs via online partial evaluation

authors:
Roland Leißa
Klaas Boesche
Sebastian Hack
Richard Membarth
Philipp Slusallek

abstract: This paper investigates shallow embedding of DSLs by means of online partial evaluation. To this end, we present a novel online partial evaluator for continuation-passing style languages. We argue that it has, in contrast to prior work, a predictable termination policy that works well in practice. We present our approach formally using a continuation-passing variant of PCF and prove its termination properties. We evaluate our technique experimentally in the field of visual and high-performance computing and show that our evaluator produces highly specialized and efficient code for CPUs as well as GPUs that matches the performance of hand-tuned expert code.


title: Safer SDN programming through Arbiter

authors:
Michael Lopez
C. Jasson Casey
Gabriel Dos Reis
Colton Chojnacki

abstract: Software Defined Networking (SDN) programs are written with respect to assumptions on software and hardware facilities and protocol definitions. Silent mismatches between the expected feature set and implemented feature set of SDN artifacts can easily lead to hard to debug network configurations, decreased network performance, outages, or worse, security vulnerabilities. We show how the paradigm of axiomatic programming, supported by practical dependent types, provides effective support for SDN executable specifications and verification.


title: CLOP: a multi-stage compiler to seamlessly embed heterogeneous code

authors:
Dmitri Makarov
Matthias Hauswirth

abstract: Heterogeneous programming complicates software development. We present CLOP, a platform that embeds code targeting heterogeneous compute devices in a convenient and clean way, allowing unobstructed data flow between the host code and the devices, reducing the amount of source code by an order of magnitude. The CLOP compiler uses the standard facilities of the D programming language to generate code strictly at compile-time. In this paper we describe the CLOP language and the CLOP compiler implementation.


title: An empirical study on configuration-related issues: investigating undeclared and unused identifiers

authors:
Flávio Medeiros
Iran Rodrigues
Márcio Ribeiro
Leopoldo Teixeira
Rohit Gheyi

abstract: The variability of configurable systems may lead to configuration-related issues (i.e., faults and warnings) that appear only when we select certain configuration options. Previous studies found that issues related to configurability are harder to detect than issues that appear in all configurations, because variability increases the complexity. However, little effort has been put into understanding configuration-related faults (e.g., undeclared functions and variables) and warnings (e.g., unused functions and variables). To better understand the peculiarities of configuration-related undeclared/unused variables and functions, in this paper we perform an empirical study of 15 systems to answer research questions related to how developers introduce these issues, the number of configuration options involved, and the time that these issues remain in source files. To make the analysis of several projects feasible, we propose a strategy that minimizes the initial setup problems of variability-aware tools. We detect and confirm 2 undeclared variables, 14 undeclared functions, 16 unused variables, and 7 unused functions related to configurability. We submit 30 patches to fix issues not fixed by developers. Our findings support the effectiveness of sampling (i.e., analysis of only a subset of valid configurations) because most issues involve two or less configuration options. Nevertheless, by analyzing the version history of the projects, we observe that a number of issues remain in the code for several years. Furthermore, the corpus of undeclared/unused variables and functions gathered is a valuable source to study these issues, compare sampling algorithms, and test and improve variability-aware tools.


title: The next-generation in-stadium experience (keynote)

authors:
Priya Narasimhan
Utsav Drolia
Jiaqi Tan
Nathan D. Mickulicz
Rajeev Gandhi

abstract: YinzCam is a cloud-hosted service that provides sports fans with real-time scores, news, photos, statistics, live radio, streaming video, etc., on their mobile devices. YinzCam’s infrastructure is currently hosted on Amazon Web Services (AWS) and supports over 30 million installs of the official mobile apps of 140+ NHL/NFL/NBA/NRL/NCAA sports teams and venues. YinzCam’s workload is necessarily multi-modal (e.g., pre-game, in-game, post-game, game-day, non-gameday), with normal game-time traffic being twenty-fold of that on non-game days. This paper describes the evolution of YinzCam’s production architecture and distributed infrastructure, from its beginnings in 2009, when it was used to support thousands of concurrent users, to today’s system that supports millions of concurrent users on any game day. We also discuss key new opportunities to improve the fan experience inside the stadium of the future, without impacting the available bandwidth, by crowd-sourcing the thousands of mobile devices that are in fans’ hands inside these venues. We present Krowd, a novel distributed key-value store for promoting efficient content sharing, discovery and retrieval across the mobile devices inside a stadium. We present CHIPS, a system that ensures that users’ privacy is maintained while their devices participate in the crowdsourced infrastructure.


title: Model querying with query models

authors:
Carlos Noguera
Viviane Jonckers

abstract: Model querying is an integral part of Model-Driven Engineering. Developers query models when specifying model transformations, when defining model constraints, or simply when they need to extract some information from the model. Model queries are often specified in a general-purpose programming language, with developers just navigating models through their programming interfaces. OCL is the best known model query language, and while successful, it is difficult to express complex structural properties featured in target model elements. In this paper we describe a model query facility that aims at easing the description of structural features in a query. In our approach, developers model their queries by reusing fragments of the target model to specify the invariant parts of the template, augmented with variables and special relations to specify what can vary. The query itself conforms to a meta-model that extends the meta-model under-query. By reusing the queried meta- model developers can reduce the mental overhead that comes from using a different language to specify the queries. We have developed a proof of concept tool for the Eclipse Modeling Framework (EMF) that (1) generates a query meta-model from a target meta- model, (2) allows the construction of queries using a graphical, graph-based editor and (3) executes the queries by translating them to a set of logic predicates that are then evaluated using an extension of the logic-based query language Ekeko.


title: Generating safe boundary APIs between typed EDSLs and their environments

authors:
Bob Reynders
Dominique Devriese
Frank Piessens

abstract: Embedded domain specific languages (EDSLs) are used to represent special-purpose code in a general-purpose language and they are used for applications like vector calculations and run-time code generation. Often, code in an EDSL is compiled to a target (e.g. GPU languages, JVM bytecode, assembly, JavaScript) and needs to interface with other code that is available at that level but uses other data representations or calling conventions. We present an approach for safely making available such APIs in a typed EDSL, guaranteeing correct conversions between data representations and the respect for calling conventions. When the code being interfaced with is the result of static compilation of host language code, we propose a way to auto-generate the needed boilerplate using meta-programming. We instantiate our technique with JavaScript as the target language, JS-Scala as the EDSL, Scala.js as the static compiler and Scala macros to generate the boilerplate, but our design is more generally applicable. We provide evidence of usefulness of our approach through a prototype implementation that we have applied in a non-trivial code base.


title: Composing code generators for C&C ADLs with Application-specific behavior languages (tool demonstration)

authors:
Jan Oliver Ringert
Bernhard Rumpe
Andreas Wortmann

abstract: Modeling software systems as component & connector architectures with application-specific behavior modeling languages enables domain experts to describe each component behavior with the most appropriate language. Generating executable systems for such language aggregates requires composing appropriate code generators for the participating languages. Previous work on code generator composition either focuses on white-box integration based on code generator internals or requires extensive handcrafting of integration code. We demonstrate an approach to black-box generator composition for architecture description languages that relies on explicit interfaces and exploits the encapsulation of components. This approach is implemented for the architecture modeling framework MontiArcAutomaton and has been evaluated in various contexts. Ultimately, black-box code generator composition facilitates development of code generators for architecture description languages with embedded behavior languages and increases code generator reuse.


title: Almost first-class language embedding: taming staged embedded DSLs

authors:
Maximilian Scherr
Shigeru Chiba

abstract: Embedded domain-specific languages (EDSLs), inheriting a general-purpose language's features as well as look-and-feel, have traditionally been second-class or rather non-citizens in terms of host-language design. This makes sense when one regards them to be on the same level as traditional, non-EDSL library interfaces. However, this equivalence only applies to the simplest of EDSLs. In this paper we illustrate why this is detrimental when moving on to EDSLs that employ staging, i.e. program reification, by example of various issues that affect authors and users alike. We believe that if EDSLs are to be considered a reliable, language-like interface abstraction, they require exceptional attention and design scrutiny. Instead of unenforceable conventions, we advocate the acceptance of EDSLs as proper, i.e. almost first-class, citizens while retaining most advantages of pure embeddings. As a small step towards this goal, we present a pragmatic framework prototype for Java. It is based on annotations that explicate and document membership to explicit EDSL entities. In a nutshell, our framework identifies (annotated) method calls and field accesses as EDSL terms and dynamically constructs an abstract-syntax representation, which is eventually passed to a semantics-defining back end implemented by the EDSL author.


title: Generative software product line development using variability-aware design patterns

authors:
Christoph Seidl
Sven Schuster
Ina Schaefer

abstract: Software Product Lines (SPLs) are an approach to reuse in-the-large that models a set of closely related software systems in terms of commonalities and variabilities. Design patterns are best practices for addressing recurring design problems in object-oriented source code. In the practice of implementing an SPL, instances of certain design patterns are employed to handle variability, which makes these "variability-aware design patterns" a best practice for SPL design. However, there currently is no dedicated method for proactively developing SPL using design patterns suitable for realizing variable functionality. In this paper, we present a method to perform generative SPL development with design patterns. We use role models to capture design patterns and their relation to a variability model. We further allow mapping of individual design pattern roles to elements of realization artifacts to be generated (e.g., classes, methods) and check the conformance of the realization with the specification of the pattern. With this method, we support proactive development of SPL using design patterns to apply best practices for the realization of variability. We present an implementation of our approach within the Eclipse IDE and demonstrate it within a case study.


title: Lightweight, generative variant exploration for high-performance graphics Applications

authors:
Kai Selgrad
Alexander Lier
Franz Köferl
Marc Stamminger
Daniel Lohmann

abstract: Rendering performance is an everlasting goal of computer graphics and significant driver for advances in both, hardware architecture and algorithms. Thereby, it has become possible to apply advanced computer graphics technology even in low-cost embedded appliances, such as car instruments. Yet, to come up with an efficient implementation, developers have to put enormous efforts into hardware/problem-specific tailoring, fine-tuning, and domain exploration, which requires profound expert knowledge. If a good solution has been found, there is a high probability that it does not work as well with other architectures or even the next hardware generation. Generative DSL-based approaches could mitigate these efforts and provide for an efficient exploration of algorithmic variants and hardware-specific tuning ideas. However, in vertically organized industries, such as automotive, suppliers are reluctant to introduce these techniques as they fear loss of control, high introduction costs, and additional constraints imposed by the OEM with respect to software and tool-chain certification. Moreover, suppliers do not want to share their generic solutions with the OEM, but only concrete instances. To this end, we propose a light-weight and incremental approach for meta programming of graphics applications. Our approach relies on an existing formulation of C-like languages that is amenable to meta programming, which we extend to become a lightweight language to combine algorithmic features. Our method provides a concise notation for meta programs and generates easily sharable output in the appropriate C-style target language.


title: Inverse macro in Scala

authors:
Hiroshi Yamaguchi
Shigeru Chiba

abstract: We propose a new variant of typed syntactic macro systems named inverse macro, which improves the expressiveness of macro systems. The inverse macro system enables to implement operators with complex side-effects, such as lazy operators and delimited continuation operators, which are beyond the power of existing macro systems. We have implemented the inverse macro system as an extension to Scala 2.11. We also show the expressiveness of the inverse macro system by comparing two versions of shift/reset, bundled in Scala 2.11 and implemented with the inverse macro system.


title: Automatic code generation in practice: experiences with embedded robot controllers

authors:
Sorin Adam
Marco Kuhrmann
Ulrik Pagh Schultz

abstract: Mobile robots often use a distributed architecture in which software components are deployed to heterogeneous hardware modules. Ensuring the consistency with the designed architecture is a complex task, notably if functional safety requirements have to be fulfilled. We propose to use a domain-specific language to specify those requirements and to allow for generating a safety-enforcing layer of code, which is deployed to the robot. The paper at hand reports experiences in practically applying code generation to mobile robots. For two cases, we discuss how we addressed challenges, e.g., regarding weaving code generation into proprietary development environments and testing of manually written code. We find that a DSL based on the same conceptual model can be used across different kinds of hardware modules, but a significant adaptation effort is required in practical scenarios involving different kinds of hardware.


title: IncLing: efficient product-line testing using incremental pairwise sampling

authors:
Mustafa Al-Hajjaji
Sebastian Krieter
Thomas Thüm
Malte Lochau
Gunter Saake

abstract: A software product line comprises a family of software products that share a common set of features. It enables customers to compose software systems from a managed set of features. Testing every product of a product line individually is often infeasible due to the exponential number of possible products in the number of features. Several approaches have been proposed to restrict the number of products to be tested by sampling a subset of products achieving sufficient combinatorial interaction coverage. However, existing sampling algorithms do not scale well to large product lines, as they require a considerable amount of time to generate the samples. Moreover, samples are not available until a sampling algorithm completely terminates. As testing time is usually limited, we propose an incremental approach of product sampling for pairwise interaction testing (called IncLing), which enables developers to generate samples on demand in a step-wise manner. Furthermore, IncLing uses heuristics to efficiently achieve pairwise interaction coverage with a reasonable number of products. We evaluated IncLing by comparing it against existing sampling algorithms using feature models of different sizes. The results of our approach indicate efficiency improvements for product-line testing.


title: Tool demo: testing configurable systems with FeatureIDE

authors:
Mustafa Al-Hajjaji
Jens Meinicke
Sebastian Krieter
Reimar Schröter
Thomas Thüm
Thomas Leich
Gunter Saake

abstract: Most software systems are designed to provide custom functionality using configuration options. Testing such systems is challenging as running tests of a single configuration is often not sufficient, because defects may appear in other configurations. Ideally, all configurations of a software system should be tested, which is usually not applicable in practice due to the combinatorial explosion with respect to the configuration options. Multiple sampling strategies aim to reduce the set of tested configurations to a feasible amount, such as T-wise sampling, random configurations, and user-defined configurations. However, these strategies are often not applied in practice as they require manual effort or a specialized testing framework. Within our tool FeatureIDE, we integrate all aforementioned strategies and reduce the manual effort by automating the process of generating and testing configurations. Furthermore, we provide support for unit testing to avoid redundant test executions and for variability-aware testing. With this extension of FeatureIDE, we aim to make recent testing techniques for configurable systems applicable in practice.


title: Recaf: Java dialects as libraries

authors:
Aggelos Biboudis
Pablo Inostroza
Tijs van der Storm

abstract: Mainstream programming languages like Java have limited support for language extensibility. Without mechanisms for syntactic abstraction, new programming styles can only be embedded in the form of libraries, limiting expressiveness. In this paper, we present Recaf, a lightweight tool for creating Java dialects; effectively extending Java with new language constructs and user defined semantics. The Recaf compiler generically transforms designated method bodies to code that is parameterized by a semantic factory (Object Algebra), defined in plain Java. The implementation of such a factory defines the desired runtime semantics. We applied our design to produce several examples from a diverse set of programming styles and two case studies: we define i) extensions for generators, asynchronous computations and asynchronous streams and ii) a Domain-Specific Language (DSL) for Parsing Expression Grammars (PEGs), in a few lines of code.


title: Automatic non-functional testing of code generators families

authors:
Mohamed Boussaa
Olivier Barais
Benoit Baudry
Gerson Sunyé

abstract: The intensive use of generative programming techniques provides an elegant engineering solution to deal with the heterogeneity of platforms and technological stacks. The use of domain-specific languages for example, leads to the creation of numerous code generators that automatically translate highlevel system specifications into multi-target executable code. Producing correct and efficient code generator is complex and error-prone. Although software designers provide generally high-level test suites to verify the functional outcome of generated code, it remains challenging and tedious to verify the behavior of produced code in terms of non-functional properties. This paper describes a practical approach based on a runtime monitoring infrastructure to automatically check the potential inefficient code generators. This infrastructure, based on system containers as execution platforms, allows code-generator developers to evaluate the generated code performance. We evaluate our approach by analyzing the performance of Haxe, a popular high-level programming language that involves a set of cross-platform code generators. Experimental results show that our approach is able to detect some performance inconsistencies that reveal real issues in Haxe code generators.


title: A change-centric approach to compile configurable systems with #ifdefs

authors:
Larissa Braz
Rohit Gheyi
Melina Mongiovi
Márcio Ribeiro
Flávio Medeiros
Leopoldo Teixeira

abstract: Configurable systems typically use #ifdefs to denote variability. Generating and compiling all configurations may be time-consuming. An alternative consists of using variability-aware parsers, such as TypeChef. However, they may not scale. In practice, compiling the complete systems may be costly. Therefore, developers can use sampling strategies to compile only a subset of the configurations. We propose a change-centric approach to compile configurable systems with #ifdefs by analyzing only configurations impacted by a code change (transformation). We implement it in a tool called CHECKCONFIGMX, which reports the new compilation errors introduced by the transformation. We perform an empirical study to evaluate 3,913 transformations applied to the 14 largest files of BusyBox, Apache HTTPD, and Expat configurable systems. CHECKCONFIGMX finds 595 compilation errors of 20 types introduced by 41 developers in 214 commits (5.46% of the analyzed transformations). In our study, it reduces by at least 50% (an average of 99%) the effort of evaluating the analyzed transformations by comparing with the exhaustive approach without considering a feature model. CHECKCONFIGMX may help developers to reduce compilation effort to evaluate fine-grained transformations applied to configurable systems with #ifdefs.


title: A vision for online verification-validation

authors:
Matthew A. Hammer
Bor-Yuh Evan Chang
David Van Horn

abstract: Today's programmers face a false choice between creating software that is extensible and software that is correct. Specifically, dynamic languages permit software that is richly extensible (via dynamic code loading, dynamic object extension, and various forms of reflection), and today's programmers exploit this flexibility to "bring their own language features" to enrich extensible languages (e.g., by using common JavaScript libraries). Meanwhile, such library-based language extensions generally lack enforcement of their abstractions, leading to programming errors that are complex to avoid and predict.


title: Delaying decisions in variable concern hierarchies

authors:
Jörg Kienzle
Gunter Mussbacher
Philippe Collet
Omar Alam

abstract: Concern-Oriented Reuse (CORE) proposes a new way of structuring model-driven software development, where models of the system are modularized by domains of abstraction within units of reuse called concerns. Within a CORE concern, models are further decomposed and modularized by features. This paper extends CORE with a technique that enables developers of high-level concerns to reuse lower-level concerns without unnecessarily committing to a specific feature selection. The developer can select the functionality that is minimally needed to continue development, and reexpose relevant alternative lower-level features of the reused concern in the reusing concern's interface. This effectively delays decision making about alternative functionality until the higher-level reuse context, where more detailed requirements are known and further decisions can be made. The paper describes the algorithms for composing the variation (i.e., feature and impact models), customization, and usage interfaces of a concern, as well as the concern's realization models and finally an entire concern hierarchy, as is necessary to support delayed decision making in CORE.


title: Bootstrapping domain-specific meta-languages in language workbenches

authors:
Gabriël Konat
Sebastian Erdweg
Eelco Visser

abstract: It is common practice to bootstrap compilers of programming languages. By using the compiled language to implement the compiler, compiler developers can code in their own high-level language and gain a large-scale test case. In this paper, we investigate bootstrapping of compiler-compilers as they occur in language workbenches. Language workbenches support the development of compilers through the application of multiple collaborating domain-specific meta-languages for defining a language's syntax, analysis, code generation, and editor support. We analyze the bootstrapping problem of language workbenches in detail, propose a method for sound bootstrapping based on fixpoint compilation, and show how to conduct breaking meta-language changes in a bootstrapped language workbench. We have applied sound bootstrapping to the Spoofax language workbench and report on our experience.


title: Explaining anomalies in feature models

authors:
Matthias Kowal
Sofia Ananieva
Thomas Thüm

abstract: The development of variable software, in general, and feature models, in particular, is an error-prone and time-consuming task. It gets increasingly more challenging with industrial-size models containing hundreds or thousands of features and constraints. Each change may lead to anomalies in the feature model such as making some features impossible to select. While the detection of anomalies is well-researched, giving explanations is still a challenge. Explanations must be as accurate and understandable as possible to support the developer in repairing the source of an error. We propose an efficient and generic algorithm for explaining different anomalies in feature models. Additionally, we achieve a benefit for the developer by computing short explanations expressed in a user-friendly manner and by emphasizing specific parts in explanations that are more likely to be the cause of an anomaly. We provide an open-source implementation in FeatureIDE and show its scalability for industrial-size feature models.


title: Synthesizing regular expressions from examples for introductory automata assignments

authors:
Mina Lee
Sunbeom So
Hakjoo Oh

abstract: We present a method for synthesizing regular expressions for introductory automata assignments. Given a set of positive and negative examples, the method automatically synthesizes the simplest possible regular expression that accepts all the positive examples while rejecting all the negative examples. The key novelty is the search-based synthesis algorithm that leverages ideas from over- and under-approximations to effectively prune out a large search space. We have implemented our technique in a tool and evaluated it with non-trivial benchmark problems that students often struggle with. The results show that our system can synthesize desired regular expressions in 6.7 seconds on the average, so that it can be interactively used by students to enhance their understanding of regular expressions.


title: Automated regression testing of BPMN 2.0 processes: a capture and replay framework for continuous delivery

authors:
Majid Makki
Dimitri Van Landuyt
Wouter Joosen

abstract: Regression testing is a form of software quality assurance (QA) that involves comparing the behavior of a newer version of a software artifact to its earlier correct behavior, and signaling the QA engineer when deviations are detected. Given the large potential in automated generation and execution of regression test cases for business process models in the context of running systems, powerful tools are required to make this practically feasible, more specifically to limit the potential impact on production systems, and to reduce the manual effort required from QA engineers.


title: Programmable semantic fragments: the design and implementation of typy

authors:
Cyrus Omar
Jonathan Aldrich

abstract: This paper introduces typy, a statically typed programming language embedded by reflection into Python. typy features a fragmentary semantics, i.e. it delegates semantic control over each term, drawn from Python's fixed concrete and abstract syntax, to some contextually relevant user-defined semantic fragment. The delegated fragment programmatically 1) typechecks the term (following a bidirectional protocol); and 2) assigns dynamic meaning to the term by computing a translation to Python.


title: A feature-based personalized recommender system for product-line configuration

authors:
Juliana Alves Pereira
Pawel Matuszyk
Sebastian Krieter
Myra Spiliopoulou
Gunter Saake

abstract: Today’s competitive marketplace requires the industry to understand unique and particular needs of their customers. Product line practices enable companies to create individual products for every customer by providing an interdependent set of features. Users configure personalized products by consecutively selecting desired features based on their individual needs. However, as most features are interdependent, users must understand the impact of their gradual selections in order to make valid decisions. Thus, especially when dealing with large feature models, specialized assistance is needed to guide the users in configuring their product. Recently, recommender systems have proved to be an appropriate mean to assist users in finding information and making decisions. In this paper, we propose an advanced feature recommender system that provides personalized recommendations to users. In detail, we offer four main contributions: (i) We provide a recommender system that suggests relevant features to ease the decision-making process. (ii) Based on this system, we provide visual support to users that guides them through the decision-making process and allows them to focus on valid and relevant parts of the configuration space. (iii) We provide an interactive open-source configurator tool encompassing all those features. (iv) In order to demonstrate the performance of our approach, we compare three different recommender algorithms in two real case studies derived from business experience.


title: Dependence-driven delimited CPS transformation for JavaScript

authors:
Laure Philips
Joeri De Koster
Wolfgang De Meuter
Coen De Roover

abstract: In today’s web applications asynchronous requests to remote services using callbacks or futures are omnipresent. The continuation of such a non-blocking task is represented as a callback function that will later be called with the result of the request. This style of programming where the remainder of a computation is captured in a continuation function is called continuation-passing style (CPS). This style of programming can quickly lead to a phenomenon called “call- back hell”, which has a negative impact on the maintain- ability of applications that employ this style. Several alter- natives to callbacks are therefore gaining traction within the web domain. For example, there are a number of frameworks that rely on automatically transforming sequential style code into the continuation-passing style. However, these frame- works often employ a conservative approach in which each function call is transformed into CPS. This conservative approach can sequentialise requests that could otherwise be run in parallel. So-called delimited continuations can remedy, but require special marks that have to be manually inserted in the code for marking the beginning and end of the continuation. In this paper we propose an alternative strategy in which we apply a delimited CPS transformation that operates on a Program Dependence Graph instead to find the limits of each continuation.We implement this strategy in JavaScript and demonstrate its applicability to various web programming scenarios.


title: Lightweight modular staging (LMS): generate all the things! (keynote)

abstract: Recent years have seen a surge of interest in staging and generative programming, driven by the increasing difficulty of making high-level code run fast on modern hardware. While the mechanics of program generation are relatively well understood, we have only begun to understand how to develop systems in a generative way. The Lightweight Modular Staging (LMS) platform forms the core of a research agenda to make generative programming more widely accessible, through powerful libraries and a growing selection of case studies that illuminate design patterns and crystallize best practices for high-level and effective generative programming. This talk will reflect on the foundations of LMS, on applications, achievements, challenges, as well as ongoing and future work.


title: Actor profiling in virtual execution environments

authors:
Andrea Rosà
Lydia Y. Chen
Walter Binder

abstract: Nowadays, many virtual execution environments benefit from concurrency offered by the actor model. Unfortunately, while actors are used in many applications, existing profiling tools are not much effective in analyzing the performance of applications using actors. In this paper, we present a new instrumentation-based technique to profile actors in virtual execution environments. Our technique adopts platform-independent profiling metrics that minimize the perturbations induced by the instrumentation logic and allow comparing profiling results across different platforms. In particular, our technique measures the initialization cost, the amount of executed computations, and the messages sent and received by each actor. We implement our technique within a profiling tool for Akka actors on the Java platform. Evaluation results show that our profiling technique helps performance analysis of actor utilization and communication between actors in large-scale computing frameworks.


title: Towards scalable configuration testing in variable software

authors:
Valentin Rothberg
Christian Dietrich
Andreas Ziegler
Daniel Lohmann

abstract: Testing a software product line such as Linux implies building the source with different configurations. Manual approaches to generate configurations that enable code of interest are doomed to fail due to the high amount of variation points distributed over the feature model, the build system and the source code. Research has proposed various approaches to generate covering configurations, but the algorithms show many drawbacks related to run-time, exhaustiveness and the amount of generated configurations. Hence, analyzing an entire Linux source can yield more than 30 thousand configurations and thereby exceeds the limited budget and resources for build testing.


title: Towards a software product line of trie-based collections

authors:
Michael J. Steindorfer
Jurgen J. Vinju

abstract: Collection data structures in standard libraries of programming languages are designed to excel for the average case by carefully balancing memory footprint and runtime performance. These implicit design decisions and hard-coded trade-offs do constrain users from using an optimal variant for a given problem. Although a wide range of specialized collections is available for the Java Virtual Machine (JVM), they introduce yet another dependency and complicate user adoption by requiring specific Application Program Interfaces (APIs) incompatible with the standard library.


title: Classless Java

authors:
Yanlin Wang
Haoyuan Zhang
Bruno C. d. S. Oliveira
Marco Servetto

abstract: This paper presents an OO style without classes, which we call interface-based object-oriented programming (IB). IB is a natural extension of closely related ideas such as traits. Abstract state operations provide a new way to deal with state, which allows for flexibility not available in class-based languages. In IB state can be type-refined in subtypes. The combination of a purely IB style and type-refinement enables powerful idioms using multiple inheritance and state. To introduce IB to programmers we created Classless Java: an embedding of IB directly into Java. Classless Java uses annotation processing for code generation and relies on new features of Java 8 for interfaces. The code generation techniques used in Classless Java have interesting properties, including guarantees that the generated code is type-safe and good integration with IDEs. Usefulness of IB and Classless Java is shown with examples and case studies.


title: Extensible modeling with managed data in Java

authors:
Theologos Zacharopoulos
Pablo Inostroza
Tijs van der Storm

abstract: Many model-driven development (MDD) tools employ specialized frameworks and modeling languages, and assume that the semantics of models is provided by some form of code generation. As a result, programming against models is cumbersome and does not integrate well with ordinary programming languages and IDEs. In this paper we present MD4J, a modeling approach for embedding metamodels directly in Java, using plain interfaces and annotations. The semantics is provided by data managers that create and manipulate models. This architecture enables two kinds of extensibility. First, the data managers can be changed or extended to obtain different base semantics of a model. This allows a kind of aspect-oriented programming. Second, the metamodels themselves can be extended with additional fields and methods to modularly enrich a modeling language. We illustrate our approach using the example of state machines, discuss the implementation, and evaluate it with two case-studies: the execution of UML activity diagrams and an aspect-oriented refactoring of JHotDraw.


title: Four languages and lots of macros: analyzing autotools build systems

authors:
Jafar M. Al-Kofahi
Suresh C. Kothari
Christian Kästner

abstract: Build systems are crucial for software system development, however there is a lack of tool support to help with their high maintenance overhead. GNU Autotools are widely used in the open source community, but users face various challenges from its hard to comprehend nature and staging of multiple code generation steps, often leading to low quality and error-prone build code. In this paper, we present a platform, AutoHaven, to provide a foundation for developers to create analysis tools to help them understand, maintain, and migrate their GNU Autotools build systems. Internally it uses approximate parsing and symbolic analysis of the build logic. We illustrate the use of the platform with two tools: ACSense helps developers to better understand their build systems and ACSniff detects build smells to improve build code quality. Our evaluation shows that AutoHaven can support most GNU Autotools build systems and can detect build smells in the wild.


title: Reducing calling convention overhead in object-oriented programming on embedded ARM thumb-2 platforms

authors:
Joseph Caldwell
Shigeru Chiba


title: Type qualifiers as composable language extensions

authors:
Travis Carlson
Eric Van Wyk

abstract: This paper reformulates type qualifiers as language extensions that can be automatically and reliably composed. Type qualifiers annotate type expressions to introduce new subtyping relations and are powerful enough to detect many kinds of errors. Type qualifiers, as illustrated in our ableC extensible language framework for C, can introduce rich forms of concrete syntax, can generate dynamic checks on data when static checks are infeasible or not appropriate, and inject code that affects the program's behavior, for example for conversions of data or logging.


title: Code staging in GNU Guix

abstract: GNU Guix is a "functional" package manager that borrows from earlier work on Nix by Dolstra et al.. Guix implements high-level abstractions such as packages and operating system services as domain-specific languages (DSL) embedded in Scheme, and it also implements build actions and operating system orchestration in Scheme. This leads to a multi-tier programming environment where embedded code snippets are staged for eventual execution.


title: The landscape of refactoring research in the last decade (keynote)

abstract: In the last decade refactoring research has seen an exponential growth. I will attempt to map this vast landscape and the advances that the community has made by answering questions such as who does what, when, where, with who, why, and how. I will muse on some of the factors contributing to the growth of the field, the adoption of research into industry, and the lessons that we learned along this journey. This will inspire and equip you so that you can make a difference, with people who make a difference, at a time when it makes a difference.


title: How preprocessor annotations (do not) affect maintainability: a case study on change-proneness

authors:
Wolfram Fenske
Sandro Schulze
Gunter Saake

abstract: Preprocessor annotations (e.g., #ifdef in C) enable the development of similar, but distinct software variants from a common code base. One particularly popular preprocessor is the C preprocessor, cpp. But the cpp is also widely criticized for impeding software maintenance by making code hard to understand and change. Yet, evidence to support this criticism is scarce. In this paper, we investigate the relation between cpp usage and maintenance effort, which we approximate with the frequency and extent of source code changes. To this end, we mined the version control repositories of eight open- source systems written in C. For each system, we measured if and how individual functions use cpp annotations and how they were changed. We found that functions containing cpp annotations are generally changed more frequently and more profoundly than other functions. However, when accounting for function size, the differences disappear or are greatly diminished. In summary, with respect to the frequency and extent of changes, our findings do not support the criticism of the cpp regarding maintainability.


title: Avoiding useless mutants

authors:
Leonardo Fernandes
Márcio Ribeiro
Luiz Carvalho
Rohit Gheyi
Melina Mongiovi
André L. M. Santos
Ana Cavalcanti
Fabiano Cutigi Ferrari
José Carlos Maldonado

abstract: Mutation testing is a program-transformation technique that injects artificial bugs to check whether the existing test suite can detect them. However, the costs of using mutation testing are usually high, hindering its use in industry. Useless mutants (equivalent and duplicated) contribute to increase costs. Previous research has focused mainly on detecting useless mutants only after they are generated and compiled. In this paper, we introduce a strategy to help developers with deriving rules to avoid the generation of useless mutants. To use our strategy, we pass as input a set of programs. For each program, we also need a passing test suite and a set of mutants. As output, our strategy yields a set of useless mutants candidates. After manually confirming that the mutants classified by our strategy as "useless" are indeed useless, we derive rules that can avoid their generation and thus decrease costs. To the best of our knowledge, we introduce 37 new rules that can avoid useless mutants right before their generation. We then implement a subset of these rules in the MUJAVA mutation testing tool. Since our rules have been derived based on artificial and small Java programs, we take our MUJAVA version embedded with our rules and execute it in industrial-scale projects. Our rules reduced the number of mutants by almost 13% on average. Our results are promising because (i) we avoid useless mutants generation; (ii) our strategy can help with identifying more rules in case we set it to use more complex Java programs; and (iii) our MUJAVA version has only a subset of the rules we derived.


title: Refining semantics for multi-stage programming

authors:
Rui Ge
Ronald Garcia

abstract: The multi-stage programming paradigm supports runtime code generation and execution. Though powerful, its potential is impeded by the lack of static analysis support. Van Horn and Might proposed a general-purpose approach to systematically develop static analyses by transforming an environmental abstract machine, which evolves a control string, an environment and a continuation as a program evaluates. To the best of our knowledge, no such semantics exists for a multi-stage language like MetaML.


title: Rewriting a shallow DSL using a GHC compiler extension

authors:
Mark Grebe
David Young
Andy Gill

abstract: Embedded Domain Specific Languages are a powerful tool for developing customized languages to fit specific problem domains. Shallow EDSLs allow a programmer to program using many of the features of a host language and its syntax, but sacrifice performance. Deep EDSLs provide better performance and flexibility, through the ability to manipulate the abstract syntax tree of the DSL program, but sacrifice syntactical similarity to the host language. Using Haskino, an EDSL designed for small embedded systems based on the Arduino line of microcontrollers, and a compiler plugin for the Haskell GHC compiler, we show a method for combining the best aspects of shallow and deep EDSLs. The programmer is able to write in the shallow EDSL, and have it automatically transformed into the deep EDSL. This allows the EDSL user to benefit from powerful aspects of the host language, Haskell, while meeting the demanding resource constraints of the small embedded processing environment.


title: Analyzing the impact of natural language processing over feature location in models

authors:
Raúl Lapeña
Jaime Font
Oscar Pastor
Carlos Cetina

abstract: Feature Location (FL) is a common task in the Software Engineering field, specially in maintenance and evolution of software products. The results of FL depend in a great manner in the style in which Feature Descriptions and software artifacts are written. Therefore, Natural Language Processing (NLP) techniques are used to process them. Through this paper, we analyze the influence of the most common NLP techniques over FL in Conceptual Models through Latent Semantic Indexing, and the influence of human participation when embedding domain knowledge in the process. We evaluated the techniques in a real-world industrial case study in the rolling stocks domain.


title: A classification of variation control systems

authors:
Lukas Linsbauer
Thorsten Berger
Paul Grünbacher

abstract: Version control systems are an integral part of today's software and systems development processes. They facilitate the management of revisions (sequential versions) and variants (concurrent versions) of a system under development and enable collaboration between developers. Revisions are commonly maintained either per file or for the whole system. Variants are supported via branching or forking mechanisms that conceptually clone the whole system under development. It is known that such cloning practices come with disadvantages. In fact, while short-lived branches for isolated development of new functionality (a.k.a. feature branches) are well supported, dealing with long-term and fine-grained system variants currently requires employing additional mechanisms, such as preprocessors, build systems or custom configuration tools. Interestingly, the literature describes a number of variation control systems, which provide a richer set of capabilities for handling fine-grained system variants compared to the version control systems widely used today. In this paper we present a classification and comparison of selected variation control systems to get an understanding of their capabilities and the advantages they can offer. We discuss problems of variation control systems, which may explain their comparably low popularity. We also propose research activities we regard as important to change this situation.


title: A Haskell compiler for signal transforms

authors:
Geoffrey Mainland
Jeremy Johnson

abstract: Building a reusable, auto-tuning code generator from scratch is a challenging problem, requiring many careful design choices. We describe HSpiral, a Haskell compiler for signal transforms that builds on the foundational work of Spiral. Our design leverages many Haskell language features to ensure that our framework is reusable, flexible, and efficient. As well as describing the design of our system, we show how to extend it to support new classes of transforms, including the number-theoretic transform and a variant of the split-radix algorithm that results in reduced operation counts. We also show how to incorporate rewrite rules into our system to reproduce results from previous literature on code generation for the fast Fourier transform.


title: Automatic generation of virtual learning spaces driven by CaVaDSL: an experience report

authors:
Ricardo Giuliani Martini
Pedro Rangel Henriques

abstract: Several applications are based on Domain-Specific Languages (DSL). They provide the right terminology to a peculiar problem/subject, because they use a particular domain vocabulary that defines abstract concepts, different from general-purpose languages. Aiming an easy generation of virtual Learning Spaces (LS) for the use of the responsible of institutional archives or museums, we have idealized and developed an external domain-specific language, called CaVa DSL, to describe, in an abstract level, virtual exhibition rooms in the museum curator's viewpoint, giving the curator the possibility to specify the virtual LS upon a domain ontology vocabulary. We also contribute with a set of processors that deal with CaVa DSL and generates virtual Learning Spaces, turning available the navigation over important and real information contained in archival documents to the public through virtual museums. To demonstrate the obtained results, we present a running example along the paper showing the virtual LS generation process.


title: Silverchain: a fluent API generator

authors:
Tomoki Nakamaru
Kazuhiro Ichikawa
Tetsuro Yamazaki
Shigeru Chiba

abstract: This paper presents a tool named Silverchain, which generates class definitions for a fluent API from the grammar of the API. A fluent API is an API that is used by method chaining and its grammar is a BNF-like set of rules that defines method chains accepted in type checking. Fluent APIs generated by Silverchain provide two styles of APIs: One is for building a chain by concatenating all method calls in series. The other is for building a chain from partial chains by passing child chains to method calls in the parent chain as their arguments. To generate such a fluent API, Silverchain first translates given grammar into a set of deterministic pushdown automata without ϵ-transitions, then encodes these automata into class definitions. Each constructed automata corresponds to a nonterminal in given grammar and recognizes symbol sequences produced from its corresponding nonterminal.


title: Staging for generic programming in space and time

authors:
Georg Ofenbeck
Tiark Rompf
Markus Püschel

abstract: Metaprogramming is among the most promising candidates to solve the abstraction vs performance trade-off that plagues software engineering through specialization. Metaprogramming has been used to enable low-overhead generic programming for a long time, with C++ templates being one of the most prominent examples. But often a single, fixed pattern of specialization is not enough, and more flexibility is needed. Hence, this paper seeks to apply generic programming techniques to challenges in metaprogramming, in particular to abstract over the execution stage of individual program expressions. We thus extend the scope of generic programming into the dimension of time. The resulting notion of stage polymorphism enables novel abstractions in the design of program generators, which we develop and explore in this paper. We present one possible implementation, in Scala using the lightweight modular staging (LMS) framework, and apply it to two important case studies: convolution on images and the fast Fourier transform (FFT).


title: Staging with control: type-safe multi-stage programming with control operators

authors:
Junpei Oishi
Yukiyoshi Kameyama

abstract: Staging allows a programmer to write domain-specific, custom code generators. Ideally, a programming language for staging provides all necessary features for staging, and at the same time, gives static guarantee for the safety properties of generated code including well typedness and well scopedness. We address this classic problem for the language with control operators, which allow code optimizations in a modular and compact way. Specifically, we design a staged programming language with the expressive control operators shift0 and reset0, which let us express, for instance, multi-layer let-insertion, while keeping the static guarantee of well typedness and well scopedness. For this purpose, we extend our earlier work on refined environment classifiers which were introduced for the staging language with state. We show that our language is expressive enough to express interesting code generation techniques, and that the type system enjoys type soundness. We also mention a type inference algorithm for our language under reasonable restriction.


title: Quoted staged rewriting: a practical approach to library-defined optimizations

authors:
Lionel Parreaux
Amir Shaikhha
Christoph E. Koch

abstract: Staging has proved a successful technique for programmatically removing code abstractions, thereby allowing for faster program execution while retaining a high-level interface for the programmer. Unfortunately, techniques based on staging suffer from a number of problems — ranging from practicalities to fundamental limitations — which have prevented their widespread adoption. We introduce Quoted Staged Rewriting (QSR), an approach that uses type-safe, pattern matching-enabled quasiquotes to define optimizations. The approach is “staged” in two ways: first, rewrite rules can execute arbitrary code during pattern matching and code reconstruction, leveraging the power and flexibility of staging; second, library designers can orchestrate the application of successive rewriting phases (stages). The advantages of using quasiquote-based rewriting are that library designers never have to deal directly with the intermediate representation (IR), and that it allows for non-intrusive optimizations — in contrast with staging, it is not necessary to adapt the entire library and user programs to accommodate optimizations.


title: Rewriting for sound and complete union, intersection and negation types

abstract: Implementing the type system of a programming language is a critical task that is often done in an ad-hoc fashion. Whilst this makes it hard to ensure the system is sound, it also makes it difficult to extend as the language evolves. We are interested in describing type systems using declarative rewrite rules from which an implementation can be automatically generated. Whilst not all type systems are easily expressed in this manner, those involving unions, intersections and negations are well-suited for this.


title: RaTrace: simple and efficient abstractions for BVH ray traversal algorithms

authors:
Arsène Pérard-Gayot
Martin Weier
Richard Membarth
Philipp Slusallek
Roland Leißa
Sebastian Hack

abstract: In order to achieve the highest possible performance, the ray traversal and intersection routines at the core of every high-performance ray tracer are usually hand-coded, heavily optimized, and implemented separately for each hardware platform—even though they share most of their algorithmic core. The results are implementations that heavily mix algorithmic aspects with hardware and implementation details, making the code non-portable and difficult to change and maintain.


title: Accurate reification of complete supertype information for dynamic analysis on the JVM

authors:
Andrea Rosà
Eduardo Rosales
Walter Binder

abstract: Reflective supertype information (RSI) is useful for many instrumentation-based dynamic analyses on the Java Virtual Machine (JVM). On the one hand, while such information can be obtained when performing the instrumentation within the same JVM process executing the instrumented program, in-process instrumentation severely limits the code coverage of the analysis. On the other hand, performing the instrumentation in a separate process can achieve full code coverage, but complete RSI is generally not available, often requiring expensive runtime checks in the instrumented program. Providing accurate and complete RSI in the instrumentation process is challenging because of dynamic class loading and classloader namespaces. In this paper, we present a novel technique to accurately reify complete RSI in a separate instrumentation process. We implement our technique in the dynamic analysis framework DiSL and evaluate it on a task profiler, achieving speedups of up to 45% for an analysis with full code coverage.


title: Towards compositional and generative tensor optimizations

authors:
Adilla Susungi
Norman A. Rink
Jerónimo Castrillón
Immo Huismann
Albert Cohen
Claude Tadonki
Jörg Stiller
Jochen Fröhlich

abstract: Many numerical algorithms are naturally expressed as operations on tensors (i.e. multi-dimensional arrays). Hence, tensor expressions occur in a wide range of application domains, e.g. quantum chemistry and physics; big data analysis and machine learning; and computational fluid dynamics. Each domain, typically, has developed its own strategies for efficiently generating optimized code, supported by tools such as domain-specific languages, compilers, and libraries. However, strategies and tools are rarely portable between domains, and generic solutions typically act as ''black boxes'' that offer little control over code generation and optimization. As a consequence, there are application domains without adequate support for easily generating optimized code, e.g. computational fluid dynamics. In this paper we propose a generic and easily extensible intermediate language for expressing tensor computations and code transformations in a modular and generative fashion. Beyond being an intermediate language, our solution also offers meta-programming capabilities for experts in code optimization. While applications from the domain of computational fluid dynamics serve to illustrate our proposed solution, we believe that our general approach can help unify research in tensor optimizations and make solutions more portable between domains.


title: Parser generation by example for legacy pattern languages

abstract: Most modern software languages enjoy relatively free and relaxed concrete syntax, with significant flexibility of formatting of the program/model/sheet text. Yet, in the dark legacy corners of software engineering there are still languages with a strict fixed column-based structure — the compromises of times long gone, attempting to combine some human readability with some ease of machine processing. In this paper, we consider an industrial case study for retirement of a legacy domain-specific language, completed under extreme circumstances: absolute lack of documentation, varying line structure, hierarchical blocks within one file, scalability demands for millions of lines of code, performance demands for manipulating tens of thousands multi-megabyte files, etc. However, the regularity of the language allowed to infer its structure from the available examples, automatically, and produce highly efficient parsers for it.


title: Verification of high-level transformations with inductive refinement types

authors:
Ahmad Salim Al-Sibahi
Thomas P. Jensen
Aleksandar S. Dimovski
Andrzej Wasowski

abstract: High-level transformation languages like Rascal include expressive features for manipulating large abstract syntax trees: first-class traversals, expressive pattern matching, backtracking and generalized iterators. We present the design and implementation of an abstract interpretation tool, Rabit, for verifying inductive type and shape properties for transformations written in such languages. We describe how to perform abstract interpretation based on operational semantics, specifically focusing on the challenges arising when analyzing the expressive traversals and pattern matching. Finally, we evaluate Rabit on a series of transformations (normalization, desugaring, refactoring, code generators, type inference, etc.) showing that we can effectively verify stated properties.


title: Funcons for HGMP: the fundamental constructs of homogeneous generative meta-programming (short paper)

abstract: The PLanCompS project proposes a component-based approach to programming-language development in which fundamental constructs (funcons) are reused across language definitions. Homogeneous Generative Meta-Programming (HGMP) enables writing programs that generate code as data, at run-time or compile-time, for manipulation and staged evaluation. Building on existing formalisations of HGMP, this paper introduces funcons for HGMP and demonstrates their usage in component-based semantics.


title: Orchestrating dynamic analyses of distributed processes for full-stack JavaScript programs

authors:
Laurent Christophe
Coen De Roover
Elisa Gonzalez Boix
Wolfgang De Meuter

abstract: Dynamic analyses are commonly implemented by instrumenting the program under analysis. Examples of such analyses for JavaScript range from checkers of user- defined invariants to concolic testers. For a full-stack JavaScript program, these analyses would benefit from reasoning about the state of the client-side and server-side processes it is comprised of. Lifting a dynamic analysis so that it supports full-stack programs can be challenging. It involves distributed communication to maintain the analysis state across all processes, which has to be deadlock-free. In this paper, we advocate maintaining distributed analysis state in a centralized analysis process instead — which is communicated with from the processes under analysis. The approach is supported by a dynamic analysis platform that provides abstractions for this communication. We evaluate the approach through a case study. We use the platform to build a distributed origin analysis, capable of tracking the expressions from which values originate from across process boundaries, and deploy it on collaborative drawing application. The results show that our approach greatly simplifies the lifting process at the cost of a computational overhead. We deem this overhead acceptable for analyses intended for use at development time.


title: Explaining spreadsheets with spreadsheets (short paper)

authors:
Jácome Cunha
Mihai Dan
Martin Erwig
Danila Fedorin
Alex Grejuc

abstract: Based on the concept of explanation sheets, we present an approach to make spreadsheets easier to understand and thus easier to use and maintain. We identify the notion of explanation soundness and show that explanation sheets which conform to simple rules of formula coverage provide sound explanations. We also present a practical evaluation of explanation sheets based on samples drawn from widely used spreadsheet corpora and based on a small user study.


title: Rash: from reckless interactions to reliable programs

authors:
William Gallard Hatch
Matthew Flatt

abstract: Command languages like the Bourne Shell provide a terse syntax for exploratory programming and system interaction. Shell users can begin to write programs that automate their tasks by simply copying their interactions verbatim into a script file. However, command languages usually scale poorly beyond small scripts, and they can be difficult to integrate into larger programs. General-purpose languages scale well, but are verbose and unwieldy for common interactive actions such as process composition.


title: Inferring ownership domains from refinements

authors:
Ebrahim Khalaj
Marwan Abi-Antoun

abstract: Ownership type qualifiers clarify aliasing invariants that cannot be directly expressed in mainstream programming languages. Adding qualifiers to code, however, often involves significant overhead and difficult interaction.