The Pillars of Functional Programming (Part 2)

Nikolay Mozgovoy

This is the continuation of the topic from The Pillars of Functional Programming (Part 1), proceeding with the consequences of treating the functions as a first-class type.

O' First-class Functions, the aftermath

Closures

The concept of Closures may seem hard to grasp, but in fact, they aren’t a rocket science. From programmer’s perspective, you should consider closure as a function created at runtime that have references to free variables. Alternatively, you may favor a definition on Image 5: function + environment in which it was created = closure.

Closure

Image 5. Closure

Interestingly, the first appearance of closures was not intentional: they were accidentally invented during bugfix in LISP compiler by Steve Russel and received the name “FUNARG device” at the time.

The importance and appliance of closures is similar to objects in object-oriented languages, since they bind together data and behavior. Furthermore closures provide information hiding very similar to access specifier "private" in languages like C++, Java or C#, since every variable defined inside the closure function remains invisible outside of its scope.

It is possible to consider the function creating a closure as a class definition, while closure itself as an instance of such class.

Compare the following examples of utilizing closures in Clojure and F# with class definition in C#:

  1. ; Clojure
  2. (defn new-color [r g b]
  3.   (let [
  4.     mix (fn [c1 c2] ; private function
  5.       (-> (+ c1 c2) (#(/ % 2)) float Math/round))
  6. ; variable 'self' serves as substitute for keyword 'this' in C# or Java
  7.     self {
  8.       ; public properties
  9.       :R r
  10.       :G g
  11.       :B b
  12. ; mix-with is a closure itself
  13. ; since it references free variables r g b
  14. ; here it serves as a public function
  15.       :mix-with (fn [other-color]
  16.         (new-color
  17.           (mix r (other-color :R))
  18.           (mix g (other-color :G))
  19.           (mix b (other-color :B))))}]
  20.       ; return newly create object
  21.     self))
  22.  
  23. (def red (new-color 255 0 0))
  24. (def white (new-color 255 255 255))
  25. (def coral-red
  26.   ((((red :mix-with) white)
  27.           :mix-with) red))

 

  1. // F#
  2. open System
  3.  
  4. type Color = {
  5.     R: byte
  6.     G: byte
  7.     B: byte
  8.     MixWith: (Color -> Color)
  9. }
  10.  
  11. let rec NewColor r g b =
  12.   let mix a b = // private function
  13.     ((float)a + (float)b) / 2.0
  14.     |> Math.Round
  15.     |> byte
  16.   { // public properties
  17.     R = r;
  18.     G = g;
  19.     B = b;
  20. // MixWith is a closure itself
  21. // since it references free variables r g b
  22. // here it serves as a public function
  23.     MixWith = fun otherColor ->
  24.         NewColor
  25.             (mix r otherColor.R)
  26.             (mix g otherColor.G)
  27.             (mix b otherColor.B)
  28.   }
  29.  
  30. let red = NewColor 255uy 0uy 0uy
  31. let white = NewColor 255uy 255uy 255uy
  32. let coralRed = (red.MixWith white).MixWith red

 

  1. // C#
  2. public class Color {
  3.  
  4.     private byte Mix(byte c1, byte c2) =>
  5.         (byte)Math.Round(
  6.             ((float)c1 + (float)c2) / 2);
  7.  
  8.     public Color(byte r, byte g, byte b) {
  9.         this.R = r;
  10.         this.G = g;
  11.         this.B = b;
  12.     }
  13.  
  14.     public byte R { get; }
  15.     public byte G { get; }
  16.     public byte B { get; }
  17.  
  18.     public Color MixWith(Color otherColor) =>
  19.         new Color(
  20.             this.Mix(this.R, otherColor.R),
  21.             this.Mix(this.G, otherColor.G),
  22.             this.Mix(this.B, otherColor.B));
  23. }
  24.  
  25. var red = new Color(255, 0, 0);
  26. var white = new Color(255, 255, 255);
  27. var coralRed = red.MixWith(white).MixWith(red);

 

They are identical in functionality, while in Clojure and F# we achieved it using just first-class functions.

 

Partial Application

I must confess that emulating object systems with closures even being possible and quite laconic, is not an everyday practice. There is another much common application of closures called “partial application”, which simply means the process of breaking a single function into multiple ones of smaller arity.

Motivation of doing such transformation is simple. Quite often, an application is not supplied with all the arguments required to perform some operation immediately. Therefore, instead of passing them around until other arguments appear, it is possible to pack existing arguments into closure objects, or, in other words, partially apply a function to them.

Let’s rethink the previous example extracting the colors mixing function from the color type (which would be more idiomatic approach):

  1. ; Clojure
  2. (defrecord color [R G B])
  3.  
  4. (defn mix-colors [c1 c2]
  5.   (let [mix (fn [c1 c2]
  6.     (-> (+ c1 c2) (#(/ % 2)) float Math/round))]
  7.     (color.
  8.       (mix (:R c1) (:R c2))
  9.       (mix (:G c1) (:G c2))
  10.       (mix (:B c1) (:B c2)))))
  11.  
  12. ; That is our simple palette:
  13. (def red (color. 255 0 0))
  14. (def green (color. 0 255 0))
  15. (def blue (color. 0 0 255))
  16. (def white (color. 255 255 255))
  17.  
  18. ; Imagine brush color was set to red
  19. (def brush-color red)
  20. (comment
  21.   Now we will remember it in closure and use for mixing with other colors from palette
  22.   In other words, we will partially apply mix-colors to the color we know at the moment)
  23. (def mix-with-palette (fn [color]
  24. (comment
  25.   This function is closure
  26.   it references free variable brush-color)
  27.   (mix-colors brush-color color)))
  28. (comment
  29.   Then apply mix-with-palette to other colors as soon as they available)
  30. (def olive (mix-with-palette green))
  31. (def purple (mix-with-palette blue))

 

  1. // F#
  2. type Color = {
  3.     R: byte
  4.     G: byte
  5.     B: byte
  6. }
  7.  
  8. let mixColors c1 c2 =
  9.     let mix a b =
  10.         ((float)a + (float)b) / 2.0
  11.         |> System.Math.Round
  12.         |> byte
  13.     { R = mix c1.R c2.R;
  14.       G = mix c1.G c2.G;
  15.       B = mix c1.B c2.B; }
  16. // That's our simple palette:
  17. let red = { R=255uy; G=0uy; B=0uy; }
  18. let green = { R=0uy; G=255uy; B=0uy; }
  19. let blue = { R=0uy; G=0uy; B=255uy; }
  20. // Imagine brush color was set to red
  21. let brushColor = red
  22.  
  23. (* Now we'll remember it in closure and use for mixing with other colors from palette
  24.    In other words we'll partially apply mixColors to the color we know at the moment *)
  25. let mixWithPalette =
  26. (* This function is closure
  27.   it references free variable brushColor  *)
  28.     fun color -> mixColors brushColor color
  29.  
  30. (* Then apply mixWithPalette to other colors as soon as they awailable *)
  31. let olive = mixWithPalette green
  32. let purple = mixWithPalette blue

 

The term “partial application” is often conflated with the so called “currying”. For the sake of simplicity, consider currying as a special case of partial application that means a process of breaking a function of N arguments into a chain of N functions of single argument.

 

Lazy evaluation

Lazy evaluation is a way of computing, in which values are not calculated until they are required. This neat feature can severely speed up applications, reduce memory footprint, and allows to process infinite data. Lazy evaluation is attainable in multiple ways. It can be either an evaluation strategy supported by language itself (i.e. Haskell), or it can be implemented via special data structures, which is especially easy with first-class functions available in any functional language.

Clojure, F# and C# used for examples in this article aren’t lazy languages by themselves, they employ eager evaluation strategy, nevertheless they heavily utilize lazy evaluation and support it through their data structures.

  1. ; Clojure
  2. (def array
  3.   (take 10 (repeatedly #(rand-int 1000))))
  4. (def ordered-array
  5.   (delay (sort array))); sort array on demand
  6. (force ordered-array); force evaluation

 

  1. // F#
  2. let rn = new Random()
  3. // Generate array
  4. let arr = [| for _ in 1 .. 1000 -> rn.Next() |]
  5. // orderedArray will be sorted on demand
  6. let orderedArray = lazy (arr |> Array.sort)
  7. orderedArray.Force() // force evaluation

 

  1. // C#
  2. var rn = new Random();
  3. var sequence = Enumerable
  4.     .Range(0, 1000)
  5.     .Select(i => rn.Next());
  6. var orderedSequence = sequence
  7.     .OrderBy(a => a);
  8. /* Most of the LINQ functions share lazy nature utilizing iterator pattern under the hood. Running this code will only define 'orderedSequence' but not evaluate it until someone will force it with ToArray or foreach statement */

 

Using closures, it is quite easy to implement lazy data structures and infinite sequences by yourself:

  1. ; Clojure
  2. (defn new-seq [next-value value]
  3.   ; return function of action argument
  4.   (fn [action]
  5.     (cond ; something like a switch but better
  6.       (= action :next) ; if action is :next
  7. ; create a new generator with the next value
  8.         (new-seq next-value (next-value value))
  9.       (= action :value) ; if action is :value
  10.         value))) ; return current value
  11. ; sequence of powers of 2
  12. (def powers-of-2 (new-seq (fn [x] (* 2 x)) 2))
  13. (powers-of-2 :value) ; 2
  14. (((powers-of-2 :next) :next) :value) ; 8
  15. ; doesn’t it look like enumerator.MoveNext().MoveNext().Current in C#?

 

  1. // F#
  2. type Seq<'T> = {
  3.     value: 'T;
  4.     next: (unit -> Seq<'T>) }
  5.  
  6. let rec newSeq next value : Seq<'T> = {
  7. // return current value
  8.     value = value;
  9. // create a new sequence with the next value
  10.     next = (fun () -> newSeq next (next value))
  11. }
  12. // sequence of powers of 2
  13. let pow2Seq = newSeq (fun x -> x * 2) 2
  14. pow2Seq.value // 2
  15. pow2Seq.next().next().value // 8
  16. // doesn’t it look like enumerator.MoveNext().MoveNext().Current in C#?

 

Even though the final result looks like enumerator in C#, the approach is qualitatively different, since we do not change a state of an object. Our data remains immutable and functions pure.

 

Recursion

As it was already mentioned, changing the state of variables is not encouraged if simply not possible when using functional languages. Therefore, looping isn’t a suitable way of handling sequences of data, since loops rely on the changing of the counter state. An alternative is to utilize recursive function calls. In functional world, recursion is considered as an idiomatic way to handle repeatable operations. Interestingly, the original article by John McCarthy describing LISP was called “Recursive Functions of Symbolic Expressions and Their Computation by Machine”.

In fact, both recursion and looping are functionally identical, and every recursive algorithm can be replaced with loop and vice versa, while recursion is subjectively more expressive. There is a remarkable citation by L. Peter Deutsch regarding this matter: “To iterate is human, to recurse, divine.” While being a simple and elegant solution for certain problems, recursion has several technical issues to be addressed: firstly, possible overflow of the call stack and secondly, unnecessary memory consumption.  Stack overflow appears to be a dread for most of the languages (including virtual machines like JVM & CLR), since they utilize the call stack of fixed size. On the other hand, some languages have no such limitation, notably Racket can dynamically extend the call stack, until it reaches a memory limit of the virtual machine. Nevertheless, there are other approaches to overcome unnecessary call stack consumption.

Often recursive functions end with the call to itself, such functions are called “tail-recursive” and can be easily optimized by compiler to a simple loop.

Let’s examine different types of recursive functions in contrast, starting with directly recursive functions without tail calls:

  1. ; Clojure no tail recursion
  2. (defn factorial-without-tail [x]
  3.   (if (< x 2)
  4.     1
  5.     (* x (factorial-without-tail (- x 1)))))
  6.  
  7. ; (factorial-without-tail 100000)
  8. ; Exception java.lang.StackOverflowError

 

  1. // Clojure binary decompiled into Java
  2. public static final Var const__2 = RT.var(
  3.   "clojure.core", "bigint");
  4.  
  5. public static Object invokeStatic(Object x) {
  6.   Object object;
  7.   if (Numbers.lt(x, 2L)) {
  8.     object = ((IFn)const__2.getRawRoot()).invoke(1L);
  9.   } else {
  10.     Object object2 = x;
  11.     Object object3 = x;
  12.     x = null;
  13.     object = Numbers.multiply(
  14.       object2,
  15.       // recursive, stack-consuming call
  16.       invokeStatic(Numbers.minus(object3, 1L)));
  17.   }
  18.   return object;
  19. }

 

  1. // F# no tail recursion
  2. let rec factorial (x : int) : bigint =
  3.     if x < 2
  4.     then 1I
  5.     else (bigint x) * factorial (x - 1)
  6.  
  7. // factorial 100000
  8. // Process is terminating due to StackOverflowException

 

  1. // F# binary decompiled into C#
  2. public static BigInteger factorial (int x) {
  3.   if (x < 2)
  4.     return BigInteger.One;
  5.   // recursive, stack-consuming call
  6.   return new BigInteger(x) * factorial (x - 1);
  7. }

 

These functions can be rewritten in a specific manner, so that compiler would detect a trivial possibility to convert the recursive calls into a simple loop:

  1. ; Clojure tail recursion
  2. (defn factorial [x]
  3.   (loop [x x, acc (bigint 1)]
  4.     (if (< x 2)
  5.       acc
  6.     (recur (- x 1) (* x acc)))))
  7. ; (factorial 100000)
  8. ; Gigantic number

 

  1. // Binary decompiled into Java
  2. public static final Var const__0 = RT.var(
  3.   "clojure.core", "bigint");
  4.  
  5. public static Object invokeStatic(Object x) {
  6.   Object object = x;
  7.   x = null;
  8.   Object x2 = object;
  9.   Object acc = ((IFn)const__0.getRawRoot()).invoke(1L);
  10.   // There is a loop on a place of recursion now!
  11.   do {
  12.     if (Numbers.lt(x2, 2L)) break;
  13.     Number number = Numbers.minus(x2, 1L);
  14.     Object object2 = x2;
  15.     x2 = null;
  16.     Object object3 = acc;
  17.     acc = null;
  18.     acc = Numbers.multiply(object2, object3);
  19.     x2 = number;
  20.   } while (true);
  21.   Object object4 = acc;
  22.   acc = null;
  23.   return object4;
  24. }

 

  1. // F# tail recursion
  2. let factorial (x : int) : bigint =
  3.     let rec loop x acc : bigint =
  4.         if x < 2
  5.         then acc
  6.         else loop (x - 1) ((bigint x) * acc)
  7.     loop x 1I
  8.  
  9. // factorial 100000
  10. // Gigantic number

 

  1. // Binary decompiled into C#
  2. internal static BigInteger loop(int x, BigInteger acc) {
  3.   int num;
  4.   // There is a loop on a place of recursion now!
  5.   for (; x >= 2; x = num) {
  6.     num = x - 1;
  7.     acc = new BigInteger(x) * acc;
  8.   }
  9.   return acc;
  10. }
  11.  
  12. public static BigInteger factorial(int x) {
  13.   return loop(x, BigInteger.One);
  14. }

 

Although some algorithms cannot be trivially converted into a simple loop, especially mutually recursive ones:

  1. ; Clojure mutual recursion
  2. (declare r2) ; forward reference
  3.  
  4. (defn r1 [i call-stack]
  5.   (let [call-stack (cons (str "r1 " i) call-stack)]
  6.     (if (< i 1)
  7.       call-stack
  8.       (r2 (- i 1) call-stack))))
  9.  
  10. (defn r2 [i call-stack]
  11.   (let [call-stack (cons (str "r2 " i) call-stack)]
  12.     (if (< i 1)
  13.       call-stack
  14.       (r1 (- i 1) call-stack))))
  15.  
  16. ; (r1 10000 nill)
  17. ; Exception java.lang.StackOverflowError

 

  1. // F# mutual recursion
  2. let rec r1 (i : int) (callStack : list<string>)=
  3.     let call = String.Format("r1 {0}", i)
  4.     let callStack = call::callStack
  5.     if i < 1
  6.     then callStack
  7.     else r2 (i - 1) callStack
  8. and r2 (i : int) (callStack : list<string>) =
  9.     let call = String.Format("r2 {0}", i)
  10.     let callStack = call::callStack
  11.     if i < 0
  12.     then callStack
  13.     else r1 (i - 1) callStack
  14. // r1 10000
  15. (* Surprisingly F# compiler is able to optimize mutual tail-recursive functions! *)

 

In case when tail call optimization is not an option, there is a universal cure called “trampoline”. Trampoline is just a special kind of function that calls the function that was supplied to it: if the value returned by the supplied function is a function as well, then trampoline repeats until the returned value is not a function. Trampoline, while being a last-ditch action against stack consumption, requires target recursive functions to be rewritten in a specific manner:

  1. ; Clojure
  2. ; Trampoline source code:
  3. (source trampoline)
  4. (defn trampoline
  5.   "trampoline can be used to convert algorithms requiring mutual
  6.  recursion without stack consumption. Calls f with supplied args, if
  7.  any. If f returns a fn, calls that fn with no arguments, and
  8.  continues to repeat, until the return value is not a fn, then
  9.  returns that non-fn value. Note that if you want to return a fn as a
  10.  final value, you must wrap it in some data structure and unpack it
  11.  after trampoline returns."
  12.   {:added "1.0"
  13.    :static true}
  14.   ([f]
  15.      (let [ret (f)]
  16.        (if (fn? ret)
  17.          (recur ret)
  18.          ret)))
  19.   ([f & args]
  20.      (trampoline #(apply f args))))

 

  1. ; Clojure
  2. (declare r2)
  3.  
  4. (defn r1 [i call-stack]
  5.   (let [call-stack (cons (str "r1 " i) call-stack)]
  6.     (if (< i 1)
  7.       call-stack
  8. ; return a closure instead of recursive call
  9.       #(r2 (- i 1) call-stack))))
  10.  
  11. (defn r2 [i call-stack]
  12.   (let [call-stack (cons (str "r2 " i) call-stack)]
  13.     (if (< i 1)
  14.       call-stack
  15. ; return a closure instead of recursive call
  16.       #(r1 (- i 1) call-stack))))
  17.  
  18. (trampoline r1 10000 nil)
  19. ; OK! Prints the history of recursive calls

 

In conclusion about recursion, it is essential to point out that it is absolutely unnecessary to write recursive functions every time you need to simply transform a data sequence or perform iterative action. In every functional language these operations are generalized by functions like map, reduce, or similar ones:

  1. ; Clojure
  2. ; some numbers:
  3. (def data [1 2 3 4 5])
  4. ; their sum:
  5. (def sum (reduce + data))
  6. ; their percents of a sum:
  7. (def percents (map #(/ % sum) data))
  8. ; print each percent into output
  9. (doseq [x percents] (println x))

 

  1. // F#
  2. (* this is just example, consider using rational numbers in real projects instead *)
  3. // some numbers:
  4. let data = [|1m;2m;3m;4m;5m|]
  5. // their sum:
  6. let sum = data |> Seq.reduce(
  7.     fun x y -> x + y)
  8. // their percents of a sum:
  9. let percents = data |> Seq.map(
  10.     fun x -> x / sum)
  11. // print each percent into output
  12. percents |> Seq.iter Console.WriteLine

 

  1. // C#
  2. /* this is just example, consider using rational numbers in real projects instead */
  3. var data = new decimal[] { 1, 2, 3, 4, 5 };
  4. /* Indeed, LINQ borrowed functional 'reduce' in form of Aggregate */
  5. var sum = data.Aggregate((x, y) => x + y);
  6. /* and functional 'map' in form of Select */
  7. var percents = data.Select(x => x / sum);
  8. /* here we still have to iterate */
  9. foreach (var p in percents)
  10.     Console.WriteLine(p);

 

Summary

So far, we have briefly examined the four pillars of functional paradigm:

  1. Immutability
  2. Purity
  3. First-class functions
  4. Recursion

 

Interestingly, most of the object-oriented features have respective alternatives in functional programming:

Goal

Imperative/OOP

FP

Binding data & behaviour

Class -> Object

Closures

Decoupling from concrete implementation

Interface

Function signature

Encapsulation

Access modifiers

Immutability, Closures

 

It is remarkable, considering fact that the functional paradigm is notably older than the object oriented one. From my perspective, it seems like the functional paradigm superseded its time with its features, while imperative languages had to evolve rediscovering them when facing the challenges of growing complexity.

Regarding this matter, the opinion of object-oriented pioneer Alan Key is quite thought-provoking: OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP”. His view appears different to a common perspective about what object-orientation truly means.

For me personally, OOP is remarkable for reasons rather philosophical than technical, while technically it is rather close if not inferior to functional programming. Object-oriented perspective is crucially important in modeling the system in the way of reducing the mismatch between mental and software model of the system, while following functional practices may significantly simplify technical issues of reliability, scalability, and complexity.

This is not about superiority of one paradigm over another. You should treat languages like tools, more or less, suitable to perform a specific task.

However, taking into account the power of modern hardware and expressive power of functional paradigm, you should consider its application in practice.

While using functional languages in concrete commercial software maybe the matter of discussion, it is undoubtedly should be a default choice of learning the programming for beginners.

According to Dijkstra: “A fundamental reason for the preference is that functional programs are much more readily appreciated as mathematical objects than imperative ones, so that you can teach what rigorous reasoning about programs amounts to.”

Finally, functional programming, being declarative, provokes wishful thinking, which is a superior quality of having the own vision of what should be rather than adjusting yourself to existing circumstances.

References

If you have found this material interesting, consider the following resources:

https://web.mit.edu/alexmv/6.037/sicp.pdf

http://www.paulgraham.com/articles.html

https://clojure.org/

https://fsharp.org/

https://racket-lang.org/

Need an innovative and reliable IT consultant?

Let's connect

Contact us

Thank you for reaching out to Sigma Software! Please fill the form below. Our team will contact you shortly.