Publications by Martin Odersky

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Implementing machine learning algorithms for large data, such as the Web graph and social networks, is challenging. Even though much research has focused on making sequential algorithms more scalable, their running times continue to be prohibitively long. ...

We design and study newObj, a calculus and dependent type system forobjects and classes which can have types as members. Type members canbe aliases, abstract types, or new types. The type system can modelthe essential concepts of Java's inner classes as well as virtual typesand family polymorphism found in BETA or gbeta. It can also model mostconcepts of SML-style module systems, including sharing constraintsand higher-order functors, but excluding applicative functors.The type system can thus be used as a

dotty is a new, experimental Scala compiler based on DOT, the calculus of Dependent Object Types. Higher-kinded types are a natural extension of first-order lambda calculus, and have been a core construct of Haskell and Scala. As long as such types are jus ...

Programming with monads can be advantageous even in imperative languages with builtin support for side effects. However, in these languages composing monadic programs is different from composing side effecting imperative programs. This does not need to be ...

Understanding a program entails understanding its context; dependencies, configurations and even implementations are all forms of contexts. Modern programming languages and theorem provers offer an array of constructs to define contexts, implicitly. Scala ...

We identify three programming language abstractions for the construction of re-usable components: abstract type members, explicit selftypes and symmetric mixin composition. Together, these abstractions enable us to transform an arbitrary assembly of static program parts with hard references between them into a system of re-usable components. The transformation maintains the structure of the original system. We demonstrate this approach in two case studies, a subject/observer framework and a compiler front-e

We will develop a Scala-based language and a development environment to simplify the construction of cloud-backed smartphone applications, both by professionals and by end users. We will develop programming assistance tools that use cloud analysis (running on http://ecocloud.ch infrastructure) to suggest code fragments, and enable development and customization of applications both from the desktop and directly from smartphones.

We identify three programming language abstractions for the construction of re-usable components: abstract type members, explicit selftypes and symmetric mixin composition. Together, these abstractions enable us to transform an arbitrary assembly of static program parts with hard references between them into a system of re-usable compo-nents. The transformation maintains the structure of the original system. We demonstrate this approach in two case studies, a subject/observer framework and a compiler front-

Composability and deadlock-freedom are important properties that are stated for transactional memory (TM). Commonly, the Semantics of TM requires linearization of transactions. It turns out that linearization of transactions that have cyclic communication brings incomposability and deadlock. Inspired from TM and Actors, this work proposes Transactors that provide facilities of isolation from TM and communication from Actors. We define the semantics of Transactors including support for cyclic transactional c

FlowPools, proposed by are a powerful way to express dataflow logic in highly parallelized applications. The original paper proposes two ways of implementing a FlowPool: Single-Lane FlowPools (SLFP) and Multi-Lane FlowPools (MLFP). While SLFPs showed decent performance overall, insertion operations do not scale. MLFPs solve this limitation as benchmarks discussed in have shown. This report goes into the details of the implementation of MLFPs and lies out the benchmarking results to show that MLFPs may reduc

Inlining is used in many different ways in programming languages: some languages use it as a compiler-directive solely for optimization, some use it as a metaprogramming feature, and others lay their design in-between. This paper presents inlining through ...

Type-and-effect systems are a well-studied approach for reasoning about the computational behavior of programs. A major roadblock in adopting effect systems in popular languages is the tradeoff between expressiveness and verbosity. In this technical report, we present a syntactically lightweight but expressive system for annotating effect-polymorphic behavior of functions. The presented system is independent from any specific effect domains and can be embedded in an extensible type-and-effect system.

We introduce quasiquotes for the Scala programming language, which solve the problem of manual tree construction and deconstruction. Included case studies show that quasiquotes indeed are easier to work with than existing tools for tree construction. When limitations of current implementation are lifted quasiquotes will become the ultimate tool for the tree manipulation.

This report describes an implementation of a non-blocking concurrent shared-memory hash trie based on single-word compare-and-swap instructions. Insert, lookup and remove operations modifying different parts of the hash trie can be run independent of each other and do not contend. Remove operations ensure that the unneeded memory is freed and that the trie is kept compact. A pseudocode for these operations is presented and a proof of correctness is given -- we show that the implementation is linearizable an

Focusing on path-dependent types, the paper develops foundations for Scala from first principles. Starting from a simple calculus D-

Parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. Parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to b ...

Compilation of polymorphic code through type erasure gives compact code but performance on primitive types is significantly hurt. Full specialization gives good performance, but at the cost of increased code size and compilation time. Instead we propose a ...

Type classes were originally developed in Haskell as a disciplined alternative to ad-hoc polymorphism. Type classes have been shown to provide a type-safe solution to important challenges in software engineering and programming languages such as, for examp ...

Functional Nets combine key ideas of functional programming and Petri nets to yield a simple and general programming notation. They have their theoretical foundation in Join calculus. This paper presents functional nets, reviews Join calculus, and shows how the two relate.

Implementing correct and deterministic parallel programs is challenging. Even though concurrency constructs exist in popular pro- gramming languages to facilitate the task of deterministic parallel pro- gramming, they are often too low level, or do not compose well due to underlying blocking mechanisms. In this report, we present the detailed proofs of the linearizability, lock- freedom, and determinism properties of FlowPools, a deterministic concurrent dataflow abstraction presented in [1].

Martin Odersky

Chat with Graph Search

Tools and Frameworks for Big Learning in Scala: Leveraging the Language for High Productivity and Performance

A Nominal Theory of Objects with Dependent Types

Implementing Higher-Kinded Types in Dotty

Representing Monads with Capabilities

Simplicitly: Foundations and Applications of Implicit Function Types

Scalable Component Abstractions

PhoneLab: Cloud-Backed Development Environment for Smartphones

Scalable Component Abstractions

Transactors: Unifying Transactions and Actors

Multi-Lane FlowPools: A Detailed Look

Semantics-preserving inlining for metaprogramming

Relative Effect Declarations for Lightweight Effect-Polymorphism

Quasiquotes for Scala

Cache-Aware Lock-Free Concurrent Hash Tries

The Essence of Dependent Object Types

Staged parser combinators for efficient data processing

Compiling generics through user-directed type specialization

Type Classes as Objects and Implicits

Functional Nets

FlowPools: A Lock-Free Deterministic Concurrent Dataflow Abstraction – Proofs