Learning Functional Programming in Go

4.2 (12 reviews total)
By Lex Sheehan
  • Instant online access to over 7,500+ books and videos
  • Constantly updated with 100+ new titles each month
  • Breadth and depth in over 1,000+ technologies
  1. Pure Functional Programming in Go

About this book

Lex Sheehan begins slowly, using easy-to-understand illustrations and working Go code to teach core functional programming (FP) principles such as referential transparency, laziness, recursion, currying, and chaining continuations.

This book is a tutorial for programmers looking to learn FP and apply it to write better code. Lex guides readers from basic techniques to advanced topics in a logical, concise, and clear progression.

The book is divided into four modules. The first module explains the functional style of programming: pure functional programming, manipulating collections, and using higher-order functions. In the second module, you will learn design patterns that you can use to build FP-style applications. In the next module, you will learn FP techniques that you can use to improve your API signatures, increase performance, and build better cloud-native applications. The last module covers Category Theory, Functors, Monoids, Monads, Type classes and Generics.

By the end of the book, you will be adept at building applications the FP way.

Publication date:
November 2017
Publisher
Packt
Pages
672
ISBN
9781787281394

 

Chapter 1. Pure Functional Programming in Go

"Go is an attempt to combine the safety and performance of statically typed languages with the convenience and fun of dynamically typed interpretative languages."

- Rob Pike

Do you love Go? If so, why? Could it be better? Can you write your code better today?

Go is simple yet powerful, its compiler is fast and cross-platform, and it makes concurrent programming easy. Go also provides useful tooling and has a great development community. Perhaps Go could be better. (We'll explore that question in some depth.) This book will help you write better code using the functional programming (FP) style of coding. Let's get started!

In this chapter, I will share the benefits of pure FP as well as its performance implications in Go by working through Fibonacci sequence code samples. Starting with a simple imperative implementation, you will explore functional implementations and learn some test-driven development and benchmark techniques along the way.

The goal of this chapter is to:

  • Become grounded in the theory of FP
  • Learn how to implement functional solutions
  • Determine what type of FP will best fit your business requirements
 

Motivation for using FP


The FP style of programming can help you write less code in a more concise and expressive way, with fewer errors. How is that possible? Well, FP treats computation as an evaluation of mathematical functions. FP leverages this computational model (and the work of some brilliant mathematicians and logicians) to enable optimizations and performance gains that are simply not possible using traditional imperative coding techniques.

Developing software is not easy. You must handle numerous non-functional requirements (NFRs) first, such as:

  • Complexity
  • Extensibility
  • Maintainability
  • Reliability
  • Concurrency
  • Scalability

Software is becoming more and more complex. What is the average number of third-party dependencies in your typical application? What did that look like 5 years ago? Our applications often must integrate with other services within our own company and with our partners as well as external customers. How can we manage this growing complexity?

Applications used to run on-site on servers that were given pet names, such as Apollo, Gemini, and so on. It seems like every client would have a different naming scheme. Nowadays, most applications are deploying into a cloud environment, for example, AWS or the Google Cloud Platform. Do you have a lot of software applications that run on a lot of servers? If so, you should treat your servers more like cattle; there's just so many of them. Also, since you've got auto scaling, what's important is not a single server but the herd. As long as you always have at least one server in your cluster running for the accounting department, that's all that really matters.

With numbers comes complexity. Can you compose your applications to fit together like Lego blocks, and do you find it easy to write useful tests that run really fast. Alternatively, do you ever feel like there's too much scaffolding/for loops in your code? Do you like handling theerr != nilcondition so frequently? Would you like to see a simpler, cleaner way to do the same thing? Do your applications have any global variables? Do you have code in place to always properly manage its state and prevent all the possible side effects? Have race conditions ever been a problem?

Are you aware of all the possible error conditions in your applications, and do you have code in place to handle them? Can you look at the function signature of any function in your code and immediately have an intuition as to what it does?

Are you interested in learning about a better way to achieve your NFRs and enjoy developing Go software even more than you do right now? Looking for the silver bullet? If so, please continue reading.

Note

Note that the rest of this book will be written in first person plural since we will be learning together.

 

Getting the source code


Note

The GitHub repository for this book's source code is https://github.com/l3x/learn-fp-go. If you store your Go projects in the ~/myprojects directory, then run cd ~/myprojects; git clone https://github.com/l3x/learn-fp-go.git. Next, run the cd command into the first project directory: cd ~/myprojects/learn-fp-go/1-functional-fundamentals/ch01-pure-fp/01_oop.

The directory structure of the source files

Directories correspond to the book's units and chapters:

Note

You'll find an executable init script file in all project directories. It's there to make your life easier. When you cd into a project directory, first source the init script. You can do that by either typing source init or . init . (The dot (.) and source commands are interchangeable.) The init script will use Glide to install any dependencies for your project in a vendors directory. For details see the How to build and run Go project section in the Appendix, Miscellaneous Information and How-Tos. PS: Dependencies are third-party Go libraries that our Go application needs to run properly. 

Let's run our first Go application as follows:

Each chapter is divided into sequentially numbered directories that are in the order of their appearance in the book.

How to run our first Go application

First, let's make sure we have Go installed, our GOPATH is properly set, and that we can run a Go application.

Note

If you are using a macOS, then check out the instructions on how to use the brew command to install Go in the appendix; otherwise, to install Go, visit: http://golang.org/doc/install.To set your GOPATH, visit: https://github.com/golang/go/wiki/SettingGOPATH.

Many people use a global GOPATH to store the source code for all their Go applications or, frequently, manually reset their GOPATH. I found this practice to be troublesome when working with multiple Go projects for multiple clients, each of which had differing Go versions and third-party dependencies.

The example Go applications that we'll use in this chapter do not have dependencies; that is, we don't have to import any third-party packages. So, all we have to do to run our first app--cars.go--is verify that Go is installed, set our GOPATH, and type go run cars.go:

Using a global GOPATH is easy for projects that are super simple, like the examples in this chapter.

In Chapter 2, Manipulating Collections, our Go applications will start getting more complex, and we'll get introduced to a simple, more consistent way to manage our Go development environments.

 

Imperative versus declarative programming


Let's look at why the functional style of programming helps us be more productive than the imperative alternative.

"We are not makers of history. We are made by history."

- Martin Luther King, Jr.

Nearly all computer hardware is designed to execute machine code, which is native to the computer, written in the imperative style. The program state is defined by the contents of memory, and the statements are instructions in the machine language where each statement advances the state of computation forward, toward a final outcome. Imperative programs change their state over time, step by step. High-level imperative languages, such as C and Go, use variables and more complex statements, but they still follow the same paradigm. Since the basic ideas in imperative programming are both conceptually similar to low-level code that operates directly on computer hardware, most computer languages--such as Go, also known as C of the 21st century--are largely imperative.

Imperative programming is a programming paradigm that uses statements that change a program's state. It focuses on the step-by-step mechanics of how a program operates.

The term is often used in contrast to declarative programming. In declarative programming, we declare what we want the results to be. We describe what we want, not detailed instructions of how to get it.

Here's a typical, imperative way to find Blazer in a slice of cars:

var found bool 
carToLookFor := "Blazer" 
cars := []string{"Accord", "IS250", "Blazer" }
for _, car := range cars {
   if car == carToLookFor {
      found = true; // set flag
   }
}
fmt.Printf("Found? %v", found)

Here's a functional way of accomplishing the same task:

cars := []string{"Accord", "IS250", "Blazer" }
fmt.Printf("Found? %v", cars.contains("Blazer"))

That's nine lines of imperative code, compared to two lines in the functional programming (FP) style.

Functional constructs often express our intent more clearly than for loops in such cases and are especially useful when we want to filter, transform, or aggregate the elements in a dataset.

In the imperative example, we must code the how. We must:

  • Declare a Boolean flag
  • Declare and set a variable value
  • Create a looping structure
  • Compare each iterated value
  • Set the flag

In the functional example, we declare what we want to do. We are able to focus on what we want to accomplish, rather than bloating our code with the mechanics of looping structures, setting variable values, and so on.

In FP, iteration is implemented by the library function contains(). Leveraging library functions means that we code less and allow library developers to focus on highly efficient implementations, which have been typically vetted and performance enhanced by seasoned professionals. We don't have to write, debug, or test such high-quality code for repetitive logic.

Now, let's look at how we could look for Blazer using the object-oriented programming paradigm:

type Car struct {
   Model string
}
accord := &Car{"Accord"}; is250 := &Car{"IS250"}; blazer := &Car{"Blazer"}
cars := []*Car{is250, accord, blazer}
var found bool
carToLookFor := is250
for _, car := range cars {
   if car == carToLookFor {
     found = true;
   }
}
fmt.Printf("Found? %v", found)

First, we declare our object types:

type Car struct {
   Model string
}
type Cars []Car

Next, we add our methods:

func (cars *Cars) Add(car Car) {
   myCars = append(myCars, car)
}

func (cars *Cars) Find(model string) (*Car, error) {
for _, car := range *cars {
if car.Model == model {
return &car, nil
      }
   }
return nil, errors.New("car not found")
}

Here, we declare a global variable, namely myCars, where we will persist the state, that is, the list of cars that we will build:

var myCars Cars

Add three cars to the list. The Car object encapsulates the data for each object, and the cars object encapsulates our list of cars:

func main() {
   myCars.Add(Car{"IS250"})
   myCars.Add(Car{"Blazer"})
   myCars.Add(Car{"Highlander"})

Look for Highlander and print the results:

    car, err := myCars.Find("Highlander")
if err != nil {
      fmt.Printf("ERROR: %v", car)
   } else {
      fmt.Printf("Found %v", car)
   }
}

We are using car objects, but we are essentially doing the same operations as we were in the simple imperative code example. We do have objects that have state and to which we could add methods, but the underlying mechanisms are the same. We assign a state to object properties, modify the internal state by making method calls, and advance the state of execution until we arrive at the desired outcome. That's imperative programming.

 

Pure functions


"Insanity is doing the same thing over and over again and expecting different results."

- Albert Einstein

We can use this insanity principle to our advantage with pure functions.

Assigning values to variables during an imperative function's execution may result in the modification of a variable in the environment in which it has run. If we run the same imperative function again, using the same input, the result may differ.

Given the results of an imperative function and given the same input, different results may be returned each time it is run. Is that not insanity?

Pure functions:

  • Treat functions as first-class citizens
  • Always return the same result given the same input(s)
  • Have no side effects in the environment in which they run
  • Do not allow an external state to affect their results
  • Do not allow variable values to change over time

Two characteristics of a pure function include referential transparency and idempotence:

  • Referential transparency: This is where a function call can be replaced with its corresponding value without changing the program's behavior
  • Idempotence: This is where a function call can be called repeatedly and produce the same result each time

Referentially transparent programs are more easily optimized. Let's see whether we can perform optimizations using a caching technique and Go's concurrency features.

 

Fibonacci sequence - a simple recursion and two performance improvements


The Fibonacci sequence is a sequence of numbers where each number is equal to the previous two numbers added together. Here's an example of this:

 1  1  2  3  5  8  13  21  34

So, 1 plus 1 is 2, 2 plus 3 is 5, 5 plus 8 is 13, and so on.

Let's use the Fibonacci sequence to help illustrate a number of concepts.

A recursive function is a function that calls itself in order to break down complex input into simpler ones. With each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached.

The Fibonacci sequence can be easily implemented as a recursive function:

func Fibonacci(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return Fibonacci(x-2) + Fibonacci(x-1)
    }
}

In the preceding recursive function (Fibonacci), if the input is the simple case of 0 then it returns 0. Similarly, if the input is 1 or 2 then return 1.

An input of 0, 1 or 2 is called the base case or stopping condition; else, fib will call itself twice, adding the previous value in the sequence to the one preceding it:

Fibonacci(5) calculation graph

In the preceding figure Fibonacci(5) calculation graph, we can visually see how the fifth element in the Fibonacci sequence is calculated. We see f(3) is calculated twice and f(2) is calculated thrice. Only the final leaf nodes of 1 are added together to calculate the sum total of 5:

func main() {
   fib := Fibonacci
   fmt.Printf("%vn", fib(5))
}

Run that code and you'll get 5. Recursive functions perform identical calculations over and over again; f(3) is calculated twice and f(2) is calculated thrice. The deeper the graph, the more redundant calculations get executed. That is terribly inefficient. Try it yourself. Pass a value greater than 50 to fib and see how long you have to wait for the final result.

Go provides many ways to improve this performance. We'll look at two options: memoization and concurrency.

Memoization is an optimization technique used to increase performance by storing the results of expensive function calls and returning the cached result when the same input occurs again.

Memoization works well because of the following two properties of pure functions:

  • They always return the same result given the same input(s)
  • They have no side effects in the environment in which they run

Memoization

Let's utilize a memoization technique to speed up our Fibonacci calculation.

First, let's create a function type named Memoized() and define our Fibonacci variable to be of that type:

type Memoized func(int) int
var fibMem Memoized

Next, let's implement theMemoize()function. The key thing to realize here is that as soon as our application starts, even before ourmain()function is executed, ourfibMemvariable get wired up. If we were to step through our code we'd see that ourMemoizefunction is called. The cache variable is assigned and our anonymous function is returned and assigned to our fibMem function literal variable.

funcMemoize(mf Memoized) Memoized {
       cache := make(map[int]int)
return func(key int) int {
if val, found := cache[key]; found {
return val
              }
              temp := mf(key)
              cache[key] = temp
return temp
       }
}

Memoize takes a Memoized() function type as its input and returns a Memoized() function.

In the first line of Memoize, we create a variable of the type map to act as our cache in order to hold computed Fibonacci computations.

Next, we create a closure that is of the type Memoized(), which is returned by the Memoize() function. Note that a closure is an inner function that closes over or that has access to variables in its outer scope.

Inside the closure, if we find the computation for the passed integer, we return its value from the cache; else we call the recursive Fibonacci function(mf) with the integer parameter (key), whose return value will be stored incache[key]. Next time, when the same key is requested its value will be returned directly from the cache.

An anonymous function is a function defined with no name. When an anonymous function includes logic that can access variables defined in its scope, for example, cache, and if that anonymous function can be passed as an argument or returned as the value of function calls, which is true in this case, then we can refer to this anonymous function as a lambda expression.

We'll implement the logic of the Fibonacci Sequence in a function named fib:

func fib(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return fib(x-2) + fib(x-1)
   }
}

The last thing we do in our memoize.go file is to create the following function:

func FibMemoized(n int) int {
return fibMem(n)
}

Now, it's time to see if our wiring works properly. In our main() function when we execute our println statement, we get the correct output.

println(fibonacci.FibMemoized(5))

The following is the output:

5

We can verify that 5 is the correct answer by glancing back at our Fibonacci(5)calculation graph shown earlier in this chapter.

If we were to step through our code using a debugger, we'd see that fibonacci.FibMemoized(5) calls the following

func FibMemoized(n int) int {
return fibMem(n)
}

And the value of n variable is 5. Since fibMem is pre-wired, we start executing at the return statement (and we have access to the cache variable that has already been initialized) . So, we begin executing at the return statement shown in the following code (from the Memoize function):

return func(key int) int {
if val, found := cache[key]; found {
return val
   }
   temp := mf(key)
   cache[key] = temp
return temp
}

Since this is the first time through, there are no entries in the cache and we skip past the body of the if block and run temp := mf(key)

That calls the fib function:

func fib(x int) int {
if x == 0 {
return 0
} else if x <= 2 {
return 1
} else {
return fib(x-2) + fib(x-1)
   }
}

Run the fib function as follows:

Since x is greater than 2 we run the last else statement that recursively calls fib twice. Recursive calls to fib continues until the base conditions are reached and the final result is calculated and returned.

 

The difference between an anonymous function and a closure


Let's look at a few simple code examples to understand the difference between an anonymous function and a closure.

Here's a typical named function:

func namedGreeting(name string) {
   fmt.Printf("Hey %s!n", name)
}

The following is an example of the anonymous function:

func anonymousGreeting() func(string) {
     return func(name string) {
            fmt.Printf("Hey %s!n", name)
     }
}

Now, let's call them both and call an anonymous inline function to say Hey to Cindy:

func main() {
   namedGreeting("Alice")


   greet := anonymousGreeting()
   greet("Bob")


   func(name string) {
      fmt.Printf("Hello %s!n", name)
   }("Cindy")
}

The output will be as follows:

Hello Alice!
Hello Bob!
Hello Cindy!

Now, let's look at a closure named greeting and see the difference between it and the anonymousGreeting() function.

Since the closure function is declared in the same scope as the msg variable, the closure has access to it. The msg variable is said to be in the same environment as the closure; later, we'll see that a closure's environment variables and data can be passed around and referenced at a later time during a program's execution:

func greeting(name string) {
     msg := name + fmt.Sprintf(" (at %v)", time.Now().String())

     closure := func() {
            fmt.Printf("Hey %s!n", msg)
     }
     closure()
}


func main() {
     greeting("alice")
}

The output will be as follows:

Hey alice (at 2017-01-29 12:29:30.164830641 -0500 EST)!

In the next example, instead of executing the closure in the greeting() function, we will return it and assign its return value to the hey variable in the main function:

func greeting(name string) func() {
     msg := name + fmt.Sprintf(" (at %v)", time.Now().String())
     closure := func() {
            fmt.Printf("Hey %s!n", msg)
     }
     return closure
}

func main() {
     fmt.Println(time.Now())
     hey := greeting("bob")
     time.Sleep(time.Second * 10)
     hey()
}

The output will be as follows:

2017-01-29 12:42:09.767187225 -0500 EST
Hey bob (at 2017-01-29 12:42:09.767323847 -0500 EST)!

Note that the timestamp is calculated when the msg variable is initialized, at the time the greeting("bob") value is assigned to the hey variable.

So, 10 seconds later, when greeting is called and the closure is executed, it will reference the message that was created 10 seconds ago.

This example shows how closures preserve state. Instead of manipulating the state in the outside environment, closures allow states to be created, passed around, and subsequently referenced.

With functional programming, you still have a state, but it's just passed through each function and is accessible even when the outer scopes, from where they originated, have already exited.

Later in this book, we'll see a more realistic example of how closures can be leveraged to maintain a context of application resources required by an API.

Another way to speed up our recursive Fibonacci function is to use Go's concurrency constructs.

FP using Go's concurrency constructs

Given the expression result := function1() + function2(), parallelization means that we can run each function on a different CPU core and the total time will be approximately the time it takes for the most expensive function to return its result. Consider the following explanation for parallelization and concurrency:

  • Parallelization: Executing multiple functions at the same time (in different CPU cores)
  • Concurrency: Breaking a program into pieces that can be executed independently

Note

I recommend that you check out the video Concurrency is Not Parallelism, by Rob Pike at https://player.vimeo.com/video/49718712. This is where he explains concurrency as a decomposition of a complex problem into smaller components, where individual components can be run simultaneously resulting in improved performance, assuming communication between them is managed.

Go enhances the concurrent execution of Goroutines with synchronization and messaging using channels and provides multiway concurrent control with the Select statement.

The following language constructs provide a model in Go for concurrent software construction that is easy to understand, use, and reason about:

  • Goroutine: A lightweight thread managed by the Go runtime.
  • Go statements: The go instruction that starts the execution of a function call as an independent concurrent thread of control, or Goroutine, in the same address space as the calling code.
  • Channel: A typed conduit through which you can send and receive values with the channel operator, namely <-.

In the following code, data is sent to channel in the first line. In the second line, data is assigned the value received from channel:

channel <- data
data := <-channel

Since Go channels behave as FIFO queues, where the first items in are the first items out, and since the calculation for the next number in a Fibonacci sequence is a small component, it seems that our Fibonacci sequence function calculation is a great candidate for a concurrency implementation.

Let's give it a go. First, let's define a Channel function that uses a channel to perform Fibonacci calculations:

func Channel(ch chan int, counter int) {
       n1, n2 := 0, 1
for i := 0; i < counter; i++ {
              ch <- n1
              n1, n2 = n2, n1 + n2
       }
       close(ch)
}

First, we declare the variables n1 and n2 to hold our initial sequence values of 0 and 1.

Then, we create a loop for the total number of times given. In each loop, we send the next sequential number to the channel and calculate the next number in the sequence, until we reach our counter value, which is the last sequential number in our sequence.

The following FibChanneled function creates a channel, namely ch, using the make() function and defines it as a channel that contains integers:

funcFibChanneled(n int) int {
       n += 2
ch := make(chan int)
go Channel(ch, n)
       i := 0; var result int
for num := range ch {
              result = num
              i++
       }
return result
}

We run our Channel (Fibonacci) function as a Goroutine and pass it the ch channel and the 8number, which tells Channel to produce the first eight numbers from the Fibonacci sequence.

Next, we range over the channel and print any values that the channel produces for as long as the channel has not been closed.

Now, let's take a breather and examine what we've accomplished with our Fibonacci sequence examples.

 

Testing FP using test-driven development


Let's write some tests to verify each technique (simple recursive, memoized, and channeled) works properly. We'll use TDD to help us design and write better code.

TDD, a software development method where the developer starts with requirements and first writes a simple test that will fail. Then, it writes just enough code to make it pass. It continues this unit testing pattern repeatedly until there are no more reasonable tests that validate the code satisfies the requirements. The concept is to get something working now and perfect it later. After each test, refactoring is performed to implement a little more of the feature requirement.

The same or similar test(s) are performed again as well as introducing new test code to test the next piece of the feature. The process is iterated as many times as necessary until each unit is functioning according to the desired specifications:

TDD workflow diagram

We can start using a table of input values and their corresponding result values to verify that the function under test is working properly:

// File: chapter1/_01_fib/ex1_test.go
package fib

import "testing"

var fibTests = []struct {
   a int
   expected int
}{
   {1, 1},
   {2, 2},
   {3, 3},
   {4, 5},
   {20, 10946},
   {42, 433494437},
}

func TestSimple(t *testing.T) {
   for _, ft := range fibTests {
      if v := FibSimple(ft.a); v != ft.expected {
        t.Errorf("FibSimple(%d) returned %d, expected %d", ft.a, v, ft.expected)
      }
   }
}

Recall that the Fibonacci sequence looks like this: 1 1 2 3 5 8 13 21 34. Here, the first element is 1 {1, 1}, the second element is 2 {2, 2}, and so on.

We use the range statement to iterate through the table, row by row, and check each calculated result (v := FibSimple(ft.a)) against the expected value (ft.expected) from that row.

Only if there is a mismatch do we report the error.

Later in the ex1_test.go file, we find the benchmark testing facility in action, which allows us to examine the performance of our Go code:

func BenchmarkFibSimple(b *testing.B) {
     fn := FibSimple
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

Let's open a terminal window and write the cd command to the first set of Go code, our book's source code repository. For me, that directory is ~/clients/packt/dev/learn-fp-go/1-functional-fundamentals/ch01-pure-fp/01_fib.

A note about paths

In the first example, I used the~/myprojects/learn-fp-gopath. The path that I actually used to create the code in this book is~/clients/packt/dev/learn-fp-go. So, please don't be confused by those paths. They are the same thing.

Also, later in the book, when we start using Dot Init, the screenshots may reference the~/devdirectory. That comes from the Init script, that is,MY_DEV_DIR=~/dev.

Here are a few links in that directory:

[email protected] -> /Users/lex/clients/packt/dev/learn-fp-go/2-design-patterns/ch04-solid/01_duck
[email protected] -> /Users/lex/clients/packt/dev/learn-fp-go/1-functional-fundamentals/ch03-hof/01_hof
[email protected] -> /Users/lex/clients/packt/dev/learn-fp-go/2-design-patterns/ch07-onion-arch/04_onion

For more information about Dot Init, see the appendix.

How to run our tests

In the first benchmark test, we examine the performance of computing the eighth number in the Fibonacci sequence. Note that we pass the -bench=.argument, which means run all benchmark tests. The ./... argument means to run all the tests in this directory and all the child directories as well:

When we request the eighth number in the sequence, the simple recursive implementation runs faster than the memoized and channeled (optimized) versions, 213 ns/op compared to 1302 ns/op and 2224 ns/op, respectively.

In fact, when the simple version is executed once, it only takes 3.94 ns/op.

One very cool feature of Go's benchmark testing facility is that it is smart enough to figure out how many times to execute the function under test. The value of b.N will increase each time until the benchmark runner is satisfied with the stability of the benchmark. The faster the function runs under a test, the more times the benchmark facility will run it. The more times the benchmark facility runs a function, the more accurate the performance metric, for example, 3.94 ns/op.

Take the FibSimple test for example. When it is passed with 1, it means it only needs to execute once. Since it only takes 3.94 ns/op, we see it is executed 10,000,000 times. However, when FibSimple is passed with 40, we see that it takes 2,509,110,502 ns to complete one operation, and the benchmark facility is smart enough to only run it once. That way, we can be assured that running benchmark tests is as accurate as possible and they run within a reasonable time. How nice is that?

Since the FibSimple implementation is recursive and has not been optimized, we can test our assumption that the time it takes to calculate each successive number in the sequence will increase exponentially. We can do this using a common testing technique by calling the private function benchmarkFibSimple, which avoids directly invoking the test driver:

func benchmarkFibSimple(i int, b *testing.B) {
     for n := 0; n < b.N; n++ {
            FibSimple(i)
     }
}

func BenchmarkFibSimple1(b *testing.B)  { benchmarkFibSimple(1, b) }
func BenchmarkFibSimple2(b *testing.B)  { benchmarkFibSimple(2, b) }
func BenchmarkFibSimple3(b *testing.B)  { benchmarkFibSimple(3, b) }
func BenchmarkFibSimple10(b *testing.B) { benchmarkFibSimple(4, b) }
func BenchmarkFibSimple20(b *testing.B) { benchmarkFibSimple(20, b) }
func BenchmarkFibSimple40(b *testing.B) { benchmarkFibSimple(42, b) }

We test the first four numbers in the sequence, 20 and then 42. Since it takes about 3 seconds for my computer to calculate the 42nd number in the sequence, I decided not to go any higher. No need to wait longer than that when we can easily see the exponential growth pattern, without having to wait for more than a minute to get our results.

Our benchmark testing has proven that our simple, recursive implementation of the Fibonacci sequence behaves as expected. This behavior equates to poor performance.

Let's look at a few ways to increase performance.

We have observed that our FibSimple implementation always returns the same result, given the same input(s), and that there are no side effects in the environment in which it runs. For example, if we pass FibSimple an 8 value, we know that every time the result will be 13. We used this fact to leverage a caching technique called memoization to create the FibMemoized function.

Now, let's write some tests to see how effective MemoizeFcn is.

Since our fibTests structure has been defined in another test in our package, in chapter1/_01_fib/ex1_test.go, we don't need to define it again. This way, we only define the test table once, and we're able to reuse it in subsequent Fibonacci function implementations to get a reasonable apples-to-apples comparison of each solution.

Here's the basic unit test for the FibMemoized function:

func TestMemoized(t *testing.T) {
   for _, ft := range fibTests {
      if v := FibMemoized(ft.a); v != ft.expected {
         t.Errorf("FibMemoized(%d) returned %d, expected %d", ft.a, v, ft.expected)
      }
   }
}

It won't return an error unless there is a bug in our code.

That's one of the great things about running unit tests. You don't hear about them unless something breaks.

Note

We should write unit tests in order to:

  • Ensure that what you implement meets your feature requirements
  • Leverage testing to help you think about how best to implement your solution
  • Produce quality tests that can be used in your constant integration process
  • Verify that your implementation meets interface requirements with other parts of your application
  • Make developing integration tests easier
  • Safeguard your work against other developers, who might implement a component that could break your code in production

Here are the benchmark tests:

func BenchmarkFibMemoized(b *testing.B) {
     fn := FibMemoized
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

As before, in the FibSimple example, we examine the performance of computing the eighth number in the Fibonacci sequence:

func BenchmarkFibMemoized(b *testing.B) {
     fn := FibMemoized
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

func benchmarkFibMemoized(i int, b *testing.B) {
     for n := 0; n < b.N; n++ {
            FibMemoized(i)
     }
}

func BenchmarkFibMemoized1(b *testing.B)  { 
    benchmarkFibMemoized(1, b) }
func BenchmarkFibMemoized2(b *testing.B)  { 
    benchmarkFibMemoized(2, b) }
func BenchmarkFibMemoized3(b *testing.B)  { 
    benchmarkFibMemoized(3, b) }
func BenchmarkFibMemoized10(b *testing.B) { 
    benchmarkFibMemoized(4, b) }
func BenchmarkFibMemoized20(b *testing.B) { 
    benchmarkFibMemoized(20, b) }
func BenchmarkFibMemoized40(b *testing.B) { 
    benchmarkFibMemoized(42, b) }

As before, we carry out a test calling FibMemoized, using 1, 2, 3, 4, 20, and 42 as input.

Here's the complete listing for the FibChanelled function:

package fib

import "testing"

func TestChanneled(t *testing.T) {
     for _, ft := range fibTests {
            if v := FibChanneled(ft.a); v != ft.expected {
                   t.Errorf("FibChanneled(%d) returned %d, expected %d", ft.a, v, ft.expected)
            }
     }
}

func BenchmarkFibChanneled(b *testing.B) {
     fn := FibChanneled
     for i := 0; i < b.N; i++ {
            _ = fn(8)
     }
}

func benchmarkFibChanneled(i int, b *testing.B) {
     for n := 0; n < b.N; n++ {
            FibChanneled(i)
     }
}

func BenchmarkFibChanneled1(b *testing.B)  { 
    benchmarkFibChanneled(1, b) }
func BenchmarkFibChanneled2(b *testing.B)  { 
    benchmarkFibChanneled(2, b) }
func BenchmarkFibChanneled3(b *testing.B)  { 
    benchmarkFibChanneled(3, b) }
func BenchmarkFibChanneled10(b *testing.B) { 
    benchmarkFibChanneled(4, b) }
func BenchmarkFibChanneled20(b *testing.B) { 
    benchmarkFibChanneled(20, b) }
func BenchmarkFibChanneled40(b *testing.B) { 
    benchmarkFibChanneled(42, b) }

We performed twooptimizations on our original Fibonacci sequence logic using a caching technique and Go's concurrency features. We wrote both the optimization implementations. More optimizations are possible. In some cases, optimization techniques can be combined to produce even faster code.

What if all we had to do was write a simple recursive version and then when we compiled our Go code, the Go compiler would automatically generate object code with performance optimizations?

Note

Lazy evaluation: An evaluation strategy that delays the evaluation of an expression until its value is needed, which improves performance by avoiding needless calculations.

 

A journey from imperative programming to pure FP and enlightenment


Let's take a journey from imperative to a pure functional way of programming a sum function. First, let's look at the imperative sum function:

funcSumLoop(nums []int) int {
       sum := 0
for _, num := range nums {
              sum += num
       }
return sum
}

The integer variablesumchanges or mutates over time;sumis not immutable.There are no for loops or mutating variables in pure FP.

So, how can we iterate through a series of elements using pure FP? We can do this using recursion.

Note

Immutable variable: A variable whose value is assigned during runtime and cannot be modified.

Note that Go does have constants, but they differ from immutable variables in that values are assigned to constants at compile time, rather than at runtime:

funcSumRecursive(nums []int) int {
if len(nums) == 0 {
return 0
}
return nums[0] + SumRecursive(nums[1:])
}

Notice that the last line of the preceding SumRecursive function calls itself: SumRecursive(nums[1:]) . That's recursion.

Benchmark test for the imperative SumLoop function

We have heard that recursion in Go can be slow. So, let's write some benchmark tests to check it out. First, let's test the performance of the basic imperative function SumLoop:

func benchmarkSumLoop(s []int, b *testing.B) {
for n := 0; n < b.N; n++ {
              SumLoop(s)
       }
}

func BenchmarkSumLoop40(b *testing.B) { benchmarkSumLoop([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }

Results: It took 46.1 ns/op.

Benchmark test for the SumRecursive function

Now that we know how long the imperative function SumLoop takes, let's write a benchmark test to see how long our recursive version, namely SumRecursive, would take:

funcbenchmarkSumRecursive(s []int, b *testing.B) {
for n := 0; n < b.N; n++ {
              SumRecursive(s)
       }
}

func BenchmarkSumRecursive40(b *testing.B) { benchmarkSumRecursive([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}, b) }

Results: It took178 ns/op.

Tail call recursion is faster in languages such as Prolog, Scheme, Lua, and Elixir, and the ECMAScript 6.0-compliant JavaScript engines embrace the pure functional style of programming. So, let's give it a shot:

funcSumTailCall(vs []int) int {
if len(vs) == 0 {
return 0
}
return vs[0] + SumTailCall(vs[1:])
}

Results of the benchmark test: It took192 ns/op.

Note

TCO: A tail call is where the last statement of a function is a function call. An optimized tail call has been effectively replaced with a GoTo statement, which eliminates thework required to set up the call stack before the function call and restore it afterward.

We could even use GoTo statements to further speed up the tail call recursion, but it would still be three times slower than the imperative version.

Why? This is because Go does not provide pure FP support. For example, Go does not perform TCOs, nor does it provide immutable variables.

A time of reckoning

Why would we want to use pure FP in Go? If writing expressive, easy-to-maintain, and insightful code is more important than performance, then perhaps.

What are our alternatives? Later, we'll look at some pure FP libraries that have done the heavy lifting for us and have made strides toward being more performant.

Is that all there is to functional programming in Go? No. Not by a long shot. What we can do with FP in Go is currently partially limited by the fact that the Go compiler currently does not support TCO; However, that may change soon. For details see the How to Propose Changes To Go section in the Appendix.

There is another aspect to functional programming that Go fully supports: function literals. And as it turns out, that is the single most important characteristic that a language must have to support FP.

Note

Function literals: These are functions that are treated as first-class citizens of a language, for example, any variable type, such as int and string. In Go, functions can be declared as a type, assigned to variables and fields of a struct, passed as arguments to other functions, and returned as values from other functions. Function literals are closures, giving them access to the scope in which they are declared.When function literals are assigned to a variable at runtime, for example, val := func(x int) int { return x + 2}(5), we can call that anonymous function a function expression. Function literals are used in lambda expressions along with currying. (For details about lambda expressions, see Chapter 10, Functors, Monoids, and Generics.)

A quick example of a function literal

See that {ret = n + 2} is our anonymous function/function literal/closure/lambda expression.

Our function literal:

  • Is written like a function declaration, but without a function name following the func keyword
  • Is an expression
  • Has access to all the variables available in its lexical scope (n in our case)
package main

func curryAddTwo(n int) (ret int) {
defer func(){ret = n + 2}()
return n
}

func main()  {
   println(curryAddTwo(1))
}

The output is as follows:

3

Note that we used the defer statement to delay the execution of our function literal until after its surrounding function (curryAddTwo) is returned. Since our anonymous function has access to all the variables in its scope (n), it can modify n. The modified value is what gets printed.

 

Summary


When testing pure functions, we simply pass input arguments and verify the results. There is no environment or context to set up. There is no need for stubs or mocks. There are no side effects. Testing could not be easier.

Pure functions can be parallelized for performance gains in a horizontally scaled, multi-CPU environment. However, given that Go has not yet been optimized to support pure functional programming, a pure FP implementation in Go might not meet our performance requirements. We won't let that hinder us from leveraging Go's many effective non-pure functional programming techniques. We've already seen how we can gain performance by adding caching logic and leveraging Go's concurrency features. There are many functional patterns that we can use, and we'll soon see how. We'll also see how we can leverage them to meet stringent performance requirements.

In the next chapter, you'll learn about high-order functions as we explore different ways to manipulate collections using FP programming techniques.

 

About the Author

  • Lex Sheehan

    Lex Sheehan has a B.S. in Computer Science from Auburn University, resides in Atlanta, GA, and works as a senior software engineer with over 20 years of experience. He has a deep understanding of functional programming (FP). After using FP techniques in Ruby, Scala, JavaScript, Haskell, and Java, and writing an article about FP in Go, he decided it was time to write a book about it.

    Lex worked for IBM Software Group and IBM Global Business Services, designing and building various enterprise business systems. He is the author of eight US patents (IT security and data transformations) and he writes a blog titled Application Development with Lex Sheehan.

    Lex has turned his attention to distributed systems programming and crypto economics. He is currently leveraging his background in Go and passion for blockchain technologies to build a privacy layer for the Ethereum (and other) blockchains.

    Lex is available to consult and meet with your CTO and/or provide in-house training on the information in this book and related technologies.

    Browse publications by this author

Latest Reviews

(12 reviews total)
Easy to download the right book formats
Ouvrage très clair et complet
Utterly useless book. I think the author just mixed two buzzwords together to have a book that would sell for the title alone.

Recommended For You

Book Title
Unlock this full book FREE 10 day trial
Start Free Trial