Powered by
2016 7th ACM SIGPLAN Scala Symposium (SCALA 2016),
October 30–31, 2016,
Amsterdam, Netherlands
Frontmatter
Message from the Chairs
It is our great pleasure to welcome you to the second edition of the Scala Symposium (Scala '16). The 2016 Scala Symposium is part of SPLASH 2016 and takes place on October 30th and 31st 2016 in Amsterdam, the Netherlands. The Scala Symposium is a forum for researchers and practitioners to share new ideas and results related and of interest to the Scala programming language community.
Papers
A Scala Library for Testing Student Assignments on Concurrent Programming
Mikaël Mayer and Ravichandhran Madhavan
(EPFL, Switzerland)
We present a lightweight library for testing concurrent Scala programs by systematically exploring multiple interleavings between user-specified operations on shared objects. Our library is targeted at beginners of concurrent programming in Scala, runs on a standard JVM, and supports conventional synchronization primitives such as `wait`, `notify`, and `synchronized`. The key component of the library is the trait `SchedulableMonitor` that accepts a thread schedule, and interleaves as per the schedule all user-specified operations invoked through multiple threads on objects implementing the trait. Using our library, we developed a unit test engine that tests concurrent operations on shared objects on thousands of schedules obtained by bounding the number of context-switches. If a unit test fails on a schedule, the test engine offers as feedback the interleaved traces of execution that resulted in the failure. We used our test engine to automatically test and evaluate two assignments: (a) lock-based producer/consumer problem, and (b) lock-free sorted list implementation, offered to a class of 150 under-graduate students of EPFL. Our evaluations show that the system is effective in detecting bugs in students' solutions.
@InProceedings{SCALA16p1,
author = {Mikaël Mayer and Ravichandhran Madhavan},
title = {A Scala Library for Testing Student Assignments on Concurrent Programming},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {1--10},
doi = {},
year = {2016},
}
Reactive Async: Expressive Deterministic Concurrency
Philipp Haller, Simon Geries, Michael Eichberg, and Guido Salvaneschi
(KTH, Sweden; TU Darmstadt, Germany)
Concurrent programming is infamous for its difficulty. An important source of difficulty is non-determinism, stemming from unpredictable interleavings of concurrent activities. Futures and promises are widely-used abstractions that help designing deterministic concurrent programs, although this property cannot be guaranteed statically in mainstream programming languages. Deterministic-by-construction concurrent programming models avoid this issue, but they typically restrict expressiveness in important ways.
This paper introduces a concurrent programming model, Reactive Async, which decouples concurrent computations using so-called cells, shared locations which generalize futures as well as recent deterministic abstractions such as LVars. Compared to previously
proposed programming models Reactive Async provides (a) a fallback mechanism for the case where no computation ever computes the value of a given cell, and (b) explicit and optimized handling of cyclic dependencies. We present a complete implementation of the Reactive Async programming model as a library in Scala. Finally, the paper reports on a case study applying Reactive Async to static analyses of JVM bytecode based on the Opal framework.
@InProceedings{SCALA16p11,
author = {Philipp Haller and Simon Geries and Michael Eichberg and Guido Salvaneschi},
title = {Reactive Async: Expressive Deterministic Concurrency},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {11--20},
doi = {},
year = {2016},
}
RandIR: Differential Testing for Embedded Compilers
Georg Ofenbeck,
Tiark Rompf, and
Markus Püschel
(ETH Zurich, Switzerland; Purdue University, USA)
This paper describes RandIR, a tool for differential testing of compilers using random instances of a given intermediate representation (IR). RandIR assumes no fixed target language but instead supports extensible IR-definitions through an internal IR-independent representation of operations. This makes it particularly well suited to test embedded compilers for multi-stage programming, which is our main use case. The ideas underlying our work, however, are more generally applicable.
RandIR is able to automatically simplify failing instances of a test, a technique commonly referred to as shrinking. This enables testing with large random IR samples, thus increasing the odds of detecting a buggy behavior, while still being able to simplify failing instances to human-readable code.
@InProceedings{SCALA16p21,
author = {Georg Ofenbeck and Tiark Rompf and Markus Püschel},
title = {RandIR: Differential Testing for Embedded Compilers},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {21--30},
doi = {},
year = {2016},
}
SMT-Based Checking of Predicate-Qualified Types for Scala
Georg Stefan Schmid and
Viktor Kuncak
(EPFL, Switzerland)
We present *qualified types* for Scala, a form of refinement types adapted to the Scala language. Qualified types allow users to refine base types and classes using predicate expressions. We implemented a type checker for qualified types that is embedded in Scala's next-generation compiler Dotty and delegates constraint checking to an SMT solver. Our system supports many of Scala's functional as well as its object-oriented constructs. To propagate user-provided qualifier ascriptions we utilize both Scala's own type system and an incomplete, but effective qualifier inference algorithm. Our evaluation shows that for a series of examples exerting various of Scala's language features, the additional compile-time overhead is manageable. By combining these features we show that one can verify essential safety properties such as static bounds-checks while retaining several of Scala's advanced features.
@InProceedings{SCALA16p31,
author = {Georg Stefan Schmid and Viktor Kuncak},
title = {SMT-Based Checking of Predicate-Qualified Types for Scala},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {31--40},
doi = {},
year = {2016},
}
Reflections on LMS: Exploring Front-End Alternatives
Tiark Rompf
(Purdue University, USA)
Metaprogramming techniques to generate code at runtime in
a general-purpose meta-language
have seen a surge of interest in recent years, driven by the
widening performance gap between high-level languages and emerging
hardware platforms.
In the context of Scala, the LMS (Lightweight Modular Staging)
framework has contributed to ``abstraction without
regret''--high-level programming without performance
penalty--in a number of challenging domains,
through runtime code generation and embedded
compiler pipelines based on stacks of DSLs.
Based on this experience, this paper crystallizes some of the design
decisions of LMS and discusses potential alternatives, which
maintain the underlying spirit but differ in implementation choices:
specifically, strategies for realizing more flexible front-end
embeddings using type classes instead of higher-kinded types,
and strategies for type-safe metaprogramming with untyped
intermediate representations.
@InProceedings{SCALA16p41,
author = {Tiark Rompf},
title = {Reflections on LMS: Exploring Front-End Alternatives},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {41--50},
doi = {},
year = {2016},
}
Implementing Higher-Kinded Types in Dotty
Martin Odersky, Guillaume Martres, and Dmitry Petrashko
(EPFL, Switzerland)
dotty is a new, experimental Scala compiler based on DOT, the calculus of Dependent Object Types. Higher-kinded types are a natural extension of first-order lambda calculus, and have been a core construct of Haskell and Scala. As long as such types are just partial applications of generic classes, they can be given a meaning in DOT relatively straightforwardly. But general lambdas on the type level require extensions of the DOT calculus to be expressible. This paper is an experience report where we describe and discuss four implementation strategies that we have tried out in the last three years. Each strategy was fully implemented in the dotty compiler. We discuss the usability and expressive power of each scheme, and give some indications about the amount of implementation difficulties encountered.
@InProceedings{SCALA16p51,
author = {Martin Odersky and Guillaume Martres and Dmitry Petrashko},
title = {Implementing Higher-Kinded Types in Dotty},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {51--60},
doi = {},
year = {2016},
}
A Generic Algorithm for Checking Exhaustivity of Pattern Matching (Short Paper)
Fengyun Liu
(EPFL, Switzerland)
Algebraic data types and pattern matching are key features of func- tional programming languages. Exhaustivity checking of pattern matching is a safety belt that defends against unmatched excep- tions at runtime and boosts type safety. However, the presence of language features like inheritance, typecase, traits, GADTs, path- dependent types and union types makes the checking difficult and the algorithm complex.
In this paper we propose a generic algorithm that decouples the checking algorithm from specific type theories. The decoupling makes the algorithm simple and enables easy customization for specific type systems.
@InProceedings{SCALA16p61,
author = {Fengyun Liu},
title = {A Generic Algorithm for Checking Exhaustivity of Pattern Matching (Short Paper)},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {61--64},
doi = {},
year = {2016},
}
A Scalable Infrastructure for Teaching Concepts of Programming Languages in Scala with WebLab: An Experience Report
Tim van der Lippe, Thomas Smith, Daniël Pelsmaeker, and
Eelco Visser
(Delft University of Technology, Netherlands)
In this paper, we report on our experience in teaching a course on
concepts of programming languages at TU Delft based on Krishnamurthi's
PAPL book with the definitional interpreter approach using Scala as
meta-language and using the WebLab learning management system. In
particular, we discuss our experience with encoding of definitional
interpreters in Scala using case classes, pattern matching, and
recursive functions; offering this material in the web-based learning
management system WebLab; automated grading and feedback of
interpreter submissions using unit tests; testing tests to force
students to formulate tests, instead of just implementing
interpreters; generation of tests based on a reference implementation
to reduce the effort of producing unit tests; and the construction of
a product line of interpreters in order to maximize reuse and
consistency between reference implementations.
@InProceedings{SCALA16p65,
author = {Tim van der Lippe and Thomas Smith and Daniël Pelsmaeker and Eelco Visser},
title = {A Scalable Infrastructure for Teaching Concepts of Programming Languages in Scala with WebLab: An Experience Report},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {65--74},
doi = {},
year = {2016},
}
SecureScala: Scala Embedding of Secure Computations
Markus Hauck,
Savvas Savvides, Patrick Eugster,
Mira Mezini, and Guido Salvaneschi
(Codecentric, Germany; Purdue University, USA; TU Darmstadt, Germany)
Cloud computing offers an attractive and cost-efficient computing platform and hence it has been widely adopted by the industry and the government. At the same time, cloud computing poses a serious security challenge because sensitive data must often be outsourced to third party entities that can access the data and perform computations on them.
Partial homomorphic encryption is promising for secure computation, since it allows programs to be executed over encrypted data. Despite advances in cryptographic techniques have improved the expressivity of such programs, integration with mainstream languages has seen little progress.
To this end, we present SecureScala, a domain-specific language in Scala that allows expressing secure programs without requiring any cryptographic knowledge. SecureScala is based on a novel combination of free monads and free applicative functors and supports parallel execution and static analyzability. We evaluate our approach through several case studies, demonstrate its expressivity, and show that it incurs in limited performance overhead.
@InProceedings{SCALA16p75,
author = {Markus Hauck and Savvas Savvides and Patrick Eugster and Mira Mezini and Guido Salvaneschi},
title = {SecureScala: Scala Embedding of Secure Computations},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {75--84},
doi = {},
year = {2016},
}
Semantics-Driven Interoperability between Scala.js and JavaScript
Sébastien Doeraene, Tobias Schlatter, and
Nicolas Stucki
(EPFL, Switzerland)
Hundreds of programming languages compile to JavaScript.
Yet, most of them fail, at one level or another, to provide satisfactory interoperability with JavaScript APIs.
This is limiting, as interoperability is at least required to manipulate web pages through the DOM API, but also to use the eco-system of existing JavaScript libraries.
This paper presents the interoperability features of Scala.js, which solves the shortcomings of previous approaches.
Scala.js offers a separate hierarchy of JavaScript types, whose operations have semantics borrowed from ECMAScript 2015.
The interoperability features are complete with respect to ECMAScript 2015, save for two exceptions which are still being worked on.
This allows Scala.js programs to perform any operation that an ECMAScript program could do, thereby guaranteeing that they can talk to any JavaScript library.
@InProceedings{SCALA16p85,
author = {Sébastien Doeraene and Tobias Schlatter and Nicolas Stucki},
title = {Semantics-Driven Interoperability between Scala.js and JavaScript},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {85--94},
doi = {},
year = {2016},
}
Scaps: Type-Directed API Search for Scala
Lukas Wegmann, Farhad Mehta, Peter Sommerlad, and Mirko Stocker
(1plusX, Switzerland; University of Applied Sciences Rapperswil, Switzerland)
Type-directed API search, using queries composed of both keywords and type signatures to retrieve definitions from APIs, are popular in the functional programming community. This search technique allows programmers to easily navigate complex and large APIs in order to find the definitions they are interested in. While there exist some effective approaches to address type-directed API search for functional languages, we observed that none of these have been successfully adapted for use with statically-typed, object-oriented languages. The challenge here is incorporating large and unified inheritance hierarchies and the resulting prevalence of subtyping into an API retrieval model. We describe a new approach to API retrieval and provide an implementation thereof for the Scala language. Our evaluation with queries mined from Q&A websites shows that the model retrieves definitions from the Scala standard library with 94% of the relevant results in the top 10.
@InProceedings{SCALA16p95,
author = {Lukas Wegmann and Farhad Mehta and Peter Sommerlad and Mirko Stocker},
title = {Scaps: Type-Directed API Search for Scala},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {95--104},
doi = {},
year = {2016},
}
Info
Tool Demonstrations
Building a Modular Static Analysis Framework in Scala (Tool Paper)
Quentin Stiévenart, Jens Nicolay,
Wolfgang De Meuter, and Coen De Roover
(Vrije Universiteit Brussel, Belgium)
We present Scala-AM, a framework for implementing static analyses as systematically abstracted abstract machines.
Analyses implemented on top of Scala-AM separate operational semantics from machine abstraction concerns.
This modularity facilitates varying the analyzed language and the applied abstraction method in an analysis.
We describe the design of our framework and demonstrate its use in a static analysis for the DOT calculus.
We conclude with a tour of the features of Scala through which Scala-AM achieves its modularity.
@InProceedings{SCALA16p105,
author = {Quentin Stiévenart and Jens Nicolay and Wolfgang De Meuter and Coen De Roover},
title = {Building a Modular Static Analysis Framework in Scala (Tool Paper)},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {105--109},
doi = {},
year = {2016},
}
The sbt-rats Parser Generator Plugin for Scala (Tool Paper)
Anthony M. Sloane, Franck Cassez, and Scott Buckley
(Macquarie University, Australia)
Tools for creating parsers are a key part of a mature language eco-system. Scala
has traditionally relied on combinator libraries for defining parsers but being
libraries they come with fundamental implementation limitations. An alternative
is to use a Java-based parser generator such as ANTLR or Rats! but these tools
are quite verbose and not ideal to use with Scala code. We describe our
experiences with Scala-focused parser generation that is embodied in our
sbtrats plugin for the Scala Build Tool. At its simplest, sbtrats provides a
bridge to the Rats! parser generator for Java. On top of this bridge, we have a
simple grammar definition notation that incorporates annotations for tree
construction and pretty-printing. As well as generating a Rats! grammar,
sbtrats can optionally generate case class definitions for the tree structure
and a pretty-printer defined using our Kiama language processing library. We
explain the sbtrats grammar notation and describe our positive experiences
using it to define grammars for LLVM assembly notation and the SMTLIB
input/output language for SMT solvers.
@InProceedings{SCALA16p110,
author = {Anthony M. Sloane and Franck Cassez and Scott Buckley},
title = {The sbt-rats Parser Generator Plugin for Scala (Tool Paper)},
booktitle = {Proc.\ SCALA},
publisher = {ACM},
pages = {110--113},
doi = {},
year = {2016},
}
Info
proc time: 0.11