Functions

Since functional programming (FP) is the focus, let’s explore the most essential functions. We’ll be dealing with pure functions, first-class functions, and anonymous functions. These concepts are closely related to the stack which stores function control contexts.

Pure functions

All functions in FP are pure functions. Therefore, every function discussed below is pure. The most beneficial aspects of FP, such as concurrency and predictability, derive from these pure functions.

A fully deterministic program is realistically impossible because I/O is indeterministic. However, pure functions in FP have no side effects, like accessing global variables. Consequently, they benefit concurrency and unit testing because there are no shared resources.

The benefits of pure functions for concurrent programming are not automatic. The higher the linearizability of a function—meaning it can be composed of code segments that can be executed independently without data dependencies—the better. We should remove dependencies not only on global data by using pure functions but also within the inner code of those functions as much as possible. In fact, (tail) recursive functions are favored for this reason: they minimize dependencies in loops. This kind of dependency reduction is necessary for superscalar processors.

In C++, we can create pure functions by adding the const qualifier to member functions. Additionally, types in function signatures should be declared as constants. Let’s pay attention to constant parameters in function arguments, as they do not help with optimization. Const-qualification can help with optimization only in declarations or by extending temporary object lifetimes.

auto func(const auto in) const{
	// do
}

Types

Static type systems are beneficial for FP. It’s extremely difficult to evaluate the equality of functions, but type equivalence and inclusion relationships are relatively easy. So, using categories named traits or type classes can explicitly and rigorously ensure the composition of functions. Explicitness is very important because we expect consistent results when using FP.

Forms of polymorphism include the following: subtype polymorphism, generally called inheritance; coercion polymorphism, sometimes called implicit type casting; parametric polymorphism, called generics or in C++ templates; and others. Dynamic type casting occurs at runtime and impacts immutability. We should also avoid implicit casting to prevent unexpected results. However, template type inferences occur at compile-time.

C++ has implicit casting, a legacy from C. In a strict sense, C++ is not a strongly typed language. If possible, use explicit casting such as static_cast. For classes, you can add the explicit keyword to avoid implicit casting.

class c {
public:
  explicit c() = default;
};

First-class functions

If functions can be passed as values, they are called first-class functions. First-class functions can be passed as arguments to other functions, and functions that receive functions as arguments are called higher-order functions. However, the linearity of a call stack interferes with implementation because first-class functions are non-linear types.

Let’s assume the function exists at the top of the stack. Accessing the previous stack frame is an undefined behavior after returning. Therefore, first-class functions are dynamically allocated on the heap at runtime. However, the lifetime of an allocated first-class function is empirically short. Allocating and freeing such a function each time is inefficient, considering the allocation overhead for a short-lived function. So, it’s common to use arena allocation with GC. This problem is known as the funarg problem.

Lazy computation

Why is lazy computation key to FP? One reason is optimization. FP programs often utilize (tail) recursive functions for reduced side effects and increased simplicity. However, large data structures generated by these methods are rarely used immediately. So, it is more efficient to compute data only when needed. In other words, lazy computation prevents speculative execution. For example, in f(a, b), instead of computing both a and b, we can compute only the necessary expression. The lower the computation cost, the less efficient lazy computation becomes. Additionally, lazy computation requires functions to be pure.

Lazy computation can be generalized to coroutines. Programming languages with language-level support for lazy computation can use stackless coroutines without explicit coroutine support. There are advantages to expressing infinite data structures, which are effectively utilized in scientific applications. Further, lazy computation is helpful even when returning a bottom type.

Let’s delve deeper. Most CPUs on the market have more than one physical core. In an era where asynchronous programming is becoming increasingly important, lazy computation concepts combined with transactional memory are moving toward software transactional memory as valuable primitives. Software transactional memory enables simply structured multicore programming through speculative execution, similar to a seqlock.

Based on the explanation so far, FP might seem inefficient. Indeed, FP prioritizes productivity over efficiency. This is expected because microprocessors are optimized for C-like languages. (All CPU manufacturers have been providing at least a C compiler.) Consequently, FP has only recently become popular as hardware has improved. Unfortunately, FP is generally unsuitable for embedded systems due to its unpredictable runtime memory footprint, except for some FP languages that adopt linear types.

Implementation

In C++, functions are not first-class objects. Therefore, we use the std::function container. Below is an example of the std::function implementation from Clang. If functions are reachable at compile-time, we can use move semantics (std::move) for perfect forwarding. However, this approach can be puzzling. Also, guaranteeing type safety requires unnecessarily complex template metaprogramming. (This implementation roughly uses currying to achieve type safety.) However, most compilers perform highly optimizations with constant folding, a type of partial evaluation, without an r-value reference.

template <class _Rp, class... _ArgTypes>
template <class _Fp, class>
function<_Rp(_ArgTypes...)>::function(_Fp __f) : __f_(std::move(__f)) {}

...

template <class _Rp, class... _ArgTypes>
class __value_func<_Rp(_ArgTypes...)> {
  typename aligned_storage<3 * sizeof(void*)>::type __buf_;

  typedef __base<_Rp(_ArgTypes...)> __func;
  __func* __f_;
}

The best application of first-class objects is higher-order functions. Higher-order functions are necessary for implementing the core idea of a monad; assigning how to apply to the monad and how to compute to the caller. Simple forms of higher-order functions are shown below.

import std;

auto time(auto func, std::unsigned_integral auto num) {
  std::chrono::steady_clock::time_point
      begin = std::chrono::steady_clock::now();

  for (auto i = 0u; i < num; ++i) {
    func();
  }

  std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::microseconds>(
      end - begin).count();
  std::cout << "END\n"
            << std::format("time: {}ms", duration)
            << std::endl;
}

...

time([&] {
    // do
  }, 10000u);

Anonymous functions

All functions are anonymous. Unless symbols are exported for linking, subroutines are just code snippets comprising a prologue and an epilogue. Therefore, the features of anonymous functions are unsurprising.

add(int, int):
        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 4], edi
        mov     dword ptr [rbp - 8], esi
        mov     eax, dword ptr [rbp - 4]
        add     eax, dword ptr [rbp - 8]
        pop     rbp
        ret

There are many problems when anonymous functions refer to outer-scope objects. For example, using temporary objects or objects that are destroyed before anonymous function execution. To prevent this, referencing or copying enclosed scope objects bound with a function is called capture, and anonymous functions with a capture feature are called closures.

If functions are first-class objects, anonymous functions are purely syntactic sugar. They are helpful not only for simple computations such as basic operations in a higher-order function, simplifying syntax but also for lazy computation used to capture different values to improve code reusability. However, pay attention to readability issues known as “callback hell”.

In C++, templates can be used in lambdas. Alternatively, using auto in arguments acts like syntactic sugar. It’s interpreted roughly as generating an implicit template<typename T>. auto can also use concepts, similar to templates, by adding a type constraint before the auto keyword.

  [&] (auto in){
    // do
  }