Volume
LIPIcs, Volume 56
30th European Conference on Object-Oriented Programming (ECOOP 2016)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Conference on Object-Oriented Programming (ECOOP)
Event
ECOOP 2016, July 18-22, 2016, Rome, ItalyEditors
Publication Details
- published at: 2016-07-18
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-014-9
- DBLP: db/conf/ecoop/ecoop2016
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 56, ECOOP'16, Complete Volume
Abstract
LIPIcs, Volume 56, ECOOP'16, Complete Volume
Cite as
30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@Proceedings{krishnamurthi_et_al:LIPIcs.ECOOP.2016,
title = {{LIPIcs, Volume 56, ECOOP'16, Complete Volume}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016},
URN = {urn:nbn:de:0030-drops-61391},
doi = {10.4230/LIPIcs.ECOOP.2016},
annote = {Keywords: Programming Techniques, Software Engineering}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, List of Authors
Abstract
Front Matter, Table of Contents, Preface, List of Authors
Cite as
30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{krishnamurthi_et_al:LIPIcs.ECOOP.2016.0,
author = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
title = {{Front Matter, Table of Contents, Preface, List of Authors}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {0:i--0:xiv},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.0},
URN = {urn:nbn:de:0030-drops-60949},
doi = {10.4230/LIPIcs.ECOOP.2016.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, List of Authors}
}
Document
Trace Typing: An Approach for Evaluating Retrofitted Type Systems
Abstract
Recent years have seen growing interest in the retrofitting of
type systems onto dynamically-typed programming languages, in order to improve type safety, programmer productivity, or performance. In such cases, type system developers must strike a delicate balance between disallowing certain coding patterns to keep the type system simple, or including them at the expense of additional complexity and effort. Thus far, the process for designing retrofitted type systems has been largely ad hoc, because evaluating multiple variations of a type system on large bodies of existing code is a significant undertaking.
We present trace typing: a framework for automatically and
quantitatively evaluating variations of a retrofitted type system
on large code bases. The trace typing approach involves gathering
traces of program executions, inferring types for instances of
variables and expressions occurring in a trace, and merging types
according to merge strategies that reflect specific (combinations
of) choices in the source-level type system design space.
We evaluated trace typing through several experiments. We compared several variations of type systems retrofitted onto JavaScript, measuring the number of program locations with type errors in each case on a suite of over fifty thousand lines of JavaScript code. We also used trace typing to validate and guide the design of a new retrofitted type system that enforces fixed object layout for JavaScript objects. Finally, we leveraged the types computed by trace typing to automatically identify tag tests --- dynamic checks that refine a type --- and examined the variety of tests identified.
Cite as
Esben Andreasen, Colin S. Gordon, Satish Chandra, Manu Sridharan, Frank Tip, and Koushik Sen. Trace Typing: An Approach for Evaluating Retrofitted Type Systems. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{andreasen_et_al:LIPIcs.ECOOP.2016.1,
author = {Andreasen, Esben and Gordon, Colin S. and Chandra, Satish and Sridharan, Manu and Tip, Frank and Sen, Koushik},
title = {{Trace Typing: An Approach for Evaluating Retrofitted Type Systems}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {1:1--1:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.1},
URN = {urn:nbn:de:0030-drops-60952},
doi = {10.4230/LIPIcs.ECOOP.2016.1},
annote = {Keywords: Retrofitted type systems, Type system design, trace typing}
}
Document
QL: Object-oriented Queries on Relational Data
Abstract
This paper describes QL, a language for querying complex, potentially recursive data structures. QL compiles to Datalog and runs on a standard relational database, yet it provides familiar-looking object-oriented features such as classes and methods, reinterpreted in logical terms: classes are logical properties describing sets of values, subclassing is implication, and virtual calls are dispatched dynamically by considering the most specific classes containing the receiver. Furthermore, types in QL are prescriptive and actively influence program evaluation rather than just describing it. In combination, these features enable the development of concise queries based on reusable libraries, which are written in a purely declarative style, yet can be efficiently executed even on very large data sets. In particular, we have used QL to implement static analyses for various programming languages, which scale to millions of lines of code.
Cite as
Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer. QL: Object-oriented Queries on Relational Data. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 2:1-2:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{avgustinov_et_al:LIPIcs.ECOOP.2016.2,
author = {Avgustinov, Pavel and de Moor, Oege and Jones, Michael Peyton and Sch\"{a}fer, Max},
title = {{QL: Object-oriented Queries on Relational Data}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {2:1--2:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.2},
URN = {urn:nbn:de:0030-drops-60968},
doi = {10.4230/LIPIcs.ECOOP.2016.2},
annote = {Keywords: Object orientation, Datalog, query languages, prescriptive typing}
}
Document
Fine-grained Language Composition: A Case Study
Abstract
Although run-time language composition is common, it normally takes the form of a crude Foreign Function Interface (FFI). While useful, such compositions tend to be coarse-grained and slow. In this paper we introduce a novel fine-grained syntactic composition of PHP and Python which allows users to embed each language inside the other, including referencing variables across languages.
This composition raises novel design and implementation challenges. We show that good solutions can be found to the design challenges; and that the resulting implementation imposes an acceptable
performance overhead of, at most, 2.6x.
Cite as
Edd Barrett, Carl Friedrich Bolz, Lukas Diekmann, and Laurence Tratt. Fine-grained Language Composition: A Case Study. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 3:1-3:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{barrett_et_al:LIPIcs.ECOOP.2016.3,
author = {Barrett, Edd and Bolz, Carl Friedrich and Diekmann, Lukas and Tratt, Laurence},
title = {{Fine-grained Language Composition: A Case Study}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {3:1--3:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.3},
URN = {urn:nbn:de:0030-drops-60975},
doi = {10.4230/LIPIcs.ECOOP.2016.3},
annote = {Keywords: JIT, tracing, language composition}
}
Document
Making an Embedded DBMS JIT-friendly
Abstract
While database management systems (DBMSs) are highly optimized,
interactions across the boundary between the programming language (PL) and the DBMS are costly, even for in-process embedded DBMSs. In this paper, we show that programs that interact with the popular embedded DBMS SQLite can be significantly optimized -- by a factor of 3.4 in our benchmarks -- by inlining across the PL / DBMS boundary. We achieved this speed-up by replacing parts of SQLite's
C interpreter with RPython code and composing the resulting meta-tracing virtual machine (VM) -- called SQPyte -- with the PyPy VM. SQPyte does not compromise stand-alone SQL performance and is 2.2% faster than SQLite on the widely used TPC-H benchmark suite.
Cite as
Carl Friedrich Bolz, Darya Kurilova, and Laurence Tratt. Making an Embedded DBMS JIT-friendly. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bolz_et_al:LIPIcs.ECOOP.2016.4,
author = {Bolz, Carl Friedrich and Kurilova, Darya and Tratt, Laurence},
title = {{Making an Embedded DBMS JIT-friendly}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {4:1--4:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.4},
URN = {urn:nbn:de:0030-drops-60986},
doi = {10.4230/LIPIcs.ECOOP.2016.4},
annote = {Keywords: DBMSs, JIT, performance, tracing}
}
Document
Reference Capabilities for Concurrency Control
Abstract
The proliferation of shared mutable state in object-oriented
programming complicates software development as two seemingly
unrelated operations may interact via an alias and produce
unexpected results. In concurrent programming this manifests itself as data-races. Concurrent object-oriented programming further suffers from the fact that code that warrants synchronisation cannot easily be distinguished from code that does not. The burden is placed solely on the programmer to reason about alias freedom, sharing across threads and side-effects to deduce where and when to apply concurrency control, without inadvertently blocking parallelism.
This paper presents a reference capability approach to concurrent
and parallel object-oriented programming where all uses of
aliases are guaranteed to be data-race free. The static type of
an alias describes its possible sharing without using explicit
ownership or effect annotations. Type information can express
non-interfering deterministic parallelism without dynamic
concurrency control, thread-locality, lock-based schemes, and
guarded-by relations giving multi-object atomicity to nested data
structures. Unification of capabilities and traits allows
trait-based reuse across multiple concurrency scenarios with
minimal code duplication. The resulting system brings together
features from a wide range of prior work in a unified way.
Cite as
Elias Castegren and Tobias Wrigstad. Reference Capabilities for Concurrency Control. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 5:1-5:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{castegren_et_al:LIPIcs.ECOOP.2016.5,
author = {Castegren, Elias and Wrigstad, Tobias},
title = {{Reference Capabilities for Concurrency Control}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {5:1--5:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.5},
URN = {urn:nbn:de:0030-drops-60998},
doi = {10.4230/LIPIcs.ECOOP.2016.5},
annote = {Keywords: Type systems, Capabilities, Traits, Concurrency, Object-Oriented}
}
Document
A Calculus for Variational Programming
Abstract
Variation is ubiquitous in software. Many applications can benefit from making this variation explicit, then manipulating and computing with it directly---a technique we call "variational programming". This idea has been independently discovered in several application domains, such as efficiently analyzing and verifying software product lines, combining bounded and symbolic model-checking, and computing with alternative privacy profiles. Although these
domains share similar core problems, and there are also many similarities in the solutions, there is no dedicated programming language support for variational programming. This makes the various implementations tedious, prone to errors, hard to maintain and reuse, and difficult to compare.
In this paper we present a calculus that forms the basis of a programming language with explicit support for representing, manipulating, and computing with variation in programs and data. We illustrate how such a language can simplify the implementation of variational programming tasks. We present the syntax and semantics of the core calculus, a sound type system, and a type inference algorithm that produces principal types.
Cite as
Sheng Chen, Martin Erwig, and Eric Walkingshaw. A Calculus for Variational Programming. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 6:1-6:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chen_et_al:LIPIcs.ECOOP.2016.6,
author = {Chen, Sheng and Erwig, Martin and Walkingshaw, Eric},
title = {{A Calculus for Variational Programming}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {6:1--6:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.6},
URN = {urn:nbn:de:0030-drops-61005},
doi = {10.4230/LIPIcs.ECOOP.2016.6},
annote = {Keywords: Variational programming, variational types, variability-aware analyses}
}
Document
Interprocedural Type Specialization of JavaScript Programs Without Type Analysis
Abstract
Previous work proposed lazy basic block versioning, a technique for just-in-time compilation of dynamic languages which we believe represents an interesting point in the design space. Basic block versioning is simple to implement, simple enough that a single developer can build a complete just-in-time compiler for JavaScript in a year, yet it performs surprisingly well as it propagates
context-sensitive type information to generate type-specialized code on the fly.
In this paper, we demonstrate that lazy basic block versioning
can be extended is simple ways to propagate type information across function call boundaries. This gives some of the benefits of whole-program analysis, or a tracing compiler, without having to implement the machinery for either. We have implemented this proposal in the Higgs JavaScript virtual machine and report on the empirical evaluation of this system on a set of industry standard benchmarks. The approach eliminates 94.3 of dynamic type tests on average,
which we show is more than what is achievable with any static whole-program type analysis.
Cite as
Maxime Chevalier-Boisvert and Marc Feeley. Interprocedural Type Specialization of JavaScript Programs Without Type Analysis. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{chevalierboisvert_et_al:LIPIcs.ECOOP.2016.7,
author = {Chevalier-Boisvert, Maxime and Feeley, Marc},
title = {{Interprocedural Type Specialization of JavaScript Programs Without Type Analysis}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {7:1--7:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.7},
URN = {urn:nbn:de:0030-drops-61019},
doi = {10.4230/LIPIcs.ECOOP.2016.7},
annote = {Keywords: Just-In-Time Compilation, Dynamic Language, Optimization, Object Oriented, JavaScript}
}
Document
C++ const and Immutability: An Empirical Study of Writes-Through-const
Abstract
The ability to specify immutability in a programming language is a
powerful tool for developers, enabling them to better understand and
more safely transform their code without fearing unintended changes to program state. The C++ programming language allows developers to
specify a form of immutability using the const keyword. In this work, we characterize the meaning of the C++ const qualifier and present the ConstSanitizer tool, which dynamically verifies a stricter form of immutability than that defined in C++: it identifies const uses that are either not consistent with transitive immutability, that write to mutable fields, or that write to formerly-const objects whose const-ness has been cast away.
We evaluate a set of 7 C++ benchmark programs to find writes-through-const, establish root causes for how they fail to respect our stricter definition of immutability, and assign attributes
to each write (namely: synchronized, not visible, buffer/cache,
delayed initialization, and incorrect). ConstSanitizer finds 17
archetypes for writes in these programs which do not respect our
version of immutability. Over half of these seem unnecessary to us.
Our classification and observations of behaviour in practice
contribute to the understanding of a widely-used C++ language feature.
Cite as
Jon Eyolfson and Patrick Lam. C++ const and Immutability: An Empirical Study of Writes-Through-const. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 8:1-8:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{eyolfson_et_al:LIPIcs.ECOOP.2016.8,
author = {Eyolfson, Jon and Lam, Patrick},
title = {{C++ const and Immutability: An Empirical Study of Writes-Through-const}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {8:1--8:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.8},
URN = {urn:nbn:de:0030-drops-61024},
doi = {10.4230/LIPIcs.ECOOP.2016.8},
annote = {Keywords: empirical study, dynamic analysis, immutability}
}
Document
LJGS: Gradual Security Types for Object-Oriented Languages
Abstract
LJGS is a lightweight Java core calculus with a gradual security type system. The calculus guarantees secure information flow for
sequential, class-based, typed object-oriented programming with
mutable objects and virtual method calls. An LJGS program is
composed of fragments that are checked either statically or
dynamically. Statically checked fragments adhere to a security type
system so that they incur no run-time penalty whereas dynamically
checked fragments rely on run-time security labels. The programmer
marks the boundaries between static and dynamic checking with casts
so that it is always clear whether a program fragment requires
run-time checks. LJGS requires security annotations on fields and
methods. A field annotation either specifies a fixed static
security level or it prescribes dynamic checking. A method
annotation specifies a constrained polymorphic security signature.
The types of local variables in method bodies are analyzed
flow-sensitively and require no annotation. The dynamic checking of
fields relies on a static points-to analysis to approximate implicit
flows. We prove type soundness and non-interference for LJGS.
Cite as
Luminous Fennell and Peter Thiemann. LJGS: Gradual Security Types for Object-Oriented Languages. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 9:1-9:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{fennell_et_al:LIPIcs.ECOOP.2016.9,
author = {Fennell, Luminous and Thiemann, Peter},
title = {{LJGS: Gradual Security Types for Object-Oriented Languages}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {9:1--9:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.9},
URN = {urn:nbn:de:0030-drops-61031},
doi = {10.4230/LIPIcs.ECOOP.2016.9},
annote = {Keywords: gradual typing, security typing, Java, hybrid information flow control}
}
Document
Formal Language Recognition with the Java Type Checker
Abstract
This paper is a theoretical study of a practical problem: the
automatic generation of Java Fluent APIs from their specification. We explain why the problem's core lies with the expressive power of Java generics. Our main result is that automatic generation is possible whenever the specification is an instance of the set of deterministic context-free languages, a set which contains most "practical" languages. Other contributions include a collection of techniques and idioms of the limited meta-programming possible with Java generics, and an empirical measurement demonstrating that the runtime of the "javac" compiler of Java may be exponential in the program's length, even for programs composed of a handful of lines and which do not rely on overly complex use of generics.
Cite as
Yossi Gil and Tomer Levy. Formal Language Recognition with the Java Type Checker. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 10:1-10:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{gil_et_al:LIPIcs.ECOOP.2016.10,
author = {Gil, Yossi and Levy, Tomer},
title = {{Formal Language Recognition with the Java Type Checker}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {10:1--10:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.10},
URN = {urn:nbn:de:0030-drops-61042},
doi = {10.4230/LIPIcs.ECOOP.2016.10},
annote = {Keywords: Parser Generators, Generic Programming, Fluent API}
}
Document
IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs
Abstract
Derived values are values calculated from base values. They can be
expressed in object-oriented languages by means of getters calculating the derived value, and in relational or logic databases by means of (materialized) views. However, switching to a different calculation strategy (for example caching) in object-oriented programming requires invasive code changes, and the databases limit expressiveness by disallowing recursive aggregation.
In this paper, we present IceDust, a data modeling language for
expressing derived attribute values without committing to a calculation strategy. IceDust provides three strategies for calculating derived values in persistent object graphs: Calculate-on-Read, Calculate-on-Write, and Calculate-Eventually. We have developed a path-based abstract interpretation that provides static dependency analysis to generate code for these strategies. Benchmarks show that different strategies perform better in different scenarios. In addition we have conducted a case study that suggests that derived value calculations of systems used in practice can be expressed in IceDust.
Cite as
Daco C. Harkes, Danny M. Groenewegen, and Eelco Visser. IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 11:1-11:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{harkes_et_al:LIPIcs.ECOOP.2016.11,
author = {Harkes, Daco C. and Groenewegen, Danny M. and Visser, Eelco},
title = {{IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {11:1--11:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.11},
URN = {urn:nbn:de:0030-drops-61059},
doi = {10.4230/LIPIcs.ECOOP.2016.11},
annote = {Keywords: Incremental Computing, Data Modeling, Domain Specific Language}
}
Document
Magic with Dynamo -- Flexible Cross-Component Linking for Java with Invokedynamic
Abstract
Modern software systems are not built from scratch. They use functionality provided by libraries. These libraries evolve and often upgrades are deployed without the systems being recompiled.
In Java, this process is particularly error-prone due to the mismatch between source and binary compatibility,
and the lack of API stability in many popular libraries.
We propose a novel approach to mitigate this problem based on the use of invokedynamic instructions for cross-component method invocations. The dispatch mechanism of invokedynamic is used to provide on-the-fly signature adaptation. We show how this idea can be used to construct a Java compiler that produces more resilient bytecode.
We present the dynamo compiler, a proof-of-concept implemented as a javac post compiler. We evaluate our approach using several benchmark examples and two case studies showing how the dynamo compiler can prevent certain types of linkage and stack overflow errors that have been observed in real-world systems.
Cite as
Kamil Jezek and Jens Dietrich. Magic with Dynamo -- Flexible Cross-Component Linking for Java with Invokedynamic. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 12:1-12:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{jezek_et_al:LIPIcs.ECOOP.2016.12,
author = {Jezek, Kamil and Dietrich, Jens},
title = {{Magic with Dynamo -- Flexible Cross-Component Linking for Java with Invokedynamic}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {12:1--12:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.12},
URN = {urn:nbn:de:0030-drops-61068},
doi = {10.4230/LIPIcs.ECOOP.2016.12},
annote = {Keywords: Java, compilation, linking, binary compatibility, invokedynamic}
}
Document
Object Inheritance Without Classes
Abstract
Which comes first: the object or the class? Language designers enjoy
the conceptual simplicity of object-based languages (such as Emerald
or Self) while many programmers prefer the pragmatic utility of
classical inheritance (as in Simula and Java). Programmers in
object-based languages have a tendency to build libraries to support
traditional inheritance, and language implementations are often
contorted to the same end. In this paper, we revisit the relationship
between classes and objects. We model various kinds of inheritance in
the context of an object-oriented language whose objects are not
defined by classes, and explain why class inheritance and
initialisation cannot be easily modelled purely by delegation.
Cite as
Timothy Jones, Michael Homer, James Noble, and Kim Bruce. Object Inheritance Without Classes. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 13:1-13:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{jones_et_al:LIPIcs.ECOOP.2016.13,
author = {Jones, Timothy and Homer, Michael and Noble, James and Bruce, Kim},
title = {{Object Inheritance Without Classes}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {13:1--13:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.13},
URN = {urn:nbn:de:0030-drops-61077},
doi = {10.4230/LIPIcs.ECOOP.2016.13},
annote = {Keywords: Inheritance, Objects, Classes, Operational semantics}
}
Document
One Way to Select Many
Abstract
Selecting items from a collection is one of the most common tasks
users perform with graphical user interfaces. Practically every
application supports this task with a selection feature different
from that of any other application. Defects are common,
especially in manipulating selections of non-adjacent elements,
and flexible selection features are often missing when they would
clearly be useful. As a consequence, user effort is wasted. The
loss of productivity is experienced in small doses, but all
computer users are impacted. The undesirable state of support
for multi-element selection prevails because the same selection
features are redesigned and reimplemented repeatedly. This
article seeks to establish common abstractions for
multi-selection. It gives generic but precise meanings to
selection operations and makes multi-selection reusable; a
JavaScript implementation is described. Application vendors
benefit because of reduced development effort. Users benefit
because correct and consistent multi-selection becomes available
in more contexts.
Cite as
Jaakko Järvi and Sean Parent. One Way to Select Many. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 14:1-14:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{jarvi_et_al:LIPIcs.ECOOP.2016.14,
author = {J\"{a}rvi, Jaakko and Parent, Sean},
title = {{One Way to Select Many}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {14:1--14:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.14},
URN = {urn:nbn:de:0030-drops-61080},
doi = {10.4230/LIPIcs.ECOOP.2016.14},
annote = {Keywords: User interfaces, Multi-selection, JavaScript}
}
Document
Program Tailoring: Slicing by Sequential Criteria
Abstract
Protocol and typestate analyses often report some sequences of
statements ending at a program point P that needs to be
scrutinized, since P may be erroneous or imprecisely
analyzed. Program slicing focuses only on the behavior at P by
computing a slice of the program affecting the values at P. In
this paper, we propose to restrict our attention to the subset of
that behavior at P affected by one or several statement
sequences, called a sequential criterion (SC). By leveraging the
ordering information in a SC, e.g., the temporal order in a few
valid/invalid API method invocation sequences, we introduce a
new technique, program tailoring, to compute a tailored program
that comprises the statements in all possible execution paths
passing through at least one sequence in SC in the given
order. With a prototyping implementation, Tailor, we show why
tailoring is practically useful by conducting two case studies on
seven large real-world Java applications. For program
debugging and understanding, Tailor can complement program
slicing by removing SC-irrelevant statements. For program
analysis, Tailor can enable a pointer analysis, which is
unscalable to a program, to perform a more focused and therefore
potentially scalable analysis to its specific parts containing
hard language features such as reflection.
Cite as
Yue Li, Tian Tan, Yifei Zhang, and Jingling Xue. Program Tailoring: Slicing by Sequential Criteria. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 15:1-15:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{li_et_al:LIPIcs.ECOOP.2016.15,
author = {Li, Yue and Tan, Tian and Zhang, Yifei and Xue, Jingling},
title = {{Program Tailoring: Slicing by Sequential Criteria}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {15:1--15:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.15},
URN = {urn:nbn:de:0030-drops-61092},
doi = {10.4230/LIPIcs.ECOOP.2016.15},
annote = {Keywords: Program Slicing, Program Analysis, API Protocol Analysis}
}
Document
Composing Interfering Abstract Protocols
Abstract
The undisciplined use of shared mutable state can be a source of program errors when aliases unsafely interfere with each other.
While protocol-based techniques to reason about interference abound, they do not address two practical concerns: the decidability of protocol composition and its integration with protocol abstraction.
We show that our composition procedure is decidable and that it ensures safe interference even when composing abstract protocols.
To evaluate the expressiveness of our protocol framework for safe shared memory interference, we show how this same protocol framework can be used to model safe, typeful message-passing concurrency idioms.
Cite as
Filipe Militão, Jonathan Aldrich, and Luís Caires. Composing Interfering Abstract Protocols. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{militao_et_al:LIPIcs.ECOOP.2016.16,
author = {Milit\~{a}o, Filipe and Aldrich, Jonathan and Caires, Lu{\'\i}s},
title = {{Composing Interfering Abstract Protocols}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {16:1--16:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.16},
URN = {urn:nbn:de:0030-drops-61108},
doi = {10.4230/LIPIcs.ECOOP.2016.16},
annote = {Keywords: shared memory interference, protocol composition, aliasing, linearity}
}
Document
The Elements of Decision Alignment
Abstract
When one object makes a request of another, why do we expect that
the second object's behavior correctly satisfies the first object's
wishes? The need to cope with such principal-agent problems
shapes programming practice as much as it shapes human organizations
and economies. However, the literature about such plan coordination
issues among humans is almost disjoint from the literature about
these issues among objects. Even the terms used are unrelated.
These fields have much to learn from each other---both from their
similarities and from the causes of their differences. We propose a
framework for thinking about decision alignment as a bridge
between these disciplines.
Cite as
Mark S. Miller and Bill Tulloh. The Elements of Decision Alignment. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 17:1-17:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{miller_et_al:LIPIcs.ECOOP.2016.17,
author = {Miller, Mark S. and Tulloh, Bill},
title = {{The Elements of Decision Alignment}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {17:1--17:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.17},
URN = {urn:nbn:de:0030-drops-61111},
doi = {10.4230/LIPIcs.ECOOP.2016.17},
annote = {Keywords: economics, law, contracts, principal-agent problem, incentive alignment, least authority, verification}
}
Document
A Calculus with Partially Dynamic Records for Typeful Manipulation of JSON Objects
Abstract
This paper investigates language constructs for high-level and
type-safe manipulation of JSON objects in a typed functional language. A major obstacle in representing JSON in a static type system is their heterogeneous nature: in most practical JSON APIs, a JSON array is a heterogeneous list consisting of, for example, objects having common fields and possibly some optional fields. This paper presents a typed calculus that reconciles static typing constraints and heterogeneous JSON arrays based on the idea of partially dynamic records originally proposed and sketched by Buneman and Ohori for complex database object manipulation. Partially dynamic records are dynamically typed records, but some parts of their structures are statically known. This feature enables us to represent JSON objects as typed data structures. The proposed calculus smoothly extends with ML-style pattern matching and record polymorphism. These results yield a typed functional language where the programmer can directly import JSON data as terms having static types, and can manipulate them with the full
benefits of static polymorphic type-checking. The proposed calculus
has been embodied in SML#, an extension of Standard ML with record
polymorphism and other practically useful features. This paper also
reports on the details of the implementation and demonstrates its
feasibility through examples using actual Web APIs. The SML# version 3.1.0 compiler includes JSON support presented in this paper, and is available from Tohoku University as open-source software under a BSD-style license.
Cite as
Atsushi Ohori, Katsuhiro Ueno, Tomohiro Sasaki, and Daisuke Kikuchi. A Calculus with Partially Dynamic Records for Typeful Manipulation of JSON Objects. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 18:1-18:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{ohori_et_al:LIPIcs.ECOOP.2016.18,
author = {Ohori, Atsushi and Ueno, Katsuhiro and Sasaki, Tomohiro and Kikuchi, Daisuke},
title = {{A Calculus with Partially Dynamic Records for Typeful Manipulation of JSON Objects}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {18:1--18:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.18},
URN = {urn:nbn:de:0030-drops-61128},
doi = {10.4230/LIPIcs.ECOOP.2016.18},
annote = {Keywords: JSON, Type System, Polymorphic Record Calculus}
}
Document
Higher-Order Demand-Driven Program Analysis
Abstract
We explore a novel approach to higher-order program analysis that brings ideas of on-demand lookup from first-order CFL-reachability program analyses to higher-order programs. The analysis needs to produce only a control-flow graph; it can derive all other information including values of variables directly from the graph. Several challenges had to be overcome, including how to build the control-flow graph on-the-fly and how to deal with non-local variables in functions. The resulting analysis is flow- and context-sensitive with a provable polynomial-time bound. The analysis is formalized and proved correct and terminating, and an initial implementation is described.
Cite as
Zachary Palmer and Scott F. Smith. Higher-Order Demand-Driven Program Analysis. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 19:1-19:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{palmer_et_al:LIPIcs.ECOOP.2016.19,
author = {Palmer, Zachary and Smith, Scott F.},
title = {{Higher-Order Demand-Driven Program Analysis}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {19:1--19:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.19},
URN = {urn:nbn:de:0030-drops-61132},
doi = {10.4230/LIPIcs.ECOOP.2016.19},
annote = {Keywords: functional programming, program analysis, polynomial-time, demand-driven, flow-sensitive, context-sensitive}
}
Document
Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics
Abstract
Semantic specifications do not make a systematic connection between the names and scopes in the static structure of a program and memory layout, and access during its execution. In this paper, we introduce a systematic approach to the alignment of names in static semantics and memory in dynamic semantics, building on the scope graph framework for name resolution. We develop a uniform memory model consisting of frames that instantiate the scopes in the scope graph of a program. This provides a language-independent correspondence between static scopes and run-time memory layout, and between static resolution paths and run-time memory access paths. The approach scales to a range of binding features, supports straightforward type soundness proofs, and provides the basis for a language-independent specification of sound reachability-based garbage collection.
Cite as
Casper Bach Poulsen, Pierre Néron, Andrew Tolmach, and Eelco Visser. Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 20:1-20:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{bachpoulsen_et_al:LIPIcs.ECOOP.2016.20,
author = {Bach Poulsen, Casper and N\'{e}ron, Pierre and Tolmach, Andrew and Visser, Eelco},
title = {{Scopes Describe Frames: A Uniform Model for Memory Layout in Dynamic Semantics}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {20:1--20:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.20},
URN = {urn:nbn:de:0030-drops-61140},
doi = {10.4230/LIPIcs.ECOOP.2016.20},
annote = {Keywords: Dynamic semantics, scope graphs, memory layout, type soundness, operational semantics}
}
Document
Lightweight Session Programming in Scala
Abstract
Designing, developing and maintaining concurrent applications is an
error-prone and time-consuming task; most difficulties arise because
compilers are usually unable to check whether the inputs/outputs
performed by a program at runtime will adhere to a given protocol
specification. To address this problem, we propose lightweight session programming in Scala: we leverage the native features of the Scala
type system and standard library, to introduce (1) a representation of session types as Scala types, and (2) a library, called lchannels, with a convenient API for session-based programming, supporting local and distributed communication. We generalise the idea of Continuation-Passing Style Protocols (CPSPs), studying their formal relationship with session types. We illustrate how session programming can be carried over in Scala: how to formalise a communication protocol, and represent it using Scala classes and lchannels, letting the compiler help spotting protocol violations. We attest the practicality of our approach with a complex use case, and evaluate the performance of lchannels with a series of benchmarks.
Cite as
Alceste Scalas and Nobuko Yoshida. Lightweight Session Programming in Scala. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 21:1-21:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{scalas_et_al:LIPIcs.ECOOP.2016.21,
author = {Scalas, Alceste and Yoshida, Nobuko},
title = {{Lightweight Session Programming in Scala}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {21:1--21:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.21},
URN = {urn:nbn:de:0030-drops-61156},
doi = {10.4230/LIPIcs.ECOOP.2016.21},
annote = {Keywords: session types, Scala, concurrency}
}
Document
Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java
Abstract
Many current program analyses require highly precise pointer
information about small, tar- geted parts of a given program. This
motivates the need for demand-driven pointer analyses that compute
information only where required. Pointer analyses generally compute
points-to sets of program variables or answer boolean alias
queries. However, many client analyses require richer pointer
information. For example, taint and typestate analyses often need to
know the set of all aliases of a given variable under a certain
calling context. With most current pointer analyses, clients must
compute such information through repeated points-to or alias queries, increasing complexity and computation time for them.
This paper presents Boomerang, a demand-driven, flow-, field-, and
context-sensitive pointer analysis for Java programs. Boomerang
computes rich results that include both the possible allocation sites of a given pointer (points-to information) and all pointers that can point to those allocation sites (alias information). For increased precision and scalability, clients can query Boomerang with respect to particular calling contexts of interest.
Our experiments show that Boomerang is more precise than existing
demand-driven pointer analyses. Additionally, using Boomerang, the
taint analysis FlowDroid issues up to 29.4x fewer pointer queries
compared to using other pointer analyses that return simpler pointer
infor- mation. Furthermore, the search space of Boomerang can be
significantly reduced by requesting calling contexts from the client
analysis.
Cite as
Johannes Späth, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 22:1-22:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{spath_et_al:LIPIcs.ECOOP.2016.22,
author = {Sp\"{a}th, Johannes and Nguyen Quang Do, Lisa and Ali, Karim and Bodden, Eric},
title = {{Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {22:1--22:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.22},
URN = {urn:nbn:de:0030-drops-61164},
doi = {10.4230/LIPIcs.ECOOP.2016.22},
annote = {Keywords: Demand-Driven; Static Analysis; IFDS; Aliasing; Points-to Analysis}
}
Document
Transactional Tasks: Parallelism in Software Transactions
Abstract
Many programming languages, such as Clojure, Scala, and Haskell, support different concurrency models.
In practice these models are often combined, however the semantics of the combinations are not always well-defined.
In this paper, we study the combination of futures and Software Transactional Memory.
Currently, futures created within a transaction cannot access the transactional state safely, violating the serializability of the transactions and leading to undesired behavior.
We define transactional tasks: a construct that allows futures to be created in transactions.
Transactional tasks allow the parallelism in a transaction to be exploited, while providing safe access to the state of their encapsulating transaction.
We show that transactional tasks have several useful properties: they are coordinated, they maintain serializability, and they do not introduce non-determinism.
As such, transactional tasks combine futures and Software Transactional Memory, allowing the potential parallelism of a program to be fully exploited, while preserving the properties of the separate models where possible.
Cite as
Janwillem Swalens, Joeri De Koster, and Wolfgang De Meuter. Transactional Tasks: Parallelism in Software Transactions. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{swalens_et_al:LIPIcs.ECOOP.2016.23,
author = {Swalens, Janwillem and De Koster, Joeri and De Meuter, Wolfgang},
title = {{Transactional Tasks: Parallelism in Software Transactions}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {23:1--23:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.23},
URN = {urn:nbn:de:0030-drops-61173},
doi = {10.4230/LIPIcs.ECOOP.2016.23},
annote = {Keywords: Concurrency, Parallelism, Futures, Threads, Fork/Join, Software Transactional Memory}
}
Document
Staccato: A Bug Finder for Dynamic Configuration Updates
Abstract
Modern software applications are highly configurable, allowing
configuration options to be changed even during program
execution. When dynamic configuration updating is implemented
incorrectly, program errors can result. These program errors occur
primarily when stale data—computed from old configurations—or
inconsistent data—computed from different configurations—are used. We introduce Staccato, the first tool designed to detect these
errors. Staccato uses a dynamic analysis in the style of taint
analysis to find the use of stale configuration data in Java
programs. It supports concurrent programs running on commodity
JVMs. In some cases, Staccato can provide automatic bug avoidance and semi-automatic repair when errors occur.
We evaluated Staccato on 3 open-source applications that support
complex reconfigurability. Staccato found multiple errors in all of
them. Staccato requires only modest annotation overhead and has
moderate performance overhead.
Cite as
John Toman and Dan Grossman. Staccato: A Bug Finder for Dynamic Configuration Updates. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 24:1-24:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{toman_et_al:LIPIcs.ECOOP.2016.24,
author = {Toman, John and Grossman, Dan},
title = {{Staccato: A Bug Finder for Dynamic Configuration Updates}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {24:1--24:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.24},
URN = {urn:nbn:de:0030-drops-61185},
doi = {10.4230/LIPIcs.ECOOP.2016.24},
annote = {Keywords: Dynamic Configuration Updates, Dynamic Analysis, Software configuration}
}
Document
Transforming Programs between APIs with Many-to-Many Mappings
Abstract
Transforming programs between two APIs or different versions of
the same API is a common software engineering task. However,
existing languages supporting for such transformation cannot
satisfactorily handle the cases when the relations between
elements in the old API and the new API are many-to-many
mappings: multiple invocations to the old API are supposed to be
replaced by multiple invocations to the new API. Since the
multiple invocations of the original APIs may not appear
consecutively and the variables in these calls may have different
names, writing a tool correctly to cover all such invocation
cases is not an easy task. In this paper we propose a novel
guided-normalization approach to address this problem. Our core
insight is that programs in different forms can be
semantics-equivalently normalized into a basic form guided by
transformation goals, and developers only need to write rules for
the basic form to address the transformation. Based on this
approach, we design a declarative program transformation
language, PATL, for adapting Java programs between different
APIs. PATL has simple syntax and basic semantics to handle
transformations only considering consecutive statements inside
basic blocks, while with guided-normalization, it can be extended
to handle complex forms of invocations. Furthermore, PATL ensures
that the user-written rules would not accidentally break def-use
relations in the program. We formalize the semantics of PATL on
Middleweight Java and prove the semantics-preserving property of
guided-normalization. We also evaluated our language with three
non-trivial case studies: i.e. updating Google Calendar API,
switching from JDom to Dom4j, and switching from Swing to
SWT. The result is encouraging; it shows that our language allows
successful transformations of real world programs with a small
number of rules and little manual resolution.
Cite as
Chenglong Wang, Jiajun Jiang, Jun Li, Yingfei Xiong, Xiangyu Luo, Lu Zhang, and Zhenjiang Hu. Transforming Programs between APIs with Many-to-Many Mappings. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 25:1-25:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{wang_et_al:LIPIcs.ECOOP.2016.25,
author = {Wang, Chenglong and Jiang, Jiajun and Li, Jun and Xiong, Yingfei and Luo, Xiangyu and Zhang, Lu and Hu, Zhenjiang},
title = {{Transforming Programs between APIs with Many-to-Many Mappings}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {25:1--25:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.25},
URN = {urn:nbn:de:0030-drops-61195},
doi = {10.4230/LIPIcs.ECOOP.2016.25},
annote = {Keywords: Program transformation, API migration}
}
Document
Towards Ontology-Based Program Analysis
Abstract
Program analysis is fundamental for program optimizations, debugging,
and many other tasks. But developing program analyses has been a
challenging and error-prone process for general users. Declarative
program analysis has shown the promise to dramatically improve the
productivity in the development of program analyses. Current
declarative program analysis is however subject to some major
limitations in supporting cooperations among analysis tools, guiding
program optimizations, and often requires much effort for repeated
program preprocessing.
In this work, we advocate the integration of ontology into declarative
program analysis. As a way to standardize the definitions of concepts
in a domain and the representation of the knowledge in the domain,
ontology offers a promising way to address the limitations of current
declarative program analysis. We develop a prototype framework named
PATO for conducting program analysis upon ontology-based program
representation. Experiments on six program analyses confirm the
potential of ontology for complementing existing declarative program
analysis. It supports multiple analyses without separate program
preprocessing, promotes cooperative Liveness analysis between two
compilers, and effectively guides a data placement optimization for
Graphic Processing Units (GPU).
Cite as
Yue Zhao, Guoyang Chen, Chunhua Liao, and Xipeng Shen. Towards Ontology-Based Program Analysis. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 26:1-26:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
Copy BibTex To Clipboard
@InProceedings{zhao_et_al:LIPIcs.ECOOP.2016.26,
author = {Zhao, Yue and Chen, Guoyang and Liao, Chunhua and Shen, Xipeng},
title = {{Towards Ontology-Based Program Analysis}},
booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)},
pages = {26:1--26:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-014-9},
ISSN = {1868-8969},
year = {2016},
volume = {56},
editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.26},
URN = {urn:nbn:de:0030-drops-61201},
doi = {10.4230/LIPIcs.ECOOP.2016.26},
annote = {Keywords: ontology, compiler, program analysis}
}