Evaluating math terms as nested lambdas instead of expression tree

Question

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";
}
````

Answer 1

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!