Aleksander Boruch-Gruszecki

Aleksander Boruch-Gruszecki

Auto-generated profile, based on publicly available information

Aleksander Boruch-Gruszecki

EPFL, Lausanne, Switzerland

Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

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

Representative Publications

View All Publications
20 November 2023 in ACM Transactions on Programming Languages and Systems
Verified
Journal Article
Open access
ABAleksander Boruch-Gruszecki
Aleksander Boruch-Gruszecki
MOMartin Odersky
Martin Odersky
ELEdward Lee
Edward Lee
OLOndřej Lhoták
Ondřej Lhoták
JBJonathan Brachthäuser
Jonathan Brachthäuser
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 < :◻ , a calculus where such captured variables are succinctly represented in types, and show it can be used to safely implement effects and effect polymorphism via scoped capabilities. We discuss how the decision to track captured variables guides key aspects of the calculus, and show that CC < :◻ admits simple and intuitive types for common data structures and their typical usage patterns. We demonstrate how these ideas can be used to guide the implementation of capture checking in a practical programming language.

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 January 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
LPLionel Parreaux
Lionel Parreaux
ABAleksander Boruch-Gruszecki
Aleksander Boruch-Gruszecki
AFAndong Fan
Andong Fan
CCChun Yin Chau
Chun Yin Chau
Type inference in the presence of first-class or “ impredicative ” second-order polymorphism à la System F has been an active research area for several decades, with original works dating back to the end of the 80s. Yet, until now many basic problems remain open, such as how to type check expressions like ( λ x . ( x     123 ,   x     True ) ) id reliably. We show that a type inference approach based on multi-bounded polymorphism , a form of implicit polymorphic subtyping with multiple lower and upper bounds, can help us resolve most of these problems in a uniquely simple and regular way. We define F ≤ , a declarative type system derived from the existing theory of implicit coercions by Cretin and Rémy (LICS 2014), and we introduce SuperF, a novel algorithm to infer polymorphic multi-bounded F ≤ types while checking user type annotations written in the syntax of System F. We use a recursion-avoiding heuristic to guarantee termination of type inference at the cost of rejecting some valid programs, which thankfully rarely triggers in practice. We show that SuperF is vastly more powerful than all first-class-polymorphic type inference systems proposed so far, significantly advancing the state of the art in type inference for general-purpose programming languages.

29 April 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
YXYichen Xu
Yichen Xu
ABAleksander Boruch-Gruszecki
Aleksander Boruch-Gruszecki
MOMartin Odersky
Martin Odersky
Data races have long been a notorious problem in concurrent programming. They are hard to detect, and lead to non-deterministic behaviours. There has been a lot of interest in type systems that statically guarantee data race freedom. Significant progress has been made in this area, and these type systems are increasingly usable and practical. However, their adoption in mainstream programming languages is still limited, which is largely attributed to their strict alias prevention principles that obstruct the usage of existing programming patterns. This is a deterrent to the migration of existing code bases. To tackle this problem, we propose Capture Separation Calculus (System CSC), a calculus that models fork-join parallelism and statically prevents data races while being compatible with established programming patterns. It follows a control-as-you-need philosophy: by default, aliases are allowed, but they are tracked in the type system. When data races are a concern, the tracked aliases are controlled to prevent data-race-prone patterns. We study the formal properties of System CSC. Type soundness is proven via the standard progress and preservation theorems. Additionally, we formally verify the data race freedom property of System CSC by proving that the reduction of a well-typed program is confluent.

31 October 2022 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
ABAleksander Boruch-Gruszecki
Aleksander Boruch-Gruszecki
RWRadosław Waśko
Radosław Waśko
YXYichen Xu
Yichen Xu
LPLionel Parreaux
Lionel Parreaux
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 currently results in puzzling type errors in most of these languages. Yet this combination of features occurs naturally in many scenarios, such as when manipulating typed ASTs. To support it properly, compilers needs to implement a form of subtyping reconstruction: the ability to reconstruct subtyping information uncovered at runtime during pattern matching. We introduce cDOT, a new calculus in the family of Dependent Object Types (DOT) intended to serve as a formal foundation for subtyping reconstruction. Being descended from pDOT, itself a formal foundation for Scala, cDOT can be used to encode advanced object-oriented features such as generic inheritance, type constructor variance, F-bounded polymorphism, and first-class recursive modules. We demonstrate that subtyping reconstruction subsumes GADTs by encoding λ 2, G µ , a classical constraint-based GADT calculus, into cDOT.

8 October 2024 in Proceedings of the ACM on Programming Languages
Verified
Journal Article
Open access
ABAleksander Boruch-Gruszecki
Aleksander Boruch-Gruszecki
AGAdrien Ghosn
Adrien Ghosn
MPMathias Payer
Mathias Payer
CPClément Pit-Claudel
Clément Pit-Claudel
Modern software needs fine-grained compartmentalization, i.e., intra-process isolation. A particularly important reason for it are supply-chain attacks, the need for which is aggravated by modern applications depending on hundreds or even thousands of libraries. Object capabilities are a particularly salient approach to compartmentalization, but they require the entire program to assume a lack of ambient authority. Most of existing code was written under no such assumption; effectively, existing applications need to undergo a rewrite-the-world migration to reap the advantages of ocap. We propose gradual compartmentalization , an approach which allows gradually migrating an application to object capabilities, component by component in arbitrary order, all the while continuously enjoying security guarantees. The approach relies on runtime authority enforcement and tracking the authority of objects the type system. We present Gradient, a proof-of- concept gradual compartmentalization extension to Scala which uses Enclosures and Capture Tracking as its key components. We evaluate our proposal by migrating the standard XML library of Scala to Gradient.