  We present a non-vacuous definition of compositionality. It is based on the
idea of combining the minimum description length principle with the original
definition of compositionality (that is, that the meaning of the whole is a
function of the meaning of the parts).
  The new definition is intuitive and allows us to distinguish between
compositional and non-compositional semantics, and between idiomatic and
non-idiomatic expressions. It is not ad hoc, since it does not make any
references to non-intrinsic properties of meaning functions (like being a
polynomial). Moreover, it allows us to compare different meaning functions with
respect to how compositional they are. It bridges linguistic and corpus-based,
statistical approaches to natural language understanding.
