Computational creativity seeks, in part, to develop autonomous agents that exhibit creativity. Language is an ideal creative domain for studying computer agents due to its rich interconnectedness and immense space of possible combinations. This dissertation explores the design, testing, and theory of creative computer systems that write microfiction and play the board game Codenames. The designs of these systems are all similarly based on building up creative artifacts from the underlying structure of the relationships between words. A critical component of the creative process is the ability to evaluate the quality of creative output. Human and automated assessment of our creative systems' outputs yields insights into the challenge of automated creative evaluation. Those insights are formalized into a novel paradigm for designing creative systems and theoretical analyses of the properties of creative domains that facilitate evaluation.