There are some very good answers. I will try to contribute to the discussion.
On the topic of declarative, logic programming in Prolog, there is the great book "The Craft of Prolog" by Richard O'Keefe. It is about writing efficient programs using a programming language that lets you write very inefficient programs. In this book, while discussing the efficient implementations of several algorithms (in the chapter "Methods of Programming"), the author takes the following approach:
- define the problem in English
- write a working solution that is as declarative as possible; usually, that means pretty much exactly what you have in your question, just correct Prolog
- from there, take steps to refine the implementation to make it faster
The most enlightening (for me) observation I was able to make while working my way through these:
Yes, the final version of the implementation is much more efficient than the "declarative" specification the author started with. It is still very declarative, succinct, and easy to understand. What has happened in between is that the final solution captures properties of the problem to which the initial solution was oblivious.
In other words, while implementing a solution, we have used as much of our knowledge about the problem as we can. Compare:
Find a permutation of a list such that all elements are in ascending order
Merging two sorted lists will result in a sorted list. Since there might be sublists that are already sorted, use these as a starting point, instead of sublists of length 1.
A small aside: a definition like the one you have given is attractive because it is very general. However, I cannot escape the feeling that it purposefully ignores the fact that permutations are, well, a combinatorial problem. This is something we already know! This is not a criticism, just an observation.
As to the real question: how to move forward? Well, one way is to provide as much knowledge about the problem we are declaring to the computer.
The best attempt I know of to really solve the problem is presented in the books co-authored by Alexander Stepanov, "Elements of Programming" and "From Mathematics to Generic Programming". I am sadly not up to the task of summarizing (or even fully understanding) everything in these books. However, the approach there is to define efficient (or even optimal) library algorithms and data structures, under the provision that all relevant properties of the input are known in advance. The final result is:
- Each well-defined transformation is a a refinement of the constraints that are already in place (the properties that are known);
- We let the computer decide which transformation is optimal based on the existing constraints.
As to why it hasn't quite happened yet, well, computer science is a really young field, and we are still coping with truly appreciating the novelty of most of it.
To give you a taste of what I mean by "refining the implementation": take for example the easy problem of getting the last element of a list, in Prolog. The canonical declarative solution is to say:
last(List, Last) :-
append(_, [Last], List).
Here, the declarative meaning of
List1AndList2 is the concatenation of
Since in the second argument to
append/3 we have a list with only one element, and the first argument is ignored (the underscore), we get a split of the original list which discards the front of the list (
List1 in the context of
append/3) and demands that the back (
List2 in the context of
append/3) is indeed a list with only one element: so, it is the last element.
The actual implementation provided by SWI-Prolog, however, says:
last([X|Xs], Last) :-
last_(Xs, X, Last).
last_(, Last, Last).
last_([X|Xs], _, Last) :-
last_(Xs, X, Last).
This is still nicely declarative. Read top to bottom, it says:
The last element of a list only makes sense for a list of at least one element.
The last element for a pair of the tail and the head of a list, then, is:
the head, when the tail is empty, or the last of the non-empty tail.
The reason why this implementation is provided is to work around the practical issues surrounding the execution model of Prolog. Ideally, it shouldn't make a difference which implementation is used. Similarly, we could have said:
last(List, Last) :-
The last element of a list is the first element of the reversed list.
If you want to get your fill of inconclusive discussions about what is good, declarative Prolog, just go through some of the questions and answers in the Prolog tag on Stack Overflow.