The difference to me is maybe not as formal, though if I had to pick one I'd pick your definition: declarative is when variables are like mathematical variables

The difference to me is maybe not as formal, though if I had to pick one I'd pick your definition: declarative is when variables are like mathematical variables, and not like turing-machine memory cells. To me the difference is in the level of abstraction. In a non-declarative language, one way to reverse a list is to traverse it, remembering the last item, and change the pointer of the current item to point to the remembered item (if there's no remembered item, the current item is the head of the list, and we make it point to the list terminator). So we have to say exactly how to build the value we're interested in, the reversed list. Whereas in a declarative language, I simply give a definition of what a reversed list is, without saying how to go about doing it. In fact the computer is free to come up with any way it wants to do this, and I can define a reversed list as being the fold of construction over that list. Prelude> foldl (flip (:)) [] [1,2,3,4] [4,3,2,1] Which does not force me, the programmer, to use any mutable memory cells; in other words this operation is loosely defined enough that it could be "run" both destructively and immutably. The fact that the function declaration does not specify the implementation is what I usually mean by "declarative".