SciTech.blog

# Fixpoints of functions in Python and C++

27 Sep 2017, 10:07 • c++, python

The fixpoint operator ($$\mu$$) on functions provides a way of converting nonrecursive functions into recursive ones. Let's learn how to implement it in Python and C++.

A fixpoint of a mapping $$\phi$$ is an $$x$$ such that $$\phi(x)=x$$. Consider the following function:

$f(g,x) = \begin{cases} 1 & \text{for } x \leqslant 1 \\ x \cdot g(x-1) & \text{for } x>1 \end{cases}$

If we restrict ourselves to $$\mathbb{N}$$, $$f$$ is of type $$(\mathbb{N} \rightarrow \mathbb{N}) \times \mathbb{N} \rightarrow \mathbb{N}$$, which can be also thought of as $$(\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})$$:

$f(g) = \begin{cases} 1 & \text{for } x \leqslant 1 \\ \lambda x . x \cdot g(x-1) & \text{for } x>1 \end{cases}$

Viewed thus, $$f$$ is an endofunction, so we can try to get its (least) fixpoint, $$\mu f$$ (hence $$\mu f=f(\mu f)$$). Note that what we get is the factorial:

$\mu f(x)=x!$

It's very easy to implement $$\mu$$ in Python:

def fact_(x, f):
if x <= 1:
return 1
else:
return x * f(x-1)

def fix(f):
return lambda x: f(x, fix(f))

fact = fix(fact_)
print(fact(5))


Since Python is dynamically typed, there are no type declarations in the code. We simply return a $$\lambda$$-function which applies $$f$$ to $$x$$ and itself.

However, in C++ we'd run into difficulties because the definition of fix is self-referencing (Python is dynamic so it doesn't matter there). What we need to do is define a callable class. The () operator can then refer to the fixpoint itself as follows:

template<typename T> class Fix {
std::function<T(const T&, const std::function<T(T)>&)> f;
public:
Fix(const std::function<T(const T&, const std::function<T(T)>&)>& _f) : f(_f) {}
T operator()(T x) const {
return f(x, *this);
}
};

int fact_(int x, const std::function<int(int)>& f) {
return x <=1 ? 1 : x * f(x - 1);
}

const auto& fact = Fix<int>(factF);
std::cout << fact(5) << std::endl;


Note that since Fix is a class, we can use f(x, *this).

Comments

Name: