Applying Purity To The Imperative World

Programming
Part of the BlogBook: Functional Programming Lessons in Imperative Code
Page content

One of the distinguishing features of functional programming is an emphasis on pure functions. I will start with an initial sloppy definition of purity to get us started, and will refine it into a range of definitions later. If you don’t like this first one, bear with me.

For now we’ll go with, a pure function is a function that considers only its inputs or immutable external values, makes no changes to any other values, and returns the same result given the same parameters every time. I add the consulting external values because in the case of

data Color = RGB Int Int Int deriving Show

red = RGB 255 0 0

maskRed :: Color -> Color
maskRed (RGB rIn gIn bIn) =
    let (RGB rMask gMask bMask) = red
    in RGB (min rIn rMask) (min gIn gMask) (min bIn bMask)

even if red is in some external module, since it is immutable maskRed will still be a pure function. Immutability renders that distinction irrelevant in Haskell, because you can term-rewrite an external term to simply become part of the function transparently. In imperative languages a function may incorporate references to mutable values so that is not automatically a safe assumption.

You can in principle program an imperative language purely, producing something similar to the style you’d produce in Haskell. But it is painful… to put it lightly. Haskell has a lot of affordances for programming with very small-scale pure functions. Your imperative language does not. If you try to introduce them, they will be klunkier. It can be easy to take Haskell’s space-based syntax for granted and miss just how many parentheses it elides compared to almost every other language’s syntax expressing an equivalent thing. Trying to copy Haskell produces an explosion of functions and parentheses everywhere.

And that’s also before we even consider the fact that nearly every library you use in an imperative langauge is not pure, requiring you to jump through hoops to isolate it into a pure value, if it is even possible.

If you try to carry Haskell’s highly granular function style into an imperative language, you will experience a lot of pain, while not experiencing a lot of the benefits. The details and resulting cost/benefit ratio will vary from language to language, but it is not what they are meant to do. In fact I’ve seen very few people try it online, one imagines they get broken of it fairly quickly.

So why am I talking about this if we can’t program this way in our imperative languages?

Well, in one of the statements that I know from experience will now cheese off some of the purest functional advocates…

Purity Is Relative

Another way of expressing the idea of purity is that pure code has no “effects”, though in this context that just moves the question into “ok, well, what is an ’effect’ then?”

Again I will not try to create a universally-agreed upon definition, but call it “a change in the environment that can be witnessed by other code”. By “other code” here we generally mean “code written in the subset of the language defined as ‘safe’ by the language designers”. We say this because if we declare that any unsafety in the language renders the language 100% unsafe and all 100% unsafe languages are therefore equally unsafe with no distinctions, then there is no debate to be had; all languages are completely unsafe. While there may be a mathematical sense in which this is true, it is not a practically useful definition.

In Haskell, it is trivial to make a “pure function” that will crash the process if evaluated fully. Evaluating an infinite list while retaining its head, resulting in Haskell trying and failing to manifest the entire infinite list in RAM is “pure”, that is, evaluating an infinite list is not considered an “effect”. It is hard to handle that as an “effect”; it is trivially a Turing-complete thing to know about a function in advance. Fortunately, we can get a long way on modern computers by just sort of closing our eyes and pretending that’s not an “effect” a computation can have on an OS process, even though “killing every other currently-running computation in the program” is almost the epitome of a witnessable “effect”; other computations will be forced to witness this effect, unless you want to get pedantic about computations that no longer exist being unable to witness anything.

But I am not criticizing Haskell not considering that an effect. It is a choice so practical that it is all but forced on them. Few languages have a useful capacity to deal with out-of-memory issues at all, especially if we ignore “run the GC and hope for the best” as a solution; even fewer can do it well.

Furthermore, real processors are mutable at their core. CPU registers are fundamentally mutable. Memory is fundamentally mutable. Any pure computation you like will inevitably have effects viewable by a debugger, even if there is no way to view them from within the safe subset of the language.

Again, this is not a criticism of the concept. But it does mean that even in Haskell the concept already is relative to your definition of what exactly constitutes an “effect”. We already can’t call any non-trivial Haskell function “pure” if we consider it as mutating CPU registers and RAM or if we consider it relative to what a debugger can witness.

So, in light of that discussion of purity and “effects”, consider this Go code:

type WebpageFetcher interface {
	FetchPage(url string) (contents string, err error)
}

func Tail10(fetcher WebpageFetcher, url string) string {
	page, err := fetcher.FetchPage(url)
	if err != nil {
		return ""
	}
	if len(page) < 10 {
		return page
	}
	return page[len(page)-10:]
}

Is Tail10 a pure function?

The obvious answer is “no”. Fetching a web page is not only an “effect”, it’s a huge set of effects. Sockets opened, packets sent and received, and at the end of that, any arbitrary content could be returned every time it is called because the target webpage need not be constant itself. (And all of that just to throw it all away except the last ten bytes…) It couldn’t be less pure.

The obvious answer is wrong. The correct answer is “insufficient information”.

Consider an implementation of WebpageFetcher:

type TestWeb map[string]string

func (tw TestWeb) FetchPage(url string) (string, error) {
	return tw[url], nil
}

And a call to Tail10 in the test code as such:

func TestTail10(t *testing.T) {
	url := "https://jerf.org/test"
	web := TestWeb{
		url: "more than ten chars content",
	}
	if Tail10(web, url) != "rs content" {
		t.Fatal("Tail10 is not working correctly")
	}
}

This particular invocation of Tail10 is pure. You can’t label a map as immutable in Go, but by inspection we can see it will never mutate it. Two values are passed in to this function, which could without loss be marked as “immutable” in a hypothetical version of Go which supported that, and the code would still run, and have no witnessable effects because it returns an entirely new value.

Of course, if you pass it a more natural implementation of a WebpageFetcher that in fact did reach out to the web, the function would be blatently impure.

In this particular case, the Tail10 function returned a new value. If the “business logic” was expected to reach out and perform some action that would mutate state, like, say, writing to an S3 bucket, you can write an implementation of the interface that records the action in itself. In this case, that implementation is being mutated as a result of the business logic, but this mutation is confined to the implementation of that object, which is only being used for testing. While it may technically be “mutation” as far as Haskell is concerned, there is still a clean boundary you can draw around the mutation to know it doesn’t escape out into your code in the case of testing code.

FP “Pure Core” -> Imperative “Purifiable Core”

Many Haskell writers have observed that a well-factored Haskell program is strongly drawn to an overall architecture that has a “pure core” and some sort of IO shell around it to do whatever the program is supposed to do in the real world. This happen in Haskell because the language is so good at dealing with that pure core that it strongly affords a style in which you move as much of the program into it as possible.

Imperative languages can not directly apply this concept very well because that fluidity of dealing with pure code at the smallest granularity is missing. But we can create packages (modules, whatever your language calls that level of architecture) that are purifiable.

This is now a routine play for me when I’m writing a program in an imperative language. Rather than intermixing all my “business logic” with all the impure code that gathers all the data for that business logic, I generally end up with these pieces:

  1. The business logic.
  2. An implementation of all the impure code in the module broken out into a class or local equivalent.
  3. An stubbed out implementation of that interface used for testing to turn the business logic into relatively pure code.
  4. A real implementation of the impure code.
  5. An “integration” test of the impure code. This is easier than setting up a full integration test of conventional imperative code that casually intermixes the logic and impure code. For instance, the business logic may read and write a number of S3 buckets with arbitrary logic done on the contents, but the impure code to read/write some S3 value in some particular way can be tested in isolation to do just the thing we expect.

This may seem like a lot more than just writing the code. It really isn’t a lot more. It’s mostly what you need to write to have minimally professional code anyhow, just with more structure than you may be used to. It is more, though, I can’t deny. However, it is in the range where if you save only one multi-hour debugging session brought on by complicated mixtures of business logic and impure code, it has already paid off. It also gets easier as you practice this style.

If you design your system with all this purifiable code from the beginning, it begins to compound. When you write a component that depends on three other purifiable subcomponents, the purified components of those three subcomponents can then become part of the purification system for this component.

This is going to be one of the major recurring themes in this series of posts. While imperative languages resist taking the purity down to the granularity that functional programming languages do at the small scale, you will find them much less resistent at medium scales. You will be going somewhat out of your way to program in a style that would likely not come naturally to someone who never stepped out of imperative languages, and it is still a bit more expensive in the short term than a “natural” imperative approach, but it amortizes much more nicely over a medium-sized chunk of code and in my experience almost immediately pays off when you are able to write better test cases. But even if you skip that, it pays off in the medium term anyhow.

Purifiable Code in Haskell

You can do something similar in Haskell; there is more than one way to do it, but free monads are the most similar to the approach I take in imperative code..

However, this is not commonly done. I think that’s probably because Haskell makes it easier to purify things to a much greater extent, plus the aforementioned “more than one way to do it”. Testing pure code is easy, and what is left is something that can generally be integration tested, plus the fact that the type system itself constitutes more testing than in imperative code.

Still, it is not unheard of in the functional world. Here’s an example of it. Note this uses ekmett’s free package for Control.Monad.Free, not control-monad-free.

{-# LANGUAGE DeriveFunctor #-}

module Tmp where

import Control.Monad.Free (Free(..), liftF)
import qualified Data.Map as Map

-- Build the API we want to define
data Fetcher next =
    FetchPage String (String -> next)
    deriving Functor

-- Some machinery to make it easier to use.
fetchPage :: String -> FetchProgram String
fetchPage url = liftF (FetchPage url id)
type FetchProgram = Free Fetcher

-- A simple program to fetch two web pages and do some
-- simple manipulation to them
program :: FetchProgram String
program = do
    p1 <- fetchPage "http://jerf.org"
    p2 <- fetchPage "http://jerf.org/iri"
    return $ take 12 p1 ++ take 12 p2

-- Define a fake web.
urlContents = Map.fromList [
          ("http://jerf.org", "a very good website"),
          ("http://jerf.org/iri", "a very good blog")]

-- Run 'program' completely purely. Note that for this
-- to type check, it is indeed rigidly required to be String.
testRunPure :: FetchProgram String -> String
testRunPure prog =
    case prog of
        Free (FetchPage url g) -> do
            let contents = Map.findWithDefault "" url urlContents
            testRunPure (g contents)
        Pure r -> r

-- Run 'program' but with an implementation that does
-- real IO. In the interests of not boring the reader,
-- this does not actually do fetching, but we print
-- some things to demonstrate that we are indeed in IO.
testRunIO :: FetchProgram String -> IO String
testRunIO prog =
    case prog of
        Free (FetchPage url g) -> do
            let contents = Map.findWithDefault "" url urlContents
            putStrLn $ "Contents of " ++ url ++ ": " ++ contents
            testRunIO (g contents)
        Pure r -> return r

We can interrogate this module to super-double confirm that the purity of program does indeed depend on which interpreter we use to run the program value:

ghci> :t testRunPure program
testRunPure program :: String
ghci> :t testRunIO program
testRunIO program :: IO String

I suspect a second reason Haskell programmers don’t use this very often is that this is actually a bit of a pain. Imperative code lacks the guarantee of purity, but it is easier to set this structure up in an imperative language. Anyone reading the imperative langauge will understand immediately what is happening with purifiable modules. They may not quite understand why you wrote it that way, and may try to “simplify” it out of existence (hopefully the great testing you wrote will talk them back out of it), but it won’t confuse them. This Haskell code works, but it’s a lot of machinery to achieve it, even by Haskell standards, so it’s not worth bringing it out if a conventional pure core does the job, which it usually does.