Expression algebras
Some phenomena can be conveniently described as expressions in observations of one or more processes. To do this requires developing an algebra of real numbers with "placeholders" where a placeholder represents a process.
For example, consider writing software for some kind of "smart watch" fitness device that includes a heart rate monitor. We might define heart rate performance over an interval of time by something like
$r/r_{t} - 1.0$ .
If $r$ "fixes" at some time $t +\Delta t$ to a value greater than $r_{t}$, performance will be positive. If it fixes to the same value as $r_{t}$ then performance will be $0$ and if $r_{t + \Delta t}$ is observed to be less than $r_{t}$, degradation has occurred.
In our smart watch application we may in some contexts be interested only in the positive part of heart-rate performance, i.e.
$(r/r_{t} - 1.0)^{+} = max (0, r/r_{t} - 1.0)$ .
We can create further derived expressions that scale and "cap" performance$100 * min (0.2, max (0, r/r_{t} - 1.0))$ .
Of course, for the above formula to result in physicals amounts we must specify concretely when the heart-rate is to be observed e.g.
$fix (t + \Delta t, 100 * min (0.2, max (0, r/r_{t} - 1.0))) = $
$100 * min (0.2, max (0, r_{t + \Delta t}/r_{t} - 1.0))$ .
Let's look at one way to express all this in C++. The core idea is to model each primitive expression case as a C++ type. The recursive expression type itself is a discriminated union.
#include <string>
#include <iostream>
#include <functional>
#include <algorithm>
#include <boost/variant.hpp>
#include <boost/variant/apply_visitor.hpp>
struct _neg;
struct _fix;
struct _add;
struct _sub;
struct _mul;
struct _div;
struct _max;
struct _min;
struct _const;
struct _obs;
using expression =
boost::variant<
_const
, _obs
, boost::recursive_wrapper<_neg>
, boost::recursive_wrapper<_fix>
, boost::recursive_wrapper<_add>
, boost::recursive_wrapper<_sub>
, boost::recursive_wrapper<_mul>
, boost::recursive_wrapper<_div>
, boost::recursive_wrapper<_min>
, boost::recursive_wrapper<_max>
>;
Now that we've got the definition of expression out of the way, we can "go back" and fill in the skipped details of the expression classes.
struct _const { double f; };
struct _obs { std::string tag; };
struct _neg { expression f; };
struct _fix { std::string d; expression f; };
struct _add { expression lhs; expression rhs; };
struct _sub { expression lhs; expression rhs; };
struct _mul { expression lhs; expression rhs; };
struct _div { expression lhs; expression rhs; };
struct _max { expression lhs; expression rhs; };
struct _min { expression lhs; expression rhs; };
I'm using a simple std::string to represent a fixing time $t$. Of course in the real world that would probably be some kind of datetime.
The stream insertion operators aren't pretty but they are regular.
std::ostream& operator << (std::ostream& os, _neg const& e) {
return os << "-(" << e.f << ")";
}
std::ostream& operator << (std::ostream& os, _fix const& e) {
return os << "fix(" << e.d << ", " << e.f << ")";
}
std::ostream& operator << (std::ostream& os, _add const& e) {
return os << e.lhs << " + " << e.rhs;
}
std::ostream& operator << (std::ostream& os, _sub const& e) {
return os << e.lhs << " - " << e.rhs;
}
std::ostream& operator << (std::ostream& os, _mul const& e) {
return os << e.lhs << " * " << e.rhs;
}
std::ostream& operator << (std::ostream& os, _div const& e) {
return os << e.lhs << " / " << e.rhs;
}
std::ostream& operator << (std::ostream& os, _max const& e) {
return os << "max (" << e.lhs << ", " << e.rhs << ")";
}
std::ostream& operator << (std::ostream& os, _min const& e) {
return os << "min (" << e.lhs << ", " << e.rhs << ")";
}
std::ostream& operator << (std::ostream& os, _obs const& e) {
return os << "observation(\"" << e.tag << "\")";
}
std::ostream& operator << (std::ostream& os, _const const& e) {
return os << e.f;
}
Now things start to get interesting. Definitions of the elementary arithmetic operators. This bit is worth reading closely to make sure you understand it before moving on.
namespace detail {
struct neg_visitor :
boost::static_visitor {
expression operator()(_const lhs) const {
return _const {-lhs.f};
}
template
expression operator ()(T const& x) const {
_neg res; res.f = x; return res;
}
};
template <class Op>
struct binop_visitor
: boost::static_visitor<expression>{
typedef std::function<double(double, double)> op_t;
op_t op;
binop_visitor (op_t const& op) : op(op)
{}
expression operator()(_const lhs, _const rhs) const {
return _const {op (lhs.f, rhs.f)};
}
template <class T, class U>
expression operator ()(T const& x, U const& y) const {
Op res; res.lhs = x; res.rhs = y; return res;
}
};
}//namespace detail
expression operator - (expression const& x) {
return boost::apply_visitor (detail::neg_visitor (), x);
}
expression operator + (expression const& lhs, expression const& rhs) {
return boost::apply_visitor (detail::binop_visitor<_add> (
[](double x, double y) ->double { return x + y; })
, lhs, rhs);
}
expression operator - (expression const& lhs, expression const& rhs) {
return boost::apply_visitor (detail::binop_visitor<_sub> (
[](double x, double y) ->double { return x - y; })
, lhs, rhs);
}
expression operator * (expression const& lhs, expression const& rhs) {
return boost::apply_visitor (detail::binop_visitor<_mul> (
[](double x, double y) -> double { return x * y; })
, lhs, rhs);
}
expression operator / (expression const& lhs, expression const& rhs) {
return boost::apply_visitor (detail::binop_visitor<_div> (
[](double x, double y) -> double { return x / y; })
, lhs, rhs);
}
expression max (expression const& lhs, expression const& rhs) {
return boost::apply_visitor (detail::binop_visitor<_max> (
[](double x, double y) -> double { return (std::max) (x, y); })
, lhs, rhs);
}
expression min (expression const& lhs, expression const& rhs) {
return boost::apply_visitor (detail::binop_visitor<_min> (
[](double x, double y) -> double { return (std::min) (x, y); })
, lhs, rhs);
}
Here are the basic expression factory functions modulo fix.
expression const_ (double f) { return _const{f}; }
expression observation (std::string const& tag) { _obs m; m.tag = tag; return m; }
Here then is fix.
expression fix (std::string const& d, expression const& x);
namespace detail {
struct fix_visitor :
boost::static_visitor<expression> {
std::string d;
fix_visitor (std::string const& d) : d(d)
{}
expression operator ()(_const const& x) const
{ return x; }
expression operator ()(_obs const& x) const
{ _fix res;
res.d = d; res.f = x; return res; }
expression operator ()(_neg const& x) const
{ return x; }
expression operator ()(_fix const& x) const
{ return x; }
expression operator ()(_add const& x) const
{ _add res; res.lhs = fix (d, x.lhs);
res.rhs = fix (d, x.rhs); return res; }
expression operator ()(_sub const& x) const
{ _sub res; res.lhs = fix (d, x.lhs);
res.rhs = fix (d, x.rhs); return res; }
expression operator ()(_mul const& x) const
{ _mul res; res.lhs = fix (d, x.lhs);
res.rhs = fix (d, x.rhs); return res; }
expression operator ()(_div const& x) const
{ _div res; res.lhs = fix (d, x.lhs);
res.rhs = fix (d, x.rhs); return res; }
expression operator ()(_max const& x) const
{ _max res; res.lhs = fix (d, x.lhs);
res.rhs = fix (d, x.rhs); return res; }
expression operator ()(_min const& x) const
{ _min res; res.lhs = fix (d, x.lhs);
res.rhs = fix (d, x.rhs); return res; }
};
}//namespace detail
expression fix (std::string const& d, expression const& x) {
return boost::apply_visitor (detail::fix_visitor (d), x);
}
You see what's going on there right? In order to fix an expression you have to recurse down into the expression replacing unfixed observations with fix expressions.
Ok, let's give it a go!
int main () {
expression rate = observation ("heart rate");
expression scale = const_ (100);
expression score = scale * fix ("t + 5",
min (const_ (0.2), max (rate / fix ("t", rate) - const_ (1.0), const_ (0.0))))
;
std::cout << score << std::endl;
return 0;
}
That program produces the output
100 * min (0.2, max(fix(t + 5, observation("heart rate")) / fix(t, observation("heart rate")) - 1, 0.0))
(note that the fixing to $t + 5$ has moved into the interior of the original expression as we'd hope).
So that's it - a basic expression algebra with placeholders. What's missing at this point is a function to simplify an expression in the context of a set of fixings. If we assume fixings are described as tuples of (1) the observation tag, (2) the time-stamp and (3) the observed value, the signature for that function might read something like,
expression simplify ( std::vector<std::tuple<std::string, std::string, double>> const& fixings , expression const& xpr);I'll leave the implementation of this as an exercise for the reader.
