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.
While those rules are easy to understand and remember, in practice they're harder to follow than most people realise.

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

"the amplification of the essential and the elimination of the irrelevant"

Robert C. Martin
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.

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 nowReservationDto 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 nowstring reservationDateint 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 void return 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.
If you want to harvest the benefits of functional programming in a mainstream language, you must look out for such pitfalls. There's no tooling to assist you.


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.

2020-02-24 08:16 UTC

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.

2020-02-26 7:12 UTC

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.

2020-02-26 09:51 UTC

I love this post and enthusiastically agree with all the points you made.

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.

For what its worth, that overload of DateTime.TryParse is impure because it depends on DateTimeFormatInfo.CurrentInfo, which depends on System.Threading.Thread.CurrentThread.CurrentCulture, which is mutable.

There are lists maintained for .NET methods that are pure.

Yacoub, could you share some links to such lists?

2020-02-26 20:14 UTC

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) 😉

2020-02-26 21:56 UTC

Tyson, I meant lists maintained as part of the PurityAnalyzer project. You can find them here.

2020-02-27 07:48 UTC
The [Haskell] compiler enforces the functional interaction law. You can't call impure actions from pure functions.

And in contrast, the C# compiler does not enfore the functional interaction law, right?

For exampe, suppose Foo and Bar are pure functions such that Foo calls Bar and the code compiles. Then only change the implementation of Bar in such a way that it is now impure and the code still compiles, which is possible. So Foo is 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?

2020-03-07 12:59 UTC

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, Foo starts 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) and bar both start out pure, foo can call bar. When bar later becomes impure, its type changes and foo can 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 Foo calls Bar and Bar is impure, then Foo must also be impure. This follows by elimination, because a pure function can't call an impure action. Therefore, since Foo can call Bar, and Bar is impure, then Foo must also be impure.

The causation is reversed, so to speak.

Does that answer your question?

2020-03-08 11:32 UTC

Yes, that was a good answer. Thank you.

...a pure function can't call an impure action.

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 to Unit), and it does not mutate anything. However, it calls the impure property DateTime.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.

...a pure function has to obey two rules:
  • The same input always produces the same output.
  • Calling it causes no side effects.

Is it possible for a function to violate the first rule but not violate the second rule?

2020-03-09 04:12 UTC

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 void Foo() { } and we wouldn't be able to tell the difference. This version of Foo is clearly pure, although degenerate.

Is it possible for a function to violate the first rule but not violate the second rule?
Yes, the following method is non-deterministic, but has no side effects: DateTime Foo() => DateTime.Now; The input is always unit, but the return value can change.

2020-03-10 9:03 UTC

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.Now and 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); } with void Bar(ref int i) => i++;. That is, Bar mutates state outside of its stack frame, namely in the stack frame of Foo, so it is not weakly deterministic, but Foo is. (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.

2020-03-10 14:05 UTC

Tyson, I disagree with your basic premise:

"It follows then that the functional interaction law (pure functions cannot call impure actions) does not follow from the definition of a pure function."
I don't think that this follows.

The key is that your example is degenerate. The Foo function is only pure because DateTime.Now isn't used. The actual, underlying property that we're aiming for is referential transparency. Can you replace Foo with 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:

foo :: () -> ()
foo () =
  let _ = getCurrentTime
  in ()

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 getCurrentTime, which is an impure action. Its type is IO UTCTime. The IO container marks the action as impure.
  • The underscore is a wildcard that tells Haskell to discard the value.
  • The type of foo is () -> (). It takes unit as input and returns unit. There's no IO container involved, so the function is pure.
This works because Haskell is a strictly functional language. Every expression is referentially transparent. The implication is that something like IO UTCTime is an opaque container of UTCTime values. A pure caller can see the container, but not its contents. A common interpretation of this is that IO represents 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 of getCurrentTime is discarded, the impure action never runs (the box is never opened). This may be clearer with this example:

bar :: () -> ()
bar () =
  let _ = putStrLn "Bar!"
  in ()

Like foo, bar calls an impure action: putStrLn, which corresponds to Console.WriteLine. Having the type String -> IO () it's impure. It works like this:

> putStrLn "Example"
Example

None the less, because bar discards the IO () return value after it calls putStrLn, it never evaluates:

> bar ()
()

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 Foo C# code pure? Yes, it is, because it's referentially transparent.

Regarding the purity of QuickSort, you may find this discussion interesting.

2020-03-12 7:40 UTC


Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Monday, 24 February 2020 07:31:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 24 February 2020 07:31:00 UTC