← Max Bo

Papers I like

@article{Martens_2025, title={Finite-Choice Logic Programming}, volume={9}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3704849}, DOI={10.1145/3704849}, number={POPL}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Martens, Chris and Simmons, Robert J. and Arntzenius, Michael}, year={2025}, month=jan, pages={362–390} }

@article{10.1145/3236774, author = {Mokhov, Andrey and Mitchell, Neil and Peyton Jones, Simon}, title = {Build systems \`{a} la carte}, year = {2018}, issue_date = {September 2018}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {2}, number = {ICFP}, url = {https://doi.org/10.1145/3236774}, doi = {10.1145/3236774}, abstract = {Build systems are awesome, terrifying -- and unloved. They are used by every developer around the world, but are rarely the object of study. In this paper we offer a systematic, and executable, framework for developing and comparing build systems, viewing them as related points in landscape rather than as isolated phenomena. By teasing apart existing build systems, we can recombine their components, allowing us to prototype new build systems with desired properties.}, journal = {Proc. ACM Program. Lang.}, month = jul, articleno = {79}, numpages = {29}, keywords = {functional programming, build systems, algorithms} }

@article{Crichton_2024, title={A Core Calculus for Documents: Or, Lambda: The Ultimate Document}, volume={8}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3632865}, DOI={10.1145/3632865}, number={POPL}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Crichton, Will and Krishnamurthi, Shriram}, year={2024}, month=jan, pages={667–694} }

@misc{omar2018livefunctionalprogrammingtyped, title={Live Functional Programming with Typed Holes}, author={Cyrus Omar and Ian Voysey and Ravi Chugh and Matthew A. Hammer}, year={2018}, eprint={1805.00155}, archivePrefix={arXiv}, primaryClass={cs.PL}, url={https://arxiv.org/abs/1805.00155}, }

@misc{fung2021simplestandsurprisingsorting, title={Is this the simplest (and most surprising) sorting algorithm ever?}, author={Stanley P. Y. Fung}, year={2021}, eprint={2110.01111}, archivePrefix={arXiv}, primaryClass={cs.DS}, url={https://arxiv.org/abs/2110.01111}, }

@article{mcclellan2012, doi = {10.1088/1748-9326/7/3/034019}, url = {https://dx.doi.org/10.1088/1748-9326/7/3/034019}, year = {2012}, month = {aug}, publisher = {IOP Publishing}, volume = {7}, number = {3}, pages = {034019}, author = {Justin McClellan and David W Keith and Jay Apt}, title = {Cost analysis of stratospheric albedo modification delivery systems}, journal = {Environmental Research Letters}}

@article{Graf_2022, title={Binary Fuse Filters: Fast and Smaller Than Xor Filters}, volume={27}, ISSN={1084-6654}, url={http://dx.doi.org/10.1145/3510449}, DOI={10.1145/3510449}, journal={ACM Journal of Experimental Algorithmics}, publisher={Association for Computing Machinery (ACM)}, author={Graf, Thomas Mueller and Lemire, Daniel}, year={2022}, month=mar, pages={1–15} }

@misc{wydrowski2023loadbalanceintroducingprequal, title={Load is not what you should balance: Introducing Prequal}, author={Bartek Wydrowski and Robert Kleinberg and Stephen M. Rumble and Aaron Archer}, year={2023}, eprint={2312.10172}, archivePrefix={arXiv}, primaryClass={cs.DC}, url={https://arxiv.org/abs/2312.10172}, }

@misc{park2024iclrincontextlearningrepresentations, title={ICLR: In-Context Learning of Representations}, author={Core Francisco Park and Andrew Lee and Ekdeep Singh Lubana and Yongyi Yang and Maya Okawa and Kento Nishi and Martin Wattenberg and Hidenori Tanaka}, year={2024}, eprint={2501.00070}, archivePrefix={arXiv}, primaryClass={cs.CL}, url={https://arxiv.org/abs/2501.00070}, }

@misc{libkind2024patternrunsmatterfree, title={Pattern runs on matter: The free monad monad as a module over the cofree comonad comonad}, author={Sophie Libkind and David I. Spivak}, year={2024}, eprint={2404.16321}, archivePrefix={arXiv}, primaryClass={math.CT}, url={https://arxiv.org/abs/2404.16321}, }

@article{10.1145/3607840, author = {Lorenzen, Anton and Leijen, Daan and Swierstra, Wouter}, title = {FP²: Fully in-Place Functional Programming}, year = {2023}, issue_date = {August 2023}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {7}, number = {ICFP}, url = {https://doi.org/10.1145/3607840}, doi = {10.1145/3607840}, abstract = {As functional programmers we always face a dilemma: should we write purely functional code, or sacrifice purity for efficiency and resort to in-place updates? This paper identifies precisely when we can have the best of both worlds: a wide class of purely functional programs can be executed safely using in-place updates without requiring allocation, provided their arguments are not shared elsewhere. We describe a linear _fully in-place_ (FIP) calculus where we prove that we can always execute such functions in a way that requires no (de)allocation and uses constant stack space. Of course, such a calculus is only relevant if we can express interesting algorithms; we provide numerous examples of in-place functions on datastructures such as splay trees or finger trees, together with in-place versions of merge sort and quick sort. We also show how we can generically derive a map function over _any_ polynomial data type that is fully in-place. Finally, we have implemented the rules of the FIP calculus in the Koka language. Using the Perceus reference counting garbage collection, this implementation dynamically executes FIP functions in-place whenever possible.}, journal = {Proc. ACM Program. Lang.}, month = aug, articleno = {198}, numpages = {30}, keywords = {FBIP, Tail Recursion Modulo Cons} }

@article{10.1145/3607845, author = {Augustsson, Lennart and Breitner, Joachim and Claessen, Koen and Jhala, Ranjit and Peyton Jones, Simon and Shivers, Olin and Steele Jr., Guy L. and Sweeney, Tim}, title = {The Verse Calculus: A Core Calculus for Deterministic Functional Logic Programming}, year = {2023}, issue_date = {August 2023}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {7}, number = {ICFP}, url = {https://doi.org/10.1145/3607845}, doi = {10.1145/3607845}, abstract = {Functional logic languages have a rich literature, but it is tricky to give them a satisfying semantics. In this paper we describe the Verse calculus, VC, a new core calculus for deterministic functional logic programming. Our main contribution is to equip VC with a small-step rewrite semantics, so that we can reason about a VC program in the same way as one does with lambda calculus; that is, by applying successive rewrites to it. We also show that the rewrite system is confluent for well-behaved terms.}, journal = {Proc. ACM Program. Lang.}, month = aug, articleno = {203}, numpages = {31}, keywords = {Verse calculus, Verse language, choice operator, confluence, declarative programming, evaluation strategy, even/odd problem, functional programming, lambda calculus, lenient evaluation, logic programming, logical variables, normal forms, rewrite rules, skew confluence, substitution, unification} }

@article{DUNNING2021100049, title = {The t-digest: Efficient estimates of distributions}, journal = {Software Impacts}, volume = {7}, pages = {100049}, year = {2021}, issn = {2665-9638}, doi = {https://doi.org/10.1016/j.simpa.2020.100049}, url = {https://www.sciencedirect.com/science/article/pii/S2665963820300403}, author = {Ted Dunning}, keywords = {Quantile estimation, t-digest, OLAP database, Open-source, Greenwald–Khanna algorithm}, abstract = {The t-digest is an on-line algorithm for building small sketches of data that can be used to approximate rank-based statistics with high accuracy, particularly near the tails. This new kind of sketch is robust with respect to skewed distributions, repeated samples and ordered datasets. Separately computed sketches can be combined with little or no loss in accuracy. An open-source Java implementation with no external dependencies of this algorithm is available as a free-standing library. Independent implementations in Go, C++ and Python are available. The t-digest is in widespread internal use in major companies and is also available in popular software such as Postgres, ElasticSearch, Apache Kylin and Apache Druid. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.} }

@article{Masson_2019, title={DDSketch: a fast and fully-mergeable quantile sketch with relative-error guarantees}, volume={12}, ISSN={2150-8097}, url={http://dx.doi.org/10.14778/3352063.3352135}, DOI={10.14778/3352063.3352135}, number={12}, journal={Proceedings of the VLDB Endowment}, publisher={Association for Computing Machinery (ACM)}, author={Masson, Charles and Rim, Jee E. and Lee, Homin K.}, year={2019}, month=aug, pages={2195–2205} }

10.1.1.76.4286

@article{10.1145/3555644, author = {Litt, Geoffrey and Lim, Sarah and Kleppmann, Martin and van Hardenberg, Peter}, title = {Peritext: A CRDT for Collaborative Rich Text Editing}, year = {2022}, issue_date = {November 2022}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {6}, number = {CSCW2}, url = {https://doi.org/10.1145/3555644}, doi = {10.1145/3555644}, abstract = {Conflict-Free Replicated Data Types (CRDTs) support decentralized collaborative editing of shared data, enabling peer-to-peer sharing and flexible branching and merging workflows. While there is extensive work on CRDTs for plain text, much less is known about CRDTs for rich text with formatting. No algorithms have been published, and existing open-source implementations do not always preserve user intent.In this paper, we describe a model of intent preservation in rich text editing, developed through a series of concurrent editing scenarios. We then describe Peritext, a CRDT algorithm for rich text that satisfies the criteria of our model. The key idea is to store formatting spans alongside the plaintext character sequence, linked to a stable identifier for the first and last character of each span, and then to derive the final formatted text from these spans in a deterministic way that ensures concurrent operations commute.We have prototyped our algorithm in TypeScript, validated it using randomized property-based testing, and integrated it with an editor UI. We also prove that our algorithm ensures convergence, and demonstrate its causality preservation and intention preservation properties.}, journal = {Proc. ACM Hum.-Comput. Interact.}, month = nov, articleno = {531}, numpages = {36}, keywords = {rich text, conflict-free replicated data types, collaborative editing, asynchronous collaboration} }

@article{10.1145/3212477.3212479, author = {Chisnall, David}, title = {C Is Not a Low-level Language: Your computer is not a fast PDP-11.}, year = {2018}, issue_date = {March-April 2018}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {16}, number = {2}, issn = {1542-7730}, url = {https://doi.org/10.1145/3212477.3212479}, doi = {10.1145/3212477.3212479}, abstract = {In the wake of the recent Meltdown and Spectre vulnerabilities, it’s worth spending some time looking at root causes. Both of these vulnerabilities involved processors speculatively executing instructions past some kind of access check and allowing the attacker to observe the results via a side channel. The features that led to these vulnerabilities, along with several others, were added to let C programmers continue to believe they were programming in a low-level language, when this hasn’t been the case for decades.}, journal = {Queue}, month = apr, pages = {18–30}, numpages = {13} }

10.1371/journal.pone.0199239