Mindset shifts for Functional Programming (with Clojure)

For more experienced functional programmers, most of this post will seem introductory, but I introduce some more advanced stuff near the end.

Functional Programming over Canadian Programming

Lately, I've been thinking about this Functional Programming journey I've been on. I thought it started when I was twenty, but It may have started when I was twelve. See, I used to watch a lot of G4TechTV here in Canada. I still remember Amber Macarthur introducing a cool new website called Remember the Milk.

Remember the Milk was, to my knowledge, one of the first ToDo list Software-as-a-Service apps, circa 2005. All that tech consumer television certainly inspired me to, not only become a computer nerd, but it inspired me to take up programming at thirteen years old because I believed computing was the future.

I didn't learn functional programming at thirteen years old though. Like most, I started with an imperative programming language. I learned to program with the easiest programming language around: The C programming language. Okay, it wasn't that easy, but I still learned. Making introduction to computer programming in University a breeze.

All throughout University I was still a Remember the Milk user. One day their website spawned a careers page. Much to my curiousity, I decided to checkout the Software Engineer position as I usually did on those kinds of job postings back then. Remember the Milk's job description was different though. There was talk about Scalable Internet Architectures, and this obscure programming language called Scala.

Soon after, I became enamoured with Scala. I thought "this was what Java should have been", but I hit a wall soon after reading Scala for the Impatient. And, I was impatient. I didn't really understand the funcitonal programming features of Scala. Most of my Scala code looked similar to the Java code I was writing in my programming classes. What the hell were closures, reducers, special-access methods, actors, and pattern matching? No fucking clue. Of course my internet research lead me to another functional programming language, a pure functional programming language, Haskell.

Haskell suffered from none of the deficiencies of Java Virtual Machine (JVM) functional programming languages at the time. It had it's own complier that produced binaries as well as having it's own read-eval-print-loop (REPL), and importantly, because I was a broke student, there was a great book online for free to learn Haskell. Finally, I had unlocked functional programming. I went back to Scala, only using the functional programming features for years.

Solving problems with Scala and functional programming eventually qualified me for a full-time Clojure position when I finally dropped out of University.

Transformations over Instructions

The first mindset shift when learning Haskell was to think of a program as a series of transformations on data rather than a series of instructions. A philosophy I would carry into other programming languages throughout my career, like when I was Golang developer. Pure functions and reducers like map and filter made for simplicity and easy testing. Transformations on data are so important, Clojure provides transducers to decouple those transformations from their contexts. Of course, most of us know what a simple series of transformations look like in Clojure:

(->> (range)
     (filter even?)
     (map inc)
     (take 10))

(->> (range)
     (filter even?)
     (map inc)
     (take 10)
     (reduce +))

Thinking of programs as a series of transformations was necessary because functional programming languages defaulted to immutable or persistent data structures. Meaning, if you want to change the data in the structure, you didn't mutate the data structure, rather you got a whole new data structure in memory at the end of the transformation, preserving the old data structure.

At a high level, an operation like map produces a collection the same length as it's input collection, applying an input function to each value in the input collection as the output collection. Simple on the surface. But, how do you do that without state and, therefore, looping?

Recursion over Looping

Pure functional programming languages like Haskell do not contain a looping construct like for while or do...while. Loops, by their nature, often facilitate side-effects and mutate a variable to track whether or not to continue iteration.

Inspired by mathematics (a recurring theme in functional programming), functional programming languages often facilitate iteration through recursion. The mindset shift being, how do we construct a recursive function to emulate a loop?

We can emulate an iteration in a functional programming language by taking advantage of the lexical scope each recursive call has.

(defn recursive-map
  "Recursively applies `f` to each element in `coll`,
  returning the new collection."
  [f coll]
  (let [[head & tail] coll]
    (if (empty? coll)
      nil
      (cons (f head) (recursive-map f tail)))))
      
user> (recursive-map identity (range 10))
(0 1 2 3 4 5 6 7 8 9)
user> (recursive-map inc (range 10))
(1 2 3 4 5 6 7 8 9 10)

Typically, code like this is an anti-pattern in Clojure as it would consume too much stack space for large input. We would have passed our output through each call, building it through the recursive calls like using Clojure's loop and recur. Unfortunately, Clojure does not have tail-call optimization. To get around this, it has a special form recur to signal to the compiler not to consume stack space, but it has to be in the end position unlike our recursive-map call.

I chose the example above because it shows a common functional programming technique: Destructuring our input collection into a head and tail. Head being the first element in our collection, and tail being a collection with all except the head of the collection. Rather than looping over an array and applying our function, each recursive call applies a 1-arity function f to each element before getting cons'd into the list.

Functions over Objects

Our recursive-map above example uses another mindset shift: higher-order functions. Higher-order functions form the basis for everything else in functional programming. In functional programming languages, functions are first class, meaning we can treat them like any other piece of data. We can pass them to other functions as arguments, return functions from functions, and even having lists of functions. Higher-order functions let us decouple a function from it's usage, provided the function signatures align.

user> (take 1 (map println [1 2 3 4 5]))
;; 1
;; 2
;; 3
;; 4
;; 5
;; (nil)
user> (take 1 (map println '(1 2 3 4 5)))
;; 1
;; (nil)

Functional Programming emphasizes pure functions. That is, functions free from side-effects. Side-effects are behaviours functions perform during their execution aside from computing the output. For example, IO operations, network transmission, and writing to a database are all side-effects. Side-effects cause numerous bugs in software development, so by (nearly) eliminating side-effects, functional programming (nearly) elminates this whole class of bugs.

Design over Spaghetti

I like to think of transformations, recursion, and functions as the fundamentals of functional programming. With them we can design and emulate a finite state machine (FSM) without any actual state by using the recurring lexical scope to bind our current FSM state. Whenever the state "transitions", we'll return a function to replace our game-state in game-loop with a new state for our fake game engine below. Even though I wrote this example in Clojure, there's nothing stopping someone from replicating it in Haskell:

(defn pause-menu
  [game]
  (let [{:keys [menu player]} game]
    (do
      (draw-game game)
      (if (= :affirm (:action player))
        (when-let [menu-item (collision player)]
          (cond
            (= menu-item :resume-game) play-game
            (= menu-item :options) (partial options-menu pause-menu)
            (= menu-item :quit-game) quit-game
            :else pause-menu))
        pause-menu))))

(defn options-menu
  [previous game]
  (let [{:keys [menu player]} game]
    (do
      (draw-game game)
      (if (= :affirm (:action player))
        (when-let [menu-item (collision player)]
          (cond
            (= menu-item :controls) controls-menu
            (= menu-item :accessibility) accessibility-menu
            (= menu-item :exit-options) previous
            :else options-menu))
        options-menu))))

(defn play-game
  [game]
  (let [{:keys [components player]} game]
    (do
      (doseq [component components]
        (update! component))
      (draw-game game)
      (if (= :paused (:action player))
        pause-menu
        play-game))))

(defn start-menu
  [game]
  (let [{:keys [menu player]} game]
    (do
      (draw-game game)
      (if (= :affirm (:action player))
        (when-let [menu-item (collision player)]
          (cond ;; our state transition
            (= menu-item :start-game) play-game
            (= menu-item :options) (partial options-menu start-menu)
            (= menu-item :quit-game) quit-game
            :else start-menu))
        start-menu))))

;; Our initial state
(defn start-game
  [game]
  (start-menu game))

(defn game-loop
  [game-state game-engine]
  (when-not (:quit game-engine)
    (recur (game-state game-engine) (game-engine))))

(defn -main
  []
  (game-loop (start-game game-engine) (game-engine)))

Regular readers will recognize this FSM as my "stateless" state pattern from my design patterns series, but I want to emphasis something else: how we can use the fundamentals of Functional Programming to design solutions without making our lives miserable. At least until AI puts us out of work.

Closure over Conclusion

Functional Programming is awesome. When I started learning Haskell, it felt like learning to code all over again. After the initial hurdle, Functional Programming gave me a cognitive model for programming that leads to more simplicity and less bugs by emphasizing transformations, recursion, and functions.