Category :

Functional Programming: Using Lazy Evaluation to Write More Modular Code

Many articles on Functional Programming claim that it makes code simpler and more maintainable, but the examples provided tend to either be too abstract or too difficult to understand if you don’t already know Functional concepts. This post provides a simple, specific example of how the concept of Lazy Evaluation lets you separate concerns and create modular code in a way that is very hard to do otherwise.

One common task in scientific computing is calculating numerical approximations to quantities that are hard to solve for exactly, such as complex integrals or square roots. This involves two related concepts: generating the next approximation, and figuring out when to stop. A standard, imperative solution has to entangle these concepts in one function. For example, one way to approximate an integral is to generate successive Riemann Sums until two approximations in a row fall are sufficiently close to each other:

Update: I’ve cleaned up the code below, removing a few bugs and adding some tests

The integrate function above intertwines the code to generate the next approximation and figure out when to stop, which results in several problems:

  • Testability: we can’t test the stopping criterion and the approximation separately–if either one is broken, it will result in incorrect code, and finding the source of the problem is more difficult.
  • Extensibility: if we want to change the stopping criterion to look at more elements, we have to rewrite a significant part of the implementation. If we want to extend this code to allow an arbitrary stopping criterion, then we need to save every estimate in memory until the code is finished executing, since we don’t know how many estimates will be needed.
  • Modification: similarly, changing our integral implementation to a more efficient algorithm such as Simpson’s rule would require also changing the stopping criterion and making sure nothing breaks
  • Reusability: we can’t easily reuse the stopping criterion for other approximation problems, such as calculating differential equations or square roots

So how can we solve these problems? Luckily Python has a concept called generators, which can basically let you create a list-like function that outputs its values only as they’re needed. For more on generators see here. This lets us rewrite the integrate function to separate concerns and produce more modular code:

This version solves all the problems listed above:

  • We can write separate unit tests for integrationGenerator and approximateUntilEstimatesWithin, which makes it easier to ensure correctness and debug any issues.
  • We can modify approximateUntilEstimatesWithin to a new criterion without needing to change anything about integrationGenerator. Whether we want to compare two estimates in a row or fifty, we don’t need any changes to integrationGenerator.
  • The integral implementation can be changed without needing to look at or consider the approximation criterion.
  • We can reuse approximateUntilEstimatesWithin on other problems. For example, here’s Newton’s method for square root approximations:
  • In particular, if we had 5 different approximations and 5 different stopping criteria, the new version lets us write 5 + 5 = 10 functions, while the previous version would have required 5*5 = 25 functions.

The interesting thing about the separation above is that this is only possible with lazy evaluation: without it, Python would attempt to evaluate an infinite number of successive approximations and crash.

This post was inspired by John Hughes’ Why Functional Programming Matters. If you liked it, check out the original paper!

Categories: Functional Programming, Productivity, Programming