prolog is actually impure logic language, and given the general lack of HOF i'd be reticent in labelling it functional.

it's a declarative language though, and the model you have 'here is a query, what solutions exist' is reasonably accurate