We present a formal language for specifying via constraints a "design space" of DNA constructs composed of genetic parts, and an algorithm for automatically and correctly creating a novel representation of the space of satisfying designs. The language is simple, captures a large class of design spaces, and possesses algorithms for common operations on design spaces. The flexibility of this approach is demonstrated using a 16-gene nitrogen fixation pathway and genetic logic circuits.