Mach7: Pattern Matching for C++

by Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup

License Agreement (BSD)

Mach7: Pattern Matching Library for C++

Copyright 2011-2013, Texas A&M University.
Copyright 2014 Yuriy Solodkyy.
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.

    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in the
      documentation and/or other materials provided with the distribution.

    * Neither the names of Mach7 project nor the names of its contributors
      may be used to endorse or promote products derived from this software
      without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

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:

// Lambda calculator
struct Term       { virtual ~Term() {}     };
struct Var : Term { std::string name;      };
struct Abs : Term { Var&  var;  Term& body;};
struct App : Term { Term& func; Term& arg; };

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.

Building sources

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

make         - builds .exe files from all the .cpp files in current directory.
make timings - builds all combinations of encodings, syntax and benchmarks 
               out of skeleton.cxx for timing purposes
make syntax  - builds all combinations of configuration flags supported by the 
               library to make sure nothing was omitted
make test    - runs all the .exe files in the current folder

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 | tmp | (ver) ] [ filemask*.cpp ... ]
build [ syntax | timing | cmp | doc | clean | test | check ]

Commands supported so far:

build [ pgo | tmp | (ver) ] [ filemask*.cpp ... ] - build given C++ files
build        - Build all examples using the most recent MS Visual C++ compiler installed
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
tmp   - Keep temporaries
(ver) - Use a specific version of Visual C++ to compiler the source code. (ver) can be one of the following:
      - 2010 - Visual C++ 10.0
      - 2012 - Visual C++ 11.0
      - 2013 - Visual C++ 12.0

The following batch files do some of these sub-commands directly and have since been integrated into build.bat:

 * test-pm-timing.bat - builds all combinations of encodings, syntax and benchmarks out of skeleton.cxx for timing purposes (same as "make timings" for Visual C++)
 * test-pgo.bat - compiles and performs profile-guided optimizations on all files passed as arguments
 * test-pm.bat - builds sources varying amount of derived classes and virtual functions in them
 * test-pm-daily.bat - builds all files in the test suite
 * test-pm-daily-pgo.bat - builds all files in the test suite and performs profile-guided optimizations on them
 * ttt.bat - converts the summary of outputs into a latex definitions used in the performance table

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. 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]

Support

Please contact Yuriy Solodkyy at [email protected] with any questions regarding Mach7.

Known bugs and limitations

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

The following files crash GCC 4.4.5 on my Fedora 13 box: extractor.cpp, shape2.cpp, shape4.cpp, shape5.cpp, shape6.cpp, shape.cpp, numbers.cpp, category.cpp, exp.cpp If they do on yours too, just delete them, they are all test cases anyways.

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