Fixed-point Combinators, Tying the Recursive Knot, and Recursive Lambda Expressions
In Lambda Calculus, we cannot refer to the Lambda Abstraction itself within a Lambda Abstraction. Similarly, C++ does not allow defining a recursive lambda expression. Thus, we cannot straightforwardly implement recursion.
A workaround for this is to define a lambda expression that:
Add an additional first parameter to the lambda expression.
Call that additional first parameter inside the lambda expression at each recursive call site.
Such an additional first parameter should have the value of a yet-unknown hypothetical recursive function. Thus, we should use auto to represent its type. Using auto in a lambda expression's parameter list requires C++14 or above.
For example, we can define the following lambda expression to calculate the nth Fibonacci Number recursively:
1 2 3 4 5 6 7 8 9 10
auto fib = []( auto recursive_fib, unsignedint n ) -> unsignedlong { if (n == 0) return0UL; else { if (n == 1) return1UL; elsereturnrecursive_fib(n - 1) + recursive_fib(n - 2); } };
After defining such a lambda expression, we can use a Fixed-point Combinator to tie the recursive knot and return a new recursive function without the additional first parameter.
What is a Fixed-Point Combinator?
In mathematics, a fixed-point for function \(f\) refers to an element \(x\) that is mapped to itself by the function, i.e., \(x = f(x)\). For example, given \(f(x)=x^{2}-3x+4\), then \(2\) is a fixed point of \(f\), because \(f(2) = 2\).
A combinator is a function that operates on a function (i.e., a higher-order function).
A fixed-point combinatorg for function f satisfies g(f)(...) = f(g(f), ...). This is reminiscent of the form \(x = f(x)\) for fixed points in mathematics, and g(f) can be seen as a fixed-point of function f.
This implies that a fixed-point combinator g, when called on f, returns a new function (the g(f) above), that, when called with parameters ..., is equivalent to directly calling f with both g(f) and .... This means that a fixed-point combinator returns a new recursive function without the additional first parameter of f.
This is done by tying the recursive knot of f. Tying the recursive knot refers to, for such a previously defined lambda expression f, passing a function that represents the hypothetical recursive function, which in this case is g(f), to its first parameter.
We can implement fixed-point combinators in C++ using the following struct, whose instance represents g(f) and contains an operator() method, in which can use this to self-reference to g(f), allowing us to support f(g(f), ...):
R operator()(Args... args)const{ returnf(*this, args...); } };
auto fib = []( auto recursive_fib, unsignedint n ) -> unsignedlong { if (n == 0) return0UL; else { if (n == 1) return1UL; elsereturnrecursive_fib(n - 1) + recursive_fib(n - 2); } };
intmain(){ auto fib_ = FixedPointCombinator<decltype(fib), unsignedlong, unsignedint> {fib};
unsignedint input; scanf("%u", &input);
unsignedlong result = fib_(input); printf("%lu\n", result);
return0; }
compiles to the following LLVM IR under clang++ -std=c++14 -O2 -S -emit-llvm, in which FixedPointCombinator<decltype(fib), unsigned long, unsigned int> {fib} has been optimized to the recursive function @_ZNK3$_0clI20FixedPointCombinatorIS_mJjEEEEmT_j:
!0= !{i321, !"wchar_size",i324} !1= !{!"clang version 9.0.1 (https://github.com/conda-forge/clangdev-feedstock 2ea3b72da24769de0dfc6dac99251a5d7a46144d)"} !2= !{!3,!3,i640} !3= !{!"int",!4,i640} !4= !{!"omnipotent char",!5,i640} !5= !{!"Simple C++ TBAA"}
We can slightly modify the code above to support a fixed-point combinator that also provides memoization. Note that the instance of the fixed-point combinator is now stateful, and we should pass it by reference to fib (i.e., change the first parameter of fib to reference type):
R operator()(Args... args){ std::tuple<Args...> args_tuple(args...);
// Check if result is in the memoization map auto found = memo.find(args_tuple); if (found != memo.end()) { return found->second; // Return the cached result }
// Otherwise, compute and store the result R result = f(*this, args...); memo[args_tuple] = result; return result; } };
auto fib = []( auto& recursive_fib, unsignedint n ) -> unsignedlong { if (n == 0) return0UL; else { if (n == 1) return1UL; elsereturnrecursive_fib(n - 1) + recursive_fib(n - 2); } };
intmain(){ auto fib_ = FixedPointCombinatorWithMemoization<decltype(fib), unsignedlong, unsignedint> {fib};
unsignedint input; scanf("%u", &input);
unsignedlong result = fib_(input); printf("%lu\n", result);
return0; }
Type Abstractions and Template Functions
Polymorphic Lambda Calculus (also known as Second Order Lambda Calculus or System F) introduces Type Abstractions and Type Applications.
A Type Abstraction, written as λ X . t, represents a Term (often a Lambda Abstraction) t containing a Type Variable X.
A Type Application, written as t [T], uses a Concrete Type T to replace all instances of the Type Variable in the Term of the Type Abstraction.
This can be used to implement Polymorphic Lambda Abstractions.
For example, the following Type Abstraction representing a Polymorphic Identity Function:
1
id = λ X . λ x: X . x
can be instantiated to yield any concrete identity function that may be required, such as id [Nat]: Nat -> Nat.
Such Type Abstractions can be implemented in C++ using template functions:
1 2 3
template <typename X> autoid(X x){ return x; }
while Type Applications correspond to template instantiations:
1
id<int>
Should the template function be passed a callable, we usually want to use a template typename to support functions, function pointers, functors, and lambda expressions. Alternatively, we can also use auto to represent its type in the template function's parameter list. Note that using auto in a (non-lambda expression) function's parameter list requires C++20 or above.
For example, the following Type Abstraction:
1
double = λ X . λ f: X -> X . λ a: X . f(f a)
can be represented using the following template function:
1 2 3 4 5
template <typename X, typename F> autodouble_(const F f){ return [f](X a) { returnf(f(a)); }; }
C++ compilers support aggressive inlining optimizations when lambda expressions are used. For example, the call to const auto g = double_<int>([](int x) { return 2 * x; }); in the following source code:
Template Metaprogramming in C++ had been untyped, with template parameters being generic type variables substituted at template instantiation.
In C++20, a type system has been added to this untyped template language through concepts. They are Boolean predicates on template parameters evaluated at the point of, not after, template instantiation. The compiler will produce a clear error immediately if a programmer tries to use a template parameter that doesn't meet the requirements of a concept.
This starkly contrasts the challenging-to-grasp errors reported after an invalid type substitutes a generic type variable emanating from the implementation context rather than the template instantiation itself.
For instance, the first two arguments to std::sort must be random-access iterators. If an argument is not a random-access iterator, an error will occur when std::sort attempts to use it as a bidirectional iterator.
1 2
std::list<int> l = {2, 1, 3}; std::sort(l.begin(), l.end());
Without concepts, compilers may produce large amounts of error information, starting with an equation that failed to compile when it tried to subtract two non-random-access iterators:
1 2 3
In instantiation of 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare)[with_RandomAccessIterator = std::_List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]': error: no matchfor 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>') std::__lg(__last - __first) * 2,
However, if concepts are used, the problem can be found and reported at template instantiation:
1 2
error: cannot call function 'void std::sort(_RAIter, _RAIter) [with _RAIter = std::_List_iterator<int>]' note: concept 'RandomAccessIterator()' was not satisfied
It is straightforward to implement Type Classes with concepts. For instance, the Type Class below specifies the equal (==) operations for Type Constructors that are its instances:
1 2
classEq a where (==) :: a -> a -> Bool
This can be implemented using the following C++ concept:
1 2 3 4 5 6 7 8 9
#include<concepts>
// Declaration of the concept "Eq", // which is satisfied by any type 'T' such that for values 't' of type 'T', the expression t == t compiles and its type satisfies the concept std::same_as<bool> // This is represented using a "requires expression" which returns a bool template <typename T> concept Eq = requires (T t) { { t == t } -> std::same_as<bool>; };
Afterwards, such a concept can be specified when template parameters are being introduced in a template definition, to indicate that the corresponding template parameter must satisfy the concept.