Functional Programming Patterns

class: roomy big-h1 no-footer bgs-contain
background-image: url(/slides/fp-patterns/lambda.svg)

.ff-fancy[
# Functional Programming Patterns]

.right[## Abhinav Sarkar
#### Functional Conf 2022
]

???

- ask about java and functional programming experience

---
class: no-footer thank-you center

# Abhinav Sarkar
### @[abhin4v](https://twitter.com/abhin4v)
Senior software engineer 
Google Search

???

---
class: title fogscreen
background-image: url(/slides/fp-patterns/complex.jpg)

# Complexity

.footer[
  - Credit: [flic.kr/p/2bSUnWZ](https://flic.kr/p/2bSUnWZ) (CC BY-SA 2.0)
]

???

- what is the biggest challenge for programmers these days?
- it's complexity
- thanks for Moore's law and improvements in compilers and runtimes, we don't need to care about nitty-gritties of performance of most of the programs we write anymore
- and thanks to the same, the computers are running the world now.
- which has lead to more and more complex things being implemented in software.

---
# Complexity

- Complexity is the degree of entanglement in software.
- Complex programs are hard to understand and hence hard to change.

???

- I bet you have seen complex codebases
- These are generally codebases which no one wants to touch
- Complex codebases are caused by large number of interactions between different parts of the codebase. As the number of interacting parts increases, the interactions between them increases exponentially, giving rise to an entangled codebase.
- Development of these projects get slower and slower and finally you do a massive rewrite hoping that it'll make working on these projects fast again
- Fred Brooks discussed complexity in great details in his 1986 paper titled "No Silver Bullet – Essence and Accident in Software Engineering".
- In the paper, Fred classifies complexity in two categories: Essential and Accidental.

---
# Essential Complexity

- Required for solving the problem at hand.
  - Like implementing Breadth-first search algorithm for finding the shortest path.
  - It is unavoidable regardless of which tools and frameworks you use.

---
# Accidental Complexity

- Not inherent to the problem; brought while writing the program.
--

- Choose to use _C_? Now you have to manage memory too.
--

- Choose to use _Java_? Now you have to model everything as objects.
--

- Choose to use _node_? Now you have to deal with 3 million dependencies.

---
class: img-caption

![](/slides/fp-patterns/rube-goldberg-machine.jpg)

Rube Goldberg Machine

.footer[
  - Credit: [flic.kr/p/6tm2ny](https://flic.kr/p/6tm2ny) (CC BY-SA 2.0)
]

???

- rude goldberd machine
  - fragile and opaque
  - things break easily and mysteriously when trying to make changes
- good programmers seek to reduce accidental complexity as much as possible
- i claim that functional programming helps in reducing accidental complexity as compared to OOP

---
class: title fogscreen
background-image: url(/slides/fp-patterns/circuit.jpg)

# Functional Programming

.footer[
  - Credit: [flic.kr/p/8QcS2v](https://flic.kr/p/8QcS2v) (CC BY 2.0)
]

---
# Functional Programming

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

---
# Salient Aspects

- pure functions
???
- a function is pure if it's output depends only on it's input and nothing else
- easier to reason about and debug because they don't depend on mutable state
- easier to test because there are no dependencies
- §
--

- first-class and higher-order functions
???
- first-class functions can be passed to and returned from functions
- functions which take or return functions are called higher-order functions
- §
--

- no/constrained mutable state
???
- mutable state leads to coupling between components
- mutable state requires synchronization when working with multiple threads
- FP eschews mutable state
- FP languages are immutable by default and mutability is opt-in by using specific constructs
- §
--

- no/constrained side-effects
???
- side effects are any changes in state that do not depend on the function inputs
- IO is side effect too
- code with side effects is harder to reason about
- FP languages provide specific constructs to constrain side effects
- §
--

- lazy evaluation
???
- some FP languages come with lazy evaluation
- notice that a static type system, although prevalent in FP languages, is not a requirement.

---
class: no-heading

```javascript

let meetups =
  [{name: 'JS', isActive: true, members: 700},
   {name: 'Clojure', isActive: true, members: 900},
   {name: 'Java', isActive: false, members: 600},
   {name: 'Go', isActive: true, members: 500}];

let totalMembers = meetups
  .filter(m => m.isActive)
  .map(m => m.members)
  .reduce((acc, m) => acc + m, 0);
```

---
class: title fogscreen
![](/slides/clojure-concurrency-you/Clojure.png# absolute t-0 center w-75pct)

# Clojure

.footer[
  - Credit: [commons.wikimedia.org](https://commons.wikimedia.org/wiki/File:Clojure_logo.svg) (Public domain)
]
---
# Clojure
--

- dynamically typed
--

- functional programming language
--

- from the Lisp family
--

- runs on JVM

---
# Clojure

```clojure
(def meetups
  [{:name "JS" :is-active true :members 700}
   {:name "Clojure" :is-active true :members 900}
   {:name "Java" :is-active false :members 600}
   {:name "Go" :is-active true :members 500}])

(def total-members
  (->> meetups
    (filter :is-active)
    (map :members)
    (reduce (fn [acc m] (+ acc m)) 0)))
```

???
- Rest of my examples will be in Java and Clojure.
- Clojure examples are to show the idiomatic usage of FP.
- Some Java examples act as contrast to Clojure examples while some show how you can use FP in Java as well.
- Java is one of the most used programming languages, and is quickly gaining many FP features.

---
class: title fogscreen
background-image: url(/slides/fp-patterns/pattern.jpg)

# Functional Programming Patterns

.footer[
  - Credit: [flic.kr/p/728ELR](https://flic.kr/p/728ELR) (CC BY 2.0)
]

---
class: no-footer quote

> Each pattern describes a problem that occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice.

—  Christopher Alexander, A Pattern Language

???
- In other words, a pattern is a reusable solution to an frequently occurring program.
- In programming, they are often called design patterns as well, but that term is so overloaded now that I'm sticking to just programming patterns.
- The patterns that I mention in this talk are not a comprehensive list, neither are they in any sense a top-n list. These are just some potential patterns I noticed during my work and wanted to share.
- I'm sure there are many more patterns out there to be discovered. the community needs to continue digging existing patterns out of production FP software until a core set of patterns clearly emerges.

---
# Functional Programming Patterns

1. Immutable Data; Explicit State
1. Dataflow Programming
1. Explicit over Implicit
1. Data-oriented Programming
1. Functional Core; Imperative Shell

???
- In the order of most used to least used.
- Also, in order of easiest to use to hardest to use.

---
class: title
# Immutable Data; Explicit State

---
# Immutable Data

- Objects which once created cannot be changed.
- All domain objects should be immutable:
  - User, Account, Transaction, Event etc.

---
# Immutable Data

- No sneaky action-at-distance.
- Thread safety.
- Easier to reason about.
- GC is quite fast now. Creating objects is cheap.

---
# Immutable Data

- In Java < 14, use Google `@AutoValue` or Lombok `@Value` annotations.
- In Java >= 14, use record classes.
- In Clojure, just use built-in data structures like vector and map.
- Clojure data structures share memory so they are more memory efficient.

???
- `@AutoValue` and `@Value` annotations relieve the programmer from the task of writing all boilerplate code in Java.

---
class: compact

# Immutable Data: Java < 14

```java
import lombok.Value;
import lombok.With;

@Value
public class Person {
  private String name;
  @With private int age;
  private double score;
}

Person abhinav = new Person("abhinav", 30, 100.0);
String name = abhinav.getName();
Person olderAbhinav = abhinav.withAge(31);
```

---
class: compact

# Immutable Data: Java >= 14

```java
public record Person(String name, int age, double score) {
  public Person withAge(int age) {
    return new Person(this.name, age, this.score);
  }
}

Person abhinav = new Person("abhinav", 30, 100.0);
String name = abhinav.name();
Person olderAbhinav = abhinav.withAge(31);
```

---
class: compact

# Immutable Data: Clojure

```clojure
=> (def abhinav {:name "Abhinav" :age 30 :score 100.0})
{:name "Abhinav", :age 30, :score 100.0}

=> (def name (:name abhinav))
"Abhinav"

=> (def older-abhinav (assoc abhinav :age 31))
{:name "Abhinav", :age 31, :score 100.0}
```

---
# Explicit State

- Everything is immutable by default.
- Mutable state is marked explicitly so.
- Examples are thread pools, connection pools, dynamic configs, caches etc.

---
# Explicit State

- Mutability is constrained. You know the possible sources of sneaky action-at-distance.
- Proper thread safety implemented for these specific mutability constructs.
- Easier to reason about.

---
class: compact

# Explicit State: Clojure

```clojure
=> (def abhinav (atom {:hair-color :black :age 33}))
#'user/abhinav
=> (swap! abhinav pass-time)
{:hair-color :gray, :age 34}
=> (reset! abhinav {:hair-color :none :age 33})
{:hair-color :none, :age 33}
=> @abhinav
{:hair-color :none, :age 33}
```

```clojure
(defn pass-time [person]
   (-> person
      (assoc :hair-color :gray)
      (update :age inc)))
```

---
class: compact

# Explicit State: Java

```java
class Person {
  private String hairColor;
  private int age;
  public Person(String hairColor, int age) {
    this.hairColor = hairColor;
    this.age = age;
  }
  public Person withAge(int age) {
    return new Person(this.hairColor, age);
  }
  public Person withHairColor(String hairColor) {
    return new Person(hairColor, this.age);
  }
  public Person passTime() {
    return this.withHairColor("Gray").withAge(this.age + 1);
  }
}
```

---
class: compact

# Explicit State: Java

```java
AtomicReference<Person> abhinav =
 new AtomicReference(new Person("Black", 33));
abhinav.updateAndGet(Person::passTime);
abhinav.set(new Person(null, 33));
abhinav.get();
```

---
# Explicit State

- In Clojure, use [`atom`](https://clojure.org/reference/atoms), [`agent`](https://clojure.org/reference/agents) or [`ref`](https://clojure.org/reference/refs).
  - In Java, use [`AtomicReference`](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/AtomicReference.html) with immutable value.
  - Or use [Quasar](http://www.paralleluniverse.co/quasar/) or [Akka](https://doc.akka.io/docs/akka/current/index-actors.html) actors with inaccessible mutable state.
  - If using dependency injection libraries like [Guice](https://github.com/google/guice) or [Dagger](https://dagger.dev) use scopes to constrain mutability.
  - [VAVR library](https://www.vavr.io/) provides persistent DS like Clojure for Java.

---
class: title
# Dataflow Programming

---
class: compact

# Dataflow Programming

- A programming paradigm that models a program as a directed graph of the data flowing between operations.

```java
public class Compiler {
 public void compile() {
 List<File> files = findSourceFiles();
 List<Token> tokens = tokenizeSourceFiles(files);
 AST ast = generateAbstractSyntaxTree(tokens);
 IR ir = generateIntermediateRepresentation(ast);
 ASM asm = generateAssemblyInstructions(ir);
 writeAssemblyOutputFiles(asm);
 }
}
```

---
class: center

![](/slides/fp-patterns/dp1.svg)

---
class: no-heading
```clojure
(defn compile! []
  (-> (find-source-files!)
      (tokenize-source-files!)
      (generate-abstract-syntax-tree)
      (generate-intermediate-representation)
      (generate-assembly-instructions)
      (write-assembly-output-files!)))
```

???

- modeling programs as flow of immutable data
- each operation does a single thing
- operations are composed together for full functionality'
  - adding new operations to the composition is much easier because of decoupling between parts.
- easy to extend by inserting operations between
- easy to test each operation in isolation
- easy to monitor each component separately
- state, if any, is either hidden in the operations or outside the system

---
class: center

![](/slides/fp-patterns/dp2.svg)

---
class: center no-heading

![](/slides/fp-patterns/frpong.svg)

frpong game dataflow diagram

.footer[
  - Source: [frpong](https://github.com/abhin4v/frpong)
]

---
class: fs-50pct
```clojure
(defn collision-detector [ticks pos vel-in acc pd-pos game-state-in game-state vel-out]
 (go-loop
 (let [;; read all current values
 tick (<! ticks)
 [vel-x vel-y] (<! vel-in)
 [x y] (<! pos)
 [gx gy] (<! acc)
 [lpaddle-y rpaddle-y] (<! pd-pos)
 [_ score] (<! game-state-in)

;; calculate next position and detect collision
          [xn yn]               (next-pos [x y] [vel-x vel-y] [gx gy] tick)
          x-state               (detect-x-collision xn yn lpaddle-y rpaddle-y)
          y-state               (detect-y-collision yn)
          x-collision           (collision? x-state)
          y-collision           (collision? y-state)

;; calculate next velocity and game state
          vel-xn                (min ball-speed (+ (adjust-vel x-state vel-x) (* gx tick)))
          vel-yn                (min ball-speed (+ (adjust-vel y-state vel-y) (* gy tick)))
          state-n               (cond
                                  (= x-state :gameover)        :gameover
                                  (or x-collision y-collision) :collision
                                  :else                        :moving)
          score-n               (if x-collision (inc score) score)

;; add a small random perturbation to the ball velocity on collision with paddles
          [vel-xn vel-yn]       (if x-collision
                                  (map perturb [vel-xn vel-yn])
                                  [vel-xn vel-yn])]
      (!> vel-out [vel-xn vel-yn])
      (!> game-state [state-n score-n]))))
```

.footer[
  - Source: [frpong](https://github.com/abhin4v/frpong)
]

---
# Dataflow Programming

- In Java, use an Actor framework like [Akka](http://akka.io).
- [Dagger producers](https://dagger.dev/dev-guide/producers.html) can also be used if you don't want to use Actors.
- Or roll your own using [`ArrayBlockingQueue`](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ArrayBlockingQueue.html) and [`ExecutorService`](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ExecutorService.html).
- In Clojure, use [core.async](https://www.braveclojure.com/core-async/).

---
class: title
# Explicit over Implicit

---
class: col-2 compact

# Explicit over Implicit

.no-list[
- Singletons / global state
- Aspect Oriented Programming
- Hidden Code Generation
- Threadlocals
- Hidden Middlewares
]
 
 
 
 
 
 
 
 
 
---
class: col-2 compact

# Explicit over Implicit

.no-list[
- Singletons / global state
- Aspect Oriented Programming
- Hidden Code Generation
- Threadlocals
- Hidden Middlewares
]

.yes-list[
- Dependency injection
- Higher-order functions
- Macros
- Explicit stateful components
- Passing context as function parameter
]

???

- you may not realize it but these days, Java programs use a lot of implicit "magical" things.
- Implicit or hidden code or state makes the code hard to understand and reason about.
- Sources of bug-at-distance.
- Making them explicit may make the code more verbose but then it's all out there for programmers to see.

---
class: compact

# Explicit over Implicit

Replace

```java
@Transactional
void transferMoney(Account from, Account to, Amount amount) {
  accountDAO.subtract(from, amount);
  accountDAO.add(to, amount);
}
```

with

```clojure
(defn transfer-money [from to amount]
  (java.jdbc/with-db-transaction [txn db-conn-pool]
    (account-dao/subtract txn from amount)
    (account-dao/add txn to amount)))
```

---
class: compact fs-75pct

# Explicit over Implicit

Replace

```java
@RequestMapping(value = "/{org_nr}/devices")
@Authorization(
 resource = @TargetResource(
 type = ORGANIZATION, identifiedBy = "org_nr"),
 requiresPermission = ANY_ROLE,
 requiresAuthenticationLevel = TWO_FACTOR
)
List<Devices> getDevices(@RequestParam("org_nr") String orgNr) { .. }
```

with

```clojure
(GET "/:org_nr/devices" [org-nr :as req]
  (check-auth
    {:target [:organization org-nr]
     :role :any
     :level :two-factor}
     req
    #(get-devices org-nr))))
```
---
class: compact

# Explicit over Implicit

```clojure
(def handler
  (-> routes
    (make-handler)
    (wrap-swagger-ui "/swagger-ui")
    (wrap-defaults api-defaults)
    (wrap-json-params)
    (wrap-json-response)
    (wrap-monitoring)
    (wrap-errors)))

(run-jetty handler {:port 3000})
```

---
class: title
# Data-oriented Programming

---
# Data-oriented Programming

- Data is easy to manipulate.
- Data is easy to extend.
- Data can be interpreted in different ways.
- Data can be saved into DB/disk or sent over network.

---
class: compact

# Data as Control Flow

- Dispatch table

```clojure
(defn routes []
  ["/" [["api/" [["v1/" {"ping"  ping
                         "orgs"  {["/" :id] {:get org/get}}
                         "users" {"/me" {:get    user/me
                                         :delete user/logout}}}]
                 [true not-found-handler]]]
       ["oauth/" {[:subdomain ""]          oauth/launch
                  [:subdomain "/callback"] oauth/callback}]
       [true default-site-handler]]])
```

---
class: compact

# Data as Control Flow

- Logic Programming

![](/slides/fp-patterns/sudoku-puzzle.svg# center)

.footer[
  - Credit: [commons.wikimedia.org](https://commons.wikimedia.org/wiki/File:Sudoku_Puzzle_by_L2G-20050714_standardized_layout.svg) (Public domain)
]

---
# Data as Instructions

- Rule engines

---
class: fs-70pct compact

```java
public record Cart(double cartTotal, String cartId) {}

public class CartRule extends CoRRuleBook {
  public void defineRules() {
    //give 5% off when cart total is greater than 1000
    addRule(RuleBuilder.create()
      .withFactType(Cart.class)
      .withResultType(Double.class)
      .when(facts -> facts.getOne().cartTotal() > 1000)
      .then((facts, result) -> result.setValue(result.getValue() * 0.95))
      .stop()
      .build());
}

public class CartPromotionRule {
  public static void main(String[] args) {
    RuleBook cartPromotion = RuleBookBuilder.create(CartRule.class)
      .withResultType(Double.class)
      .withDefaultResult(0.0)
      .build();
    NameValueReferableMap facts = new FactMap();
    facts.setValue("cart", new Cart(450.0, 123456, customer, entries));
    cartPromotion.run(facts);
    homeLoanRateRuleBook.getResult().ifPresent(result ->
      System.out.println("Final price: " + result));
  }
}
```

.footer[
  - Using the [RuleBook](https://github.com/deliveredtechnologies/rulebook) Java library for implementing rule engines]
---
# Data as Instructions

- Interpreters

---
class: compact

```clojure
(:ragavardhini d/melakarthas)
=> {:arohanam [:s :r3 :g3 :m1 :p :d1 :n2 :s.],
    :avarohanam (:s. :n2 :d1 :p :m1 :g3 :r3 :s)}

(play-arohanam-and-avarohanam (:hanumatodi d/melakarthas))

(play-arohanam-and-avarohanam (:vasanta d/janyas))

(play-phrase (phrase [:s :r2 :g3 :p :m1 :g3 :r2 :s]
                      [ 1   1  1  1   1   1   2   4]
                      1))

(play-phrase
  (phrase (:mechakalyani d/melakarthas)
          [:m :d :n :g :m :d :r :g :m  :g :m :d :n :s.]
          [ 1  1  2  1  1  2  1  1  4   1  1  1  1  4]
          2))

(play-string (:bilahari d/janyas)
              "s,,r g,p, d,s., n,d, p,dp mgrs rs .n .d s,,,
               s,,r g,p, m,,g p,d, r.,,s. n,d, p,,m g,r,")
```

.footer[
  - Source: [ragavardhini](https://github.com/ssrihari/ragavardhini) (EPL-1.0)
]
---
class: compact

# Data as Instructions

- Code generation from data

```clojure
(def q-sqlmap {:select [:foo/a :foo/b]
               :from   [:foo]})
(sql/format q-sqlmap :namespace-as-table? true)
=> ["SELECT foo.a, foo.b FROM foo"]
```

.footer[
  - Using the [honeysql](https://github.com/seancorfield/honeysql) Clojure library for generating SQL
]

--
```clojure
(sql/format (update q-sqlmap :select #(conj % :foo/c))
   :namespace-as-table? true)
=> ["SELECT foo.a, foo.b, foo.c FROM foo"]
```

--
```clojure
(sql/format (merge q-sqlmap {:where [:= :foo/a "baz"]})
   :namespace-as-table? true)
=> ["SELECT foo.a, foo.b FROM foo WHERE foo.a = ?" "baz"]
```

---
# Data as Finite State Machine

.center[
![](/slides/fp-patterns/turnstile.svg)

A turnstile's state-machine
]

---
class: fs-50pct

```clojure
(ns turnstile
  (:require [tilakone.core :as tk :refer [_]]))

; State definitions, pure data here:
(def turnstile-states
  [{::tk/name        :locked
    ::tk/transitions [{::tk/on :coin, ::tk/to :unlocked ::tk/actions [:inc-coin-count]}
                      {::tk/on :push, ::tk/to :locked}
                      {::tk/on _}]}
   {::tk/name        :unlocked
    ::tk/transitions [{::tk/on :push ::tk/to :locked ::tk/actions [:inc-pass-count]}
                      {::tk/on :coin ::tk/to :unlocked}
                      {::tk/on _, ::tk/to :locked}]}])

; FSM has states, a function to execute actions, and current state and value:
(def turnstile
  {::tk/states  turnstile-states
   ::tk/action! (fn [{::tk/keys [action] :as fsm}]
                  (case action
                    :inc-coin-count (update fsm :coin-count inc)
                    :inc-pass-count (update fsm :pass-count inc)))
   ::tk/state   :locked
   :coin-count   0
   :pass-count   0})

; Apply same inputs to our FSM:
(->> [:coin :push :push :coin :coin :push]
  (reduce tk/apply-signal turnstile)
  (juxt :coin-count :pass-count))
;=> [2 2]
```

.footer[
  - Using the [tilakone](https://github.com/metosin/tilakone) Clojure library for implementing state-machines]

---
class: title
# Functional Core; Imperative Shell

---
# Functional Core; Imperative Shell

.center[![](/slides/fp-patterns/functional-core.svg)]

---
# Functional Core

- only pure functions
- no side-effects
- as many decisions as possible
- easier to test and to change
- make as big as possible

---
# Imperative Shell

- only side effects
  - error handling
  - state
  - IO
- as few conditionals or decisions as possible
- harder to test
- make as thin as possible

---
class: no-heading center

.center[
![](/slides/fp-patterns/mobius.png# w-60pct)

Mobius Architecture
]

.footer[
  - Credit: [Mobius Wiki](https://github.com/spotify/mobius/wiki/Mobius-Loop) (Apache License 2.0)
]
---
class: no-heading center

.center[
![](/slides/fp-patterns/redux.svg# w-60pct)

Redux Architecture
]

---
# References

- [No Silver Bullet —Essence and Accident in Software Engineering](http://worrydream.com/refs/Brooks-NoSilverBullet.pdf)
- [Why Functional Programming Matters](https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf)
- [Simple Made Easy](https://www.infoq.com/presentations/Simple-Made-Easy/)
- [Functional Core; Imperative Shell](https://gist.github.com/kbilsted/abdc017858cad68c3e7926b03646554e)
- [Translating an Enterprise Spring Webapp to Clojure](https://blog.jakubholy.net/translating-enterprise-spring-app-to-clojure/)
- [Java with a Clojure Mindset](https://danlebrero.com/2019/03/06/java-with-a-clojure-mindset/)
- ["Making machines that make music" by Srihari Sriraman](https://www.youtube.com/watch?v=u9CGcusOz60)

---
class: big-h1 no-footer center mr-5 thank-you ph-1

.ff-fancy[
# Thanks]
## @[abhin4v](https://twitter.com/abhin4v)