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.

Substructural type systems provide static guarantees about resource usage in programs. In most practical systems, however, the available usage constraints and their composition are predetermined by the language design, with only limited support for application programmers to customize them. We present a technique for expressing modular substructural constraints on function arrows in embedded domainspecific languages, enabling resource disciplines to be customized to the heterogeneous requirements of real-wo

As the number of cores increases in modern multiprocessors, it is becoming increasingly difficult to write general purpose applications that efficiently utilize this computing power. Most applications manipulate structured data. Modern languages and platforms provide collection frameworks with basic data structures like lists, hashtables and trees. These data structures have a range of predefined operations which include mapping, filtering or finding elements. Such bulk operations traverse the collection an

Type-level programming is becoming more and more popular in the realm of functional programming. However, the combination of type-level programming and subtyping remains largely unexplored in practical programming languages. This paper presents match types ...

There is a rapid rise of multi-cores in recent hardware architectures. To exploit computational power of multi-core architectures, software should shift to be as concurrent as possible; and therefore should have concurrency control mechanisms. There are different concurrency programming paradigms such as locking and conditions, non-blocking algorithms, actors and software transactional memory (STM). There is a need to compare these approaches in terms of ease of use and performance. This work implements thr

A scalable programming language is one in which the same concepts can describe small as well as large parts. Towards this goal, Scala unifies concepts from object and module systems. An essential ingredient of this unification is the concept of objects wit ...

With the rise of multicores, there is a trend of supporting data-parallel collection operations in general purpose programming languages. These operations are highly parametric, incurring abstraction performance penalties. Furthermore, data-parallel operations must scale when applied to irregular workloads. Work-stealing is a proven technique for load balancing irregular workloads, but general purpose work-stealing also suffers abstraction penalties. We present a generic data-parallel collections design bas

Though being seemingly orthogonal, the scoping restrictions enforced by capture checking and mutable variables give rise to surprising challenges when they interact. To obtain a system that is both sound and expressive, the Scala capture checker introduced ...

We propose a new type-theoretic foundation of Scala and languages like it: the Dependent Object Types (DOT) calculus. DOT models Scala’s path-dependent types, abstract type members and its mixture of nominal and structural typing through the use of reﬁneme ...

Foundational work on programming has been based traditionally on some variant of lambda calculus. This approach, while ideally suited to sequential programming, is increasingly at odds with modern programs which are reactive in their interfaces and concurrent in their implementation. Standard process calculi, on the other hand, model nothing but the concurrent aspects of systems, and are ill-suited to express sequential behavior. This talk will show how nets consisting of functions and rewrite rules can ser

Capabilities are widely used in the design of software systems to ensure security. A system of capabilities can become a mess in the presence of objects and functions: objects may leak capabilities and functions may capture capabilities. They make reasonin ...

Type systems usually characterize the shape of values but not their free variables. However, many desirable safety properties could be guaranteed if one knew the free variables captured by values. We describe CC

This article presents a modular, flow-insensitive type-and- effect system for purity with lightweight annotations. It does not enforce a global programming discipline and allows ar- bitrary effects to occur in impure parts of the program. The system is des ...

AI agents that interact with the real world through tool calls pose fundamental safety challenges: agents might leak private information, cause unintended side effects, or be manipulated through prompt injection. To address these challenges, we propose to put the agent in a programming-language-based "safety harness": instead of calling tools directly, agents express their intentions as code in a capability-safe language, Scala 3 with capture checking. Capabilities are program variables that regulate access

Unique object references have many important applications in object-oriented programming. For instance, with sufficient encapsulation properties they enable safe and efficient transfer of message objects between concurrent processes. However, it is a long-standing challenge to integrate unique references into practical object-oriented programming languages. This paper introduces a new approach to external uniqueness. The idea is to use capabilities for enforcing both aliasing constraints that guarantee exte

Cluster computing systems today impose a trade-off between generality, performance and productivity. Hadoop and Dryad force programmers to write low level programs that are tedious to compose but easy to optimize. Systems like Dryad/LINQ and Spark allow co ...

We present a work-stealing algorithm for runtime scheduling of data-parallel operations in the context of shared-memory architectures on data sets with highly-irregular workloads that are not known a priori to the scheduler. This scheduler can parallelize ...

Generics on the Java platform are compiled using the erasure transformation, which only supports by-reference values. This causes slowdowns when generics operate on primitive types, such as integers, as they have to be transformed into reference-based objects. Project Valhalla is an effort to remedy this problem by specializing classes at load-time so they can efficiently handle primitive values. In its current early prototype, the Valhalla compilation scheme limits the interaction between specialized and e

What is a good method to specify and derive imperative programs? This paper argues that a new form of functional programming fits the bill, where variable functions can be updated at specified points in their domain. Traditional algebraic specification and functional programming are a powerful pair of tools for specifying and implementing domains of discourse and operations on them. Recent work on evolving algebras has introduced the function update in algebraic specifications, and has applied it with good

In modern programming high-level data-structures are an important foundation for most applications. With the rise of the multi-core era, there is a growing trend of supporting data-parallel collection operations in general purpose programming languages and platforms. To facilitate object-oriented reuse these operations are highly parametric, incurring abstraction performance penalties. Furthermore, data-parallel operations must scale when used in problems with irregular workloads. Work-stealing is a proven

Software engineering demands generality and abstraction, performance demands specialization and concretization. Generative programming can provide both, but the effort required to develop high-quality program generators likely offsets their benefits, even if a multi-stage programming language is used. We present lightweight modular staging, a library-based multi-stage programming approach that breaks with the tradition of syntactic quasi-quotation and instead uses only types to distinguish between binding t

Martin Odersky

Chat with Graph Search

Modular Substructural Constraints for Embedded DSLs

On A Generic Parallel Collection Framework

Type-Level Programming with Match Types

Concurrent Programming Paradigms, A Comparison in Scala

Foundations of Path-Dependent Types

On Lock-Free Work-stealing Iterators for Parallel Data Structures

A Formal Foundation of Reach Capabilities

Dependent Object Types

Functional Nets

Stoic: Towards Disciplined Capabilities

Capturing Types

A Flow-Insensitive, Modular Effect System for Purity

Securing Agents With Tracked Capabilities

Capabilities for External Uniqueness

Jet: An Embedded DSL for High Performance Big Data Processing

Near Optimal Work-Stealing Tree Scheduler for Highly Irregular Data-Parallel Workloads

Improving the Interoperation between Generics Translations

Programming with Variable Functions

Achieving Efficient Work-Stealing for Data-Parallel Collections

Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs