﻿ Real World Functional Programming

# Real World Functional Programming

## Mikael Lundin

### Email

mikael.lundin@valtech.se

litemedia.info

@mikaellundin

# Why functional programming?

• Code with less side effects
• Code that is more expressive
• Code that is easy to parallelize

This presentation will show you how you can become a better programmer by learning functional programming and using those concepts and constructs in your day to day work.

Most of my examples will be in C# but it should be comprehensible by any Java programmer also.

# Scenario: Average age

Calculate the average age in the assigned group
How can Pascal finish before Ada?

Let's use a scenario that we can come back to through the talk.

While you think about that I will talk about some of the history of functional programming.

# History

Alonzo Church

λ

It all began in the 1930's with Alonzo Church when he created the lambda calculus. He wanted to discribe the world in functions.

# Lambda Calculus

## With lambda calculus we define functions

`(λx.x*x) 9 = 9 * 9 = 81`

## Functions can be used as arguments

`(λx.λop.(op x x)) 9 (+) = 9 + 9= 18`
• This is a function that squares a number.
• We can call this with the number nine
• If you type out it, it will become 9 * 9
• The result is of course 81

The point here is the function and that we can reuse it with other arguments.

• Here's a function that takes two arguments, x and op. op is a function that operates on x and takes two arguments.
• We can call this with the number 9 and operation (+)
• This of course prints out as 9 + 9
• And the result is 18

# History

## List Processing Language (LISP)

### [1958] John McCarthy

`(fn arg1 arg2)`

## Simple computations

```						(+ 1 2)
-> 3```
```						(ceil 1.2)
-> 2```

LISP was created 1958 as the first functional language, at the same time as COBOL and Fortran two imperative programming languages.

LISP pioneered computer science paradigms that we still use today, tree data structures, dynamic typing and self hosting compiler.

# History: Lisp

## Calculate interest over years

```						(defun calc (amount year interest)
(if (= year 0)
amount
(calc
(+ amount (* amount interest))
(- year 1)
interest)
)
)```
```							(calc 200 3 0.1)
-> (calc 220 2 0.1)
-> (calc 242 1 0.1)
-> (calc 266.2 0 0.1)
-> 266.2```

Here's some code that will calculate interest for an amount of money over a couple of years in lisp. It reads like this

```							if year = 0 then
return amount
else
calc
amount + (amount * interest / 100)
year--
interest
```

# Recursion

Recursion: see recursion.

# History CHART

Lisp came 1958 right between the large imperative languages Fortran and Cobol. Most of the languages we use today derive from those two languages.

Scheme is a more formalized version of Lisp and it came about 1975 and became quite popular, especially in the academic world.

It's worth to notice Common Lisp, the standardization of Lisp in 1984 and how Haskell came out of Scheme in 1987. Haskell is a pure functional programming language, and that means that it does not allow side effects.

Caml that came out of ML and OCaml that came out of Caml is worth to notice. Objective Caml is what inspired F# that is the main functional programming language on the .NET platform today.

# Imperative programming?

Imperative programming includes state. You have a state and you modify it until you're satified with the result.

It's like making pancakes. You start with an empty bowl. You had flour, eggs, and milk. You take the contents and put it into a frying pan and after 2 minutes you have a pancake.

Imperative programming is having a state and mutating it into completeness.

# Imperative programming?

## How did Ada calculate average age?

```						int total = 0;
foreach (var personAge in group)
{
total = total + personAge;
}

var average = total / group.Count;```

Remember Ada and Pascal? They're going to calculate the average age of everyone in their group. Ada goes for a purely imperative approach. She sums up everyones age in the group and then divide with the number of people in the group.

It is very easy for our brains to understand imperative thinking because we have been schooled that way.

# Functional Programming

## Four concepts of functional programming

• Functional types
• Expressivity
• Immutable values
• Declarative programming

Pascal used a more functional way to solve the problem and managed to do so before Ada even though he had a four times larger group of people.

The four concepts of functional programming are Functional types, expressivity, immutable values and declarative programming. I will look into what these concepts are, and how Pascal can use them to complete the task.

# Functional Types

This is called a recursive type.

A functional type is a type that works well with functional programming paradigms. The most common is the linked list.

The linked list has two parts, a head and a tail. The tail is in itself a linked list. This makes the type recursive.

## What does the linked list look like in code?

```						interface ILinkedList<TItem>
{
bool IsEmpty { get; }

}```

How would a linked list definition look in code? Something like this where the type has a head, and a tail. You have a property to tell if the list is empty or not. It's all you need for this recursive type.

### More functional types

Pascal used the linked list functional type to structure his group.

Another common functional type is the binary tree. You use that for search and sorting algorithms.

In a functional language each function has a type. This makes it easier to use functions as values.

# Expressivity

## How do you express the problem?

```								Add everyones age together.
Divide by number of people.```
2. ### Pascal

```							for a group of people
total age is first persons age
added with rest of the group

average age is total age
divided by the group size```

The key to expressivity is how you express the problem. Ada tackles the problem as the entire group where as Pascal tries to solve the problem for the indiviual person.

# Pascal's problem

```						private AgeAndCount Total(ILinkedList<int> group)
{
if (group.IsEmpty)
{
}```

Returns two values ([age], [calculated group size])

```							var total = Total(group.Tail);

return new AgeAndCount(
total.Age + group.Head, // total age
total.Count + 1);       // total count
}```
```							var total = Total(group);
var average = total.Age / total.Count;```

We define the following

1. What happens when there's only one person in the group? Return that persons age with group size 1
2. For a group we express that the total age is first persons age + rest of the groups calculated age

We calculate the number of persons in the group at the same time as we calculate the age. Since we need to return two values form the calculation we uses another functional construct called Tuple. It is simply two values as one.

# Pascal's calculation

## This has enabled parallel calculation

Instead of counting from start to finish Pascal divided his problem into 8 subproblems

He told the first person in each column to calculate the ages and return the result to him.

# Expressivity

## Recursion in non functional languages

```					public long Aggregate(int i)
{
if (i == 0)
return 0;

return i + Aggregate(i - 1);
}```
`Aggregate(100); -> 100 + 99 + .. + 1 + 0`

C# has no tail recursion optimization

You should beware of recursing in non functional languages, because they do not optimize for recursion. When you write a recursion like this it will compile into function calls where as a functional language might optimize it into a while loop. This is called tail recursion optimization because extensive functional calls is expensive.

Make sure that you know that the depth has a limit before you start recursing in C#.

# Immutability

```						int total = 0;
foreach (var personAge in group)
{
total = total + personAge;
}

var average = total / group.Count;```

Ada's solution is dependent on the mutable variable `total`.

It's mutable values that makes parallelization so hard. If we we're to parallelize Ada's solution it would be necessary to share the mutable state "total" between different threads. This is the source of deadlocks and race conditions.

# Immutable values

## An immutable value cannot change

In FP you don't set variables, but bind values.
• Less side effects
• Enforces expressive problem solving

# Immutable values

## The .NET string class is immutable

```						// Immutable string
string title = "Real world";
title += " functional programming";```
```							// Substring creates a new string
string subTitle = title.Substring(11);```

We have immutable types in the .NET framework. String is immutable. If we add another string to a string, it will create a new string - not modify the existing.

String instance methods that manipulates the string always returns a new string instance.

# Immutable values

## Mutable vs. immutable in .NET

```						// Mutable list
var primes = new List<int>();
```							// Immutable DateTime
var date = DateTime.Now

Immutable leads to function chaining. No operation on datetime can ever return null

# Immutable values

## Create your own immutable types

• Only modify values through the constructor
• Changing a value, means creating a new instance
```					public class Person
{
public Person(string name, int age)
{
Name = name;
Age = age;
}

public string Name { get; private set; }

public int Age { get; private set; }

public Person IncrementAge(int years) { ... }
}```

Creating immutable types will help you code more functionally so you should make your types immutable where you can. In an immutable type you can't modify values without getting a new instance of the type.

In above example you will get a new Person instance when you want to increase the age of the Person.

# Declarative programming

```						int total = 0;
foreach (var personAge in group)
{
total = total + personAge;
}

var average = total / group.Count;```

Ada's describes how to do it - not declarative

Ada's problem solution focus on how to calculate the result. A declarative problem solution will focus on what we want instead of how to get it.

# Declarative programming

## In F# Pascal would solve it like this

`						let averageAge group =`
```							// Calculate the average
let average (totalAge, groupSize) =
totalAge / groupSize```
```							// Sum up total age
let rec ageAndCount = function
| [] -> 0, 0
| age :: group ->
let totalAge, groupSize = ageAndCount group
(age + totalAge, groupSize + 1)```
```						// What is the average of the total
average (ageAndCount group)```

In declarative programming we declare what, instead of how.

averageAge of group is -> call average with result from totalAgeAndCount of group

average is -> totalAge divided by groupSize

totalAgeAndCount is -> 0, 0 when group is empty first persons age + rest of the groups age and rest of the group size + 1

Like this we have declared what we want instead of how to get it. This method is declarative and very expressive.

# Declarative UI

```						// Create window
Form frmMain = new Form();

// Flow panel
FlowLayoutPanel pnlTopDown = new FlowLayoutPanel
{ FlowDirection = FlowDirection.TopDown};

// Create controls
Label lblTitle = new Label
{ Text = "Hello Valtech TECH Days!", Width = 200};
Label lblParagraph = new Label
{ Text = "This is not so declarative", Width = 200 };
Button btnClickMe = new Button
{ Text = "Click me" };

// Tie an event to the button
btnClickMe.Click += (o, e) =>
MessageBox.Show("There must be a more declarative way");

new Control[] { lblTitle, lblParagraph, btnClickMe});

// Display the form
frmMain.Show();```

Windows forms programming is an exellent example of UI programming that is not declarative. All the way you tell the computer how it should produce the desired UI.

# Declarative programming

## Example of a declarative UI

```						<div class="declarative-ui">
<h2>Declarative UI</h2>
<p>
We're describing
<em>what</em>
<em>how</em>
</p>
<button id="click-me">Click me</button>
</div>```

In HTML you tell the browser what it should display, and not how to do it. With the previous example of WinForms programming, it is interesting that XAML is declarative. Microsoft took windows programming from being imperative to declarative with the transformation from WinForms to WPF.

# Declarative programming

• Express the logic of a computation without describing its control flow
• Eliminate side effects
• Describe what computation should be performed and not how to compute it

Declarative programming should be independent on what order you declare things. A good example of this is XSLT style sheets where you define templates for rendering and it does not matter in what order you do things.

It eliminates side effects since you don't have any mutable state.

The trick is to define what instead of how.

# Recap

• Code with less side effects
• Code that is more expressive
• Code that is easy to parallelize

Using immutable values instead of mutating states causes less side effects that is a known source for bugs

Expressive code is easier to read as it states what is being done instead of how

If we want to make parallelization embarrassing, we should use functional programming

# More functionality

 F# Clojure Scala Monads Haskell Function composition Binary trees Tuples XSLT Erlang Currying Purity Partial functions

Things that didn't make it.

# Thank you!

## Resources

Thank you for listening. Go to my blog litemedia.info for more info. Read Tomas Petricek's book about functional programming. Learn a functional programming language.