Prolog世代の感想としては、昔は普通にLispで実装されていたしなぁ。効率以外で理論的にダメな理由はないんじゃない。

DSLというレイヤーでみたらWhatの実現手段が推論だろうが手続きだろうがそれこそどうでもいいんじゃないかな。
単に望みの記述を書くための手段なんだから、DSLの表現にHowを望むかWhatを望むかは使う人次第だと思う。
私はどちらかといえばHowを隠蔽してWhatを記述するためにDSLを使いますよ。