Declaring Vs Impering

After years of OO programming,  I had become quite used to the imperative approach to implementing algorithms. One of the beauties of functional programming is that it challenges you to adapt to a different way of thinking and to look at other ways of approaching problem solving, implementing algorithms, and indeed to designing software modules and complete systems.

Imperative programming is all about executing a sequence of steps, each of which, can mutate program state. Declarative programming, on the other hand, is more about declaring what you want a program or component to do with one or more immutable data structures and about linking these declarations together to implement declarations at higher abstraction levels or to form a pipeline of operations on immutable data structures. That difference may seem a bit abstract so lets dive into some code to show what I mean (and maybe learn some Clojure along the way if you are not already familiar with this wonderful language).

Looping

Even something as simple as a looping construct can be enough to show the difference between the imperative and declarative approach.

  
 
    public int sum(int[] nums) { 
        int result = 0; 
        for (int i = 0; i < nums.length; i++) { 
            result += nums[i]; 
        } 
        return result; 
    } 

 

This example is a typical for loop written in Java. The algorithm to sum up an array of numbers is implemented as a sequence of steps which are repeated on the updated mutable variables – the counter variable, i, and the accumulator variable, result.

The Functional Programming approach in implementing this algorithm would be to use recursion to declare the operation to be performed on the array. The following is an example of this declarative approach in Clojure. numbers here is a Vector in Clojure similar to an array.

(defn sum [numbers] 
  (let [go (fn go [numbers result] 
             (if (seq numbers) 
               (go (rest numbers) (+ result (first numbers))) 
               result))] 
    (go numbers 0)))

In the example above, there is an inner function declared called go. This function takes, as parameters, the current immutable state of the numbers collection that it is summing up and also the current immutable result. These arguments are, at runtime, immutable values created for every call to the go function. When executed, this function will return the result if there are no more numbers to process – (seq numbers) returns a falsey value in this case – or else the go function recursively calls itself passing in the rest of the numbers to process along with a new result value calculated from adding the head of the current nums vector to the current result.

Note here that (rest numbers) creates a new immutable Vector with the same numbers except omitting the first number.

Also

(+ result (first numbers))

returns a newly calculated immutable result value.

This implementation can be simplified in Clojure using the loop construct below.

(defn sum-with-loop [numbers] 
  (loop [nums numbers 
         result 0] 
    (if (seq nums) 
      (recur (rest nums) (+ result (first nums))) 
      result)))


In this code, the inner go function is replaced with (loop
which also allows its parameters to be initialized.

(recur..here is a Clojure construct which will recursively execute loop with new arguments. The benefit of using the recur construct in Clojure is that it uses tail recursion. This means that, provided the recursive call is the very last evaluation of the function, the function’s stack frame can be reused for the recursive call meaning that stack overflow can be avoided for large data structures.

Implementing a loop is a reletively low level abstraction but, even at this abstraction level, we can see the difference between the imperative and declarative approach. The imperative for loop uses mutable variables to specify, quite explicitly, a sequence of steps to be implemented. The functional declarative approach uses recursion and more so describes, at a higher level, what we want the program to do. We are literally just saying
“Is the Vector empty? if so just give us back the aggregate but, if not..”
“Produce a new aggregate by adding the top of the list to the current aggregate”
“Now just go ahead and do all that again but with the rest of the Vector as a new Vector…oh and use the new aggregate”.

Declaring At Higher Abstraction Levels

In functional programming, pure functions are composed to create new pure functions. By a pure function, I mean a function which always returns the same output value(s) for the same input value(s) for all possible input values.
So, often in functional programming, there is no need to implement low level recursive loops. Instead functions at higher abstraction levels can be used instead and there are many common functions that are provided in all functional programming languages. The declarative approach really shines when using these higher level functions. Implementations become a lot more concise and readable compared to their corresponding imperative implementations.

Lets look at an example of this. So, say we want to transform a list of numbers into a new list by taking just the even numbers and multiplying them by n.

The following is an imperative approach written in Java – this can be done in a declarative way with Java 8’s functional programming features but the example here is to show the imperative approach that is common in OO programming.

 
 
    public List<Integer> multiplyEvenNumbersBy(List<Integer> nums, int n) { 
        List<Integer> result = new ArrayList<Integer>(); 
 
        for (Integer x : nums){ 
            if(x % 2 == 0) { 
                result.add(x * n); 
            } 
        } 
 
        return result; 
    }

Now, below we implement the same function in a declarative way in Clojure.

(defn multiply-even-numbers-by [nums n] 
  (->> nums (filter even?) (map #(* % n))))

In the declarative approach, we can use these higher abstracted functions called filter and map to declare exactly what we want to do do:

“Give me a sequence of just the even numbers with each one multiplied by n”.

#(* % n) is a shorter way to write anonymous functions in Clojure with % being an argument passed to this one arg function which multiplies its argument by n.

Again everything is immutable in the declarative approach unlike the mutable variables that are used in the imperative approach.

Laziness

The other beauty about the declarative approach using map and filter is that this declarative approach is lazy. It is using lazy sequences in Clojure which are only actually evaluated if they are needed.

(->> nums (filter even?) (map #(* % n)))

The above does not actually immediately produce a new sequence. Instead, it builds up a composition of functions, a functional pipeline, which will be executed to produce elements of this new sequence as they are needed.

For example, lets take a Vector of numbers and, from it, create a new sequence with each number multiplied by 2.
This example is executed directly in the Clojure REPL (read eval print loop console that allows immediate execution of Clojure code.)
It is common to do this in Functional Programming using a utility map function. This takes a data structure and a function to be performed on each element in the data structure in order to produce a new data structure.

(def result (map (fn [x] (println "executing") (* x 2)) [1 2 3]))
=> #'clojure-blogs.core/result

In the above Clojure code, we are declaring that the functional pipeline to map the Vector [1 2 3], into a new sequence, be bound (like ‘assigned to’ in a language with mutable variables) to the Symbol (like a variable) result. A println “executing” side effect (interaction with the function’s outside environment) has been added to the mapping function in order to prove that this function is not executing until one or more elements of the resulting sequence are actually required.
The code above is executed immediately and we can see the result simply prints the the new Symbol with the namespace clojure-blogs.core and name result. The Vector has not yet been transformed and the mapping function has not yet actually been executed. All we have done here is build up a functional pipeline on the original Vector which will be later executed on one element or more elements if their resulting elements are required.

Now, lets actually use result in order to force evaluation of the mapping function and the production of our new Vector.

result 
executing 
executing 
executing 
=> (2 4 6)

In the above code, we reference the result Symbol in the REPL. Now, result needs to be evaluated meaning that the functional pipeline that it references needs to be executed on each element to produce elements of the resulting sequence.
We are transforming every element of the Vector here but we could instead ask for one or more elements at a time meaning that the pipeline is, in turn, executed on each of these elements at a time to produce a new element. We can now clearly see that our map function has been eventually executed 3 times – 1 time for each number in the original Vector.

Conclusion

The declarative approach of Functional Programming can be a bit of a mind shift when coming from a more imperative OO background. It certainly was for me but it was a very positive mind shift. It makes for much more concise code and, in my opinion, it allows us to move up abstraction levels more easily and take on more complex problems without having to keep so much in our head at once.

I would always encourage other developers to stick with what might be a new way of thinking for them as it really can reap great rewards. I know, after years of writing imperative code, seeing more declarative code can seem a bit foreign and it can seem like it will take too long to get to grips with – especially when multiple data transformations like filters and maps are chained together. It is always a good approach to make sure that each of the smaller transformation functions and also the functions passed as parameters to them, are kept small, pure and well named. If it seems like its too much trying to understand a functional pipeline with multiple maps, filters flatMaps etc, I always think…”imagine if this had been written imperatively though and all the extra loops, branches and mutable state I would have to comprehend – all that extra stuff I would have to hold in my head” – I know.. if imperative code is well abstracted and organized, it should be easier to read but, in my opinion, writing declarative code can in itself bring us a step towards code that is easier to read, understand and maintain.

The declarative approach really shines when used in conjunction with laziness – complex functional pipelines that are only executed on an element of a data structure, if it is required for that element to be evaluated. These pipelines don’t even always need to have a tangible data structure to operate on, and can even produce their own data structures one element at a time – this is the concept of infinite sequences which I will get to in an upcoming blog post.

Thanks!

Thanks so much for taking time to read this blog. I really hope it has helped in other peoples’ functional journeys.
Feel free to leave feedback in the comments.

Leave a Reply

Your email address will not be published. Required fields are marked *