Precisely define "what to solve" and "how to solve" corollary in functional and imperative programming respectively

Question

I am not sure if I ever clearly understood standard corollary "what to solve" and "how to solve" used to point out difference between functional (declarative) and imperative programming paradigm respectively.

In most of places where this difference is explained is often supplemented with example where some loop control structure is used to imply imperative way of solving problem where recursive method is used to imply declarative way of solving problem. I am not too much hung up on loop control structure vs recursive method.

For example, to me below method of finding length of list (say in Haskell) is just different way of saying "how to solve" problem vs having a for loop in c#/java and increasing counter till the end of list.

Len :: [Int] -> Int
Len [] = 0
Len [x:xs] = 1 + Len(xs)

Isn't above code snippet is just different way of saying "how to solve" problem ? If yes, then I think its more of defining boundary on "how" part between imperative and declarative programming.

Please help on clarifying this with some better example. Thanks !!

Answer 1

Isn't above code snippet is just different way of saying "how to solve" problem ?

Yes. In the end, computer science is invariably about computing so you're always talking about "how to solve" a problem.

But if you read the functional example a certain way:

Len :: [Int] -> Int
Len [] = 0
Len [x:xs] = 1 + Len(xs)

"Length is a function that takes a list of integers and returns an integer."
"Length of an empty list is zero."
"Length of a non-empty list is one plus the length of the 1..n-th elements of the list." 

These are all is statements. They declare what something is. Then look at a (contrived) imperative version:

length(x: [int]): int {
  y = 0;
  foreach(_ in x) {
    y++;
  }
  return y;
}

"Length is a function that takes a list of integers and returns an integer."
"To calculate that, initialize a variable y with the value 0 - 
  then count the entries in your list, adding to y each time -
  then return the value in variable y."

Imperative programming is not declaring what things are, they're recipes about how to do something.

Of course, in the end the computer ends up doing very similar things which is why this sort of distinction isn't very useful when talking about code. Functional versus imperative versus object oriented programming is about how you the programmer think about problems. How do you approach them? How do you describe them? Certain languages make expressing the different models more or less effective, so we talk about "functional languages" and the such as a shortcut for "this language allows programmers that think of things functionally to express themselves well to the computer and other programmers in code".

Answer 2

In functional programming, the "how" is "evaluate this expression" instead of "execute this sequence of steps." As programmers, we can pretty much automatically translate expressions into sequences of steps to evaluate them in our minds, so the distinction isn't always very clear. Also, FP expressions often resemble sequences of statements.

I find that adding multiple layers of lazy evaluation often results in a clearer distinction. Say you have a list of possible locations for config files, each with a list of clusters, each with a list of nodes. You don't want to read any more config files than you have to. You want to connect to the first node you can, and you want to stop trying to connect to any more nodes after you have made a successful connection. You might write it in Scala like this:

val validConfigs = allConfigFiles.filter(_.isValid)
val clusters = validConfigs.flatMap(_.getClusters)
val nodes = clusters.flatMap(_.getNodes)
val sessions = nodes.flatMap(_.getSession)
val validSession = sessions.headOption

If allConfigFiles, getClusters, and getNodes return lazy collections, like a LazyList or an Observable, then the actual evaluation order is very interesting:

• Essentially nothing is done except setting up thunks until the last line.
• The first element of sessions is requested.
• The first element of nodes is requested.
• The first element of clusters is requested.
• The first element of allConfigFiles is requested.
• isValid is called on the first config file.
• If it wasn't valid, the next element of allConfigFiles is requested.
• isValid is called on the next config file.
• If it is valid, then getClusters is called on the config file.
• Assuming at least one cluster is available from that config file, getNodes is called on it, and the first node is requested.
• Assuming at least one node was specified, getSession is called on it.
• If the session wasn't able to be established, the next node is requested from clusters.
• If there are no more nodes in the cluster, the next cluster is requested from validConfigs.
• If there are no more clusters in that config file, the next config file is requested from allConfigFiles.

Writing this same code in an imperative style while trying to get the same on-demand characteristics typically results in a morass of if statements and loop breaks, especially if some of the steps indicate failure via throwing exceptions, or need to do cleanup like closing file handles.

When people say they are specifying "what to solve," they are referring to this idea that the actual evaluation order might not be readily apparent, even though the intended result is often easier to see.

Answer 3

In my opinion syntactic expression (be it imperative or functional) is almost pure coincidence wrt "what" and "how". While I can see some analogy with mathematical equations (an equation to be solved is "what" and solution of the equation is "how"): In common sense people understand it, "what" is nearer the problem and "how" is nearer the solution, the "what" and "how" lies in the relation to the knowledge of the problem domain as well as the possibility to process that knowledge.

The difference is similar to the geographic map. The map itself depicts a network of roads and is the "what". Pathfinder, given two points, can give you "how" you can drive from A to B. That knowledge is already in the map, so for repeated tasks it's more valuable to have a map than specific route descriptions. If one knows how to "read" the map.

It is probably incorrect to ask if your Haskell function is "what" or "how" as it's just a small fragment of the road and can be both a path and a map. To talk about "whats" and "hows" makes sense only having some information system. Then we will clearly see that declarative knowledge (an ontology) plus some generic algorithm (imperative or otherwise) makes the system more valuable because "what" is more generic, and can potentially solve much more problems in the domain.

An alternative is to have almost everything expressed as "how", which most probably is not flexible enough and usually not that valuable.

In other words, expressing knowledge as "what" can make it more useful, but it also assumes the system has a "how" part: Some interpreter, rule engine, logical inferencer, etc, which "understands" how to deal with "what". The win comes at bigger volumes: It is easy to add more "what" as declarations are rarely described in sophisticated programming language, and ideally the interpreter part remains the same.

According to that, the Haskell snippet looks like "how" unless you have a system, which operates on it (NB: not just executes it). It's code-data duality.