Mach7: Pattern Matching for C++

by Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup

Abstract

Pattern matching is an abstraction mechanism that can greatly simplify source code. Commonly, pattern matching is built into a language to provide better syntax, faster code, correctness guarantees and improved diagnostics. Mach7 is a library solution to pattern matching in C++ that maintains many of these features. All the patterns in Mach7 are user-definable, can be stored in variables, passed among functions, and allow the use of open class hierarchies.

Mach7 by Example

Fibonacci numbers demonstrates the use of patterns with built-in types in Mach7:

// Fibonacci numbers
int fib(int n)
{
    var<int> m;

    Match(n)
    {
      Case(1)     return 1;
      Case(2)     return 1;
      Case(2*m)   return sqr(fib(m+1)) - sqr(fib(m-1));
      Case(2*m+1) return sqr(fib(m+1)) + sqr(fib(m));
    }
    EndMatch
}

Lambda calculator demonstrates use of pattern matching to decompose objects and nested patterns:

// Declare C++ equivalent of an Algebraic Data Type Term and its 3 variants:
struct Term       { virtual ~Term() {}     };
struct Var : Term { std::string name;      };
struct Abs : Term { Var&  var;  Term& body;};
struct App : Term { Term& func; Term& arg; };

// Tell Mach7 library which members should be bound in which binding positions
namespace mch
{
    template <> struct bindings<Var> { Members(Var::name); };
    template <> struct bindings<Abs> { Members(Abs::var , Abs::body); };
    template <> struct bindings<App> { Members(App::func, App::arg);  };
}

// Implement fully-functional lambda-calculator
Term* eval(Term* t)
{
    var<const Var&> v;
    var<const Term&> b,a;

    Match(*t)
    {
      Case(C<Var>())               return &match0;
      Case(C<Abs>())               return &match0;
      Case(C<App>(C<Abs>(v,b),a))  return eval(subs(b,v,a));
      Otherwise() cerr << "error"; return nullptr ;
    }
    EndMatch
}

It can also be used to demonstrate relational matching on several arguments:

bool operator==(const Term& left, const Term& right)
{
    var<std::string> s;
    var<const Term&> v,t,f;

    Match(left,right)
    {
      Case(C<Var>(s),     C<Var>(+s)     ) return true;
      Case(C<Abs>(&v,&t), C<Abs>(&+v,&+t)) return true;
      Case(C<App>(&f,&t), C<App>(&+f,&+t)) return true;
      Otherwise()                          return false;
    }
    EndMatch

    return false; // To prevent all control path warning
}

Next example demonstrates that the library can deal efficiently and in a type-safe manner with non-polymorphic classes like boost::variant as well.

void print(const boost::variant<double,float,int>& v)
{
    var<double> d; var<float> f; var<int> n;

    Match(v)
    {
      Case(C<double>(d)) cout << "double " << d << endl; break;
      Case(C<float> (f)) cout << "float  " << f << endl; break;
      Case(C<int>   (n)) cout << "int    " << n << endl; break;
    }
    EndMatch
}

Breve syntax is not the only thing Mach7 has to offer - the generated code is faster than Visitors!

For a more detailed set of examples, have a look at the code that was prepared for CppCon 2014 presentation, and implemented using visitors as well as pattern matching. These are simple enough to help you get started on your own Mach7 project.

Continuous Integration

We use Travis CI and AppVeyor for continuous integration and currently have all check-ins validated in the following configurations:

| | G++ | Clang | |-------|-----|-------| | Linux | 4.9 | 3.4 | | OSX | 4.9 | 3.5 |

| | 2019 | 2017 | 2015 | 2013 | 2012 | 2010 | /analyze | |-------|------|------|------|------|------|------|------| | x86 | Fail | OK | OK | OK | OK | OK | OK | | x64 | Fail | OK | OK | OK | OK | N/A | OK |

Branches

master - main development branch
release - cleaned-up branch with non-essential files deleted. FI from but does not RI back to master to avoid deletion of files there. Don't do any actual editing in this branch.

Building sources

If you haven't done so yet, get a copy of this Git repo locally by executing:

git clone https://github.com/solodon4/Mach7.git

The library itself is header only and does not require building. To build unit and timing tests we've accumulated over time several scripts, which we don't completely abandon in favor of newer ones as they maintain the flags the original experiments on the library were built with.

Using CMake (3.2 or later)

CMake support is the most recent and is still very experimental at this point. To build with cmake, perform the following commands from within Mach7 folder:

cmake -H. -Bbuild
cmake --build build --target install

Note: this requires administrative privileges under all systems, if you don't like this, try commands below:

cmake -H. -Bbuild -DCMAKE_INSTALL_PREFIX=/wherever/doesn't/require/administrative/priviege
cmake --build build --target install

But please make sure msvc/clang/gcc is able to find the path your provide above when including Mach7's headers in your own project:

MSVC: https://stackoverflow.com/questions/335408/where-does-visual-studio-look-for-c-header-files
Gcc/Clang: -I
CMake: https://stackoverflow.com/questions/13703647/how-to-properly-add-include-directories-with-cmake

Using Makefiles for GCC (4.4 or later) or Clang (3.3 or later)

Top-level Makefile synopsis:

make         - build all library tests
make all     - same as above right now
make unit    - build all unit tests
make time    - build all timing tests
make cmpl    - build all tests for timing the compilation times of the library
make clean   - clean all built targets and intermediaries
make test    - run all the built tests
make check   - run those tests for which there are correct_output/*.out files and check that the output is the same
make doc     - build Mach7 documentation (requires doxygen)
make includes.png - build graph representation of header inclusions (requires graphviz dot)

To see a list of more specific targets supported by other makefiles, see comments inside them.

To build a particular file, say test/unit/example05.cpp, build a target with the same filename and extension .exe instead of .cpp (even on Unix family OS). For example:

cd $MACH7_ROOT/code/test/unit
make example05.exe

Lower-level makefiles support most of the phony targets of the top-level makefile, to which the top-level makefile forwards the corresponding calls. For example:

To build and run just the unit tests:

cd $MACH7_ROOT/code/test/unit
make
make check
make test

Similarly, to build and run all the timing tests:

cd $MACH7_ROOT/code/test/time
make
make test

Using Visual C++ (2010 or later)

Mach7 uses its own build.bat script to build all the examples and unit tests that come with it. The script assumes each .cpp file to be a standalone program. You can find the most up-to-date list of supported commands by running:

build.bat /?

Syntax:

build [ pgo | repro | tmp | <ver> ] [ filemask*.cpp ... ]
build [ syntax | timing | cmp | doc | clean | test | check ]

Commands supported so far:

build [ pgo | repro | tmp | <ver> | <arch> ] [ filemask*.cpp ... ] - build given C++ files
build        - Build all examples using the most recent MS Visual C++ compiler installed
build unit   - Build all unit tests
build syntax - Build all supported library options combination for sy

Mach7

Install / Use

README