Pattern Matching in an Open World∗
Weixin Zhang

Bruno C. d. S. Oliveira

The University of Hong Kong
Hong Kong, China
wxzhang2@cs.hku.hk

The University of Hong Kong
Hong Kong, China
bruno@cs.hku.hk

Abstract
Pattern matching is a pervasive and useful feature in functional programming. There have been many attempts tobring similar notions to Object-Oriented Programming (OOP)in the past. However, a key challenge in OOP is how patternmatching can coexist with the open nature of OOP data structures, while at the same time guaranteeing other desirable
properties for pattern matching.
This paper discusses several desirable properties for pattern matching in an OOP context and shows how existing
approaches are lacking some of these properties. We argue
that the traditional semantics of pattern matching, which
is based on the order of patterns and adopted by many approaches, is in conflict with the openness of data structures.
Therefore we suggest that a more restricted, top-level patternmatching model, where the order of patterns is irrelevant, isworthwhile considering in an OOP context. To compensate
for the absence of ordered patterns we propose a complementary mechanism for case analysis with defaults, which
can be used when nested and/or multiple case analysis isneeded. To illustrate our points we develop Castor: a metaprogramming library in Scala that adopts both ideas. Castor
generates code that uses type-safe extensible visitors, andlargely removes boilerplate code typically associated withvisitors. We illustrate the applicability of our approach witha case study modularizing the interpreters in the famousbook "Types and Programming Languages".
CCS Concepts • Software and its engineering → Language features;
Keywords Pattern matching, Meta-programming, OOP∗ This work was funded by Hong Kong Research Grant Council projects

number 17210617 and 17258816.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
GPCE ’18, November 5–6, 2018, Boston, MA, USA© 2018 Association for Computing Machinery.
ACM ISBN 978-1-4503-6045-6/18/11. . . $15.00
https://doi.org/10.1145/3278122.3278124

ACM Reference Format:
Weixin Zhang and Bruno C. d. S. Oliveira. 2018. Pattern Matchingin an Open World. In Proceedings of the 17th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE ’18), November 5–6, 2018, Boston, MA, USA. ACM, New
York, NY, USA, 13 pages. https://doi.org/10.1145/3278122.3278124

1

Introduction

Pattern matching is a pervasive and useful feature in functional programming. Languages such as Haskell [20] or ML [24]use algebraic datatypes to model data structures, and pattern matching to process such data structures. Algebraic
datatypes and pattern matching allow concise programs formany applications. For example, compilers, interpreters or
program analysis, often require extensive analysis on a complex Abstract Syntax Tree (AST) structure. In functional
languages, ASTs are modeled with algebraic datatypes. Withbuilt-in support for pattern matching, analyzing and manipulating an AST can be done in a concise way.
Object-Oriented Programming (OOP) often uses class hierarchies instead of algebraic datatypes to model data structures. Still, the same need for processing data structures also
exists in OOP. However, there are important differences between data structures modeled with algebraic datatypes andclass hierarchies. Algebraic datatypes are typically closed,
having a fixed set of variants. In contrast class hierarchies
are open, allowing the addition of new variants. A closed setof variants facilitates exhaustiveness checking of patterns
but sacrifices the ability to add new variants. OO class hierarchies do support the addition of new variants, but without
mechanisms similar to pattern matching some programs are
unwieldy and cumbersome to write.
There have been many attempts to bring notions similar to pattern matching to OOP in the past. The Visitor
pattern [10] is frequently used as a poor man’s approach
to pattern matching in OO languages. However, classic formulations of the Visitor pattern have a high notational
overhead, and also lack extensibility for dealing with newdata variants. More recently several new designs for extensible visitors [15, 26, 27, 42] provide variations of the Visitor
pattern that allow for the modular addition of new variants.
However, these techniques do not solve the high notational
overhead problem and do not provide a concise notation
for pattern matching. Case classes in Scala [25] provide aninteresting blend between algebraic datatypes and class hierarchies. Case classes come in different flavors. Sealed case

GPCE ’18, November 5–6, 2018, Boston, MA, USAclasses are very much like classical algebraic datatypes, andfacilitate exhaustiveness checking at the cost of a closed (nonextensible) set of variants. Open case classes support patternmatching for class hierarchies, which can modularly add newvariants. However no exhaustiveness checking is possible
for open case classes. Multiple dispatching [8] and multimethods [7] provide OOP alternatives to pattern matching,enabling method dispatching to be determined by multiple
arguments at run-time (rather than just one). This facilitates
the definition of binary (and n-ary) operations such as equality, but it does not provide immediate support for nested
patterns. Furthermore, type systems supporting multiple dispatching add significant complexity. Finally, there are also
approaches [19, 23] that attempt to do a more principleddesign that integrates pattern matching and OOP while preserving the ability to add new variants and the ability tocheck for exhaustiveness. However, such approaches require
new non-trivial language designs and thus cannot be usedin existing languages such as Scala.
This paper starts by identifying several desirable properties for pattern matching in an OOP context:• Conciseness. Patterns should be described concisely withpotential support for wildcards, deep patterns and guards.
• Exhaustiveness. Patterns should be exhaustive to avoid
runtime matching failure. The exhaustiveness of patterns
should be statically verified by the compiler and the missing cases should be reported if patterns are incomplete.
• Extensibility. Datatypes should be extensible in the sensethat new data variants can be added while existing operations can be reused without modification.
• Composability. Patterns should be composable so thatcomplex patterns can be built from smaller pieces. Whencomposing overlapped patterns, programmers should be
warned about possible redundancies.
We show that many widely used approaches lack some ofthese properties. We argue that a problem is that many approaches try to closely follow the traditional semantics ofpattern matching, which assumes a closed set of variants.
Under a closed set of variants, it is natural to use the orderof patterns to prioritize some patterns over the others. However, when the set of variants is not predefined a priori thenrelying on some ordering of patterns is problematic, especially if separate compilation and modular type-checking are
to be preserved. Nonetheless many OO approaches, which
try to support both an extensible set of variants and patternmatching, still try to use the order of patterns to define thesemantics. Unfortunately, this makes it hard to support otherdesirable properties such as exhaustiveness or composability.
Therefore we suggest two different mechanisms to deal
with patterns in an OO context. Firstly, we suggest a more
restricted, top-level pattern matching model, where the order of patterns is irrelevant. Secondly, to compensate forthe absence of ordered patterns we propose a second mechanism for case analysis with defaults, which can be used when

Weixin Zhang and Bruno C. d. S. Oliveira
nested and/or multiple case analysis is needed. The second
mechanism is directly inspired by Zenger and Odersky [40]’sidea of Extensible Algebraic Datatypes with Defaults (EADDs).
In EADDs the key idea is that if pattern matching always
comes with a default then it is always exhaustive. However,
the key problem with EADDs is that not all operations havea good default. In our approach, top-level pattern matchingdoes not force programmers to define a default, while stillretaining exhaustiveness. However, we argue that, in practice, many operations that require nested patterns tend tohave a good default for the nested patterns. Thus we propose
applying the EADDs idea only to nested patterns.
To illustrate our points we develop Castor1 : a metaprogramming library in Scala that adopts both ideas, and toa large extent, meets all the properties summarized above.
The key idea is to combine case classes with extensible visitors so that top-level case analysis is done using visitors,
while nested case analysis is done using Scala’s own built-in
pattern matching. Castor eliminates the complexity andverbosity of visitors by providing users with annotations.
Through macro annotation processing, the annotated program is transformed and boilerplate automatically generated. We illustrate the applicability of our approach with acase study modularizing the interpreters in the famous book
"Types and Programming Languages" (TAPL) [31].
In summary, this paper makes the following contributions:• Desirable properties for open pattern matching: We
summarize the desirable properties of pattern matchingand evaluate existing approaches accordingly (Section 2).
• The Castor metaprogramming library: We present a
novel encoding for modular pattern matching based on an
encoding of extensible visitors. The pattern matching encoding is automated using metaprogramming (Section 4).
• Non-trivial modular operations: We show how to use
Castor in defining non-trivial pattern matching operations, as well as dependencies (Section 3).
• Case study: We conduct a case study on TAPL that illustrate the effectiveness of Castor (Section 5).
Source code for Castor and case study is available at:https://github.com/wxzh/Castor

2

Pattern Matching in Scala: An Evaluation

This section reviews existing approaches to pattern matchingin Scala. To facilitate our discussion, a running example fromTAPL [31]—an untyped, arithmetic language called Arith—
is used. Our goal is to model the syntax and semantics ofArith in a concise and modular manner. None of the existing Scala approaches, including the Visitor pattern, sealedcase classes, open case classes and partial functions, fully
accomplishes the task. We discuss why these approaches failand describe the desirable properties for a better solution.
1 Castor stands for CASe class visiTOR

Pattern Matching in an Open WorldGPCE ’18, November 5–6, 2018, Boston, MA, USAt ::= 0 | succ t | pred t | true | false | if t then t else t | iszero t
t 1 → t 1′
succ t 1 → succ t 1′

pred 0 → 0

if true then t 2 else t 3 → t 2
iszero 0 → true

PredZeronv ::= 0 | succ nv

pred (succ nv 1 ) → nv 1

if false then t 2 else t 3 → t 3

PredSucc

t 1 → t 1′
pred t 1 → pred t 1′
t 1 → t 1′

Pred

if t 1 then t 2 else t 3 → if t 1′ then t 2 else t 3
t 1 → t 1′

iszero (succ nv 1 ) → false

iszero t 1 → iszero t 1′

Figure 1. The syntax and semantics of Arith.
2.1

Running Example: Arith

The syntax and semantics of Arith are formalized in Figure 1. Arith has the following syntactic forms: zero, successor, predecessor, true, false, conditional and zero test. The
definition nv identifies 0 and successive application of succ
to 0 as numeric values. The operational semantics of Arith
is given in small-step style, with a set of reduction rules specifying how a term can be rewritten in one step. Repeatedly
applying these rules will eventually evaluate a term to avalue. There might be multiple rules defined on one syntactic form. For instance, rules PredZero, PredSucc and Pred
are all defined on a predecessor term. How pred t is going tobe evaluated in the next step is determined by the shape of
the inner term t. If t is a successor application to a numericvalue, then PredSucc will be applied, etc.
Arith is a good example for assessing the 4 desirable
properties of pattern matching summarized in Section 1 because: 1) The small-step style semantics is best expressedwith a concise nested case analysis on terms; 2) Arith is a
unification of two sublanguages, Nat (zero, successor andpredecessor) and Bool (true, false, and conditional) with anextension (zero test). An ideal implementation of Arith is tohave Nat and Bool separately defined and modularly reused.
2.2

The Visitor Pattern

The Visitor pattern [10] is often used in OOP languages for
simulating pattern matching. Figure 2 implements the Nat
sublanguage using the Visitor pattern. The class hierarchymodels the abstract syntax of Nat, where the abstract class
Tm represents the datatype of terms and syntactic constructsof terms are concrete subclasses of Tm. A generic accept
method is defined throughout the class hierarchy, which
is implemented by invoking the corresponding lowercase
method defined on the visitor instance it takes. These lowercase methods are declared in the visitor interface TmVisit.
Operations over Tm are concrete implementations of TmVisit.
For example, object nv instantiates the type parameter A of
TmVisit as Boolean and implements each visit method accordingly. For recursive cases like tmSucc, we call t.accept(nv).
Discussion of the Approach. A well-known criticism of
the Visitor pattern is its verbosity, which is manifested in
encoding the small-step semantics in eval1. Defining tmZero

object NoRuleApplies extends Exception// Class hierarchy
abstract class Tm {def accept[A](v: TmVisit[A]): A }object TmZero extends Tm {def accept[A](v: TmVisit[A]) = v.tmZero }class TmSucc(t: Tm) extends Tm {def accept[A](v: TmVisit[A]) = v.tmSucc(t) }class TmPred(t: Tm) extends Tm {def accept[A](v: TmVisit[A]) = v.tmPred(t) }// Visitor interface
trait TmVisit[A] {def tmZero: A
def tmSucc(t: Tm): A
def tmPred(t: Tm): A }// Numeric value checking visitor
object nv extends TmVisit[Boolean] {def tmZero = true
def tmSucc(t: Tm) = t.accept(nv)def tmPred(t: Tm) = false }// Small-step evaluation visitor
object eval1 extends TmVisit[Tm] {def tmZero = throw NoRuleApplies
def tmSucc(t: Tm) = new TmSucc(t.accept(eval1))
def tmPred(t: Tm) = t.accept(new TmVisit[Tm] {// Anonymous visitor
def tmZero = TmZero
def tmSucc(t1: Tm) = // PredSucc
if (t1.accept(nv)) t1
else new TmPred(t.accept(eval1))
def tmPred(t1: Tm) = new TmPred(t.accept(eval1))})}

Figure 2. Implementing Nat with the Visitor pattern.
and tmSucc for eval1 is easy by throwing an exception andcalling eval1 on the inner term respectively. However, defining tmPred is tricky! Take the PredSucc rule for example,
which cancels a pair of predecessor and successor application
to a numeric value. As a visitor recognizes only one level representation of a term, it is insufficient to implement rules that
require deep case analysis like PredSucc. To further reveal
the shape of the inner term, an auxiliary anonymous visitor
is hence needed. Then rules like PredSucc are possible tobe specified inside that anonymous visitor.

GPCE ’18, November 5–6, 2018, Boston, MA, USA// Sealed case class hierarchy
sealed abstract class Tmcase object TmZero extends Tmcase class TmSucc(t: Tm) extends Tmcase class TmPred(t: Tm) extends Tm// Numeric value checking function
def nv(t: Tm): Boolean = t match {case TmZero => truecase TmSucc(t1) => nv(t1)case _ => false }// Small-step evaluation function
def eval1(t: Tm): Tm = t match {case TmSucc(t1) => TmSucc(eval1(t1))
case TmPred(TmZero) => TmZerocase TmPred(TmSucc(t1)) if nv(t1) => t1 // PredSucc
case TmPred(t1) => TmPred(eval1(t1))
case _ => throw NoRuleApplies }Figure 3. Implementing Nat with sealed case classes.
A problem arises when we try to reuse the Nat implementation above in implementing Arith. The Visitor pattern
suffers from the Expression Problem (EP) [38]: it is easy to
add new operations by defining new visitors (as illustrated by
nv and eval1) but hard to add new variants. The reason is that
the Tm hierarchy is tightly coupled with the TmVisit interface. When trying to add new subclasses to the Tm hierarchy,
we are unable to implement their accept methods because
there exist no corresponding visit methods in TmVisit. A
non-solution is to modify TmVisit with new visit methods.
As a consequence, all existing concrete implementations ofTmVisit have to be modified in order to account for thosevariants. This violates the “no modification on existing code”
principle of the EP. Thus, the implementation is neither extensible nor composable. Even if modification is allowed, theimplementation would become much more tedious. There isa lot of boilerplate needs to be written for boring cases (e.g.
cases that return false in nv). Nevertheless, exhaustivenessis enforced since a concrete visitor is an object, which must
implement all visit methods exposed by the visitor interface.
2.3

Sealed Case Classes

Pattern matching, a feature originally from functional languages, offers the ability to “inspect and decompose data
simultaneously”. This ability makes it possible to model Nat
concisely. As a programming language that unifies functionaland OO paradigms, Scala [25] supports first-class patternmatching via case classes/extractors [9]. Figure 3 shows animplementation using Scala’s sealed case classes, which is
close to an implementation written in a pure functional language like Haskell or ML. A case class hierarchy models theabstract syntax. The case keyword triggers the compiler toautomatically inject methods into the class/object, including a constructor method (apply) and an extractor method(unapply). The injected constructor method simplifies theWeixin Zhang and Bruno C. d. S. Oliveira
creation of terms. For example, a successor application to
constant zero can be constructed via TmSucc(TmZero). Conversely, the injected extractor enables tearing down a term
via pattern matching, as illustrated by the implementationof nv. The term t is matched sequentially against a series ofpatterns (case clauses). For example, TmSucc(TmZero) will behandled by the second case clause of nv, which recursively invokes nv on TmZero and returns a true eventually. A wildcard
pattern (_) is used for handling boring cases altogether.
Discussion of the Approach. The strength of pattern matching shines in encoding the small-step semantics. With thehelp of pattern matching, the overall definition of eval1 is adirect mapping from the formalization shown in Figure 1. As
an example, the PredSucc rule is concisely and precisely described by a deep pattern (TmPred(TmSucc(t1))) with a guard(if nv(t1)). Furthermore, sealed case classes facilitate exhaustiveness checking on patterns. If we forgot to write thewildcard pattern in nv, the Scala compiler would warn us thata case clause for TmPred is missing. An exception is eval1,
whose exhaustiveness is not checked by the compiler due tothe use of guards. A guard might call some function whose
execution result is only known at runtime, making the reachability of that pattern difficult to decide statically. The priceto pay for exhaustiveness is the inability to add new variants of Tm in separate files. Thus, like the visitor version, theimplementation is neither extensible nor composable.
2.4 Open Case Classes
Case classes in Scala can also be open, as the sealed keyword
is optional. By removing sealed, we exchange exhaustiveness checking for the ability to add new variants in separate
files. Combined with EADDs [40], it is possible to implement
Arith in a modular manner. The idea is to use a default (wildcard pattern) in each operation to handle variants that are
not explicitly mentioned. The existence of a default makes
operations extensible, as variants added later will be automatically subsumed by that default. If the extended variants
have behavior different from the default, we can define a
new operation that deals with the extended variants anddelegates to the old operation. Figure 4 shows how to modularize Arith using open case classes. Note that Tm is declared
as a top-level open datatype.
Discussion of the Approach. One nice aspect about thisapproach is that sublanguages, Nat and Bool, are now implemented separately into two traits Nat and Bool. Nat and Bool
introduce their respective variants of Tm and a corresponding
definition of eval1. The definition nv defined by Nat works
well in Arith, as it happens to have a very good default that
automatically works for extended cases. For instance, callingnv(TmFalse) returns false as expected.
Unfortunately, eval1 is more problematic. In the generalcase defining Arith in terms of Nat and Bool causes problems
as EADDs do not work well for such non-linear extensions.
eval1 needs to be overridden for combining definitions fromPattern Matching in an Open World
abstract class Tm
trait Nat {case object TmZero extends Tmcase class TmSucc(t: Tm) extends Tmcase class TmPred(t: Tm) extends Tm
def nv(t: Tm): Boolean = ... // Same as in Figure 3
def eval1(t: Tm): Tm = ... // Same as in Figure 3}
trait Bool {case object TmTrue extends Tmcase object TmFalse extends Tmcase class TmIf(t1: Tm,t2: Tm,t3: Tm) extends Tm
def eval1(t: Tm): Tm = t match {case TmIf(TmTrue,t2,_) => t2
case TmIf(TmFalse,_,t3) => t3
case TmIf(t1,t2,t3) => TmIf(eval1(t1),t2,t3)
case _ => throw NoRuleApplies}}
trait Arith extends Nat with Bool { // Unificationcase class TmIsZero(t: Tm) extends Tm
override def eval1(t: Tm) = t match {case _: TmSucc => super[Nat].eval1(t)case _: TmPred => super[Nat].eval1(t)case _: TmIf => super[Bool].eval1(t)case TmIsZero(TmZero) => TmTruecase TmIsZero(TmSucc(t1)) if nv(t1) => TmFalse
case TmIsZero(t1) => TmIsZero(eval1(t1))
case _ => throw NoRuleApplies}}

Figure 4. Implementing Arith with open case classes.
Nat and Bool as well as complementing rules for the zero test.

This turns out to be quite tedious and error-prone: we haveto recognize interesting old cases (TmSucc, TmPred and TmIf)
using typecases and delegate appropriately to either Nat or
Bool via a super call. If the programmer forgets delegating
any of those cases, then the pattern matching falls into thewildcard pattern (the last case), throwing a NoRuleApplies
exception. In this situation the semantics of pattern matching
and wildcard patterns are to blame: since pattern matching
just follows the order of patterns, once we make a super callto a definition with wildcards then all cases will be covered.
Therefore to workaround this problem we have to carefully
delegate the cases one-by-one to the super calls. Without
any assistance from the Scala compiler during this process,it is rather easy to make mistakes like forgetting to delegate
a case or delegating a case to a wrong parent.
2.5

Partial Functions

To ease the composition of Nat and Bool, one may turn to
Scala’s PartialFunction. PartialFunction provides an orElse
method for composing partial functions. orElse tries the composed partial functions sequentially until no MatchError israised. The open case class version can be adapted using
PartialFunction with a few changes, e.g. eval1 in Bool:def eval1: PartialFunction[Tm,Tm] = {GPCE ’18, November 5–6, 2018, Boston, MA, USA
Table 1. Pattern matching support comparison

VisitorSealed case class
Open case classPartial function
CastorConciseness#= good, #G= neutral, #= bad

Exhaustiveness Extensibility Composability
#
#
#
#
#
#
#
#
G
#
G*

* Castor only gets half score on exhaustiveness because for nested case analysis

Scala cannot enforce a default. In a language-based approach nested case analysis
should always require a default, thus fully supporting exhaustiveness.

... // Cases for TmIfcase TmTrue => throw NoRuleApplies
case TmFalse => throw NoRuleApplies }eval1 is a partial function of type PartialFunction[Tm,Tm].
A value of PartialFunction[Tm,Tm] is constructed using theanonymous function syntax, where the argument Tm is di-

rectly pattern matched. The convenience of wildcard patterns is lost: wildcards are replaced by named patterns to
avoid shadowing other partial functions to be combined.
Discussion of the Approach. Partial functions make thecomposition of features work more smoothly, avoiding the
problems with eval1 for the open case classes approach:override def eval1 = super[Nat].eval1 orElse
super[Bool].eval1 orElse{ ... /* Cases for TmIsZero */ }Composing eval1 in Arith is done by chaining eval1 fromNat and Bool as well as a new partial function for the zerotest using the orElse combinator.
Still, this implementation is not very satisfactory. orElse

is left-biased, thus the combination order determines the composed semantics. That is, f orElse g is not equivalent to g
orElse f, if f and g are two overlapped partial functions(i.e. both f and g define same case patterns). orElse gives nowarning when composing such overlapped partial functions
and the semantics of the overlapped patterns are all from either f or g, depending on which comes first. It is not possible
to have a mixed semantics for overlapped patterns from bothf and g, which restricts the reusability of partial functions.

2.6

Discussion

So far, we have presented (partial) implementations of Arith
using the Visitor pattern, sealed case classes, open caseclasses, partial functions. Unfortunately, none of these implementations fully meets the desirable properties—conciseness,exhaustiveness, extensibility and composability—summarized
in Section 1. Using these four properties as criteria, Table 1
compares the pattern matching support of these approaches.
Key Observations. Conciseness and exhaustiveness are
somehow conflicting with each other. The support for guards
brings conciseness but, at the same time, complicates exhaustiveness checking. A guard might call some function whose
execution result is unknown at compile-time, making the

GPCE ’18, November 5–6, 2018, Boston, MA, USAreachability of that case clause hard to check. Regarding extensibility and composability, essentially what makes patternmatching hard to be extended or composed is that the caseclauses are order-sensitive and gathered in one definition.
We observe that it is useful to distinguish between toplevel (shallow) patterns and nested (deep) patterns. Top-level
patterns should be order-insensitive and split into multiple
definitions so that they can be easily composed. For many
functions nested patterns often have a good default. That isthe case for the nested patterns in eval1 as well as other examples illustrated in Section 3. While there are operations forwhich sometimes nested patterns do not have good defaults,
in our personal experience and also the extended case study
in Section 5 these operations are not very common in practice. Therefore we propose an approach for nested patterns
that offers conciseness for the common case: nested patterns
should come with a default so that they would work for variant extensions. We apply this key insight in designing the
Castor framework, which turns out to be compared favorably in terms of the four properties among the approaches.
An overview of Castor will come next in Section 3.

3

An Overview of Castor

This section presents the Castor framework. We first show
how to model the Arith language discussed in Section 2
using Castor and discuss how this implementation meetsthe desirable properties. We then show how to define various
types of operations that pose previously identified challenges
in a modular setting. In particular, we show that dependent
operations [30], context-sensitive operations [18] and multisorted languages [28] can be nicely modeled in Castor.
3.1 Arith with Castor
A nice aspect of the Visitor pattern is that it decentralizes
pattern matching into multiple, order-insensitive methods.
Taking the best of both worlds, Castor combines open caseclasses with extensible visitors [15, 26, 27]. To reduce thecomplexity and verbosity incurred by visitors, Castor employs metaprogramming for generating boilerplate.
Recall the Arith language shown in Figure 1. With Castor, it is possible to model Arith in a concise and modularway, as shown in Figure 5. A Castor component is a trait annotated with @family. Component Term serves as the root of
all terms, where an open data type Tm is declared and marked
as @adt. The signature of the small-step evaluator is specified by the inner trait Eval1, where @default(Tm) denotesthat Eval1 is an operation on Tm with a default behavior. The
output type of Eval1 is declared by setting the abstract typeOTm as Tm. The default behavior is specified via the otherwise
method, which throws a NoRuleApplies exception. Nat andBool are independent extensions to Term that are defined
separately as two Castor components. Nat, for example,
extends the data type Tm with TmZero, TmSucc and TmPred

Weixin Zhang and Bruno C. d. S. Oliveira@family trait Term {@adt trait Tm // Datatype declaration@default(Tm) trait Eval1 { // Signature
type OTm = Tm
def otherwise = _ => throw NoRuleApplies}}@family trait Nat extends Term {// Datatype extension@adt trait Tm extends super.Tm {def TmZero: Tm
def TmSucc: Tm => Tm
def TmPred: Tm => Tm}
def nv(t: Tm): Boolean = ... // Same as in Figure 3@default(Tm) trait Eval1 extends super.Eval1 {override def tmSucc = t => TmSucc(this(t))
override def tmPred = {case TmZero => TmZerocase TmSucc(t) if nv(t) => tcase t => TmPred(this(t))}}}@family trait Bool extends Term {@adt trait Tm extends super.Tm {def TmTrue: Tm
def TmFalse: Tm
def TmIf: (Tm,Tm,Tm) => Tm}@default(Tm) trait Eval1 extends super.Eval1 {override def tmIf = {case (TmTrue,t2,_) => t2
case (TmFalse,_,t3) => t3
case (t1,t2,t3) => TmIf(this(t1),t2,t3)}}}@family trait Arith extends Nat with Bool {@adt trait Tm extends super[Nat].Tm
with super[Bool].Tm {def TmIsZero: Tm => Tm}@visit(Tm) trait Eval1 extends super[Nat].Eval1
with super[Bool].Eval1 {def tmIsZero = {case TmZero => TmTruecase TmSucc(t) if nv(t) => TmFalse
case t => TmIsZero(this(t))}}}

Figure 5. Implementing Arith with Castor.
methods. These capitalized methods use function types toexpress how to construct these variants. As opposed to thecase classes counterpart, methods are more compact.
The combination of case classes and visitors provides Castor with flexibility in defining operations over Tm. Operations that focus on a fixed subset of variants and have a good
default like nv are defined as functions. Ordinary operations
like Eval1 are defined as visitors for retaining composability.
But unlike normal visitors, nested case analysis is much simplified via (nested) pattern matching rather than auxiliary

Pattern Matching in an Open WorldGPCE ’18, November 5–6, 2018, Boston, MA, USA

visitors. Take the evaluation of a predecessor term for example. When a predecessor is processed by Eval1, it will be recognized and dispatched to the tmPred method. Then its innerterm is pattern matched using several case clauses via Scala’s
anonymous function syntax. As these are case clauses, deep
patterns and guards can be used. To apply Eval1 on the inner
term, we call this(t). To restore the convenience of wildcards for visitors, Castor provides an annotation @default,
which provides a default implementation for all known variants. By annotating @default and inheriting otherwise fromTerm’s Eval1, we only need to override interesting cases.
Definitions from Nat and Bool are easily combined in Arith
through Scala’s mixin composition. Datatype definitions are
merged with a new constructor for the zero test. With toplevel patterns split into different methods, Eval1 from Nat
and Bool are merged without conflicts. The only thing weneed to do is to complement the case for zero test. As thezero test is a case that requires programmer written code,
Arith’s Eval1 is annotated with @visit rather than @default.
Client Code. A Castor component can be directly imported
in client code. Here are some tests on Arith:@family @adts(Tm) @ops(Eval1)
trait PrintArith extends Arith {@default(Tm) trait PtmTerm {type OTm = String
def otherwise = ptmAppTerm(_)
override def tmIf = "if " + this(_) +" then " + this(_) + " else " + this(_)}@default(Tm) trait PtmAppTerm {type OTm = String
def otherwise = ptmATerm(_)
override def tmPred = "pred " + ptmATerm(_)
override def tmSucc = "succ " + ptmATerm(_)
override def tmIsZero = "iszero " + ptmATerm(_)}@default(Tm) trait PtmATerm {type OTm = String
def otherwise = "(" + ptmTerm(_) + ")"override def tmZero = "0"
override def tmTrue = "true"
override def tmFalse = "false"}}

import Arith._val tm = TmIsZero(
TmIf(TmFalse,TmTrue,TmPred(TmSucc(TmZero))))eval1(tm) // TmIsZero(TmPred(TmSucc(TmZero)))eval1(eval1(tm)) // TmIsZero(TmZero)eval1(eval1(eval1(tm))) // TmTrue
By importing Arith, we are able to construct a term using
all the variants including those from Nat and Bool. Castor’sFigure 6. Pretty printer for Arith.

visitors are used like normal functions with their lowercase
name. The constructed term is evaluated step by step usingeval1 and the result for each step is shown in the comments.
Discussion. Here we discuss how Castor addresses thefour desirable properties:• Conciseness. By employing Scala’s concise syntax andmetaprogramming, Castor greatly simplifies the definition and usage of visitors. In particular, the need for auxiliary visitors in performing deep case analysis is now
replaced by pattern matching via case clauses. The concept of visitors is even made transparent to the end user,
making the framework more user-friendly.
• Exhaustiveness. The exhaustiveness of patterns in Castor consists of two parts. Top-level patterns are methods,
whose exhaustiveness is checked in the code generation
phase by the Scala compiler (see Section 4 for details). For
nested patterns using case clauses, a default must be provided. However, this is neither statically enforced by Scala
nor Castor. Note, however, that with specialized language
support it is possible to enforce that nested always provide
a default. This is precisely what EADDs [40] do.
• Extensibility. As illustrated by Nat, Bool and Arith, we
can extend the datatype with new variants and operations,modularly. Such extensibility is enabled by the underlying
extensible visitor encoding (see Section 4 for details).

• Composability. Castor obtains composability via Scala’s
mixin composition, as illustrated by Arith. Unlike partial
functions, which silently compose overlapped patterns,
composing overlapped patterns in Castor will trigger
compilation errors because they are conflicting methods
from different traits. The error message will indicate thesource of conflicts and we are free to select an implementation in resolving the conflict.
3.2

Pretty Printing: Operations with Dependencies

Operations that depend (or even mutually depend) on otheroperations pose additional challenges for modularity [30].
Castor fully supports modular dependent operations.
Consider implementing a pretty printer for Arith. To
print out parenthesis only when necessary, we classify terms
according to whether they are primitives or applications.
Figure 6 gives the implementation, which illustrates how to
add new (possibly dependent) operations with Castor. The
pretty printer consists of three mutually dependent visitors:
PtmTerm, PtmAppTerm and PtmATerm, each of which focuses ona subset of terms and delegates remaining cases to others.
Castor allows operations with complex dependencies to be
defined in a natural and modular way. We can directly refer toother visitors in scope via their lowercase name and use themas normal functions. For instance, visitor PtmTerm delegates
its boring cases to visitor PtmAppTerm by supplying the term
to ptmAppTerm. The magic under the hood is that Castor
generates a lowercase val declaration for each visitor, whichallows the visitor to be used elsewhere. @adt and @ops areauxiliary annotations that provide information for Castor
in generating code. More details will come in Section 4.

GPCE ’18, November 5–6, 2018, Boston, MA, USA
3.3

Weixin Zhang and Bruno C. d. S. Oliveiracase ty@Some(TyNat) => tycase _ => None }def tmPred = tmSucc // Case definition reuseddef tmTrue = Some(TyBool)def tmFalse = tmTrue // Case definition reuseddef tmIf = (t1,t2,t3) =>(this(t1),this(t2),this(t3)) match {case (Some(TyBool),o2,o3) if o2==o3 => o2case _ => None }def tmIsZero = t => this(t) match {case Some(TyNat) => Some(TyBool)case _ => None }Structural Equality

Structural equality is an operation that checks whether two
terms are constructed consistently. We can already compare
the structural equality of two terms using == thanks to theequals method injected by the case keyword. Still, manually encoding structural equality is interesting as it shows
how to pattern match on multiple arguments. A Castor
implementation of structural equality for Arith is:@family @adts(Tm) @ops(Eval1)
trait EqArith extends Arith {@visit(Tm) trait Equal {type OTm = Tm => Boolean
def tmZero = {case TmZero => truecase _ => false }def tmSucc = t => {case TmSucc(s) => this(t)(s)case _ => false }... // Definition for other cases elided}}
Equal is a context-sensitive visitor [15] whose context is thesecond term being compared. To capture the context, we
instantiate the output type OTm as a function type Tm =>Boolean. Pattern matching on the two terms is done differently: the shape of the first term is revealed by the visit
methods whereas the shape of the second term is revealed
by case clauses. We then recursively compare their subterms
if they fall in the same pattern; otherwise, a false is returned.
Note that all cases share the same default (false). We could
use Scala’s pattern matching mechanism to avoid duplicatingthat default by overriding the generated apply method:
override def apply(t: Tm) = s => {try { t.accept(this)(s) }catch { case _: MatchError => false }}When two terms are constructed differently, a MatchError exception is thrown. The apply method catches that exception
and returns false. However, we prefer to use nested caseanalysis with a default to stick to the core ideas in Castor.
3.4}}

Like Tm, Ty is a datatype for representing types. Two concrete
types, TyNat and TyBool, are introduced for classifying terms
that produces numbers or boolean values. A visitor Typeof isdefined for type checking terms. The output type of Typeof
is Option[Ty], indicating that if a term is well-typed, some
type will be returned; otherwise a None will be returned. One
interesting thing to notice is that for variants that share thesame signature and behavior, it is sufficient to define thebehavior once and reuse the definition for other variants, as
illustrated by tmSucc and tmPred. Such reuse is, however, hardto achieve for case clauses because they are not referable.

4

Extensible Visitors and Code Generation

The power of Castor comes from the underlying extensible
visitors. The extensible visitor encoding combines ideas fromprevious work [15, 26, 27, 42] for better supporting patternmatching. Furthermore, Castor employs Scalameta [1, 5],
a modern Scala meta-programming library, for generating
the boilerplate required by the visitor encoding. This section
first presents the encoding by explaining the generated code
for Arith shown in Figure 5 and then formalizes the code
generation and discusses the limitations of Castor.
4.1

An Encoding of Extensible Visitors

Recall the Castor implementation of Arith shown in Figure 5. Let us first have a look at the generated code for Term:

Typed Arith

The Arith language presented so far allows erroneous terms
like TmPred(TmTrue) to be constructed. To rule out erroneousterms, we introduce types and a type-checking operation
to the Arith language. The introduction of types evolves
Arith from an untyped language to a typed language:@family @adts(Tm) @ops(Eval1)
trait TyArith extends Arith {@adt trait Ty {def TyNat: Ty
def TyBool: Ty}@visit(Tm) trait Typeof {type OTm = Option[Ty]def tmZero = Some(TyNat)
def tmSucc = t => this(t) match {trait Term {type TmV <: TmVisit
abstract class Tm { def accept(v: TmV): v.OTm }trait TmVisit { _: TmV =>type OTm
def apply(t: Tm) = t.accept(this) }trait TmDefault extends TmVisit { _: TmV =>def otherwise: Tm => OTm }trait Eval1 extends TmDefault { _: TmV => ... }val eval1: Eval1}

The visitor encoding presented here is slightly different
from the one shown in Figure 2. The use of several Scalaspecific features requires explanations. Instead of directly
using TmVisit in declaring the accept method, we use TmV-an
abstract type bounded by TmVisit. This decouples Tm fromPattern Matching in an Open Worlda specific visitor interface, allowing covariant refinementon the upper bound of TmV to account for new data variants.
The return type of the visit methods is parameterized by an
abstract type OTm rather than a type parameter. Hence thereturn type of accept is now a path dependent type v.OTm. A
syntactic sugar method apply is defined inside TmVisit for
enabling v(t) as a shorthand of t.accept(v), where t and v
are instances of Tm and TmVisit respectively. To pass this as
an argument of accept in implementing apply, we state that
TmVisit is of type TmV using a self-type annotation. TmDefault
is the default visitor interface, which extends TmVisit with
an otherwise method for specifying the default behavior.
Eval1 is a visitor annotated with @default, thus extending
TmDefault with a self-type annotation. There is a corresponding val with lowercase name generated for Eval1, which not
only allows the visitor to be used like normal functions but
also facilitates exhaustiveness checking, as seen later.
The encoding makes more sense with the following generated code for Nat:
trait Nat extends Term {type TmV <: TmVisit
case object TmZero extends Tm {def accept(v: TmV): v.OTm = v.tmZero }case class TmSucc(t: Tm) extends Tm {def accept(v: TmV): v.OTm = v.tmSucc(t) }case class TmPred(t: Tm) extends Tm {def accept(v: TmV): v.OTm = v.tmPred(t) }trait TmVisit extends super.TmVisit { _: TmV =>def tmZero: OTm
def tmSucc: Tm => OTm
def tmPred: Tm => OTm }trait TmDefault extends TmVisit
with super.TmDefault { _: TmV =>def tmZero = otherwise(TmZero)def tmSucc = t => otherwise(TmSucc(t))
def tmPred = t => otherwise(TmPred(t)) }def nv(t: Tm): Boolean = ...
trait Eval1 extends TmDefault
with super.Eval1 { _: TmV => ... }}The constructors of Tm are transformed to case classes/objects
that extend Tm. To implement the accept method, TmVisit isextended with lowercase visit methods one for each constructor. The upper bound of TmV is refined as the new TmVisitto allow invocations on extended visit methods in implementing accept for new subclasses of Tm. TmDefault is a default visitor that provides an implementation for each visit
method. The default implementation reconstructs the termand passes it to the otherwise method. nv remains unchanged
while Eval1 is modified by extending TmDefault and annotating itself as TmV. Bool and Arith are transformed in the sameway. Their definitions are elided for space reasons.
Companion Object. Besides modifying the trait annotatedwith @family, Castor also automatically generates a companion object for it, e.g. Nat:GPCE ’18, November 5–6, 2018, Boston, MA, USA
Fam ::= @family @adts( D ) @ops(V )trait F extends F { Adt V is}
Adt ::= @adt trait D extends super[F ].D { Ctr}
V is ::= @a( D ) trait V extends super[F ].V { . . . }a::= default | visit
Ctr ::= def C :D | def C :(T )=>DT::= D | Int | Boolean | T =>T
Figure 7. Syntax.
object Nat extends Nat {type TmV = TmVisit
object eval1 extends Eval1 }Castor tries to bind all the abstract types to their corresponding visitor interfaces. Moreover, the val declarations
are met by singleton objects that extend traits with capitalized names. Automatically generating companion objects
is useful for two reasons. Firstly, it provides exhaustivenesschecking for concrete visitors. That is, if a visitor does not implement all the visit methods, the object creation fails, withthe missing methods being reported to the user. Secondly,
the companion objects can be directly imported into client
code, simplifying the usage of Castor components.
4.2

Formalized Code Generation

We can see that although the extensible visitor encoding
is powerful, directly programming with it is cumbersome.
Moreover, the encoding relies on advanced features of Scala,making it less accessible to novice Scala programmers. To
reduce the complexity and verbosity of the encoding, Castor employs Scalameta based macro annotations [1, 5] ingenerating code. With Scalameta, we are able to modify theparsed source program before type-checking takes place.
Figure 7 describes valid Scala programs accepted by Castor. Uppercase meta-variables range over capitalized names.
A is written as a shorthand for sequence A1 •. . .•An , where •denotes with, comma or semicolon according to the context.
Figure 8 formalizes the translation. We use semantic brackets(⟦·⟧) in defining the translation rules and angle brackets (<>)
for processing sequences. The translation is quite straightforward. One can easily see that processing Term and Nat
through Figure 8 generates the code shown previously. Here
we briefly discuss some interesting cases. A trait is recognized as a base case if it extends nothing. Base cases needextra declarations such as abstract class for datatypes orval declaration for visitors. Non-argument constructors aretranslated to case objects rather than case classes.
4.3

Limitations

Castor has some limitations due to the use of metaprogramming and the restrictions from the current Scalameta library:• Unnecessary annotations. With the current version of
Scalameta, we are not able to get information from annotated parents. If parents’ information were accessible,
annotations @adts and @ops could be eliminated.

GPCE ’18, November 5–6, 2018, Boston, MA, USA

Weixin Zhang and Bruno C. d. S. Oliveira⟦@family @adts( D ) @ops(V ) trait F extends F { Adt V is} ⟧ =FullSub
FullSimple
trait F extends F { ⟦Adt⟧ ⟦V is⟧}MoreExt
RcdSubBot
FullError
object F extends F {⟨type D V = D Visit | D ∈ D ∪ Adt⟩
Extension
Bot
Variant⟨object v extends V | V ∈ V ∪ V is⟩}
TyRcd
TyStr
TyArithFullUntyped
SimpleBool
TyLet
Top
⟦@adt trait D { Ctr} ⟧ =RecordTyNat
StrTyBoolArith
UntypedLet
Typedtype D V <:D Visit
abstract class D { def accept(v:D V): v.OD}
Type
Nat
Bool
VarApp⟦Ctr ⟧
Term
trait D Visit { _: D V =>type OD
def apply(x:D ) = x.accept(this)Figure 9. Simplified inheritance graph.
⟦Ctr ⟧visit }the modified program rather than the original program.
trait D Default extends D Visit { _: D V =>Reasoning about the error messages becomes harder as
def otherwise:D => OD
they are mispositioned and require some understanding⟦Ctr ⟧de f aul t }of the generated code.
⟦@adt trait D extends super[F ].D { Ctr} ⟧ =type D V <:D Visit
5 Case Study and Evaluation⟦Ctr ⟧
To give some evidence on the expressivity and effectivenesstrait D Visit extends super[F ].D Visitof Castor, we conduct a case study on TAPL [31]. Examples{ _: D V =>⟦Ctr ⟧visit }shown in previous sections are directly from or greatly intrait D Default extends D Visit with super[F ].D Default
spired by the TAPL case study. TAPL are a good benchmark{ _: D V => ⟦Ctr ⟧de f aul t }for assessing the capabilities of modular pattern matching⟦def C :D⟧ =and has been adopted by EVF [42]. The reason is that corecase object C extends D { def accept(v:D V) = v.c}data structures of TAPL interpreters, types and terms, are⟦def C :(T )=>D⟧ =modeled using algebraic datatypes; operations over types
case class C(x :T ) extends D { def accept(v:D V) = v.c(x )} and terms are defined via pattern matching. There are a few⟦def C :D⟧visit = def c :OD
operations that require nested patterns: small-step seman⟦def C : (T )=>D⟧visit = def c :(T )=>OD
tics, type equality and subtyping relations. They all come⟦def C :D⟧de f aul t = def c = otherwise(C )with a default. The data structures and associated operations⟦def C : (T )=>D⟧de f aul t = def c = (x )=> otherwise(C(x ))should be modular as new language features are introduced⟦@a( D ) trait V { . . . } ⟧ =and combined. However, without proper support for modutrait V extends DA { _: D V => . . . }lar pattern matching, the original implementation duplicatesval v : Vcode for features that could be shared. With Castor andtechniques shown in Section 3, we are able to refactor the⟦@a( D ) trait V extends super[F ].V { . . . } ⟧ =non-modular implementation into a modular manner. Our
trait V extends DA with super[F ].V { _: D V => . . . }evaluation shows that the refactored version significantly⟦X ⟧ = ⟨⟦X ⟧ | X ∈ X ⟩reduces the SLOC. However, at the moment, improved modularity does come at some performance penalty.
Figure 8. Translation.
• Boilerplate nested composition. Lacking of parents’ information also disallows automatically composing nested
members. Assuming that automatic nested composition isavailable, Arith shown in Figure 5 can be simplified as:@family trait Arith extends Nat with Bool {@adt trait Tm { ... }@visit(Tm) trait Eval1 { ... }}By expressing the inheritance relationship once at the family level, extend clauses for members such as super[Nat].Tm
with super[Bool].Tm can be inferred.
• Imprecise error messages. As Castor modifies the annotated programs, what the compiler reports are errors on

5.1

Overview

The Scala implementation of TAPL [3] strictly follows theoriginal OCaml version, which uses sealed case classes andpattern matching. The first 10 languages (arith, untyped,
fulluntyped, tyarith, simplebool, fullsimple, fullerror, bot, rcdsubbot and fullsub) are our candidates for refactoring. Eachlanguage implementation consists of 4 files: parser, syntax,
core and demo. These languages cover various features including arithmetic, lambda calculus, records, fix points, error
handling, subtyping, etc. Features are shared among these
10 languages. For example, arith is included by fulluntyped,
fullsimple and fullsub. However, such featuring sharing isachieved via duplicating code, causing problems like:Pattern Matching in an Open WorldGPCE ’18, November 5–6, 2018, Boston, MA, USA
Evaluation time (ms)Table 2. SLOC evaluation of TAPL interpreters
Extracted Castorbool
71
extension
24
str
42
let
48
moreext
112
nat
85
record
117
top
79
typed
82
varapp40
variant
136
misc
212

EVF
98
34
55
47
106
103
198
86
138
65
161
172

Language Castorarith
31
untyped40
fulluntyped
18
tyarith22
simplebool
24
fullsimple
24
fullerror
68
bot
40
rcdsubbot
30
fullsub
57

EVF
33
46
47
26
38
83
105
61
39
116

Scala
106
124
256
157
212
619
396
190
257
618

Total

1857

2935

fulluntyped
tyarithsimplebool

82.6

290.9

157.9
124.3

655.3

208

fullsimple
bot

406.8

158.9

387.3

172.7

fullerror
rcdsubbot

337.3

120.6

418.5

205.5

fullsub

531.3

166

0

Scala

312.9

166.6

175

350

525

700

Figure 10. Performance evaluation of TAPL interpreters.
Evaluation time (ms)1402

• Inconsistent definitions. Lambdas are printed as "lambda"
in all languages except untyped, which is "\".
• Feature leaks. Features introduced in the latter part ofthe book (e.g. System F) leak to previous language implementations such as fullsimple.
Our refactoring focuses on syntax and core where datatypes
and associated operations are defined. Figure 9 gives a simplified high-level overview of the refactored implementation.
The candidate languages are represented as gray boxes andextracted features/sub-languages are represented as whiteboxes. From Figure 9 we can see that the interactions between languages (revealed by the arrows) are quite intense.
5.2

Castor

105.4
84.8

arith
untypedEvaluation

We evaluate Castor by answering the following questions:• Q1. Is Castor effective in reducing SLOC?
• Q2. How does Castor compare to EVF [42]?
• Q3. How much performance penalty does Castor incur?
Q1. Table 2 reports the SLOC comparison results. With
shared features modularly extracted and reused, Castor
reduces over half of the total SLOC compared to the nonmodular implementation written in plain Scala.
Q2. Table 2 also compares Castor with EVF [42], a modular
visitor framework in Java. Like Castor, EVF automaticallygenerates boilerplate code associated with visitors. However,
better support for pattern matching and more concise syntax
for Castor result in around 25% SLOC reduction with respect
to EVF. Moreover, EVF requires manual instantiation fromJava interfaces to classes for creating objects. The instantiation burden can be quite heavy for feature-rich languages.
Castor completely removes the burden of instantiation by
generating companion objects automatically.
Q3. To measure the performance, we randomly generate
10,000 terms for each language and calculate the average
evaluation time for 10 runs. The ScalaMeter [2] microbenchmark framework is used for performance measurements. The
benchmark programs are compiled using Scala 2.12.3 andexecuted on a MacBook Pro with 2.6 GHz Intel Core i5 with
8 GB memory. Figure 10 compares the execution time in

VisitorSealed case class
Open case classPartial function
Castor

93.8
84.8
96.3
121.3
105.4
0

32.5

65

97.5

130

Figure 11. Performance evaluation of Arith.
milliseconds. From the figure we can see that Castor implementations have a 1.24x (arith) to 3.2x (fullsub) slowdownwith respect to the corresponding non-modular Scala implementations. Figure 11 further compares the performanceof the Arith implementations discussed in Section 2. Without surprise, modular implementations are slower than nonmodular implementations. With underlying optimizations,
implementations based on case classes are faster than implementations based on visitors. The implementation in partial
function is worst due to the heavy use of exception handling.
Discussion. We believe that the performance penalty ismainly caused by method dispatching. A modular implementation typically has a complex inheritance hierarchy.
Dispatching on a case needs to go across that hierarchy. Another source of performance might be the use of functions
instead of normal methods in visitors. Of course, more rigorous benchmarks need to be conducted to verify our guesses.
One possible way to boost the performance is to turn TAPL
interpreters into compilers via staging [33].

6

Related Work

Polymorphic Variants. OCaml supports polymorphic variants [11]. Unlike traditional variants, polymorphic variant
constructors are defined individually and are not tied to aparticular datatype. Garrigue [12] presents a solution to the
EP using polymorphic variants. To correctly deal with recursive calls, open recursion and an explicit fixed-point operator
must be used properly, otherwise the recursion may go to theoriginal function rather than the extended one. This causes
additional work for the programmer especially when theoperation has complex dependencies. In contrast, Castor
handles open recursion easily through OO dynamic dispatching, reducing the burden of programmers significantly.

GPCE ’18, November 5–6, 2018, Boston, MA, USA
Open Data Types and Open Functions. To solve the EP,
Löh and Hinze [22] propose to extend Haskell with open
datatypes and open functions. Different from classic closed
datatypes and closed functions, the open variants decentralize the definition of datatypes and functions and there isa mechanism that reassembles the pieces into a complete
definition. To avoid unanticipated captures caused by classic first-fit pattern matching, a best-fit scheme is proposed,
which rearranges patterns according to their specificness
rather than the order (e.g. wildcards are least specific). However open datatypes and open functions are not supported instandard Haskell and more importantly, they do not support
separate compilation: the source for all files with variants ofa datatype must be available for generating code.
Data Types à la Carte (DTC). DTC [37] encodes composable datatypes using existing features of Haskell. The idea is
to express extensible datatypes as a fixpoint of co-productsof functors. While it is possible to define operations thathave dependencies and/or require nested pattern matchingwith DTC, the encoding becomes complicated and needs significant machinery. There is some follow-up work that tries
to equip DTC with additional power. Bahr and Hvitved [4]extend DTC with GADTs [39] and automatically generates
boilerplate using Template Haskell [35]. Oliveira et al. [29]use list-of-functors instead of co-products to better simulate
OOP features subtyping, inheritance and overriding.
Modular Church-Encoded Interpreters. Solutions to the
EP based on Church encodings can also be used for developing modular interpreters. Well-known techniques are finallytagless [6], Object Algebras [28] and Polymorphic Embedding [16]. However, these techniques do not support patternmatching and/or dependencies, making it hard to define operations like small-step semantics discussed in Section 2.
Typical workarounds are defining the operation together
with the dependencies or use advanced features like intersection types and a merge operator [30, 32]. In contrast, Castor
allows us to implement operations that need nested patterns
and/or with dependencies in a simple, modular way.
Extractors. Extractors [9] are an alternative pattern matching mechanism in Scala. Extractors are objects with a userdefined unapply method that specifies how to tear down an
object. Compared to case classes, extractors are flexible, independent of classes but verbose. Emir et al. [9] further compare case classes and extractors with other four OO patternmatching techniques according to conciseness, maintainability and performance. Their results show that case classes
and extractors are complementary in terms of these criteria. Two criteria that we consider important—exhaustivenessand composability—are not addressed. Like open case classes,
extractors do not meet these two properties as well.
Other Approaches to Pattern Matching in OOP. There
are many attempts to introduce pattern matching into mainstream OOP languages like Java [14, 21] and C++ [36]. Some

Weixin Zhang and Bruno C. d. S. Oliveira
new OOP languages are designed with first-class patternmatching such as Newspeak [13], Fortress [34] or Grace [17].
Yet, how to cooperate pattern matching with the open nature of OOP class hierarchy while preserving the desirable
properties summarized in Section 1 is still challenging.
Extensible Visitors. Section 4 presents an extensible visitor encoding for modular pattern matching. The basis of theencoding comes from [26] and the use of case classes andthe way to express dependencies are inspired by [15, 27]. A
common problem of these encodings is that although powerful, they are too complicated for practical use. In contrast,
Castor simplifies the encoding through meta-programming.
Similar idea has been adopted in EVF [42] which generates
boilerplate associated with visitors through Java annotation
processor. Unlike Castor, nested pattern matching in EVF
is simulated via constructing anonymous visitors with fluent setters and Java 8’s lambdas [41]. Consequently, deep
patterns and guards are not supported and the notation overhead is much higher than Scala’s case clauses. EVF also generates various traversal templates for eliminating boilerplatein querying and transforming AST structures. Essentially,
these traversal templates can be ported to Castor by generating code and providing annotations similar to @default.

7

Conclusion and Future Work

This work argues that pattern matching in an extensible
setting would benefit from an unordered semantics for (toplevel) patterns. In essence, extensibility and composability
do not interact well with ordered patterns. To accommodate
for the convenience of nested patterns, we propose a secondcase analysis mechanism with defaults. We argue that suchnested patterns often have good default for most operationsin practice. This is partly validated by our case study, wherepractically all operations that used nested case analysis had
good defaults for such nested patterns. We applied this idea
in designing Castor, a Scala meta-programming frameworkthat allows programmers to write concise, exhaustive, extensible and composable pattern matching code. While Castor is practical and serves the purpose of demonstrating
our points regarding pattern matching, there are important
drawbacks on such a meta-programming, library-based approach: error reporting is imprecise; the syntax and typingof Scala cannot be changed to enforce certain restrictions.
A worthwhile path for future work would be to study amore principled language design that builds on the ideas ofthis work. Another path would be to support GADTs [39].
There is some initial support for GADTs that allows simple,
typed, embedded DSLs to be modeled with Castor. For spacereasons, we do not discuss such support in this paper. We
would like continue the investigation and see if more realistic
embedded DSLs can be modeled with Castor.

Pattern Matching in an Open World

References[1] [n. d.]. Scalameta. http://scalameta.org/. ([n. d.]).
[2] [n. d.]. ScalaMeter. http://scalameter.github.io/. ([n. d.]).
[3] [n. d.]. TAPL Scala. https://github.com/ilya-klyuchnikov/tapl-scala/.
([n. d.]).
[4] Patrick Bahr and Tom Hvitved. 2011. Compositional data types. In
Proceedings of the seventh ACM SIGPLAN workshop on Generic programming. ACM, 83–94.
[5] Eugene Burmako. 2017. Unification of Compile-Time and Runtime
Metaprogramming in Scala. Ph.D. Dissertation. EPFL.
[6] Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan. 2009. Finallytagless, partially evaluated: Tagless staged interpreters for simpler
typed languages. Journal of Functional Programming 19, 5 (2009),
509–543.
[7] Craig Chambers. 1992. Object-oriented multi-methods in Cecil. In
European Conference on Object-Oriented Programming.
[8] Curtis Clifton, Gary T Leavens, Craig Chambers, and Todd Millstein.
2000. MultiJava: Modular open classes and symmetric multiple dispatch for Java. In ACM Sigplan Notices, Vol. 35. ACM, 130–145.
[9] Burak Emir, Martin Odersky, and John Williams. 2007. Matching
objects with patterns. In European Conference on Object-Oriented Programming.
[10] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides.
1994. Design Patterns : Elements of Reusable Object-Oriented Software.
Addisson-Wesley.
[11] Jacques Garrigue. 1998. Programming with polymorphic variants. In
ML Workshop.
[12] Jacques Garrigue. 2000. Code reuse through polymorphic variants. In
Workshop on Foundations of Software Engineering.
[13] Felix Geller, Robert Hirschfeld, and Gilad Bracha. 2010. Pattern Matching for an object-oriented and dynamically typed programming language.
Number 36. Universitätsverlag Potsdam.
[14] Martin Hirzel, Nathaniel Nystrom, Bard Bloom, and Jan Vitek. 2008.
Matchete: Paths through the pattern matching jungle. In International
Symposium on Practical Aspects of Declarative Languages.
[15] Christian Hofer and Klaus Ostermann. 2010. Modular Domain-specific
Language Components in Scala. In Proceedings of the Ninth International Conference on Generative Programming and Component Engineering (GPCE ’10).
[16] Christian Hofer, Klaus Ostermann, Tillmann Rendel, and Adriaan
Moors. 2008. Polymorphic Embedding of Dsls. In Proceedings of the 7thInternational Conference on Generative Programming and Component
Engineering (GPCE ’08).
[17] Michael Homer, James Noble, Kim B. Bruce, Andrew P. Black, andDavid J. Pearce. 2012. Patterns As Objects in Grace. In Proceedings of
the 8th Symposium on Dynamic Languages (DLS ’12). New York, NY,
USA, 17–28.
[18] Pablo Inostroza and Tijs van der Storm. 2015. Modular Interpreters
for the Masses: Implicit Context Propagation Using Object Algebras.
In Proceedings of the 2015 ACM SIGPLAN International Conference on
Generative Programming: Concepts and Experiences.
[19] Chinawat Isradisaikul and Andrew C. Myers. 2013. Reconciling Exhaustive Pattern Matching with Objects. In Proceedings of the 34th
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’13).
[20] Simon Peyton Jones. 2003. Haskell 98 language and libraries: the revised
report. Cambridge University Press.
[21] Jed Liu and Andrew C Myers. 2003. JMatch: Iterable abstract patternmatching for Java. In PADL.
[22] Andres Löh and Ralf Hinze. 2006. Open data types and open functions.
In Proceedings of the 8th ACM SIGPLAN international conference on

GPCE ’18, November 5–6, 2018, Boston, MA, USA
Principles and practice of declarative programming.
[23] Todd Millstein, Colin Bleckner, and Craig Chambers. 2004. Modular
Typechecking for Hierarchically Extensible Datatypes and Functions.
ACM Trans. Program. Lang. Syst. 26, 5 (Sept. 2004).
[24] Robin Milner, Mads Tofte, Robert Harper, and David Macqueen. 1997.
The Definition of Standard ML-Revised. (1997).
[25] Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stéphane Micheloud, Nikolay Mihaylov, Michel Schinz,
Erik Stenman, and Matthias Zenger. 2004. An overview of the Scala
programming language. Technical Report.
[26] Martin Odersky and Matthias Zenger. 2005. Independently extensible
solutions to the expression problem. In The 12th International Workshop
on Foundations of Object-Oriented Languages.
[27] Bruno C. d. S. Oliveira. 2009. Modular Visitor Components. In Proceedings of the 23rd European Conference on Object-Oriented Programming.
[28] Bruno C. d. S. Oliveira and William R. Cook. 2012. Extensibility for the
Masses: Practical Extensibility with Object Algebras. In Proceedings ofthe 26th European Conference on Object-Oriented Programming.
[29] Bruno C. d. S. Oliveira, Shin-Cheng Mu, and Shu-Hung You. 2015.
Modular Reifiable Matching: A List-of-functors Approach to Twolevel Types. In Proceedings of the 2015 ACM SIGPLAN Symposium on
Haskell (Haskell ’15).
[30] Bruno C. d. S. Oliveira, Tijs van der Storm, Alex Loh, and William R.
Cook. 2013. Feature-Oriented Programming with Object Algebras.
In Proceedings of the 27th European Conference on Object-Oriented
Programming.
[31] Benjamin C Pierce. 2002. Types and programming languages. MITpress.
[32] Tillmann Rendel, Jonathan Immanuel Brachthäuser, and Klaus Ostermann. 2014. From Object Algebras to Attribute Grammars. In Proceedings of the 2014 ACM International Conference on Object-Oriented
Programming Systems Languages and Applications.
[33] Tiark Rompf and Martin Odersky. 2010. Lightweight Modular Staging:
A Pragmatic Approach to Runtime Code Generation and Compiled
DSLs. In In GPCE.
[34] Sukyoung Ryu, Changhee Park, and Guy L Steele Jr. 2010. Adding pattern matching to existing object-oriented languages. In ACM SIGPLAN
Foundations of Object-Oriented Languages Workshop.
[35] Tim Sheard and Simon Peyton Jones. 2002.
Template metaprogramming for Haskell. In Proceedings of the 2002 ACM SIGPLAN
workshop on Haskell.
[36] Yuriy Solodkyy, Gabriel Dos Reis, and Bjarne Stroustrup. 2013. Open
Pattern Matching for C++. In Proceedings of the 12th International Conference on Generative Programming: Concepts and Experiences (GPCE’13).
[37] Wouter Swierstra. 2008. Data types à la carte. Journal of functional
programming 18, 4 (2008), 423–436.
[38] Philip Wadler. 1998. The Expression Problem. Email. (Nov. 1998).
Discussion on the Java Genericity mailing list.
[39] Hongwei Xi, Chiyan Chen, and Gang Chen. 2003. Guarded Recursive Datatype Constructors. In Proceedings of the 30th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages (POPL’03).
[40] Matthias Zenger and Martin Odersky. 2001. Extensible Algebraic
Datatypes with Defaults. In Proceedings of the Sixth ACM SIGPLAN
International Conference on Functional Programming.
[41] Weixin Zhang. 2017. Extensible domain-specific languages in objectoriented programming. HKU Theses Online (HKUTO) (2017).
[42] Weixin Zhang and Bruno C. d. S. Oliveira. 2017. EVF: An Extensible
and Expressive Visitor Framework for Programming Language Reuse.
In European Conference on Object-Oriented Programming.