Computer Science
ComputerScience,1970-2008-Computer Science-2004.jsonl.gz.gz
Computer Science
deda190af435124b183008ecb03fc13eee874e28
Polarity sensitivity and evaluation order in type-logical grammar

We present a novel, type-logical analysis of_polarity sensitivity_: how negative polarity items (like"any"and"ever") or positive ones (like"some") are licensed or prohibited. It takes not just scopal relations but also linear order into account, using the programming-language notions of delimited continuations and evaluation order, respectively. It thus achieves greater empirical coverage than previous proposals.


Introduction
Polarity sensitivity (Ladusaw, 1979) has been a popular linguistic phenomenon to analyze in the categorial (Dowty, 1994), lexical-functional (Fry, 1997(Fry, , 1999, and type-logical (Bernardi, 2002;Bernardi and Moot, 2001) approaches to grammar. The multitude of these analyses is in part due to the more explicit emphasis that these traditions place on the syntax-semantics interface-be it in the form of Montague-style semantic rules, the Curry-Howard isomorphism, or linear logic as glue-and the fact that polarity sensitivity is a phenomenon that spans syntax and semantics.
On one hand, which polarity items are licensed or prohibited in a given linguistic environment depends, by and large, on semantic properties of that environment (Ladusaw, 1979;Krifka, 1995, inter alia). For example, to a first approximation, negative polarity items can occur only in downward-entailing contexts, such as under the scope of a monotonically decreasing quantifier. A quantifier q, of type (e → t) → t where e is the type of individuals and t is the type of truth values, is monotonically decreasing just in case (1) ∀s 1 . ∀s 2 . ∀x. s 2 (x) ⇒ s 1 (x) ⇒ q(s 1 ) ⇒ q(s 2 ). Thus (2a) is acceptable because the scope of nobody is downward-entailing, whereas (2b-c) are unacceptable.
On the other hand, a restriction on surface syntactic form, such as that imposed by polarity sensitivity, is by definition a matter of syntax. Besides, there are syntactic restrictions on the configuration relating the licensor to the licensee. For example, (2a) above is acceptablenobody manages to license anybody-but (3) below is not. As the contrast in (4) further illustrates, the licensor usually needs to precede the licensee.
The syntactic relations allowed between licensor and licensee for polarity sensitivity purposes are similar to those allowed between antecedent and pronoun for variable binding purposes. To take one example, just as an antecedent's ability to bind a (c-commanded) pronoun percolates up to a containing phrase (such as in (5), what Büring (2001) calls "binding out of DP"), a licensor's ability to license a (c-commanded) polarity item percolates up to a containing phrase (such as in (4a)).
(5) [Every boy i 's mother] saw his i father.
Moreover, just as a bindee can precede a binder in a sentence when the bindee sits in a clause that excludes the binder (as in (6); see Williams, 1997, §2.1), a licensee can precede a licensor in a sentence when the licensee sits in a clause that excludes the licensor (as in (7); see Ladusaw, 1979, page 112).
(6) That he i would be arrested for speeding came as a surprise to every i motorist. (7) That anybody would be arrested for speeding came as a surprise to the district attorney.
This paper presents a new, type-logical account of polarity sensitivity that encompasses the semantic properties exemplified in (2) and the syntactic properties exemplified in (3-4). Taking advantage of the Curry-Howard isomorphism, it is the first account of polarity sensitivity in the grammatical frameworks mentioned above to correctly fault (3) for the failure of nobody to appear before Axiom A A For each unary mode α (blank, u, or p in this paper): For each binary mode β (blank or c in this paper): Figure 1: Natural deduction rules for multimodal categorial grammar (Bernardi, 2002, pages 9 and 50). To reduce notation, we do not distinguish structural punctuation from logical connectives. anybody. The analysis makes further correct predictions, as we will see at the end of §3.
The analysis here borrows the concepts of delimited continuations (Felleisen, 1988;Danvy and Filinski, 1990) and evaluation order from the study of programming languages. Thus this paper is about computational linguistics, in the sense of applying insights from computer science to linguistics. The basic idea transfers to other formalisms, but type-logical grammar-more precisely, multimodal categorial grammar-offers a fragment NL R − whose parsing problem is decidable using proof-net technology (Moot, 2002, §9.2), which is of great help while developing and testing the theory.
2 Delimited continuations Figure 1 shows natural deduction rules for multimodal categorial grammar, a member of the type-logical family of grammar formalisms (Moortgat, 1996a;Bernardi, 2002). Figure 2 lists our structural postulates. These two figures form the logic underlying our account.
We use two binary modes: the default mode (blank) for surface syntactic composition, and the continuation mode c. As usual, a formula of the form A • B can be read as "A followed by B". By contrast, a formula of the form A • c B can be read as "A in the context B". In programming-language terms, the formula A • c B plugs a subexpression A into a delimited continuation B. The Root rule creates a trivial continuation: it says that 1 is a right identity for the c mode, where 1 can be thought of as a nullary connective, effectively enabling empty antecedents for the c mode. The binary modes, along with the first three postulates in Figure 2, provide a new way to encode Moortgat's ternary connective q (1996b) for insitu quantification. For intuition, it may help to draw logical formulas as binary trees, distinguishing graphically between the two modes.
To further capture the interaction between scope inversion and polarity sensitivity exemplified in (3-4), we use three unary modes: the value mode (blank), the unquotation mode u, and the polarity mode p. The value mode marks when an expression is devoid of in-situ quantification, or, in programming-language terms, when it is a pure value rather than a computation with control effects. As a special case, any formula can be turned pure by embedding it under a diamond using the T postulate, analogous to quotation or staging in programming languages. Quotations can be concatenated using the K postulate. The unquotation mode u marks when a diamond can be canceled using the Unquote postulate. Unquotation is also known as eval or run in programming languages. The polarity mode p, and the empirical utility of these unary modes, are explained in §3.
A derivation is considered complete if it culminates in a sequent whose antecedent is built using the default binary mode • only, and whose conclusion is a type of the form u A. Below is a derivation of Alice saw Bob.

(8)
Alice np saw (np\ u s)/np Bob np /E saw • Bob np\ u s \E Alice • (saw • Bob) u s Note that clauses take the type u s rather than the usual s, so the Unquote rule can operate on clauses. We abbreviate u s to s • below.
To illustrate in-situ quantification, Figure 3 on the following page shows a derivation of Alice saw a man's mother. For brevity, we treat a man as a single lexical item. It is a quantificational noun phrase whose polarity is neutral in a sense that contrasts with other quantifiers considered below. The crucial part of this derivation is the use of the structural postulates Root, Left, and Right to divide the sentence into two parts: the subexpression a man and its context Alice saw 's mother. The type of a man, s • / c (np\ c s • ), can be read as "a subexpression that produces a clause when placed in a context that can enclose an np to make a clause".

Polarity sensitivity and evaluation order
The p mode mediates polarity sensitivity. For every unary mode α, we can derive A Figure 6: Linear order in polarity licensing: ruling out Anybody saw nobody using left-to-right evaluation order postulates in Figure 2, whenever two quantifiers take inverse rather than linear scope with respect to each other, the transitions must pass through a start state (that is, a clause type that can be Unquoted) in between. This constraint is an empirical advance over previous accounts, which are oblivious to linear order. The input and output polarities of quantifiers are highly mutually constrained. Take everybody for example. If we hold the polarity assignments of the other quantifiers fixed, then the existence of a linear-scope reading for A man introduced everybody to somebody forces everybody to be input-positive and output-neutral. But then our account predicts that Nobody introduced everybody to somebody has a linear-scope reading, unlike the simpler sentence Nobody introduced Alice to somebody. This prediction is borne out, as observed by Kroch (1974, pages 121-122) and discussed by Szabolcsi (2004).