hyperoperations in c++

because it's a horrible idea. i'm not the only one with horrible ideas: check out https://github.com/klmr/named-operator.

as a recovering c++ weenie, i think that the ability to change the meaning of the goddamned language is somewhat horrifying, because even simple statements like a + b can devolve into hundreds of lines of template errors — and then, when fixed, wind up mutating global state and making you sad anyway when you have a crash in prod.

of course, as a recovering c++ weenie, i know exactly how to make these horrible things happen and have a deep, pent-up rage/delight in seeing things crash, burn, then keep flying, so i needed an outlet.

the hyperoperator sequence is what you get if exponentiation doesn't satisfy you. their intuitive derivation is "multiplication is (for some value of is) just repeated addition, exponentiation is (again, for some value of is) , so why not define another operator to be repeated exponentiation?" this next operator is knows as tetration, and is the first in the sequence of hyperoperations.

for your reference (and mine, while i'm writing this), the hyperoperations may be defined either by the fully recursive formula god, i love org mode. all the writing, code, math, and output from this shitpost lives in exactly one file, and i can inline-edit, format, and run the code blocks, all from emacs. truly a dream come true. if you're curious about this and maybe want to fuck up your life too, go check it out.

or by the more readable, less formal set of expressions

the latter of which is a pretty decent candidate for direct translation into code. both because it's easier to read and implement, and because the theoretically-lovely recursive formula given in \eqref{orge731696} is horribly inefficient if you implement it directly. we do actually want to be able to run this program, you know.

we'll start with some pretty standard c++: a templatized function the astute reader will note that this didn't have to be a template. we could have written a simple recursive function call. but what are we, C programmers? this is Real Software, written by Segmentation fault (core dumped) and some specializations. nothing too crazy. i'll even use int as our numeric type!

 1template <int N>
 2int hyperop(int a, int b) {
 3  int acc = a;
 4  for (int i = 0; i < b - 1; ++i)
 5    acc = hyperop<N - 1>(a, acc);
 6  return acc;
 7}
 8
 9template<>
10int hyperop<0>(int, int b) {
11  return b + 1;
12}
13
14template<>
15int hyperop<1>(int a, int b) {
16  return a + b;
17}
18
19// for efficiency; we're all about zero-cost abstractions here
20template<>
21int hyperop<2>(int a, int b) {
22  return a * b;
23}

testing this, we see that it gives the results you'd expect from the intuitive definition of the hyperoperations:

int main() {
  cout
    << "2[0]3 = " << setw(5) << hyperop<0>(2, 3) << '\n'
    << "2[1]3 = " << setw(5) << hyperop<1>(2, 3) << '\n'
    << "2[2]3 = " << setw(5) << hyperop<2>(2, 3) << '\n'
    << "2[3]3 = " << setw(5) << hyperop<3>(2, 3) << '\n'
    << "2[4]3 = " << setw(5) << hyperop<4>(2, 3) << '\n'
    << "2[5]3 = " << setw(5) << hyperop<5>(2, 3) << '\n'
    << "2[6]3 = " << setw(5) << hyperop<6>(2, 3) << '\n'
    ;
}

g++ -o hyperop-easy hyperop-easy.c++ &&
    ./hyperop-easy

2[0]3 =     4
2[1]3 =     5
2[2]3 =     6
2[3]3 =     8
2[4]3 =    16
2[5]3 = 65536
2[6]3 =     2

oops. well, we just won't use that last one. no, i will NOT use bignums, you can't make me! (it overflows long, too.)

of course we're not done. who told you we were done!?

the real beauty of c++ is making the hard easy, the easy hard, and both cause unexpected template substitution errors. we want some convenient syntax for this, and anyone who says we're abusing how operators work be damned! the stl gets to cause unexpected behavior thanks to operator precedence not changing in an overload, so why shouldn't we?

since python uses ** as an exponentiation operator, we should use that as our syntax for exponentiation, too, just a little extended. c++, as you may know, does not have a ** operator, but it does have a unary * operator — pointer dereferencing — that's conveniently overloadable! so we'll just use that.

but, like, how? and how are we going to manage to chain them and get the right operator?

we'll start with some intermediate types, since you can't overload built-in operators and some operator overloads have to be members (they think they're sooooo darned special). so we'll pull a trick from java sorry, bjarne (pp. 22–23). and define our own numeric class for the right-hand side. we're also going to need some way to count how many asterisks we've typed — and we want to do that statically — which i've decided to do via an intermediate type that should disappear at runtime. so:

24// forward declaration because c++ is actually not very smart
25template <typename last>
26struct next_op;
27
28struct integer {
29  constexpr const static int N = 2; // "we will discuss this later"
30  int i;
31
32  // copy-constructible from int
33  integer(int i) : i(i) {}
34
35  // implicitly convertable to int, if we need to
36  operator int() const { return i; }
37
38  // will be defined out-of-line once we know more about next_op
39  next_op<integer> operator*();
40};
41
42// nice convenient literal syntax, totally not a confusing suffix
43integer operator""_i(unsigned long long i) { return integer(i); }

for the purposes of this shitpost, i have refrained from testing some of the more exotic operations you can perform on integers, such as addition. the conversion operator operator int should take care of all that for us.

anyway, that's integer defined. now, for next_op:

44template <typename last>
45struct next_op {
46  constexpr const static int N = last::N + 1;
47  const last& l;
48
49  // can create the next operator from the current one
50  next_op(const last& l) : l(l) {}
51
52  // can perform that construction by iterative dereferencing
53  next_op<next_op<last>> operator*() { return next_op<next_op<last>>(*this); }
54
55  // implicitly converts to... an integer? sure, why not?
56  operator int() const { return l; }
57};
58
59// finally define construction of next_op<integer>
60next_op<integer> integer::operator*() { return next_op<integer>(*this); }

the objective here being that we can "dereference" integer some number of times, then perform a final "multiplication" to actually apply the hyperoperator. speaking of:

61template<typename last>
62int operator*(int a, next_op<last> b) {
63  return hyperop<decltype(b)::N>(a, b);
64}

that should do it. i refer you back to the the beginning of this post.