Stefan Monnier
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Stefan Monnier has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Marc Feeley
Université de Montréal, Montréal, Canada
2 shared publications - Brigitte Pientka
McGill University, Montreal, Canada
1 shared publication - Cassandre Hamel
Université de Montréal, Montréal, Canada
1 shared publication - Frédéric Lahaie-Bertrand
Université de Montréal, Montréal, Canada
1 shared publication - Junyoung Jang
McGill University, Montreal, Canada
1 shared publication - Laurent Huberdeau
Université de Montréal, Montréal, Canada
1 shared publication
Latest Publications
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 14-26
Arborescent Garbage Collection: A Dynamic Graph Approach to Immediate Cycle Collection
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 14-26
Open AccessArborescent Garbage Collection: A Dynamic Graph Approach to Immediate Cycle Collection
- Open Access
- 17 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 70-83
The Design of a Self-Compiling C Transpiler Targeting POSIX Shell
Software supply chain attacks are increasingly frequent and can be hard to guard against. Reproducible builds ensure that generated artifacts (executable programs) can be reliably created from their source code. However, the tools used by the build process are also vulnerable to supply chain attacks so a complete solution must also include reproducible builds for the various compilers used. With this problem as our main motivation we explore the use of the widely available POSIX shell as the only trusted pre-built binary for the reproducible build process. We have developed pnut, a C to POSIX shell transpiler written in C that generates human-readable shell code. Because the compiler is self-applicable, it is possible to distribute a human-readable shell script implementing a C compiler that depends only on the existence of a POSIX compliant shell such as bash, ksh, zsh, etc. Together, pnut and the shell serve as the seed for a chain of builds that create increasingly capable compilers up to the most recent version of the GNU Compiler Collection (GCC) that is a convenient basis to build any other required tool in the toolchain. The end result is a complete build toolchain built only from a shell and human-readable source files. We discuss the level of C language support needed to achieve our goal, the generation of portable POSIX shell code from C, and the performance of the compiler and generated code.
- 17 October 2024
- Published by Association for Computing Machinery (ACM)
- p. 70-83
Open AccessThe Design of a Self-Compiling C Transpiler Targeting POSIX Shell
Software supply chain attacks are increasingly frequent and can be hard to guard against. Reproducible builds ensure that generated artifacts (executable programs) can be reliably created from their source code. However, the tools used by the build process are also vulnerable to supply chain attacks so a complete solution must also include reproducible builds for the various compilers used. With this problem as our main motivation we explore the use of the widely available POSIX shell as the only trusted pre-built binary for the reproducible build process. We have developed pnut, a C to POSIX shell transpiler written in C that generates human-readable shell code. Because the compiler is self-applicable, it is possible to distribute a human-readable shell script implementing a C compiler that depends only on the existence of a POSIX compliant shell such as bash, ksh, zsh, etc. Together, pnut and the shell serve as the seed for a chain of builds that create increasingly capable compilers up to the most recent version of the GNU Compiler Collection (GCC) that is a convenient basis to build any other required tool in the toolchain. The end result is a complete build toolchain built only from a shell and human-readable source files. We discuss the level of C language support needed to achieve our goal, the generation of portable POSIX shell code from C, and the performance of the compiler and generated code.
- Open Access
- 28 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 29-36
Normalizable Types
In dependently typed programming languages, quotients can be introduced in two different ways: elements of each equivalence class can be made either propositionally equal, at the cost of having to manipulate those equality proofs, or definitionally equal, at the cost of requiring a normalization function. The convenience of definitional equality could make the requirement of a normalization function tolerable, if it were not for the fact that those quotients need to be normalized every time we look at them. In the context of proof assistants, this is sometimes acceptable since efficiency of the code is not always relevant, but for a programming language it means these kinds of quotient types (sometimes called normalized types) are usable only with normalization functions which are cheap, and in the end they do not offer very many benefits over the use of smart constructors which eagerly normalize their return value. We propose an adjustment to normalized types that allows manipulating values of such types without having to normalize them, thus offering much finer control over the code’s efficiency, as well as making those quotient types usable even when normalization functions are too costly or impractical at runtime.
- 28 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 29-36
Open AccessNormalizable Types
In dependently typed programming languages, quotients can be introduced in two different ways: elements of each equivalence class can be made either propositionally equal, at the cost of having to manipulate those equality proofs, or definitionally equal, at the cost of requiring a normalization function. The convenience of definitional equality could make the requirement of a normalization function tolerable, if it were not for the fact that those quotients need to be normalized every time we look at them. In the context of proof assistants, this is sometimes acceptable since efficiency of the code is not always relevant, but for a programming language it means these kinds of quotient types (sometimes called normalized types) are usable only with normalization functions which are cheap, and in the end they do not offer very many benefits over the use of smart constructors which eagerly normalize their return value. We propose an adjustment to normalized types that allows manipulating values of such types without having to normalize them, thus offering much finer control over the code’s efficiency, as well as making those quotient types usable even when normalization functions are too costly or impractical at runtime.
- Open Access
- 5 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-9
Design Pattern for Reusing Immutable Methods in Object-Oriented Languages
Context. Features and styles inspired by functional programming have grown in popularity in the world of object-oriented programming. Immutability is a core concept of functional programming, which brings advantages to software development. However, introducing immutability in object-oriented programming presents some challenges. Problem. One of these challenges is method overriding. When inheriting non-destructive mutators (methods used on immutable objects which return a new object instead of modifying the receiver), a naive approach generates code duplication and has scalability issues. Contribution. We analyse an example of this overriding problem and propose a solution in a new design pattern based on the factory method pattern. We also discuss the advantages and limitations of this pattern, as well as implementations in Clojure, Java, and Kotlin. We also identify and discuss the language features that mostly affect the implementation of this pattern. Conclusion. Our proposed design pattern helps mitigate some of the code duplication and scalability problems of a naive approach. However, the inclusion of a functional updating language feature is required to completely remove the scalability issues.
- 5 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-9
Open AccessDesign Pattern for Reusing Immutable Methods in Object-Oriented Languages
Context. Features and styles inspired by functional programming have grown in popularity in the world of object-oriented programming. Immutability is a core concept of functional programming, which brings advantages to software development. However, introducing immutability in object-oriented programming presents some challenges. Problem. One of these challenges is method overriding. When inheriting non-destructive mutators (methods used on immutable objects which return a new object instead of modifying the receiver), a naive approach generates code duplication and has scalability issues. Contribution. We analyse an example of this overriding problem and propose a solution in a new design pattern based on the factory method pattern. We also discuss the advantages and limitations of this pattern, as well as implementations in Clojure, Java, and Kotlin. We also identify and discuss the language features that mostly affect the implementation of this pattern. Conclusion. Our proposed design pattern helps mitigate some of the code duplication and scalability problems of a naive approach. However, the inclusion of a functional updating language feature is required to completely remove the scalability issues.
- Open Access
- 12 January 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (POPL) , 1-27
Mœbius: metaprogramming using contextual types: the stage where system f can pattern match on itself
We describe the foundation of the metaprogramming language, Mœbius, which supports the generation of polymorphic code and, more importantly, the analysis of polymorphic code via pattern matching. Mœbius has two main ingredients: 1) we exploit contextual modal types to describe open code together with the context in which it is meaningful. In Mœbius, open code can depend on type and term variables (level 0) whose values are supplied at a later stage, as well as code variables (level 1) that stand for code templates supplied at a later stage. This leads to a multi-level modal lambda-calculus that supports System-F style polymorphism and forms the basis for polymorphic code generation. 2) we extend the multi-level modal lambda-calculus to support pattern matching on code. As pattern matching on polymorphic code may refine polymorphic type variables, we extend our type-theoretic foundation to generate and track typing constraints that arise. We also give an operational semantics and prove type preservation. Our multi-level modal foundation for Mœbius provides the appropriate abstractions for both generating and pattern matching on open code without committing to a concrete representation of variable binding and contexts. Hence, our work is a step towards building a general type-theoretic foundation for multi-staged metaprogramming that, on the one hand, enforces strong type guarantees and, on the other hand, makes it easy to generate and manipulate code. This will allow us to exploit the full potential of metaprogramming without sacrificing the reliability of and trust in the code we are producing and running.
- 12 January 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (POPL) , 1-27
Open AccessMœbius: metaprogramming using contextual types: the stage where system f can pattern match on itself
We describe the foundation of the metaprogramming language, Mœbius, which supports the generation of polymorphic code and, more importantly, the analysis of polymorphic code via pattern matching. Mœbius has two main ingredients: 1) we exploit contextual modal types to describe open code together with the context in which it is meaningful. In Mœbius, open code can depend on type and term variables (level 0) whose values are supplied at a later stage, as well as code variables (level 1) that stand for code templates supplied at a later stage. This leads to a multi-level modal lambda-calculus that supports System-F style polymorphism and forms the basis for polymorphic code generation. 2) we extend the multi-level modal lambda-calculus to support pattern matching on code. As pattern matching on polymorphic code may refine polymorphic type variables, we extend our type-theoretic foundation to generate and track typing constraints that arise. We also give an operational semantics and prove type preservation. Our multi-level modal foundation for Mœbius provides the appropriate abstractions for both generating and pattern matching on open code without committing to a concrete representation of variable binding and contexts. Hence, our work is a step towards building a general type-theoretic foundation for multi-staged metaprogramming that, on the one hand, enforces strong type guarantees and, on the other hand, makes it easy to generate and manipulate code. This will allow us to exploit the full potential of metaprogramming without sacrificing the reliability of and trust in the code we are producing and running.
- 4 June 2020
- Published by Aspect-Oriented Software Association (AOSA) in The Art, Science, and Engineering of Programming
- Vol. 5 (1) , 1:1-1:26
SMIE: Weakness is Power!
Automatic indentation of source code is fundamentally a simple matter of parsing the code and then applying language- and style-specific rules about relative indentation of the various constructs. Yet, in practice, full parsing is not always an option, either because of quirks of the language, or because the code is temporarily syntactically incorrect, or because of an incomplete or broken grammar. I present the design of Emacs’s Simple-Minded Indentation Engine (SMIE), which gets its power from the weakness of the underlying parsing technique. It makes it possible to perform local parsing, which is hence unaffected by irrelevant surrounding code. This provides a form of graceful degradation in the face of incomplete, erroneous, or just plain problematic information.
- 4 June 2020
- Published by Aspect-Oriented Software Association (AOSA) in The Art, Science, and Engineering of Programming
- Vol. 5 (1) , 1:1-1:26
SMIE: Weakness is Power!
Automatic indentation of source code is fundamentally a simple matter of parsing the code and then applying language- and style-specific rules about relative indentation of the various constructs. Yet, in practice, full parsing is not always an option, either because of quirks of the language, or because the code is temporarily syntactically incorrect, or because of an incomplete or broken grammar. I present the design of Emacs’s Simple-Minded Indentation Engine (SMIE), which gets its power from the weakness of the underlying parsing technique. It makes it possible to perform local parsing, which is hence unaffected by irrelevant surrounding code. This provides a form of graceful degradation in the face of incomplete, erroneous, or just plain problematic information.