What is declarative programming?

The concept has been bandied about, and has entered into more popular discussion with the broad acceptance of XML. Beside the overall definition, however ("Declarative is the 'what' of programming; imperative, the 'how'"), I haven't heard a definition that sketches, even, what declarative programming is and how it looks like.

For the "quartet of programming styles", being: imperative, object-oriented, functional, and logical, it seems pretty clear that there are well-defined general boundaries (with enough wiggle room to cause fanatics to enjoy flame-wars as the mood struck them) to separate one style from another, with languages easily falling into one or more of those camps:

• C: imperative
• Smalltalk/Java: imperative/object-oriented
• Lisp(and Scheme and Dylan and ...)/Haskell/ML: functional
• Prolog (Mercury): logical

This was all clear-cut and well and good.

But for classifying something as "declarative programming" it seemed that there has been talk of its benefits or drawbacks, but not much more than superficial talk of what it is. Camps from both the functional programming community and the logic programming community stake claims over the declarativeness of their programming languages, but how does one recognize code as declarative? What is the measure by which the "declarativeness" of such code may be ascertained?

Up until recently, I have been troubled by such misgivings only marginally. I had it from authority, a Lisp giant, Patrick Winston, in a Prolog book (Bratko's 3rd ed of "Prolog Programming for Artificial Intelligence"), that the logical style of Prolog is declarative and the functional style is not. Before your send your flame, here's the quote:

"[...] In my view, modern Lisp is the champion of these [imperative] languages, for Lisp in its Common Lisp form is enormously expressive, but how to do something is still what the Lisp programmer is allowed to be expressive about. Prolog, on the other hand, is a language that clearly breaks away from the how-type languges, encouraging the programmer to describe situations and problems, not the detailed means by which the problems are to be solved.

Consequently, an introduction to Prolog is important for all students of Computer Science, for there is no better way to see what the notion of what-type programming is all about. [...]"

I add here that I also view the bulk of Haskell in this light: although it is possible to code declaratively in Haskell, most Haskell code I see is concern with solving the problem (the "how") instead of describing the problem (the "what"). Put another way, it is natural to use the functional and imperative (with monadic do) styles, and it takes effort to use the logic style.

That has been my prejudice until recently, but then recent correspondence with colleagues, including David F. Place, who recently had an excellent article in the Monad.Reader about Monoid, has opened this issue for reexamination. So, I turn to you, gentle reader. I present two very different programs below. One written in the logic style; one, functional. Both solve the same problem, and both authors claim their own version is definitively declarative. I view the world through a particular lense, so I see one perspective. But I am burning with curiosity: do you see A) or B) as declarative, or both, or neither? If so, how do you justify your position?

A) the "logical" program approach:

import Control.Monad.State
import Data.List

splits :: (Eq a) ⇒ [a] → [(a, [a])]
splits list = list >>= λx . return (x, delete x list)

choose :: Eq a ⇒ StateT [a] [] a
choose = StateT $ λs . splits s

sendmory' :: StateT [Int] [ ] [Int]
sendmory' =
     do
       let m = 1
       let o = 0
       s ← choose
       guard (s > 7)
       e ← choose
       d ← choose
       y ← choose
       n ← choose
       r ← choose
       guard (num [s, e, n, d ] + num [m, o, r , e ]
              ≡ num [m, o, n, e, y ])
       return [s, e, n, d , m, o, r , y ]

B) the functional program approach (provided by David F. Place):

solve input accept return
    = solve' [] input [0..9] accept return

solve' bindings [] _ accept return 
          | accept bindings = [return bindings]
          | otherwise = []
solve' bindings ((_,g):xs) digits accept return
          = concatMap f $ g digits
     where f n = solve' (bindings++[n]) xs
                          (delete n digits)
                          accept return

num = foldl ((+) . (*10)) 0

sendMoreMoney =
     solve (('m', const [1]) :
            ('o', const [0]) :
            ('s', filter ( > 7)) :
            (zip "edynr" (repeat id)))
       (λ [m,o,s,e,d,y,n,r] . num [s,e,n,d] 
                                  + num [m,o,r,e]
                                  ≡ num [m,o,n,e,y])
       (λ [m,o,s,e,d,y,n,r] . [s,e,n,d,m,o,r,y])