Philipp Schuster

Philipp Schuster

Auto-generated profile, based on publicly available information

Philipp Schuster

University of Tübingen, Germany

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
31 March 2020 in Journal of Functional Programming
Verified
Journal Article
Open access
PDF file
JBJonathan Immanuel Brachthäuser
Jonathan Immanuel Brachthäuser
PSPhilipp Schuster
Philipp Schuster
KOKlaus Ostermann
Klaus Ostermann
Effect handlers are a promising way to structure effectful programs in a modular way. We present the Scala library Effekt , which is centered around capability passing and implemented in terms of a monad for multi-prompt delimited continuations. Effekt is the first library implementation of effect handlers that supports effect safety and effect polymorphism without resorting to type-level programming. We describe a novel way of achieving effect safety using intersection types and path-dependent types. The effect system of our library design fits well into the programming paradigm of capability passing and is inspired by the effect system of Zhang & Myers (2019, Proc. ACM Program. Lang. 3 (POPL), 5:1-5:29). Capabilities carry an abstract type member, which represents an individual effect type and reflects the use of the capability on the type level. We represent effect rows as the contravariant intersection of effect types. Handlers introduce capabilities and remove components of the intersection type. Reusing the existing type system of Scala, we get effect subtyping and effect polymorphism for free.

29 April 2022 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
JBJonathan Immanuel Brachthäuser
Jonathan Immanuel Brachthäuser
PSPhilipp Schuster
Philipp Schuster
ELEdward Lee
Edward Lee
ABAleksander Boruch-Gruszecki
Aleksander Boruch-Gruszecki
Reasoning about the use of external resources is an important aspect of many practical applications. Effect systems enable tracking such information in types, but at the cost of complicating signatures of common functions. Capabilities coupled with escape analysis offer safety and natural signatures, but are often overly coarse grained and restrictive. We present System C, which builds on and generalizes ideas from type-based escape analysis and demonstrates that capabilities and effects can be reconciled harmoniously. By assuming that all functions are second class, we can admit natural signatures for many common programs. By introducing a notion of boxed values, we can lift the restrictions of second-class values at the cost of needing to track degree-of-impurity information in types. The system we present is expressive enough to support effect handlers in full capacity. We practically evaluate System C in an implementation and prove its soundness.

2 August 2020 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
PSPhilipp Schuster
Philipp Schuster
JBJonathan Immanuel Brachthäuser
Jonathan Immanuel Brachthäuser
KOKlaus Ostermann
Klaus Ostermann
Effect handlers encourage programmers to abstract over repeated patterns of complex control flow. As of today, this abstraction comes at a significant price in performance. In this paper, we aim to achieve abstraction without regret for effect handlers. We present a language for effect handlers in _capability-passing style_ (λ Cap ) and an implementation of this language as a translation to simply-typed lambda calculus in _iterated continuation-passing style_. A suite of benchmarks indicates that the novel combination of capability-passing style and iterated CPS enables significant speedups over existing languages with effect handlers or control operators. Our implementation technique is general and allows us to generate code in any language that supports first-class functions. We then identify a subset of programs for which we can further improve the performance and guarantee full elimination of the effect handler abstraction. To formally capture this subset, we refine λ Cap to λ λ Cap with a more restrictive type system. We present a type-directed translation for λ λ Cap that inserts staging annotations and prove that no abstractions or applications related to effect handlers occur in the translated program. Using this second translation we observe additional speedups in some of the benchmarks.

22 October 2017
Verified
Conference Paper
Open access
JBJonathan Immanuel Brachthäuser
Jonathan Immanuel Brachthäuser
PSPhilipp Schuster
Philipp Schuster

30 August 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MLMatthew Lutze
Matthew Lutze
MMMagnus Madsen
Magnus Madsen
PSPhilipp Schuster
Philipp Schuster
JBJonathan Immanuel Brachthäuser
Jonathan Immanuel Brachthäuser
Type and effect systems have been successfully used to statically reason about effects in many different domains, including region-based memory management, exceptions, and algebraic effects and handlers. Such systems’ soundness is often stated in terms of the absence of effects. Yet, existing systems only admit indirect reasoning about the absence of effects. This is further complicated by effect polymorphism which allows function signatures to abstract over arbitrary, unknown sets of effects. We present a new type and effect system with effect polymorphism as well as union, intersection, and complement effects. The effect system allows us to express effect exclusion as a new class of effect polymorphic functions: those that permit any effects except those in a specific set. This way, we equip programmers with the means to directly reason about the absence of effects. Our type and effect system builds on the Hindley-Milner type system, supports effect polymorphism, and preserves principal types modulo Boolean equivalence. In addition, a suitable extension of Algorithm W with Boolean unification on the algebra of sets enables complete type and effect inference. We formalize these notions in the λ ∁ calculus. We prove the standard progress and preservation theorems as well as a non-standard effect safety theorem: no excluded effect is ever performed. We implement the type and effect system as an extension of the Flix programming language. We conduct a case study of open source projects identifying 59 program fragments that require effect exclusion for correctness. To demonstrate the usefulness of the proposed type and effect system, we recast these program fragments into our extension of Flix.

16 October 2023 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
MMMarius Müller
Marius Müller
PSPhilipp Schuster
Philipp Schuster
JSJonathan Lindegaard Starup
Jonathan Lindegaard Starup
KOKlaus Ostermann
Klaus Ostermann
JBJonathan Immanuel Brachthäuser
Jonathan Immanuel Brachthäuser
Effect handlers are a high-level abstraction that enables programmers to use effects in a structured way. They have gained a lot of popularity within academia and subsequently also in industry. However, the abstraction often comes with a significant runtime cost and there has been intensive research recently on how to reduce this price. A promising approach in this regard is to implement effect handlers using a CPS translation and to provide sufficient information about the nesting of handlers. With this information the CPS translation can decide how effects have to be lifted through handlers, i.e., which handlers need to be skipped, in order to handle the effect at the correct place. A structured way to make this information available is to use a calculus with a region system and explicit subregion evidence. Such calculi, however, are quite verbose, which makes them impractical to use as a source-level language. We present a method to infer the lifting information for a calculus underlying a source-level language. This calculus uses second-class capabilities for the safe use of effects. To do so, we define a typed translation to a calculus with regions and evidence and we show that this lift-inference translation is typability- and semantics-preserving. On the one hand, this exposes the precise relation between the second-class property and the structure given by regions. On the other hand, it closes a gap in a compiler pipeline enabling efficient compilation of the source-level language. We have implemented lift inference in this compiler pipeline and conducted benchmarks which indicate that the approach is indeed working.