One way of looking at the history of programming language design is that there was a revolution with the introduction of the subroutine. Twenty or thirty years later, two refinements of the subroutine call were seriously considered:
I've just been programming in Prolog after a 20 year hiatus and realizing just how incredibly powerful unification and backtracking are. However, polymorphism won. Why?
I have done a LOT of programming in Prolog, and while I love the language for its expressive power, I have to agree with svenningsson that as soon as you try to do anything non-declarative it becomes a puzzle to use the ! operator (cut, discards backtracking options) in the right places, which is extremely error prone.
Though not perfect, one language that elegantly manages to combine backtracking and non-declarative (imperative/side effecting) code is Icon. It basically isolates expressions which can backtrack naturally from the general program structure (e.g. statements) such that it is relatively easy to see that backtracking will not lead to unexpected results, like in Prolog. I am not sure why not more languages are based on this execution model, my guess is that the majority of programmers are really stuck in sequential thinking, and backtracking is confusing.
I am not sure if backtracking compares with polymorphism directly. To me, it is more of an alternative to closures, as the #1 use for closures in most languages is custom iteration (think map/filter/fold etc). For example, in Icon I can say:
every write 10<(1..10)*2
Which takes a sequence of numbers, multiplies them by two, filters out those >10, and prints the result ("every" is bit like a repeat-fail loop in Prolog). In a list/closure based language, I have to write:
for (filter (map [1..10] \x.x*2) \x.x>10) \x.(write x)
granted, this is a bit contived as list comprehensions & currying can simplify this, and not all icon code is that terse, but you get the idea. The Icon version is not only more expressive obviously, but also has the advantage that it does not use intermediate lists and is "lazy" in a co-routine sense, i.e. it will write out the first number before getting to do *2 on the second element. This means it allows you to write code that is equally efficient even if you end up not using all result
Immediately the cut operator came to my mind: Prolog is beautiful and concise just as long as you want and can program declaratively. Once you start using the cut operator (i.e. cut all backtracking at that position), you have to think through too complex situations to find a good solution or understand code from others / your old code.
So the problems with optimizing backtracking seems to be the consensus here, with 3 out of 4 answers (as of 12th of Aug. 2011) stating it (+1 to both Aardappel and svenningsson).