Is functional programming a type of declarative programming?

Question

I am aware that declarative programming just passes the input and expects the output without stating the procedure how it is done. In functional programming, is a programming paradigm, which takes an input and returns an output. When I checked the Higher order functional programming, we pass a function to map/reduce, which does not reveal the procedure how it is done. So is higher order functional programming and declarative programming the same thing??

Answer 1

Short answer: No.

Wikipedia defines declarative programming as:

In computer science, declarative programming is a programming paradigm - a style of building the structure and elements of computer programs - that expresses the logic of a computation without describing its control flow.

Or to state it a bit boldly: "Say what you want, not how you want it.".

This is thus in contrast with imperative programming languages where a program is seen as a set of instructions that are done one after another. The fact that map, etc. do not reveal the procedure does not make it declarative: one can use a lot of C libraries that are proprietary and do not allow you to inspect the source code. That however, does not mean that these are declarative.

The definition of functional programming on the other hand is:

In computer science, functional programming is a programming paradigm - a style of building the structure and elements of computer programs - that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions or declarations instead of statements.

Based on these definitions one could say that functional programming is a subset of declarative programming. In a practical sense however if we follow the strict definitions, no programming language nowadays is purely, and un-ambigously declarative or functional. One can however say that Haskell is more declarative than Java.

Declarative programming is usually considered to be "safer" since people tend to have trouble managing side-effects. A lot of programming errors are the result of not taking all side effects into account. On the other hand it is hard to

1. design a language that allows a programmer to describe what he wants without going into details on how to do it;
2. implement a compiler that will generate - based on such programs - an efficient implementation; and
3. some problems have inherent side effects. For instance if you work with a database, a network connection or a file system, then reading/writing to a file for instance is supposed to have side effects. One can of course decide not to make this part of the programming language (for instance many constraint programming languages do not allow these type of actions, and are a "sub language" in a larger system).

There have been several attempts to design such language. The most popular are - in my opinion - logic programming, functional programming, and constraint programming. Each has its merits and problems. We can also observe this declarative approach in for instance databases (like SQL) and text/XML processing (with XSLT, XPath, regular expressions,...) where one does not specify how a query is resolved, but simply specifies through for instance the regular expression what one is looking for.

Whether a programming language is however declarative, is a bit of a fuzzy discussion. Although programming languages, modeling languages and libraries like Haskell, Prolog, Gecode,... have definitely made programming more declarative, these are probably not declarative in the most strict sense. In the most strict sense, one should think that regardless how you write the logic, the compiler will always come up with the same result (although it might take a bit longer).

Say for instance we want to check whether a list is empty in Haskell. We can write this like:

is_empty1 :: [a] -> Bool
is_empty1 [] = True
is_empty1 (_:_) = False

We can however write it like this as well:

is_empty2 :: [a] -> Bool
is_empty2 l = length l == 0

Both should give the same result for the same queries. If we however give it an infinite list, is_empty1 (repeat 0) will return False whereas is_empty2 (repeat 0) will loop forever. So that means that we somehow still wrote some "control flow" into the program: we have defined - to some extent - how Haskell should evaluate this. Although lazy programming will result in the fact that a programmer does not really specify what should be evaluated first, there are still specifications how Haskell will evaluate this.

According to some people, this is the difference between programming and specifying. One of my professors once stated that according to him, the difference is that when you program something, you have somehow control about how something is evaluated, whereas when you specify something, you have no control. But again, this is only one of the many definitions.

Answer 2

Not entirely, functional programming emphasises more on what to compute rather than how to compute. However, there are patterns available in functional programming that are pretty much control flow patterns you would commonly associate with declarative programming, take for example the following control flow:

let continue = ref true in
while !continue do
  ...
  if cond then continue := false
  else
     ...
done

Looks familiar huh? Here you can see some declarative constructs but this time round we are in more control.