JVM Advent

The JVM Programming Advent Calendar

Functional vs Imperative Programming. Fibonacci, Prime and Factorial in Java 8

There are multiple programming styles/paradigms, but two well-known ones are Imperative and Functional.

Imperative programming is the most dominant paradigm as nearly all mainstream languages (C++, Java, C#) have been promoting it. But in the last few years functional programming started to gain attention. One of the main driving factors is that simply all new computers are shipped with 4, 8, 16 or more cores and it’s very difficult to write a parallel program in imperative style to utilize all cores. Functional style moves this difficultness to the runtime level and frees developers from hard and error-prone work.

Wait! So what’s the difference between these two styles.

Imperative programming is a paradigm where you tell how exactly and which exact statements machine/runtime should execute to achieve desired result.

Functional programming is a form of declarative programming paradigm where you tell what you would like to achieve and machine/runtime determines the best way how to do it.

Functional style moves the how part to the runtime level and helps developers focus on the what part. By abstracting the how part we can write more maintainable and scalable software.

To handle the challenges introduced by multicore machines and to remain attractive for developers Java 8 introduced functional paradigm next to imperative one.

Enough theory, let’s implement few programming challenges in Imperative and Functional style using Java and see the difference.

Fibonacci Sequence Imperative vs Functional (The Fibonacci Sequence is the series of numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, … The next number is found by adding up the two numbers before it.)

Fibonacci Sequence in iterative and imperative style

public static int fibonacci(int number) {
  int fib1 = 1;
  int fib2 = 1;
  int fibonacci = fib1;
  for (int i = 2; i < number; i++) {
    fibonacci = fib1 + fib2;
    fib1 = fib2;
    fib2 = fibonacci;
  }
  return fibonacci;
}

for(int i = 1; i  <= 10; i++) {
  System.out.print(fibonacci(i) +" ");
}
// Output: 1 1 2 3 5 8 13 21 34 55 

As you can see here we are focusing a lot on how (iteration, state) rather that what we want to achieve.

Fibonacci Sequence in iterative and functional style

IntStream fibonacciStream = Stream.iterate(
    new int[]{1, 1},
    fib -> new int[] {fib[1], fib[0] + fib[1]}
  ).mapToInt(fib -> fib[0]);

fibonacciStream.limit(10).forEach(fib ->  
    System.out.print(fib + " "));
// Output: 1 1 2 3 5 8 13 21 34 55 

In contrast, you can see here we are focusing on what we want to achieve.

Prime Numbers Imperative vs Functional (A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.)

Prime Number in imperative style

public boolean isPrime(long number) {  
  for(long i = 2; i <= Math.sqrt(number); i++) {  
    if(number % i == 0) return false;  
  }  
  return number > 1;  
}
isPrime(9220000000000000039L) // Output: true

Again here we are focusing a lot on how (iteration, state).

Prime Number in functional style

public boolean isPrime(long number) {  
  return number > 1 &&  
    LongStream
     .rangeClosed(2, (long) Math.sqrt(number))  
     .noneMatch(index -> number % index == 0);
}
isPrime(9220000000000000039L) // Output: true

Here again we are focusing on what we want to achieve. The functional style helped us to abstract away the process of explicitly iterating over the range of numbers.

You might now think, hmmm, is this all we can have …. ? Let’s see how can we use all our cores (gain parallelism) in functional style.

public boolean isPrime(long number) {  
  return number > 1 &&  
    LongStream
    .rangeClosed(2, (long) Math.sqrt(number))
    .parallel()  
    .noneMatch(index -> number % index == 0);
}
isPrime(9220000000000000039L) // Output: true

That’s it! We just added .parallel() to the stream. You can see how library/runtime handles complexity for us.

Factorial Imperative vs Functional ( The factorial of n is the product of all positive integers less than or equal to n.)

Factorial in iterative and imperative style

public long factorial(int n) {
  long product = 1;
  for ( int i = 1; i <= n; i++ ) {
    product *= i;
  }
  return product;
}
factorial(5) // Output: 120

Factorial in iterative and functional style

public long factorial(int n) {
 return LongStream
   .rangeClosed(1, n)
   .reduce((a, b) -> a *   b)
   .getAsLong();
}
factorial(5) // Output: 120

It’s worth repeating that by abstracting the how part we can write more maintainable and scalable software.

To see all the functional goodies introduced by Java 8 check out the following Lambda Expressions, Method References and Streams guide.

Author: Artur Mkrtchyan

Software Engineer living in Berlin.
Technology Leader and Continuous Learner with 10+ years of experience. Excellent Leader with an experience building cross-functional engineering teams and highly scalable products, especially using open-source software.

Next Post

Previous Post

3 Comments

  1. Dr Alexander J Turner December 14, 2015

    Hi,

    Whilst this is informative I find it hard to swallow that ‘what we want to achieve’ for the fibonacci functional style is creating a new array for every iteration. This is just bonkers. How about making a functional style which is at least within an order of magnitude of the imperative style? This must be possible. Without that, your post is really an anti-advert for functional programming; that is a shame because functional has a place in anyone’s tool kit.

    I was very disappointed indeed with Java lambdas; they offer almost nothing to the language other than a new syntax. The power of C++ lambdas when combined with templates makes a joke of Java’s attempts. I hope that people like yourself are able to claw back some of the damage done by coming up with performant and clear patterns using lambdas in Java. All this business about running over X cores is nonsense when the linear speed speed is orders of magnitude too slow. 100 times faster on one core always beats scaling over 16 cores. I am sorry to see micro computer programmers are learning the hare way the lessons learned by super computer programmers back in the 1990s.

    Thanks for the post and best wishes – AJ

    • Artur Mkrtchyan December 14, 2015 — Post Author

      Hi,

      I could definitely make functional fibonacci more performant but the point here was to make it as simple as possible. When performance is really critical and procedural style is performing better, one might choose to switch to it.

      What was your expectation from Java Lambdas ?

      I don’t know your experience with Super and Micro computers as you call them, but I enjoy the way technologies evolve now days.

      Thanks,
      Artur

  2. Dr Alexander J Turner December 15, 2015

    Hi Artur,

    I wish it were possible to make the functional method perform as well as imperative. Without that, the functional approach is always second best. The thing is, performance matters even from an environmental point of view.

    As for lambdas. If they had supported compile time polymorphic dispatch and were true closures then they would have offered something useful. Other than technical issues around the management of inner classes, the current lambda implementation in Java offers nothing new to the language other than a more brief syntax.

    For example, a C++ lambda can be used as a template argument to a function. Thus the function is reified into a monomorphic dispatch point to the lambda. Consequently, a lambda has not overhead even at the dispatch level. All of this is missing from Java so lambdas are always second class citizens to functions. However, Java lambdas are eagerly evaluated, so the are second class citizens to Haskell lambdas, They are neither one thing nor the other.

    I had hoped for a purity of implementation rather than a hack around in syntax implemented by hacking around with invoke dymanic. Invoke dynamic has no place in a statically typed language like Java. That was a huge mistake on the part of Oracle.

    Thanks for the reply – AJ

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

© 2024 JVM Advent | Powered by steinhauer.software Logosteinhauer.software

Theme by Anders Norén