Scala 2018- Proceedings of the 9th ACM SIGPLAN International Symposium on Scala

Full Citation in the ACM Digital Library

SESSION: Keynote

Cross-platform language design in Scala.js (keynote)

Have you ever wondered what is the secret sauce of Scala.js? What defines Scala.js, above all else, is the overarching will to make it cross-platform. A cross-platform language is both portable—most source code cross-compiles and behaves the same way on multiple platforms—and interoperable—code written in that language can interoperate with other languages on the target platforms. Most multi-platform languages are designed with one of those two properties in mind, and only address the other one as an afterthought. This results in poor integration, difficulty to write portable code, or even the impossibility to use some platform-specific libraries. This talk shows how Scala.js was designed as a cross-platform language. We show how portability and interoperability drive every design decision, from which language feature to include to performance considerations. We state a criteria of completeness for interoperability, and show how Scala.js satisfies it (with the exception of one JavaScript language feature, still work-in-progress). We give insights about what features are critical for portability, and which ones can be relaxed in the name of performance. In particular, we stress the importance of the ecosystem of libraries: existing assumptions in the ecosystem can force the language designer into reproducing behaviors of Scala/JVM, even when they are accidental. As a practical exercise, we study the main language changes that made it into Scala.js 1.x wrt. 0.6.x—as well as possible future developments—and how they fit into the cross-platform language design methodology.

SESSION: DSLs and Parsing

A domain-specific language for microservices

A common architectural pattern for complex online systems is a collection of “microservices” communicating via RPC interfaces. A service architecture provides autonomy for teams to develop, deploy, and operate system modules without centralized coordination. But this autonomy comes at a cost in leverage—the fixed costs of running a service are high, and the desire to avoid them can lead to poor design choices.

In this paper we describe Strato, a system built at Twitter that runs many microservices hosted in a shared service platform—trading a little autonomy for a lot of leverage. Hosted microservices are written in a Scala-like DSL that supports transparent concurrency and native access to Thrift data (the common currency of services at Twitter). The DSL compiles to a concurrency library written in Scala with an arrows-based interface. We detail the design and implementation of the DSL and concurrency library, and evaluate the effectiveness of Strato in improving leverage at Twitter.

Parser combinators for context-free path querying

Transparent integration of a domain-specific language for specification of context-free path queries (CFPQs) into a general-purpose programming language as well as static checking of errors in queries may greatly simplify the development of applications using CFPQs. LINQ and ORM can be used for the integration, but they have issues with flexibility: query decomposition and reusing of subqueries are a challenge. Adaptation of parser combinators technique for paths querying may solve these problems. Conventional parser combinators process linear input, and only the Trails library is known to apply this technique for path querying. Trails suffers the common parser combinators issue: it does not support left-recursive grammars and also experiences problems in cycles handling. We demonstrate that it is possible to create general parser combinators for CFPQ which support arbitrary context-free grammars and arbitrary input graphs. We implement a library of such parser combinators and show that it is applicable for realistic tasks.

Garnishing parsec with parsley

Parser combinators are a clean and powerful abstraction which can provide reasonably efficient means of parsing a grammar into a form which the programmer desires. They remain close to the domain of grammars whilst at the same time offering enormous flexibility. In Haskell, the Parsec library is a prime example of such a library. However, a direct translation to Scala proves to be unbearably slow. This paper describes the semantics and design of a new library, called Parsley, which retains a close resemblance to Parsec style whilst providing very competitive performance.

SESSION: Scala Foundations

Path dependent types with path-equality

While the Scala type system provides expressive features like objects with type members, the lack of equality checking between path-dependent types prohibits some programming idioms. One such an example is abstract domain combinators in implementing static analyzers. In this paper, we propose to extend the Scala type system with path-equality, and formalize it as a DOT variant, π DOT, which supports records with type members and elds. We show that π DOT has the normalization property and prove its type soundness.

κDOT: scaling DOT with mutation and constructors

Scala unifies concepts from object and module systems by allowing for objects with type members which are referenced via path-dependent types. The Dependent Object Types (DOT) calculus of Amin et al. models only this core part of Scala, but does not have many fundamental features of Scala such as strict and mutable fields. Since the most commonly used field types in Scala are strict,the correspondence between DOT and Scala is too weak for us to meaningfully prove static analyses safe for Scala by proving them safe for DOT.

A DOT calculus that can support strict and mutable fields together with constructors that do field initialization would be more suitable for analysis of Scala. Toward this goal, we present κDOT, an extension of DOT that supports constructors and field mutation and can emulate the different types of fields in Scala. We have proven κDOT sound through a mechanized proof in Coq. We present the key features of κDOT and its operational semantics and discuss work-in-progress toward making κDOT fully strict.

Initialization patterns in Dotty

Safe object initialization is important to avoid a category of runtime errors in programming languages. In this paper, we provide a case study of the initialization patterns on the Dotty compiler. In particular, we find that calling dynamic-dispatching methods, the usage of closures and instantiating nested classes are important for initialization of Scala objects. Based on the study, we conclude that existing proposals for safe initialization are inadequate for Scala.

SESSION: Scala Extensions

Truly abstract interfaces for algebraic data types: the extractor typing problem

Pattern matching enables inspecting algebraic data types, but typically prevents hiding the implementation of the matched algebraic data type. In Scala, instead, extractors also allow pattern matching on non-algebraic data types and invoking methods on the obtained objects, while partially decoupling API consumers from the API implementation.

But as we show in this paper, pattern matching using extractors is restricted compared to matching against case classes. We argue this violates the appropriate variant of the uniform access principle. To address this problem, we propose a small language extension, which enables defining truly abstract interfaces and freely evolve their implementation.

Interflow: interprocedural flow-sensitive type inference and method duplication

Scala heavily relies on a number of object-oriented abstractions to support its feature-rich collections library. There are known techniques that optimize those abstractions away in just-in-time (JIT) compilers, but applying them in the ahead-of-time (AOT) setting is problematic. Profile-guided optimization (PGO) lets AOT compilers apply some of the same optimizations that JIT compilers employ, but it comes at a high complexity cost.

In this paper, we introduce Interflow, an alternative approach towards ahead-of-time optimization of Scala programs which relies on interprocedural flow-sensitive type inference and method duplication. Our evaluation shows that an Interflow-based optimizing compiler built on top of the Scala Native toolchain outperforms existing PGO-based optimizing compilers for Scala.

Moreover, we demonstrate that Interflow and PGO can be combined to achieve further improvements. On our benchmarks, with both Interflow and PGO enabled, the Scala Native toolchain approaches the performance of the HotSpot JVM.

Extending Scala with records: design, implementation, and evaluation

This paper presents a design for extensible records in Scala satisfying design goals such as structural subtyping, typesafe polymorphic operations, and separate compilation without runtime bytecode generation. Using new features of Scala 3, the design requires only minimal, local changes to the Scala 3 reference compiler Dotty as well as a small library component. Runtime performance is evaluated experimentally using a novel benchmarking suite generator, showing that the design is competitive with Scala 2's cached reflection for structural field access, and excels at immutable extension and update operations.