The Principle of Compositionality, often attributed to Gottlob Frege, asserts that the meaning of a complex expression is a function of the meanings of its constituent expressions and the syntactic rules used to combine them. This principle is the cornerstone of formal semantics and a key design constraint for computational systems that process natural language meaning. Without compositionality, it would be impossible to explain how speakers understand an unbounded number of novel sentences from a finite vocabulary.
Formal Statement and Implications
⟦E⟧ = G_f(⟦E₁⟧, ..., ⟦Eₙ⟧)
where G_f is the semantic operation associated with f.
Equivalently: the semantic interpretation function ⟦·⟧ is a
homomorphism from the syntactic algebra to the semantic algebra.
Formally, compositionality requires that the semantic interpretation function be a homomorphism from the algebra of syntactic expressions to an algebra of meanings. This means that each syntactic rule f has a corresponding semantic rule G_f, and the meaning of any expression can be computed bottom-up from the meanings of its parts. In Montague Grammar, this homomorphism maps syntactic parse trees to expressions of intensional logic; in CCG-based systems, it maps categorial derivations to lambda terms.
Challenges to Compositionality
Many natural language phenomena appear to challenge strict compositionality. Idioms like "kick the bucket" have non-compositional meanings. Context dependence—including indexicals ("I," "here"), presuppositions, and conversational implicatures—means that meaning depends on more than the expression itself. Coercion phenomena, where the meaning of a word shifts depending on its linguistic context, seem to violate the principle that word meanings are fixed inputs to composition.
The compositionality question is central to modern NLP. Recursive neural networks (Socher et al., 2013) and tree-structured LSTMs compose meanings bottom-up following syntactic structure, implementing a form of neural compositionality. However, Transformer-based models like BERT compute contextual representations through attention over entire sequences, not strictly bottom-up. Whether these models learn compositional representations is an active area of research, with studies showing both compositional generalization successes and systematic failures on novel combinations.
Compositionality in Distributional Semantics
A major challenge in computational linguistics is extending distributional (vector-space) word meanings to phrases and sentences compositionally. Simple approaches like vector addition or component-wise multiplication provide weak compositionality. More principled approaches include the tensor-based framework of Coecke, Sadrzadeh, and Clark, which uses category-theoretic methods to compose vectors guided by syntactic types, and the work of Baroni and Zamparelli on learning composition functions as matrices. These approaches attempt to reconcile the success of distributional word representations with the compositional structure of formal semantics.
The debate over compositionality continues to shape the field. Strict compositionality may be too strong as a universal constraint on natural language, but it remains an essential organizing principle for building systems that can compute meaning systematically. Even approaches that relax strict compositionality—such as construction grammar-inspired models—typically retain some form of compositional combination as a default mechanism.