← 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

@article{10.1093/jeg/lbab034, author = {Li, Xiaodi}, title = {Do new housing units in your backyard raise your rents?}, journal = {Journal of Economic Geography}, volume = {22}, number = {6}, pages = {1309-1352}, year = {2021}, month = {09}, abstract = {There is a growing debate about whether new housing units increase rents for immediately surrounding apartments. Some argue new market-rate development produces a supply effect, which should alleviate the demand pressure on existing housing units and decrease their rents. Others contend that new development will attract high-income households and new amenities, generating an amenity effect and driving up rents. I contribute to this debate by estimating the impact of new high-rises on nearby residential rents, residential property sales prices and restaurant openings in New York City. To address the selection bias that developers are more likely to build new high-rises in fast-appreciating areas, I restrict the sample to residential properties near approved new high-rises and exploit the plausibly exogenous timing of completion conditional upon the timing of approval. I provide event study evidence that within 500 ft, for every 10\% increase in the housing stock, rents decrease by 1\%; and for every 10\% increase in the condo stock, condo sales prices decrease by 0.9\%. In addition, I show that new high-rises attract new restaurants, which is consistent with the hypothesis about amenity effects. However, I find that the supply effect dominates the amenity effect, causing net reductions in the rents and sales prices of nearby residential properties.}, issn = {1468-2702}, doi = {10.1093/jeg/lbab034}, url = {https://doi.org/10.1093/jeg/lbab034}, eprint = {https://academic.oup.com/joeg/article-pdf/22/6/1309/47258299/lbab034.pdf}, }

@article{10.1162/rest_a_01055, author = {Asquith, Brian J. and Mast, Evan and Reed, Davin}, title = {Local Effects of Large New Apartment Buildings in Low-Income Areas}, journal = {The Review of Economics and Statistics}, volume = {105}, number = {2}, pages = {359-375}, year = {2023}, month = {03}, abstract = {We study the local effects of new market-rate housing in low-income areas using microdata on large apartment buildings, rents, and migration. New buildings decrease rents in nearby units by about 6\% relative to units slightly farther away or near sites developed later, and they increase in-migration from low-income areas. We show that new buildings absorb many high-income households and increase the local housing stock substantially. If buildings improve nearby amenities, the effect is not large enough to increase rents. Amenity improvements could be limited because most buildings go into already-changing neighborhoods or buildings could create disamenities such as congestion.}, issn = {0034-6535}, doi = {10.1162/rest_a_01055}, url = {https://doi.org/10.1162/rest\_a\_01055}, eprint = {https://direct.mit.edu/rest/article-pdf/105/2/359/2073255/rest\_a\_01055.pdf}, }

@inproceedings{Neumann2015UnnestingAQ, title={Unnesting Arbitrary Queries}, author={Thomas Neumann and Alfons Kemper}, booktitle={Datenbanksysteme f{\"u}r Business, Technologie und Web}, year={2015}, url={https://api.semanticscholar.org/CorpusID:15999707} }

@inproceedings{Neumann2024ACO, title={A Critique of Modern SQL and a Proposal Towards a Simple and Expressive Query Language}, author={Thomas Neumann and Viktor Leis}, booktitle={Conference on Innovative Data Systems Research}, year={2024}, url={https://api.semanticscholar.org/CorpusID:268890301} }

@inproceedings{10.5555/3088723.3088749, author = {Boldyreva, Alexandra and Chenette, Nathan and Lee, Younho and O'Neill, Adam}, title = {Order-Preserving Symmetric Encryption}, year = {2009}, isbn = {9783642010002}, publisher = {Springer-Verlag}, address = {Berlin, Heidelberg}, abstract = {We initiate the cryptographic study of order-preserving symmetric encryption OPE, a primitive suggested in the database community by Agrawal et al.\"{\i} \'{z}SIGMOD '04 for allowing efficient range queries on encrypted data. Interestingly, we first show that a straightforward relaxation of standard security notions for encryption such as indistinguishability against chosen-plaintext attack IND-CPA is unachievable by a practical OPE scheme. Instead, we propose a security notion in the spirit of pseudorandom functions PRFs and related primitives asking that an OPE scheme look "as-random-as-possible" subject to the order-preserving constraint. We then design an efficient OPE scheme and prove its security under our notion based on pseudorandomness of an underlying blockcipher. Our construction is based on a natural relation we uncover between a random order-preserving function and the hypergeometric probability distribution. In particular, it makes black-box use of an efficient sampling algorithm for the latter.}, booktitle = {Proceedings of the 28th Annual International Conference on Advances in Cryptology - EUROCRYPT 2009 - Volume 5479}, pages = {224–241}, numpages = {18} }

@inproceedings{10.1145/2808425.2808431, author = {Hwang, Yong Ho and Kim, Sungwook and Seo, Jae Woo}, title = {Fast Order-Preserving Encryption from Uniform Distribution Sampling}, year = {2015}, isbn = {9781450338257}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/2808425.2808431}, doi = {10.1145/2808425.2808431}, booktitle = {Proceedings of the 2015 ACM Workshop on Cloud Computing Security Workshop}, pages = {41–52}, numpages = {12}, keywords = {uniform sampling, symmetric encryption, order-preserving}, location = {Denver, Colorado, USA}, series = {CCSW '15} }

@inproceedings{10.1145/3385412.3386037, author = {Boehm, Hans-J.}, title = {Towards an API for the real numbers}, year = {2020}, isbn = {9781450376136}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3385412.3386037}, doi = {10.1145/3385412.3386037}, abstract = {The real numbers are pervasive, both in daily life, and in mathematics. Students spend much time studying their properties. Yet computers and programming languages generally provide only an approximation geared towards performance, at the expense of many of the nice properties we were taught in high school. Although this is entirely appropriate for many applications, particularly those that are sensitive to arithmetic performance in the usual sense, we argue that there are others where it is a poor choice. If arithmetic computations and result are directly exposed to human users who are not floating point experts, floating point approximations tend to be viewed as bugs. For applications such as calculators, spreadsheets, and various verification tasks, the cost of precision sacrifices is high, and the performance benefit is often not critical. We argue that previous attempts to provide accurate and understandable results for such applications using the recursive reals were great steps in the right direction, but they do not suffice. Comparing recursive reals diverges if they are equal. In many cases, comparison of numbers, including equal ones, is both important, particularly in simple cases, and intractable in the general case. We propose an API for a real number type that explicitly provides decidable equality in the easy common cases, in which it is often unnatural not to. We describe a surprisingly compact and simple implementation in detail. The approach relies heavily on classical number theory results. We demonstrate the utility of such a facility in two applications: testing floating point functions, and to implement arithmetic in Google's Android calculator application.}, booktitle = {Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation}, pages = {562–576}, numpages = {15}, keywords = {real numbers, decidability, comparison, API design}, location = {London, UK}, series = {PLDI 2020} }