Functional programming
with Elixir

Daniel Perez
danhper
CTO@Claude Tech

http://bit.ly/elixir-fp-intro

Today's topic

Functional programming
with Elixir

Today's topic

Functional programming
with Elixir

Outline

1. Overview of the functional paradigm
2. Elixir functional programming features
3. State management in Elixir

Functional paradigm

Programming paradigm

A "way of programming"

• Way of reasonning
• Way of structuring code

A few programming paradigms

• Imperative programming (C, Fortran, Basic)
• Functional programming (Elixir, Haskell, ML)
• Object oriented programming (SmallTalk, Java)
• Many others: process oriented, logic

Multi paradigms

A lot of language support multiple programming paradigms
e.g. Scala supports imperative, functional, object oriented

A lot of languages support some functional features
e.g. High order functions are used in many languages

Imperative programming

• Focus on the "how"
• Program is built by mutating state
• Conditions, loops and functional calls for control flow

Functional programming

• Set of transformations through functions
• Transformations instead of mutations
• Control flow involves recursion

Functional programming

Definition

Programming based on transformations through functions

Merits of functional programming

• Easier to reason about
• Needs less context to understand
• Plays well with concurrent programming

Unsuited for functional programming

Tasks with a lot of mutations are not appropriate for FP

• Large data structures
• Many mutations in the data structures

Matrix operations is a good example

Overview of functional features in Elixir

• Pattern matching
• Recursion
• High order functions
• Immutable data structures

Pattern matching

What is pattern matching?

Matching a source expression with a target expression

1. Match the target with the source
2. Bind the source values to the target variables

Match operator

In Elixir = means "match", not "assignment"

iex(1)> a = 1
1
iex(2)> a
1
iex(3)> 1 = a
1
iex(4)> 1 = 1
1
iex(5)> 2 = a
** (MatchError) no match of right hand side value: 1

Match operator

iex(1)> a = 1
1
iex(2)> [x] = [2]
[2]
iex(3)> x
2
iex(4)> %{key: value} = %{key: "value", other: "other"}
%{key: "value", other: "other"}
iex(5)> value
"value"

Match context

Semantic changes depending on the context

• Variable name in normal context returns its value
• Variable name in match context will be bound

Different match contexts

# match operator
def match_op_match_context(value) do
  {a, b} = value
  a + b
end

# case expression
def case_match_conext(value) do
  case value do
    {a, b} -> a + b
  end
end

# function clause
def func_match_context({a, b}), do: a + b

Enough to implement if/else

case x < 1 do
  true -> "if branch"
  false -> "else branch"
end

Matching with guards

Using predicates when pattern matching, replacing the need for else if

def status(age) when age < 18, do: "child"
def status(age) when age < 65, do: "adult"
def status(age), do: "senior"

Check docs for usable expressions

Pinning variables

The following is a common pattern

case value do
  a when a == some_variable -> do_something()
  _ -> do_something_else()
end

case value do
  ^some_variable -> do_something()
  _ -> do_something_else()
end

Pattern matching order of evaluation

Match patterns are evaluated simultaneously
therefore the following will not work

def published?(platform, %{^platform => %{state: "published"}}), do: true
def published?(_platform, _info), do: false

Recursion

Recursive function

A function that directly
or indirectly calls itself

Recursive functions usually have a

• base case: the case where the function stop recursing
• recursion case: the case where the function keep recursing

The sum function

• When list is empty, return 0
• When list is not empty, return current_value + sum(rest_of_the_list)

which translates into

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)

Execution of the sumfunction

The result of the recursive call is not enough to compute the function final result

sum([1, 2, 3])
1 + sum([2, 3])
1 + 2 + sum([3])
1 + 2 + 3 + sum([])
1 + 2 + 3 + 0
1 + 2 + 3
1 + 5
6

Stack increases at each iteration

Tail recursion

Make the recursive call the last expression of the function

Non tail-recursive

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)

Tail-recursive

def sum(list), do: do_sum(list, 0)
defp do_sum([], acc), do: acc
defp do_sum([head | tail], acc), do: do_sum(tail, acc + head)

Tail call optimization

Function calls normally accumulate on the stack
Tail calls optimization avoids increasing the size of the stack when a function call is a tail call

Normal function call

All the function calls stay in the stack

defmodule WithStack do
  def foo(), do: "foo" <> bar()
  def bar(), do: "bar" <> baz()
  def baz(), do: raise "error"
end

try do
  WithStack.foo()
rescue
  _ -> :erlang.get_stacktrace()
end
# [{WithStack, :baz, 0, [file: 'iex', line: 6]},
#  {WithStack, :bar, 0, [file: 'iex', line: 5]},
#  {WithStack, :foo, 0, [file: 'iex', line: 4]},
#  {:erl_eval, :do_apply, 6, [file: 'erl_eval.erl', line: 670]},
#  ...
# ]

Tail function calls

Tail calls do not remain in the stack

defmodule NoStack do
  def foo(), do: bar()
  def bar(), do: baz()
  def baz(), do: raise "error"
end

try do
  NoStack.foo()
rescue
  _ -> :erlang.get_stacktrace()
end
# [{NoStack, :baz, 0, [file: 'iex', line: 17]},
#  {:erl_eval, :do_apply, 6, [file: 'erl_eval.erl', line: 670]},
#  ...
# ]

Tail call optimization

The following code will not stack overflow

def sample_infinite_loop() do
  wait_for_something()
  do_something()
  sample_infinite_loop()
end

High order functions

High order functions motivation

We want to abstract common patterns

Sum function

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)

Count function

def count([]), do: 0
def count([head | tail]), do: 1 + sum(tail)

Abstracting common patterns

sum and count both:

• recurse on a list
• accumulate a result by applying a function

This is often called reduce or fold

First class functions

Functions can be used as normal values

• saved into a variable
• used as function parameters
• used as return value

Many languages implement this feature

Implementing a high order function

The reduce function could be implemented as follow

def reduce([], initial_value, _f), do: initial_value
def reduce([head | tail], initial_value, f) do
  f.(head, reduce(tail, initial_value, f))
end

sum and count can then be implemented as

def sum(list), do: reduce(list, 0, fn (elem, acc) -> elem + acc end)
def count(list), do: reduce(list, 0, fn (_elem, acc) -> 1 + acc end)

Common high order functions

• map: applies a function on all elements of a list
• filter: filters a list using a predicate function
• reduce: reduces a list to a scalar using a binary function

Immutability

Mutable vs Immutable

regarding data structures

• operations on a mutable structure will modify it
• operations on an immutable structure will return a new updated one

Mutability in Elixir

All data structures in Elixir are immutable

list = [1, 2, 3, 4]
List.delete(list, 3)# returns a new list

map = %{foo: "bar"}
Map.put(map, :bar, "baz") # returns a new map

conn = get_conn()
halt(conn) # returns a new conn

Common mistake

When getting started, is easy to forget about immutability

def some_plug(conn) do
  unless authorized?(conn) do
    conn
    |> put_status(403)
    |> halt()
  end
  conn
end

A stateful world

Handling state

• a lot of real world task need state
• structures cannot be mutated
• we need a way to model the state

State in Elixir

• Elixir is immutable
• Use Agent when you need state
• Agent is a wrapper around GenServer
• What is going on in GenServer?

A short outline

• (re)view OTP building blocks
• implement simple stateful server
• generalize our stateful server

Language concurrency builtins

• spawn
• send
• receive
• monitor
• link

Spawning a process

pid = spawn fn ->
  IO.puts "Hello from #{inspect(self())}"
end
:timer.sleep(10)
Process.alive?(pid) |> IO.inspect # false

Communicate with a process

pid = spawn fn ->
  receive do
    {:ping, sender} -> send(sender, :pong)
  end
end
:timer.sleep(10)
Process.alive?(pid) # true
send(pid, {:ping, self()})
flush() # :pong
Process.alive?(pid) # false

Creating a server

defmodule PingServer do
  def start do
    spawn(__MODULE__, :loop, [])
  end

  def loop do
    receive do
      {:ping, sender} ->
        send(sender, :pong)
        loop()
    end
  end
end

Stateful arguments

def loop(some_int) do
  receive do
    {:add, value} ->
      loop(some_int + value)
  end
end

Creating a Stack server

defmodule StackServer do
  def loop(state) do
    receive do
      {:push, value} ->
        new_state = [value | state]
        loop(new_state)
      {:pop, sender} ->
        [value | new_state] = state
        send(sender, value)
        loop(new_state)
    end
  end
end

push function

defmodule StackServer do
  def push(pid, value) do
    send(pid, {:push, value})
  end
end

Making pop synchronous

defmodule StackServer do
  def pop(pid) do
    ref = make_ref()
    send(pid, {:pop, self(), ref})
    receive do
      {^ref, value} -> value
    end
  end

  def loop(state) do
    receive do
      {:pop, sender, ref} ->
        [value | new_state] = state
        send(sender, {ref, value})
        loop(new_state)
    end
  end
end

Making the server generic

• A server has a state
• A server uses a main loop
• A server can handle sync/async requests

Refactoring our main loop

defmodule ClumsyGenServer do
  def loop(module, state) do
    receive do
      {:async, message} ->
        {:noreply, new_state} = module.handle_cast(message, state)
        loop(module, new_state)
      {:sync, message, sender, ref} ->
        {:reply, reply, new_state} =
          module.handle_call(message, {sender, ref}, state)
        send(sender, {ref, reply})
        loop(module, new_state)
    end
  end
end

Extracting logic of push and pop

defmodule ClumsyGenServer do
  def cast(pid, message) do
    send(pid, {:async, message})
  end

  def call(pid, message) do
    ref = make_ref()
    send(pid, {:sync, message, self(), ref})
    receive do
      {^ref, reply} -> reply
    end
  end
end

Rewriting push and pop

defmodule StackServer do
  def init(state) do
    {:ok, state}
  end
  def pop(pid) do
    ClumsyGenServer.call(pid, :pop)
  end
  def push(pid, value) do
    ClumsyGenServer.cast(pid, {:push, value})
  end
  def handle_cast({:push, value}, state) do
    {:noreply, [value | state]}
  end
  def handle_call(:pop, _from, [head | rest]) do
    {:reply, head, rest}
  end
end