> I'm pretty sure Prolog not specifying an execution strategy would mean that your program terminates under one interpreter but not under another, not to mention their asymptotic complexity, which I think is not as bad with SQL.
Yup! But it's not as bad as it seems. In a pure logic language, the changing the execution strategy can only change three things:
(0) Whether a query terminates, in which case it returns the entire soution set.
(1) If the query doesn't terminate, which subset of the solution set is returned.
(2) How fast it runs, of course.
Which is a lot better than the subtle things that can go wrong when optimizing imperative programs by hand. Selecting an execution strategy for a declarative program is no different from tuning a garbage collector: if you do it wrong, bad things can still happen, but they won't be as bad as if you manage things by hand and do it wrong.
> it's sort of a lie to promise that you can spell out predicates describing a solution and the machine will find a solution satisfying these predicates, because sometimes it can't.
Yup! Which leads (IMO) to the conclusion that general-purpose languages must always include some imperative (explicit control) component. Declarative languages really shine as DSLs, though.