**Editor for this issue:** <>

- "Wlodek Zadrozny", Compositional Semantics
- BARBARA PARTEE, Re: 2.514 Compositional Semantics

COMPOSITIONAL SEMANTICS ALWAYS EXISTS _____________________________________ CS is usually defined as a functional dependence of the meaning of an expression on the meanings of its parts. One of the first natural questions we might want to ask is whether NL expressions can have CS. That is whether after deciding what (say) sentences and their parts mean, we can find a function that would compose the meaning of a whole from the meanings of its parts. The answer to this question is somewhat disturbing. It turns out that whatever we decide that some language expressions should mean, it is always possible to produce a function that would give CS to it (see below for a more precise for- mulation of this fact). The upshot is that compositionality, as defined above, is not a strong constraint on a semantic theory. The intuitions behind this result can be illustrated quite simply: Consider the language of finite strings of digits from 0 to 7. Let's fix a random function from this language into {0,1}. Let the meaning function be defined as the value of the string as the corresponding number in base 8 if the value of the function is 0, and in base 10, otherwise. Clearly, the meaning of any string is a composition of the meanings of digits (notice that the values of the digits are the same in both bases). But, intuitively, this situation is different from standard cases when we consider only one base and the meaning of a string is given by a simple formula re- ferring only to digits and their positions in the string. The theorem we prove below shows that however complex is the language, and whatever strange meanings we want to assign to its expressions, we can always do it compositionally. One of the more bizarre consequences of this fact is that we do not have to start building compositional semantics for NL beginning with assigning meanings to words. We can equally well start by assigning meanings to LETTERS, and do it in such a way that, for any sentence, the intuitive meaning we associate with it would be a function of the meaning of the letters from which this sentence is composed. PROVING EXISTENCE OF COMPOSITIONAL SEMANTICS ____________________________________________ Let S be any collection of expressions (intuitively, sen- tences and their parts). Let M be a set s.t. for any s member of S, there is m = m(s) which is a member of M s.t. m is the meaning of s. We want to show that there is a compositional semantics for S which agrees with the function associating m with m(s) , which will be denoted by m(x). Since elements of M can be of any type, we do not automat- ically have (for all elements of S) m(s.t) = m(s)#m(t) (where # is some operation on the meanings). To get this kind of homomorphism we have to perform a type raising oper- ation that would map elements of S into functions and then the functions into the required meanings. We begin by trivially extending the language S by adding to it an "end of expression" character $, which may appear only as the last element of any expression. The purpose of it is to encode the function m(x) in the following way: The meaning function mu that provides compositional seman- tics for S maps it into a set of functions in such a way that mu(s.t) = mu(s) ( mu (t)). We want that the original semantics be easily decoded from mu(s), and therefore we require that, for all s, mu(s.$) = m(s) Note that such a type raising operation is quite common both in mathematics (e.g. 1 being a function equal to 1 for all values) and in mathematical linguistics. Secondly, we assume here that there is only one way of composing elements of S -- by concatenation; but all our arguments work for lan- guages with many operators as well. Theorem. There is a function mu s.t, for all s, mu(s.t) = mu(s) ( mu (t)) , and mu(s.$) = m(s). Proof. Let t(0) , t(1) , ... , t(alpha) enumerate S. We can create a big table specifying meaning values for all strings and their combinations. Then the conditions above can be written as mu(t(0)) = { < $ , m(t(0)) > , < mu(t(0)), mu (t(0) . t(0)) >, ... , < mu(t(alpha)), mu(t(0).t(alpha)) > , ... } mu(t(1)) = { < $ , m(t(1)) > , < mu(t(0)), mu (t(1) . t(0)) >, ... , < mu(t(alpha)), mu(t(1).t(alpha)) > , ... } ... mu(t(alpha)) = { < $ , m(t(alpha)) > , < mu(t(0)), mu (t(alpha).t(0)) >, ... , < mu(t(alpha)), mu(t(alpha).t(alpha)) > , ... } ... By the solution lemma (Aczel, "Lectures on Non-wellfounded Sets", 1987; Barwise & Etchemendy, "The Liar", 1987) this set of equations has a solution (unique). We have directly specified the function as a set of pairs with appropriate values. Note that that there is place for recursion in syntactic categories. Also, if certain string does not belong to the language we assume that the value in this table is undefined; thus mu is not necessarily defined for all possible concatenations of strings of S. CAN WE PUT MORE MEANING INTO COMPOSITIONALITY? ______________________________________________ In view of the above theorem, it would be meaningless to keep the definition of compositionality as a homomorphism from syntax to semantics without imposing some conditions on this homomorphism. Here are some remarks: COMPUTABILITY WON'T DO I haven't checked it completely, but it seems to me that if the original function m(x) is computable, so is the solution mu(x). Also, note that in mathematics (where semantics is clearly compositional) we can talk about noncomputable functions. GOING BACK TO INTUITIONS We have some intuitions and a bunch of examples associated with the concept of compositionality. E.g. for NP -> Adj N , we can map nouns and adjectives into sets and concatenation into set intersection, and get an intuitively correct seman- tics for expressions like "red carpet", "blue dog", .... There seem to be two issues here: (1) This works for a lim- ited domain, like: "everyday solids" and colors; so perhaps compositionality should be replaced by a notion of local compositionality. That is, given some classes of expressions (that are specifiable by syntax + semantics + pragmatics) and a syntactic operation on them (e.g. concatenation), we can predict the meaning of a complex expression by mapping the syntactic operation into a semantic one and applying the latter to the meanings of the parts. This kind of approach to semantics is implicit in the paper by Fillmore, Kay and O'Connor "Regularity and idiomaticity in grammatical cons- tructions, Language 64 (3) , 1988, and is explicitly advo- cated in a recent report by A. Manaster Ramer and myself. (2) The function that composes the meanings should be "eas- ily" definable, e.g. in terms of boolean operations on sets. This can be made precise for instance along the lines of a joint paper with A. Manaster Ramer, published in Proc. of Coling '90, where we argue that one can compare expressive power of various grammatical formalisms in terms of re- lations that they allow us to define; the same approach can obviously be applied to semantics. OTHER INTUITIONS (SEMI-SERIOUSLY) Based on the above proof and some observations of the field, I'd like to conjecture that the degree to which a semantic formalism for NL resembles the meaning function given by the solution lemma is inversely proportional to the number of syntactic constructions and proportional to the number of lexical items resembling words of a natural language. In other words, you get a very messy semantics if you limit the number of constructions and increase the vocabulary.Mail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue

I published an article titled "Compositionality" in 1984 in _Varieties of Formal Semantics_, ed. F. Landman and F. Veltman, GRASS 3, Foris, Dordrecht. I included quite a bit of discussion of the fact that there are a great many possible versions of the principle depending on the interpretations of or constraints on key terms like "function of", or "parts" (that's where your theory of syntax goes), and discussed a number of potential obstacles to compositionality, some I think only apparent, some real. Some (particularly some of the Amsterdam formal semanticists) take compositionality as a working hypothesis or methodological principle, others try to pin down specific versions and argue empirically whether they can be correct. By the way the "occasional sailor" problem, which seemed so formidable initially, was elegantly solved by Greg Stump in the late 70's. Theo Janssen's Amsterdam dissertation of 1983 is all about compositionality and includes a nice exposition of the Montagovian strategy of requiring a homomorphism from the syntactic algebra to the semantic algebra, also includes applications of Montague grammar to programming languages, as well as discussion of a number of controversial linguistic constructions. Barbara Partee Linguistics and Philosophy, UMass/Amherst parteecs.umass.eduMail to author|Respond to list|Read more issues|LINGUIST home page|Top of issue