Publications related to Programming language theory

Formal Foundations of Capture Tracking

Type systems are a device for verifying properties of programs without running them. Many programming languages used in the industry have always had a type system, while others were initially created without a type system and later adopted one, when the ad ...

EPFL2024

A case for DOT: Theoretical Foundations for Objects with Pattern Matching and GADT-Style Reasoning

Yichen Xu, Lionel Emile Vincent Parreaux, Aleksander Slawomir Boruch-Gruszecki

Many programming languages in the OO tradition now support pattern matching in some form. Historical examples include Scala and Ceylon, with the more recent additions of Java, Kotlin, TypeScript, and Flow. But pattern matching on generic class hierarchies ...

Assoc Computing Machinery2022

Type-Level Programming with Match Types

Martin Odersky, Olivier Eric Paul Blanvillain

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 ...

ASSOC COMPUTING MACHINERY2022

Enclosure: Language-Based Restriction of Untrusted Libraries

James Richard Larus, Mathias Josef Payer, Edouard Bugnion, Evangelos Marios Kogias, Adrien Ghosn

Programming languages and systems have failed to address the security implications of the increasingly frequent use of public libraries to construct modern software. Most languages provide tools and online repositories to publish, import, and use libraries ...

ACM2021

Representing Monads with Capabilities

Martin Odersky, Aleksander Slawomir Boruch-Gruszecki, Jonathan Immanuel Brachthäuser

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 ...

2021

Exploiting Errors for Efficiency: A Survey from Circuits to Applications

Babak Falsafi, Alexandros Daglis, Eva Darulova, Mattia Cacciotti, Damien Zufferey, Dorde Jevdic, Sasa Misailovic

When a computational task tolerates a relaxation of its specification or when an algorithm tolerates the effects of noise in its execution, hardware, system software, and programming language compilers or their runtime systems can trade deviations from cor ...

ASSOC COMPUTING MACHINERY2020

Stoic: Towards Disciplined Capabilities

Martin Odersky, Nada Amin, Fengyun Liu, Sandro Stucki, Paolo Giosuè Giarrusso

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 ...

2020

The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy

Lionel Emile Vincent Parreaux

MLsub extends traditional Hindley-Milner type inference with subtyping while preserving compact principal types, an exciting new development. However, its specification in terms of biunification is difficult to understand, relying on the new concepts of bi ...

2020

Introducing a Paper-Based Programming Language for Computing Education in Classrooms

Francesco Mondada, Christian Giang, Andrea Mussati, Aditya Mehrotra, Noé Duruz

Past research has shown that the use of tangible platforms for computingeducation can enhance students’ interest, engagement and collaboration within workgroups. However, to this day, the adoption of such interfaces in classrooms has remained relatively sc ...

ACM2020

Semantics-preserving inlining for metaprogramming

Martin Odersky, Sébastien Jean R Doeraene, Nicolas Alexander Stucki

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 ...

2020

Type-Safe Metaprogramming and Compilation Techniques For Designing Efficient Systems in High-Level Languages

Lionel Emile Vincent Parreaux

Software engineering practices have been steadily moving towards higher-level programming languages and away from lower-level ones. High-level languages tend to greatly improve safety, productivity, and code maintainability because they handle various impl ...

EPFL2020

EVA: An Encrypted Vector Arithmetic Language and Compiler for Efficient Homomorphic Computation

Blagovesta Hristova Kostova, Wei Dai

Fully-Homomorphic Encryption (FHE) offers powerful capabilities by enabling secure offloading of both storage and computation, and recent innovations in schemes and implementations have made it all the more attractive. At the same time, FHE is notoriously ...

ASSOC COMPUTING MACHINERY2020

Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs

Marco Mattavelli, Simone Casale Brunet, Endri Bezati, Anatoly Prihozhy

Large dataflow designs are a result of behavioral specification of modern complex digital systems and/or a result of unfolding and transforming looped and branched programs. Since deep-submicron silicon technology provides large amounts of available resour ...

SPRINGER2020

Secured Routines: Language-based Construction of Trusted Execution Environments

James Richard Larus, Edouard Bugnion, Adrien Ghosn

Trusted Execution Environments (TEEs), such as Intel SGX enclaves, use hardware to ensure the confidentiality and integrity of operations on sensitive data. While the technology is available on many processors, the complexity of its programming model and i ...

USENIX ASSOC2019

Finally, a Polymorphic Linear Algebra Language

Amir Shaikhha, Lionel Emile Vincent Parreaux

Many different data analytics tasks boil down to linear algebra primitives. In practice, for each different type of workload, data scientists use a particular specialised library. In this paper, we present Pilatus, a polymorphic iterative linear algebra la ...

2019

System Support for Efficient Replication in Distributed Systems

Dragos-Adrian Seredinschi

Current online applications, such as search engines, social networks, or file sharing services, execute across a distributed network of machines. They provide non-stop services to their users despite failures in the underlying network. To achieve such a hi ...

EPFL2019

Initialization patterns in Dotty

Martin Odersky, Fengyun Liu

Safe object initialization is important to avoid a category of runtime errors in programming languages. In this paper, we provide a case study of the initialization patterns on the Dotty compiler. In particular, we find that calling dynamic-dispatching met ...

2018

Theory and Practice of Coroutines with Snapshots

Aleksandar Prokopec, Fengyun Liu

While event-driven programming is a widespread model for asynchronous computing, its inherent control flow fragmentation makes event-driven programs notoriously difficult to understand and maintain. Coroutines are a general control flow construct that can ...

2018

Cross-Platform Language Design

Sébastien Jean R Doeraene

Programming languages are increasingly compiled to multiple runtimes, each featuring their own rich structures such as their object model. Furthermore, they need to interact with other languages targeting said runtimes. A language targeting only one runtim ...

EPFL2018

Efficient Dynamic Optimisation Heuristics for Dataflow Pipelines

Marco Mattavelli, Simone Casale Brunet, Endri Bezati, Anatoly Prihozhy

Large dataflow designs appear as a result of functional specification of modern complex digital systems and/ or a result of unfolding and behavioral transformation of looped and branched programs. Since deep-submicron silicon technology provides large amou ...

IEEE2018