> I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power.

They're not that complex. I'm writing one from scratch right now:

http://github.com/mthom/scryer-prolog

Speaking of constraint solvers, the author of Power of Prolog, Markus Triska, is now in the process of porting his clp(ℤ) constraint solver over to my system, having already ported his boolean constraint solver, clp(B). They are quite complex, but it helps that they're written entirely in Prolog.