The ability to form complex linguistic units from simpler ones lies at the center of many explanations of the communicative success and robustness of natural language. A closely related ability is that to generalize knowledge about such constructions to novel ones. The present investigation addresses the question what the minimal conditions for the emergence of such productive compositional communication are. Two features are argued to be required for this: relations between elements and classes over their relations. Using signaling games with reinforcement learning we show that a learning bias involving both aspects can lead to the emergence of such generalizable structure.