SLE 2021: Proceedings of the 14th ACM SIGPLAN International Conference on Software Language Engineering

Full Citation in the ACM Digital Library

SESSION: Keynote

Integrating usability into programming language design (keynote)

Programming language design research has traditionally focused primarily on theoretical properties and performance considerations. But programming languages are interfaces that programmers use to write programs. Recent work has begun to explore how to integrate interdisciplinary methods, including qualitative and quantitative user studies, into the language design process. I’ll describe how we applied such methods in two different designs, Obsidian and Glacier, some of the insights we gained, and discuss the larger impact these emerging methods can have on the field.


Monilogging for executable domain-specific languages

Runtime monitoring and logging are fundamental techniques for analyzing and supervising the behavior of computer programs. However, supporting these techniques for a given language induces significant development costs that can hold language engineers back from providing adequate logging and monitoring tooling for new domain-specific modeling languages. Moreover, runtime monitoring and logging are generally considered as two different techniques: they are thus implemented separately which makes users prone to overlooking their potentially beneficial mutual interactions. We propose a language-agnostic, unifying framework for runtime monitoring and logging and demonstrate how it can be used to define loggers, runtime monitors and combinations of the two, aka. moniloggers. We provide an implementation of the framework that can be used with Java-based executable languages, and evaluate it on 2 implementations of the NabLab interpreter, leveraging in turn the instrumentation facilities offered by Truffle, and those offered by AspectJ.

Vision: the next 700 language workbenches

Language workbenches (LWBs) are tools to define software languages together with tailored Integrated Development Environments for them. A comprehensive review of language workbenches by Erdweg et al. (Comput. Lang. Syst. Struct. 44, 2015) presented a feature model of functionality of LWBs from the point of view of "languages that can be defined with a LWB, and not the definition mechanism of the LWB itself". This vision paper discusses possible functionality of LWBs with regard to language definition mechanisms. We have identified five groups of such functionality, related to: metadefinitions, metamodifications, metaprocess, LWB itself, and programs written in languages defined in a LWB. We design one of the features ("ability to define dependencies between language concerns") based on our vision.

Automating the synthesis of recommender systems for modelling languages

We are witnessing an increasing interest in building recommender systems (RSs) for all sorts of Software Engineering activities. Modelling is no exception to this trend, as modelling environments are being enriched with RSs that help building models by providing recommendations based on previous solutions to similar problems in the same domain. However, building a RS from scratch requires considerable effort and specialized knowledge. To alleviate this problem, we propose an automated approach to the generation of RSs for modelling languages. Our approach is model-based, and we provide a domain-specific language called Droid to configure every aspect of the RS (like the type and features of the recommended items, the recommendation method, and the evaluation metrics). The RS so configured can be deployed as a service, and we offer out-of-the-box integration of this service with the EMF tree editor. To assess the usefulness of our proposal, we present a case study on the integration of a generated RS with a modelling chatbot, and report on an offline experiment measuring the precision and completeness of the recommendations.

Executing certified model transformations on Apache Spark

Formal reasoning on model transformation languages allows users to certify model transformations against contracts. CoqTL includes a specification of a transformation engine in the Coq interactive theorem prover. An executable engine can be automatically extracted from this specification. Transformation contracts are proved by the user against the CoqTL specification and guaranteed to hold on the transformation running on the extracted implementation of CoqTL. The design of the transformation engine specification in CoqTL aims at easing the certification step, but this requirement harms the execution performance of the extracted engine.

In this paper, we aim at providing a scalable distributed implementation of the CoqTL specification. To achieve this objective we proceed in two steps. First, we introduce a refined specification of CoqTL that increases the engine parallelization. We present a mechanized proof of the equivalence with standard CoqTL. Second, we develop a prototype implementation of the refined specification on top of Spark. Finally, by evaluating the performance of a simple case study, we assess the speedup our solution can reach.

New ideas: automated engineering of metamorphic testing environments for domain-specific languages

Two crucial aspects for the trustworthy utilization of domain-specific languages (DSLs) are their semantic correctness, and proper testing support for their users. Testing is frequently used to verify correctness, but is often done informally -- which may yield unreliable results -- and requires substantial effort for creating suitable test cases and oracles.

To alleviate this situation, we propose an automated technique for building metamorphic testing environments for DSLs. Metamorphic testing identifies expected relationships between the outputs of two consecutive tests, reducing the effort in specifying oracles and creating test cases manually. This new ideas paper presents the overarching concepts, the architecture and a prototype implementation. We illustrate our proposal using a DSL to model and simulate data centres.

A concurrency model for JavaScript with cooperative cancellation

This paper proposes a concurrency model for JavaScript with thread-like abstractions and cooperative cancellation. JavaScript uses an event-driven model, where an active computation runs until it completes or blocks for an event while concurrent computations wait for other events as callbacks. With the introduction of Promises, the control flow of callbacks can be written in a more direct style. However, the event-based model is still a source of confusion with regard to execution order, race conditions, and termination.

The thread model is a familiar concept to programmers and can help reduce concurrency errors in JavaScript programs. This work is a library-based design, which uses an abstraction based on the reader monad to pass a thread ID through a thread's computation. A thread can be cancelled, paused, and resumed with its thread ID. This design allows hierarchical cancellation where a child thread is cancelled if its parent is cancelled. It also defines synchronization primitives to protect shared states. A formal semantics is included to give a precise definition of the proposed model.

There is more than one way to zen your Python

The popularity of Python can be at least partially attributed to the concept of pythonicity, loosely defined as a combination of good practices accepted within the community. Despite the popularity of both Python itself and the pythonicity of code written in it, this concept has not been studied that well, and the first attempts to define it formally are rather recent. In this paper, we take the next steps in exploring this topic by conducting an independent literature review in order to create a catalogue of pythonic idioms, reproduce the results of a recent paper on the usage of pythonic idioms, perform an external direct replication of it by reusing the same open source toolset and dataset, and extend the body of knowledge by also analysing how the use of pythonic idioms evolve over time in open source codebases.

Getting grammars into shape for block-based editors

Block-based environments are visual programming environments that allow users to program by interactively arranging visual jigsaw-like blocks. They have shown to be helpful in several domains but often require experienced developers for their creation. Previous research investigated the use of language workbenches to generate block-based editors based on grammars, but the generated block-based editors sometimes provided too many unnecessary blocks, leading to verbose environments and programs. To reduce the number of interactions, we propose a set of transformations to simplify the original grammar, yielding a reduction of the number of (useful) kinds of blocks available in the resulting editors. We show that our generated block-based editors are improved for a set of observed aesthetic criteria up to a certain complexity. As such, analyzing and simplifying grammars before generating block-based editors allows us to derive more compact and potentially more usable block-based editors, making reuse of existing grammars through automatic generation feasible.

Fast incremental PEG parsing

Incremental parsing is an integral part of code analysis performed by text editors and integrated development environments. This paper presents new methods to significantly improve the efficiency of incremental parsing for Parsing Expression Grammars (PEGs). We build on Incremental Packrat Parsing, an algorithm that adapts packrat parsing to an incremental setting, by implementing the memoization table as an interval tree with special support for shifting intervals, and modifying the memoization strategy to create tree structures in the table. Our approach enables reparsing in time logarithmic in the size of the input for typical edits, compared with linear-time reparsing for Incremental Packrat Parsing. We implement our methods in a prototype called GPeg, a parsing machine for PEGs with support for dynamic parsers (an important feature for extensibility in editors). Experiments show that GPeg has strong performance (sub-5ms reparse times) across a variety of input sizes (tens to hundreds of megabytes) and grammar types (from full language grammars to minimal grammars), and compares well with existing incremental parsers. As a complete example, we implement a syntax highlighting library and prototype editor using GPeg, with optimizations for these applications.

Faster reachability analysis for LR(1) parsers

We present a novel algorithm for reachability in an LR(1) automaton. For each transition in the automaton, the problem is to determine under what conditions this transition can be taken, that is, which (minimal) input fragment and which lookahead symbol allow taking this transition. Our algorithm outperforms Pottier's algorithm (2016) by up to three orders of magnitude on real-world grammars. Among other applications, this vastly improves the scalability of Jeffery's error reporting technique (2003), where a mapping of (reachable) error states to messages must be created and maintained.

Automatic grammar repair

We describe the first approach to automatically repair bugs in context-free grammars: given a grammar that fails some tests in a given test suite, we iteratively and gradually transform the grammar until it passes all tests. Our core idea is to build on spectrum-based fault localization to identify promising repair sites (i.e., specific positions in rules), and to apply grammar patches at these sites whenever they satisfy explicitly formulated pre-conditions necessary to potentially improve the grammar.

We have implemented this approach in the gfixr system, and successfully used it to fix grammars students submitted as homeworks in a compiler engineering course, and to map one Pascal dialect grammar against another dialect. gfixr can be configured to explore the repair space in different ways, and can also take advantage of counterexamples to enable restriction patches that make the grammar less permissive.

Vision: bias in systematic grammar-based test suite construction algorithms

The core of grammar-based test suite construction algorithms is a procedure to derive a set of specific phrases, which are then converted into sentences that can be fed into the system under test. This process includes several degrees of freedom and different implementations choose different but ultimately fixed solutions. We show that these fixed choices inherently bias the generated test suite.

We quantify these biases and evaluate the effect they have on coverage over the system under test for which the test suite is constructed. We show that the effect of these biases remains prevalent in large real world grammars and systems, even when the test suites grow very large.

SEALS: a framework for building self-adaptive virtual machines

Over recent years, self-adaptation has become a major concern for software systems that evolve in changing environments. While expert developers may choose a manual implementation when self-adaptation is the primary concern, self-adaptation should be abstracted for non-expert developers or when it is a secondary concern. We present SEALS, a framework for building self-adaptive virtual machines for domain-specific languages. This framework provides first-class entities for the language engineer to promote domain-specific feedback loops in the definition of the DSL operational semantics. In particular, the framework supports the definition of (i) the abstract syntax and the semantics of the language as well as the correctness envelope defining the acceptable semantics for a domain concept, (ii) the feedback loop and associated trade-off reasoning, and (iii) the adaptations and the predictive model of their impact on the trade-off. We use this framework to build three languages with self-adaptive virtual machines and discuss the relevance of the abstractions, effectiveness of correctness envelopes, and compare their code size and performance results to their manually implemented counterparts. We show that the framework provides suitable abstractions for the implementation of self-adaptive operational semantics while introducing little performance overhead compared to a manual implementation.

FIDDLR: streamlining reuse with concern-specific modelling languages

Model-Driven Engineering (MDE) reduces complexity, improves Separation of Concerns and promotes reuse by structuring software development as a process of model production and refinement. Domain-Specific Modelling Languages and Aspect-Oriented Modelling techniques can reduce complexity and improve modularization of crosscutting concerns in situations where the features of general purpose modelling languages are not well aligned with the subject of study. In this article we present FIDDLR, a novel framework that integrates the ideas of Domain-Specific Modelling Languages, Concern-Oriented Reuse and MDE to modularize concerns that cross-cut multiple levels of abstraction of the software development process and streamline the reuse process. It also prescribes the integration of the different tooling along this process. We demonstrate the effectiveness of our framework and the potential for reduced complexity and leveraged reuse by building a reusable concern that exposes the services a system offers through a REST interface.