# 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](../examples/demo.py). ## Contents * [Basics](basics.md) * [Tracing](tracing.md) * [Laziness](laziness.md) * [Fixpoints](fixpoints.md) * [Prelude](prelude.md) * [Design Considerations](design-considerations.md) * [Implementation Details](implementation.md) * [Related Stuff](related.md) ## 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_](https://tue.nl/). * 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_](http://www.di.uminho.pt/~jno/ps/pdbc.pdf), 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 ```python 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_](laziness.md#tail-recursion-and-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](basics.md#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`.