Isn't this just Prolog?
At the very least, a constraint programming language would be a good basis to start with here.
But Prolog is far from the last word on the subject. For one, it is basically untyped. There are dependently-typed programming languages that can express non-trivial properties via types, which the compiler can check (see ezyang's example).
See also:
http://stackoverflow.com/questions/2829347/a-question-about-...