The Functional Essence of Imperative Binary Search Trees
Anton Lorenzen, Daan Leijen, Wouter Swierstra, Sam Lindley
PLDI'24 | June 2024
Publications
Publications
Publications by Year
-
Tail Recursion Modulo Context: An Equational Approach (extended version)
Daan Leijen, Anton Lorenzen
under submission to JFP. | May 2024
This is an extended version of the POPL'23 publication under submission to a special issue of the Journal of Functional Programming (JFP). Extended topics include an improved TRMC algorithm, composing contexts, _field_ contexts, and first-class constructor contexts.
-
Qualified Effect Types — Taming Control-Flow through Linear Effect Handlers
Jonathan Immanuel Brachthäuser, Daan Leijen
MSR-TR-2023-42 | November 2023
Published by Microsoft
This technical report is the result of an internship of Jonathan Brachthäuser at Microsoft Research, Redmond in 2018. While the report is published in 2023, the paper reflects the work at the time of writing.
Continuing WebAssembly with Effect Handlers
LUNA PHIPPS-COSTIN, ANDREAS ROSSBERG, ARJUN GUHA, Daan Leijen, DANIEL HILLERSTRÖM, KC SIVARAMAKRISHNAN, MATIJA PRETNAR, SAM LINDLEY
OOPSLA'23 | October 2023
FP$^2$: Fully in-Place Functional Programming
Anton Lorenzen, Daan Leijen, Wouter Swierstra
ICFP 2023 | September 2023
preprint
Exploring Perceus for OCaml
Elton Pinto, Daan Leijen
September 2023
Presented at the "Higher order, Typed, Strict: ML Family Workshop 2023" co-located with ICFP'23.
The Functional Essence of Imperative Binary Search Trees
Anton Lorenzen, Daan Leijen, Wouter Swierstra, Sam Lindley
MSR-TR-2023-28 | July 2023
Published by Microsoft
v4, Dec 27, 2023 (previously titled "A Functional Correspondence between Top-down and Bottom-up Tree Algorithms") This is an extended version of the PLDI'24 publication.
FP^2: Fully in-Place Functional Programming (TR)
Anton Lorenzen, Daan Leijen, Wouter Swierstra
MSR-TR-2023-19 | May 2023
Published by Microsoft
Extended version of the ICFP'23 publication
Tail Recursion Modulo Context: An Equational Approach
Daan Leijen, Anton Lorenzen
POPL'23 | January 2023
-
Reference counting with frame limited reuse
Anton Lorenzen, Daan Leijen
ICFP'22 | August 2022
What About the Integer Numbers? Fast Arithmetic with Tagged Integers — A Plea for Hardware Support
MSR-TR-2022-17 | July 2022
Published by Microsoft
Presented at ML language workshop 2022 (co-located with ICFP'22).
Tail Recursion Modulo Context — An Equational Approach
Daan Leijen, Anton Lorenzen
MSR-TR-2022-18 | July 2022
Published by Microsoft
-
Reference Counting with Frame Limited Reuse (extended version, v2)
Anton Lorenzen, Daan Leijen
MSR-TR-2021-30 | November 2021
Published by Microsoft
Mar 15, 2022, v2
Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C)
Ningning Xie, Daan Leijen
Proc. ACM Prog. Lang. (ICFP'21) | August 2021, Vol 5(ICFP): pp. 71
doi: 10.1145/3473576
Perceus: Garbage Free Reference Counting with Reuse
Alex Reinking*, Ningning Xie*, Leonardo de Moura, Daan Leijen
The 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI ’21) | June 2021
(*) The first two authors contributed equally to this work. Distinguished paper at PLDI'21.
First-class Named Effect Handlers
Ningning Xie, Youyou Cong, Daan Leijen
MSR-TR-2021-10 | May 2021
Published by Microsoft
Presented at the 8th ACM SIGPLAN Workshop on Higher-Order Programming with Effects (HOPE'21).
Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C) (Extended Version)
Ningning Xie, Daan Leijen
MSR-TR-2021-5 | March 2021
Published by Microsoft
v4, 2021-06-07. Extended version of the ICFP'21 paper.
-
Perceus: Garbage Free Reference Counting with Reuse (Extended version)
Alex Reinking*, Ningning Xie*, Leonardo de Moura, Daan Leijen
MSR-TR-2020-42 | November 2020
Published by Microsoft
(*) The first two authors contributed equally to this work. v4, 2021-06-07. Extended version of the PLDI'21 paper.
Effect Handlers in Haskell, Evidently
Ningning Xie, Daan Leijen
The 13th ACM SIGPLAN International Haskell Symposium | August 2020
Effect Handlers, Evidently
Ningning Xie, Jonathan Brachthauser, Daniel Hillerstrom, Philipp Schuster, Daan Leijen
The 25th ACM SIGPLAN International Conference on Functional Programming (ICFP) | August 2020
Effect Handlers, Evidently (Extended Version)
Ningning Xie, Jonathan Brachthauser, Daniel Hillerstrom, Philipp Schuster, Daan Leijen
MSR-TR-2020-23 | July 2020
Published by Microsoft
Extended version of the ICFP'20 article.
-
Structured Asynchrony with Algebraic Effects
MSR-TR-2017-21 | May 2017
Type Directed Compilation of Row-Typed Algebraic Effects
Proceedings of Principles of Programming Languages (POPL'17), Paris, France | January 2017
-
Algebraic Effects for Functional Programming
MSR-TR-2016-29 | August 2016
-
Koka: Programming with Row Polymorphic Effect Types
Mathematically Structured Functional Programming 2014 | March 2014
-
Koka: Programming with Row-Polymorphic Effect Types
MSR-TR-2013-79 | August 2013
Published by Microsoft
Publications by Research Area
-
The Functional Essence of Imperative Binary Search Trees
Anton Lorenzen, Daan Leijen, Wouter Swierstra, Sam Lindley
PLDI'24 | June 2024
Tail Recursion Modulo Context: An Equational Approach (extended version)
Daan Leijen, Anton Lorenzen
under submission to JFP. | May 2024
This is an extended version of the POPL'23 publication under submission to a special issue of the Journal of Functional Programming (JFP). Extended topics include an improved TRMC algorithm, composing contexts, _field_ contexts, and first-class constructor contexts.
Qualified Effect Types — Taming Control-Flow through Linear Effect Handlers
Jonathan Immanuel Brachthäuser, Daan Leijen
MSR-TR-2023-42 | November 2023
Published by Microsoft
This technical report is the result of an internship of Jonathan Brachthäuser at Microsoft Research, Redmond in 2018. While the report is published in 2023, the paper reflects the work at the time of writing.
Continuing WebAssembly with Effect Handlers
LUNA PHIPPS-COSTIN, ANDREAS ROSSBERG, ARJUN GUHA, Daan Leijen, DANIEL HILLERSTRÖM, KC SIVARAMAKRISHNAN, MATIJA PRETNAR, SAM LINDLEY
OOPSLA'23 | October 2023
FP$^2$: Fully in-Place Functional Programming
Anton Lorenzen, Daan Leijen, Wouter Swierstra
ICFP 2023 | September 2023
preprint
Exploring Perceus for OCaml
Elton Pinto, Daan Leijen
September 2023
Presented at the "Higher order, Typed, Strict: ML Family Workshop 2023" co-located with ICFP'23.
The Functional Essence of Imperative Binary Search Trees
Anton Lorenzen, Daan Leijen, Wouter Swierstra, Sam Lindley
MSR-TR-2023-28 | July 2023
Published by Microsoft
v4, Dec 27, 2023 (previously titled "A Functional Correspondence between Top-down and Bottom-up Tree Algorithms") This is an extended version of the PLDI'24 publication.
FP^2: Fully in-Place Functional Programming (TR)
Anton Lorenzen, Daan Leijen, Wouter Swierstra
MSR-TR-2023-19 | May 2023
Published by Microsoft
Extended version of the ICFP'23 publication
Tail Recursion Modulo Context: An Equational Approach
Daan Leijen, Anton Lorenzen
POPL'23 | January 2023
Reference counting with frame limited reuse
Anton Lorenzen, Daan Leijen
ICFP'22 | August 2022
What About the Integer Numbers? Fast Arithmetic with Tagged Integers — A Plea for Hardware Support
MSR-TR-2022-17 | July 2022
Published by Microsoft
Presented at ML language workshop 2022 (co-located with ICFP'22).
Tail Recursion Modulo Context — An Equational Approach
Daan Leijen, Anton Lorenzen
MSR-TR-2022-18 | July 2022
Published by Microsoft
Reference Counting with Frame Limited Reuse (extended version, v2)
Anton Lorenzen, Daan Leijen
MSR-TR-2021-30 | November 2021
Published by Microsoft
Mar 15, 2022, v2
Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C)
Ningning Xie, Daan Leijen
Proc. ACM Prog. Lang. (ICFP'21) | August 2021, Vol 5(ICFP): pp. 71
doi: 10.1145/3473576
Perceus: Garbage Free Reference Counting with Reuse
Alex Reinking*, Ningning Xie*, Leonardo de Moura, Daan Leijen
The 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI ’21) | June 2021
(*) The first two authors contributed equally to this work. Distinguished paper at PLDI'21.
First-class Named Effect Handlers
Ningning Xie, Youyou Cong, Daan Leijen
MSR-TR-2021-10 | May 2021
Published by Microsoft
Presented at the 8th ACM SIGPLAN Workshop on Higher-Order Programming with Effects (HOPE'21).
Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C) (Extended Version)
Ningning Xie, Daan Leijen
MSR-TR-2021-5 | March 2021
Published by Microsoft
v4, 2021-06-07. Extended version of the ICFP'21 paper.
Perceus: Garbage Free Reference Counting with Reuse (Extended version)
Alex Reinking*, Ningning Xie*, Leonardo de Moura, Daan Leijen
MSR-TR-2020-42 | November 2020
Published by Microsoft
(*) The first two authors contributed equally to this work. v4, 2021-06-07. Extended version of the PLDI'21 paper.
Effect Handlers in Haskell, Evidently
Ningning Xie, Daan Leijen
The 13th ACM SIGPLAN International Haskell Symposium | August 2020
Effect Handlers, Evidently
Ningning Xie, Jonathan Brachthauser, Daniel Hillerstrom, Philipp Schuster, Daan Leijen
The 25th ACM SIGPLAN International Conference on Functional Programming (ICFP) | August 2020
Effect Handlers, Evidently (Extended Version)
Ningning Xie, Jonathan Brachthauser, Daniel Hillerstrom, Philipp Schuster, Daan Leijen
MSR-TR-2020-23 | July 2020
Published by Microsoft
Extended version of the ICFP'20 article.
Structured Asynchrony with Algebraic Effects
MSR-TR-2017-21 | May 2017
Type Directed Compilation of Row-Typed Algebraic Effects
Proceedings of Principles of Programming Languages (POPL'17), Paris, France | January 2017
Algebraic Effects for Functional Programming
MSR-TR-2016-29 | August 2016
Koka: Programming with Row Polymorphic Effect Types
Mathematically Structured Functional Programming 2014 | March 2014
Koka: Programming with Row-Polymorphic Effect Types
MSR-TR-2013-79 | August 2013
Published by Microsoft
Publications by Type
-
The Functional Essence of Imperative Binary Search Trees
Anton Lorenzen, Daan Leijen, Wouter Swierstra, Sam Lindley
PLDI'24 | June 2024
Continuing WebAssembly with Effect Handlers
LUNA PHIPPS-COSTIN, ANDREAS ROSSBERG, ARJUN GUHA, Daan Leijen, DANIEL HILLERSTRÖM, KC SIVARAMAKRISHNAN, MATIJA PRETNAR, SAM LINDLEY
OOPSLA'23 | October 2023
FP$^2$: Fully in-Place Functional Programming
Anton Lorenzen, Daan Leijen, Wouter Swierstra
ICFP 2023 | September 2023
preprint
Tail Recursion Modulo Context: An Equational Approach
Daan Leijen, Anton Lorenzen
POPL'23 | January 2023
Reference counting with frame limited reuse
Anton Lorenzen, Daan Leijen
ICFP'22 | August 2022
Perceus: Garbage Free Reference Counting with Reuse
Alex Reinking*, Ningning Xie*, Leonardo de Moura, Daan Leijen
The 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI ’21) | June 2021
(*) The first two authors contributed equally to this work. Distinguished paper at PLDI'21.
Effect Handlers in Haskell, Evidently
Ningning Xie, Daan Leijen
The 13th ACM SIGPLAN International Haskell Symposium | August 2020
Effect Handlers, Evidently
Ningning Xie, Jonathan Brachthauser, Daniel Hillerstrom, Philipp Schuster, Daan Leijen
The 25th ACM SIGPLAN International Conference on Functional Programming (ICFP) | August 2020
Type Directed Compilation of Row-Typed Algebraic Effects
Proceedings of Principles of Programming Languages (POPL'17), Paris, France | January 2017
Koka: Programming with Row Polymorphic Effect Types
Mathematically Structured Functional Programming 2014 | March 2014
-
Tail Recursion Modulo Context: An Equational Approach (extended version)
Daan Leijen, Anton Lorenzen
under submission to JFP. | May 2024
This is an extended version of the POPL'23 publication under submission to a special issue of the Journal of Functional Programming (JFP). Extended topics include an improved TRMC algorithm, composing contexts, _field_ contexts, and first-class constructor contexts.
Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C)
Ningning Xie, Daan Leijen
Proc. ACM Prog. Lang. (ICFP'21) | August 2021, Vol 5(ICFP): pp. 71
doi: 10.1145/3473576
-
Qualified Effect Types — Taming Control-Flow through Linear Effect Handlers
Jonathan Immanuel Brachthäuser, Daan Leijen
MSR-TR-2023-42 | November 2023
Published by Microsoft
This technical report is the result of an internship of Jonathan Brachthäuser at Microsoft Research, Redmond in 2018. While the report is published in 2023, the paper reflects the work at the time of writing.
The Functional Essence of Imperative Binary Search Trees
Anton Lorenzen, Daan Leijen, Wouter Swierstra, Sam Lindley
MSR-TR-2023-28 | July 2023
Published by Microsoft
v4, Dec 27, 2023 (previously titled "A Functional Correspondence between Top-down and Bottom-up Tree Algorithms") This is an extended version of the PLDI'24 publication.
FP^2: Fully in-Place Functional Programming (TR)
Anton Lorenzen, Daan Leijen, Wouter Swierstra
MSR-TR-2023-19 | May 2023
Published by Microsoft
Extended version of the ICFP'23 publication
What About the Integer Numbers? Fast Arithmetic with Tagged Integers — A Plea for Hardware Support
MSR-TR-2022-17 | July 2022
Published by Microsoft
Presented at ML language workshop 2022 (co-located with ICFP'22).
Tail Recursion Modulo Context — An Equational Approach
Daan Leijen, Anton Lorenzen
MSR-TR-2022-18 | July 2022
Published by Microsoft
Reference Counting with Frame Limited Reuse (extended version, v2)
Anton Lorenzen, Daan Leijen
MSR-TR-2021-30 | November 2021
Published by Microsoft
Mar 15, 2022, v2
First-class Named Effect Handlers
Ningning Xie, Youyou Cong, Daan Leijen
MSR-TR-2021-10 | May 2021
Published by Microsoft
Presented at the 8th ACM SIGPLAN Workshop on Higher-Order Programming with Effects (HOPE'21).
Generalized Evidence Passing for Effect Handlers (or, Efficient Compilation of Effect Handlers to C) (Extended Version)
Ningning Xie, Daan Leijen
MSR-TR-2021-5 | March 2021
Published by Microsoft
v4, 2021-06-07. Extended version of the ICFP'21 paper.
Perceus: Garbage Free Reference Counting with Reuse (Extended version)
Alex Reinking*, Ningning Xie*, Leonardo de Moura, Daan Leijen
MSR-TR-2020-42 | November 2020
Published by Microsoft
(*) The first two authors contributed equally to this work. v4, 2021-06-07. Extended version of the PLDI'21 paper.
Effect Handlers, Evidently (Extended Version)
Ningning Xie, Jonathan Brachthauser, Daniel Hillerstrom, Philipp Schuster, Daan Leijen
MSR-TR-2020-23 | July 2020
Published by Microsoft
Extended version of the ICFP'20 article.
Structured Asynchrony with Algebraic Effects
MSR-TR-2017-21 | May 2017
Algebraic Effects for Functional Programming
MSR-TR-2016-29 | August 2016
Koka: Programming with Row-Polymorphic Effect Types
MSR-TR-2013-79 | August 2013
Published by Microsoft
-
Exploring Perceus for OCaml
Elton Pinto, Daan Leijen
September 2023
Presented at the "Higher order, Typed, Strict: ML Family Workshop 2023" co-located with ICFP'23.
People
Daan Leijen
Principal Researcher