solodon4/mach7

Functional programming style pattern-matching library for C++

mach7's Issues

Broken links in readme

It seems that any link I click on, it turns out to really not work. I just go to the github 404 page, which leads me to believe that the resources are private to the repo editors, and not me (or the open public)

One good example is here:

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

the link embedded in that (https://github.com/solodon4/Mach7/blob/master/code/numbers.cpp#L202-L216) gives me the 404.

Match on boost::variant is much slower than visitor based solution in Release build

On Dec 12, 2014, at 15:23, Andrzej Krzemienski wrote:

Hi Yuriy,
I have made a simple benchmark of visiting boost::variant with Mach7 vs using boost::static_visitor. Here is the code of the benchmark (fairly short):
https://akrzemi1.wordpress.com/examples/mach7-benchmark/

I tested in GCC 4.8.2. (on Windows). For non-optimized version Mach7 is more-less 1.35 times faster. When compiled with -O2, boost::static_visitor is about 4.5 times faster. The results from a couple of runs (measured in clock ticks):

optimized:

mach7 visit
908 204
915 199
908 202
931 199
945 201
905 198

non-optimized:

mach7 visit
8304 11599
8575 11624
10144 11888
8394 12472
8252 11628
8591 11628

boost::static_visitor probably does something similar to Mach7: a switch on an integer.

Regards,
Andrzej

error C2440: 'return': cannot convert from 'const Circle *' to 'Circle *'

Present on several classes in Visual C++ 2012, 2013, 2015

Compile time error with if Members macro gets more than 10 arguments

Hi Yuriy,

I'm not sure whether this is a bug or a known limitation of C's macro system, although I can hardly believe the latter.

I tried to add all members of the huge class ScopeBase. My first attempt caused the compiler to emit about 140 lines of error messages, quickly resigning after 20 reported errors. I later realized that the compilation error depends on the number of arguments passed to Members. The file traverse_all.cc shows exactly what I mean. The current version of the file does not compile. However, if one comments out an arbitrary argument (for example ScopeBase::use_types_), the example builds again.

Here is the error message:

traverse_all.cc:69:9: error: use of undeclared identifier 'XTL_REPEAT_WITH_ScopeBase'
        Members(ScopeBase::old_signals_, //map<perm_string, Signal*>
        ^
mach7/patterns/bindings.hpp:169:87: note: expanded from macro 'Members'
    #define Members(...)                                                XTL...
                                                                                      ^
mach7/macros.hpp:121:29: note: expanded from macro 'XTL_REPEAT'
#define XTL_REPEAT(n,m,...) XTL_REPEAT_WITH(,n,m,__VA_ARGS__)
                            ^
mach7/macros.hpp:119:36: note: expanded from macro 'XTL_REPEAT_WITH'
#define XTL_REPEAT_WITH(s,n,m,...) XTL_REPEAT_WITH_ ## n(s,m,__VA_ARGS__)
                                   ^
<scratch space>:181:1: note: expanded from here
XTL_REPEAT_WITH_ScopeBase
^
traverse_all.cc:69:9: error: expected parameter declarator
mach7/patterns/bindings.hpp:169:87: note: expanded from macro 'Members'
    #define Members(...)                                                 XTL...
                                                                                      ^
mach7/macros.hpp:121:29: note: expanded from macro 'XTL_REPEAT'
#define XTL_REPEAT(n,m,...) XTL_REPEAT_WITH(,n,m,__VA_ARGS__)
                            ^
mach7/macros.hpp:119:59: note: expanded from macro 'XTL_REPEAT_WITH'
#define XTL_REPEAT_WITH(s,n,m,...) XTL_REPEAT_WITH_ ## n(s,m,__VA_ARGS__)
                                                          ^
traverse_all.cc:69:9: error: C++ requires a type specifier for all declarations
mach7/patterns/bindings.hpp:169:120: note: expanded from macro 'Members'
  ...XTL_REPEAT(XTL_NARG(__VA_ARGS__),CMa,__VA_ARGS__)
                                      ^
traverse_all.cc:69:28: error: no type named 'old_signals_' in 'ScopeBase'
        Members(ScopeBase::old_signals_, //map<perm_string, Signal*>
                ~~~~~~~~~~~^
mach7/patterns/bindings.hpp:169:124: note: expanded from macro 'Members'
  ...XTL_REPEAT(XTL_NARG(__VA_ARGS__),CMa,__VA_ARGS__)
                                          ^~~~~~~~~~~
mach7/macros.hpp:121:50: note: expanded from macro 'XTL_REPEAT'
#define XTL_REPEAT(n,m,...) XTL_REPEAT_WITH(,n,m,__VA_ARGS__)
                                                 ^~~~~~~~~~~
mach7/macros.hpp:119:62: note: expanded from macro 'XTL_REPEAT_WITH'
#define XTL_REPEAT_WITH(s,n,m,...) XTL_REPEAT_WITH_ ## n(s,m,__VA_ARGS__)

Best regards

Bugs when building with VS 2013 and VS 2015

There are several source issues that have to be fixed due to changes in the standard library and supported features in Visual Studio 2013 and 2015

Linker errors when building unit tests

This occurs with both CMake and the Bakefile system I'm working on:

[6/172] Linking CXX executable unit/example01
FAILED: : && /home/ryan/stuff/Downloads/clang+llvm-3.6.0-x86_64-linux-gnu/bin/clang++   -fcolor-diagnostics   unit/CMakeFiles/example01.dir/example01.cpp.o  -o unit/example01  -rdynamic && :
unit/CMakeFiles/example01.dir/example01.cpp.o: In function `mch::vtblmap<mch::type_switch_info>::get(void const*)':
../unit/example01.cpp:(.text._ZN3mch7vtblmapINS_16type_switch_infoEE3getEPKv[_ZN3mch7vtblmapINS_16type_switch_infoEE3getEPKv]+0xd3): undefined reference to `mch::vtblmap<mch::type_switch_info>::update(long)'
clang: error: linker command failed with exit code 1 (use -v to see invocation)

This happens when linking pretty much any of the tests.

[question] Clarify how users should define XTL sub-type relation for their types

adapt_boost_variant.hpp is a good start, but it isn't enough to understand the concept.

E.g., what is subtype_cast_impl for? How Am I supposed to say that a reference to super-type should be cast to a reference to a sub-type?

[Segfault] when binding `var<vector<type *>>` to class member of the same type

Env: clang++ with clang++ --version:

clang version 3.8.0 (tags/RELEASE_380/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/sbin

Description

This code produces the error

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff6121d54 in __memmove_ssse3_back () from /usr/lib/libc.so.6

at this line. As you can see params is an instance of the var template which I'm trying to fill with a copy of the member argv_ of the ExpFunc object. The type of argv is vector<Expression*> and argv_ is stored as non-pointer, non-reference in ExpFunc. params was instanciated as follows:

var<vector<Expresson *>> params;

You can find the whole test here. I deleted most of the other unit tests and the respective include files in order to make sure that the error arises from a use of Mach7.

Add Visual C++ equivalent of RDTSC code

Windows headers are incompatible with /Za flag, which disables language extensions. Windows header right now seems to only be used for timing purposes, so we can include it conditionally when extensions are enabled only. Enabling them though makes us rely on the worst timer available.

Write equivalent of RDTSC access code we now have for GCC in Microsoft assembly.

Using __builting_assume with Clang makes linker fail to resolve mch::vtblmap<mch::type_switch_info>::update(long)

This is not a Mach7 bug per se, likely an Apple one, but this tracks the fact that the use of __builtin_assume is currently commented out for clang. This started happening after installing Xcode 7.0.1 but I seem to have the same issue now while trying this on Ubuntu (see build log)

The reduced repro is:

typedef long intptr_t;
namespace mch {

template <typename T> class vtblmap
{
    struct A
    {
        bool is_full() ;
    };
public:
    T& update(intptr_t );
    intptr_t get_vtbl;
    void  get( )
    {
        update(get_vtbl);
    }
    A* descriptor;
};

template <typename T> T& vtblmap<T>::update(intptr_t vtbl)
{
    __builtin_assume(descriptor->is_full())     ; // Comment this out for the linker error to disappear
}

struct type_switch_info ;
class B {
    public:
    static long choose(  )
    {
        vtblmap<type_switch_info> a;
        a.get();
    }
};
}

template<    class S, class T> void  lift_ex2(int , S , T )
{
    mch::B::choose;
}

int b,  c   ;
void  my_g( )
{
    lift_ex2(c,b,my_g);
}

unit test exp.cpp triggers an UB

Unit test exp.cpp has an undefined behavior and triggers a crash when I run tests.

In line 375 an object of type Mod is created and then passed to function myeval. Function myeval does not have a case for type Mod so it exits w/o any return statement.

I cannot fix it as I do not know what this unit test is intended to illustrate.

Replace all uses of patterns/all.hpp with the exact set of headers used

This should help search for all the examples that deal with a specific pattern or combinator as combinators specifically are not searchable: +, &, *, &&, || etc. would render to too many false-positive hits.

Problem with std::unique_ptr

example04-smart-ptr.cpp demonstrates how one can match on unique_ptr values. The example, however only describes the usage of adapter aided matching using the reference operator. Below that, there is another example showing an alternate matching technique:

//...
// previous example
#else
int evl(const Expr& e)
{
    var<ExprPtr> e1, e2;
    var<int> n;

    Match(e)
    {
        Case(C<Value> (n)    ) return n;
        Case(C<Plus>  (e1,e2)) return evl(*e1) + evl(*e2);
        Case(C<Minus> (e1,e2)) return evl(*e1) - evl(*e2);
        Case(C<Times> (e1,e2)) return evl(*e1) * evl(*e2);
        Case(C<Divide>(e1,e2)) return evl(*e1) / evl(*e2);
    }
    EndMatch

    XTL_UNREACHABLE; // To avoid warning that control may reach end of a non-void function
}
#endif

The code snippet pasted above does not compile. However, that's exactly what I need, as I cannot use references in my current context.

Is there any way to get the desired behaviour to work?

type_switchN-patterns-xtl.hpp does not work with polymorphic types

The following program does not compile, although it would compile if I replaced type_switchN-patterns-xtl.hpp with type_switchN-patterns.hpp.

#include <memory>
//#include <mach7/type_switchN-patterns.hpp>  // this works
#include <mach7/type_switchN-patterns-xtl.hpp> // this does not work
#include <xtl/adapters/std/memory.hpp>
#include <mach7/patterns/constructor.hpp>
#include <mach7/patterns/address.hpp>
#include <cassert>

namespace s1
{
  struct Expr { virtual ~Expr() {} };
  using ExprPtr = std::unique_ptr<const Expr>;

  struct Value : Expr { double value; explicit Value(double v) : value(v) {} };
  struct Var : Expr { bool is_x; explicit Var(bool x) : is_x(x) {} };

  struct Plus : Expr
  {
    ExprPtr expr1; ExprPtr expr2;
    explicit Plus(ExprPtr e1, ExprPtr e2) : expr1(std::move(e1)), expr2(std::move(e2)) {}
  };

  struct Times : Expr
  {
    ExprPtr expr1; ExprPtr expr2;
    explicit Times(ExprPtr e1, ExprPtr e2) : expr1(std::move(e1)), expr2(std::move(e2)) {}
  };

  typedef ExprPtr tree_type;
  double eval(tree_type const&, double x, double y);
}


namespace mch ///< Mach7 library namespace
{
  template <> struct bindings<s1::Value> { Members(s1::Value::value); };
  template <> struct bindings<s1::Var> { Members(s1::Var::is_x); };
  template <> struct bindings<s1::Plus> { Members(s1::Plus::expr1, s1::Plus::expr2); };
  template <> struct bindings<s1::Times> { Members(s1::Times::expr1, s1::Times::expr2); };
} // of namespace mch

namespace s1
{
  double eval_(Expr const& t, double x, double y)
  {
    mch::var<Expr const&> expr1, expr2;
    mch::var<bool> is_x;
    mch::var<double> value;

    Match(t)
    {
      Case(mch::C<Times>(&expr1, &expr2))
        return eval_(expr1, x, y) * eval_(expr2, x, y);
      Case(mch::C<Plus>(&expr1, &expr2))
        return eval_(expr1, x, y) + eval_(expr2, x, y);
      Case(mch::C<Var>(is_x))
        return is_x ? x : y;
      Case(mch::C<Value>(value))
        return value;
      Otherwise()
        return assert(false), 0.0;
    }
    EndMatch
  }

  double eval(tree_type const& t, double x, double y)
  {
    return eval_(*t, x, y);
  }
}

int main() {}

Split match.hpp

Split match.hpp into headers per ADT encoding. Users would be able to include specific one for his project as well as compare them in diff tools.

Deconstructing a variant containing a struct is broken

The following code fails on my debian unstable with clang 3.8 and boost 1.58:

#include <iostream>
#include <boost/variant.hpp>
#include <mach7/type_switchN-patterns.hpp> // Support for N-ary Match statement on patterns
#include <mach7/patterns/address.hpp>      // Address and dereference combinators
#include <mach7/patterns/bindings.hpp>     // Mach7 support for bindings on arbitrary UDT
#include <mach7/patterns/constructor.hpp>  // Support for constructor patterns
#include <mach7/patterns/equivalence.hpp>  // Equivalence combinator +
#include <mach7/patterns/primitive.hpp> // Wildcard, variable and value patterns

struct S1
{
  unsigned t1;
  unsigned t2;
};

namespace mch
{
  template <> struct bindings<S1> { Members(S1::t1, S1::t2); };
}

using VV = boost::variant<S1>;

int main(int argc, char *argv[])
{
  using namespace mch;
  VV v = S1{10, 20};
  var<unsigned> t1;
  var<unsigned> t2;
  Match(v)
  {
    Case(C<S1>(t1, t2))
      std::cout << t1 << ':' << t2 << std::endl;
      assert(t1 == 10);
      assert(t2 == 20);
      break;
  } EndMatch
  return 0;
}

The struct is initialized with 10:20, but the std::cout prints 0:10 for me.

Mach7 with variant: cannot access the matched sub-object

I am using the library to switch on boost::variant and inspect/modify a given sub-type, as per the example below.

This doesn't work, because (to my knowedge) there is no way to get access to a mutable A from an instance of var<A&>.

Would it be possible to extend the interface of mch::var to get mutating access to its contained value?

#include <boost/variant.hpp>
#include <Mach7/code/type_switchN-patterns-xtl.hpp>
#include <Mach7/code/adapters/boost/adapt_boost_variant.hpp>
#include <Mach7/code/patterns/constructor.hpp>
#include <Mach7/code/patterns/primitive.hpp>

struct A
{
    int ma;
};
using V = boost::variant<A>;

void mutate_member(V& v)
{
    mch::var<A&> a;

    Match (v)
    {
        Case(mch::C<A>(a))
             a.ma = 2; // ERROR: cannot mutate a subobject of A
    }
    EndMatch
}

int main() {}

Need clarification on how to mutate Boost.Variants

Although I try hard, I cannot figure out how I can use Mach7 to switch on a mutable variant in order to mutate its contents. The following is how I solve my problem in a 'traditional' way:

struct M{ char im = 0; };
struct N{ char in = 0; };
typedef boost::variant<M, N> VM;

void visit(VM& vm)
{
  if(M* m = boost::get<M>(&vm))
    m->im = 'm';
  else if (N* n = boost::get<N>(&vm))
    n->in = 'n';
}

How am I suppose to do the same with Mach7?
I was only able to come up with this:

void visit7(VM& vm)
{
  mch::var<M&> m;
  mch::var<N&> n;

  Match(vm)
  {
    Case(mch::C<M>(m))
    {
      M* mp = m.m_value;
      mp->im = 'm';
    }
    Case(mch::C<N>(n))
    {
      N* np = n.m_value;
      np->in = 'n';
    }
  }
  EndMatch
}

But I suppose there must be a better way. Can you show me how it is intended to be used?

Move to CMake

Maintaining Visual C++, XCode etc. projects has became too cumbersome. Move to CMake

[maybe bug] Nested matching always chooses first case

given the following class hierarchy

struct Expression {};

struct ExpBinary : Expression {
    Expression *left, *right;

    ExpBinary(Expression *o1, Expression *o2)
        : left(o1)
        , right(o2) {}
};

struct ExpArith : ExpBinary {
    enum function { 
        SUB, ADD, MUL, DIV 
    };

    function arithOp;

    ExpArith(function f, Expression *l, Expression *r)
        : ExpBinary(l, r)
        , arithOp(f) {}
};

struct ExpLogical : ExpBinary {
    enum function_log { 
        GT, LT, EQ 
    };

    function_log logicalOp;

    ExpLogical(function_log f, Expression *l, Expression *r)
        : ExpBinary(l, r)
        , logicalOp(f) {}
};

struct ExpInteger : Expression {
    int value;
    ExpInteger(int v) : value(v) {}
};

The following evaluator somehow does not work:

int evaluate(const Expression& exp){
    var<Expression&> left, right;
    var<ExpLogical::function_log> lOp;
    var<ExpArith::function> aOp;
    int val;

    Match(exp){
        Case(C<ExpBinary>(&left, &right)) {
            Match(exp) {
                // cout << typeid(exp).name() << endl;
                Case(C<ExpArith>(aOp)) {
                    //cout << "exparith!\n";
                    Match(aOp) {
                        Case(ExpArith::ADD) {
                            return evaluate(left) + evaluate(right);
                        }
                        Case(ExpArith::SUB) {
                            return evaluate(left) - evaluate(right);
                        }
                        Case(ExpArith::MUL) {
                            return evaluate(left) * evaluate(right);
                        }
                        Case(ExpArith::DIV) {
                            return evaluate(left) / evaluate(right);
                        }
                        Otherwise() {
                            return 0;
                        }
                    } EndMatch
                }
                Case(C<ExpLogical>(lOp)) {
                    cout << "explogical!\n"; //never reached, but it should
                    Match(lOp) {
                        Case(ExpLogical::GT) {
                            return evaluate(left) > evaluate(right);
                        }
                        Case(ExpLogical::LT) {
                            return evaluate(left) < evaluate(right);
                        }
                        Case(ExpLogical::EQ) {
                            return evaluate(left) == evaluate(right);
                        }
                        Otherwise() {
                            return 0;
                        }
                    } EndMatch
                }
                Otherwise() {
                    cout << "Error in exp arith/logical matching!\n";
                    return 0;
                }
            } EndMatch
        }
        Case(C<ExpInteger>(val)) {
            return val;
        }
        Otherwise() {
            cout << "Error in evaluate!\n";
            return 0;
        }
    } EndMatch
}

If I build the expression

Expression *log =
        new ExpLogical(ExpLogical::GT,
                       new ExpInteger(3),
                       new ExpInteger(4));

and try to evaluate it using the statement,

cout << evaluate(*log) << endl;

the program outputs -1 which is wrong. Somehow the statement Case(C<ExpLogical>(lOp)) is not reached, instead the second Match(exp) chooses Case(C<ExpArith>(aOp)). I don't understand why, since the patterns against which the subjecting values are being matched are clearly different. Do you have any idea? Is it disallowed to nest Match statements?

I also provided the whole (compilable) example as a gist.

Best regards

Add Members macro

We refer in documentation to variadic macro Members, while we still use CM etc. in the actual source files. Implement Members and change definitions to use it

programmer-friendly header files arrangement

PROBLEM DESCRIPTION:

Currently the library header files are located in folder $MACH7_ROOT/code/, e.g., $MACH7_ROOT/code/patterns/constructor.hpp. This makes it somewhat inconvenient for the library users: what path should they add to systems include directory?

$MACH7_ROOT? In that case the programmers has to include headers like this:

#include <code/patterns/constructor.hpp>

$MACH7_ROOT/code? In that case the programmers has to include headers like this:

#include <patterns/constructor.hpp>

In either case from the #include it is not clear what library we are using.

I can add to system includes the folder that contains $MACH7_ROOT and therewith have the programmers include headers like this:

#include <Mach7/code/patterns/constructor.hpp>

But now the final path will vary among the users: it depends on how I name the cloned repository.

PROPOSAL:

Move all the library header files to folder $MACH7_ROOT/code/include/mach7 and add a recommendation that users should add $MACH7_ROOT/code/include to their system includes path.

Directory structure

Separate:

• Patterns
• Unit tests

[Question] Reader/Writer Locks

I am working on a concurrent implementation of your C++ Pattern Matching Library. Currently I am working with the vtblmap3st file using reader/writer locks to see if this out performs a single lock. I have a question whether or not locking/unlocking the shared and non-shared locks where the reference to the pointer ce is returned is safe, or this could corrupt the data in the cache.

Compile time performance

A very subjective question but:

Some templates take a long time to compile. Does this library introduce a great toll on compile times when used regularly? e.g. Is it possible to create exponential or quadratic compile times for simple patterns?

Don't know how to label this though. Sorry about that.

problems building unit tests with make

I can't build and execute unit tests on Red Hat Linux using make.

Top-level Makefile contains like:

# Create a list of source files.
SOURCES  = $(shell ls *.cpp)

But ls *.cpp is not a valid bash command, and I get an error. You probably meant either find -name *.cpp or find -maxdepth 1 -name *.cpp, but I do not know which one.

If I fix this, and then run make test, I get a bash error:

basename: extra operand `comp.clang.hpp'
Try `basename --help' for more information.
======================================== [ *.exe ]
/bin/sh: line 17: ./*.exe: No such file or directory

Weed out deprecated headers

Question from email:

Is that possible the Constructor pattern is used without C(P) ?
when I read the paper in Open Pattern Matching For C++, it says Constructor pattern should be used with C(p), for recognize it's class type. but, when I see the example01 file, It just match its type as Case(Circle) - not Case(C(center, radiuse) - is that syntax changed ?
or, the two usage is distinct its' functionality ? like ... for specifying which constructor / and it's member binding, use the Constructor Pattern, and When Just specify its' type, is using Case(ClassType) ?

Incomplete Answer:

Yes, we’ve been experimenting with different syntaxes in the project and currently the library can support several of them. Not at the same time unfortunately, but as close as we could get to this. Search for uses of macro XTL_DEFAULT_SYNTAX as it controls which of the syntaxes and encodings the library should use. The older match.hpp header would default to Case clauses with syntax you see in example01.cpp. The newer syntax towards which we lean is enabled by including header type_switchN-patterns.hpp. It is derived from the older match.hpp, however it moves experimentation further in the direction of relational matching (multiple arguments) and patterns. You can still use patterns syntax in the old header, but you’d have to use Qua clauses instead of Case clauses. Header type_switchN-patterns-xtl.hpp is even further generalization of the type_switchN-patterns.hpp that allows support for non-polymorphic (in C++ terminology) classes like boost::variant. That’s the most recent version of the header, which I’ll be moving forward. Other headers would be either eliminated if they are superseded by this one, or kept (like match.hpp), when they provide functionality not superseded by this latter one. We do strongly recommend the syntax from the paper via use of this last header as it provides the most flexibility in design overall.

Action:

Eliminate all experimental match*.hpp headers and leave only the older match.hpp and then latest type_switchN-patterns-xtl.hpp with a sexier name. These 2 will have differences in functionality, and preference should be given to the latter newer one. All other experimental derivations should be cleaned out.

Constructor pattern limited to at most 4 arguments?

If I call the function Template C as follows

Match(foo){
    Case(C<SomeType>(arg0, arg1, arg2, arg3)){
        /* ... */
    }
    Otherwise(){/*...*/}
} EndMatch

everything works as expected. However, if I write,

Match(foo){
    Case(C<SomeType>(arg0, arg1, arg2, arg3, arg4)){
        /* ... */
    }
    Otherwise(){/*...*/}
} EndMatch

the compiler complains about no matching function for call to 'C'.
I already looked at constructor.hpp and the implementations of the class templates constr{0,1,2,3,4}. I assume those to be the underlying base of C which almost certainly itself is a macro (is that right?), which would explain the limitation to 4 arguments of the call operator. But then I looked more closely and realized that only the number of template arguments changes. The call operator overloads (more or less) stay the same throughout the different versions of constr.

    template <typename U> const T* operator()(const U* u) const noexcept { return dynamic_cast<const T*>(u); }
    template <typename U>       T* operator()(      U* u) const noexcept { return dynamic_cast<      T*>(u); }
    template <typename U> const T* operator()(const U& u) const noexcept { return operator()(&u); }
    template <typename U>       T* operator()(      U& u) const noexcept { return operator()(&u); }
                          const T* operator()(const T* t) const noexcept { return t; }
                                T* operator()(      T* t) const noexcept { return t; }
                          const T* operator()(const T& t) const noexcept { return &t; }
                                T* operator()(      T& t) const noexcept { return &t; }

Why is that? I'm probably missing something obvious here...
Could you elaborate the expansion of C a little further. Somehow I can't find the macro definition. I also tried to compile with gcc -E in order to view the expansions, without much success (however, the output did hurt my eyes).

Best regards
Florian

XTL_FALL_THROUGH

I had to rollback XTL_FALL_THROUGH to 1 again because old Qua clauses seem to be putting break statements in the wrong place. See extractor.cpp for repro.

The value has to be 0 by default and macro probably deprecated (unless we want All Fit semantics too) because several novices made a mistake of not putting break at the end of the case clause effectively making the Match statement super slow because the code was needlessly checking all the predicates after the matching clause.

Early exits

Trace applicable case labels to leave switch early when no more applicable case clauses exist

Matching against STL containers and ranges

C++ containers are harder to decompose because they are not recursive data structures (not expressed in their own terms, not containing an instance of themselves like lists and trees in functional programming would). This was the subject of slides 66 and 67 of my C++ Now talk: http://bit.ly/Mach7CppNow

To explain the slides there: a recursive list is easy to decompose with nested matching, e.g.:

Case(C(head, C(nexthead, tail))) ...

However std::list is not recursive, so it is not applicable to it.

Ranges are also not recursive, but at least they conceptually can reflect part of themselves, so I think we should be able to build patterns for matching against ranges. I started working on such a pattern (I called it sequence pattern: https://github.com/solodon4/Mach7/blob/master/code/patterns/sequence.hpp), however there was something else I still had to resolve on the level of idea, so I don't think I have yet an example of their usage. The idea was to let that pattern match against arbitrary number of elements and then accept as the last pattern something that would be capable of matching against the range of remaining (not yet matched elements). As such I added 'all' and 'exist' patterns, whose example usage can be found on lines 406 and 408 here:

https://github.com/solodon4/Mach7/blob/master/code/prolog-pat2.cpp#L406

In other words, it is very easy to create pattern that would match against first n elements of a container with its n sub-patterns. It is not clear what to do with the remaining elements after n as we would ideally want to forward the computation to them after decomposition through pattern matching (fold).

Besides the sequence pattern, I was also trying to experiment with syntaxes for other patterns capable of matching multiple elements, as for example, on commented-out lines 460 and 461 in the same file, but that didn't quite work, so I don't have a good solved story for STL containers yet.

Cannot switch on poly and variant in same file

It seams it is currently impossible to declare two type-switch statements in one file, where one is "traditional" (vtable-based) and the other is xtl-based. I need to include two headers:
type_switchN-patterns.hpp and type_switchN-patterns-xtl.hpp which contain conflicting definitions.

(For the same reason, I guess I would be unable to do a switch on two arguments, where one argument is a polymorphic type, and the other is boost::variant.)

I realize, there are plans for unification. But for the time being, would it be possible to provide a way for the two headers to coexist? Define symbols in different namespaces, #undef the macros?

Sometimes binding to var<T const&> does not work

The following is the code taken from the intro page; and it works:

#include <mach7/type_switchN-patterns-xtl.hpp>
#include <mach7/adapters/boost/adapt_boost_variant.hpp>
#include <mach7/patterns/constructor.hpp>                // for mch::C
#include <mach7/patterns/primitive.hpp>                  // for mch::var
#include <iostream>

using namespace mch;
using namespace std;

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
}

int main() {}

But if I change var-s to represent references:

#include <mach7/type_switchN-patterns-xtl.hpp>
#include <mach7/adapters/boost/adapt_boost_variant.hpp>
#include <mach7/patterns/constructor.hpp>                // for mch::C
#include <mach7/patterns/primitive.hpp>                  // for mch::var
#include <iostream>

using namespace mch;
using namespace std;

void print(const boost::variant<double, float, int>& v)
{
  var<double const&> d; var<float const&> f; var<int const&> 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
}

int main() {}

The program no longer compiles. I am convinced from the other examples I was shown, that it is the library's intention to handle such match. Am I correct? If so, we have got a bug here.

[Proposal] Trimmed down version of mach7 for educational purposes

I'm quite new to C++ and it's templating system. Mach7 is another intriguing evidence for the power of template metaprogramming. Currently I'm using Mach7 based on idioms that I learned using the examples included in this repository. I rather dislike the fact that I don't solidly understand the inner workings of the library. Your paper Open Pattern Matching in C++ helps a bit with regards to this problem, because after reading it, I got a slight intuition for how the library implements certain things, however I want to really understand what's going on and that's not easy if the code base contains hard core MSVC Stack overflow workarounds :)

My Proposal: A trimmed down version of mach7 containing nothing but the utter essence of the library to illustrate the concepts used. Also macros and compiler/portability issues should strictly be avoided. That would, of course, mean to just address one compiler (either clang or gcc).

What do you think?

Best regards
Florian

No compile time complaint where there should be one

Hi Yuriy,

I played around with compile-lambda-a.cpp and added a new function whose
purpose is to replace every string in any lambda term with "foobar". This makes use of
a nested Match {...} EndMatch construct. The full version of this file is available at a gist that I uploaded.

The relevant parts are given here:

void change_vars(Term& t) {
    var<Var&>  v;
    var<Term&> t1, t2;
    var<std::string> s;

    Match(t)
    {
        Case(C<Var>(s)) { return; }
        Case(C<Abs>(&v,&t1)) {
            ((Var &) v).name = std::string("foobar");

            // "Match(t1) {" instead of the line below
            // produces a SIGSEGV. Why is that?
            Match((Term &) t1){
                Case(C<Var>(v)) {
                    ((Var &) v).name = std::string("foobar");
                    return;
                }
                Otherwise() { return; }
            } EndMatch

            change_vars(t1);
            return ;
        }
        Case(C<App>(&t1,&t2)) {
            change_vars(t1);
            change_vars(t2);
            return ;
        }
    }
    EndMatch

    return;
}

I know by now, that the instanciation of the var template produces structs with appropriately overloaded conversion operators. But in the context of the Match statement unambiguous type deduction should not be working and thus the compiler should produce an error when it encountered Match(t1){ (see comment in above code block). But that does not happen.

With Match(t1) instead of the correct Match((Term &) t1) the code compiles, but quickly produces a SIGSEGV. Why does it even compile?

Best regards
Florian

xtl adjustments

1. xtl_get is right now for 1 argument only
2. had to reset lowest bits to 0 by default - make this to be dependent on the type of key or something
3. generalize vtbl_of to be a function returning equivalence class
4. right now xtl implementation assumes sub objects after subtype_dynamic_cast are always at the same offset. Can this be parameterized? Also can some types benefit from direct jump and then do an analog of static_cast or something to adjust themselves?

support mail address not valid

Hello Yuriy,

I was trying to send you an email, but the
mail address in section support doesn't seem to
be valid. Could you check that?

Best regards
Florian

Replace memberN with generic equivalent

Right now bindings generate non-generic names member0, member1, ..., memberN. Replace them with generic equivalents that can be accessed with variadic templates etc.

What is progress of standatizing open pattern matching and/or open multimethods?

Hi,

I have just watched video of "Accept No Visitors" talk and was really impressed!

There was mentioned will to standardise these techniques, which would be really nice to have this language feature with low-level performance and yet high level abstractions!

Is there any progress with that? Was there a proposal submitted or drafted (not sure where to browse for these)? What are comments from other committee members?

Thanks!

adapt_boost_variant: how to say 'any sub-type of a variant'?

I am trying to do a type switch on two variants, as per the example below. My intention is to match the case where the left-hand object 'tank' has the sub-type TankC and the right-hand side object 'load' has any type. I managed to achieve the effect by listing two labels one immediately after the other, but I guess there must be a more direct way of expressing this?

#include <boost/variant.hpp>
#include <Mach7/code/type_switchN-patterns-xtl.hpp>
#include <Mach7/code/adapters/boost/adapt_boost_variant.hpp>
#include <Mach7/code/patterns/constructor.hpp>

struct TankA {};
struct TankB {};
struct TankC {};

struct Load1 {};
struct Load2 {};

typedef boost::variant<TankA, TankB, TankC> Tank;
typedef boost::variant<Load1, Load2> Load;

int interact(Tank const& tank, Load const& load)
{
  using mch::C;

  Match (tank, load)
  {
    Case (C<TankA>(), C<Load1>())
      return 61;
    Case (C<TankA>(), C<Load2>())
      return 62;
    Case (C<TankB>(), C<Load1>())
      return 71;
    Case (C<TankB>(), C<Load2>())
      return 72;
    Case (C<TankC>(), C<Load1>()) //
    Case (C<TankC>(), C<Load2>()) // I want these two cases to be one
      return 0;
    Otherwise()
      return -1;
  }
  EndMatch
}

int main()
{
  assert (interact(TankC(), Load2()) == 0);
}

Nested patterns and scalars

Is it possible to mix instances of var and nested patterns in the binding part of a constructor pattern? For example, is the following code allowed:

Case(C<ExpLogical>(
         C<ExpRelation>(
             C<ExpCharacter>(charVal),
             C<ExpName>(name),
             relOp),
         C<ExpAttribute>(attrName),
         logOp)){

where attrName, name, charVal, logOp and relOp are instances of the var template and Exp* have the layout:

namespace mch {
    template <> struct bindings<ExpUNot> {
        Members(ExpUNot::operand1_);
    };

    template <> struct bindings<ExpCharacter> {
        Members(ExpCharacter::value_);
    };

    template <> struct bindings<ExpAttribute> {
        Members(ExpAttribute::name_);
    };

    template <> struct bindings<ExpLogical> {
        Members(ExpLogical::operand1_,
                ExpLogical::operand2_,
                ExpLogical::fun_);
    };

    template <> struct bindings<ExpFunc> {
        Members(ExpFunc::name_,
                ExpFunc::argv_);
    };

    template <> struct bindings<ExpName> {
        //TODO: add prefix
        Members(//ExpName::prefix_, // unique_ptr<ExpName>
                ExpName::name_,
                ExpName::indices_);
    };

    template <> struct bindings<ExpRelation> {
        Members(ExpRelation::operand1_,
                ExpRelation::operand2_,
                ExpRelation::fun_);
    };
};

Here some Context. I need to search an Expression AST for a very specific pattern. Without the ExpRelation::fun_ and ExpLogical::fun_ bindings it worked quite well, but when I first began to experiment with the first code snippet instead of the simpler

Case(C<ExpLogical>(
         C<ExpRelation>(
             C<ExpCharacter>(charVal),
             C<ExpName>(name)),
         C<ExpAttribute>(attrName))){

no pattern seemed to match anymore.

Extract XTL_SUPPORT(feature) into separate project implementing WG21's N3694

WG21 has a proposal for feature test macros, which strives to unify what Mach7's XTL_SUPPORT(feature) macro and similar macros in other libraries do. Extract it into a subproject based on http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3694.htm

Does Mach7 switch on heterogenous interfaces?

I tested that the library for the support of boost::variant, and the simple example works fine, after I defined all the template specializations as per your example. However, I somehow got the expectation that I should be able to use the switch with two variants, like this:

void test(variant<X, Y, Z> vx, variant<M, N> vm)
{
    var<X> x; var<Y> y; var<Z> z;
    var<M> m; var<N> n;

    Match(vx, vm)
    {
        Case(C<X>(x), C<M>(m)) use(x, m);
        Case(C<Y>(y), C<M>(m)) use(y, m);
        // etc.
    }
    EndMatch
}

This fails to compile with classical meta-programming errors, but before I analyze them in detail, I wanted to check with you if my use case is even supposed to work?

Is Mach7 intended to switch on multiple heterogeneous types? Or is it just a bug in the implementation? Or perhaps my bug?

Rewrite old tag dispatching switch to use XTL generalization

We have a set of macros implement matching in those cases where we rely on tags instead of RTTI. We can let the user express relation between his tagged classes using XTL primitive and see if it would fit in the same way boost::variant did. The only problem I can immediately see is the substitutability loop that was iterating over base tags, but maybe we don't need it.

Support of boost::any is currently incorrect

Current adaptation for boost::any is wrong. The problem is that currently XTL still keeps the same assumption that the polymorphic implementation does: the offsets within objects of the same class must remain constant. This happens because Mach7 simply saves the offset to reapply it on other objects of the same type. With boost::any there is no such guarantee (since heap part is not at fixed offset with respect to the main boost::any object). Even with boost::variant it is possible to do heap-based implementation that would violate this, but the one in boost right now seem to satisfy the requirement.

This is not an unsolvable problem though (see bullet 4 of issue #6): we plan to have an adaptor for classes that don’t satisfy this requirement that would let users implement a slower, but type-safe cast once the subtyping relation was established with the Match statement (e.g. via the address of typeid).

Loading/unloading DLL

Robert suggested a plausible scenario today that might lead to invalid dispatch and should be considered when designing language solution:

1. Dll A is loaded
2. Classes from Dll A pass through a type switch and get memoized there
3. Dll A is unloaded
4. Dll B is loaded into the same physical address as Dll A was occupying
5. Some of v-tables in Dll B might be in the same spots as others from Dll A
6. If any of these vtbl pointers from Dll B now go through the same typeswitch, the typeswitch will incorrectly assume that it has already seen that vtbl-pointer.

To avoid this in language solution, we might need to remove vtbl-pointers from vtbl-map when Dll A is unloaded. Would also be interesting to see how often this may happen in practice with something like COM.

Error while building

I am getting the following error while doing cmake --build . :

In file included from /home/mnciitbhu/Git_Clones/Mach7/code/test/unit/algebraic.cpp:45:0:
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../match.hpp:946:9: note: #pragma message: Default pattern matching syntax is: G
   XTL_MESSAGE("Default pattern matching syntax is: G")
         ^
In file included from /home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/../metatools.hpp:47:0,
                 from /home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/bindings.hpp:48,
                 from /home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../unisyn.hpp:49,
                 from /home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../match.hpp:111,
                 from /home/mnciitbhu/Git_Clones/Mach7/code/test/unit/algebraic.cpp:45:
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/primitive.hpp:470:82: error: invalid use of ‘this’ at top level
     template <typename T> bool operator()(T&& t) const noexcept_when(noexcept_of(this->m_pat(std::forward<T>(t)))) { return m_pat(std::forward<T>(t)
                                                                                  ^
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/../config.hpp:345:37: note: in definition of macro ‘noexcept_when’
 #define noexcept_when(...) noexcept(__VA_ARGS__)
                                     ^
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/primitive.hpp:470:70: note: in expansion of macro ‘noexcept_of’
     template <typename T> bool operator()(T&& t) const noexcept_when(noexcept_of(this->m_pat(std::forward<T>(t)))) { return m_pat(std::forward<T>(t)
                                                                      ^
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/primitive.hpp:491:72: error: invalid use of ‘this’ at top level
     operator const result_type&() const noexcept_when(noexcept_of(eval(this->m_pat))) { return eval(this->m_pat); } // FIX: avoid implicit conversio
                                                                        ^
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/../config.hpp:345:37: note: in definition of macro ‘noexcept_when’
 #define noexcept_when(...) noexcept(__VA_ARGS__)
                                     ^
/home/mnciitbhu/Git_Clones/Mach7/code/test/unit/../../patterns/primitive.hpp:491:55: note: in expansion of macro ‘noexcept_of’
     operator const result_type&() const noexcept_when(noexcept_of(eval(this->m_pat))) { return eval(this->m_pat); } // FIX: avoid implicit conversio
                                                       ^
unit/CMakeFiles/algebraic.dir/build.make:54: recipe for target 'unit/CMakeFiles/algebraic.dir/algebraic.cpp.o' failed
make[2]: *** [unit/CMakeFiles/algebraic.dir/algebraic.cpp.o] Error 1
CMakeFiles/Makefile2:143: recipe for target 'unit/CMakeFiles/algebraic.dir/all' failed
make[1]: *** [unit/CMakeFiles/algebraic.dir/all] Error 2
Makefile:75: recipe for target 'all' failed
make: *** [all] Error 2

Am I missing anything?

what do you recommend for runtime pattern matching?

what do you recommend for runtime pattern matching?

Lock-free vtbl-map

Problem with multi-threaded access of vtbl-map

Are there any example of a recursive match?

For example, if you have a n : nat (the classical ADT), how can you do match "n with S (S n') ..."?
Are there limitation in the current implementation of recursive match?
Thank you.