5
\$\begingroup\$

I need to store some math terms. Originally I would use a tree to do it, especially if parsing strings was involved. However, since the expressions are built within the code and need not be parsed, I thought of doing it with nested lambdas and overloaded operators instead.

Since these expressions will probably be run a few thousand times (possibly up to 100k), I wonder if I should expect any problems (e.g. call stack too full) or what other thoughts you have on this approach. I expect no math term to contain more than 100 operators (in f+g*h I count 2 operators, for that matter).

Run it on godbolt

#include <functional>
#include <iostream>

using Func = std::function<double(double)>;

class Cube{
    public:
    double operator()(double x) const{
        return x*x*x;
    }
};

Func operator+(Func lhs, Func rhs){
    return [lhs, rhs](double x){
        return lhs(x) + rhs(x);
    };
}

Func operator-(Func lhs, Func rhs){
    return [lhs, rhs](double x){
        return lhs(x) - rhs(x);
    };
}

Func operator*(Func lhs, Func rhs){
    return [lhs, rhs](double x){
        return lhs(x) * rhs(x);
    };
}

Func operator/(Func lhs, Func rhs){
    return [lhs, rhs](double x){
        return lhs(x) / rhs(x);
    };
}
int main(){
    std::function<double(double)> square = [](double x){
        return x*x;
    };

    Cube c;

    auto result1 = square + c;
    auto result2 = square - c;
    auto result3 = square * c;
    auto result4 = c / square;
    auto result5 = result1 + result2 - result3 * result4;


    double x = 3.5;

    std::cout << "result1: " << result1(x) << "\n";
    std::cout << "result2: " << result2(x) << "\n";
    std::cout << "result3: " << result3(x) << "\n";
    std::cout << "result4: " << result4(x) << "\n";
    std::cout << "result5: " << result5(x) << "\n";
}
````
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I wondered about something similar myself, and it turns out this is surprisingly efficient. The call stack should not be deeper than if you were to evaluate the equivalent expression written directly in C++. It might be faster to make a bytecode compiler+interpreter, but using lambdas is certainly a more elegant way to do this in C++. \$\endgroup\$
    – G. Sliepen
    Jul 1, 2022 at 12:23

1 Answer 1

5
\$\begingroup\$

I don't see any major problems with this approach, in fact it strikes me as quite elegant! However, I notice your Cube callable/functor and your square function are not composable with the rest of your operators, and this is trivially fixable by making them also functions returning lambdas:

Func square(Func op) {
    return [op](double x) {
        auto r = op(x);
        return r*r;
    };
}

And similarly for cube. Note how I cache the result - this way if op has side effects, they only happen once, as most consumers of the library might expect.

What I mean by composable is that you can now do stuff like:

Func complicatedOperation = square(cube(cube + square));

The way these would get composed is by having a small helper function, id:

double id(double x) {
    return x;
}

id or "identity", a function which just returns its argument, provides a simple way of saying "value goes here" when the tree is being constructed.

and if you want to start the expression tree with the square or cube functions, define these:

liftedSquare = square(id);
liftedCube = cube(id);

Now, there's an easier way here - what about just having:

#include <cmath>
...
Func operator^(const Func& lhs, const Func& rhs){
    return [lhs, rhs](const double x){
        return std::pow(lhs(x), rhs(x));
    };
}

No need for separate square and cube anymore! square becomes auto square = id ^ lift(2);. lift is this function which is basically just a lazy version of id, it takes a value and returns a function returning that value.

Then just chuck everything into a namespace so it doesn't interfere with other operator overloads, and you have this:

#include <functional>
#include <cmath>
#include <iostream>

namespace LazyOps {
    using Func = std::function<double(double)>;
    namespace {
        double _id(const double x) {
            return x;
        }
        
    }
    Func id = _id;

    Func lift(const double x) {
        return [x](const double _) {
            return x;
        };
    }

    Func cube(const Func& op) {
        return [op](const double x) {
            auto r = op(x);
            return r*r*r;
        };
    }

    Func square(const Func& op) {
        return [op](const double x) {
            auto r = op(x);
            return r*r;
        };
    }

    Func operator+(const Func& lhs, const Func& rhs){
        return [lhs, rhs](const double x){
            return lhs(x) + rhs(x);
        };
    }

    Func operator-(const Func& lhs, const Func& rhs){
        return [lhs, rhs](const double x){
            return lhs(x) - rhs(x);
        };
    }

    Func operator*(const Func& lhs, const Func& rhs){
        return [lhs, rhs](const double x){
            return lhs(x) * rhs(x);
        };
    }

    Func operator/(const Func& lhs, const Func& rhs){
        return [lhs, rhs](const double x){
            return lhs(x) / rhs(x);
        };
    }

    Func operator^(const Func& lhs, const Func& rhs){
        return [lhs, rhs](const double x){
            return std::pow(lhs(x), rhs(x));
        };
    }
}

int main(){
    using namespace LazyOps;
    auto liftedSquare = square(id);
    auto liftedCube = cube(id);
    auto result1 = liftedSquare + liftedCube;
    auto result2 = liftedSquare - liftedCube;
    auto result3 = liftedSquare * liftedCube;
    auto result4 = liftedCube / liftedSquare;
    auto newSquare = id ^ lift(2);
    auto result5 = result1 + result2 - result3 * result4;
    auto result6 = cube(square(liftedCube / liftedSquare));
    auto result7 = id ^ id;


    double x = 4.0;

    std::cout << "result1: " << result1(x) << "\n";
    std::cout << "result2: " << result2(x) << "\n";
    std::cout << "result3: " << result3(x) << "\n";
    std::cout << "result4: " << result4(x) << "\n";
    std::cout << "result5: " << result5(x) << "\n";
    std::cout << "result6: " << result6(x) << "\n";
    std::cout << "result7: " << result7(x) << "\n";
    std::cout << "square(" << x << "): " << newSquare(x) << "\n";
}

Unfortunately, the compiler isn't great with compiling auto result = id ^ id; just like that, therefore I had to put in a type deduction hint by putting the actual _id function in a private anonymous namespace and defining an alias Func id = _id; in the actual LazyOps namespace.

As for whether this will blow up your stack, I can't really say, but hopefully accepting the Func arguments as const references can help with that. Make a small script to generate some huge expression tree and see how it goes!

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.