So we have seen that Prolog is an interesting language that combines
logic and computation. Some programs are very simple and elegant and
execute very reasonably, such as the append program or the
member program. Other programs, such as those derived from
context-free grammars, are very simple and elegant, but sometimes have
undesirable computational properties. For example, some context-free
grammars have recognition times that are exponential in the
length of the input string. This is clearly undesirable, since we
know that there are recognition algorithms that work for all
context-free grammars in at worst cubic time. And even worse, for
some grammars, such as left-recursive grammars, Prolog will go into an
infinite loop, not returning an answer at all. We also saw the same
problem with the Datalog language. Perfectly good specifications
might end up with (very) bad computational behavior. In the next
chapter we will see how Prolog might be modified to deal with some of
these problems.