FuPy: Functional Programming in Python

Warning: FuPy is a proof-of-concept experiment that got out of hand. It still has a couple of loose ends.

Overview

A functional program consists of a collection of function definitions. FuPy provides various function combinators, written as infix operators, to define functions as compositions of other functions, without having to apply them to arguments.

Such function combinators require functions to take one argument and produce one result. The former is not the case for all Python functions. For instance, f() takes no arguments and f(x, y) takes two arguments. By wrapping functions in the class Func, they are made composable and function arguments are automatically packed or unpacked as needed, to adhere to the one-argument regime. This class and various factory functions to produce such Func-wrapped functions are defined in FuPy.basics (see below).

Besides offering composable functions, there are three other features that make FuPy especially interesting for educational use:

• Func-wrapped functions, including FuPy lambda abstractions created by la, can be printed (converted to readable strings).

• Evaluation of expressions involving Func-wrapped functions can be traced, resulting in a sequence of intermediate expressions.

• Expression evaluation can be suspended through sharable lazy expressions with memoization (a.k.a. thunks). When evaluated, their result is cached, so that multiple evaluations of the same expression are avoided. Among other things, this allows for potentially infinite values, such as the list (stream) of all natural numbers. In most cases, FuPy handles suspension and resumption automatically. That is, FuPy is lazy. (In fact, a bit too lazy, so that you may need to call force to get the final result.)

The following sections include some examples. Also see demo.py.

Contents

• Basics

• Tracing

• Laziness

• Fixpoints

• Prelude

• Design Considerations

• Implementation Details

• Related Stuff

Notes

FuPy development history

When I wrote “Staying DRY with OO and FP” (IOI Journal, 2024), I needed a language to present some example code. I chose Python because it has some support for both OO and FP, and its syntax is reasonably simple (though its semantics isn’t always). Initially, I had the idea of adding a few basic features that I missed, such as the (polymorphic) identity function and an infix operator for function composition. For a moment, I even believed that someday these might be part of standard Python.

As I kept adding features to FuPy, it became clear that it would be hard to integrate these more deeply into the standard Python language. Thus, FuPy become more a Domain-Specific Language (DSL) hosted in Python. One of the lessons I learned is that it is hard to add the core FP concepts to Python (FP is a package deal: it doesn’t work well if only some features are available). For one thing, Python’s type system is too limited (lacking support for Higher-Kinded Types).

FuPy syntax and calculation

FuPy syntax may look cryptic (or even unreadable) because of its compact notation and unfamiliar building blocks. The main advantage of this syntax is that it is more suitable for calculations based on algebraic symbol manipulation. This allows one to calculate (from their specification) functional programs that are correct by construction. This documentation does not explain the calculational approach to program design. Three sources:

• The elective CS bachelor course Functional Programming (2IPH0) taught at Eindhoven University of Technology.

• Jeremy Gibbons, “Calculating Functional Programs”, Chapter 5 in Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, Lecture Notes in Computer Science, vol. 2297. Springer, pp. 151–203, 2002.

• José N. Oliveira, Program Design by Calculation, University of Minho, Portugal, 2023. (This book uses a slightly different mathematical notation.)

FuPy vs Haskell

The functional programming language Haskell mostly works with curried functions, whereas in the theory of functional programming, uncurried functions are often more convenient. Therefore, FuPy offers many uncurried functions, and easy ways of defining your own. FuPy did take some inspiration from Haskell (such as operator sections) and is not hard to translate to Haskell (in the future, we intend to support export to Haskell).

FuPy performance

Because everything is interpreted in FuPy, there is a (considerable) runtime and memory overhead. In compiled functional programming languages, like Haskell, a lot of this overhead is compiled away. In the future, we intend to support export to plain Python (where printability and traceability of functions are sacrificed in favor of performance).

FuPy and RecursionError

The limit on the recursion depth in Python can be obtained and set by

import sys

print(sys.getrecursionlimit())  # default (a few) 1000

sys.setrecursionlimit(...)

One needs to be careful when increasing the maximum recursion depth. In Python, deep recursions are not recommended (like processing a list of a million items recursively). One approach is to make the function tail recursive and employ laziness to do tail-call elimination (TCE).

FuPy and interoperability with Python

One can view FuPy as a Domain Specific Language (DSL) for functional programming, hosted in Python. Ideally, FuPy is used in isolation to work with (pure) functional programs. However, there is some interoperability with “full” Python:

• Python functions can be wrapped in Func to use them with FuPy.

• Values of types int, bool, str, float, and tuple can be used with most of their operators.
  Note that @ (matrix multiplication), & (bitwise AND), and | (bitwise OR) when used in operator sections only work with functions.

• Types int (restricted to non-negative values) and list can be treated as (co-)inductive types (see FuPy.prelude) through

  • in_nat, out_nat, cata_nat, ana_nat

  • in_list, out_list, cata_list, ana_list

FuPy and type hints

An attempt has been made to provide type hints in the source code. But due to limitations of the Python type system (such as the lack of support for Higher Kinded Types, not all type annotations can be verified by mypy.