What makes functional programming languages declarative as opposed to Imperative?

Question

On many articles, describing the benefits of functional programming, I have seen functional programming languages, such as Haskell, ML, Scala or Clojure, referred to as "declarative languages" distinct from imperative languages such as C/C++/C#/Java. My question is what makes functional programming languages declarative as opposed to imperative.

An often encountered explanation describing the differences between Declarative and Imperative programming is that in Imperative programming you tell the computer "How to do something" as opposed to "What to do" in declarative languages. The problem I have with this explanation is that you are constantly doing both in all programming languages. Even if you go down to the lowest level assembly you are still telling the computer "What to do", you tell the CPU to add two numbers, you don't instruct it on how to perform the addition. If we go to the other end of the spectrum, a high level pure functional language like Haskell, you are in fact telling the computer how to achieve a specific task, that is what your program is a sequence of instructions to achieve a specific task which the computer does not know how to achieve alone. I understand that languages such as Haskell, Clojure, etc. are obviously higher level than C/C++/C#/Java and offer features such as lazy evaluation, immutable data structures, anonymous functions, currying, persistent data structures, etc. all which make functional programming possible and efficient, but I wouldn't classify them as declarative languages.

A pure declarative languages for me would be one which is comprised entirely of declarations only, an example of such a languages would be CSS (Yes I know CSS would technically not be a programming language). CSS just contains style declarations which are used by the HTML and Javascript of the page. CSS cannot do anything else besides make declarations, it cannot create class functions, i.e. functions which determine the style to display based on some parameter, you cannot execute CSS scripts, etc. That for me describes a declarative language (notice I did not say declarative programming language).

Update:

I've been playing around with Prolog recently and to me, Prolog is the closest programming language to a fully declarative language (At least in my opinion), if it is not the only fully declarative programming language. To elaborate programming in Prolog is done by making declarations which state either a fact (a predicate function which returns true for a specific input) or a rule (a predicate function which returns true for a given condition/pattern based on the inputs), rules are defined using a pattern matching technique. To do anything in prolog you query the knowledge base by substituting one or more of the inputs of a predicate with a variable and prolog tries to find values for the variable(s) for which the predicate succeeds.

My point is in prolog there are no imperative instructions, you basically telling (declaring) the computer what it knows and then asking (querying) about about the knowledge. In functional programming languages you are still giving instructions i.e. take a value, call function X and add 1 to it, etc, even if you are not directly manipulating memory locations or writing out computation step by step. I wouldn't say that programming in Haskell, ML, Scala or Clojure is declarative in this sense, though I may be wrong. Is proper, true, pure functional programming declarative in the sense that I described above.

Answer 1

You seem to be drawing a line between declaring things and instructing a machine. There is no such hard-and-fast separation. Because the machine that's being instructed in imperative programming need not be physical hardware, there is much freedom for interpretation. Almost everything can be seen as an explicit program for the right abstract machine. For example, you could see CSS as a rather high level language for programming a machine that primarily resolves selectors and sets attributes of the thus-selected DOM objects.

The question is whether such a perspective is sensible, and conversely, how closely the sequence of instructions resembles a declaration of the result being computed. For CSS, the declarative perspective is clearly more useful. For C, the imperative perspective is clearly predominant. As for languages as Haskell, well…

The language has specified, concrete semantics. That is, of course one can interpret the program as a chain of operations. It doesn't even take too much effort to choose the primitive operations so that they map nicely onto commodity hardware (this is what the STG machine and other models do).

However, the way Haskell programs are written, they frequently can sensibly be read as a description of the result to be computed. Take, for example, the program to compute the sum of the first N factorials:

sum_of_fac n = sum [product [1..i] | i <- ..n]

You can desugar this and read it as a sequence of STG operations, but far more natural is to read it as a description of the result (which is, I think, a more useful definition of declarative programming than “what to compute”): The result is the sum the products of [1..i] for all i = 0, …, n. And that is far more declarative than almost any C program or function.

Answer 2

The basic unit of an imperative program is the statement. Statements are executed for their side effects. They modify the state they receive. A sequence of statements is a sequence of commands, denoting do this then do that. The programmer specifies the exact order to perform the computation. This is what people mean by telling the computer how to do it.

The basic unit of a declarative program is the expression. Expressions do not have side effects. They specify a relationship between an input and output, creating a new and separate output from their input, rather than modifying their input state. A sequence of expressions is meaningless without some containing expression specifying the relationship between them. The programmer specifies the relationships between data, and the program infers the order to perform the computation from those relationships. This is what people mean by telling the computer what to do.

Imperative languages have expressions, but their primary means of getting things done is statements. Likewise, declarative languages have some expressions with semantics similar to statements, like monad sequences inside Haskell's do notation, but at their core, they are one big expression. This lets beginners write code that is very imperative-looking, but the true power of the language comes when you escape that paradigm.

Answer 3

The real defining characteristic that separates declarative from imperative programming is in declarative style you are not giving sequenced instructions; at the lower level yes the CPU operates this way, but that's a concern of the compiler.

You suggest CSS is a "declarative language", I wouldn't call it a language at all. It's a data structure format, like JSON, XML, CSV, or INI, just a format for defining data that's known to an interpreter of some nature.

Some interesting side effects happen when you take the assignment operator out of a language, and this is the real cause for losing all those step1-step2-step3 imperative instructions in declarative languages.

What do you do with the assignment operator in a function? You create intermediate steps. That's the crux of it, the assignment operator is used to alter data in a step-by-step fashion. As soon as you can no longer alter data, you lose all of those steps and end up with:

Every function has only one statement, this statement being the single declaration

Now there are many ways to make a single statement look like many statement, but that's just trickery, for instance: 1 + 3 + (2*4) + 8 - (7 / (8*3)) this is clearly a single statement, but if you write it as...

1 +
3 +
(
  2*4
) +
8 - 
(
  7 / (8*3)
)

It can take on the appearance of a sequence of operations which can be easier for the brain to recognize the desired decomposition the author was intending. I often do this in C# with code like..

people
  .Where(person => person.MiddleName != null)
  .Select(person => person.MiddleName)
  .Distinct();

This is a single statement, but shows the appearance of being decomposed into many - notice there are no assignments.

Also note, in both above methods - the way the code is actually executed is not in the order you immediately read it in; because this code says what to do, but it does not dictate how. Note the simple arithmetic above is obviously not going to be executed in the sequence it's written left to right, and in the C# example above those 3 methods are actually all re-entrant and not executed to completion in sequence, the compiler in fact generates code that will do what that statement wants, but not necessarily how you assume.

I believe getting used to this no-intermediate-steps approach of declarative coding is really the most difficult part of it all; and why Haskell is so tricky because few languages truly disallow it like Haskell does. You have to start doing some interesting gymnastics to accomplish some things that you would typically do with the aid of intermediate variables, such as summation.

In a declarative language, if you want an intermediate variable to do something with - it means passing it as a parameter to a function which does that thing. This is why recursion becomes so important.

sum xs = (head xs) + sum (tail xs)

You can't create a resultSum variable and add to it as you loop through xs, you have to simply take the first value, and add it to whatever the sum is of everything else - and to access everything else you have to pass xs to a function tail because you can't just create a variable for xs and pop the head off which would be an imperative approach. (Yes I know you could use destructuring but this example is meant to be illustrative)

Answer 4

I know I'm late to the party, but I had an epiphany the other day so here it goes...

I think comments about functional, immutable and no side-effects miss the mark when explaining the difference between declarative vs imperative or explaining what declarative programming means. Also, as you mention in your question, the whole "what to do" vs "how to do it" is too vague and really doesn't explain either.

Let's take the simple code a = b + c as a basis and view the statement in a few different languages to get the idea:

When we write a = b + c in an imperative language, like C, we are assigning the current value of b + c to the variable a and nothing more. We aren't making any fundamental statement about what a is. Rather, we are simply executing a step in a process.

When we write a = b + c in a declarative language, like Microsoft Excel, (yes, Excel is a programming language and probably the most declarative of them all,) we are asserting a relationship between a, b and c such that it is always the case that a is the sum of the other two. It's not a step in a process, it's an invariant, a guarantee, a declaration of truth.

Functional languages are declarative as well, but almost by accident. In Haskel for example a = b + c also asserts an invariant relationship, but only because b and c are immutable.

So yes, when objects are immutable and functions are side-effect free, code becomes declarative (even if it looks identical to imperative code,) but they aren't the point. Nor is avoiding assignment. The point of declarative code is to make fundamental statements about relationships.

Answer 5

You are right that there is no clear distinction between telling the computer what to do and how to do it.

However, on one side of the spectrum you almost exclusively think about how to manipulate memory. That is, to solve a problem, you present it to the computer in a form like "set this memory location to x, then set that memory location to y, jump to memory location z ..." and then somehow you end up having the result in some other memory location.

In managed languages like Java, C# and so on, you don't have a direct access to the hardware memory anymore. The imperative programmer is now concerned with static variabes, references or fields of class instances, all of which are to some degree absractions for memory locations.

In langugaes like Haskell, OTOH, memory is completely gone away. It is simply not the case that in

f a b = let y = sum [a..b] in y*y

there must be two memory cells that hold the arguents a and b and another one that holds the intermediate result y. To be sure, a compiler backend could emit final code that works this way (and in some sense it must do so as long as the target architecture is a v. Neumann machine).

But the point is we don't need to internalize the v. Neumann architecture to understand the above function. Nor do we need a contemporary computer to run it. It would be easy to translate programs in a pure FP language to a hypothetical machine that works on the base of the SKI calculus, for instance. Now try the same with a C program!

A pure declarative languages for me would be one which is comprised entirely of declarations only

This is not strong enough, IMHO. Even a C program is just a sequence of declarations. I feel we must qualify the declarations further. For example, are they telling us what something is (declarative) or what it does (imperative).