That's super cool. I'm definitely not an expert on the subject but this paper about dif/2 intrigues me: https://arxiv.org/abs/1607.01590
And perhaps Ciao's paper could offer some hints? http://cliplab.org/papers/hermenegildo11:ciao-design-tplp.pd...
You're probably already aware of it but Scryer Prolog seems like an interesting place to borrow ideas from. Both Scryer and Trealla have efficient string (list of characters) representations.