I definitely agree that a sufficiently smart compiler and/or fast interpreter is an extremely important asset when working with Prolog, and also that it takes a

I definitely agree that a sufficiently smart compiler and/or fast interpreter is an extremely important asset when working with Prolog, and also that it takes almost superhuman effort to write such compilers. However, at least in my experience, "nudging" the system in the right direction is much easier with Prolog than with imperative languages: With Prolog, all it takes is often simply reordering a few goals, which some systems even perform automatically for you (see YAP, and some parts of SWI-Prolog for examples, in particular the RDF framework). There is also typically much less code to rewrite in the first place. Critically, the ability to reorder your goals depends on your working in the pure subset of the language. If you leave this subset, then also automatic or manual optimizations are orders of magnitude harder to apply. Regarding Haskell and Prolog, my experience also differs significantly: From my experience and observation, the consequences of lazy evaluation are much harder to understand than Prolog's implicit search mechanism and backtracking.