The Pillars of Functional Programming (Part 1)

Nikolay Mozgovoy

Until now, it was hard to call functional programming a mainstream practice. It still remains not well understood and is perceived as a topic rather obscure if not with the enigmatic halo and awe.

Even though respected gurus like Robert Martin, Rich Hickey, Mark Seeman, and others try to promote it, not so many developers practice it consciously. Nevertheless, the functional paradigm itself slowly but surely sneaks into our general-purpose languages and tools sometimes giving new names and applications to fairly old concepts. Just consider Reactive Extensions, React, Redux, LINQ, Java Streams, and C# 8 as a superficial example of this process. In this article, we will try to figure out what is the foundation of the functional paradigm. Why does it really matter? What features make it close to still dominant object-oriented programming?

 

Case History of Functional Programming

When looking at the functional programming as a modern trend, it is interesting to note that this is in fact one of the oldest paradigms. It is even older then structural programming and the times when Go To statement became considered harmful! Here is a short list of programming paradigms with the respective time of their appearance:

  • Imperative:
    • Machine (1940s);
    • Procedural (1960s – FORTRAN, ALGOL, COBOL, BASIC);
    • Structured (1966-1968 “Go To Statement Considered Harmful” by Dijkstra);
    • Object-oriented (1967 - Simula, 1972 - Smalltalk);
    • Event-driven (1970s);
  • Declarative:
    • Functional (1958 - LISP);
    • Logic (1972 - Prolog);
    • Domain-specific (1974 - SQL);
    • Functional reactive (1997-2000 Paul Hudak).

 

So, the story begins back in 1958 with creation of LISP, which was and remains an overwhelmingly powerful language, and you can learn more about it in our special article. LISP was created by John McCarthy who was a pioneer of Artificial Intelligence in the way that the term AI itself was coined by him. For the foundation of his new language, he took the concept of Lambda Calculus, a distinctive notation for function. That’s where the term “lambda” originally came from and then spread among various languages.

Lambda Calculus was developed in 30s by Alonzo Church and can be considered as an alternative to a Turing machine. In fact, both scientist were solving the same problem at the same time though they came up to it with different approaches. Turing machine is virtually a state machine, in other words it has a set of states and the rules of transition between them. Lambda calculus, on the other hand, does not operate the state at all, it is stateless. This difference in theoretical approaches led to fundamentally different design of the future programming languages and was naturally reflected with the first two high-level languages: Fortran and LISP, respectively.

Programming in FORTRAN and its successors (including C, C++, Java) or any other imperative language is actually programming a state machine, while programming in LISP and functional languages looks like a composition of recursive functions.

This difference is so crucial that it actually affects the way of thinking.

At this point I should admit that, in reality, most of the functional languages allows a programmer to bring in some imperative code, though this this is not “idiomatic” way and rarely justified.

Over the time, there were many functional languages developed, let’s mention the most prominent ones:

  • LISP – 1958;
    • Scheme – 1970;
      • Racket – 1994;
    • Common Lisp – 1984;
    • Clojure – 2007;
  • ML (Meta Language) – 1973;
    • OCaml -1996;
    • F# - 2005;
  • Erlang – 1986;
  • Haskell – 1990;
  • Scala – 2004.

There is a troubling question why functional languages were almost completely whipped out of industry and given up the market to imperative (procedural and later object-oriented) languages? Wasn’t that an evidence of their inferiority and if so, why are we experiencing the comeback of functional practices nowadays?

For that reason, we should point out that functional languages being declarative are indeed more abstract and expressive, but such qualities cannot be easily achieved without trade-offs in performance. Therefore, imperative languages appeared to be superior at the time when personal computers were rising, and every byte counted.

Nevertheless, functional languages did survive. Firstly, they were continuously evolving in academic environment for an obvious reason of closeness to math together with availability of powerful mainframes. Secondly, functional languages were constantly finding application in solving cutting-edge problems even by private companies. One of prominent applicants was Xerox, which employed LISP in its pioneering workstations that featured one of the first graphical user interfaces. Another but truly remarkable was experience of employing the Erlang system by Ericson in building distributed telecom systems. It appeared that building the same system in functional Erlang compared to C++ shortens the codebase three times, while almost doubling the performance!

Software Development
Looking for a technological partner to make working software solutions?

We have outstanding track record in many knowledge-savvy industries.

This is an important point, because previously we admitted that declarative expressiveness indeed comes with trade-off in performance, and this is still true, while another truth is that imperative approaches cease to work at some degree of system complexity. For simplicity it can be explained in two ways: either human intelligence fails to efficiently model a distributed system like a state machine or a state machine is an incorrect way to model such systems. Keeping that in mind, let’s take into account the radical change in hardware we experienced during the last decade and a half (Images 1-3). We came from single processor workstations to dozen-core smartphones, while the line between fast RAM and formerly slow persistent storage is blurring. Modern software should utilize these powers efficiently and reliably. While imperative approach naturally fits programming a single calculator such as Turing machine, it seems to be not suitable for handling parallel, distributed, heterogeneous computations.

CPU cores trend

Image 1. CPU cores trend (cores/year)

 

GPU cores trend

Image 2. GPU cores trend (cores/year)

 

RAM price trend

Image 3. RAM price trend ($ per Mbyte/year)

 

The Pillars of Functional Programming

Every object-oriented developer should be well familiar with the so called Four Pillars OOP:

  1. Encapsulation
  2. Inheritance
  3. Polymorphism
  4. Abstraction

 

Since it is a familiar approach, it would be suitable to represent the key features of the functional paradigm in the same way.

So, the Four Pillars of the Functional Programming would be:

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

 

Herein below we will describe them precisely and see that in addition to them some OO features are not just achievable, but appear to be a natural part of functional languages as well.

 

Immutability

Immutability is a default property of all functional data structures and variables, which means impossibility to change an object state once it was created.

Being a quite harsh and strange restriction at first glance, immutability appeared to be a really valuable property having the following benefits:

  • Simplified reasoning of program behavior
  • Simplified application of immutable objects (no temporal coupling)
  • Simplified testing
  • Thread-safety by-default
  • Allows safe sharing of data

 

  1. ; Clojure
  2. (def animals (list "dog" "cat" "rat"))
  3. (cons "horse" animals) ; returns a new list of animals, not changing existing one
  1. // F#
  2. let animals = ["dog";"cat";"rat"]
  3. let moreAnimals = List.append animals ["horse"] // returns a new list
  1. // C#
  2. var animals = new ReadOnlyCollection<string>(new [] { "dog", "cat", "rat" });
  3. var moreAnimals = animals.Append("horse"); // returns a new Enumerable

 

There is still an important argument that arises against immutability, which claims on inefficeient memory consumtption caused by necessity to recreate an object each time we need to have it in a different state.

While being true, to some degree, that property of immutability has a relatively higher demand on memory, it isn’t that simple under the hood. In fact, functional languages heavily utilize the sharing of the data across created data structures, which is safe and intuitive optimization considering impossibility to change existing data.

Consider an example illustrated on Image 3: adding the “Rat” to the list of animals does not really recreate nor change existing list, this operation indeed creates a new list, but this new list consists of a new record plus reference to the existing list!

Data sharing across immutable data structures

Image 4. Data sharing across immutable data structures

 

Now it is important to point out that demand of immutability should already be very close for developers familiar with the OO notion of encapsulation.

The notion of encapsulation is mainly risen as an attempt to make the flow of the program state more predictable, and the functional principle of immutability brings this quality to the extreme.

Another interesting quality of immutability is that you can consider it as a prototype pattern built into language by default:

  1. ; Clojure
  2. (defrecord color [R G B])
  3.  
  4. (def green ; create green color
  5.     (color. 0 255 0))
  6. (def yellow ; create yellow from green
  7.     (update green
  8.         :R (fn [_] 255)))
  9. (def red ; create red from yellow
  10.     (update yellow
  11.         :G (fn [_] 0)))
  12. ; no initial color changed its state:
  13. ; user=> green
  14. ; {:R 0, :G 255, :B 0}
  15. ; user=> yellow
  16. ; {:R 255, :G 255, :B 0}
  17. ; user=> red
  18. ; {:R 255, :G 0, :B 0}
  1. // F#
  2. type Color = {
  3.     R: byte
  4.     G: byte
  5.     B: byte
  6. }
  7. // create green color
  8. let green = { R = 0uy; G = 255uy; B = 0uy }
  9. // create yellow from green
  10. let yellow = { green with R = 255uy }
  11. // create red from yellow
  12. let red = { yellow with G = 0uy }
  13. // no initial color changed its state:
  14. // > green
  15. // { R = 0uy; G = 255uy; B = 0uy }
  16. // > yellow    
  17. // { R = 255uy; G = 255uy; B = 0uy }
  18. // > red
  19. // { R = 255uy; G = 0uy; B = 0uy }
  1. // C#
  2. public class Color {
  3.     public Color(byte r, byte g, byte b) {
  4.         this.R = r;
  5.         this.G = g;
  6.         this.B = b;
  7.     }
  8.  
  9.     public byte R { get; }
  10.     public byte G { get; }
  11.     public byte B { get; }
  12.  
  13.     public Color WithRed(byte red) =>
  14.         new Color(red, this.G, this.B);
  15.     public Color WithGreen(byte green) =>
  16.         new Color(this.R, green, this.B);
  17.     public Color WithBlue(byte blue) =>
  18.         new Color(this.R, this.G, blue);
  19. }
  20. var green = new Color(0, 255, 0);
  21. var yellow = green.WithRed(255);
  22. var red = yellow.WithGreen(0);
  23. /* Same behavior achieved in C# with significant extra code */
  24. // > red
  25. // { B=0, G=0, R=255 }
  26. // > yellow
  27. // { B=0, G=255, R=255 }
  28. // green
  29. // { B=0, G=255, R=0 }

 

Purity

Purity is the property of functions not to have side-effects and any dependence on external state or time.

As we have already mentioned, Lambda calculus as the basis of functional programming, has nothing to do with the state or interaction with the real world, it’s just pure mathematical notation, therefore, such property is a default expectation from functional languages.

A function is considered pure when:

  • The function always evaluates the same result value given the same argument value(s);
  • Evaluation of the result does not cause any side effect.

The property of purity has very similar benefits to the immutability:

  • Simplified reasoning of program behavior;
  • Simplified application of pure functions;
  • Simplified testing;
  • Thread-safety by-default;
  • Allows memorization.

We must confess that purity is not achieved that simple, since real software has to interact with the real world, and the real word has mutable states and changes over time. There are many approaches to that problem, it is not completely solved yet while the topic itself deserves an article of its own. Anyways, many functional languages allow having a mutable state as well as impure functions, although such possibility is intended to be used with caution and vigilance. Note how LISP and F# use a naming convention and special syntax to distinguish impure operations.

  1. ; in LISP
  2. (define (inc x) (+ x 1)) ; pure function
  3.  
  4. (define i 1)
  5. (define (bad-inc!) (set! i (+ i 1))) ; impure function, changing global variable
  1. // in F#
  2. let inc x = x + 1 // pure function
  3. // mutable variables in F# have to be declared explicitly
  4. let mutable i = 0
  5. // impure function, changing global variable using special operator <-
  6. let badInc () = i <- i + 1
  1. // in C#
  2. Math.Pow(2, 8); // pure function
  3. Path.GetTempFileName(); // impure function, returns randomized values
  4. DateTime.Now; // impure function, operates time

 

And again, the property of purity should be well familiar for OO developers who strive to cover their code with robust unit tests and isolate dependencies on file system, network, time, etc. In case of using functional languages, they enforce a developer to follow such discipline.

 

First-class functions

This feature is a really distinctive one and draws the line between languages that can be called functional and that can’t. If previous features (immutability and purity) indeed can be achieved by mere discipline, availability of first-class functions can be hardly determined by language. First-class functions is a feature of programming language to treat functions as a standard datatype, just like integers, characters, etc. In other words, it allows a programmer to create functions in runtime, pass them as function arguments, and return them from function calls.

Note that in this context you may often face another related term as “Higher-order functions.” To be precise, higher order functions is a limited feature compared to first-class functions, which allows a developer to pass functions as an argument or return as a result of function evaluation, but not necessarily creating them in runtime. In that way, a procedural language like C supports higher-order functions, but not first-class functions, therefore, cannot be called a functional language.

Treating functions as a separate datatype is a natural way to achieve polymorphism, in other words, ability of a single function (or algorithm) to process multiple datatypes. Therefore, all functional languages support polymorphism.

This can be easily understood from familiar object-oriented perspective when you consider a function signature as an interface, while every function with such signature is a respective implementation of such interface.

As an example of this quality, consider a sorting function, which is able to sort unlimited number of types by unlimited number of rules:

  1. ; Clojure
  2. (def numbers [7 4 1 2 3])
  3. ; ascending is a first-class function, created at runtime
  4. (def ascending (fn [a b] (- a b)))
  5. ; sort is a higher-order function, taking comparison function as an argument
  6. (sort ascending numbers) ; (1 2 3 4 7)
  7. (sort (fn [a b] (- b a)) numbers) ; (7 4 3 2 1)
  8.  
  9. ; Using data structures from previous example
  10. (def colors [green yellow red])
  11. (defn luminance [color] (+
  12.   (* 0.2126 (:R color))
  13.   (* 0.7152 (:G color))
  14.   (* 0.0722 (:B color))))
  15. ; Sort colors by luminance
  16. (sort (fn [c1 c2] (- (luminance c1) (luminance c2))) colors) ; red, green, yellow
  1. // F#
  2. let numbers = [7; 4; 1; 2; 3;]
  3. // ascending is a first-class function, created at runtime
  4. let ascending = fun a b -> a – b
  5. // List.sortWith is a higher-order function, taking comparison function as an argument
  6. numbers |> List.sortWith(ascending) // [1; 2; 3; 4; 7]
  7. numbers |> List.sortWith(fun a b -> b - a) // [7; 4; 3; 2; 1]
  8.  
  9. let luminance color =
  10.     2126 * (int)color.R +
  11.     7152 * (int)color.G +
  12.     0722 * (int)color.B
  1. // Using data structures from previous example
  2. let colors = [green; yellow; red;]
  3. // Sort colors by luminance
  4. colors |> List.sortWith(fun c1 c2 -> luminance c1 - luminance c2) // [red; green; yellow]

 

And that’s not all, the availability of first-class functions has a number of crucial consequences that are described in the continuation of this article: The Pillars of Functional Programming (Part 2).

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.