i'm a long time lisper, but i don't think this is justified.

implementing prolog/backtracking on top of lisp is certainly possible and not even too hard (see e.g. https://github.com/nikodemus/screamer)

and implementing Coq on top of lisp is also possible.

but IMO the "with ease" phrase is not justified in this context.

if you only mean that lisp will not be in the way if you set out to implement these, then i agree. lisp -- the language and the typical opensource implementation -- will be much less of an obstacle than other languages when chosen as foundations.