DLS 2016 – Author Index |
Contents -
Abstracts -
Authors
|
| Byrd, William E. |
DLS '16: "A Small Embedding of Logic ..."
A Small Embedding of Logic Programming with a Simple Complete Search
Jason Hemann, Daniel P. Friedman, William E. Byrd, and Matthew Might (Indiana University, USA; University of Utah, USA) We present a straightforward, call-by-value embedding of a small logic programming language with a simple complete search. We construct the entire language in 54 lines of Racket---half of which implement unification. We then layer over it, in 43 lines, a reconstruction of an existing logic programming language, miniKanren, and attest to our implementation's pedagogical value. Evidence suggests our combination of expressiveness, concision, and elegance is compelling: since microKanren's release, it has spawned over 50 embeddings in over two dozen host languages, including Go, Haskell, Prolog and Smalltalk. 
@InProceedings{DLS16p96,
author = {Jason Hemann and Daniel P. Friedman and William E. Byrd and Matthew Might},
title = {A Small Embedding of Logic Programming with a Simple Complete Search},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {96--107},
doi = {},
year = {2016},
}
 Info
|
|
| Chari, Guido |
DLS '16: "Building Efficient and Highly ..."
Building Efficient and Highly Run-Time Adaptable Virtual Machines
Guido Chari, Diego Garbervetsky, and Stefan Marr (University of Buenos Aires, Argentina; CONICET, Argentina; JKU Linz, Austria) Programming language virtual machines (VMs) realize language semantics, enforce security properties, and execute applications efficiently. Fully Reflective Execution Environments (EEs) are VMs that additionally expose their whole structure and behavior to applications. This enables develop- ers to observe and adapt VMs at run time. However, there is a belief that reflective EEs are not viable for practical usages because such flexibility would incur a high performance overhead. To refute this belief, we built a reflective EE on top of a highly optimizing dynamic compiler. We introduced a new optimization model that, based on the conjecture that variability of low-level (EE-level) reflective behavior is low in many scenarios, mitigates the most significant sources of the performance overheads related to the reflective capabilities in the EE. Our experiments indicate that reflective EEs can reach peak performance in the order of standard VMs. Concretely, that a) if reflective mechanisms are not used the execution overhead is negligible compared to standard VMs, b) VM operations can be redefined at language-level without incurring in significant overheads, c) for several software adaptation tasks, applying the reflection at the VM level is not only lightweight in terms of engineering effort, but also competitive in terms of performance in comparison to other ad-hoc solutions.
@InProceedings{DLS16p60,
author = {Guido Chari and Diego Garbervetsky and Stefan Marr},
title = {Building Efficient and Highly Run-Time Adaptable Virtual Machines},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {60--71},
doi = {},
year = {2016},
}
|
|
| Daloze, Benoit |
DLS '16: "Cross-Language Compiler Benchmarking: ..."
Cross-Language Compiler Benchmarking: Are We Fast Yet?
Stefan Marr, Benoit Daloze, and Hanspeter Mössenböck (JKU Linz, Austria) Comparing the performance of programming languages is difficult because they differ in many aspects including preferred programming abstractions, available frameworks, and their runtime systems. Nonetheless, the question about relative performance comes up repeatedly in the research community, industry, and wider audience of enthusiasts. This paper presents 14 benchmarks and a novel methodology to assess the compiler effectiveness across language implementations. Using a set of common language abstractions, the benchmarks are implemented in Java, JavaScript, Ruby, Crystal, Newspeak, and Smalltalk. We show that the benchmarks exhibit a wide range of characteristics using language-agnostic metrics. Using four different languages on top of the same compiler, we show that the benchmarks perform similarly and therefore allow for a comparison of compiler effectiveness across languages. Based on anecdotes, we argue that these benchmarks help language implementers to identify performance bugs and optimization potential by comparing to other language implementations.
@InProceedings{DLS16p120,
author = {Stefan Marr and Benoit Daloze and Hanspeter Mössenböck},
title = {Cross-Language Compiler Benchmarking: Are We Fast Yet?},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {120--131},
doi = {},
year = {2016},
}
Info
|
|
| De Meuter, Wolfgang |
DLS '16: "Just-in-Time Inheritance: ..."
Just-in-Time Inheritance: A Dynamic and Implicit Multiple Inheritance Mechanism
Mattias De Wael, Janwillem Swalens, and Wolfgang De Meuter (Vrije Universiteit Brussel, Belgium) Multiple inheritance is often criticised for the ambiguity that arises when multiple parents want to pass on a feature with the same name to their offspring. A survey of programming languages reveals that no programming language has an inherently implicit and dynamic approach to resolve this ambiguity. This paper identifies just-in-time inheritance as the first implicit and dynamic inheritance mechanism. The key idea of just-in-time inheritance is that one of the parents is favoured over the others, which resolves the ambiguity, and that the favoured parent can change at runtime. However, just-in-time inheritance is not the silver bullet to solve all ambiguity problems heir to multiple inheritance, because it is not applicable in all scenarios. We conclude that the applicability of just-in-time inheritance is to be found in systems where multiple inheritance is used to model an ``is-a OR is-a''-relation, rather than the more traditional ``is-a AND is-a''-relation.
@InProceedings{DLS16p37,
author = {Mattias De Wael and Janwillem Swalens and Wolfgang De Meuter},
title = {Just-in-Time Inheritance: A Dynamic and Implicit Multiple Inheritance Mechanism},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {37--47},
doi = {},
year = {2016},
}
|
|
| De Wael, Mattias |
DLS '16: "Just-in-Time Inheritance: ..."
Just-in-Time Inheritance: A Dynamic and Implicit Multiple Inheritance Mechanism
Mattias De Wael, Janwillem Swalens, and Wolfgang De Meuter (Vrije Universiteit Brussel, Belgium) Multiple inheritance is often criticised for the ambiguity that arises when multiple parents want to pass on a feature with the same name to their offspring. A survey of programming languages reveals that no programming language has an inherently implicit and dynamic approach to resolve this ambiguity. This paper identifies just-in-time inheritance as the first implicit and dynamic inheritance mechanism. The key idea of just-in-time inheritance is that one of the parents is favoured over the others, which resolves the ambiguity, and that the favoured parent can change at runtime. However, just-in-time inheritance is not the silver bullet to solve all ambiguity problems heir to multiple inheritance, because it is not applicable in all scenarios. We conclude that the applicability of just-in-time inheritance is to be found in systems where multiple inheritance is used to model an ``is-a OR is-a''-relation, rather than the more traditional ``is-a AND is-a''-relation.
@InProceedings{DLS16p37,
author = {Mattias De Wael and Janwillem Swalens and Wolfgang De Meuter},
title = {Just-in-Time Inheritance: A Dynamic and Implicit Multiple Inheritance Mechanism},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {37--47},
doi = {},
year = {2016},
}
|
|
| Dubroy, Patrick |
DLS '16: "Modular Semantic Actions ..."
Modular Semantic Actions
Alessandro Warth, Patrick Dubroy, and Tony Garnock-Jones (Y Combinator Research, USA; Northeastern University, USA) Parser generators give programmers a convenient and declarative way to write parsers and other language-processing applications, but their mechanisms for extension and code reuse often leave something to be desired. We introduce Ohm, a parser generator in which both grammars and their interpretations can be extended in safe and modular ways. Unlike many similar tools, Ohm completely separates grammars and semantic actions, avoiding the problems that arise when these two concerns are mixed. This paper describes the particular way in which Ohm achieves this separation, and discusses the resulting benefits to modularity and extensibility.
@InProceedings{DLS16p108,
author = {Alessandro Warth and Patrick Dubroy and Tony Garnock-Jones},
title = {Modular Semantic Actions},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {108--119},
doi = {},
year = {2016},
}
Info
|
|
| Foley-Bourgon, Vincent |
DLS '16: "Efficiently Implementing the ..."
Efficiently Implementing the Copy Semantics of MATLAB's Arrays in JavaScript
Vincent Foley-Bourgon and Laurie Hendren (McGill University, Canada) Compiling MATLAB---a dynamic, array-based language---to JavaScript is an attractive proposal: the output code can be deployed on a platform used by billions and can leverage the countless hours that have gone into making JavaScript JIT engines fast. But before that can happen, the original MATLAB code must be properly translated, making sure to bridge the semantic gaps of the two languages. An important area where MATLAB and JavaScript differ is in their handling of arrays: for example, in MATLAB, arrays are one-indexed and writing at an index beyond the end of an array extends it; in JavaScript, typed arrays are zero-indexed and writing out of bounds is a no-op. A MATLAB-to-JavaScript compiler must address these mismatches. Another salient and pervasive difference between the two languages is the assignment of arrays to variables: in MATLAB, this operation has value semantics, while in JavaScript is has reference semantics. In this paper, we present MatJuice --- a source-to-source, ahead-of-time compiler back-end for MATLAB --- and how it deals efficiently with this last issue. We present an intra-procedural data-flow analysis to track where each array variable may point to and which variables are possibly aliased. We also present the associated copy insertion transformation that uses the points-to information to insert explicit copies when necessary. The resulting JavaScript program respects the MATLAB value semantics and we show that it performs fewer run-time copies than some alternative approaches.
@InProceedings{DLS16p72,
author = {Vincent Foley-Bourgon and Laurie Hendren},
title = {Efficiently Implementing the Copy Semantics of MATLAB's Arrays in JavaScript},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {72--83},
doi = {},
year = {2016},
}
|
|
| Friedman, Daniel P. |
DLS '16: "A Small Embedding of Logic ..."
A Small Embedding of Logic Programming with a Simple Complete Search
Jason Hemann, Daniel P. Friedman, William E. Byrd, and Matthew Might (Indiana University, USA; University of Utah, USA) We present a straightforward, call-by-value embedding of a small logic programming language with a simple complete search. We construct the entire language in 54 lines of Racket---half of which implement unification. We then layer over it, in 43 lines, a reconstruction of an existing logic programming language, miniKanren, and attest to our implementation's pedagogical value. Evidence suggests our combination of expressiveness, concision, and elegance is compelling: since microKanren's release, it has spawned over 50 embeddings in over two dozen host languages, including Go, Haskell, Prolog and Smalltalk.
@InProceedings{DLS16p96,
author = {Jason Hemann and Daniel P. Friedman and William E. Byrd and Matthew Might},
title = {A Small Embedding of Logic Programming with a Simple Complete Search},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {96--107},
doi = {},
year = {2016},
}
Info
|
|
| Garbervetsky, Diego |
DLS '16: "Building Efficient and Highly ..."
Building Efficient and Highly Run-Time Adaptable Virtual Machines
Guido Chari, Diego Garbervetsky, and Stefan Marr (University of Buenos Aires, Argentina; CONICET, Argentina; JKU Linz, Austria) Programming language virtual machines (VMs) realize language semantics, enforce security properties, and execute applications efficiently. Fully Reflective Execution Environments (EEs) are VMs that additionally expose their whole structure and behavior to applications. This enables develop- ers to observe and adapt VMs at run time. However, there is a belief that reflective EEs are not viable for practical usages because such flexibility would incur a high performance overhead. To refute this belief, we built a reflective EE on top of a highly optimizing dynamic compiler. We introduced a new optimization model that, based on the conjecture that variability of low-level (EE-level) reflective behavior is low in many scenarios, mitigates the most significant sources of the performance overheads related to the reflective capabilities in the EE. Our experiments indicate that reflective EEs can reach peak performance in the order of standard VMs. Concretely, that a) if reflective mechanisms are not used the execution overhead is negligible compared to standard VMs, b) VM operations can be redefined at language-level without incurring in significant overheads, c) for several software adaptation tasks, applying the reflection at the VM level is not only lightweight in terms of engineering effort, but also competitive in terms of performance in comparison to other ad-hoc solutions.
@InProceedings{DLS16p60,
author = {Guido Chari and Diego Garbervetsky and Stefan Marr},
title = {Building Efficient and Highly Run-Time Adaptable Virtual Machines},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {60--71},
doi = {},
year = {2016},
}
|
|
| Garnock-Jones, Tony |
DLS '16: "Modular Semantic Actions ..."
Modular Semantic Actions
Alessandro Warth, Patrick Dubroy, and Tony Garnock-Jones (Y Combinator Research, USA; Northeastern University, USA) Parser generators give programmers a convenient and declarative way to write parsers and other language-processing applications, but their mechanisms for extension and code reuse often leave something to be desired. We introduce Ohm, a parser generator in which both grammars and their interpretations can be extended in safe and modular ways. Unlike many similar tools, Ohm completely separates grammars and semantic actions, avoiding the problems that arise when these two concerns are mixed. This paper describes the particular way in which Ohm achieves this separation, and discusses the resulting benefits to modularity and extensibility.
@InProceedings{DLS16p108,
author = {Alessandro Warth and Patrick Dubroy and Tony Garnock-Jones},
title = {Modular Semantic Actions},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {108--119},
doi = {},
year = {2016},
}
Info
|
|
| Gross, Thomas R. |
DLS '16: "Parallel Virtual Machines ..."
Parallel Virtual Machines with RPython
Remigius Meier, Armin Rigo, and Thomas R. Gross (ETH Zurich, Switzerland; PyPy.org, Switzerland) The RPython framework takes an interpreter for a dynamic language as its input and produces a Virtual Machine (VM) for that language. RPython is being used to develop PyPy, a high-performance Python interpreter. However, the produced VM does not support parallel execution since the framework relies on a Global Interpreter Lock (GIL): PyPy serialises the execution of multi-threaded Python programs. We describe the rationale and design of a new parallel execution model for RPython that allows the generation of parallel virtual machines while leaving the language semantics unchanged. This model then allows different implementations of concurrency control, and we discuss an implementation based on a GIL and an implementation based on Software Transactional Memory (STM). To evaluate the benefits of either choice, we adapt PyPy to work with both implementations (GIL and STM). The evaluation shows that PyPy with STM improves the runtime of a set of multi-threaded Python programs over PyPy with a GIL by factors in the range of 1.87× up to 5.96× when executing on a processor with 8 cores.
@InProceedings{DLS16p48,
author = {Remigius Meier and Armin Rigo and Thomas R. Gross},
title = {Parallel Virtual Machines with RPython},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {48--59},
doi = {},
year = {2016},
}
|
|
| Heinze, Thomas S. |
DLS '16: "Type Safety Analysis for Dart ..."
Type Safety Analysis for Dart
Thomas S. Heinze, Anders Møller, and Fabio Strocco (Aarhus University, Denmark) Optional typing is traditionally viewed as a compromise between static and dynamic type checking, where code without type annotations is not checked until runtime. We demonstrate that optional type annotations in Dart programs can be integrated into a flow analysis to provide static type safety guarantees both for annotated and non-annotated parts of the code. We explore two approaches: one that uses type annotations for filtering, and one that uses them as specifications. What makes this particularly challenging for Dart is that its type system is unsound even for fully annotated code. Experimental results show that the technique is remarkably effective, even without context sensitivity: 99.3% of all property lookup operations are reported type safe in a collection of benchmark programs.
@InProceedings{DLS16p1,
author = {Thomas S. Heinze and Anders Møller and Fabio Strocco},
title = {Type Safety Analysis for Dart},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {1--12},
doi = {},
year = {2016},
}
Info
|
|
| Hemann, Jason |
DLS '16: "A Small Embedding of Logic ..."
A Small Embedding of Logic Programming with a Simple Complete Search
Jason Hemann, Daniel P. Friedman, William E. Byrd, and Matthew Might (Indiana University, USA; University of Utah, USA) We present a straightforward, call-by-value embedding of a small logic programming language with a simple complete search. We construct the entire language in 54 lines of Racket---half of which implement unification. We then layer over it, in 43 lines, a reconstruction of an existing logic programming language, miniKanren, and attest to our implementation's pedagogical value. Evidence suggests our combination of expressiveness, concision, and elegance is compelling: since microKanren's release, it has spawned over 50 embeddings in over two dozen host languages, including Go, Haskell, Prolog and Smalltalk.
@InProceedings{DLS16p96,
author = {Jason Hemann and Daniel P. Friedman and William E. Byrd and Matthew Might},
title = {A Small Embedding of Logic Programming with a Simple Complete Search},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {96--107},
doi = {},
year = {2016},
}
Info
|
|
| Hendren, Laurie |
DLS '16: "Efficiently Implementing the ..."
Efficiently Implementing the Copy Semantics of MATLAB's Arrays in JavaScript
Vincent Foley-Bourgon and Laurie Hendren (McGill University, Canada) Compiling MATLAB---a dynamic, array-based language---to JavaScript is an attractive proposal: the output code can be deployed on a platform used by billions and can leverage the countless hours that have gone into making JavaScript JIT engines fast. But before that can happen, the original MATLAB code must be properly translated, making sure to bridge the semantic gaps of the two languages. An important area where MATLAB and JavaScript differ is in their handling of arrays: for example, in MATLAB, arrays are one-indexed and writing at an index beyond the end of an array extends it; in JavaScript, typed arrays are zero-indexed and writing out of bounds is a no-op. A MATLAB-to-JavaScript compiler must address these mismatches. Another salient and pervasive difference between the two languages is the assignment of arrays to variables: in MATLAB, this operation has value semantics, while in JavaScript is has reference semantics. In this paper, we present MatJuice --- a source-to-source, ahead-of-time compiler back-end for MATLAB --- and how it deals efficiently with this last issue. We present an intra-procedural data-flow analysis to track where each array variable may point to and which variables are possibly aliased. We also present the associated copy insertion transformation that uses the points-to information to insert explicit copies when necessary. The resulting JavaScript program respects the MATLAB value semantics and we show that it performs fewer run-time copies than some alternative approaches.
@InProceedings{DLS16p72,
author = {Vincent Foley-Bourgon and Laurie Hendren},
title = {Efficiently Implementing the Copy Semantics of MATLAB's Arrays in JavaScript},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {72--83},
doi = {},
year = {2016},
}
|
|
| Humer, Christian |
DLS '16: "Optimizing R Language Execution ..."
Optimizing R Language Execution via Aggressive Speculation
Lukas Stadler, Adam Welc, Christian Humer, and Mick Jordan (Oracle Labs, Austria; Oracle Labs, USA; Oracle Labs, Switzerland) The R language, from the point of view of language design and implementation, is a unique combination of various programming language concepts. It has functional characteristics like lazy evaluation of arguments, but also allows expressions to have arbitrary side effects. Many runtime data structures, for example variable scopes and functions, are accessible and can be modified while a program executes. Several different object models allow for structured programming, but the object models can interact in surprising ways with each other and with the base operations of R. R works well in practice, but it is complex, and it is a challenge for language developers trying to improve on the current state-of-the-art, which is the reference implementation -- GNU R. The goal of this work is to demonstrate that, given the right approach and the right set of tools, it is possible to create an implementation of the R language that provides significantly better performance while keeping compatibility with the original implementation. In this paper we describe novel optimizations backed up by aggressive speculation techniques and implemented within FastR, an alternative R language implementation, utilizing Truffle -- a JVM-based language development framework developed at Oracle Labs. We also provide experimental evidence demonstrating effectiveness of these optimizations in comparison with GNU R, as well as Renjin and TERR implementations of the R language.
@InProceedings{DLS16p84,
author = {Lukas Stadler and Adam Welc and Christian Humer and Mick Jordan},
title = {Optimizing R Language Execution via Aggressive Speculation},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {84--95},
doi = {},
year = {2016},
}
|
|
| Im, Hyeonseung |
DLS '16: "Precise and Scalable Static ..."
Precise and Scalable Static Analysis of jQuery using a Regular Expression Domain
Changhee Park, Hyeonseung Im, and Sukyoung Ryu (KAIST, South Korea; Kangwon National University, South Korea) jQuery is the most popular JavaScript library but the state-of-the-art static analyzers for JavaScript applications fail to analyze simple programs that use jQuery. In this paper, we present a novel abstract string domain whose elements are simple regular expressions that can represent prefix, infix, and postfix substrings of a string and even their sets. We formalize the new domain in the abstract interpretation framework with abstract models of strings and objects commonly used in the existing JavaScript analyzers. For practical use of the domain, we present polynomial-time inclusion decision rules between the regular expressions and prove that the rules exactly capture the actual inclusion relation. We have implemented the domain as an extension of the open-source JavaScript analyzer, SAFE, and we show that the extension significantly improves the scalability and precision of the baseline analyzer in analyzing programs that use jQuery.
@InProceedings{DLS16p25,
author = {Changhee Park and Hyeonseung Im and Sukyoung Ryu},
title = {Precise and Scalable Static Analysis of jQuery using a Regular Expression Domain},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {25--36},
doi = {},
year = {2016},
}
|
|
| Jordan, Mick |
DLS '16: "Optimizing R Language Execution ..."
Optimizing R Language Execution via Aggressive Speculation
Lukas Stadler, Adam Welc, Christian Humer, and Mick Jordan (Oracle Labs, Austria; Oracle Labs, USA; Oracle Labs, Switzerland) The R language, from the point of view of language design and implementation, is a unique combination of various programming language concepts. It has functional characteristics like lazy evaluation of arguments, but also allows expressions to have arbitrary side effects. Many runtime data structures, for example variable scopes and functions, are accessible and can be modified while a program executes. Several different object models allow for structured programming, but the object models can interact in surprising ways with each other and with the base operations of R. R works well in practice, but it is complex, and it is a challenge for language developers trying to improve on the current state-of-the-art, which is the reference implementation -- GNU R. The goal of this work is to demonstrate that, given the right approach and the right set of tools, it is possible to create an implementation of the R language that provides significantly better performance while keeping compatibility with the original implementation. In this paper we describe novel optimizations backed up by aggressive speculation techniques and implemented within FastR, an alternative R language implementation, utilizing Truffle -- a JVM-based language development framework developed at Oracle Labs. We also provide experimental evidence demonstrating effectiveness of these optimizations in comparison with GNU R, as well as Renjin and TERR implementations of the R language.
@InProceedings{DLS16p84,
author = {Lukas Stadler and Adam Welc and Christian Humer and Mick Jordan},
title = {Optimizing R Language Execution via Aggressive Speculation},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {84--95},
doi = {},
year = {2016},
}
|
|
| Marr, Stefan |
DLS '16: "Cross-Language Compiler Benchmarking: ..."
Cross-Language Compiler Benchmarking: Are We Fast Yet?
Stefan Marr, Benoit Daloze, and Hanspeter Mössenböck (JKU Linz, Austria) Comparing the performance of programming languages is difficult because they differ in many aspects including preferred programming abstractions, available frameworks, and their runtime systems. Nonetheless, the question about relative performance comes up repeatedly in the research community, industry, and wider audience of enthusiasts. This paper presents 14 benchmarks and a novel methodology to assess the compiler effectiveness across language implementations. Using a set of common language abstractions, the benchmarks are implemented in Java, JavaScript, Ruby, Crystal, Newspeak, and Smalltalk. We show that the benchmarks exhibit a wide range of characteristics using language-agnostic metrics. Using four different languages on top of the same compiler, we show that the benchmarks perform similarly and therefore allow for a comparison of compiler effectiveness across languages. Based on anecdotes, we argue that these benchmarks help language implementers to identify performance bugs and optimization potential by comparing to other language implementations.
@InProceedings{DLS16p120,
author = {Stefan Marr and Benoit Daloze and Hanspeter Mössenböck},
title = {Cross-Language Compiler Benchmarking: Are We Fast Yet?},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {120--131},
doi = {},
year = {2016},
}
Info
DLS '16: "Building Efficient and Highly ..."
Building Efficient and Highly Run-Time Adaptable Virtual Machines
Guido Chari, Diego Garbervetsky, and Stefan Marr (University of Buenos Aires, Argentina; CONICET, Argentina; JKU Linz, Austria) Programming language virtual machines (VMs) realize language semantics, enforce security properties, and execute applications efficiently. Fully Reflective Execution Environments (EEs) are VMs that additionally expose their whole structure and behavior to applications. This enables develop- ers to observe and adapt VMs at run time. However, there is a belief that reflective EEs are not viable for practical usages because such flexibility would incur a high performance overhead. To refute this belief, we built a reflective EE on top of a highly optimizing dynamic compiler. We introduced a new optimization model that, based on the conjecture that variability of low-level (EE-level) reflective behavior is low in many scenarios, mitigates the most significant sources of the performance overheads related to the reflective capabilities in the EE. Our experiments indicate that reflective EEs can reach peak performance in the order of standard VMs. Concretely, that a) if reflective mechanisms are not used the execution overhead is negligible compared to standard VMs, b) VM operations can be redefined at language-level without incurring in significant overheads, c) for several software adaptation tasks, applying the reflection at the VM level is not only lightweight in terms of engineering effort, but also competitive in terms of performance in comparison to other ad-hoc solutions.
@InProceedings{DLS16p60,
author = {Guido Chari and Diego Garbervetsky and Stefan Marr},
title = {Building Efficient and Highly Run-Time Adaptable Virtual Machines},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {60--71},
doi = {},
year = {2016},
}
|
|
| Meier, Remigius |
DLS '16: "Parallel Virtual Machines ..."
Parallel Virtual Machines with RPython
Remigius Meier, Armin Rigo, and Thomas R. Gross (ETH Zurich, Switzerland; PyPy.org, Switzerland) The RPython framework takes an interpreter for a dynamic language as its input and produces a Virtual Machine (VM) for that language. RPython is being used to develop PyPy, a high-performance Python interpreter. However, the produced VM does not support parallel execution since the framework relies on a Global Interpreter Lock (GIL): PyPy serialises the execution of multi-threaded Python programs. We describe the rationale and design of a new parallel execution model for RPython that allows the generation of parallel virtual machines while leaving the language semantics unchanged. This model then allows different implementations of concurrency control, and we discuss an implementation based on a GIL and an implementation based on Software Transactional Memory (STM). To evaluate the benefits of either choice, we adapt PyPy to work with both implementations (GIL and STM). The evaluation shows that PyPy with STM improves the runtime of a set of multi-threaded Python programs over PyPy with a GIL by factors in the range of 1.87× up to 5.96× when executing on a processor with 8 cores.
@InProceedings{DLS16p48,
author = {Remigius Meier and Armin Rigo and Thomas R. Gross},
title = {Parallel Virtual Machines with RPython},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {48--59},
doi = {},
year = {2016},
}
|
|
| Mezzetti, Gianluca |
DLS '16: "Type Unsoundness in Practice: ..."
Type Unsoundness in Practice: An Empirical Study of Dart
Gianluca Mezzetti, Anders Møller, and Fabio Strocco (Aarhus University, Denmark) The type system in the Dart programming language is deliberately designed to be unsound: for a number of reasons, it may happen that a program encounters type errors at runtime although the static type checker reports no warnings. According to the language designers, this ensures a pragmatic balance between the ability to catch bugs statically and allowing a flexible programming style without burdening the programmer with a lot of spurious type warnings. In this work, we attempt to experimentally validate these design choices. Through an empirical evaluation based on open source programs written in Dart totaling 2.4 M LOC, we explore how alternative, more sound choices affect the type warnings being produced. Our results show that some, but not all, sources of unsoundness can be justified. In particular, we find that unsoundness caused by bivariant function subtyping and method overriding does not seem to help programmers. Such information may be useful when designing future versions of the language or entirely new languages.
@InProceedings{DLS16p13,
author = {Gianluca Mezzetti and Anders Møller and Fabio Strocco},
title = {Type Unsoundness in Practice: An Empirical Study of Dart},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {13--24},
doi = {},
year = {2016},
}
Info
|
|
| Might, Matthew |
DLS '16: "A Small Embedding of Logic ..."
A Small Embedding of Logic Programming with a Simple Complete Search
Jason Hemann, Daniel P. Friedman, William E. Byrd, and Matthew Might (Indiana University, USA; University of Utah, USA) We present a straightforward, call-by-value embedding of a small logic programming language with a simple complete search. We construct the entire language in 54 lines of Racket---half of which implement unification. We then layer over it, in 43 lines, a reconstruction of an existing logic programming language, miniKanren, and attest to our implementation's pedagogical value. Evidence suggests our combination of expressiveness, concision, and elegance is compelling: since microKanren's release, it has spawned over 50 embeddings in over two dozen host languages, including Go, Haskell, Prolog and Smalltalk.
@InProceedings{DLS16p96,
author = {Jason Hemann and Daniel P. Friedman and William E. Byrd and Matthew Might},
title = {A Small Embedding of Logic Programming with a Simple Complete Search},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {96--107},
doi = {},
year = {2016},
}
Info
|
|
| Møller, Anders |
DLS '16: "Type Unsoundness in Practice: ..."
Type Unsoundness in Practice: An Empirical Study of Dart
Gianluca Mezzetti, Anders Møller, and Fabio Strocco (Aarhus University, Denmark) The type system in the Dart programming language is deliberately designed to be unsound: for a number of reasons, it may happen that a program encounters type errors at runtime although the static type checker reports no warnings. According to the language designers, this ensures a pragmatic balance between the ability to catch bugs statically and allowing a flexible programming style without burdening the programmer with a lot of spurious type warnings. In this work, we attempt to experimentally validate these design choices. Through an empirical evaluation based on open source programs written in Dart totaling 2.4 M LOC, we explore how alternative, more sound choices affect the type warnings being produced. Our results show that some, but not all, sources of unsoundness can be justified. In particular, we find that unsoundness caused by bivariant function subtyping and method overriding does not seem to help programmers. Such information may be useful when designing future versions of the language or entirely new languages.
@InProceedings{DLS16p13,
author = {Gianluca Mezzetti and Anders Møller and Fabio Strocco},
title = {Type Unsoundness in Practice: An Empirical Study of Dart},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {13--24},
doi = {},
year = {2016},
}
Info
DLS '16: "Type Safety Analysis for Dart ..."
Type Safety Analysis for Dart
Thomas S. Heinze, Anders Møller, and Fabio Strocco (Aarhus University, Denmark) Optional typing is traditionally viewed as a compromise between static and dynamic type checking, where code without type annotations is not checked until runtime. We demonstrate that optional type annotations in Dart programs can be integrated into a flow analysis to provide static type safety guarantees both for annotated and non-annotated parts of the code. We explore two approaches: one that uses type annotations for filtering, and one that uses them as specifications. What makes this particularly challenging for Dart is that its type system is unsound even for fully annotated code. Experimental results show that the technique is remarkably effective, even without context sensitivity: 99.3% of all property lookup operations are reported type safe in a collection of benchmark programs.
@InProceedings{DLS16p1,
author = {Thomas S. Heinze and Anders Møller and Fabio Strocco},
title = {Type Safety Analysis for Dart},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {1--12},
doi = {},
year = {2016},
}
Info
|
|
| Mössenböck, Hanspeter |
DLS '16: "Cross-Language Compiler Benchmarking: ..."
Cross-Language Compiler Benchmarking: Are We Fast Yet?
Stefan Marr, Benoit Daloze, and Hanspeter Mössenböck (JKU Linz, Austria) Comparing the performance of programming languages is difficult because they differ in many aspects including preferred programming abstractions, available frameworks, and their runtime systems. Nonetheless, the question about relative performance comes up repeatedly in the research community, industry, and wider audience of enthusiasts. This paper presents 14 benchmarks and a novel methodology to assess the compiler effectiveness across language implementations. Using a set of common language abstractions, the benchmarks are implemented in Java, JavaScript, Ruby, Crystal, Newspeak, and Smalltalk. We show that the benchmarks exhibit a wide range of characteristics using language-agnostic metrics. Using four different languages on top of the same compiler, we show that the benchmarks perform similarly and therefore allow for a comparison of compiler effectiveness across languages. Based on anecdotes, we argue that these benchmarks help language implementers to identify performance bugs and optimization potential by comparing to other language implementations.
@InProceedings{DLS16p120,
author = {Stefan Marr and Benoit Daloze and Hanspeter Mössenböck},
title = {Cross-Language Compiler Benchmarking: Are We Fast Yet?},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {120--131},
doi = {},
year = {2016},
}
Info
|
|
| Park, Changhee |
DLS '16: "Precise and Scalable Static ..."
Precise and Scalable Static Analysis of jQuery using a Regular Expression Domain
Changhee Park, Hyeonseung Im, and Sukyoung Ryu (KAIST, South Korea; Kangwon National University, South Korea) jQuery is the most popular JavaScript library but the state-of-the-art static analyzers for JavaScript applications fail to analyze simple programs that use jQuery. In this paper, we present a novel abstract string domain whose elements are simple regular expressions that can represent prefix, infix, and postfix substrings of a string and even their sets. We formalize the new domain in the abstract interpretation framework with abstract models of strings and objects commonly used in the existing JavaScript analyzers. For practical use of the domain, we present polynomial-time inclusion decision rules between the regular expressions and prove that the rules exactly capture the actual inclusion relation. We have implemented the domain as an extension of the open-source JavaScript analyzer, SAFE, and we show that the extension significantly improves the scalability and precision of the baseline analyzer in analyzing programs that use jQuery.
@InProceedings{DLS16p25,
author = {Changhee Park and Hyeonseung Im and Sukyoung Ryu},
title = {Precise and Scalable Static Analysis of jQuery using a Regular Expression Domain},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {25--36},
doi = {},
year = {2016},
}
|
|
| Rigo, Armin |
DLS '16: "Parallel Virtual Machines ..."
Parallel Virtual Machines with RPython
Remigius Meier, Armin Rigo, and Thomas R. Gross (ETH Zurich, Switzerland; PyPy.org, Switzerland) The RPython framework takes an interpreter for a dynamic language as its input and produces a Virtual Machine (VM) for that language. RPython is being used to develop PyPy, a high-performance Python interpreter. However, the produced VM does not support parallel execution since the framework relies on a Global Interpreter Lock (GIL): PyPy serialises the execution of multi-threaded Python programs. We describe the rationale and design of a new parallel execution model for RPython that allows the generation of parallel virtual machines while leaving the language semantics unchanged. This model then allows different implementations of concurrency control, and we discuss an implementation based on a GIL and an implementation based on Software Transactional Memory (STM). To evaluate the benefits of either choice, we adapt PyPy to work with both implementations (GIL and STM). The evaluation shows that PyPy with STM improves the runtime of a set of multi-threaded Python programs over PyPy with a GIL by factors in the range of 1.87× up to 5.96× when executing on a processor with 8 cores.
@InProceedings{DLS16p48,
author = {Remigius Meier and Armin Rigo and Thomas R. Gross},
title = {Parallel Virtual Machines with RPython},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {48--59},
doi = {},
year = {2016},
}
|
|
| Ryu, Sukyoung |
DLS '16: "Precise and Scalable Static ..."
Precise and Scalable Static Analysis of jQuery using a Regular Expression Domain
Changhee Park, Hyeonseung Im, and Sukyoung Ryu (KAIST, South Korea; Kangwon National University, South Korea) jQuery is the most popular JavaScript library but the state-of-the-art static analyzers for JavaScript applications fail to analyze simple programs that use jQuery. In this paper, we present a novel abstract string domain whose elements are simple regular expressions that can represent prefix, infix, and postfix substrings of a string and even their sets. We formalize the new domain in the abstract interpretation framework with abstract models of strings and objects commonly used in the existing JavaScript analyzers. For practical use of the domain, we present polynomial-time inclusion decision rules between the regular expressions and prove that the rules exactly capture the actual inclusion relation. We have implemented the domain as an extension of the open-source JavaScript analyzer, SAFE, and we show that the extension significantly improves the scalability and precision of the baseline analyzer in analyzing programs that use jQuery.
@InProceedings{DLS16p25,
author = {Changhee Park and Hyeonseung Im and Sukyoung Ryu},
title = {Precise and Scalable Static Analysis of jQuery using a Regular Expression Domain},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {25--36},
doi = {},
year = {2016},
}
|
|
| Stadler, Lukas |
DLS '16: "Optimizing R Language Execution ..."
Optimizing R Language Execution via Aggressive Speculation
Lukas Stadler, Adam Welc, Christian Humer, and Mick Jordan (Oracle Labs, Austria; Oracle Labs, USA; Oracle Labs, Switzerland) The R language, from the point of view of language design and implementation, is a unique combination of various programming language concepts. It has functional characteristics like lazy evaluation of arguments, but also allows expressions to have arbitrary side effects. Many runtime data structures, for example variable scopes and functions, are accessible and can be modified while a program executes. Several different object models allow for structured programming, but the object models can interact in surprising ways with each other and with the base operations of R. R works well in practice, but it is complex, and it is a challenge for language developers trying to improve on the current state-of-the-art, which is the reference implementation -- GNU R. The goal of this work is to demonstrate that, given the right approach and the right set of tools, it is possible to create an implementation of the R language that provides significantly better performance while keeping compatibility with the original implementation. In this paper we describe novel optimizations backed up by aggressive speculation techniques and implemented within FastR, an alternative R language implementation, utilizing Truffle -- a JVM-based language development framework developed at Oracle Labs. We also provide experimental evidence demonstrating effectiveness of these optimizations in comparison with GNU R, as well as Renjin and TERR implementations of the R language.
@InProceedings{DLS16p84,
author = {Lukas Stadler and Adam Welc and Christian Humer and Mick Jordan},
title = {Optimizing R Language Execution via Aggressive Speculation},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {84--95},
doi = {},
year = {2016},
}
|
|
| Strocco, Fabio |
DLS '16: "Type Unsoundness in Practice: ..."
Type Unsoundness in Practice: An Empirical Study of Dart
Gianluca Mezzetti, Anders Møller, and Fabio Strocco (Aarhus University, Denmark) The type system in the Dart programming language is deliberately designed to be unsound: for a number of reasons, it may happen that a program encounters type errors at runtime although the static type checker reports no warnings. According to the language designers, this ensures a pragmatic balance between the ability to catch bugs statically and allowing a flexible programming style without burdening the programmer with a lot of spurious type warnings. In this work, we attempt to experimentally validate these design choices. Through an empirical evaluation based on open source programs written in Dart totaling 2.4 M LOC, we explore how alternative, more sound choices affect the type warnings being produced. Our results show that some, but not all, sources of unsoundness can be justified. In particular, we find that unsoundness caused by bivariant function subtyping and method overriding does not seem to help programmers. Such information may be useful when designing future versions of the language or entirely new languages.
@InProceedings{DLS16p13,
author = {Gianluca Mezzetti and Anders Møller and Fabio Strocco},
title = {Type Unsoundness in Practice: An Empirical Study of Dart},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {13--24},
doi = {},
year = {2016},
}
Info
DLS '16: "Type Safety Analysis for Dart ..."
Type Safety Analysis for Dart
Thomas S. Heinze, Anders Møller, and Fabio Strocco (Aarhus University, Denmark) Optional typing is traditionally viewed as a compromise between static and dynamic type checking, where code without type annotations is not checked until runtime. We demonstrate that optional type annotations in Dart programs can be integrated into a flow analysis to provide static type safety guarantees both for annotated and non-annotated parts of the code. We explore two approaches: one that uses type annotations for filtering, and one that uses them as specifications. What makes this particularly challenging for Dart is that its type system is unsound even for fully annotated code. Experimental results show that the technique is remarkably effective, even without context sensitivity: 99.3% of all property lookup operations are reported type safe in a collection of benchmark programs.
@InProceedings{DLS16p1,
author = {Thomas S. Heinze and Anders Møller and Fabio Strocco},
title = {Type Safety Analysis for Dart},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {1--12},
doi = {},
year = {2016},
}
Info
|
|
| Swalens, Janwillem |
DLS '16: "Just-in-Time Inheritance: ..."
Just-in-Time Inheritance: A Dynamic and Implicit Multiple Inheritance Mechanism
Mattias De Wael, Janwillem Swalens, and Wolfgang De Meuter (Vrije Universiteit Brussel, Belgium) Multiple inheritance is often criticised for the ambiguity that arises when multiple parents want to pass on a feature with the same name to their offspring. A survey of programming languages reveals that no programming language has an inherently implicit and dynamic approach to resolve this ambiguity. This paper identifies just-in-time inheritance as the first implicit and dynamic inheritance mechanism. The key idea of just-in-time inheritance is that one of the parents is favoured over the others, which resolves the ambiguity, and that the favoured parent can change at runtime. However, just-in-time inheritance is not the silver bullet to solve all ambiguity problems heir to multiple inheritance, because it is not applicable in all scenarios. We conclude that the applicability of just-in-time inheritance is to be found in systems where multiple inheritance is used to model an ``is-a OR is-a''-relation, rather than the more traditional ``is-a AND is-a''-relation.
@InProceedings{DLS16p37,
author = {Mattias De Wael and Janwillem Swalens and Wolfgang De Meuter},
title = {Just-in-Time Inheritance: A Dynamic and Implicit Multiple Inheritance Mechanism},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {37--47},
doi = {},
year = {2016},
}
|
|
| Warth, Alessandro |
DLS '16: "Modular Semantic Actions ..."
Modular Semantic Actions
Alessandro Warth, Patrick Dubroy, and Tony Garnock-Jones (Y Combinator Research, USA; Northeastern University, USA) Parser generators give programmers a convenient and declarative way to write parsers and other language-processing applications, but their mechanisms for extension and code reuse often leave something to be desired. We introduce Ohm, a parser generator in which both grammars and their interpretations can be extended in safe and modular ways. Unlike many similar tools, Ohm completely separates grammars and semantic actions, avoiding the problems that arise when these two concerns are mixed. This paper describes the particular way in which Ohm achieves this separation, and discusses the resulting benefits to modularity and extensibility.
@InProceedings{DLS16p108,
author = {Alessandro Warth and Patrick Dubroy and Tony Garnock-Jones},
title = {Modular Semantic Actions},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {108--119},
doi = {},
year = {2016},
}
Info
|
|
| Welc, Adam |
DLS '16: "Optimizing R Language Execution ..."
Optimizing R Language Execution via Aggressive Speculation
Lukas Stadler, Adam Welc, Christian Humer, and Mick Jordan (Oracle Labs, Austria; Oracle Labs, USA; Oracle Labs, Switzerland) The R language, from the point of view of language design and implementation, is a unique combination of various programming language concepts. It has functional characteristics like lazy evaluation of arguments, but also allows expressions to have arbitrary side effects. Many runtime data structures, for example variable scopes and functions, are accessible and can be modified while a program executes. Several different object models allow for structured programming, but the object models can interact in surprising ways with each other and with the base operations of R. R works well in practice, but it is complex, and it is a challenge for language developers trying to improve on the current state-of-the-art, which is the reference implementation -- GNU R. The goal of this work is to demonstrate that, given the right approach and the right set of tools, it is possible to create an implementation of the R language that provides significantly better performance while keeping compatibility with the original implementation. In this paper we describe novel optimizations backed up by aggressive speculation techniques and implemented within FastR, an alternative R language implementation, utilizing Truffle -- a JVM-based language development framework developed at Oracle Labs. We also provide experimental evidence demonstrating effectiveness of these optimizations in comparison with GNU R, as well as Renjin and TERR implementations of the R language.
@InProceedings{DLS16p84,
author = {Lukas Stadler and Adam Welc and Christian Humer and Mick Jordan},
title = {Optimizing R Language Execution via Aggressive Speculation},
booktitle = {Proc.\ DLS},
publisher = {ACM},
pages = {84--95},
doi = {},
year = {2016},
}
|
34 authors
proc time: 1.14