7
$\begingroup$

A YouTube video I was watching explained the differences between Imperative and Functional programming by demonstrating how the numbers from 1 to 10 are summed up in Java and in Haskell respectively.

In Java, you must explicitly state each step and assign the result of each step to a variable - something like the following

int total = 0;
     for (int i = 1; i <= 10; i++){
         total = total + i;
     }
return total;

In Haskell, you can simply say:

sum(1..10)

My question is: There obviously is something going on in the background of a Functional language, and that something must be some sort of Imperative process. It seems like Functional Languages are really just some sort of Imperative-Language APIs. For example, I can create part of a functional language by defining a method sum(int start, int end) in Java. Did I really create a new type of language right there, or did I just define a set of Imperative method calls that hide imperative instructions from you?

I hope it's clear what I am struggling to understand.

$\endgroup$
  • 1
    $\begingroup$ For exactly the reason you state, the example of the sum function is not a good one. $\endgroup$ – David Richerby Dec 3 '13 at 13:10
  • $\begingroup$ That's why it's called a style, as opposed to a new type of computer. $\endgroup$ – user253751 Oct 19 '17 at 5:02
9
$\begingroup$

If we peel off the syntactic sugar on the front and the code generation on the back and compare what happens in between when converting source to running code for imperative languages, such as C or Java with functional languages such as ML or OCaml we will generally find the following differences in what, why, and how.

Mutable vs. immutable

With functional programming one tends to use immutable values which means that we don't have to worry if a value changes by a means external to our current function. When used correctly this removes any problems related to side effects.

Focus: Data versus function.

When one thinks of coding in imperative one first thinks of data structures and then what methods they need, when working with functional programming one first thinks of what functions are needed and then makes the data types needed. Most of the data types are either lazy list, (think stream or infinite list) or discriminated unions. When the discriminated union is recursive you instantly have created a tree or graph without having to write all of walking code.

Generics/Parametric polymorphism

This one is interesting, and if I have my facts correct, was invented with functional programming and then transplanted to imperative programming. So if you like generics thank the functional language designers.

Referential transparency/Parallelization

Because of referential transparency functional code can be more easily ported to parallel computing.

Higher order function/compositionality

Since functions can create new functions and return functions, creating new functions is based on other functions is as easy as creating new expressions instead of writing entire new methods. This leads to morphisms which are very useful if the problem you are solving can be expessed with math. Doing set transformations, think SQL and updates, is so much easier with functional programming. As Wandering Logic noted this is where functional programming languages excel.

Typing: Static versus inference.

Since the types are inferred as opposed being set by the programmer during writing, more checks can be to ensure the correctness of the code and often the functions will be made generic as opposed to being of a set type.

Pattern Matching vs switch statement

When combining matching with discriminated unions, your matching is checked to ensure you have covered every outcome. How many times have you had a run time error because you missed a case with a switch statement.

$\endgroup$
  • $\begingroup$ “when working with functional programming one first thinks of what functions are needed and then makes the data types needed”: depends on what one is modelling. Especially recursive data‑types are an as much hot spot in FP as functions are. $\endgroup$ – Hibou57 Jul 22 '14 at 0:54
  • $\begingroup$ “When combining matching with discriminated unions, your matching is checked to ensure you have covered every outcome”: while (and as a side note), case statements are checked too, with Ada, which is imperative. Being imperative does not preclude pattern matching or coverage check. $\endgroup$ – Hibou57 Jul 22 '14 at 1:02
  • $\begingroup$ @Hibou57 Nice comments. I would be interested in seeing your answer. $\endgroup$ – Guy Coder Jul 22 '14 at 14:39
  • $\begingroup$ I agree that one can think in data first before functions as noted by Hibou57. So let me clarify this a bit. I tend to use functional languages for what they are good at, and use imperative languages for what they are good at, and use logic languages for what they are good at, etc., and don't have a problem using two or more languages for one problem, separating out task among the languages. So when I use a functional language I tend to think functions first and when I need persistent data I tend to think data first, and logic I use a logic language, etc. $\endgroup$ – Guy Coder Jul 22 '14 at 14:43
  • 1
    $\begingroup$ For the Ada case statement, here the reference: 5.4 Case Statements (for the last revision up to this date). In particular for that matter, note the wording about “cover”/“coverage” and the likes. $\endgroup$ – Hibou57 Jul 22 '14 at 14:48
8
$\begingroup$

A functional programming language is notable for what it prohibits. It prohibits modifying an existing variable or data structure. You can program in a "functional style" in some imperative programming languages, but the language won't protect you from accidentally modifying an existing variable or data structure. For example, here is a recursive, functional, version of sum in Java:

int sum(int start, int end) {
  if (start > end) return 0;
  else {
    int total = start + sum(start+1, end);
    return total;
  }
}

Where functional programming languages excel is that they all have "first-class" functions. That is: a function can be used as a value, just like an integer or a data structure. Some imperative languages also have first-class functions (notably C and C++), but in Java you have to fake it with an object with a single method (usually called apply() or something.) First-class functions allow us to generalize the sum function to a function that reduces any operator:

interface IntegerOperator {
  int apply(int a, int b);
}

int sum(IntegerOperator op, int start, int end) {
  if (start > end) return 0;
  else {
    int total = op.apply(start, sum(op, start+1, end))
    return total;
  }
}

class AdditionOperator implements IntegerOperator {
  int apply(int a, int b) { return a+b; }
}

int total = sum(new AdditionOperator(), 1, 10);

If I were writing in a functional programming language I would know that every function is really a function (it returns the same value every time it is called with the same parameters), so I would know that in:

int total1 = sum(new ReallyStrangeOperator(), 1, 10);
int total2 = sum(new ReallyStrangeOperator(), 1, 10);

total1 and total2 have the same value (so for example, I could optimize out the second call to sum), whereas in an imperative programming language I have no clue about whether ReallyStrangeOperator(1,2) returns the same value every time or not.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the really informative answer. I accepted the other one but I could have just as easily accepted yours and written this comment in the other. $\endgroup$ – CodyBugstein Dec 5 '13 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.