From concepts to implementation
In this article, we will continue our investigation of applying functional programming concepts to Go. While in the previous article, we concentrated on pure functions, we will dive into the ideas and implementation behind effectful functions.
Let’s recap some of the guiding principles.
In functional programming, we try to isolate pure functions from effectful functions. Functions are considered pure if the output of a function depends on its inputs only and if the invocation of such a function does not change anything outside the scope of the function itself (e.g., global variables, the console, files, etc.).
Data structures are considered immutable, i.e., instead of modifying a structure to change data, we create copies of that structure and apply the modifications to that copy.
There exist many benefits of immutability, including:
- The caller of a function does not have to worry that the function modifies its input data, so it’s safe to pass the same input to multiple functions, synchronously or asynchronously, to cache it, etc.
- Functions are easy to understand since, by definition, it is clear that inputs are always read-only and that the only output of a function is its return value. That makes these functions easy to reason about and easy to test
When designing functions, we attempt to design them so the output of one function can be passed as an input to the next function, forming a new function.
If all functions in a composition are pure, then the result of the composition is pure, too, so we can derive more complex scenarios from simpler ones.
While it is desirable to work with pure functions, most real-world programs need side effects because they, e.g., read files, consume user input, rely on environment variables, make HTTP requests, etc.
Side effects are operations that alter or rely on a state outside the current function’s scope. Here’s some examples:
- Reading from a file because the file’s content lies outside of the control of the function. So executing a function repeatedly does not guarantee to produce the same result each time
- Reading an environment variable
- Writing to a file because the write operation might fail
- Writing to the console because doing this repeatedly will produce different results (one vs many console logs)
- Relying on the current time
In functional programming, we try to isolate side effects from pure functions such that their execution is effectful but their composition remains pure.
We represent a side effect as a function without inputs but with a strongly typed return value.
This is a sensible representation because it immediately reveals to the reader that such a function must use some state external to the function. Otherwise, it could not produce an output without any input. The name IO of the type suggests that, in many cases, implementations will make use the I/Osubsystem.
Let’s use a simple example for a side effect: creating a random integer. Such logic is a side effect because the function will produce a non-deterministic, different value each time it is invoked.
Notice the following design details of this function:
- the function randomInt generates the IO function as a higher-order function. Its purpose is to capture a configuration parameter, i.e., the limit of the random number interval. This function is pure because it does not produce the random number directly but instead returns the IO operation that does
- the resulting IO operation will produce a new random number each time, making use of the configuration parameter n from its closure.
The design of our IO datatype allows for the definition of generic composition functions, making it possible to compose more complex IO functions from simpler ones. In particular, we can implement the monadic composition functions Map, Chain, Of , Ap , etc., so we’ll have a common set of functions across various monads (e.g., the Option monad as discussed here).
Let’s take the use case of creating a random integer and then converting it to a formatted string as a simple example. The creation of a random integer is represented by the IO[int] datatype. The creation of a formatted string based on this random integer is represented by a IO[string] datatype. We make use of the Map operation to transform between the two:
Note the following aspects:
- This approach separates concerns between pure and side effectful functions. The transformation function intToString is a pure function that can be unit tested. The result of Map(intToString) is also pure. Only the original rnd IO[int] and the final rndStrg IO[string] are side effectful functions
- Composition is possible because the configuration parameter n for randomInt had been separated out into a closure, so the result is a function without parameters that can easily be composed with other functions of the same kind
- Implementation of Map is fully generic, i.e., it can be implemented (and tested) once and then reused for all particular mappings. This significantly reduces the complexity of the final program
More complex composition
From the above concepts, we can derive more complex and useful compositions. Let’s take the example of executing many IO operations. In general terms, we would like to transform a slice of such operations, i.e., IO[A] into a single IO operation returning a slice, i.e. IO[A] .
A straightforward implementation might look like this:
We might use this composition to create a sequence of random numbers:
The result of the composition is an IO operation, in this case, IO[int] so it will compose easily with subsequent operations.
However, let’s reconsider the implementation of SequenceArray . While it is fairly small and straightforward, we revisit this to set the stage for more complex compositions.
We can observe that the implementation combines two orthogonal aspects:
- handling of the slice, i.e., knowledge about how to traverse a slice, how to build a resulting slice, and how to add to it
- knowledge about the nature of an IO operation, i.e., the fact that we need to create a parameter-less function on line 3 and that we have to invoke a function to create the result on line 7
In addition, our implementation assumes that we invoke the IO operations in-sequence (instead of in-parallel).
By using our monadic composition functions, we can generalize the implementation and separate these aspects. Let’s do this stepwise.
First, we need to introduce another composition function in addition to Of and Map, the Ap function (for apply).
There is an excellent motivation for this function’s (surprising) signature in Ryan’s blog. In this context, we will concentrate on possible implementations and illustrate how to use the function to generalize the SequenceArray implementation.
Let’s start with a simple, synchronous implementation and concentrate on the application of the function first:
Using Of, Map and Ap we can rewrite SequenceArray like so:
At first glance, this implementation is longer and more complex than the previous one, but we can observe the following properties:
- Nothing inside the function body is specific to an IO operation (except for using the type). The function itself only deals with the aspect of treating a slice and delegates all operations related to dealing with IO to the operations on the IO monad
- Traversal of the input slice is only done once instead of with every invocation of the IO function, traversal is converted into the successive combination of values via the Ap function
- This latter property also delegates the decision whether the final IO operation is executed sequentially or in parallel to the implementation of Ap . The sequential traversal on line 28 only does the setup of the final IO but it’s independent of its actual execution
- Finally, we can observe that the identical implementation could be used for other monads than IO , e.g., the Option monad. Only the involved types and the monadic operations would have to change, but not the logic inside SequenceArray . We’ll discuss this aspect later.
As an illustration of the value of separating out the logic of slice traversal from the monadic logic, let’s see what it takes to run the IO operations concurrently instead of sequentially. In general, this would be sensible since often implementations of the IO monad execute real I/O operations and it can be very beneficial to execute those concurrently. If the concern exists that executing IO operations in parallel might be problematic because they might have interdependencies, then the solution is to use composition functions such as Chain to model these interdependencies. Otherwise, we can safely assume that the operations are independent.
This version of Ap has the identical interface as the synchronous implementation, so it can be used as a drop-in replacement in SequenceArray, the complexity of running and synchronizing between go routines is captured in a central place without increasing the complexity of the SequenceArray function. In fact, the same implementation can be used for sequence operations on other data structures, e.g., maps, trees, etc.
Leveling-up the use of generics
In the previous section, we have noticed that the implementation of SequenceArray is the same across different monadic types. Let’s see how to express this in Go to achieve a truly generic implementation.
The signature of our function is SequenceArray[A any](as IO[A]) IO[A] , we would like to represent IO as a type parameter as well. Notice, however, that the type IO[A] has a second level of indirection compared to the type A , this is what we call higher kinded types.
If Go supported higher kinded types, this could look like this:
However, this does not work in the current version of Go for the following reasons:
- Higher kinded types cannot be expressed, so Applicative[HKT any] where HKT in itself is a type with parameters that cannot be expressed
- Type parameters on methods (on a struct) are not permitted. Notice that on the Applicative data structure, the member methods reflect a set of functions each because they can be typed individually.
So, since the ideal solution does not work, we can still develop a generic implementation at the cost of readability of the generic function (but with little compromise for exploiters).
The idea is to treat all involved higher kinded types as individual type parameters, ignoring that HKT[A] is connected to the type A . Also, instead of relying on a Applicativ[HKT] type we pass in the monadic functions with their explicit typings into our generic implementation:
Ignoring the motivation for the ~ operator for the moment (as in AR_A), we can see how we have denormalized the higher kinded types into simple types at the cost of readability. The important advantage, however, is that this implementation can be reused across different monads, i.e., for the IO monad:
of equivalently for the Option monad:
Logging is a vital part of many applications. We will not discuss the different types of logging — such as writing to log files, sending logs to servers, or simply printing debug logs to the console — but rather focus on how and where to add logging statements to our functional composition.
From the perspective of functional programming, logging is a side effect because it changes the system outside of the scope of the log function, e.g., by writing a log statement to the console. Consequently, it should be represented as an IO operation. We usually do not care about any return value of the logging operation, so a convenient type is IO[any] .
Let’s define a simple log function that accepts a format string and returns an IO function that prints an input value to the default logger via that format string when executed:
We apply the same concept as with the random number function, i.e., we introduce pure generator functions that carry parameters (the format string and the actual value), and the side effect is executed in the final IO function. This makes the approach composable.
But why split the format string and the value a in a higher-order function instead of defining Log as a binary function with two inputs (currying)?
The reason is also to improve composability, as we will see.
How would we use this logging function? Conceptually, we would like to log the result of one side effect in the side effect of the logger, i.e., we execute the logger after the source in a chain of operations. The monadic function Chain (sometimes also called FlatMap) looks like this:
Here we see the reason for the curried Log function since the input to Chain is exactly of the form of the higher-order function returned by Log .
We can use it like this:
This approach composes well, but it has an issue: the result of the composition is IO[any] because the IO monad returned by Log is of that type and Chain composes one after the other. This is not the desired behaviour; we would like the chain to continue with the original value, not the result of the Log operation, we will discard anyway.
The solution is to introduce the ChainFirst operation. It will also execute the side effects one after the other, but it returns the result of the first one instead of the second one:
With this, our logging is composable and works as expected:
So far, we have considered side effects that always produce a value, i.e., such effects that cannot result in errors. Examples are random numbers or access to the current time. In many cases, however, the execution of side effects might result in errors, e.g., when trying to read content from a file.
In Go as well in generally in functional programming, errors are represented by returning either the desired value or an error, in idiomatic Go, via the tuple (A, error).
So we call a function with side effects that may produce an error IOEither with the following type of definition:
The motivation is to stay as close to the best practices of idiomatic Go as possible, although this type definition also bears challenges.
We start by implementing the functions Of, Map, and Ap for the new IOEither type:
The implementation is straightforward and not surprising. However, this is enough to reuse our generic implementation of SequenceArray and to produce a version that supports error handling with just one single line of code:
What an amazing power that lies behind the abstraction of monadic functions!
We could stop here, but let’s take a step back and revisit the type definition of IOEither, i.e. type IOEither[A any] func() (A, error) . Logically, the IOEither type appears to be a specialization of the IO type we had introduced before, but in fact, it is a new, unrelated type, and consequently, the implementations of the monadic functions are also unrelated.
The reason behind this disconnect is that (A, error) is not a type on its own in Go. If it were, we could have defined IOEither[A any] IO[(A, error)], a definition that would reveal the relationship between both types more clearly. In addition, there would be the chance to reuse implementation logic.
But we can come up with an alternative type definition by introducing a new type, Either that is equivalent to (A, error) but that fits into the type system of Go:
With this type of definition, our IOEither type is:
You can see how the implementation of the functions simplifies since, as the types correlate, we can compose the monadic functions of IO with those of Either to construct the functions for IOEither.
Unfortunately, an issue with this implementation leads us to the final topic. The code does not compile with the error message:
cannot use IO.Of(E.Of(a)) (value of type IO.IO[Either.Either[A]]) as IOEither[A] value in return statement
The ~ operator and base types
At first glance, the error message appears to be questionable since we have defined IOEither[A] to be IO[Either[A]], so why is the assignment not possible?
The reason is that Go does not have the concept of co- or contravariant types. It only knows about invariant types. To Go, the type IOEither[A] is a new type. It is covariant as a return value of IO[Either[A]] but not identical.
Fortunately, a special operator in Go allows us to express the desired behaviour, the ~ operator, and the concept of base types. A definition of, e.g. func Of[A any](a A) IO[A] is not generic enough if we aim to reuse this function for derived types of IO[A], such as IOEither[A] because we expect exactly IO[A] as the return value. Instead, it is sufficient to expect a return value that has IO[A] as its base type. The syntax to express this desire is:
We observe the following:
- The implementation is the same as with IO[A] as the base type
- The intent to accept contravariant return types is expressed by the introduction of a new type parameter IO_A . The ~ operator allows to specify a restriction of this type, saying that it must be a specialization of the IO[A] type. We cannot use that type directly, however, but we need to unfold the type to its native Go representation
With this generalized type definition, we can finally implement IOEither:
We see that the IOEither implementation uses the same base type approach to support even more derivations of types.
The base type problem was also the reason for the type definitions of AR_A ~A in the generic SequenceArray function. Without this type, the function could not be used if the consuming code defined a special type for the input array, e.g. type MyValues int
This article suggests separating effectful functions from pure functions in a Go codebase. We introduce the signature func() A aka IO[A] for such effectful functions because this signature allows a reader to immediately identify the function as having side effects just by looking at the definition.
We illustrate the usefulness of monadic function abstraction (Of , Map , Ap , Chain) to implement algorithms independent of the actual monad, but include the IO monad in particular. The advantage of such generic implementation lies in the fact that the code can be written and tested once, and it can then be applied to a variety of monads.
We also show that the generics type system introduced in go 1.18 provided sufficient flexibility for the implementations, although some workarounds are required.
The investigation of the seemingly simple problem of a side effectful function led to some interesting insight into problems of code reuse and generic programming.
Is it worth investing in this level of abstraction?
It is, and I find in my daily work that the attempt to split problems into the categories of pure and side effectful functions leads to testable code and, as a consequence, to a relatively stable codebase. It takes time and a learning curve to come from procedural thinking to functional thinking but after a while, this becomes second nature.
I also realize that many of my programming tasks can be considered operations on sets of data, so abstractions such as SequenceArray or SequenceMapare very useful and reduce the overall boilerplate code. In case of IO monads with the automatic benefits of running I/O operations in parallel with minimal effort (if desired and applicable).