How Compositional is a Model?

We present a formal definition of a general class of compositional functions, and show how various existing models fit this definition. Given this general definition, we discuss a notion of complexity of these compositional functions, and show how this complexity affects the expressivity and compositional generalization of these functions.