Discerning and maintaining purity by Mark Seemann
Functional programming depends on referential transparency, but identifying and keeping functions pure requires deliberate attention.
Referential transparency is the essence of functional programming. Most other traits that people associate with functional programming emerge from it: immutability, recursion, higher-order functions, functors and monads, etcetera.
To summarise, a pure function has to obey two rules:
- The same input always produces the same output.
- Calling it causes no side effects.
Lack of abstraction #
Mainstream programming languages don't distinguish between pure functions and impure actions. I'll use C# for examples, but you can draw the same conclusions for Java, C, C++, Visual Basic .NET and so on - even for F# and Clojure.
Consider this line of code:
string validationMsg = Validator.Validate(dto);
Is Validate a pure function?
You might want to look at the method signature before you answer:
public static string Validate(ReservationDto dto)
This is, unfortunately, not helpful. Will Validate always return the same string for the same dto? Can we guarantee that there's no side effects?
You can't answer these questions only by examining the method signature. You'll have to go and read the code.
This breaks encapsulation. It ruins abstraction. It makes code harder to maintain.
I can't stress this enough. This is what I've attempted to describe in my Humane Code video. We waste significant time reading existing code. Mostly because it's difficult to understand. It doesn't fit in our brains.
Agile Principles, Patterns, and Practices defines an abstraction as
This fits with the definition of encapsulation from Object-Oriented Software Construction. You should be able to interact with an object without knowledge of its implementation details."the amplification of the essential and the elimination of the irrelevant"
When you have to read the code of a method, it indicates a lack of abstraction and encapsulation. Unfortunately, that's the state of affairs when it comes to referential transparency in mainstream programming languages.
Manual analysis #
If you read the source code of the Validate method, however, it's easy to figure out whether it's pure:
public static string Validate(ReservationDto dto) { if (!DateTime.TryParse(dto.Date, out var _)) return $"Invalid date: {dto.Date}."; return ""; }
Is the method deterministic? It seems like it. In fact, in order to answer that question, you need to know if DateTime.TryParse is deterministic. Assume that it is. Apart from the TryParse call, you can easily reason about the rest of this method. There's no randomness or other sources of non-deterministic behaviour in the method, so it seems reasonable to conclude that it's deterministic.
Does the method produce side effects? Again, you have to know about the behaviour of DateTime.TryParse, but I think it's safe to conclude that there's no side effects.
In other words, Validate is a pure function.
Testability #
Pure functions are intrinsically testable because they depend exclusively on their input.
[Fact] public void ValidDate() { var dto = new ReservationDto { Date = "2021-12-21 19:00", Quantity = 2 }; var actual = Validator.Validate(dto); Assert.Empty(actual); }
This unit test creates a reservation Data Transfer Object (DTO) with a valid date string and a positive quantity. There's no error message to produce for a valid DTO. The test asserts that the error message is empty. It passes.
You can with similar ease write a test that verifies what happens if you supply an invalid Date string.
Maintaining purity #
The problem with manual analysis of purity is that any conclusion you reach only lasts until someone edits the code. Every time the code changes, you must re-evaluate.
Imagine that you need to add a new validation rule. The system shouldn't accept reservations in the past, so you edit the Validate method:
public static string Validate(ReservationDto dto) { if (!DateTime.TryParse(dto.Date, out var date)) return $"Invalid date: {dto.Date}."; if (date < DateTime.Now) return $"Invalid date: {dto.Date}."; return ""; }
Is the method still pure? No, it's not. It's now non-deterministic. One way to observe this is to let time pass. Assume that you wrote the above unit test well before December 21, 2021. That test still passes when you make the change, but months go by. One day (on December 21, 2021 at 19:00) the test starts failing. No code changed, but now you have a failing test.
I've made sure that the examples in this article are simple, so that they're easy to follow. This could mislead you to think that the shift from referential transparency to impurity isn't such a big deal. After all, the test is easy to read, and it's clear why it starts failing.
Imagine, however, that the code is as complex as the code base you work with professionally. A subtle change to a method deep in the bowels of a system can have profound impact on the entire architecture. You thought that you had a functional architecture, but you probably don't.
Notice that no types changed. The method signature remains the same. It's surprisingly difficult to maintain purity in a code base, even if you explicitly set out to do so. There's no poka-yoke here; constant vigilance is required.
Automation attempts #
When I explain these issues, people typically suggest some sort of annotation mechanism. Couldn't we use attributes to identify pure functions? Perhaps like this:
[Pure] public static string Validate(ReservationDto dto)
This doesn't solve the problem, though, because this still still compiles:
[Pure] public static string Validate(ReservationDto dto) { if (!DateTime.TryParse(dto.Date, out var date)) return $"Invalid date: {dto.Date}."; if (date < DateTime.Now) return $"Invalid date: {dto.Date}."; return ""; }
That's an impure action annotated with the [Pure] attribute. It still compiles and passes all tests (if you run them before December 21, 2021). The annotation is a lie.
As I've already implied, you also have the compound problem that you need to know the purity (or lack thereof) of all APIs from the base library or third-party libraries. Can you be sure that no pure function becomes impure when you update a library from version 2.3.1 to 2.3.2?
I'm not aware of any robust automated way to verify referential transparency in mainstream programming languages.
Language support #
While no mainstream languages distinguish between pure functions and impure actions, there are languages that do. The most famous of these is Haskell, but other examples include PureScript and Idris.
I find Haskell useful for exactly that reason. The compiler enforces the functional interaction law. You can't call impure actions from pure functions. Thus, you wouldn't be able to make a change to a function like Validate without changing its type. That would break most consuming code, which is a good thing.
You could write an equivalent to the original, pure version of Validate in Haskell like this:
validateReservation :: ReservationDTO -> Either String ReservationDTO validateReservation r@(ReservationDTO _ d _ _ _) = case readMaybe d of Nothing -> Left $ "Invalid date: " ++ d ++ "." Just (_ :: LocalTime) -> Right r
This is a pure function, because all Haskell functions are pure by default.
You can change it to also check for reservations in the past, but only if you also change the type:
validateReservation :: ReservationDTO -> IO (Either String ReservationDTO) validateReservation r@(ReservationDTO _ d _ _ _) = case readMaybe d of Nothing -> return $ Left $ "Invalid date: " ++ d ++ "." Just date -> do utcNow <- getCurrentTime tz <- getCurrentTimeZone let now = utcToLocalTime tz utcNow if date < now then return $ Left $ "Invalid date: " ++ d ++ "." else return $ Right r
Notice that I had to change the return type from Either String ReservationDTO to IO (Either String ReservationDTO). The presence of IO marks the 'function' as impure. If I hadn't changed the type, the code simply wouldn't have compiled, because getCurrentTime and getCurrentTimeZone are impure actions. These types ripple through entire code bases, enforcing the functional interaction law at every level of the code base.
Pure date validation #
How would you validate, then, that a reservation is in the future? In Haskell, like this:
validateReservation :: LocalTime -> ReservationDTO -> Either String ReservationDTO validateReservation now r@(ReservationDTO _ d _ _ _) = case readMaybe d of Nothing -> Left $ "Invalid date: " ++ d ++ "." Just date -> if date < now then Left $ "Invalid date: " ++ d ++ "." else Right r
This function remains pure, although it still changes type. It now takes an additional now argument that represents the current time. You can retrieve the current time as an impure action before you call validateReservation. Impure actions can always call pure functions. This enables you to keep your complex domain model pure, which makes it simpler, and easier to test.
Translated to C#, that corresponds to this version of Validate:
public static string Validate(DateTime now, ReservationDto dto) { if (!DateTime.TryParse(dto.Date, out var date)) return $"Invalid date: {dto.Date}."; if (date < now) return $"Invalid date: {dto.Date}."; return ""; }
This version takes an additional now input parameter, but remains deterministic and free of side effects. Since it's pure, it's trivial to unit test.
[Theory] [InlineData("2010-01-01 00:01", "2011-09-11 18:30", 3)] [InlineData("2019-11-26 13:59", "2019-11-26 19:00", 2)] [InlineData("2030-10-02 23:33", "2030-10-03 00:00", 2)] public void ValidDate(string now, string reservationDate, int quantity) { var dto = new ReservationDto { Date = reservationDate, Quantity = quantity }; var actual = Validator.Validate(DateTime.Parse(now), dto); Assert.Empty(actual); }
Notice that while the now parameter plays the role of the current time, the fact that it's just a value makes it trivial to run simulations of what would have happened if you ran this function in 2010, or what will happen when you run it in 2030. A test is really just a simulation by another name.
Summary #
Most programming languages don't explicitly distinguish between pure and impure code. This doesn't make it impossible to do functional programming, but it makes it arduous. Since the language doesn't help you, you must constantly review changes to the code and its dependencies to evaluate whether code that's supposed to be pure remains pure.
Tests can help, particularly if you employ property-based testing, but vigilance is still required.
While Haskell isn't a mainstream programming language, I find that it helps me flush out my wrong assumptions about functional programming. I write many prototypes and proofs of concept in Haskell for that reason.
Once you get the hang of it, it becomes easier to spot sources of impurity in other languages as well.
- Anything with the
voidreturn type must be assumed to induce side effects. - Everything that involves random numbers is non-deterministic.
- Everything that relies on the system clock is non-deterministic.
- Generating a GUID is non-deterministic.
- Everything that involves input/output is non-deterministic. That includes the file system and everything that involves network communication. In C# this implies that all asynchronous APIs should be considered highly suspect.
Comments
You might be interested in taking a look at PurityAnalyzer; An open source roslyn-based analyzer for C# that I started developing to help maintain pure C# code.
Unfortunately, it is still not production-ready yet and I didn't have time to work on it in the last year. I was hoping contributors would help.
Yacoub, thank you for writing. I wasn't aware of PurityAnalyzer. Do I understand it correctly that it's based mostly on a table of methods known (or assumed) to be pure? It also seems to look for certain attributes, under the assumption that if a
[Pure]attribute is present, then one can trust it. Did I understand it correctly?The fundamental problems with such an approach aside, I can't think of a better solution for the current .NET platform. If you want contributors, though, you should edit the repository's readme-file so that it explains how the tool works, and how contributors could get involved.
Here are the answers to your questions:
1.it's based mostly on a table of methods known (or assumed) to be pure?
This is true for compiled methods, e.g., methods in the .NET frameworks. There are lists maintained for .NET methods that are pure. The lists of course are still incomplete.
For methods in the source code, the analyzer checks if they call impure methods, but it also checks other things like whether they access mutable state. The list of other things is not trivial. If you are interested in the details, see this article. It shows some of the details.
2. It also seems to look for certain attributes, under the assumption that if a [Pure] attribute is present, then one can trust it. Did I understand it correctly?
I don't use the [Pure] attribute because I think that the definition of pure used by Microsoft with this attribute is different than what I consider to be pure. I used a special [IsPure] attribute. There are also other attributes like [IsPureExceptLocally], [IsPureExceptReadLocally], [ReturnsNewObject], etc. The article I mentioned above explains some differences between these.
I agree with you that I should work on readme file to explain details and ask for contributors.
I love this post and enthusiastically agree with all the points you made.
For what its worth, that overload of
DateTime.TryParseis impure because it depends onDateTimeFormatInfo.CurrentInfo, which depends onSystem.Threading.Thread.CurrentThread.CurrentCulture, which is mutable.Yacoub, could you share some links to such lists?
Tyson, I actually knew that, but in order to keep the example simple and compelling, I chose to omit that fact. That's why I phrased the sentence "Assume that it is" (my emphasis) 😉
Tyson, I meant lists maintained as part of the PurityAnalyzer project. You can find them here.
And in contrast, the C# compiler does not enfore the functional interaction law, right?
For exampe, suppose
FooandBarare pure functions such thatFoocallsBarand the code compiles. Then only change the implementation ofBarin such a way that it is now impure and the code still compiles, which is possible. SoFoois now also impure as well, but its implementation didn't change. Therefore, the C# compiler does not enfore the functional interaction law.Is this consistent with what you mean by the functional interaction law?
Tyson, thank you for writing. The C# compiler doesn't help protect your intent, if your intent is to apply a functional architecture.
In your example,
Foostarts out pure, but becomes impure. That's a result of the law. The law itself isn't broken, but the relationships change. That's often not what you want, so you can say that the compiler doesn't help you maintain a functional architecture.A compiler like Haskell protects the intent of the law. If
foo(Haskell functions must start with a lower-case letter) andbarboth start out pure,foocan callbar. Whenbarlater becomes impure, its type changes andfoocan no longer invoke it.I can try to express the main assertion of the functional interaction law like this: a pure function can't call an impure action. This has different implications in different compiler contexts. In Haskell, functions can be statically declared to be either pure or impure. This means that the Haskell compiler can prevent pure functions from calling impure actions. In C#, there's no such distinction at the type level. The implication is therefore different: that if
FoocallsBarandBaris impure, thenFoomust also be impure. This follows by elimination, because a pure function can't call an impure action. Therefore, sinceFoocan callBar, andBaris impure, thenFoomust also be impure.The causation is reversed, so to speak.
Does that answer your question?
Yes, that was a good answer. Thank you.
We definitely want this to be true, but let's try to make sure it is. What do you think about the C# function
void Foo() => DateTime.Now;? It has lots of good propertie: it alreays returns the same value (something isomorphic toUnit), and it does not mutate anything. However, it calls the impure propertyDateTime.Now. I think a reasonable person could argue that this function is pure. My guess is that you would say that it is impure. Am I right? I am willing to accept that.Is it possible for a function to violate the first rule but not violate the second rule?
Tyson, I'm going to assume that you mean something like
void Foo() { var _ = DateTime.Now; }, since the code you ask about doesn't compile 😉That function is, indeed pure, because it has no observable side effects, and it always returns unit. Purity is mostly a question of what we can observe if we consider the function a black box.
Obviously, based on that criterion, we can refactor the function to
Yes, the following method is non-deterministic, but has no side effects:void Foo() { }and we wouldn't be able to tell the difference. This version ofFoois clearly pure, although degenerate.DateTime Foo() => DateTime.Now;The input is always unit, but the return value can change.I think I need to practice test driven comment writing ;) Thanks for seeing through my syntax errors again.
Oh, you think that that function is pure. Interesting. It follows then that the functional interaction law (pure functions cannot call impure actions) does not follow from the definition of a pure function. It is possible, in theory and in practice, for a pure function to call an impure action. Instead, the functional interaction law is "just" a goal to aspire to when designing a programming language. Haskell achieved that goal while C# and F# did not. Do you agree with this? (This is really what I was driving towards in this comment above, but I was trying to approach this "blasphemous" claim slowly.)
Just as you helped me distinguish between function purity and totality in this comment, I think it would be helpful for us to consider separately the two defining properties of a pure function. The first property is "the same input always produces the same output". Let's call this weak determinism. Determinism is could be defined as "the same input always produces the same sequence of states", which includes the state of the output, so determinism is indeed stronger than weak determinism. The second property is "causes no side effect". It seems to me that there is either a lack of consensus or a lack of clarity about what constitutes a side effect. One definition I like is mutation of state outside of the current stack frame.
One reason the functional interaction law is false in general is because the corresponding interaction law for weak determinism also false in general. The function I gave above (that called
DateTime.Nowand then returned unit) is a trivial example of that. A nontrivial example is quicksort.At this point, I wanted to claim that the side effect interaction law is true in general, but it is not. This law says that a function that is side-effect free cannot call a function that causes a side effect. A counterexample is
void Foo() { int i = 0; Bar(ref i); }withvoid Bar(ref int i) => i++;. That is,Barmutates state outside of its stack frame, namely in the stack frame ofFoo, so it is not side-effect free, butFoois. (And I promise that I tested that code for compiler errors.)I need to think more about that. Is there a better definition of side effect, one for which the side effect interaction law is true?
I just realized something that I think is interesting. Purely functional programming languages enforce a property of functions stronger than purity. With respect to the first defining property of a pure function (aka weak determinism), purely functional programming languages enforce the stronger notion of determinism. Otherwise, the compiler would need to realize that functions like quicksort should be allowed (because it is weakly deterministic). This reminds me of the debate between static and dynamic programming languages. In the process of forbidding certain unsafe code, static languages end up forbidding some safe code as well.
Tyson, I disagree with your basic premise:
I don't think that this follows.The key is that your example is degenerate. The
Foofunction is only pure becauseDateTime.Nowisn't used. The actual, underlying property that we're aiming for is referential transparency. Can you replaceFoowith its value? Yes, you can.Perhaps you think this is a hand-wavy attempt to dodge a bullet, but I don't think that it is. You can write the equivalent function in Haskell like this:
I don't recall if you're familiar with Haskell, but for the benefit of any reader who comes by and wishes to follow this discussion, here are the important points:
- The function calls
- The underscore is a wildcard that tells Haskell to discard the value.
- The type of
This works because Haskell is a strictly functional language. Every expression is referentially transparent. The implication is that something likegetCurrentTime, which is an impure action. Its type isIO UTCTime. TheIOcontainer marks the action as impure.foois() -> (). It takes unit as input and returns unit. There's noIOcontainer involved, so the function is pure.IO UTCTimeis an opaque container ofUTCTimevalues. A pure caller can see the container, but not its contents. A common interpretation of this is thatIOrepresents the superposition of all possible values, just like Schrödinger's box. Also, since Haskell is a lazily evaluated language, actions are only evaluated when their values are needed for something. Since the value ofgetCurrentTimeis discarded, the impure action never runs (the box is never opened). This may be clearer with this example:Like
foo,barcalls an impure action:putStrLn, which corresponds toConsole.WriteLine. Having the typeString -> IO ()it's impure. It works like this:None the less, because
bardiscards theIO ()return value after it callsputStrLn, it never evaluates:Perhaps a subtle rephrasing of the functional interaction law would be more precise. Perhaps it should say that a pure function can't evaluate an impure action.
Bringing this back to C#, we have to keep in mind that C# doesn't enforce the functional interaction law in any way. Thus, the law works ex-post, instead of in Haskell, where it works ex-ante. Is the
FooC# code pure? Yes, it is, because it's referentially transparent.Regarding the purity of QuickSort, you may find this discussion interesting.
So every function in Haskell is referentially transparent, and if a funciton in C# is referentially transparent, then it is pure. Is C# necessary there? Does referential transparency impliy purity regardless of langauge? Do you consider purity and referential transparency to be concepts that imply each other regulardless of language? I think a function is referential transparency if and only if it is pure, and I think this is independent of the langauge.
If C# is not necessary, then it follows that every function in Haskell is pure. This seems like a contradiction with this statement.
You cited Bartosz Milewski there. He also says that every function in Haskell is pure. He calls Haskell functions returning IO a pure action. I agree with Milewski; I think every function in Haskell is pure.
How does this rephrasing help? In the exmaple from my previous comment,
baris impure whilefoois pure even thoughfooevaluatesbar, which can be verified by putting a breakpoint inbarwhen evaluatingfooor by observing thatihas value1whenfooreturns. If Haskell contained impure functions, then replacing "calls" with "evalutes" helps because everything is lazy in Haskell, but I don't see how it helps in an eager langauge like C#.Oh, sorry. I now see that my reference to quicksort was unclear. I meant the randomized version of quicksort for the pivot is selected uniformily at random from all elements being sorted. That refrasing of the functional interaction law doesn't address the issue I am trying to point out with quicksort. To elborate, consider this randomized version of quicksort that has no side effects. I think this function is pure even though it uses randomness, which is necessarily obtained from an impure function.
Tyson, my apologies that I've been so dense. I think that I'm beginning to understand where you're going with this. Calling out randomised pivot selection in quicksort helped, I think.
I would consider a quicksort function referentially transparent, even if it were to choose the pivot at random. Even if it does that, you can replace a given function call with its output. The only difference you might observe across multiple function calls would be varying execution time, due to lucky versus unlucky random pivot selection. Execution time is, however, not a property that impacts whether or not we consider a function pure.
Safe Haskell can't do that, though, so you're correct when you say:
(Actually, you can implement quicksort like that in Haskell as well. In order to not muddy the waters, I've so far ignored that the language has an escape hatch for (among other purposes) this sort of scenario:unsafePerformIO. In Safe Haskell, however, you can't use it, and I've never myself had to use it.)I'm going to skip the discussion about whether or not all of Haskell is pure, because I think it's a red herring. We can discuss it later, if you're interested.
I think that you're right, though, that the functional interaction law has to come with a disclaimer. I'm not sure exactly how to formulate it, but I need to take a detour around side effects, and then perhaps you can help me with that.
Functional programmers know that every execution has side effects. In the extreme, running any calculation on a computer produces heat. There could be other side effects as well, such as CPU registers changing values, data moving in and out of processor caches, and so on. The question is: when do side effects become significant?
We don't consider the generation of heat a significant side effect. What about a debug trace? If it doesn't affect the state of the system, does it count? If not, then how about logging or auditing?
We usually draw the line somewhere and say that anything on one side counts, and things on the other side don't. The bottom line is, though, that we consider some side effects insignificant.
I think that you have now demonstrated that there's symmetry. Not only are there insignificant side effects, but insignificant randomness also exists. The randomness involved in choosing a pivot in quicksort has no significant impact on the output.
Was that what you meant by weak determinism?