Functional Programming

What is Functional Programming?

“In computer science, functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.”

Tenets of Functional Programming

• Functions consistently map inputs to outputs
• Data is immutable (values)
• Functions have no side-effects

Functions

• Functions are types in FP, not just methods
  • They can be assigned
  • They can be passed around and returned
• FP Functions are Mathematical Functions, with all of their special properties:
  • Consistent results
  • Composition, substitution, partial evaluation, etc.

Values

• Values are immutable
• Primitives (double, int, string, etc.) are values
• Value Types and Immutable Collections: Immutable classes with equality and hashcode
• Values are implicitly concurrent
• Values don't require deep copying since they can share history
• Values are required for functional consistency
• Values are easy to reason about
• In FP, it's values all the way down

No Side Effects

• Anything that affects computation besides the function internals is a side effect
• Mathematical functions have no side-effects
• Examples of side-effects include disk i/o, printing, rendering, and loading configuration files
• In practice, there will be side-effects
• FP seeks to minimize and contain them

Summary

• Functional Programming treats computation as the evaluation of mathematical functions
• To be functional, you must have:
  • Functions as types: You can't have FP without functions
  • Value types: Mutable state breaks the functional contract
  • No side-effects: Side-effects break the functional contract

Example: Collection Abstractions

Collection Abstractions

• Things you do all the time with collections:
  • Map elements to different values
  • Filter certain elements out
  • Reduce all elements to a single value
  • Find a certain element
  • Check for the existence of one or more elements satisfying a predicate
  • Etc.
• Each pattern above is mostly boilerplate in OOP
• Let's see how FP can help

Non-Functional Collection Operation 1

Map a collection to its squares

public static List<Integer>map(List<Integer> input){
    List<Integer> output = new LinkedList<Integer>();
    for(Integer i : input){
        output.add(i * i);
    }
    return output;
}

Non-Functional Collection Operation 2

Map a collection to its doubles

public static List<Integer>map(List<Integer> input){
    List<Integer> output = new LinkedList<Integer>();
    for(Integer i : input){
        output.add(i * 2);
    }
    return output;
}

Observations

• These fragments were identical except for a single operation
• You cannot easily abstract away the common code with OOP
• Try it if you don't believe me
• Let's look at my solution

The OOP Solution

public interface IOperation<T, U> {
    public T apply(U input);
}

public static <T, U> List<T> map(List<U> input, IOperation<T, U> operation){
    List<T> output = new LinkedList<T>();
    for(U i : input){
        output.add(operation.apply(i));
    }
    return output;
}

Whoa, ugly!

The OOP Solution

public static void main(String[] args){
    List<Integer> ints = new LinkedList<Integer>();
    for(int i = 0; i < 1000000; i++) ints.add(i);

    List<Double> roots = map(ints, new IOperation<Double, Integer>() {
        @Override
        public Double apply(Integer input) {
            return Math.sqrt(input);
        }
    });

    System.out.println(roots.size());
}

This isn't particularly satisfying

The FP Solution

Java 8

List<Integer> squares =
        ints.stream().map(i -> i * i).collect(Collectors.toList());

• Notes
  • i -> i * i is a first class function
  • It is called on every element of ints (our collection)
  • map takes a function as its argument

Comparison

Java 8

List<Integer> squares =
        ints.stream().map(i -> i * i).collect(Collectors.toList());

Java 7

List<Double> squares = map(ints, new IOperation<Double, Integer>() {
    @Override
    public Double apply(Integer input) {
        return input * input;
    }
});

• 6X less code (ignoring the line break)
• More readable and less error prone

Examples in Multiple Languages

Java 8

List<Integer> squares =
        ints.stream().map(i -> i * i).collect(Collectors.toList());

Scala

val squares = (0 until 1000000) map { x => x * x }

Clojure

(def squares (map #(* % %) (range 0 1000000)))

Examples in FP Languages

Scala

val squares = (0 until 1000000) map { x => x * x }

Clojure

(def squares (map #(* % %) (range 0 1000000)))

The FP versions are even smaller than the Java 8 version because of their design

First Class Functions Summary

• First class functions allow you to abstract away repetitive patterns of action
• What is more common?
  • Domain objects
  • Patterns of action
• Programming for patterns of action gives high reuse, reduces line count, and reduces potential for errors

Example: Values

Recall: Advantages of Values

• Values are concurrent
• Values are easy to reason about
• FP's predictablility guarantees are lost when arguments are mutable
• For true FP, it's values all the way down

Java Example: Concurrent Modification

What happens here?

List<Integer> ints = new LinkedList<>();
for(int i = 0; i < 1000000; i++) ints.add(i);

new Thread(() -> {
    while(!ints.isEmpty()) ints.remove(0);
}).start();

List<Integer> evens =
        ints.stream().filter(i -> (0 == (i % 2))).collect(Collectors.toList());

System.out.println(evens.size());

Java Example Output

Exception in thread "main" java.lang.NullPointerException
	at example.StreamStuffNPE.lambda$main$1(StreamStuffNPE.java:17)
	at example.StreamStuffNPE$$Lambda$2/250421012.test(Unknown Source)
	at java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:174)
	at java.util.LinkedList$LLSpliterator.forEachRemaining(LinkedList.java:1235)
	at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:512)
	at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:502)
	at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
	at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
	at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499)
	at example.StreamStuffNPE.main(StreamStuffNPE.java:17)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:483)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:134)

What happened?

• Two threads were operating concurrently on a single mutable data structure
• I can't divine the exact details from the stack trace
• Clearly, though, the result is indeterminate

Concurrency with Immutable Data Structures

What happens here?

(def int-vec (into [] (range 1000000)))

(future
  (loop[rem (rest int-vec)]
    (if (empty? rem)
      (prn "All done")
      (recur (rest rem)))))

(count (filter #(= 0 (mod % 2)) int-vec))
=> #'user/int-vec
=> #<core$future_call$reify__6320@73f5597d: :pending>
"All done"
=> 500000

How did this work?

• The int-vec data structure was immutable
• The future did not modify int-vec; it makes a new version of it at every iteration
• The filter and count operate on the initial immutable data structure - NOT an intermediate one

Conclusion

• Values are a powerful concept that is a key requirement for FP
• Values give implicit concurrency, are easy to reason about, and are easy to manipulate and analyze
• Language Notes:
  • Scala has good value support (Immutable collections and case classes)
  • Clojure has amazing value support (Immutable collections and defrecords)
  • Java has NO value support (Collections and classes are mutable)

Example: Car Shopping

• This is trivial trade analysis example
• It is a good illustration of many real, complex problems

The Problem

• Create a sampling of items (cars)
• Evaluate each
• Return the best one

The OOP/Java Solution

Car.java

package cars;

public class Car {
    private String make = null;
    private int year = 0;
    private String color = null;
    private double topSpeed = 0.0;

    public String getMake() {
        return make;
    }

    public void setMake(String make) {
        this.make = make;
    }

    public int getYear() {
        return year;
    }

    public void setYear(int year) {
        this.year = year;
    }

    public String getColor() {
        return color;
    }

    public void setColor(String color) {
        this.color = color;
    }

    public double getTopSpeed() {
        return topSpeed;
    }

    public void setTopSpeed(double topSpeed) {
        this.topSpeed = topSpeed;
    }

    @Override
    public String toString() {
        return getColor() + " " + getYear() + " " + getMake() + 
        " with top speed of " + getTopSpeed() + " mph";
    }
}

TestDriver.java

package cars;

public class TestDriver {
    //Super complicated ranking function.
    public static double rank(Car car){
        double score = 0.0;
        switch (car.getColor()) {
            case "Red":
                score = 2.0;
                break;
            case "Green":
                score = 1.0;
                break;
            case "White":
                score = 1.5;
                break;
            case "Black":
                score = 1.9;
                break;
            case "Beige":
                score = 0.0;
                break;
        }
        return score;
    }
}

CarPurchasingModel.java

package cars;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class CarPurchasingModel {
    public static void main(String[] args){
        List<String> colors = new LinkedList<>();
        colors.add("Red");
        colors.add("Green");
        colors.add("White");
        colors.add("Black");
        colors.add("Beige");
        
        Map<Car, Double> ranked = new HashMap<Car, Double>();
        for(String color : colors){
            Car car = new Car();
            car.setColor(color);
            car.setMake("Honda");
            car.setYear(2015);
            car.setTopSpeed(120.0);
            ranked.put(car, TestDriver.rank(car));
        }
        
        Car bestCar = null;
        double bestScore = -1;
        for(Map.Entry<Car, Double> entry : ranked.entrySet()){
            if(bestCar == null || entry.getValue() > bestScore){
                bestCar = entry.getKey();
                bestScore = entry.getValue();
            }
        }
        
        System.out.println("The best car is: " + bestCar);
    }
}

The FP/Clojure Solution

Clojure Solution

(def color-options [:red :green :white :black :beige])
(def basic-car { :make "Honda" :year 2015 :color :beige :top-speed 120.0 })
(def all-cars (map #(into basic-car { :color % }) color-options))

(defn rank [item]
  "Rank the car using a very complicated user preference algorithm"
  (case (item :color)
    :red 2.0
    :green 1.0
    :white 1.5
    :beige 0.0
    :black 1.9
    0.0))

(def rank-map (zipmap all-cars (map rank all-cars)))

(prn (str "The best car is: " (apply max-key val rank-map)))

Results

• Java Output
  • The best car is: Red 2015 Honda with top speed of 120.0 mph
  • Note that I overrode toString
• Clojure Output
  • The best car is: [{:make "Honda", :color :red, :top-speed 120.0, :year 2015} 2.0]

Program Stats

• Java
  • 3 Files/Classes
  • 110 LOC
• Clojure
  • 1 File
  • 17 LOC

Observations

Data Representation

• Java used a mutable class
  • Care had to be taken to ensure consistency
  • I am stuck with this implementation - I can't add new fields at will
  • This code is not concurrent and would not work well for a parallel implementation
• Clojure used an immutable map
  • Consistency and concurrency are implicit
  • I can add fields at will, even nested complex fields
  • Parallelization would be trival (map -> pmap)

Use of Functions

• Java
  • Java relied on standard methods from collection interfaces
  • No first class functions were used in this example
• Clojure
  • Clojure made heavy use of functions for manipulating data
  • map, into, zipmap, apply, max-key

The Ranking Function

• The Java ranker was tied to a TestDriver and is only good for Cars
  • 0 reuse
  • If color is the only applicable field, I could create IColor and IColorEvaluator interfaces
  • This still requires declaring the interface everywhere it is used
• The Clojure ranker only used relevant data
  • This function can be used for any color-based ranking
  • By extension, any function using a data structure with the right fields can be reapplied
  • For example, I could use this function to pick out a refrigerator or a cat

Was this unfair to Java?

• Potential Java version improvements
  • Make Car immutable with equals, hashcode, copy, and default constructors
    • This is "Effective Java"
    • I now have to write even more code
    • A lot of code just moves around
    • I did it anyways: 126 LOC
• In any event, this is canonical Java

The Immutable OOP/Java Solution

IColorData.java

package cars2;

public interface IColorData {
    public String getColor();
}

ImmutableCar.java

package cars2;

public class ImmutableCar implements IColorData {
    private final String make;
    private final int year;
    private final String color;
    private final double topSpeed;

    public ImmutableCar(String make, int year, String color, double topSpeed) {
        this.make = make;
        this.year = year;
        this.color = color;
        this.topSpeed = topSpeed;
    }

    public String getMake() {
        return make;
    }

    public int getYear() {
        return year;
    }

    public String getColor() {
        return color;
    }

    public double getTopSpeed() {
        return topSpeed;
    }

    public ImmutableCar setMake(String newMake){
        return new ImmutableCar(newMake, getYear(), getColor(), getTopSpeed());
    }

    public ImmutableCar setYear(int newYear){
        return new ImmutableCar(getMake(), newYear, getColor(), getTopSpeed());
    }

    public ImmutableCar setColor(String newColor){
        return new ImmutableCar(getMake(), getYear(), newColor, getTopSpeed());
    }

    public ImmutableCar setTopSpeed(double newTopSpeed){
        return new ImmutableCar(getMake(), getYear(), getColor(), newTopSpeed);
    }

    @Override
    public String toString() {
        return getColor() + " " + getYear() + " " + getMake() + " with top speed of " + getTopSpeed() + " mph";
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        ImmutableCar that = (ImmutableCar) o;

        if (Double.compare(that.topSpeed, topSpeed) != 0) return false;
        if (year != that.year) return false;
        if (color != null ? !color.equals(that.color) : that.color != null) return false;
        if (make != null ? !make.equals(that.make) : that.make != null) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result;
        long temp;
        result = make != null ? make.hashCode() : 0;
        result = 31 * result + year;
        result = 31 * result + (color != null ? color.hashCode() : 0);
        temp = Double.doubleToLongBits(topSpeed);
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        return result;
    }
}

TestDriver2.java

package cars2;

public class TestDriver2 {
    //Super complicated ranking function.
    public static double rank(IColorData car){
        double score = 0.0;
        switch (car.getColor()) {
            case "Red":
                score = 2.0;
                break;
            case "Green":
                score = 1.0;
                break;
            case "White":
                score = 1.5;
                break;
            case "Black":
                score = 1.9;
                break;
            case "Beige":
                score = 0.0;
                break;
        }
        return score;
    }
}

ImprovedCarPurchasingModel.java

package cars2;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class ImprovedCarPurchasingModel {
    public static void main(String[] args){
        ImmutableCar defaultCar = new ImmutableCar("Honda", 2105, "Beige", 120.0);

        List<String> colors = new LinkedList<>();
        colors.add("Red");
        colors.add("Green");
        colors.add("White");
        colors.add("Black");
        colors.add("Beige");

        Map<ImmutableCar, Double> ranked = new HashMap<ImmutableCar, Double>();
        for(String color : colors){
            ImmutableCar car = defaultCar.setColor(color);
            ranked.put(car, TestDriver2.rank(car));
        }

        ImmutableCar bestCar = null;
        double bestScore = -1;
        for(Map.Entry<ImmutableCar, Double> entry : ranked.entrySet()){
            if(bestCar == null || entry.getValue() > bestScore){
                bestCar = entry.getKey();
                bestScore = entry.getValue();
            }
        }

        System.out.println("The best car is: " + bestCar);
    }
}

Please never make me do this again

Car Shopping Summary

• OOP and FP solutions were provided to the same problem
• The FP implementation of the solution was:
  • Much smaller
  • Concurrent
  • More flexible
  • More reusable
• These results are typical

Example: Conway's Game of Life

Demonstrating FP in a stateful world

Conway's Game of Life

• Cellular automaton
• Start with a grid in which some cells are "dead" and some are "live"
• Step forward and re-evaluate each cell
• Live cells with 2-3 living neighbors remains alive, otherwise it dies
• Dead cells with 3 living neighbors becomes a live cell

Implementation

rules

(ns conway.rules)

(defn gen-cell[](if (> (Math/random) 0.7) :alive :dead))

(defn seed-grid [rows cols]
  (vec (take rows (repeatedly (fn [] (vec (take cols (repeatedly gen-cell))))))))

(defn neighbors [[i j]]
  (let [x ((juxt inc inc identity dec dec dec identity inc) i)
        y ((juxt identity inc inc inc identity dec dec dec) j)]
    (map vector x y)))

(defn count-neighbors [grid coord]
  (let [n (map #(get-in grid %) (neighbors coord))]
    (count (filter #(= % :alive) n))))

(defn sim-step [grid coord]
  (let [n-live (count-neighbors grid coord)]
    (if (= :alive (get-in grid coord))
      (case n-live
        (2 3) :alive
        :dead)
      (if (= 3 n-live) :alive :dead))))

(defn step [grid]
  (into [] (for [i (range (count grid))]
          (into [] (for [j (range (count (get grid i)))]
                  (sim-step grid [i j]))))))

ui

(ns conway.core
  (:gen-class)
  (:require [conway.rules])
  (:import (javax.swing JFrame JPanel JButton JCheckBox Box BoxLayout)
           (java.awt BorderLayout Graphics2D Color ImageCapabilities)
           (java.awt.geom Rectangle2D$Double)
           (java.awt.event ActionListener)
           (java.awt.image VolatileImage)))

(defn panel [grid-ref]
  (let [pnl (proxy [JPanel] []
    (paint [g]
      (let [w (.getWidth this) 
            h (.getHeight this)
            bg (Rectangle2D$Double. 0 0 w (.getHeight this))
            vimg (.createVolatileImage this w h (ImageCapabilities. true))
            g2d (.createGraphics vimg)]
        (doto g2d
          (.setPaint Color/BLACK)
          (.fill bg))
        (doseq [i (range (count @grid-ref))]
          (doseq [j (range (count (get @grid-ref i)))]
            (let [c (if (= :alive (get-in @grid-ref [i j])) Color/GREEN Color/RED)
                  sq (Rectangle2D$Double. (* i (/ w (count @grid-ref)))
                                          (* j (/ h (count (get @grid-ref i))))
                                          (/ w (count @grid-ref))
                                          (/ h (count (get @grid-ref i))))]
              (do
                (.setPaint g2d c)
                (.fill g2d sq)))))
        (.drawImage g vimg 0 0 this)
        )))]
    (do 
      (add-watch grid-ref :repaint (fn [_ _ _ _] (.repaint pnl)))
    pnl)))

(defn sim-button [grid-ref]
  (let [cb (JCheckBox. "Sim!")]
    (future
      (loop []
        (do
          (when (-> cb .isSelected)
            (dosync (ref-set grid-ref (conway.rules/step @grid-ref))))
          (Thread/sleep 33))
        (recur)))
    cb))

(defn step-button [grid-ref]
  (doto (JButton. "Step")
    (.addActionListener
      (reify ActionListener
        (actionPerformed [_ _]
          (dosync (ref-set grid-ref (conway.rules/step @grid-ref))))))))

(defn reset-button [grid-ref]
  (doto (JButton. "Reset")
    (.addActionListener
      (reify ActionListener
        (actionPerformed [_ _]
          (dosync (ref-set grid-ref (conway.rules/seed-grid 100 100))))))))

(defn run-app [exit-op] (let [grid-ref (ref (conway.rules/seed-grid 100 100))]
  (doto (JFrame. "Conway's Game of Life")
    (.setSize 800 600)
    (.setDefaultCloseOperation exit-op)
    (.add (panel grid-ref) BorderLayout/CENTER)
    (.add (doto (Box. BoxLayout/PAGE_AXIS)
            (.add (step-button grid-ref))
            (.add (sim-button grid-ref))
            (.add (reset-button grid-ref))) BorderLayout/SOUTH)
    (.setVisible true))))

;(run-app JFrame/DISPOSE_ON_CLOSE)

(defn -main
  [& args]
  (future (run-app JFrame/EXIT_ON_CLOSE)))

Program Stats

• 2 Files, 105 LOC
• Logic: 1 File, 28 LOC
• Application: 1 File, 77 LOC

Observations

Program Design

• All model logic was contained in a single file with pure FP code
• The UI contained all stateful code
• I was very lazy - The UI could definitely be cleaner and smaller
• The actual domain model is managed by a single reference (a Clojure concurrency primitive)
• The reference can be watched for updates and set using transactions
• This is a typical design

Performance

• Doing some simple tests shows a 1000 x 1000 grid takes ~100 ms to compute
• Doing some simple tests shows a 100 x 100 grid takes < 1 ms to compute
• GUI performance is the major bottleneck
• Fixing GUI performance is left as an exercise for the presenter (or reader)

Conway's Game of Life Summary

• You can have complex stateful applications written in FP
• A common pattern:
  • Implement rules/logic in a completely functional manner
  • Use a Clojure concurrency primitive (atom, ref, or agent) to manage state
  • The UI interacts with the concurrency primitive
  • The concurrency primitive can be watched
  • This separates concerns