Controlling Copatterns: There and Back Again

Paul Downen · 2025

Read Controlling Copatterns: There and Back Again by Paul Downen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-12427.txt.

Introduction

Copatterns let a functional program answer its context in flexible ways, but that freedom makes program behavior hard to pin down. Paul Downen works through that problem alone in a 2025 paper, building a full set of meanings for copatterns in two passes.

Downen starts with a simple calculus of whole copatterns and walks it through several standard forms, from step-by-step rules to an abstract machine to continuation-passing style. He then reshapes the style version into a richer calculus where copatterns compose, and walks back the other way to derive matching forms in reverse. The round trip gives language designers a checked map between ways of defining what copattern programs do.

Catalog record

CREATORPaul Downen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-12427

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Controlling Copatterns: There and Back Again Paul Downen Abstract . Copatterns give functional programs a flexible mechanism for responding to their context, and composition can greatly enhance their expressiveness. However, that same expressive power makes it harder to precisely specify the behavior of programs. Using Danvy’s functional and syntactic correspondence between different semantic artifacts, we derive a full suite of semantics for copatterns, twice. First, a calculus of monolithic copatterns is taken on a journey from small-step operational semantics to abstract machine to continuation-passing style. Then within continuation-passing style, we refactor the semantics to derive a more general calculus of compositional copatterns, and take the return journey back to derive the other semantic artifacts in reverse order. DOI: 10.1145/3759427.3760362 ISBN: 979-8-4007-2150-2/25/10 Conference: Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday; October 12–18, 2025; Singapore, Singapore Proceedings of the Workshop Dedicated to Olivier Danvy on the Occasion of His 64th Birthday (OLIVIERFEST ’25), October 12–18, 2025, Singapore, Singapore CCS: Software and its engineering Patterns CCS: Software and its engineering Interpreters CCS: Theory of computation Control primitives CCS: Theory of computation Operational semantics CCS: Theory of computation Abstract machines Extended Version † † cc-license: by 1. Introduction Pattern matching—a common feature among functional languages that expresses complex traversals over trees—can be made even more powerful through a modern extension: copatterns ( Abel et al., 2013 ) . The dual to patterns, copatterns let multi-clause definitions match over more information in their calling context, reacting to the structure of projections in addition to the structure of arguments. In contrast to Haskell-style lazy data structures, copatterns are especially useful for modeling and manipulating infinite information like streams in settings that are more sensitive to termination like proof assistants and eager languages. Compositional copatterns —as recently implemented as a Scheme macro library ( Downen and Corbelino II, 2025 ) —extend copatterns with new ways to combine and apply partially-defined, context-sensitive code using a fusion of functional and object-oriented techniques. For example, a (lazy) pair can be represented in Scheme as procedure that takes ‘ fst or ‘ snd as an argument and returns the respective element. The two-by-two nested pair ((1,2),(3,4)) can then be defined through multiple equations describing chains of projection like so: ⬇ [(( quad ‘ fst ) ‘ fst ) = 1] [(( quad ‘ fst ) ‘ snd ) = 2] [(( quad ‘ snd ) ‘ fst ) = 3] [(( quad ‘ snd ) ‘ snd ) = 4]) Suppose we want to override the diagonal elements—the first of the first, and the second of the second—with new values. The function ( diag x y z ) below returns x as the very first, y as the very last, and is the same as z elsewhere ⬇ [((( diag x y z ) ‘ fst ) ‘ fst ) = x ] [((( diag x y z ) ‘ snd ) ‘ snd ) = y ] [ ( diag x y z ) = z ]) so that ( diag 50 60 quad ) represents ((50,2),(3,60)) . Notice the use of the third “fall-through” case taken whenever the first two cases don’t apply. Crucially, the context this fall-through case matches is less specified than the earlier cases, so ((( diag 50 60 quad ) ‘ snd ) ‘ fst ) should simplify to (( quad ‘ snd ) ‘ fst ) = 3 . Effectively, the above 3-clause definition of diag on two-by-two pairs is short-hand for the following expansion that manually elaborates all four cases: ⬇ ( define * [((( diag x y z ) ‘ fst ) ‘ fst ) = x ] [((( diag x y z ) ‘ snd ) ‘ snd ) = y ] [((( diag x y z ) ‘ fst ) ‘ snd ) = (( z ‘ fst ) ‘ snd )] [((( diag x y z ) ‘ snd ) ‘ fst ) = (( z ‘ snd ) ‘ fst )]) As the notation suggests, we can understand this code through equational reasoning—replacing call sites matching the left-hand side with the right-hand side. However, it is not so obvious how to convert this into an operational semantics capable of directly calculating the result of any source-level program, without elaborations like the above. This becomes even more challenging when taking into account other forms of higher-order composition that can be performed at run-time: multiple clauses can be stitched together vertically to handle undefined cases, and individual clauses can be extended horizontally to consider more context or side conditions before committing to a right-hand side. The implementation ( Downen and Corbelino II, 2025 ) gives a semantics based on macro expansion into a small subset of Scheme ( i.e., \lambda -calculus), but only describes the semantics via translation to the target language and not in terms of the source-level language itself. Thankfully, there is a general-purpose technique for converting one form of semantics into another! Danvy’s functional correspondence ( Ager et al., 2003 ) and syntactic correspondence ( Biernacka and Danvy, 2007 ) show how to use off-the-shelf program transformations to derive semantic artifacts—operational semantics, abstract machines, and continuation-passing style transformations—from one another in a way that is correct by construction. In other words, we can (mostly mechanically) generate functional and correct operational semantics directly from the macro definition implementing copatterns ( Downen and Corbelino II, 2025 ) . Yet, this is not just an exercise of turning the crank. Doing so reveals connections between copattern matching with delimited control and a form of first-class handlers. Our journey today is a round-trip hike in the semantic park. Starting from a simplified source copattern calculus with a straightforward operational semantics, we derive its corresponding continuation-passing style (CPS) transformation. Then after making a few adjustments generalizing it to match the macro definition found in ( Downen and Corbelino II, 2025 ) , we turn around and walk backwards to derive a direct-style operational semantics for compositional copattern matching. More specifically, our technical contributions are as follows: • ( Section 3 ) We derive a trio of semantic artifacts for a monolithic copattern calculus—small-step operational semantics, abstract machine, and continuation-passing style (CPS) translation—through a mechanical derivation based on functional code for copattern matching on contexts and a search to find the next redex. • ( Section 4 ) We refactor the monolithic copattern calculus into more compositional primitives that give first-class control over (1) the (delimited) calling context and (2) the options for how to handle match failure. The CPS translation corresponds to the macro definition in ( Downen and Corbelino II, 2025 ) , and shows that the compositional calculus is a conservative extension of the monolithic one. • ( Section 5 ) Going in reverse, we walk back from the CPS translation of compositional copatterns and derive the missing semantic artifacts—an abstract machine and small-step operational semantics—that correspond by construction to the CPS translation. The main highlights of these derivations are shown here, illustrating the Haskell code that corresponds to the various semantic artifacts for copattern matching. To find the detailed step-by-step process, which serves as their proof of correctness, see https://github.com/pdownen/derive-copat .

Read the complete text