I think Minikanren does a pretty good job of being an embeddable version of Prolog. It's not that difficult to implement in whatever language you choose and uses the host language's data structures, you just have to implement unification over those days structures (i.e. figure out how to make it a tree). The main things it can't do is function like a database, though even that might be possible if you get creative.
