Tuesday, September 19, 2017

Characteristics of a Functional Programming Language

Let’s start by looking at requirements for a pure Functional Programming (FP) language. In a Pure FP language, a function...
  • when given the same input parameters always returns the same results
  • has no side-effects
Sounds good, but why is it valuable? Side-effects is one of the biggest barriers to parallelizing our applications. Modern computers have multiple cores and cloud-native applications scale horizontally where copies of same app runs on multiple servers. The ability to run your application reliably in a cloud environment. How’s that for value?

A pure FP language also includes support for things like:
  • Tail Call Optimization
  • High Order Functions
  • First Class Functions
In order to accomplish pure functional programming, a language must treat functions as it does any other variable type. How can an immutable language have variables that “vary”? The way we accomplish this in an FP way is by creating new variables, rather than modifying existing ones. To see this in action, check out the Map function example in my book, Learning FP in Go.

Go is a multi-paradigm language that supports imperative, object-oriented, and functional programming styles. We could write a purely imperative program in Go or a purely functional program in Go. Go gives us the freedom to choose our programming style. That's one of the great things about Go and FP. It's not an all or nothing issue. We can migrate our code towards FP when and where it makes sense to do so.

To fully support pure FP, Go requires Tail Call Optimization (TCO) to handle production performance requirements. Since each time a recursive function calls itself a new block is added in the stack frame, we soon feel the sluggish effects of this Go compiler omission. To see how we can mitigate this issue check out the Reduce function example in my book, Learning FP in Go.

High Order Functions (HOF) take functions as arguments and/or returns functions as its result. HOFs allow us to chain our functions together in a readable manner with less code.

HOFs are arguably the focal point of any FP language, and after a quick look at FP characteristics we’ll study how we can exploit them in Go.

Characteristic Supported in Go? Description

Referential Transparency

Referential transparency means that our function expression f(x) and the results of evaluating our function are interchangeable. For example, 1 + 1 is always equals 2.  This means that we can cache the results of the first function invocation and improve performance.

Tip: If we can cache results from previous function calls then we have referential integrity.

Idempotence

Idempotence  means that we can call our function repeatedly and it will produce the same result each time.

No Side Effects

“No side effects” means that the only thing that occurs when we call a pure function is: 1) we pass in parameters and 2) we  get a result; Nothing else happens.

Tip1: If our function prints output it is impure.

Tip2: If any state/data changes anywhere else in our system as a result of calling our function then our function is impure.

Tip3: If our function has no return value then it is either impure or completely useless.

Immutable State

Immutable state means that a function when given the same input will always return the same output and will not have any observable side effects.

Currying

Currying is where we get a function that accepts x parameters and return a composition of x functions each of which take 1 parameter.  In FP, every function is a function of one argument.  For more details and a code example see my book, Learning FP in Go.

Closures

A closure is an inner function that closes over, i.e., has access to, variables in its outer scope.  See example below.

Recursion

Recursion is used by FP languages in place of loops where a function calls itself until an end condition is reached. In Go, every recursive call creates a call stack. Tail-call optimization (TCO) avoids creating a new stack by making last call in a recursion the function itself. Even though we can code recursively in Go without TCO, it’s just not practical because of poor performance. Note that recursion in pure FP languages are abstracted from sight by HOFs.

Partial Function Application

Giving a function fewer arguments than it expects is called Partial Function Application. Here, our function accepts a function with multiple parameters and returns a function with fewer parameters.  For more details and a code example see my book, Learning FP in Go.

Parametric Polymorphism

Parametric Polymorphism means "Generics”.  This is a style of datatype generic programming where we code our functions using non-specific data types.  For example, we can implement generic algorithms that work on collections of non-specific types. Generics provides code reuse, type safety and easy-to-read code. See Generics section below for a simple example.

Operator Overloading

Operator overloading, also known as “ad hoc polymorphism”, is a specific case of polymorphism, where different operators like +, = or == are treated as polymorphic functions and as such have different behaviors depending on the types of its arguments.

Type Classes

Type classes allow us to define functions that can be used on different types with a potentially different implementation for each type. Each class represents a set of types and is associated with a particular set of member functions. For example, the type class Eq represents the set of all equality types, which is precisely the set of types on which the (==) operator can be used. For more details and code examples (in Haskell) see my book, Learning FP in Go.

Hindley-Milner Type System

HM infers types without requiring any type definitions.  HM type systems support polymorphic types, where lists can contain items of different types.  If Go used HM, then the type of b would be inferred as “float64” below (rather than throwing the runtime error, “constant 1.8 truncated to integer”)

        a := 1
        b := a + 1.8

Use of Expressions

Declarative style, as opposed to Imperative, means that we write expressions, as opposed to step by step instructions. Tip: If we can call a function without using its return value then it’s impure.

First Class Functions

First Class Functions can be passed around as parameters and returned as values.

High Order Functions

High Order Functions can take functions as arguments and can return functions. For more details and a code example see my book, Learning FP in Go.

Tail Call Optimization

Tail Call Optimization makes recursive function calls performant.  A tail call happens when a function calls another as its last action. TCO acts like a GOTO statement.  Example:

  func f(x) {// some code;return g(x)}
The program does not need to return to the calling function when the called function g(x) ends b/c there is no executable code after that last line.  After the tail call, the program does not need any call stack information about g.  Without TCO the program will create a needless call stack for g;  A lot of recursive calls will cause a stack overflow.  With TCO, the recursive  program will be faster and consume far fewer resources.

Unit Type

A unit type has exactly a one value. It is also known as the identity. The unit for multiplication is 1, for addition is 0, for string concatenation is the empty string.

How many values can a type defined as a tuple of of type int contain? Infinite. (-∞, …, 0, 1, 2... ∞)

How many values can a type defined as the empty tuple contain? One. ()

The value of a unit type is that you can use it in places where we might otherwise return nil (or null). We return a unit when we don’t care what the value is. We don’t return nil, we return a value; the unit value. All functions return values; No more null pointer exceptions!

The 's indicate that the FP characteristic exists in Go.

The 's indicate that characteristic can be achieved with some effort in Go.

The 's indicate that this FP characteristic is missing or is difficult or not possible to achieve without a major upgrade to the Go compiler or without using another technology in tandem with Go.


Let’s look closer at a few characteristics of functional programming in Go...

A closer look at f(x)

Let's examine a basic function definition. "f" is the function name. "x" is the input value. Another name for "x" is the input parameter.

The entire expression "f(x)" represents the output value.


If f(x) = x + 1, then we know that every time we input the value 2, 3 will always be the output value. In other words, a pure functional program always produces consistent results and never has any side effects.
cars := LoadCars()
for _, car := range cars.Filter(ByHasNumber()).
      Filter(ByForeign()).
      Map(Upgrade()).
      Reduce(JsonReducer(cars), Collection{}) {
      log.Println(car)
}

Output:

{"car": {"make": "Honda", "model": "Accord ES2 LX"}}
{"car": {"make": "Lexus", "model": "IS250 LS"}}
{"car": {"make": "Lexus", "model": "SC 430 LS"}}
{"car": {"make": "Toyota", "model": "RAV4 EV"}}
How much more code would be required if we were to implement the for loops, error checking, and other code ceremony that is typically required when coding Go in the typical imperative style of programming?

Instead of telling Go how to filter, map, and reduce our collection, we declare what we want to accomplish. In my book, Learning FP in Go, we implement the Filter, Map, and Reduce functions. What if the Go standard library provided these basic FP functions for us?

Should we expect Go to provide HOF implementations for cars? No. That would not be reasonable. A car is a domain specific thing. What feature do some other FP languages have that support code reuse that we can use for our domain entities? (Generics)

Generics

Parametric Polymorphism means "Generics". A generic function or a data type can be written so that it can handle any data value using the same logic without having to cast the value to a specific data type. This greatly improves code reuse.

Below, is a C# code example of a generic IsEqual implementation. The generic IsEqual function will accept any type (that implements Equals). We could pass IsEqual integers and strings by simply indicating the type "T" during runtime at the moment that IsEqual is executed. We could easily extend IsEqual to support domain entities like cars.
namespace Generics
{
  private static void Main() {
     if(Compute.IsEqual(2, 2)) {
           Console.WriteLine("2 isEqualTo 2");
        }
     if(!Compute.IsEqual("A", "B")) {
           Console.WriteLine("A is_NOT_EqualTo B");
        }
  }
   public class Compute {
       public static bool IsEqual(T Val1, T Val2) {
           return Val1.Equals(Val2);
       }
   }
}


Currently, to do this in Go we would have to use the empty interface and perform a type conversion. It's that type conversion that will cause the performance hit that usually makes this sort of generics handling in Go impractical.

First class functions

First class functions allow us to make new functions by providing our base functions with functions parameters. Below, our base function is Filter. By passing ByMake("Toyota") to Filter we remove most car items from our collection, leaving only Toyotas.

cars := Filter(ByMake("Toyota"))
We also have the ability to transform any function that works on single elements into a function that works on lists by wrapping it with the Map function. Without our new functional style of programming we might be tempted to implement a for loop and apply the fmt.Sprintf transformation on each individual car as follows:

for _, car := range cars {
      thisCar := fmt.Sprintf("%s %s", car, map[string]string{
             "Honda": "LX",
             "Lexus": "LS",
             "Toyota": "EV",
      }[GetMake(car)])
      mappedCars = append(mappedCars, thisCar)
}
Instead, we can simply pass the Upgrade function to Map as we compose our data transformation:
Filter(ByMake("Toyota")).Map(Upgrade())
We no longer need to write for loops that manipulate arrays because we can call Map inline. HOFs can greatly reduce the time that it takes to develop complex logic. We can quickly compose smaller, task-specific functions into solutions for complex business logic much faster, with less scaffolding code, which means we’ll have fewer bugs to fix. Our functions are in essence reusable building blocks.

HOFs are independent , making them easy to reuse, refactor, and reorganize in our code base. This makes our programs more flexible and resilient to future code changes. More readable code, faster implementation, fewer bugs… The benefits of FP are adding up!

Closure

A Closure is a function that closes over variables in its outer scope. We really need an example to understand that statement! Here's a good one:
func addTwo() func() int {
      sum := 0
      return func() int {  // anonymous function
             sum += 2
             return sum
      }
}

func main() {
      twoMore := addTwo()
      println(twoMore())
      println(twoMore())
}

Output:

2
4
The closure above is formed by the addTwo function. Inside addTwo, both sum and the anonymous function are declared in the same lexical scope. Since addTwo closes over both sum and the anonymous function and because sum was declared before the anonymous function, the anonymous function always has access to, and can modify, the sum variable. As soon as addTwo is assigned to twoMore, addTwo’s anonymous function gets access to the sum variable and holds on to it as long as the application continues to run.

Being able to pass around context is powerful. In the Learning FP in Go book, we’ll look at a practical example where we create an application context, e.g., database connection, logger, etc. at application startup and pass that context around where needed throughout our application.

Immutable state

Immutable state means that a function when given the same input will always return the same output and will not have any observable side effects. How is that a benefit? You may ask. Let’s see...

Side effects are one of the biggest barriers to parallelizing our programs because we can't reason about changes to a global state. If we manage state outside of our imperative functions and must perform steps in a particular order, how do we accomplish our sequenced tasks across multiple servers in our cluster? That’s not an easy problem to solve.

Pure functions, on the other hand, do not require access to shared memory and cannot create race condition because they have no side effects. The simplicity and performance gains of relatively easily running our code concurrently provide more reason to design our applications using the FP paradigm.

Use of expressions

Use of expressions (rather than statements) means that in FP, we pass a value to a function that typically transforms it in some way and then returns a new value. Since FP functions have no side effects, an FP function that does not return a value is useless and a sign of code smell. In Chapter 1 of Learning FP in Go, we saw that imperative programming focuses on the step-by-step mechanics of how a program operates. Whereas, in declarative programming we declare what we want the results to be.

Imperative:

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

Declarative:

fmt.Printf("Found? %v", cars.contains("Blazer"))
That’s less code that is easier to read.

Summary

In this article, we looked at the requirements and characteristics of Functional Programming and illustrated a few using Go implementations such as:
  • Functional Composition
  • High Order Functions
  • Closures
  • Expressions
FP is a programming style that is declarative. It is more readable and usually requires much less code than other imperative or object oriented implementation options.

To find out more about why FP is well suited for cloud deployments and how FP helps us manage the complexity of software development, get a copy of Learning Functional Programming in Go.

p.s.

I hope this book preview answered a few functional programming questions you might have had. I also hope you consider purchasing a copy of my book. It has a few thing that you likely won't find anywhere else, like:
  • A visual, example laden introduction to Category Theory (*)
  • A working understanding of Lambda Expressions (in Go)
  • A better dependency management using Glide (and a dash of Bash Kung Fu)
  • A children's story about a duck's life (in Go)
  • A plethora of real world examples and illustrations
  • A unique empowerment to build better, more composable applications in today's distributed environments

A visual, example laden introduction to Category Theory (*)

This is my book's largest chapter (over 100 pages). My goal in this chapter is to deliver a deep appreciation for category theory with as many code examples, diagrams, tables and illustrations as it takes for you to really "get it".

We'll discover fundamental truths. We'll see and understand the connection between category theory, logic, lambda calculus, flow based programming and the world around us. We'll learn how to turn software development complexity into simplicity via (de)composition. (With code examples in Go and a few in Haskell, Javascript and Ruby.)

Would you like to understand the following?
A monad is just a monoid in the category of endofunctors, what's the probleⅿ?
Last but not least, we'll learn to appreciate our elementary, middle school and high school math classes. They weren't useless after all! (Read my book and send your old math teachers some love).

p.s.s.

Thank you for buying my book!



This work is licensed under the Creative Commons Attribution 3.0 Unported License.