How to guarantee referential transparency in F# applications?

Question

So I'm trying to learn FP and I'm trying to get my head around referential transparency and side effects.

I have learned that making all effects explicit in the type system is the only way to guarantee referential transparency:

The idea of “mostly functional programming” is unfeasible. It is impossible to make imperative programming languages safer by only partially removing implicit side effects. Leaving one kind of effect is often enough to simulate the very effect you just tried to remove. On the other hand, allowing effects to be “forgotten” in a pure language also causes mayhem in its own way.

Unfortunately, there is no golden middle, and we are faced with a classic dichotomy: the curse of the excluded middle, which presents the choice of either (a) trying to tame effects using purity annotations, yet fully embracing the fact that your code is still fundamentally effectful; or (b) fully embracing purity by making all effects explicit in the type system and being pragmatic - Source

I have also learned that not-pure FP languages like Scala or F# cannot guarantee referential transparency:

The ability to enforce referential transparency this is pretty much incompatible with Scala's goal of having a class/object system that is interoperable with Java. - Source

And that in not-pure FP it is up to the programmer to ensure referential transparency:

In impure languages like ML, Scala or F#, it is up to the programmer to ensure referential transparency, and of course in dynamically typed languages like Clojure or Scheme, there is no static type system to enforce referential transparency. - Source

I'm interested in F# because I have a .Net background so my next questions is:

What can I do to guarantee referential transparency in an F# applications if it is not enforced by the F# compiler?

Answer 1

The short answer to this question is that there is no way to guarantee referential transparency in F#. One of the big advantages of F# is that it has fantastic interop with other .NET languages but the downside of this, compared to a more isolated language like Haskell, is that side-effects are there and you will have to deal with them.

---

How you actually deal with side effects in F# is a different question entirely.

There is actually nothing to stop you from bringing effects into the type system in F# in very much the same way as you might in Haskell although effectively you are 'opting in' to this approach rather than it being enforced upon you.

All you really need is some infrastructure like this:

/// A value of type IO<'a> represents an action which, when performed (e.g. by calling the IO.run function), does some I/O which results in a value of type 'a.
type IO<'a> = 
    private 
    |Return of 'a
    |Delay of (unit -> 'a)

/// Pure IO Functions
module IO =   
    /// Runs the IO actions and evaluates the result
    let run io =
        match io with
        |Return a -> a            
        |Delay (a) -> a()

    /// Return a value as an IO action
    let return' x = Return x

    /// Creates an IO action from an effectful computation, this simply takes a side effecting function and brings it into IO
    let fromEffectful f = Delay (f)

    /// Monadic bind for IO action, this is used to combine and sequence IO actions
    let bind x f =
        match x with
        |Return a -> f a
        |Delay (g) -> Delay (fun _ -> run << f <| g())

return brings a value within IO.

fromEffectful takes a side-effecting function unit -> 'a and brings it within IO.

bind is the monadic bind function and lets you sequence effects.

run runs the IO to perform all of the enclosed effects. This is like unsafePerformIO in Haskell.

You could then define a computation expression builder using these primitive functions and give yourself lots of nice syntactic sugar.

---

Another worthwhile question to ask is, is this useful in F#?

A fundamental difference between F# and Haskell is that F# is an eager by default language while Haskell is lazy by default. The Haskell community (and I suspect the .NET community, to a lesser extent) has learnt that when you combine lazy evaluation and side-effects/IO, very bad things can happen.

When you work in the IO monad in Haskell, you are (generally) guaranteeing something about the sequential nature of IO and ensuring that one piece of IO is done before another. You are also guaranteeing something about how often and when effects can occur.

One example I like to pose in F# is this one:

let randomSeq = Seq.init 4 (fun _ -> rnd.Next())
let sortedSeq = Seq.sort randomSeq

printfn "Sorted: %A" sortedSeq
printfn "Random: %A" randomSeq

At first glance, this code might appear to generate a sequence, sort the same sequence and then print the sorted and unsorted versions.

It doesn't. It generates two sequences, one of which is sorted and one of which isn't. They can, and almost certainly do, have completely distinct values.

This is a direct consequence of combining side effects and lazy evaluation without referential transparency. You could gain back some control by using Seq.cache which prevents repeat evaluation but still doesn't give you control over when, and in what order, effects occur.

By contrast, when you're working with eagerly evaluated data structures, the consequences are generally less insidious so I think the requirement for explicit effects in F# is vastly reduced compared to Haskell.

---

That said, a large advantage of making all effects explicit within the type system is that it helps to enforce good design. The likes of Mark Seemann will tell you that the best strategy for designing robust a system, whether it's object oriented or functional, involves isolating side-effects at the edge of your system and relying on a referentially transparent, highly unit-testable, core.

If you are working with explicit effects and IO in the type system and all of your functions are ending up being written in IO, that's a strong and obvious design smell.

Going back to the original question of whether this is worthwhile in F# though, I still have to answer with a "I don't know". I have been working on a library for referentially transparent effects in F# to explore this possibility myself. There is more material there on this subject as well as a much fuller implementation of IO there, if you are interested.

---

Finally, I think it's worth remembering that the Curse of the Excluded Middle is probably targeted at programming language designers more than your typical developer.

If you are working in an impure language, you will need to find a way of coping with and taming your side effects, the precise strategy which you follow to do this is open to interpretation and what best suits the needs of yourself and/or your team but I think that F# gives you plenty of tools to do this.

Finally, my pragmatic and experienced view of F# tells me that actually, "mostly functional" programming is still a big improvement over its competition almost all of the time.

Answer 2

I think you need to read the source article in an appropriate context - it is an opinion piece coming from a specific perspective and it is intentionally provocative - but it is not a hard fact.

If you are using F#, you will get referential transparency by writing good code. That means writing most logic as a sequence of transformations and performing effects to read the data before running the transformations & running effects to write the results somewhere after. (Not all programs fit into this pattern, but those that can be written in a referentially transparent way generally do.)

In my experience, you can live perfectly happily in the "middle". That means, write referentially transparent code most of the time, but break the rules when you need to for some practical reason.

To respond to some of the specific points in the quotes:

It is impossible to make imperative programming languages safer by only partially removing implicit side effects.

I would agree it is impossible to make them "safe" (if by safe we mean they have no side-effects), but you can make them safer by removing some side effects.

Leaving one kind of effect is often enough to simulate the very effect you just tried to remove.

Yes, but simulating effect to provide theoretical proof is not what programmers do. If it is sufficiently discouraged to achieve the effect, you'll tend to write code in other (safer) ways.

I have also learned that not-pure FP languages like Scala or F# cannot guarantee referential transparency:

Yes, that's true - but "referential transparency" is not what functional programming is about. For me, it is about having better ways to model my domain and having tools (like the type system) that guide me along the "happy path". Referential transparency is one part of that, but it is not a silver bullet. Referential transparency is not going to magically solve all your problems.