Freezing Expressions

Question

I have a C ++ expression that I want to freeze. By this, I mean that I have the following syntax:

take x*x with x in container ... 

where ... indicates the further (not useful for this problem) syntax. However, if I try to compile this, no matter what translations of the preprocessor I used to “take” the “operator” (in quotation marks, since it is technically not an operator, but the translation phase turns it into a class with, say, the operator *, available to him), the compiler is still trying to evaluate / determine where x * x comes from (and since it was not announced earlier (since it was declared further in the "in" stage), it instead) cannot find it and gives compilation error.

My current idea essentially involves trying to put an expression inside a lambda (and since we can infer the type of the container, we can declare x correct type, for example, [](decltype(*begin(container)) x) { return x*x } - like this when the compiler looks at this statement, it is valid and no error is raised), however I encounter errors that really achieve this.

So my question is: Is there a way / what's the best way to “freeze” the x*x my expression?

EDIT : In an attempt to clarify my question, do the following. Suppose the - operator is defined in a robust way, so the following attempts to achieve what the syntax does above take ... :

MyTakeClass() - x*x - MyWithClass() - x - MyInClass() - container ...

When this statement compiles, the compiler will throw an error; x is not declared, so x * x makes no sense (and also x - MyInClass (), etc., etc.). What I'm trying to achieve is to find a way to compile the above expression using any available voodoo magic without knowing the type of x (or, in fact, it will be called x, it could be called 'somestupidvariablename') in advance.

Answer 1

I made an answer very similar to my previous answer, but using actual expression patterns that should be much faster. Unfortunately, MSVC10 crashes when it tries to compile it, but MSVC11, GCC 4.7.0 and Clang 3.2 all compile and run it just fine. (All other versions are not verified)

Patterns are used here. The implementation code is here .

 #define take #define with , #define in >>= //function call for containers template<class lhsexpr, class container> lhsexpr operator>>=(lhsexpr lhs, container& rhs) { for(auto it=rhs.begin(); it!=rhs.end(); ++it) *it = lhs(*it); return lhs; } int main() { std::vector<int> container0; container0.push_back(-4); container0.push_back(0); container0.push_back(3); take x*x with x in container0; //here the magic line for(auto it=container0.begin(); it!=container0.end(); ++it) std::cout << *it << ' '; std::cout << '\n'; auto a = x+x*x+'a'*x; auto b = a; //make sure copies work b in container0; b in container1; std::cout << sizeof(b); return 0; } 

As you can see, this is used in exactly the same way as my previous code, except that now all functions are solved at compile time, which means that it will have the same speed than lambda. In fact, C ++ 11 lambdas was preceded by boost::lambda , which works with very similar concepts.

This is a separate answer because the code is much different and much more complicated / intimidating. This also explains why the implementation is not in the answer itself.

Answer 2

I almost came up with a solution based on expression patterns (note: these are not expression patterns, they are based on expression patterns). Unfortunately, I could not come up with a method that does not require you to first use x , but I came up with a way to delay the type, so you need to declare x one globally and use it for different types again and again in the same program / file / area. Here is the type of expression in which the magic that I developed works in order to be very flexible, you should be able to easily add operations and use as you like. It is used exactly as you described, with the exception of premise x.

The disadvantages I know of are: T*T , T+T and T(long) are required to compile.

 expression x(0, true); //x will be the 0th parameter. Sorry: required :( int main() { std::vector<int> container; container.push_back(-3); container.push_back(0); container.push_back(7); take x*x with x in container; //here the magic line for(unsigned i=0; i<container.size(); ++i) std::cout << container[i] << ' '; std::cout << '\n'; std::vector<float> container2; container2.push_back(-2.3); container2.push_back(0); container2.push_back(7.1); take 1+x with x in container2; //here the magic line for(unsigned i=0; i<container2.size(); ++i) std::cout << container2[i] << ' '; return 0; } 

and here the class determines that it all works:

 class expression { //addition and constants are unused, and merely shown for extendibility enum exprtype{parameter_type, constant_type, multiplication_type, addition_type} type; long long value; //for value types, and parameter number std::unique_ptr<expression> left; //for unary and binary functions std::unique_ptr<expression> right; //for binary functions public: //constructors expression(long long val, bool is_variable=false) :type(is_variable?parameter_type:constant_type), value(val) {} expression(const expression& rhs) : type(rhs.type) , value(rhs.value) , left(rhs.left.get() ? std::unique_ptr<expression>(new expression(*rhs.left)) : std::unique_ptr<expression>(NULL)) , right(rhs.right.get() ? std::unique_ptr<expression>(new expression(*rhs.right)) : std::unique_ptr<expression>(NULL)) {} expression(expression&& rhs) :type(rhs.type), value(rhs.value), left(std::move(rhs.left)), right(std::move(rhs.right)) {} //assignment operator expression& operator=(expression rhs) { type = rhs.type; value = rhs.value; left = std::move(rhs.left); right = std::move(rhs.right); return *this; } //operators friend expression operator*(expression lhs, expression rhs) { expression ret(0); ret.type = multiplication_type; ret.left = std::unique_ptr<expression>(new expression(std::move(lhs))); ret.right = std::unique_ptr<expression>(new expression(std::move(rhs))); return ret; } friend expression operator+(expression lhs, expression rhs) { expression ret(0); ret.type = addition_type; ret.left = std::unique_ptr<expression>(new expression(std::move(lhs))); ret.right = std::unique_ptr<expression>(new expression(std::move(rhs))); return ret; } //skip the parameter list, don't care. Ignore it entirely expression& operator<<(const expression&) {return *this;} expression& operator,(const expression&) {return *this;} template<class container> void operator>>(container& rhs) { for(auto it=rhs.begin(); it!=rhs.end(); ++it) *it = execute(*it); } private: //execution template<class T> T execute(const T& p0) { switch(type) { case parameter_type : switch(value) { case 0: return p0; //only one variable default: throw std::runtime_error("Invalid parameter ID"); } case constant_type: return ((T)(value)); case multiplication_type: return left->execute(p0) * right->execute(p0); case addition_type: return left->execute(p0) + right->execute(p0); default: throw std::runtime_error("Invalid expression type"); } } //This is also unused, and merely shown as extrapolation template<class T> T execute(const T& p0, const T& p1) { switch(type) { case parameter_type : switch(value) { case 0: return p0; case 1: return p1; //this version has two variables default: throw std::runtime_error("Invalid parameter ID"); } case constant_type: return value; case multiplication_type: return left->execute(p0, p1) * right->execute(p0, p1); case addition_type: return left->execute(p0, p1) + right->execute(p0, p1); default: throw std::runtime_error("Invalid expression type"); } } }; #define take #define with << #define in >> 

Compiles and works with the correct output at http://ideone.com/Dnb50

You may notice that since x must be predefined, the with section is completely ignored. There is almost no macromagy, macros effectively turn it into " x*x >> x << container ", where >>x does absolutely nothing. Thus, the expression is effectively " x*x << container ".

Also note that this method is slow because it is an interpreter, and that is almost all slowdown. However, it has a bonus that it is serializable, you can save the function to a file, load it later and execute it then.

R.MartinhoFernandes noted that the definition of x can be simplified to just be expression x; , and it can infer the order of parameters from with , but it will require a lot of rethinking the design and will be more complicated. I could come back and add this functionality later, but at the same time I know that it is definitely possible.

---

If you can change the expression to take(x*x with x in container) , this will eliminate the need to pre-run x with something much simpler than expression patterns.

 #define with , #define in , #define take(expr, var, con) \ std::transform(con.begin(), con.end(), con.begin(), \ [](const typename con::value_type& var) -> typename con::value_type \ {return expr;}); int main() { std::vector<int> container; container.push_back(-3); container.push_back(0); container.push_back(7); take(x*x with x in container); //here the magic line for(unsigned i=0; i<container.size(); ++i) std::cout << container[i] << ' '; } 

Answer 3

I don’t think you can get this “list compilation” (not really, but it does the same thing) ala haskell using a preprocessor. The preprocessor simply performs a simple search and replaces the argument capability, so it cannot perform arbitrary replacements. A special change in the order of the parts of the expression is impossible.

I don’t see a way to do this without changing the order, since you always need x to appear before x*x somehow to define this variable. Using lambda won't help, since you still need x in front of the x*x , even if it's just an argument. This makes this syntax impossible.

There are several ways around this:

• Use a different preprocessor. There are preprocessors based on the ideas of Lisp -macros, which can be made by syntax and, therefore, can arbitrarily convert one syntax tree to another. One example is Camlp4 / Camlp5, developed for the OCaml language. There are some very good guides on how to use this for arbitrary syntax conversion. I had an explanation of how to use Camlp4 to convert make files to C code, but I can no longer find it. There are other tutorials on how to do such things.

• Change the syntax a bit. This list comprehension is just a syntactic simplification of using Monad . With the advent of C ++ 11, Monads became possible in C ++. However, syntactic sugar may not be. If you decide to wrap the material you are trying to do in Monad, much more will be possible, you just need to change the syntax a bit. Implementing Monads in C ++ is something other than fun (although I expected otherwise). Take a look here for an example of how to get Monads in C ++.

Answer 4

The best approach is to analyze it using a preprocessor. I believe that a preprocessor can be a very powerful tool for creating EDSL (embedded domain languages), but you must first understand the limitations of a preprocessor that parses things. A preprocessor can only analyze predefined tokens. Therefore, the syntax needs to be slightly changed by placing brackets around the expressions, and the FREEZE macro should also surround it (I just chose FREEZE, it could be called anything):

 FREEZE(take(x*x) with(x, container)) 

Using this syntax, you can convert it to a preprocessor sequence (of course, using the Boost.Preprocessor library). After you use it as a preprocessor sequence, you can apply many algorithms to it to transform it as you like. A similar approach is done using the Linq library for C ++, where you can write this:

 LINQ(from(x, numbers) where(x > 2) select(x * x)) 

Now, to convert to a pp sequence first, you need to identify the keywords you need to parse, for example:

 #define KEYWORD(x) BOOST_PP_CAT(KEYWORD_, x) #define KEYWORD_take (take) #define KEYWORD_with (with) 

So how does this work when you call KEYWORD(take(x*x) with(x, container)) , it will expand to (take)(x*x) with(x, container) , which is the first step to converting its in pp sequence. Now, to continue, we need to use the while construct from the Boost.Preprocessor library, but first we need to define some small macros to help us with this:

 // Detects if the first token is parenthesis #define IS_PAREN(x) IS_PAREN_CHECK(IS_PAREN_PROBE x) #define IS_PAREN_CHECK(...) IS_PAREN_CHECK_N(__VA_ARGS__,0) #define IS_PAREN_PROBE(...) ~, 1, #define IS_PAREN_CHECK_N(x, n, ...) n // Detect if the parameter is empty, works even if parenthesis are given #define IS_EMPTY(x) BOOST_PP_CAT(IS_EMPTY_, IS_PAREN(x))(x) #define IS_EMPTY_0(x) BOOST_PP_IS_EMPTY(x) #define IS_EMPTY_1(x) 0 // Retrieves the first element of the sequence // Example: // HEAD((1)(2)(3)) // Expands to (1) #define HEAD(x) PICK_HEAD(MARK x) #define MARK(...) (__VA_ARGS__), #define PICK_HEAD(...) PICK_HEAD_I(__VA_ARGS__,) #define PICK_HEAD_I(x, ...) x // Retrieves the tail of the sequence // Example: // TAIL((1)(2)(3)) // Expands to (2)(3) #define TAIL(x) EAT x #define EAT(...) 

This provides better detection of brackets and voids. And it provides a HEAD and TAIL macro that works slightly differently than BOOST_PP_SEQ_HEAD . (Boost.Preprocessor cannot process sequences that have vardiac parameters). Now here is how we can define the TO_SEQ macro that uses the while construct:

 #define TO_SEQ(x) TO_SEQ_WHILE_M \ ( \ BOOST_PP_WHILE(TO_SEQ_WHILE_P, TO_SEQ_WHILE_O, (,x)) \ ) #define TO_SEQ_WHILE_P(r, state) TO_SEQ_P state #define TO_SEQ_WHILE_O(r, state) TO_SEQ_O state #define TO_SEQ_WHILE_M(state) TO_SEQ_M state #define TO_SEQ_P(prev, tail) BOOST_PP_NOT(IS_EMPTY(tail)) #define TO_SEQ_O(prev, tail) \ BOOST_PP_IF(IS_PAREN(tail), \ TO_SEQ_PAREN, \ TO_SEQ_KEYWORD \ )(prev, tail) #define TO_SEQ_PAREN(prev, tail) \ (prev (HEAD(tail)), TAIL(tail)) #define TO_SEQ_KEYWORD(prev, tail) \ TO_SEQ_REPLACE(prev, KEYWORD(tail)) #define TO_SEQ_REPLACE(prev, tail) \ (prev HEAD(tail), TAIL(tail)) #define TO_SEQ_M(prev, tail) prev 

Now when you call TO_SEQ(take(x*x) with(x, container)) , you should get the sequence (take)((x*x))(with)((x, container)) .

Now this sequence is much easier to work with (due to the Boost.Preprocessor library). Now you can undo it, transform, filter, collapse, etc. It is extremely powerful and much more flexible than defining macros. For example, in the Linq library, the query from(x, numbers) where(x > 2) select(x * x) converted to these macros:

 LINQ_WHERE(x, numbers)(x > 2) LINQ_SELECT(x, numbers)(x * x) 

What are these macros, then it will generate a lambda for understanding the list, but it will work much more with them when it generates a lambda. You can do the same in your library, take(x*x) with(x, container) can be converted to something like this:

 FREEZE_TAKE(x, container, x*x) 

In addition, you do not define macros like take that invade global space.

Note. These macros here require the C99 preprocessor and therefore will not work in MSVC. (However, there are workarounds)