Functions are Asymmetric – Why is a raven like a writing desk?

Here are some functions:

auto f() -> int;
auto g(int) -> int;
auto h(int, int) -> int;

What they all have in common, structurally, is that they each return one thing. Even though they may take any number of arguments, they must each have one return value. One shall be the number, and the number shall be one. This is true of all functions.

(It’s not too important, but here I consider void to be “one thing” as a return type, for reasons which will hopefully become clear. Zero is right out.)

Maybe that doesn’t seem strange. It’s just how we’re used to functions working. Ah, those steeped in functional programming might say, but maybe this is the wrong way to look at it. Because if we curry functions and use partial application, we can say that they always have one argument and return one value, and then they are symmetric.

Well that’s mathematically true. This is how some languages — like Haskell — work, and they get along fine, having built-in partial application and lots of tools to deal with that view. Most languages — like C++ — don’t have that wealth of tools and it’s more natural to express multiple-argument functions. Especially because we have different tools to deal with variadic functions. Treating functions like they take multiple values is fine.

OK, rather than reducing every function to one argument, alternatively we can try to attack this problem by returning multiple values as one, in a tuple (or other product type), and we could make that work. That would be perfectly doable, if tedious.

So why bring this up at all? Because the title is missing a word. It should say “Synchronous Functions are Asymmetric”. Because when we move to asynchronous functions, they needn’t be! But implementing them with synchronous functions — as we must — can impose asymmetry.

Here are some asynchronous functions analogous to the functions above:

auto f = then([] { return 42; });
auto g = then([] (int x) { return x + 1; });
auto h = then(
  [] (int x, int y) { return x + y; });

These functions are in their “pipeable” form here without their inputs. They could occur in expressions like:

just(42) 
  | then([] (int x) { return x + 1; }) 
  | ...

They receive their inputs on the value channel, and they send their result on the value channel. But the channel can contain any number of values:

just(17, 42)
  | then([] (int x, int y) { return x + y; }) 
  | ...

And now we see the artificial constraint better: because then is implemented using a single synchronous function, it can’t send multiple values. The asymmetry of synchronous functions is causing the same annoying asymmetry in the asynchronous world.

We could of course do the same thing as in the synchronous case and return a tuple from the function passed to then. And we could even provide machinery that unwraps tuples automatically into a pack of arguments that continue down the asynchronous pipeline. But that seems like a poor solution: for instance, what if we actually want to send a tuple? In that direction lies more complexity.

If we do go down that road though, we can make it sound. We’re pushing the symmetry into the argument/return type(s), and the logical place to end up is with every function both taking and returning one blessed structured value which represents a sum-of-products-of-values. This approach exists.

Alternatively (and perhaps closer to what we are used to), we could allow then to take more (synchronous) functions:

just(A{}, B{}) 
  | then([] (A x) { ... },
         [] (B y) { ... })
  | ...

And each such function gets to send its own value onward.

Note: we aren’t doing this only to distribute the input arguments — if we wanted that, we could just do that by passing then a single function that would call more functions, distributing the arguments. We are doing this so that then itself can send more than one value.

call_by_need

(Note: “call by need” is a technique sometimes used to describe lazy evaluation. That is not how I am using it here. It just seems like a reasonable name for this function.)

template <callable ...Fs, typename ...Args>
auto call_by_need(some<Fs...>, some<Args...>)
  /* -> some<Results...> */;

call_by_need takes some functions and some arguments, and applies the functions to the arguments, returning the results. In order to implement this, we need to define semantics for how the functions will be called.

(Because of C++, we are currently limited to using tuple or equivalent machinery here, but that implementation detail isn’t going to show up in then.)

How does call_by_need call the functions? As it can — and according to the following algorithm:

For each function:
- try to call it with all arguments [0..N).
- if that fails, try to call it with arguments [0..N-1), etc, until a call succeeds.
- if that fails, try again starting with arguments [1..N), etc.
The results of the discovered function calls (with voids filtered out) become the results we’ll return.
Finally, any unused arguments are appended to the results.

In other words: we call each function with the earliest, longest sequence of arguments from the input list that is possible. This is just one possible approach, but a reasonable one.

The explanation is clearer with some examples.

The “normal” case:

call_by_need(tuple{[] (A) { return X{}; },
                   [] (B) { return Y{}; }},
             tuple{A{}, B{}});
// returns tuple<X, Y>

Swapping argument order need not alter the result order:

call_by_need(tuple{[] (A) { return X{}; },
                   [] (B) { return Y{}; }},
             tuple{B{}, A{}});
// returns tuple<X, Y>

But swapping function order does:

call_by_need(tuple{[] (B) { return Y{}; },
                   [] (A) { return X{}; }},
             tuple{A{}, B{}});
// returns tuple<Y, X>

Functions draw contiguous arguments, and arguments can be used multiple times:

call_by_need(tuple{[] (A, B) { return X{}; },
                   [] (B, C) { return Y{}; }},
             tuple{A{}, B{}, C{}});
// returns tuple<X, Y>

Any unused arguments are passed through after the function results:

call_by_need(tuple{[] (B) { return X{}; },
                   [] (C) { return Y{}; }},
             tuple{A{}, B{}, C{}});
// returns tuple<X, Y, A>

Functions can return void:

call_by_need(tuple{[] (A) { return X{}; },
                   [] (B) { return; }},
             tuple{A{}, B{}});
// returns tuple<X>

If a function can’t be called, it’s an error:

call_by_need(tuple{[] (A) { return X{}; },
                   [] (B) { return Y{}; }},
             tuple{A{}});
// error! can't call second function

And functions with default arguments work normally.

call_by_need(tuple{[] (A) { return X{}; },
                   [] (B={}) { return Y{}; }},
             tuple{A{}});
// returns tuple<X, Y>

Symmetric then

Now that we have call_by_need (implementation left as an exercise), we can use it to implement a then that is symmetric.

just(A{}, B{}) 
  | then([] (A x) { ... },
         [] (B y) { ... },
         [] { ... })
  | ...

By allowing passing multiple synchronous functions, we also allow returning multiple results into the channel. Symmetry is restored.

One interesting thing that comes out of this is that of course multiple results can mean no results. We can call then with no arguments:

just(A{}, B{}) | then() | ...

And it acts like the identity function, leaving everything alone in the channel. I take this as a sign of good compositionality. This may seem useless, but such things always do at first. For one related use case, consider using then to insert side-effectful code while passing through arguments:

just(A{}, B{}) 
  | then([] { print("hello"); }) 
  | ...

Given a channel that can contain multiple values, it makes sense for a function acting on that channel that not only can it take multiple values, but that it can also return multiple values. We are limited by C++ in the ways we can actually implement that, but I think this formulation of then is not bad.