Implement separate exists/defined predicates

The old "predicates" is thus reverted to being what it was before: a
defined predicate.

TODO: docs and new tests.