LINGUIST List 2.524

Tue 17 Sep 1991

Disc: Compositional Semantics Part 2

Editor for this issue: <>

Directory

1. "Wlodek Zadrozny", Compositional Semantics
2. 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.

Message 2: Re: 2.514 Compositional Semantics

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.edu