    Author: Erik Søe Sørensen <eriksoe(at)gmail(dot)com>
    Status: Draft
    Type: Standards Track
    Created: 17-Feb-2012
    Erlang-Version: R15B-2
    Post-History:
****
EEP XXX: Pattern-test operator
----



Abstract
========

"What kind of conditions can be expressed in an Erlang pattern
condition (i.e. a pattern plus its guard)?"

An answer that would probably match many Erlangers' mental model is,
"any condition that (a) can be expressed as a fixed decision tree and
(b) involves only type tests, subvalue extractions, and equality and
inequality comparisons - and a few more operations, notably
arithmetics, conversion functions and length()."

However, the real answer is at present somewhat more complex and
irregular; certainly more so than there are technical grounds for.

The problem is in the differences between what the pattern and the
guard can express — there is overlap (which is not in itself bad),
and neither is more powerful than the other (which is not in itself
bad either) — but the total effect is as one might fear at such
non-orthogonality, namely that (a) sometimes one is forced use use the
less convenient option in order to express the desired condition, and
(b) there are surprising holes in what it is possible to express.

This EEP suggests a solution to this, in the form of a *pattern-test
operator* which

 * takes an expression and a pattern and evaluates to a boolean value;
 * is allowed in guard expressions;
 * makes guards strictly more powerful than their corresponding
    pattern parts, and only slightly less syntactically convenient;
 * is also usable in normal expressions, meaning that some 'case'
    expressions may be stated more concisely.



Specification
=============

A "pattern-test" operator is added to Erlang.
The operator may appear in guard expressions.

The pattern-test operator has the following syntax:

    expression ::= expression '~' pattern

and has precedence at the same level as the comparison operators
(level 300).

The operator has the following basic semantics:

    Evaluate the expression, then match the result R against the pattern.
    The whole expression evaluates to 'true' if R matches the pattern,
    otherwise it evaluates to 'false'.


Binding semantics
-----------------

In addition to the basic semantics, a pattern-test expression which
contains binding occurrences of variables in its pattern may bind
these variables.

Binding takes place just as for usual pattern matching, except that
the bindings are only accessible upon a result of 'true'.

This is only relevant in three contexts:

 * If a pattern-test expression is the first operand of an 'andalso'
   expression, then its bindings are visible in the second operand.

 * If a pattern-test expression is at top-level of a guard, then
   its bindings are visible in all of its subsequent siblings.

 * If a pattern-test expression is at top-level of a guard, and the
   [guard sequence][GuardSeqInManual] consists only of that one guard,
   then the bindings are visible in the guarded expression.

Examples of the three situations are shown here:

    X ~ {A,B}  andalso  A > B

    case ... of
      X  when  X ~ {A,B},  A > B -> ...
    end

    case ... of
      X  when  X ~ {A,B}, X /= {0,0} -> A + B
    end

Alternatively, the third rule can be generalized as follows — in line
with the rules for exporting bindings from case etc. constructs:

 * Any variables which are bound in *all* guards of a guard sequence
   are visible in its guarded expression.

An examples of this situation is shown here:

    case ... of
      X  when  X ~ {ok,A}; X ~ [okay,A} -> ...A...
    end


(Other context exists in which the variables are dynamically
guaranteed to be bound in certain subsequent expressions, e.g.

    case E0 ~ P of true -> E1; false -> E2 end

where, in principle, variables bound by P could be accessible in E1.
But as always, we have to draw the line somewhere.)



Motivation
==========

A central part to Erlang's control flow constructs is branching based
on pattern matching.  Erlang allows two parts in a pattern condition:
the pattern, and its associated guard.

The pattern part is characterised by syntactic convenience.  For
instance, patterns compose well, structurally.  This is quite useful
in relation to macros, for instance.

The guard part is characterised by power of expression.  For instance,
a guard can express nearly anything a pattern can express, and
quite a few things which aren't expressible by patterns.

It is most natural to describe the structural part of a condition in
the pattern; primarily because that's what the pattern is for,
secondarily because using the guard for describing structure is
associated with a significant amount of syntactic and cognitive
overhead.  Using the guard for describing structure is typically
cumbersome, unexpected on behalf of readers of the code, and not very
maintainable.

However, at present, certain kinds of conditions can only be expressed
in a way that is against the grain of the language — or not at all.

The proposed operator remedies these problems by making it possible to
express structural conditions in guards in a simple, readable and
composable manner.

The operator might also be used outside of guards, in normal
expressions, for increased conciseness and clarity of code.

Also of relevance is the fact that an [existing EEP][EEP 29] requires
something similar to the proposed operator for its implementation.


Irregularity
------------

Most branching constructs in Erlang contain a list of clauses.

The conditions of these clauses have two purposes: to serve as
conditions, and to bind variables.  They are made up from two parts: a
pattern and a guard.

At present, there is an irregular relation between the two parts:

 * A condition which can be described as a pattern can typically also
   be described as a guard.
 * Bit-patterns are an exception; they can only be expressed using patterns.
 * In certain other areas, guards are more expressive than patterns.
 * Only the pattern part can bind variables.

The two constructs are thus unorthogonal, yet depend on each other to
provide what they lack themselves.

For one thing, this means that in some cases, the pattern part turns
out not to be expressive enough, and then the structure description
will have to be moved — in whole or in part — from the pattern to
the guard.
As things stand, this kind of reorganization has a rather large
"refactoring distance" (i.e., amount of work needed to convert the
code from one form to a semantically equivalent one with different
properties.)
Also, having to write the condition in this less natural form reduces
readability.

In other cases, the shape of the desired condition is such that it is
not expressible at all as a pattern plus a guard (see below for an
example).


Negation and Disjunction of Patterns
------------------------------------

While conjunction of patterns is supported in Erlang, both implicitly
as part of structural matching and explicitly using the '=' operator,
there is currently no support for negation and disjunction of
patterns.

For instance, to receive any message which is not a `gen_server` call
or cast, you need to do this:

      receive
        X when not (is_tuple(X,2) andalso element(1,X)=='$gen_cast')
               andalso
               not (is_tuple(X,3) andalso element(1,X)=='$gen_call') ->
          {yes, X}
        after 0 -> no
      end.

With the proposed operator, this becomes a great deal more concise and
plain to read:

      receive
        X when not (X ~ {'$gen_cast',_} orelse
                    X ~ {'$gen_call',_,_} ->
          {yes, X}
        after 0 -> no
      end.

Another example is matching anything which is not a binary starting
with the byte "123".

At present, this does not appear to be possible at all.
With the proposed operator, it's straightforward:

      receive
        X when not X ~ <<123, _/binary>> ->
          {yes, X}
      end.


Locality/composability
----------------------

Pattern conditions lack in composability.
Of course, we cannot reuse pattern conditions per se, as they're not
first-class entities; however, we have a good approximation in the
form of macros:

    -define(POINT, {_,_}).
    -define(TWO_POINTS, [?POINT,?POINT]).

At present, though, this poor man's abstraction breaks down when the
pattern condition contains both a pattern and a guard:

    -define(INT_POINT(X,Y), {X,Y} when is_integer(X), is_integer(Y)).
    -define(TWO_INT_POINTS, ???).

To achieve this effect, it is necessary to express the entire
condition in form of a guard:

    -define(INT_POINT_GUARD(P), (is_tuple(P,2)
                                 andalso is_integer(element(1,P))
                                 andalso is_integer(element(2,P)) ) ).

This quickly becomes too cumbersome and unreadable to be useful in practise.

The problem is twofold: it is one of *syntactic non-locality* (which
makes the straightforward macro approach fall apart), and one of
*"refactoring distance"* between equivalent conditions as expressed in
a pattern and in a guard.



Rationale
=========

Using the tilde character for pattern matching has roots in AWK; other
languages (such as Perl) have used in it the same meaning, but in the
combination '=~'.


Solutions employed by other languages
-------------------------------------

The details of the problems are rather language specific, so solutions
from other languages can be used only as inspiration.  In particular,
the "pattern matching + preprocessor" combination does not seem to be
very common among programming languages.

Scala, for instance, has rather strong pattern matching but no
preprocessing; like in Erlang, patterns can have guards - but only one
for the entire pattern.  Patterns can be combined through disjunction
(`|`), however, and abstract patterns are supported through
`unapply()` and `unapplySeq()` methods. (This approach uses the OOP
and strong typing aspects of Scala, and is therefore not relevant for
Erlang.)

In "What", a language which was subject of my Master's thesis project
and which has pattern matching of XML/HTML structures as one of its
forces, a similar operator exists.  With its ability to conditionally
bind variables, it allowed for some nicely readable code.
(See section 3.4.2 and chapter 8 of the
[dissertation describing What][WhatPDF].)


Alternatives
------------

Depending on the problem statement, there are a number of alternative
solutions.  I'll mention and address some in the following.

- If the question is, "how do we fix the irregularity that pattern
  matching on binaries cannot be done using guard functions?", then
  the simple and obvious solution is to add guard functions for binary
  deconstruction.

- If the question is, "how do we make patterns more composable,
  syntactically?", then an alternative solution is to make patterns
  more expressive, by providing means of expressing disjunction and
  negation of patterns, as well as local guard conditions - e.g. with

    <pre>pattern ::= pattern 'or' pattern
              | 'not' pattern
              | pattern 'when' expression</pre>

- If the question is, "how do we support pattern matching in guard
  expressions?", then two alternative answers are to reuse existing
  syntactical pattern-matching constructs: 'case' or '='.

  - Using 'case': allow case expressions in guard expressions, with
    the restriction that all body expressions must be guard
    expressions.
  - Using '=': allow `guard_exp ::= pattern '=' guard_exp`.

h- If the question is, "how do we support pattern matching in guard
  expressions?", then another alternative solution is to add a new
  guard BIF, say, `matches_spec(E,MS)`, for matchspec testing.

- Finally, adding pattern conditions as first-class citizens to the
  language, e.g. in the form of abstract patterns ([EEP 29][]).

Some of these alternatives have enough merit that they could be
considered as independent extensions; that is certainly the case for
adding the missing guard functions.
However, the proposed solution appears to be the most flexible, as
well as appearing to lead to concise and readable solutions.

### Adding guard functions for binary deconstruction

Relevant missing guard functions for binary deconstruction are:

- `erlang:binary_part/3` or equivalent
- `binary:encode_signed/2` and `binary:encode_unsigned/2` or equivalent
  (possibly strengthened to allow bitstring decoding as well).
- Extraction of a floating-point value from a binary
- Extraction of a unicode character (and the remainder) from a binary

Adding these should remove the unorthogonality hole, but won't improve
pattern compositionality or readability.

### Strengthening the pattern syntax

This is in a way the complementary solution to the proposed one.
In particular, adding the possiblity of attaching guard expressions to
parts of the pattern — rather than only to the full pattern --
mirrors the way the proposed extension allows for guard expressions to
contain pattern matching.

Which approach lends itself to the most 'natural' way of expression a
pattern condition differs depending on the condition in question.

For instance, it doesn't get much simpler than:

    case ... of
      'yes' or 'true' or 'oui' or 'si' or 1 -> ...
      'no' or 'false' or 0 -> ...

      %% Equivalent condition using '~':
      %% X when X~'yes'; X~'true'; X~'oui'; X~'si'; X~1 -> ...
    end

However, writing guard expressions inside patterns tends to obscure
the structure described by the pattern.


### Allowing 'case' in guard expressions

This extension adds quite a bit of expressiveness to guards.  It does
solve the problems, and does so without adding any genuinely new
syntax or semantics.  It does not have much else going for it, though.

Case expressions which are nested in this way leads to rather
inconcise solutions, which are in most cases not a very direct way of
expressing the conditions.

Consider for instance the length and readability of:

    case ... of
      X when case X of
               {ok, _} -> false;
               _       -> true
             end -> ...
    ...

versus

    case ... of
      X when not X ~ {ok,_} -> ...
    ...

### Allowing '=' in guard expressions

Using '=' appears to be a more natural choice than 'case'; the idea
being that it'd basically be like the proposed '~'-operator, except
working through guards failing with 'badmatch' instead of evaluating
to 'false'.

There are problems with this, though; in particular, '='-expressions
do only in rare occasions evaluate to 'true', and any non-true result
would cause the guard to fail - if, of course, '=' was used in a
top-level guard expression and no other changes to the semantics are
made.

Observe:

    case ... of
    X when {ok,_}=X -> ... % bad - never evaluates to 'true'
    %% Fix 1 - inelegant:
    X when ({ok,_}=X) /= dummy -> ...
    %% Fix 2 - supposing that begin...end is allowed:
    X when begin {ok,_}=X, true end -> ...
    %% Fix 3 - suppose that '=' at otplevel evaluates to a boolean:
    X when {ok,_}=X -> ...

Reusing existing syntax in this way opens new questions regarding
which semantics are desired, and any perceived advantage to doing so
would thus be subverted by the inability of reusing existing semantics
as well - at least not without paying a prie of either flexibility or
brevity.

In contrast, the proposed semantics for '~' are clear, easy to
understand, and it is clear how to use the operator.

### Adding a guard BIF `matches_spec/2`

Introducing the ability to perform matchspec testing in guards would
solve most of the described problems, in a simple albeit not very
syntactically convenient or indeed expected way (and performance would
presumably not be on par with that of the other described solutions,
either).

The most interesting thing about this approach is probably that it
allows for dynamic patterns — run-time selection (or, indeed,
composition) of patterns.  This would, for instance, enable dynamic
selective receive as described [in this blog post][DynSelRecv].


### First-class pattern conditions/abstract patterns

First-class pattern conditions have already been suggested in [EEP
29][] in the form of "abstract patterns".  However, the implementation
part of that EEP notes that allowing patterns in guards is a
prerequisite for implementation.  Therefore, the presently suggested,
relatively light-weight mechanism still has its place.



Backwards Compatibility
=======================

The change is fully backwards compatible in the sense that it will not
break any existing source code; the '~' operator is hitherto unused.


Related tools and features
--------------------------

Language processing tools may of course be affected.  Tools working on
Erlang Core or lower levels won't be affected.  In particular, nothing
changes on the BEAM file level.

The language addition will introduce a set of pattern guards which are
not translatable to match specs.
(Note that match specs are already behind in terms of expressiveness
when it comes to binaries.)
In the long term, this should perhaps be addressed.
In the short term, `ms_transform` should recognize these new cases and
fail appropriately.



Reference Implementation
========================

A reference implementation of the basic semantics is available at
[my otp repository at GitHub][RefImpl].

The binding semantics have not been implemented yet.



[GuardSeqInManual]:
    http://www.erlang.org/doc/reference_manual/expressions.html#id79432
    "Guard Sequences (Erlang reference manual)"
[WhatPDF]: http://www.daimi.au.dk/~eriksoe/what/What.pdf
    "What — A Domain-specific Language for Web Surfing"
[DynSelRecv]:
    http://polymorphictypist.blogspot.com/2011/10/dynamic-selective-receive-erlang-hack.html
    "Dynamic Selective Receive — an Erlang hack"
[RefImpl]: https://github.com/eriksoe/otp/tree/eep_-pattern-test-operator
    "Reference implementation"
[EEP 29]: eep-0029.md
    "EEP 29, Abstract Patterns, Stage 1, O'Keefe"



Copyright
=========

This document has been placed in the public domain.



[EmacsVar]: <> "Local Variables:"
[EmacsVar]: <> "mode: indented-text"
[EmacsVar]: <> "indent-tabs-mode: nil"
[EmacsVar]: <> "sentence-end-double-space: t"
[EmacsVar]: <> "fill-column: 70"
[EmacsVar]: <> "coding: utf-8"
[EmacsVar]: <> "End:"
