Disjunctive patterns

From Successor ML

Contents 1 Introduction 2 Motivation and Example 3 Assumptions. 4 Syntax 5 Static Semantics 6 Dynamic Semantics 7 Interactions 8 Compatibility 9 Implementation

Introduction

We propose adding disjunctive patterns ("or-patterns") to SML.

Motivation and Example

Disjunctive patterns avoid the need for repeating the same right-hand side in a match several times, by allowing to fold multiple left-hand side patterns into one. In certain cases this can significantly reduce code size, as well as the temptation to write fragile catch-all clauses to get around the code duplication.

TODO: good example.

Assumptions.

None.

Syntax

Defined by the following modifications to the Definition:

• In Section 2.8, Figure 3, and Appendix B, Figure 21, add the following production (as the last one, giving least precedence):

   [pat ::=]       pat_1 | pat_2       disjunctive

• In Section 2.9, 2nd bullet, add the following comment:

[...] (identifiers appearing in both branches of a disjunctive pattern are bound only once)

Note that the syntax immediately supports writing multiple alternatives

   pat_1 | ... | pat_n

as well as "multiple" matches:

   case exp of
       A | B | C => 1
     | D | E => 2

Static Semantics

Defined by the following modifications to the Definition:

• In Section 4.10, Patterns, add the following rule:

   C |- pat_1 => (VE,tau)    C |- pat_2 => (VE,tau)
   ------------------------------------------------  (43a)
          C |- pat_1 | pat_2 => (VE,tau)

• In Section 4.11, item 2, insert the following sentence after the first one:

Similarly, in a disjunctive pattern of the form pat_1|pat_2, the second pattern must match some value not matched by the first one. Moreover, either of them must match some value that is not matched by the surrounding pattern or match rule.

Note that both alternatives must have the same type and bind the same variables.

The wording regarding irredundancy does require compilers to warn about cases like fn _|3 => (), but not fn 3|_ => (), although the latter is redundant as well. None of the compilers currently supporting disjunctive patterns seems to detect the latter, and it is not obvious how to extend the usual algorithm appropriately.

Dynamic Semantics

Defined by the following modifications to the Definition:

• In Section 6.7, Patterns, add the following rules:

       E,v |- pat_1 => VE
   --------------------------   (149a)
   E,v |- pat_1 | pat_2 => VE

   E,v |- pat_1 => FAIL    E,v |- pat_2 => VE/FAIL
   -----------------------------------------------   (149b)
          E,v |- pat_1 | pat_2 => VE/FAIL

Interactions

None.

Compatibility

This is a fully conservative extension.

Implementation

Not difficult. Disjunctive patterns have long been available in a number of ML systems (SML/NJ, OCaml, Alice ML).