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 syntax variations
build timing - Build all supported library options combination for timing variations
build cmp    - Build all executables for comparison with other languages
build doc    - Build Mach7 documentation
build clean  - Clean all built examples
build test   - Run all built examples
build check  - Run those examples for which there are correct_output/*.out files and
               check that output is the same

Modifiers:

       pgo   - Perform Profile-Guided Optimization on produced executables
       repro - In case of error, create and compile a pre-processed repro
       tmp   - Keep temporaries
      <ver>  - Use a specific version of Visual Studio to compile the source
               code. <ver> can be one of the following:
                - 2019 - Visual C++ 16.0
                - 2017 - Visual C++ 15.0
                - 2015 - Visual C++ 14.0
                - 2013 - Visual C++ 12.0
                - 2012 - Visual C++ 11.0
                - 2010 - Visual C++ 10.0
                - 2008 - Visual C++  9.0
                - 2005 - Visual C++  8.0
                - 2003 - Visual C++  7.1
                  0000 - Do not use any VS to set up the environment, I will set it up by myself
      <arch> - Target architecture. Can be one of the following: x86, x64, arm

Talks

• "Accept No Visitors". CppCon 2014. September 12, 2014. Bellevue, WA. [slides, video]
• "Mach7: The Design and Evolution of a Pattern Matching Library for C++". C++ Now 2014. May 14, 2014. Aspen, CO. [slides, video]

Publications

• Y.Solodkyy, G.Dos Reis, B.Stroustrup. "Open Pattern Matching for C++: Extended Abstract" In Proceedings of the 2013 companion publication for conference on Systems, programming, & applications: software for humanity (SPLASH '13). ACM, New York, NY, USA, pp. 97-98. pdf, slides, notes, poster, project
• Y.Solodkyy, G.Dos Reis, B.Stroustrup. "Open Pattern Matching for C++" In Proceedings of the 12th international conference on Generative programming: concepts & experiences (GPCE '13). ACM, New York, NY, USA, pp. 33-42. pdf, slides, notes, poster, project
• Y.Solodkyy. "Simplifying the Analysis of C++ Programs" Ph.D. Thesis. Texas A&M University. August 2013. pdf, slides
• Y.Solodkyy, G.Dos Reis, B.Stroustrup. "Open and Efficient Type Switch for C++" In Proceedings of the ACM international conference on Object Oriented Programming Systems Languages and Applications (OOPSLA '12). ACM, New York, NY, USA, pp. 963-982. pdf, slides, notes, poster, extras, project]

Others about Mach7

• 2016-02-27: Andrzej's C++ blog: Another polymorphism

Projects using Mach7

• Yodl: a VHDL frontend for Yosys
• Arrow: Arrow is a fast (as or faster than C) general-purpose programming language. It does not employ a garbage collector and has minimal runtime overhead.

License

Mach7 is licensed under the BSD License.

Support

If you have any question about Mach7 or have trouble using it, the best way to get answers is to post an issue and label it as Question. This will contribute to our poor man's FAQ and hopefully help others with a similar question. I get notifications about new issues and usually respond within the same day. If you prefer not to discuss your question on GitHub, feel free to send me a private email (note there is a + in the email address).

Call for Help

We are looking for contributors to the project. If you are a student taking a programming languages class or any other class that would require you to write a small compiler or interpreter, we would love you try Mach7 for the job. We promise to help with any issues you might have with the library.

Known bugs and limitations

Right now, there are several experimental headers that one would need to include to enable one or the other syntax to work. This is a work in progress, so before you start working with a particular syntax, check examples with that syntax and make note of which of headers they include. We will clear this eventually leaving only one header, but at the moment it is a mess, and the most intuitive match.hpp is probably not the header you want as it represents older experiments. The most recent experimentation and the header you are probably looking for is mach7/type_switchN-patterns-xtl.hpp.

The library is not yet suitable for multi-threaded environment. Lock-free version of vtbl-map is in the works.

Please refrain from using solution or project files checked in here. They are not in sync with most recent changes to directory structure and are difficult to maintain. They will ultimately be replaced with a less verbose system (likely CMake), and in the meantime please use build.bat to build tests on Windows.

For the most up-to-date list of known issues see Mach7 Issues.