Functional patterns & API/implementation independence
Two great tastes that (could) go great together

What if we could combine chocolate and peanut butter? That'd be amazing, right!

Functional programming (FP) and object-oriented programming (OOP) provide very different toolboxes for defining types. FP gives us algebraic data types (ADTs) which excel in closed-domain modelling and mesh well with pattern matching. OOP gives us encapsulation, information hiding, and the ability to evolve a type's internals without breaking everyone who depends on it, essential for programming in the large¹. But OOP because of that encapsulation inspecting and teasing apart objects often requires many method calls spread across many statements.

This article will tour what makes each approach great, look at where they each fall short, and then sketch out how an OOP language could deliver FP style pattern matching without layering on ADTs as a separate type definition mechanism ².

The contribution is identifying problems and workarounds in languages that were not designed to support pattern matching that, if used, allow desugaring rich pattern match syntax to existing, simpler constructs:

• Provide stable views of potentially unstable objects to avoid TOCTOU problems.
• Define an abstraction that allows a separation of duties between types' pattern decomposers and compilers' decision tree builders.
• Explain how test prerequisites allow safely decomposing values like OOP PL's indexed sequences, which are not step-wise decomposable the way Lisp's cons lists are.
• Suggest explicit syntax cues to avoid left/right identifier confusion in patterns which occurs more often in OOP languages where variables are, by default, re-assignable.
• Where possible exploit meta-programming to enable familiar pattern syntax for values with well-understood textual forms.

A Motivating Example: HTTP Responses

Everybody has wrestled with handling an HTTP response; they're complex objects with lots of bells and whistles, and on receiving one, it often needs to be routed to the right handler code. What if we tried to handle one using OCaml style patterns.

match response with
| { ok = false; status } ->
    handle_error ("unexpected response: " ^ string_of_int status)
| { shortMimeType = ("application", "json"); json } ->
    handle_json json
| { status = 307; headers } ->
    fetch_async (headers.location) handle_json
| _ ->
    handle_error "unrecognised response"

This is pleasingly direct. The boilerplate, the fixed parts of the value we're testing against, tells us which case we're in. The non-boilerplate parts (status, json, headers) are in scope for action code. Its expressive and succinct, making logic bugs easier to find.

Patterns let us match nice things

Pattern matching is powerful because it reuses value look-alikes to specify both decision and extraction. The fixed parts of a value (the boilerplate) decide which action to take. The variable parts are available in the action code.

Here's the previous example with the fixed and variable parts explicitly called out.

(* Fixed parts formatted like this, variable parts like this *)
match response with
| { ok = false; status } ->
    handle_error ("unexpected response: " ^ string_of_int status)
| { shortMimeType = ("application", "json"); json } ->
    handle_json json
| { status = 307; headers } ->
    fetch_async (headers.location) handle_json
| _ ->
    handle_error "unrecognised response"

In our HTTP example, the boilerplate parts — whether ok is true or false, what status code we got, the major and minor components of the MIME type — are all drawn from sets that are, in practice, closed. (Status codes are an IANA registry. MIME types have a finite set of well-known values that cover the vast majority of real-world usage.)

The FP View: ADTs

To get clean pattern matching in OCaml, we'd define the response as a record. The thorny bits (how to stream the body, how to release resources like network pipes, how to access rarely-used headers) get sequestered into a separate type that is routed around without the match having to care about them:

type response_extras = { (* headers, body stream, etc. *) }

type response = {
  status        : int;
  ok            : bool;
  shortMimeType : string * string;   (* major, minor *)
  headers       : (string * string) list;
  json          : json_tree option;
  extras        : response_extras;
}

There are some deep guarantees baked into this. Because status is part of the type's representation, the compiler knows that the value of status captured in the action is exactly the same value that was tested against the pattern. One rule matches when status is 307, so any later rule that reads status is guaranteed not to see 307. The structure of the type is its interface, and patterns feed back into the type inferencer; matching against a record with a json field tells the compiler something about what's being matched.

The OO View: Encapsulation and Its Trade-offs

Now let's look at the same domain through an object-oriented lens. Here's a sketch of an HTTP response class in Kotlin:

class HttpResponse(
    val statusCode: Int,
    private val headers: Headers,
    private val bodyPromise: Promise<ByteArray>
) {
    val ok get() = statusCode in 200..299

    val shortMimeType: String by lazy {
        headers.getFirst("content-type")
            ?.let { parseMimeType(it)?.majorMinor }
            ?: "application/octet-stream"
    }

    val json: Result<JsonSyntaxTree>
        get() = /* details elided */
}

This is also appealing, but for different reasons. ok is a computed property so it doesn't need to be pre-computed but its relationship to statusCode is consistent. shortMimeType parses the Content-Type header and caches the result, handling missing or malformed headers gracefully. This type can be safely extended too; if structured Markdown responses become popular as message bodies, they can add a markdown property without changing statusCode, ok, or anything existing callers depend on. The implementation can evolve freely behind the interface.

But there's no natural way to write a pattern over this class. And there are no stability guarantees. The fact that computing ok has no side effects, and that its result is the same if read repeatedly is wholly due to its current implementation.

Objects lie. TOCTOU (Time of Check ≠ Time of Use) attacks ³ involve confusing privileged code via a getter that returns one value for the safety checks, and another when redundantly queried by the code that assumes the safety check. Even when objects don't lie intentionally, getters can have bugs and race conditions can manifest in the same way; we language designers should seize any opportunity to help systems authors maintain invariants even in the face of bugs.

Pros and cons

ADTs provide a basis for pattern syntax that mirrors constructor expression syntax, but those patterns can only operate on raw state. You can't change or extend the internal representation without breaking clients, because the entire representation is public. And when parts of your domain aren't closed (network streams, on-demand-parsed bodies), you have to create a shim to get around them like the response type. It also has no room for zero-storage conveniences; ok can be computed from status but the OCaml record has to store both.

OO types are much easier to evolve, but OOP languages do not reinforce a relationship in developers' minds between surface syntax and object state so OOP language designers need to hoist learnable, discoverable pattern syntax on something else.

Since objects can lie, if we want to preserve the benefit that checking a pattern against boilerplate lets you rely on those checks in your action, we have to be careful about how we bolt pattern matching onto OOP languages.

FP languages often use recursive types like "Cons" lists that mesh well with inductive reasoning ⁴ and inductive pattern checks. Non-FP languages instead use linear arrays or growable vectors types as the workhorse type for representing sequences of items and leave it up to user code to safely randomly access only elements that exist.

The rest of this article is going to explore what it would take to get the good parts of FP patterns while preserving the good parts of class style type definitions.

The Big Picture: Desugaring Pattern Matches

Our goal is to take a match expression over an OOP and desugar it into code that uses only simpler language constructs. The overarching shape of the output has three parts:

// Capture temporaries to provide a stable view of unstable objects
let tmp_status;
let tmp_shortMimeType;

// Nested `if`s set the rule index using a decision tree.
// For this simple example they don't actually nest.
let decision = -1;  // unmatched
if (!matched.ok) {
    decision = 0;
} else {
    // MORE DECISION CODE
}

// 3. Switch on index to execute actions
switch (decision) {
  case 0: handle_error("unexpected response: " + tmp_status); break
  case 1: handle_json(response.json);                         break
  case 2: fetch_async(tmp_location, handle_json);             break
  case 3: handle_error("unrecognised response");              break
  default: panic()
}

(We'll revisit this example in more detail later.)

Step 1 is the key to apparent stability: by using temporaries so that we only read each mentioned property at most once, we guarantee that the value tested against is the same in each pattern match test and the same used in action code. This gives us a stable view of unstable objects; even if a getter has side effects or returns different values, the pattern match code is insulated from that instability. (More detail later on subtle varieties of TOCTOU attacks and what we can actually guarantee.)

Step 2 is driven by a decision tree which expresses the boilerplate parts of patterns as sequences of simple predicates.

Step 3 is just a simple computed jump which executes the chosen action.

Decision Trees

A decision tree is a tree where each inner node is a test, a comparison of some part of the matched value against a fixed piece of boilerplate, and each leaf node is a decision (which rule(s) apply). Decision trees are a well-established technique for implementing pattern matching efficiently ⁵.

The key advantage of a decision tree over a naive if/else chain is that a test needed by multiple rules can be shared, avoiding redundant evaluation, and leading to smaller binaries. But this requires that tests can be reordered. In ADTs, reordering field reads has no semantic effect, but in an OOP language, reordering might lead to weird effects in extreme cases. There is no general solution to the efficient testing / stable order tradeoff for computed properties; type authors should strive to make property semantics independent of order of read.

Here's a simple example: matching a string against ("one", "two", "three", "four"). (In a compiler, you'd use perfect hashing to compare to a known set of strings, but this article uses strings to illustrate examining a structured value using a series of simpler tests involving unstructured values.)

flowchart TD
    Root["str.length #lt;=#gt; 4"]
    Root -->|"#lt; 4"| Inner["str[0] #lt;=#gt; 'o'"]
    Root -->|"== 4"| Four["four<br>(natch)"]
    Root -->|"#gt; 4"| Three["three<br>(umm)"]
    Inner -->|"#lt;= 'o'"| One["one"]
    Inner -->|"#gt; 'o'"| Two["two"]

This decision tree tests str.length first, splitting the candidates, and only reads str[0] on the branch where the string is short. This tree has a problem: if str is the empty string, the str[0] test is unsafe, but no prior decision guards against this. A real decision tree builder needs to track prerequisites: str[0] is only safe if some test earlier on the path implies that str.length >= 1.

(In practice, compiler writers often build a directed-acyclic-graph (DAG) instead of a tree. Not all DAGs can be converted to if/else trees but can be turned into jump instructions for a reducible control flow graph and can be turned into structured control flow statements where the language supports labeled breaks to the end of blocks.) For simplicity, this article is going to stick with trees, specifically binary decision trees.

What Is a Test?

There are two kinds of atomic tests that inner nodes of our decision tree can perform.

An RttiTest asks is the value of a portion of the matched value an instance of some type? A ValueTest asks is the value in this range? Both carry a list of prerequisites, Requirements that must be satisfied before it's safe to evaluate this test.

(The following internal abstractions used for converting pattern match syntax to simpler constructs are written in Kotlin. The precise semantics are not important. sealed interface establish a closed product type, and data classes are struct like.)

/** A predicate relating to part of a value. */
sealed interface AtomicTest {
    val tested: PropertyChain
    /** Must hold for [tested] to be safely read. */
    val prereqs: List<Requirement>
}

/**
 * Answers yes when [tested]'s result is a value
 * of the described [type].
 */
data class RttiTest(
    override val tested: PropertyChain,
    override val prereqs: List<Requirement>,
    val type: TypeDescriptor,
) : AtomicTest

/**
 * Answers yes when a property's value is in the
 * [range] according to the order specified by
 * [valueLine].
 */
data class ValueTest<T : Any>(
    override val tested: PropertyChain,
    override val prereqs: List<Requirement>,
    val valueLine: ValueLine<T>,
    val range: Range<T>,
) : AtomicTest

Values and Value Lines

To reason about ranges, we need a notion of ordered values. A ValueLine<T> is a well-behaved ordering of values of type <T>, i.e. no NaN identity surprises:

/**
 * A line of mutually comparable values.
 * @param <T> the Kotlin representation of the values.
 */
interface ValueLine<T : Any> {
    /** The least possible value, or null if unknown */
    val min: T?
    /** The greatest possible value, or null if unknown */
    val max: T?
    /** Next value, or null if unknown */
    fun follower(x: T): T?
    /** Immediately preceding value, or null if unknown */
    fun preceder(x: T): T?
    fun compare(a: T, b: T): Int
}

A floating-point value line might be ordered thus:

NaN, −∞, …negative numbers…, −0, +0, …positive numbers…, +∞.

+0 directly follows -0. The minimum is NaN and the maximum is +∞.

A string value line starts at the empty string but has no maximum. A nullable property's value might involve testing against a singleton NullLine in addition to whatever line applies to its non-null values.

Ranges are intervals on a value line:

data class Range<T : Any>(
    val min: EndPoint<T>?,
    val max: EndPoint<T>?,
) {
    fun contains(value: T, line: ValueLine<T>): Boolean { /* ... */ }
}

sealed interface EndPoint<T : Any>
/** An endpoint that excludes [value] */
data class Open<T>(val value: T)   : EndPoint<T>
/** An endpoint that includes [value] */
data class Closed<T>(val value: T) : EndPoint<T>

A null endpoint means "the limit of the value line in that direction." A range is invalid on any ValueLine where min ≥ max. A range with at least one open endpoint is empty on any value line where min == max.

Range arithmetic simplifies decision tree building by grouping related tests into ranges that can be partitioned based on expected info-gain.

When a value lines knows some of (min, max, follower, and preceder) we can normalize some ranges and range sets. For example:

• The range ([0, 3] &union; [4, 5]) is equivalent to ([0, 5]) on the integer number line because 4 immediately follows 3, but on the float value line there are values in between 3 and 4.
• On the string value line the range ["", "a"] is equivalent to a range like Range(null, Open("b")).

Property Chains

All the tests above involve an unknown quantity specified as a property chain, a path from the matched value down through its properties or indices; and a known quantity: a specific type or a range on a value line.

For example, a pattern like { headers: { Access-Control-Allow-Origin: true } } might involve reading a headers key/value mapping and then using a property that reflects the corresponding key/value pair as a boolean or null. The property chain ["headers", "accessControlAllowOrigin"] might correspond to code like matchedValue.headers.accessControlAllowOrigin and allow computing the required value at runtime.

sealed class PropertyKey
/** For named properties often used with `obj.property` syntax. */
data class NamedKey(val name: String) : PropertyKey()
/** For indexical properties often used with `obj[index]` syntax. */
data class IndexKey(val index: Int)   : PropertyKey()

data class PropertyChain(val keys: List<PropertyKey>)

When generating temporaries, we create one for each distinct property chain that appears more than once in any test and/or action capture, plus each prefix of a chain that is shared by two or more used chains. This ensures that intermediate objects (like matchedValue.headers) are also captured at most once.

Aside: Lying liars and TOCTOU guarantees

As alluded to above, the TOCTOU problem showed up early in implementations of operating system system calls: unprivileged user code passes inputs to system code that uses privileged processor instructions. It has reoccurred in web browsers; JavaScript values pass via host APIs to browser code written in privileged JavaScript or C++.

Some TOCTOU problems can be corrected by using the same value as was checked, but some cannot. Here's an example of a TOCTOU problem.

// This logs
// naive:
// Using only for evil.
// fixed:
// Using only for good.

// System code
function gatekeeper_naive(o) {
  if (o.x === 'good') {
    privilegedCode(o.x);
  }
}

function gatekeeper_fixed(o) {
  let { x } = o;  // Reads once
  if (x === 'good') {
    privilegedCode(x);
  }
}

function privilegedCode(x) {
  console.log(`Using only for ${x}.`);
}

// Malicious user code
let o = {
  count: 0,
  get x() {
    // Bait and switch
    return !this.count++ ? 'good' : 'evil';
  },
  reset() { this.count = 0; }
};
console.log('naive:');
gatekeeper_naive(o);
o.reset();
console.log('fixed:');
gatekeeper_fixed(o);

But that is not the only variety of TOCTOU attacks. TOCTOU attacks occur when any user code can run between the first check and the last use [^cwe-367-races]. Even without true concurency, it's possible to orchestrate such a situation.

// This logs:
// Using only for evil,eviler,evilest 3 times.

// System code
function gatekeeper(o) {
  // Reading once
  let arr = o.arr;
  if (arr.every(el => typeof el === 'string' && el.startsWith("good"))) {
    // Read of n executes use code between check of arr and its use
    let n = o.n;
    if (Number.isSafeInteger(n) && n >= 0) {
      privilegedCode(arr, n);
    }
  }
}

function privilegedCode(arr, n) {
  console.log(`Using only for ${arr} ${n} times.`);
}

// Malicious user code
let o = {
  arr: ["good", "gooder", "goodest"],
  get n() {
    let { arr } = this;
    // Mutate array in place.
    for (let i = arr.length; --i >= 0;) arr[i] = arr[i].replace(/good/, "evil");
    return 3;
  }
}
gatekeeper(o);

By focusing on value lines, immutable values that can be read once and safely assumed not to change in modern OOP languages, this proposal carves out a TOCTOU safe space, but as patterns where the underlying values are mutable are still potentially vulnerable. OOP languages might benefit from type system affordances that identify some types as deeply immutable (à la Joe-E [^joe-e]) and linters that point out captures of mutable values. Pattern languages could provide syntax like as copy to enable defensively copying a capture before check.

Turning Patterns into Tests: Disjunction of Conjunctions

Each action in a match corresponds to a rule index. A rule may be reachable via more than one pattern (disjunction), and a single pattern may require multiple pieces of boilerplate to match (conjunction). So a match rule desugars to a disjunction of conjunctions of requirements:

/** A test and its expected outcome */
data class Requirement(
    val test: AtomicTest,
    val outcome: Boolean,
)

/** An AND of requirements */
data class ReqConjunction(
    val requirements: List<Requirement>,
)

/** An OR of the ANDs that bundles some information about the action it points to */
data class RuleDisjunction(
    val alternatives: List<ReqConjunction>,
    /** PropertyChain, Identifier pairs */
    val captures: Captures,
    val actionIndex: Int,
    /** true if it only applies if there are no non fallback alternatives */
    val isFallback: boolean = false,
)

A pattern processor walks the pattern tokens and emits requirements. One subtle point: in most OO languages, identifiers are re-assignable by default, so a bare identifier like PI in a pattern is ambiguous — is it capturing a value into a variable called PI, or testing for equality with the constant PI? A syntax convention can resolve this. For example, requiring let name for capture sites, or allowing an explicit Lisp-style unquote for constant expressions, makes the intent clear to both programmer and compiler.

An example pattern syntax

In the playground below, we use a default pattern syntax. It's written in JavaScript so that it runs in this web page, and so has the following JavaScript like syntax, and matches JSON-like patterns.

match ( expressionToMatch ) {
  // Each rule starts with `case` and multiple rules that lead to the same action may be comma separated.
  case [ 0.0, 1.0 ] => f();
  // That rule matches an array and works on three property chains: `.length`, `[0]`, `[1]`.
  // The requirements are that `.length === 2` on the int value line, and `[0] === 0.0` and `[1] === 1.0` on the float value line.
  // Each of the latter two requirements have pre-requisites that the length is sufficient for those elements to be read.

  // Here's a rule that captures a value.
  case [ x ] => g(x);

  // Maybe Math.PI is in scope as just PI.  It'd be confusing if [ PI ] overwrote that value.
  // So if we want to use a constant value in a pattern, we can use a syntax to specify that the identifier is
  // used as a right-hand identifier, not a left-hand identifier like `x` in `[ x ]` above.
  case [ _, _, $(PI) ],
  case [ _, _, $(-PI) ] => deliciousPie();
  // Two conjunctions for the same action.

  // Rarely are you going to mix types, but here's a record that captures y when x is zero.
  case { x: 0.0, y } => pointOnYAxis(y);
}

The main elements of any type agnostic pattern syntax are:

• A way to specify which property chains have requirements: the [0] property chain in the first rule has a value test requirement that its value is in the singleton range [0.0, 0.0].
• A way to specify which proeprty chains are captured and under which identifier: expressionToMatch's .y property chain is captured as y.
• Some words like false, true, and null are obviously constant, but some like PI and undefined are just identifiers, and potentially reassignable. A way to refer to identifiers for their value. (From our HTTP response example HTTP_RESPONSE_CODE_OK might be a constant)

From this syntax, we can boil down a generic pattern syntax to a disjunction of conjunctions, and are ready to convert it to simpler control flow constructs.

Part of the elegance of ADT patterns in FP languages is that they look like construction in reverse; reading code that constructs values builds intuition about the meaning of patterns. Since this scheme is based on presented properties rather than constructor arguments, that syntactic relationship is gone. That said, JSON-like object literal syntax ({ status: 307, ok: false }) is already familiar to developers who work in JavaScript, Go, and Python; so pattern syntax designed along those lines might be readily accepted by many developers.

Building the Decision Tree

With requirements in hand, we can build the decision tree. The literature on FP languages discusses pragmatics extensively ⁵, but we're going to go with ID3 because it's simple and good enough to illustrate. It's greedy; at each node, it picks the test that best partitions the remaining candidates.

ID3 doesn't handle this-before-that constraints like prerequisites. We modify the selection criterion to exclude any test whose prerequisites are not implied by the tests already on the path from the tree root to the current node. Naive ID3 with this constraint seems to work well in practice, but the playground implementation hacked it to boost a test based on the number of tests that it unlocks, but this could be improved to boost based on the expected gains of tests it unlocks; that would require a non-greedy algo though.

Leaf nodes store a set of rule indices. An empty set means "unmatched." A set with more than one element means the patterns are ambiguous and should be flagged as an error. It's important to keep evaluating requirements even after only one rule remains as a candidate, to avoid overmatching: a rule might be distinguishable from other rules by just one test, but still not distinguishable from the "no match" case.

Coherence Checks

Once the tree is built, we're in a position to report errors:

Incomplete coverage. If there are unmatched leaves, walk up from each one collecting the tests along the path to generate a diagnostic like: "match needs a rule for when status is 200 and mime type is 'text/html'." If the match is in a Unit/void context, it's type-safe to assume an implicit else -> {}.

Redundant patterns. Ambiguous leaves (multiple rule indices) mean two patterns overlap in the values they match. The playground below has options for ways to resolve this via a first-wins rule or treating it as an error. If the programming language has enough information about types to come up with a specificity value for a rule based on "strictly matches more possible value", it could implement a most specific rule wins.

Impossible tests. A node like .x in [1, 1) (an empty range) should be pruned. This situation should probably be flagged before tree-building if it arises from conflicting requirements in a pattern like { x: 0, x: 1 }.

Generating Code

Code generation from the tree is straightforward.

1. Use a Trie to count how often property chains appear both in tests and in values captured for actions. Assign tempory names for any that have a count ≥ 2.
2. Emit temporaries for any property chain prefixes that will be multiply accessed.
3. At each inner node, emit the test and branch.
4. At each leaf, emit the rule index (or a fallthrough to the default handler).
5. After the decision tree, emit the switch on rule index, using the bindings map to make the captured values available under their local names.

Some temporaries used in captures might be needed in some subtrees but not others, so might not always be read as part of a test at the start of the action. For example, if multiple rules for the same action both capture x but one also tests it using <pattern> as x syntax. Representing them using optional types lets you initialise them lazily as the decision tree reaches the relevant node, while still being able to reference them consistently in the action code.

Example

Recall the example from above.

match response with
| { ok = false; status } ->
    handle_error ("unexpected response: " ^ string_of_int status)
| { shortMimeType = ("application", "json"); json } ->
    handle_json json
| { status = 307; headers } ->
    fetch_async (headers.location) handle_json
| _ ->
    handle_error "unrecognised response"

If this were translated to match syntax in an OOP language that uses the Kotlin form of the response class, we might go through this sequence of compiler processing steps:

First, convert the record pattern syntax into requirements.

RuleDisjunction(
  listOf(
    ReqConjunction(
      Requirement(
        ValueTest(
          PropertyChain(["ok"]), BooleanValueLine,
          Range(Closed(false), Closed(false))),
        true,
      )
    )
  ),
  Captures(Capture(PropertyChain(["status"]), Identifier("status"))),
  actionIndex = 0,
)

RuleDisjunction(
  listOf(
    ReqConjunction(
    Requirement(
      ValueTest(
        PropertyChain(["shortMimeType", 0]),
        StringValueLine,
        Range(ClosedEndPoint("application"), ClosedEndPoint("application"))),
      true,
    ),
    Requirement(
      ValueTest(
        PropertyChain(["shortMimeType", 1]),
        StringValueLine,
        Range(ClosedEndPoint("json"), ClosedEndPoint("json"))),
      true,
    )
  ),
  Captures(PropertyChain(["json"]), Identifier("json")),
  actionIndex = 1,
)

RuleDisjunction(
  listOf(
    ReqConjunction(
      Requirement(
        ValueTest(
          PropertyChain(["status"]), IntValueLine,
          Range(ClosedEndPoint(307), ClosedEndPoint(307))),
        true,
      )
    )
  ),
  Captures(PropertyChain(["headers"]), Identifier("headers")),
  actionIndex = 2,
)

RuleDisjunction(
  listOf(
    ReqConjunction( // Empty conjunction
      [],
    )
  ),
  Captures()
  actionIndex = 3,
  isFallback = true,
)

In this case we've got no pre-requisities, but this is where we'd pull them out. During tree-building it can be convenient to just keep track, as we build the tree from the top down to just keep a count of un-satisfied pre-requisites for each untested requirement.

Our tree might look like this; there's not a huge number of shared predicates to do interesting things with here.

flowchart TD
    A["x.ok == false"]
    A -->|"true"| Dec0["Decision 0"]
    A -->|"false"| B
    B["x.status == 307"]
    B -->|"true"| Dec2["Decision 2"]
    B -->|"false"| C
    C["x.shortMimeType[0] == #quot;application#quot;"]
    C -->|"true"| D
    C -->|"false"| Dec3A["Decision 3"]
    D["x.shortMimeType[1] == #quot;json#quot;"]
    D -->|"true"| Dec1["Decision 1"]
    D -->|"false"| Dec3B["Decision 3"]

We can now inspect this tree to confirm that every action is reachable (assuming predicates can evaluate to both true and false in some situation), no decision is ambiguous; each leaf has one decision index, and every path through the tree ends up making a decision.

After those coherence checks, it's time to look at the actual tests and the captures required by actions to figure out which property chains to capture as temporaries.

(Aside: OOP languages often differ from FP languages in that cycles are more common in OOP systems. In JavaScript, window === window.self && window.self === window.self.self. This scheme does not assume that the set of property chains are closed or even enumerable. It only assumes that the set of property chains that appear in a particular rule are closed and enumerable, so is compatible with language affordances like Smalltalk doesNotUnderstand and JavaScript proxies.)

With these property chain counts, we can desugar the above to code.

const matched = response;  // Capture expression
let decision = -1;  // Index for switch at bottom

// Temporaries
let tmp_status = undefined;
let tmp_shortMimeType = undefined;

// Apply the rules to pick the appropriate action
if (matched.ok) {
    tmp_status = matched.status;
    if (tmp_status == 307) {
        decision = 2;
    } else {
        tmp_shortMimeType = matched.shortMimeType;
        if (tmp_shortMimeType[0] == "application") {
            // Could collapse this into an && predicate.
            if (tmp_shortMimeType[1] == "json") {
                decision = 1;
            } else {
                decision = 3;
            }
        } else {
            decision = 3;
        }
    }
} else {
    decision = 0;
}

// Finally perform the action
switch (decision) {
    case 0: {
        // t_status never initialized on path to an action 0 leaf.
        tmp_status = matched.status;
        // Set up captures for the action code
        let status = tmp_status;
        // Action 0 code goes here
        break;
    }
    case 1: {
        let json = matched.json;
        // Action 1 code goes here
        break;
    }
    case 2: {
        let headers = matched.headers;
        // Action 2 code goes here
        break;
    }
    case 3: {
        // Action 3 code goes here
    }
    default: panic();
}

Note that according to our definition of the ok above, val ok get() = status in 200..299, we could express the ok check reusing tmp_status. Unfortunately, encapsulation in OOP means we're not allowed to do that for matches in compilation units that do not include the definition of the response type. This is one way encapsulation is both a feature and a bug. We can't look inside the box to provide stability as-if computed properties were inlined beacuse, when the match and the HTTP response type's definition are in different compilation unit, the compiler needs to assume that the implementation could change in a future version of the HTTP response library.

Further Work

This article discussed ways to bolt pattern matching onto existing languages that were not designed with it in mind, but there are several under-explored topics.

Custom pattern macros. If a language supports custom ahead-of-time token processing (like Rust macros), the match construct could delegate pattern parsing to a macro associated with the match expression's type. A URL type, for example, could let you write:

case "https://example.com" ("/" ... as path) "?q=" q -> action(path, q)

That pattern could be parsed by applying URL syntax to pick out required fields from boilerplate and using boilerplate to figure out what left identifiers are capturing:

1. A URL affix "http://example.com" which specifies boilerplate related to the URL scheme and authority.
2. "/" ... specifies boilerplate that would introduce a path allowed in an absolute URL.
3. as path a pattern operator that captures the whole path in a variable named path.
4. "?q=" specifies boilerplate that indicates that a query is started and that what follows specifies a value for the q query parameter.
5. q as a bare name specifies that the action should be able to refer to the value of that query parameter via an identifier named q.

When types that have well understood textual forms, work that mirrors those forms can help many developers write readable code for common tasks like routing requests to the right handler based on URLs without error prone regular expressions.

Sequence patterns. OMeta ⁶ explores flexible pattern matching over both textual and non-textual data by applying grammars. It works based on parsing-like techniques, not static tree building.

§2.2 PEG Extensions for Generality

PEGs operate on streams of characters, and consequently, they only support one kind of primary parsing expression: characters. Because OMeta operates on arbitrary kinds of data, it needs to support some additional kinds of expression …

Combining tree-building for records and arrays with fairly fixed structure, and falling back to Ometa for rules like "this array starts like this, has 0 or more of these, and then some of those" might allow the best of both worlds.

But adapting the value-stability scheme to sequences that way might require tracking which elements have been "unrolled" and ensuring their captured values are consistent with what was tested, incurring a defensive copy of a sequence.

As discussed under TOCTOU problems, there may be opportunities to make it easy to defensively copying captures, incorporating knowledge about which types are mutable to allow linter warnings about potentially unsafe captures in security-sensitive portions of code.

The toy implementation used by this work does naive ID3 with support for pre-requisites hacked on top. Better tree-building algorithms could take into account both that decisions have dispositive value but also that they may imply pre-requisites that enable other tests with dispositive value.

Type inference feedback. With ADTs, pattern matching feeds back into type inference: matching against _::[] tells the compiler the matched value is a list. With OO classes, the matched expression must be typed before the decision tree is built, so the compiler can choose the right value lines for each property chain. Better ways to to narrow bounds of a matched expression based on the property chains explicit in a match might help in places where modern OOP languages often do a lot of type inference, for example in input types for abbreviated lambda syntax.

IDE scaffolding. When the type is an FP sum type, an IDE can offer to fill in all the cases automatically. With OO objects, the set of property names doesn't determine a likely set of "interesting" patterns. Ways OO languages might allow annotations to guide IDEs so that widely used "core" libraries' maintainers can provide a good IDE prefill experience.

Sometimes dynamic languages are too dynamic for their own good. Could a semantics for including a constant by reference, $(…) above resolve to a different value each time through a match in a tight loop? Yes, it could, and that might require tree-building each time. What are user expectations about semantics and performance there? Can a dynamic language follow the principle of least confusion while still aggressively caching rule sets? How can property chains efficiently extend to name-like values that are static in practice but dynamic in semantics like JavaScript symbols and private member names? What about when they are dynamic in practice as when private member names are for a nested class declaration that creates a new class object with its own private names each time the enclosing scope is entered?

Conclusions

Maybe we'll never be able to safely combine chocolate and peanut butter, but we can have expressive pattern matching alongside implementation hiding if we craft semantics with care.

The problems identified herein are real: apparent object stability guarantees, test ordering that doesn't crash when applied to indexed and keyed collection types, avoiding lvalue/rvalue confusion, and building on developer's intuition about the relationship between syntax and values.

But in the context of a particular programming language, language designers should be able to navigate them by adapting some of the techniques illustrated here.

As seen through the lens of TOCTOU problems, there is no silver bullet for purelang style stability in OOP languages, but we can document which guarantees we can uphold and help complex gate-keeping and routing code authors use succinct, auditable pattern matching to convey just the safe bits across privileged code boundaries.

Appendix

Below is a playground built using a JavaScript implementation of the pattern matching syntax described above.

The authors don't claim it's a particularly good syntax, just that it can be hacked on top of JavaScript using Babel, and that it should be recongizable to readers familiar with JavaScript and match semantics in OCaml.

The implementation has some known limitations:

1. The parser is approximate because JavaScript's lexical syntax is non-context-free around regular expression literals and division operators. This simplified using Babel for most of the JS parsing, but having custom handling for the outer match envelope that Babel would reject.
2. The $(…) syntax does not obey block scoping rules as it should in a real implementation.
3. It only parses the match block, not match in the context of a larger run of JavaScript statements.
4. The implementation creates pre-requisites around array length but not for optional properties, or to require Array.isArray vs record syntax being only used for object values. It could, but that leads to large trees, probably necessary in any dynlang, but less useful for building intuitions about how this would work in a typed language that can introspect over the matched expressions type to eliminate a lot of unnecessary runtime tests.
5. The value range implication and contradiction rules do not capture contradiction across value lines: is-a string contradicting is-a number. Again, in a dynlang, one would treat generating more rules as the cost of doing business but that complicates visualization.

The code is available at github.com/mikesamuel/pl-musings/tree/main/patterns-oop/src.