Letters from the Outer Shell

Templates Calculus I

2020-10-17T00:00:00+00:00

In the previous article I have touched on the idea that you can build a Lisp-like language on top of C++ templates and type system. Whether any Lisp is a true functional language is a questionable question and can lead to some skirmishes. But the templates are functional, no doubt. I was wondering if it would be possible to build a calculus on top of templates with just types, and how far this can be pushed.

Basics

Lambda calculus is the smallest programming language. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Despite not having numbers, strings, booleans, or any non-function datatype, lambda calculus can be used to represent any Turing Machine. Lambda calculus is composed of 3 elements: variables, functions, and applications:

Name	Syntax	Explanation
Variable	x	a variable named x
Function	λx.y	a function with parameter x and body y
Application	(λx.y)a	calling the function λx.y with argument a

In templates calculus this would look like this:

Name	Syntax	Explanation
Variable	T	a variable named T
Function	template<typename T> struct f { using type = U; }	a function with parameter T and body U
Application	f<X>::type	calling the function f with argument X

The most basic function is the identity function: λx.x which is equivalent to f(x) = x. The first x is the function’s argument, and the second is the body of the function. In templates this looks as following:

template<typename T> identity { using type = T; };

The notions of free and bound variables in templates calculus is identical to lambda calculus. Evaluation in templates calculus is delegated to C++ compiler templates solver.

Currying

Lambda calculus traditionally supports only single parameter functions, we can create multi-parameter functions using a technique called currying, which simply points to the following property:

λxyz ≡ λx.λy.λz

Which is a fancy way of saying that a function of N arguments can be replaced with a function of 1 argument returning a function of 1 argument and so forth. C++ is somewhat rigid in its syntax, so let’s start small and curry a function of 2 arguments first:

template<template<typename, typename> typename F>
struct curry {
  template<typename T> struct _1 {

    template<typename U> struct _2 {
      using type = typename P<T, U>::type;
    };

    template<typename U> using type = _2<U>;
  };

  template<typename T> using type = _1<T>;
};

What happens here is that struct curry declares an inner class _1 containing another inner class _2, specialising the original T and U template arguments respectively. Notice that instead of naming those inner types simply as type they have different names. This is because C++ does not allow nested types having the same names as the enclosing types. But it is perfectly fine with type alias having the same name. Go figure. This struct curry can be used like this:

struct Jupiter, Thebe, Io, Europa

template<class T, class U> struct product { using type = std::tuple<T, U>; };

// result is list<std::tuple<Jupiter, Thebe>,
//                std::tuple<Jupiter, Io>,
//                std::tuple<Jupiter, Europa>>
map<curry<product>::type<Jupiter>::type, list<Thebe, Io, Europa>>;

You can see that with currying it is possible to use all the functions from the previous article like map or filter, passing in functions of any arity, by partially applying to them already known values. To curry functions of more than 2 arguments you would have to create curry template structs for the required arity, as it was shown previously.

Arithmetic

Before we start doing arithmetic with templates calculus we need to defined what numbers are. Recall that there are no numbers in lambda calculus, just functions, same goes for templates calculus. But there is a way to encode natural numbers using Church encoding with higher-order functions. The idea behind the encoding is remarkably simple, any natural numbers is equivalent to the number of function f applications, for instance this is zero:

λfz.z // same as λf.(λz.z)

Here, zero is a function that accepts another function and something else, and evaluates to that something else. This is zero because function f was applied 0 times. This is how numerals from 1 to 3 would look like:

λfz.f(z)        // 1, because f is applied once
λfz.f(f(z))     // 2, because f is applied twice
λfz.f(f(f(z)))  // 3, because f is applied three times

In templates calculus the same can be expressed the following way:

template<template<typename> typename F, typename Z>
struct _0 { using type = Z; };

template<template<typename> typename F, typename Z>
struct _1 { using type = typename F<Z>::type; };

template<template<typename> typename F, typename Z>
struct _2 { using type = typename F<typename F<Z>::type>::type; };

template<template<typename> typename F, typename Z>
struct _3 { using type = typename F<typename F<typename F<Z>::type>::type>::type; };

Successors

Defining numbers as described above is somewhat verbose in both calculi, so we need to create a bit more machinery. What about a successor function, a function that takes a number and evaluates to a number that immediately follows it. Lambda calculus:

λwyx.y(wyx)

If you apply this function to the zero function you will get the following:

(λwyx.y(wyx))(λsz.z) = λyx.y((λsz.z)yx) = λyx.y((λz.z)x) = λyx.y(x) ≡ 1

And if you mentally rename y to f and x to z in the resulting function you will see that it is equivalent to the function 1. In templates calculus the successor function is:

template<template<template<typename> typename, typename> typename W>
struct successor {
  template<template<typename> typename Y, typename X> using type = F<W<F,Z>>;
};

The numerals from 0 to 3 are written this way:

template<template<typename> typename F, typename Z> using _0 = Z;
template<template<typename> typename F, typename Z> using _1 = successor<_0>::type<F,Z>;
template<template<typename> typename F, typename Z> using _2 = successor<_1>::type<F,Z>;
template<template<typename> typename F, typename Z> using _3 = successor<_3>::type<F,Z>;

Verifying this result is somewhat difficult, since you need a decoder for Church numerals to convert them into Arabic decimal numerals. You can use this C++ counter trick:

template<typename T> struct counter {

 using type = T;

 static constexpr int value () {
   if constexpr (std::is_same_v<void, T) { return 1; }
   else { return T::value() + 1; }
 }
};

// prints 3
std::cout << _3<counter, void>::value() << std::endl;

Addition

Let’s say we want to add 2 and 3. Within our current model the result of this computation would be invoking successor function 2 times over function 3. In lambda calculus this expression is as follows:

(λfz.f(fz))(λwyx.y(wyx))(λgv.g(g(gv)))

    2        successor      3

By substituting all occurrences of f with successor and z with function 3 we get:

(λwyx.y(wyx)) ( (λwyx.y(wyx)) (λgv.g(g(gv))) )

   successor      successor         3

Unfortunately the following won’t work in C++, because a templates calculus numeral expects a function of one template template argument, but successor single argument is of much more complex template layout:

// error: template template argument has different template parameters
          than its corresponding template template parameter
_2<successor, _3>;

Luckily there is another way. If you look at the numerals’ signatures you will see that the second parameter is called Z and it kinda means zero, so if you place other numeral there you would get addition:

template<template<typename> typename F, typename Z> using _5 = _2<F, _3<F,Z>>;

To generalise a bit more:

template<template<template<typename> typename, typename> typename L,
         template<template<typename> typename, typename> typename R>
struct add {
  template<template<typename> typename F, typename Z> using type = L<F, R<F,Z>>;
};

template<template<typename> typename F, typename Z> using _5 = add<_2,_3>::type<F,Z>;

Multiplication

Multiplication can be done in the same vein as the addition:

template<template<template<typename> typename, typename> typename L,
         template<template<typename> typename, typename> typename R>
struct multiply {
  template<template<typename> typename F, typename Z>
  using type = L<R, Z>;
};

But this won’t compile because numerals expect two arguments, and the first argument is a function of one argument, which means you cannot simply pass numeral to a numeral as argument. This is where we need to use currying, though the function described above won’t fit here, we need to make it work for template template parameters:

template<template<template<typename> typename, typename> typename F>
struct curry {
  template<template<typename> typename T> struct _1 {

    template<typename U> struct _2 {
      using type = F<T, U>;
    };

    template<typename U> using type = typename _2<U>::type;
  };

  template<template<typename> typename T> using type = _1<T>;
};

And finally multiplication looks like this:

template<template<template<typename> typename, typename> typename L,
         template<template<typename> typename, typename> typename R>
struct multiply {
  template<template<typename> typename F, typename Z>
  using type = L<curry<R>::template type<F>::template type, Z>;
};

template<template<typename> typename F, typename Z>
using _21 = multiply<_3, _7>::type<F, Z>;

Phew, that’s a lot of templates. Next time I might elaborate on conditionals, recursions, data-structures and so forth. Till the next time, cheers!

Do C++ templates dream of Lisp?

2020-10-16T00:00:00+00:00

Imagine a Lisp embedded in C++. What kind of possibilities this would unlock? Fluid syntax and semantics, code is data and data is code. Read–eval–print loop for fast, iterative development. An omnipotent macro system to push the language to its limits. When you program in this environment, it is like you are talking directly to compiler. All your S-expressions neatly translate into AST. All the power of Lisp is under your fingertips! Then, why not just use Lisp, without C++?..

There is a reason why C++ is the language of choice for many software engineers, and not Lisp. They want speed. They want to feel the wind blowing through their hair, how fast a program written in C++ can run. There is absolutely no competition here for C++, in terms of performance and expressiveness. There is no need even to look in the direction of Lisp for a C++ engineer. Unless you consider templates.

Hardly anyone sees that dormant functional power in the meta language of the wicked. The templates can indeed be considered a separate language from C++, evaluated at compile-time, instead of runtime. They have no side-effects. Any function you write with templates is pure. This language of course lacks io to make it useful, it is too pure. But the main drawback, many people would agree, is its expressiveness, or rather the lack of it. One way to fix this is to fork a C++ compiler, for instance Clang, and modify the templates syntax, and maybe semantics, to your taste. This could work, except that this is not very portable. Only you and a couple of your friends can enjoy this new C++. There is another path, and this path is full of lists.

So, C++ templates and Lisp, let’s see. The basic building blocks of any lisp is two things: atoms and lists. Templates mainly operate on types, so for simplicity sake let us use type atoms. The list then looks like this:

template<typename... Ts> struct list {};

To manipulate lists we need some functions. The most basic LISP functions you can find are car and cdr. With a bit of renaming we have the following:

// first
template<typename T, typename... Ts>
constexpr auto first_impl(list<T, Ts...>) -> T;

template<typename L>
using first = decltype(first_impl(L{}));

// tail
template<typename T, typename... Ts>
constexpr auto tail_impl(list<T, Ts...>) -> list<Ts...>;

template<typename L>
using tail = decltype(tail_impl<>(L{}));

With only these two functions you already can freely manipulate lists of types. How about type maps:

// map
template<template<typename> typename F, typename... Ts>
constexpr auto map_impl(list<Ts...>) -> list<typename F<Ts>::type...>;

template<template<typename> typename F, typename L>
using map = decltype(map_impl<F>(L{}));

This one is a bit tougher to digest, but the semantics is quite straightforward, this function applies a function F over all elements of list L and returns a new list with the results. For example to const all types you would do the following:

struct Deckard, Batty, Bryant, Chew, Gaff;

// result is list<const Deckard, const Batty, const Bryant, const Chew, const Gaff>
map<std::add_const, list<Deckard, Batty, Bryant, Chew, Gaff>>;

Existing C++ type traits are perfectly fine with such treatment. Now you can map any trait over any list of types in one go. In the same vein we can implement filtering:

// tuple
template<typename... Ts> constexpr
bool is_tuple = false;

template<typename... Ts> constexpr
bool is_tuple<std::tuple<Ts...>> = true;

template<typename... Ts>
constexpr auto to_list_impl(std::tuple<Ts...>) -> list<Ts...>;

template<typename T, typename = std::enable_if_t<is_tuple<T>>>
using to_list = decltype(to_list_impl(T{}));

// filter
template<template<typename> typename P, typename... Ts>
constexpr auto filter_impl(list<Ts...>)
  -> to_list<decltype(std::tuple_cat(std::conditional_t<P<Ts>::value,
                                     std::tuple<Ts>,
                                     std::tuple<>>{}...))>;

template<template<typename> typename P, typename L>
using filter = decltype(filter_impl<P>(L{}));

To save some space and time we used std::tuple to deal with holes in the output list. Nevertheless, the resulting function allows us once again use some of the C++ type traits to filter list of types:

struct Holden, Leon, Taffey;

// result is list<const Leon>
filter<std::is_const, list<Holden, const Leon, Taffey>>;

In this example we deviate from the classic predicate implementation. In Lisp, predicates are functions that test their arguments for some specific conditions and returns nil if the condition is false, or some non-nil value is the condition is true. In C++ type trait predicates do not work like that, they are usually implemented as a type wrapper around a bool value. This is perfectly fine for filtering, but if you want to use these predicates with the map function, you would want to consider wrapping those bools in nil and non-nil. Nil by the way can be implemented like this:

using nil = list<>

With these basics techniques you can already start building up your own templates lisp, and try writing more complex type transformations. This comes in handy when you have to create elaborate data-structures, like maps of maps of tuples of vectors with a specific layout. This way your data-structure layout becomes a function, and the arguments to this function are map key types, value types and so on.

That’s all for today folks. In the following articles I will touch more on functional programming with C++ templates. Stay tuned.