An Introduction to Functional Programming

What is Functional Programming?

• Based on the lambda calculus (by Alfonzo Church) which predates computers!

It depends on who you ask!

A more involved answer depends on whether we're talking about pure or impure FP.

Impure FP

Pure FP

Pure FP

Referential What-Now?

An expression is called referentially transparent if it can be replaced with its corresponding value without changing the program's behavior.

This is actually a consequence of using pure functions.

So What's a Pure Function?

• Gives the same output for a given set of inputs
• Has no side effects

OK Fine, What's a Side Effect?

It's when a function has an observable effect besides returning a value.

Examples include

• Any I/O (reads/writes)
• Modifying a variable

FP Proponents Say Side Effects Bad!

In the presence of side effects, a program's behaviour may depend on history; that is, the order of evaluation matters.

Understanding and debugging a function with side effects requires knowledge about the context and its possible histories.

FP (Impure) Can Be Done In Any Language

But that language should really have support for first class functions.

This means that functions are values like any other and can therefore be passed as arguments to other functions or returned from functions.

First-Class Function Examples: JavaScript

setTimeout(function() {
  console.log("hello");
}, 3000);

undefinedhello

var greeter = function(greeting) {
  return function(name) {
    console.log(greeting + ", " + name);
  };
}
var helloGreeter = greeter("Hello")
helloGreeter("FP fans!")

Hello, FP fans!
undefined

First-Class Functions Enable Higher-Order Functions

// PHP
function map(callable $f, array $l) {
  $result = [];
  foreach ($l as $v) {
    $result[] = $f($v);
  }
  return $result;
}

$inc = function($i) {
  return $i + 1;
};
map($inc, [1, 2, 3]);
// [2, 3, 4]

FP Is Also Often Characterized By Use Of Recursion

# Python
def factorial(n):
  return 1 if (n == 0) else n * factorial(n - 1)

return factorial(5)

120

Versus Imperative Programming

Functional Programming Is An Example of the Declarative Paradigm

• It is based on the use of expressions or declarations
• contrasts with the imperative paradigm (the use of statements to change program state)

Example: imperative

# Python
chars = ['a', 'b', 'c']
upper_chars = []
for c in chars:
  upper_chars.append(c.upper())

return upper_chars

['A', 'B', 'C']

Example: functional

# Python
chars = ['a', 'b', 'c']
upper_chars = [c.upper() for c in chars]

return upper_chars

['A', 'B', 'C']

Example: expressions vs. statements

In imperative languages, if / else is a statement:

// Java
String msg = "";
if (isMoving) {
  msg = "We're moving!";
} else {
  msg = "We're stopped.";
}

In functional languages, it's an expression.

// Scala
val msg: String = if (isMoving)
                    "We're moving!"
                  else "We're stopped."

Example: Factoring

// Python
in1 = read("some-file.txt")
write("some-file.txt", in1 + "new stuff.")
in2 = read("some-file.txt")

-- Haskell
doIt = do
  in1 <- readFile("some-file.txt")
  writeFile("some-file.txt", in1 ++ "new stuff.")
  in2 <- readFile("some-file.txt")
  return in2

-- Haskell
readSomeFile = readFile("some-file.txt")
doIt = do
  in1 <- readSomeFile
  writeFile("some-file.txt", in1 ++ "new stuff.")
  in2 <- readSomeFile
  return in2

What is it Good For?

It can give us:

• Hack-proof code?
• Property-based testing (Quickcheck)
• Computer-assisted optimizations
• Computer-assisted parallelization
• Memoization potential

Whole classes of bugs become impossible.

Uses in Industry

• Facebook's Spam Filters Written in Haskell
• WhatsApp Written in Erlang
• Some of Twitter Written in Scala
• Jane Street uses OCaml
• Github uses Haskell for "Semantic"

Why Github Uses Haskell for Semantic

"it's worth mentioning that Semantic, as a rule, does not encounter runtime crashes"

Why Github Uses Haskell for Semantic

"null pointer exceptions, missing-method exceptions, and invalid casts are entirely obviated, as Haskell makes it nigh-impossible to build programs that contain such bugs."

Why Github Uses Haskell for Semantic

"the fact that the Semantic Code team spends the majority of its time working on features rather than debugging production crashes is truly remarkable—and this can largely be attributed to our choice of language."

Start Using It Today!

• Use higher-order functions instead of for loops
• Make data structures immutable

Questions