---
abstract: 'In this paper, we will discuss three semantically distinct scope assignment strategies: traditional movement strategy ([@may], [@montague], [@cooper]), polyadic approach ([@may85], [@keenan87], [@keenan92], [@BZ], [@benthem]), and continuation-based approach ([@barker], [@groote], [@barker:shan], [@kiselyov:shan], [@bekki]). As a generalized quantifier on a set $X$ is an element of $\cC(X)$, the value of the continuation monad $\cC$ on $X$, in all three approaches QPs are interpreted as $\cC$-computations. The main goal of this paper is to relate the three strategies to the computational machinery connected to the monad $\cC$ (strength and derived operations). As will be shown, both the polyadic approach and the continuation-based approach make heavy use of monad constructs. In the traditional movement strategy, monad constructs are not used but we still need them to explain how the three strategies are related and what can be expected of them wrt handling scopal ambiguities in simple sentences.'
author:
- Justyna Grudzińska
- Marek Zawadowski
title: 'Scope ambiguities, monads and strengths'
---

Scope ambiguities
=================

Multi-quantifier sentences have been known to be ambiguous with different readings corresponding to how various quantifer phrases (QPs) are semantically related in the sentence. For example,

(1) Every girl likes a boy

admits of the subject wide scope reading ($S > O$) where each girl likes a potentially different boy, and the object wide scope reading ($O > S$) where there is one boy whom all the girls like. As the number of QPs in a sentence increases, the number of distinct readings also increases. Thus a simple sentence with three QPs admits of six possible readings, and in general a simple sentence with $n$ QPs will be (at least) $n!$ ways ambiguous (we only consider readings where QPs are linearly ordered - what we will call asymmetric readings).

In this paper, we will discuss three semantically distinct scope assignment strategies

Strategy A:

:   Traditional movement strategy ([@may], [@montague], [@cooper]).

Strategy B:

:   Polyadic approach ([@may85], [@keenan87], [@keenan92], [@BZ], [@benthem]).

Strategy C:

:   Continuation-based approach ([@barker], [@groote], [@barker:shan], [@kiselyov:shan], [@bekki]).

Scope assignment strategies can be divided into two families: movement analyses (Strategies A and B) and in situ analyses (Strategy C). Strategy A has been implemented in various ways using May’s QR ([@may]), Montague’s Quantifying In Rule ([@montague]), Cooper’s Storage ([@cooper]). Strategy B involving polyadic quantification has been first introduced in the works of May ([@may85]), Keenan ([@keenan87]), Zawadowski ([@BZ]) and van Benthem ([@benthem]). The most recent Strategy C involves continuations and has been first proposed in the works of Barker ([@barker]) and de Groote ([@groote]), and then further developed and modified in the works of Barker and Shan ([@barker:shan]), Kiselyov and Shan ([@kiselyov:shan]) and Bekki and Asai ([@bekki]). The continuation-based strategies can be divided into two groups: those that locate the source of scope-ambiguity in the rules of semantic composition and those that attribute it to the lexical entries for the quantifier words. In this paper, we only consider operation-based approaches (as in [@barker]). As a generalized quantifier on a set $X$ is an element of $\cC(X)$, the value of the continuation monad $\cC$ on $X$, in all three approaches QPs are interpreted as $\cC$-computations. The main goal of this paper is to relate the three scope assignment strategies to the computational machinery connected to the monad $\cC$ (strength and derived operations). As will be shown, Strategies B and C make heavy use of monad constructs. In Strategy A, monad constructs are not used but we still need them to explain how the three strategies are related and what can be expected of them wrt handling scopal ambiguities in simple sentences.

Monads and strenghts
====================

For unexplained notions related to category theory, we refer the reader to standard textbooks on category theory. We shall be exclusively working in the cartesian closed category of sets $Set$. The category $Set$ of sets has sets as objects. A morphism in $Set$ from an object (set) X to an object (set) Y is a function $f: X{\rightarrow}Y$ from $X$ to $Y$.

Monads
------

A [*monad*]{} on $Set$ is a triple $(T,\eta,\mu)$ where $T: Set {\longrightarrow}Set$ is an endofunctor (the underlying functor of the monad), $\eta : 1_{Set} {\longrightarrow}T$ and $\mu: T^2 {\longrightarrow}T$ are natural transformations (first from identity functor on $Set$ to $T$, second from the composition of $T$ with itself to $T$) making the following diagrams

=2600 =600

(,)(,)

(0,0)\[T‘T\^2‘T‘T;\_T‘T()‘1\_T‘‘1\_T \] (500,500)(1,0)\[‘T‘T()\][500]{}[-1]{}a

(1600,0)\[T\^3‘T\^2‘T\^2‘T;\_T‘T()‘‘\]

commute. $\eta$ and $\mu$ are often referred to as [*unit*]{} and [*multiplication*]{} of the monad $T$, respectively. These diagrams express the essence of the algebraic calculations. We shall explain their meaning while describing the list monad below.

Monads can serve many different purposes. Here, we think of a monad as a device to extend the notion of computation. We think of a function $f: X{\longrightarrow}Y$ as a computation that, when given an element of $x$, provides (computes) an element $f(x)$ of $Y$. Then the function $f:X{\longrightarrow}T(Y)$ can be thought of as a computation that, when given an element $x$ in $X$, provides a computation in $T(Y)$ that might, in principle, evaluate to an element of $Y$. We shall illustrate the concept on some examples below, before we focus on the continuation monad - the main notion of computation considered in this paper.

[*Examples of monads.*]{}

1.  [*Identity monad*]{} is the simplest possible monad but not very interesting. In this case the functor $T$ and the natural transformations $\eta$ and $\mu$ are identities. For this monad, the notion of a $T$-computation in $X$ is just an element of $X$, as the function $f: X{\longrightarrow}T(Y)$ is just $f:X{\longrightarrow}Y$.

2.  [*Maybe monad*]{} is the simplest non-trivial monad. The functor $T$ associates to every set $X$ the set $T(X) =X+\{ \bot\}$ (the disjoint sum of $X$ and singleton $\{ \bot\}$), and to every function $f:X{\longrightarrow}Y$ a function $T(f): T(X) {\longrightarrow}T(Y)$ such that, for $x\in T(X)$, $$T(f)(x)  = \left\{ \begin{array}{ll}
            x & \mbox{if $x\in X$}  \\
            \bot & \mbox{if $x=\bot$}
                                        \end{array}
                    \right.$$ So $T$ adds to $X$ an additional element $\bot$, called [*bottom*]{} or [*nothing*]{}. The component at $X$ of natural transformation $\eta$ is a function $\eta_X: X {\longrightarrow}X+\{ \bot\}$ such that $\eta_X(x)=x$, i.e. it sends $x$ to the same $x$ but in the set $X+\{ \bot\}$. The component at $X$ of natural transformation $\mu$ is a function $\mu_X: X+\{ \bot, \bot' \} {\longrightarrow}X+\{ \bot\}$ such that, for $x\in  X+\{ \bot, \bot' \}$, $$\mu_X(x)  = \left\{ \begin{array}{ll}
            x & \mbox{if $x\in X$}  \\
            \bot & \mbox{if $x=\bot$ or $x=\bot'$}
                                        \end{array}
                    \right.$$ i.e. it sends $x$ in $X$ to the same $x$, and two bottoms $\bot$ and $\bot'$ in $T^2(X)$ to the only bottom $\bot$ in $T(X)$.

    For this monad, the notion of a $T$-computation in $X$ consists of elements of $X$ and an additional computation $\bot$ that says that we do not get a value in $X$. The function $f: X{\longrightarrow}T(Y)$ is just a partial function $f:X{{\hookrightarrow}} Y$. So this monad allows to treat partial computations as total.

3.  [*Exception monad*]{} is still less trivial than maybe monad. We are given a fixed set of exceptions $E$ and, for a set $X$, the monad functor is $T(X)=X+E$, i.e. the disjoint union of $X$ and $E$. If $E$ is empty, it is the identity monad; if $E$ is a singleton, then it is a maybe monad; otherwise is it like maybe monad but with many options for nothingness.

4.  [*List monad*]{} or [*monoid monad*]{} is still more interesting than the previous monad and we shall work it out in detail. It is not needed for the applications in the paper but it provides some intuitions before we move to the continuation monad. To any set $X$ the list monad functor associates the set $T(X)$ of (finite) words over $X$ (treated as an alphabet). This includes the empty word $\varepsilon$. To a function $f:X{\longrightarrow}Y$ the functor $T$ associates the function $T(f): T(X) {\longrightarrow}T(Y)$ sending the word $x_1,x_2,\ldots, x_n$ over $X$ to the word $f(x_1),f(x_2),\ldots, f(x_n)$ over $Y$. The component at $X$ of natural transformation $\eta$ is a function $\eta_X: X {\longrightarrow}T(X)$ such that $\eta_X(x)=x$, i.e. it sends (the letter) $x$ to the one letter word $x$ in $T(X)$.

    The component at $X$ of natural transformation $\mu$ is a function $\mu_X: T^2(X) {\longrightarrow}T(X)$. Note that $T^2(X)=T(T(X))$ is the set of words whose letters are words over the alphabet $X$. Thus it can be thought of as a list of lists. $\mu_X$ applied to such a list of lists flattens it to the single list. A three letter word $t=(x_1,x_2),(x_3,x_4,x_5),\varepsilon$ is a typical element of $T^2(X)$. The result of flattening $T$ is the list $\mu_X(T)=x_1,x_2,x_3,x_4,x_5$ in $T(X)$. We can think of such a word $w$ as a term/word/computation $u=y_1,y_2,y_3$ in which we intend to substitute the term $v_1=x_1,x_2$ for variable $y_1$, the term $v_2=x_3,x_4,x_5$ for variable $y_2$, and the term $v_3=\varepsilon$ for variable $y_3$, i.e. $u{[}y_1\backslash v_1,y_2\backslash v_2,y_3\backslash v_3{]}$. Now the multiplication $\mu$ can be thought of as an actual substitution. With this interpretation one can understand the intuitions behind the monad diagrams. In the left triangle, an element of $T(X)$, say $x_1,x_2,x_3$, is mapped through $\eta_{T(X)}$ to single letter word $(x_1,x_2,x_3)$ and $\mu_X$ flattens it back to $x_1,x_2,x_3$, as required for the triangle to commute. In other words, the substitution $y[y\backslash v]$ results in $v$. In the right triangle, the map $T(\eta_x)$ sends, say $x_1,x_2,x_3$, to the letter word $(x_1),(x_2),(x_2)$ with each letter being a single letter word. Thus again flattening such a list gives $x_1,x_2,x_3$ back, as required. In other words the substitution $y_1,y_2,y_3{[}y_1\backslash x_1,y_1\backslash x_2,y_3\backslash x_3{]}$ results in $x_1,x_2,x_3$. Thus the above triangles ensure that if we substitute with either term being a variable, then we get the expected result. The commutation of the square diagram, in this case, expresses the fact if we have a list of lists of lists and we flatten it in two different ways, once starting with the upper two levels of lists and the other time starting with the lower two levels of lists, and then we flatten the results again to get the ordinary lists over $X$ in $T(X)$, these lists coincide. On a more conceptual level, this square expresses the fact that the evaluation commutes with substitution. In this sense these diagrams capture the essence of all algebraic calculations.

    For this monad, the notion of a $T$-computation in $X$ consists of words over $X$ to be evaluated/computed in a monoid when elements of $X$ will be (interpreted) in a monoid. The function $f: X{\longrightarrow}T(Y)$ is just a function $f:X{\longrightarrow}T(Y)$ sending elements of $X$ to words over $Y$. So this monad allows for a list of values, for a given input.

5.  See next subsection for unexplained notation.

    [*(Covariant) power-set monad*]{} sends set $X$ to power-set $\cP(X)$ and a function $f:X{\longrightarrow}Y$ to the image function $\cP(f)=\vec{f}:\cP(X){\longrightarrow}\cP(Y)$ such that, for $h:X{\rightarrow}\bt$, $\vec{f}(h)$ is an image of $U$ under the function $f$, i.e. for $y\in Y$ $$\vec{f}(h)(y) = \bigvee_{x\in X,\; f(x)=y} h(x).$$ The unit $\eta_X: X {\longrightarrow}\cP(X)$ embeds $x$ in $X$ to the characteristic function $x$, i.e. $$\eta_X(x)(x')  = \left\{ \begin{array}{ll}
            \true & \mbox{if $x=x'$}  \\
            \false & \mbox{otherwise.}
                                        \end{array}
                    \right.$$ The multiplication $\mu_X: \cP^2(X){\rightarrow}\cP(X)$ sums elements of elements of elements, i.e. for $H\in \cP^2(X)$ and $x\in X$, $\mu_X(H)(x):X{\rightarrow}\bt$ is a function given by $$\mu_X(H)(x)  = \bigvee_{h\in \cP(X)}\; H(h)\wedge h(x).$$

    This monad also allows for a set of values, for a given input.

Notation
--------

Before we explain the notion of computation coming with the continuation monad, we restate the monad in a more functional way. To do this, we need to introduce some notation. As $Set$ is a cartesian closed category, it is customary to denote functions between sets using $\lambda$ notation. One can think of it as if we were to work in the internal language of $Set$, i.e. $\lambda$ theory where all functions have their names represented. For sets $X$ and $Y$, we shall use $X\times Y$ to denote the binary product of $X$ and $Y$ and $X{\Rightarrow}Y$ to denote the set of functions from $X$ to $Y$. As it is customary, we associate ${\Rightarrow}$ to the right, i.e. $X{\Rightarrow}Y{\Rightarrow}Z$ means $X{\Rightarrow}(Y{\Rightarrow}Z)$ and this set is naturally bijective with $(X\times Y){\Rightarrow}Z$. If we have a function $$f: X\times Y {\longrightarrow}Z,$$ then by $$\lambda y_{:Y}. f : X {\longrightarrow}Y{\Rightarrow}Z$$ we denote its exponential adjunction, i.e. the function from $X$ to the set of functions $Y{\Rightarrow}Z$ such that, for an element $x\in X$, $\lambda y_{:Y}. f(x)$ is a function from $Y$ to $Z$ such that, for an element $y\in Y$, $(\lambda y_{:Y}. f)(x)(y)$ is by definition equal $f(x,y)$. Note that in the expression $(\lambda y_{:Y}. f)(x)(y)$ the first occurrence of $y$ is an occurrence of a variable (as it is part of the name of a function), whereas the second occurrence of $y$ in this expression denotes an element of the set $Y$.

$\pi_i$ will denote the projection on $i$-component from the product. Any function $\sigma: \{1,\ldots m\} {\rightarrow}\{ 1,\ldots, n\}$ induces a generalized projection denoted $$\pi_\sigma =\lk \pi_{\sigma(1)},\ldots, \pi_{\sigma(m)} \rk: X_1\times \ldots\times X_n{\longrightarrow}X_1\times \ldots\times X_m.$$ We will use this notation mainly for $\sigma$’s being bijections, i.e. when $\pi_\sigma$ is just permutation of the component for the product.

We have a distinguished set of truth values $\bt=\{ \true, \false\}$. We shall use the usual (possibly infinitary) operations on this set. For a set $X$, we put $\cP(X)=X{\Rightarrow}\bt$, i.e. the (functional) powerset of $X$.

Continuation monad
------------------

[*Continuation monad*]{}, the most important for us, denoted $\cC$, has some similarities to the power-set monad but it also differs in a substantial way. At the level of objects, it is just twice iterated power-set construction, i.e. for set $X$, $\cC(X)=\cP^2(X)$, but at the level of morphisms, it is an inverse image of an inverse image, i.e., function $f:X{\rightarrow}Y$ induces an inverse image function between powersets $$\cP(f)=f^{-1}: \cP(Y){\rightarrow}\cP(X)$$ $$h\mapsto h\circ f, \hskip 2mm \cP(f)= {\leftarrow}h_{:\cP(Y)}.{\leftarrow}x_{:X}. h(f\, x)$$ Taking again an inverse image function, we have $$\cC(f)=\cP(f^{-1}) : \cC(X) {\rightarrow}\cC(Y)$$ $$Q \mapsto Q\circ f^{-1} , \hskip 2mm \cC(f)(Q)= \lambda h_{:\cP(Y)}.  Q(\lambda x_{:X}. h( f\, x))$$ for $Q\in \cC(X)$.\
The unit $\eta_X : X{\rightarrow}\cC(X)$ is given by $$\eta_X(x)= \lambda h_{:\cP(X)}. h(x).$$ for $x\in X$.\
The multiplication $\mu_X: \cC^{2}(X){\longrightarrow}\cC(X)$ can be explained in terms of $\eta$ $$\mu_X= (\eta_{\cP(X)})^{-1}: \cP^{4}(X){\longrightarrow}\cP^{2}(X).$$ In other words, $\mu_X(\cF):\cP(X){\rightarrow}\bt$ is a function such that $$\mu_X(\cF)(h) = \cF(\eta_{\cP(X)}(h))$$ for $\cF :\cP^{3}(X){\rightarrow}\bt$ and $h: X{\rightarrow}\bt$.\
In $\lambda$-notation, we write $$\mu_X(\cF)(h)=\cF({\leftarrow}D_{: \cC(X)}.D(h)).$$

Now we can look at the notion of computation related the continuation monad. Consider the function $$f : X{\longrightarrow}\cC(Y) .$$ By exponential adjunction (uncurrying) it corresponds to a function $$f' : \cP(Y)\times X{\longrightarrow}\bt$$ and again by exponential adjunction (currying) it corresponds to a function $$f'' : \cP(Y){\longrightarrow}\cP(X).$$ Thus a $\cC$-computation from $X$ to $Y$ is a function that sends functions from $\cP(Y)=Y{\Rightarrow}\bt$ to functions in $\cP(X)$. So instead of having a direct answer for a given element $x\in X$ what is the value $f(x)$ in $Y$, we are given for every continuation function $c: Y{\longrightarrow}\bt$ a value in the answer type $\bt$ that could be thought of as $c(f(x))$ (if there were an element in $Y$ that could be reasonably called $f(x)$). We can draw the picture illustrating the situation

=1200 =300

(,)(,) (0,50)(1,0)\[X‘Y‘f?\][600]{}[1]{}r (600,50)(1,0)\[‘‘c\][600]{}[1]{}r (630,305)[$f(c)$]{} (0,150)[(0,1)[100]{}]{} (0,250)[(1,0)[1200]{}]{}

(1200,250)[(0,-1)[100]{}]{}

Instead of ‘procedure’ $f?$ computing $y$’s from $x$’s (that we don’t have), we provide a continuation $f(c)$ for any continuation (of the computation) $c$. If $f?$ would be indeed a genuine function $f?: X{\longrightarrow}Y$, then $f(c)$ would be the composition $c\circ f?$.

Bi-strong monads
----------------

As the notion of strength is new in this context, we shall briefly recall its history. There are three manifestations of strength on a functor. Historically, the first one was the notion of enrichment of a functor (c.f. [@eilenberg]). The tensorial strength (i.e., natural transformation of a kind $X\otimes T(Y){\longrightarrow}T(X\otimes Y)$ used in this paper) was introduced in [@kock1] and further developed in [@kock4]. The cotensorial strength (i.e., natural transformation of a kind $T(X{\Rightarrow}Y){\rightarrow}X{\Rightarrow}T(Y)$) introduced in [@kock3] also proved useful in some contexts. In symmetric monoidal closed categories these concepts are equivalent, (c.f. [@kock3]).

As it was noticed in [@moggi], a monad, in order to have a well behaved notion of computation, has to be strong. Fortunately, all monads on $Set$ are strong. More precisely, all monads on set can be canonically equipped with two strengths, left and right, and moreover these strengths are compatible in a precise technical sense. This additional structure on the continuation monad will be essential when we shall analyze the meaning of multiple quantified sentences.

Let $(T,\eta,\mu)$ be a monad on $Set$. The [*left strength*]{} is a natural transformation with components $$\stl_{X,Y} : T(X)\times Y {\longrightarrow}T(X\times Y)$$ for sets $X$ and $Y$, making the diagrams

=1100 =600

(,)(,) (0,0)\[T(X)YZ‘T(XYZ)‘T(XY)Z;\_[X,YZ]{}‘\_[X,Y]{}1‘ \_[XY, Z]{}\]

and

=1500 =1100

(,)(,) (0,1000)(0,-1)\[XY‘‘\_X 1\][500]{}[1]{}l

(50,1000)(2,-1)\[‘‘\_[XY]{}\][1000]{}[1]{}r (0,0)\[T(X)Y‘T(XY)‘T\^2(X)Y‘T(T(X)Y);\_[X,Y]{}‘\_X1“\_[T(X),Y]{}\]

(1250,500)(2,-1)\[‘‘\_[XY]{}\][1000]{}[-1]{}r (1200,0)(1,0)\[‘T\^2(XY)‘T(\_[XY]{})\][1200]{}[1]{}b

commute.

The [*right strength*]{} is a natural transformation with components $$\str_{X,Y} : X\times T(Y) {\longrightarrow}T(X\times Y)$$ for sets $X$ and $Y$, making the diagrams

=1100 =600

(,)(,) (0,0)\[XYT(Z)‘T(XYZ)‘XT(YZ);\_[XY,Z]{}‘1\_[Y,Z]{}‘ \_[X,YZ]{}\]

and

=1500 =1100

(,)(,) (0,1000)(0,-1)\[XY‘‘1\_Y\][500]{}[1]{}l

(50,1000)(2,-1)\[‘‘\_[XY]{}\][1000]{}[1]{}r (0,0)\[XT(Y)‘T(XY)‘XT\^2(Y))‘T(XT(Y));\_[X,Y]{}‘1\_Y“\_[X,T(Y)]{}\]

(1250,500)(2,-1)\[‘‘\_[XY]{}\][1000]{}[-1]{}r (1200,0)(1,0)\[‘T\^2(XY)‘T(\_[XY]{})\][1200]{}[1]{}b

commute.

The monad $(T,\eta,\mu)$ on $Set$ together with two natural transformations $\stl$ and $\str$ of right and left strength is a [*bi-strong monad*]{} if, for any sets $X$, $Y$, $Z$, the square

=1200 =600

(,)(,) (00,0)\[XT(Y)Z‘XT((YZ)‘T(XY)Z‘T(XY Z);1\_X\_[Y,Z]{}‘\_[X,Y]{}1\_Z‘\_[X,YZ]{}‘\_[XY, Z]{}\]

commutes.

As we already mentioned, each monad $(T,\eta,\mu)$ on $Set$ is bi-strong. We shall define the right and left strength. Fix sets $X$ and $Y$. For $x\in X$ and $y\in Y$, we have functions $$l_{y} : X{\longrightarrow}X\times Y, \hskip 5mm{\rm and} \hskip 5mm  r_{x} : Y{\longrightarrow}X\times Y,$$ such that $$l_{y}(x) = \lk x,y\rk,  \hskip 5mm{\rm and} \hskip 5mm r_{x}(y) = \lk x,y\rk.$$ The left and right strength $$\stl_{X,Y}: T(X)\times Y {\longrightarrow}T(X\times Y) \hskip 5mm{\rm and} \hskip 5mm \str_{X,Y}: X\times T(Y) {\longrightarrow}T(X\times Y)$$ are given for $x\in X$, $s\in T(X)$, $y\in Y$ and $t\in T(Y)$ by $$\stl_{X,Y}(s,y)= T(l_y)(s)   \hskip 5mm{\rm and} \hskip 5mm  \str_{X,Y}(x,t)= T(r_x)(t),$$ respectively. We drop indices $_{X,Y}$ when it does not lead to confusion.

It is not difficult to verify that the above defines left ($\stl$) and right ($\str$) strength on the monad $T$ and since, for any $x\in X$ and $z\in Z$, the square

=1200 =600

(,)(,) (00,0)\[Y‘XY‘YZ‘XY Z;r\_x‘l\_z‘l\_z‘r\_x\]

commutes, they are compatible and make the monad $T$ bi-strong. Note that these strengths are related by the following diagram

=1200 =600

(,)(,) (00,0)\[T(X)Y ‘T(XY)‘YT(X)‘T(YX);\_[X,Y]{}‘T(\_2,\_1)‘\_2,\_1‘\_[Y,X]{}\]

[*Examples of strength on monads in $Set$.*]{}

1.  Maybe monad. The left strength $\stl_{X,Y} : (X+\{\bot\}) \times Y {\longrightarrow}(X \times Y) +\{\bot\}$ is given by $$\stl(x,y)  = \left\{ \begin{array}{ll}
            \bot & \mbox{if $x=\bot$}  \\
            \lk x,y\rk & \mbox{otherwise.}
                                        \end{array}
                    \right.$$ Right strength is similar.

2.  List monad. The left strength $\stl : T(X) \times Y {\longrightarrow}T(X \times Y)$ is given by $$\stl(\vec{x},y)  = \left\{ \begin{array}{ll}
            \varepsilon & \mbox{if $\vec{x}=\varepsilon$}  \\
            \lk x_1,y\rk, \ldots,\lk x_n,y\rk  & \mbox{if $\vec{x}=x_1,\ldots, x_n$.}
                                        \end{array}
                    \right.$$ Right strength is similar.

3.  Continuation monad. We shall describe the strength morphisms by lambda terms. The left strength is $$\stl={\leftarrow}N_{:\cC(X)}.{\leftarrow}y_{:Y}.  {\leftarrow}c_{:\cP(X\times Y)}. N({\leftarrow}x_{:X}. c(x,y)): \cC(X)\times Y {\longrightarrow}\cC(X\times Y)$$ and the right strength is $$\str={\leftarrow}x_{:X}. {\leftarrow}M_{:\cC(Y)}. {\leftarrow}c_{: \cP(X\times Y)}. M(\lambda y_{:Y}.c(x,y)): X\times \cC(Y) {\longrightarrow}\cC(X\times Y).$$

Combining computations in arbitrary monad $T$ on $Set$
------------------------------------------------------

Using both strengths, we can define two [*pile up*]{} natural transformations, the left and right. For any sets $X$ and $Y$, the [*left pile up*]{} $\pul_{X,Y}$ is defined from the diagram

=1200 =600

(,)(,) (00,0)\[T(X)T(Y)‘T(XY)‘T(XT(Y))‘T\^2(XY);\_[X,Y]{}‘\_[X,T(Y)]{}‘\_[XY]{}‘T(\_[X,Y]{})\]

In the above diagram, the function ${\pul}_{X,Y}$ is defined as a composition of three operations: the first is taking the $T$-computation on $X$ ‘outside’ to be a computation on $X\times T(Y)$, the second is taking the $T$-computation on $Y$ ‘outside’ to be a $T$-computation on $X\times Y$. In this way, we have $T$-computations coming from $X$ on $T$-computations coming from $Y$ on $X\times Y$. Now the last morphism $\mu_{X\times Y}$ flattens these two levels to one, i.e. the $T$-computation on $T$-computations to $T$-computations.

The [*right pile up*]{} ${\pur}_{X,Y}$ is defined from the diagram

=1200 =600

(,)(,) (00,0)\[T(X)T(Y)‘T(XY)‘T(T(X)Y)‘T\^2(XY);\_[X,Y]{}‘\_[T(X),Y]{}‘\_[XY]{}‘T(\_[X,Y]{})\]

This operation takes out the $T$-computations in a reverse order and so they pile up in the other way.

If these [*pile up*]{} operations agree for all sets $X$ and $Y$, the monad is called [*commutative*]{}. On our list of monads, identity, maybe and covariant power-set monads are commutative. The exception, list and continuation monads are not commutative. Most monads, including the continuation monad $\cC$, are not commutative. It should be noticed that even if the monad $T$ is not commutative, both lift morphisms agree on pairs in which at least one component comes from the actual value (not an arbitrary $T$-computation). In other words, the functions

=1400 =400

(,)(,) (0,200)(1,0)\[‘‘\_[X\_1,X\_2]{}\][1400]{}[1]{}a (0,150)(1,0)\[T(X\_1)T(X\_2)‘T(X\_1X\_2)‘\][1400]{}[0]{}a (0,100)(1,0)\[‘‘\_[X\_1,X\_2]{}\][1400]{}[1]{}b

are equalized by both

=1200 =100

(,)(,) (0,00)(1,0)\[X\_1T(X\_2)‘T(X\_1)T(X\_2)‘\_[X\_1]{}1\][1200]{}[1]{}a

and

=1200 =100

(,)(,) (0,00)(1,0)\[T(X\_1)X\_2‘T(X\_1)T(X\_2)‘1\_[X\_2]{}\][1200]{}[1]{}a

morphisms. Both $\pul$ and $\pur$ are associative. All this is shown in the Appendix.

[*Examples of $\pu$-operations.*]{}

1.  Maybe monad. The left and right pile’up’s coincide in this case, as in any commutative monad. We have $\pul_{X,Y}=\pur_{X,Y} : (X+\{\bot\}) \times (Y+\{\bot'\}) {\longrightarrow}(X \times Y) +\{\bot\}$ is given by $$\stl(x,y)  = \left\{ \begin{array}{ll}
            \bot & \mbox{if $\{x,y\} \cap \{\bot,\bot'\}\neq\emptyset$}  \\
            \lk x,y\rk & \mbox{otherwise.}
                                        \end{array}
                    \right.$$

2.  List monad. The left pile’up $\pul : T(X) \times T(Y) {\longrightarrow}T(X \times Y)$ is given by $$\pul(\lk x_1,\ldots, x_n\rk, \lk y_1,\ldots, y_m\rk)  =$$ $$= \lk \lk x_1,y_1\rk,\lk x_1,y_2\rk,\ldots,\lk x_1,y_m\rk,\lk x_2,y_1\rk, \ldots,  \lk x_n,y_{m-1}\rk,\lk x_n,y_m\rk$$ and the right pile’up $\pur : T(X) \times T(Y) {\longrightarrow}T(X \times Y)$ is given by $$\pur(\lk x_1,\ldots, x_n\rk, \lk y_1,\ldots, y_m\rk)  =$$ $$= \lk \lk x_1,y_1\rk,\lk x_2,y_1\rk,\ldots,\lk x_n,y_1\rk,\lk x_1,y_2\rk, \ldots,  \lk x_{n-1},y_m\rk,\lk x_n,y_m\rk.$$

3.  [*(Covariant) power-set monad*]{}. The left and right pile’up’s coincide in this case. We have $\pul_{X,Y}=\pur_{X,Y} : \cP(X) \times \cP(Y) {\longrightarrow}\cP(X \times Y)$ given by $$\stl(U,V)  = U\times V$$ for $U\in \cP(X)$ and $V\in \cP(Y)$.\

4.  Continuation monad. Both pile’up operations $$\pul,\pur: \cC(X)\times \cC(Y) {\longrightarrow}\cC(X\times Y)$$ can be defined, for $M\in \cC(X)$ and $N\in \cC(Y)$, by lambda terms as $$\pul(M,N)={\leftarrow}c_{:\cP(X\times Y)}. M({\leftarrow}x_{:X}. N({\leftarrow}y_{:Y} c(x,y))$$ and $$\pur(M,N)= {\leftarrow}c_{:\cP(X\times Y)}. N({\leftarrow}y_{:Y}. M({\leftarrow}x_{:X} c(x,y)).$$ The calculations for these operations are in the Appendix.

    Thus in the case of the continuation monad ‘piling up’ computations one on top of the other is nothing but putting (interpretations of) quantifiers (= computations in the continuation monad) in order, either first before the second or the second before the first.

$T$-transforms on arbitrary monad $T$ on $Set$
----------------------------------------------

There are two (binary) $T$-transformations, right and and left. For a function $f: X\times Y {\longrightarrow}T(Z)$, the left $T$-transform is defined as the composition

=1200 =600

(,)(,) (00,0)\[T(X)T(Y)‘T(Z)‘T(XY)‘T\^2(Z);[\^[,T]{}]{}\_[X,Y]{}(f)‘‘\_[Z]{}‘T(f)\]

and the right $T$-transform is defined as the composition

=1200 =600

(,)(,) (00,0)\[T(X)T(Y)‘T(Z)‘T(XY)‘T\^2(Z);[\^[,T]{}]{}\_[X,Y]{}(f)‘‘\_[Z]{}‘T(f)\]

The most popular $\cps$-transforms are for the evaluation morphism $ ev : X \times (X {\Rightarrow}Y) \rightarrow Y$ but there are also other morphisms having useful transforms.

[*Examples of $T$-transforms and in particular $\cps$-transforms.*]{}

1.  The evaluation map $ev : X \times (X {\Rightarrow}Y) \rightarrow Y$ gives rise to application transforms $${\trl}^{,T}(ev), {\trr}^{,T}(ev) :  T(X) \times T(X {\Rightarrow}Y) \rightarrow T(Y).$$ In case $T$ is the continuation monad $\cC$, they are the usual $\cps$-transforms $\cpsl(ev), \cpsr(ev) :  \cC(X) \times \cC(X{\Rightarrow}Y) \rightarrow \cC(Y)$ given by $$\cpsl(ev)(M,N)={\leftarrow}h_{:\cP(Y)}. M({\leftarrow}x_{:X}. N({\leftarrow}g_{:X{\Rightarrow}Y}. h(g\, x)))$$ for $M\in \cC(X)$ and $N\in \cC(X{\Rightarrow}Y)$.\
    Right version is similar.

2.  Various epsilon maps are typically defined as maps from a product. Thus they give rise to various $T$-transforms. We list some of them below mainly to introduce notation that will be used later. The definitions are given by lambda terms.

    1.  Left evaluation $$\epsl_X= {\leftarrow}h_{:\cP(X)}.{\leftarrow}x_{:X}. h(x)  : \cP(X) \times X \rightarrow \bt;$$

    2.  Right evaluation $$\epsr_X= {\leftarrow}x_{:X}.{\leftarrow}h_{:\cP(X)}. h(x)  : X \times \cP(X) \rightarrow \bt;$$

    3.  Left partial evaluation $$\epsl^{,X}_Y=\epsl_Y= {\leftarrow}c_{:\cP(X\times Y)}.{\leftarrow}y_{:Y}. {\leftarrow}x_{:X}. c(x,y)  : \cP(X\times Y)\times Y \rightarrow \cP(X);$$

    4.  Right partial evaluation $$\epsr^{,X}_Y=\epsr_Y={\leftarrow}y_{:Y}. {\leftarrow}c_{:\cP(X\times Y)}. {\leftarrow}x_{:X}. c(x,y)  : Y\times \cP(X\times Y) \rightarrow \cP(X);$$

3.  What we call Mostowski maps are maps similar to $\eps$’es that are the algebraic counterpart of the interpretation of generalized quantifiers of Mostowski. Again, we give a definition for total and partial case.

    1.  Left Mostowski $$\mosl_X ={\leftarrow}Q_{:\cC(X)}.{\leftarrow}c_{:\cP(X)}. Q(c): \cC(X)\times \cP(X) \rightarrow \bt;$$

    2.  Right Mostowski $$\mosr_X ={\leftarrow}c_{:\cP(X)}. {\leftarrow}Q_{:\cC(X)}. Q(c) :\cP(X) \times \cC(X) \rightarrow \bt;$$

    3.  Left partial Mostowski $$\mosl_Y ={\leftarrow}Q_{:\cC(Y)}.{\leftarrow}c_{:\cP(X\times Y)}. {\leftarrow}x_{:X}. Q( {\leftarrow}y_{:Y}. c(x,y)) : \cC(Y)\times \cP(X\times Y) \rightarrow \cP(X);$$

    4.  Right partial Mostowski $$\mosr_Y ={\leftarrow}c_{:\cP(X\times Y)}. {\leftarrow}Q_{:\cC(Y)}. {\leftarrow}x_{:X}. Q( {\leftarrow}y_{:Y}. c(x,y)) :\cP(X\times Y) \times \cC(Y) \rightarrow \cP(X).$$

Scope assignment strategies
===========================

Using the notions connected to the continuation monad introduced above, we shall now precisely state and compare three strategies (A, B, C) for determining the meaning of multi-quantifier sentences.

General remarks
---------------

In each strategy, the starting point is the Surface Structure Tree of a sentence. This tree is rewritten so as to obtain Formal Structure Trees that correspond to all and only the available meanings of the sentence. Finally, we relabel those trees to obtain Computation Trees[^1] that provide the semantics for the sentence in each of its reading.

=3150 =500

(,)(,) (40,290)[Surface]{} (20,180)[Structure]{} (100,70)[Tree]{} (0,50)[(450,360)[ ]{}]{}

(650,400)[rewriting]{} (480,290)[(disambiguation)]{} (450,250)[(1,0)[800]{}]{}

(1290,290)[Formal]{} (1270,180)[Structure]{} (1350,70)[Tree]{} (1250,50)[(450,360)[ ]{}]{}

(1850,400)[relabelling]{} (1750,290)[(interpretation)]{} (1700,250)[(1,0)[750]{}]{}

(2490,290)[Computation]{} (2500,180)[(Semantic)]{} (2620,70)[Tree]{} (2450,50)[(650,360)[ ]{}]{}

**Rewriting**. Scope assignment strategies can be divided into two families: movement analyses (rewriting rules include QR, Predicate Collapsing and possibly Rotation) and in situ analyses (no rewriting rules). Below we define three rewrite rules on trees: QR Rule, Predicate Collapsing and Rotation.

-   QR (Quantier Raising) Rule

    -   applies when we have a chosen QP in a leaf of a tree;

    -   adjoins QP to S;

    -   indexes S with the variable bound by the raised QP.

        $\mapsto$

        ($L$ - label, $\alpha, \beta$ - subtrees.)

-   Predicate Collapsing

    -   applies when all the leaves under the node labeled S are labeled with variables (not QP’s);

    -   collapses the whole subtree with the root S to a single leaf labeled with the variables $x_1, x_2, x_3$ from the leaves under S-node.

    $\mapsto$

-   Rotation

    -   applies to a tree with two distinguished nodes labeled with $S$’es superscriped with some variables: the mother labeled S$^{\vec{x}}$ and its right daughter labeled S$^{\vec{y}}$;

    -   it rotates left the subtree with root labeled S$^{\vec{x}}$;

    -   the root of this subtree is labeled S$^{\vec{x}\vec{y}}$ and the (new) leftt daughter is labeled $Polyadic$.

        $\mapsto$

        ($\alpha, \beta, \gamma$ - subtrees.)

**Relabelling**. In each scope assignment strategy, the leaves in the Computation Tree have the same labels: QPs are interpreted as $\cC$-computations, and predicates are interpreted as usual or lifted. The main difference among the three approaches consists in the shape of the Formal Structure Trees and the operations ($\eps$’es, $\mos$’es, $\pu$’es, $\cps$’es) used as labels of the inner nodes of the Computation Trees.

Strategy A
----------

In the traditional movement strategy (as variously implemented in [@may], [@montague])

-   Surface Structure Tree gets rewritten (disambiguated) as Formal Structure Trees (Logical Forms) via

    -   QR Rule;

    -   Predicate Collapsing.

-   Formal Structure Trees (LFs) are relabelled as Computation Trees as follows

    -   S$^x$ (root of a subtree representing a formula) is interpreted as a suitably typed $\mos$-operation (the only operation allowed);

    -   S (leaf of a tree) is interpreted as a predicate;

    -   QP (leaf of a tree) is interpreted as a generalized quantifier $\|Q\|$ quantifying over a set $X$ (i.e. as a $\cC$-computation on $X$).

We will illustrate each strategy on the examples involving one, two and three QPs.

**Sentence with one QP**, e.g. *Every kid (most kids) entered.*

(A1) Surface Structure Tree

(A1) Formal Structure Tree (LF) and the corresponding Computation Tree

The Computation Tree in (A1) gives rise to the following general map

=600 =600

(,)(,) (-500,300)[$\strat^1_A:$]{} (300,500)(0,-1)\[(X)(X)‘2‘\_[X]{}\][500]{}[1]{}r

In this case, there is one such map - thus Strategy A yields one reading for a sentence with one QP.

**Sentence with two QPs**, e.g. *Every girl likes a boy.*

(A2) Surface Structure Tree

(A2) Formal Structure Tree (LF) and the corresponding Computation Tree

The Computation Tree in (A2) gives rise to the following general map, with $\sigma\in S_2$ (where $S_2$ is the set of permutations of the set $\{1, 2\}$)

=1000 =1900

(,)(,) (-1000,1500)[$\strat^{2,\sigma}_A:$]{} (500,1800)(0,-1)\[(X\_1)(X\_1X\_2)(X\_2)‘‘|\_[(1)]{},|\_[(2)]{},\_2\][600]{}[1]{}r

(500,1800)(1,0)\[‘(X\_[(i)]{})‘|\_[(i)]{} \][1400]{}[1]{}a

(500,1200)(0,-1)\[(X\_[(1)]{})(X\_[(2)]{})(X\_1X\_2)‘‘1\_[X\_[(2)]{}]{}\][600]{}[1]{}r (500,600)(0,-1)\[(X\_[(1)]{})(X\_[(1)]{})‘2‘\_[X\_[(1)]{}]{}\][600]{}[1]{}r

where $\bar{\pi}_{\sigma(i)}$ is the projection on the 1st factor if $\sigma(i)=1$ and on the 3rd factor if $\sigma(i)=2$, i.e. as it should be. This convention will be used in all similar diagrams without any further explanations.\
There are two such maps corresponding to the two permutations $\sigma$ of $\{ 1,2\}$. These maps are different in general. Thus Strategy A yields two (both) asymmetric readings for a sentence with two QPs.

**Sentence with three QPs**, e.g. *Some teacher gave every student most books.*

(A3) Surface Structure Tree

(A3) Formal Structure Tree (LF)

and the corresponding Computation Tree

The Computation Tree in (A3) gives rise to the following general map, with $\sigma\in S_3$ (where $S_3$ is the set of permutations of the set $\{1, 2, 3\}$)

=1000 =2500

(,)(,) (-1000,2100)[$\strat^{3,\sigma}_A:$]{} (500,2400)(0,-1)\[(X\_1)(X\_1X\_2X\_3)(X\_2)(X\_3)‘ ‘|\_[(1)]{},|\_[(2)]{}, |\_[(3)]{}, \_2 \][600]{}[1]{}r

(500,1800)(0,-1)\[(X\_[(1)]{})(X\_[(2)]{})(X\_[(3)]{})(X\_1X\_2X\_3)‘ ‘11 \_[X\_[(3)]{}]{}\][600]{}[1]{}r

(500,1200)(0,-1)\[(X\_[(1)]{})(X\_[(2)]{})(……)‘‘1\_[X\_[(2)]{}]{}\][600]{}[1]{}r

(500,600)(0,-1)\[(X\_[(1)]{})(X\_[(1)]{})‘2‘\_[X\_[(1)]{}]{}\][600]{}[1]{}r

There are six such maps corresponding to six permutations $\sigma$ of $\{ 1,2,3\}$. These maps are different in general. Thus Strategy A yields 6 asymmetric readings for a sentence with three QPs.

Strategy B
----------

In the polyadic approach (as developed in [@may85], [@keenan87], [@keenan92], [@BZ], [@benthem])

-   Surface Structure Tree gets rewritten (disambiguated) as Formal Structure Trees (Polyadic Logical Forms) via

    -   QR Rule;

    -   Predicate Collapsing;

    -   Rotation.

-   Formal Structure Trees (PLFs) are relabelled as Computation Trees as follows

    -   $Polyadic$ (root of a subtree representing a polyadic quantifier) is interpreted as a suitably typed $\pu$-operation (we can choose globally whether we use only $\pul$ or $\pur$ and then consequently stick to it).

    -   S$^x$, S, QP are interpreted as above.

**Sentence with one QP**, e.g. *Every kid (most kids) entered.*

(B1) Surface Structure Tree

(B1) Formal Structure Tree (PLF) and the corresponding Computation Tree

The Computation Tree in (B1) gives rise to the following general map

=600 =600

(,)(,) (-500,300)[$\strat^1_B:$]{} (300,500)(0,-1)\[(X)(X)‘2‘\_X\][500]{}[1]{}r

In this case, there is one such map - thus Strategy B yields one reading for a sentence with one QP.

**Sentence with two QPs**, e.g. *Every girl likes a boy.*

(B2) Surface Structure Tree

(B2) Formal Structure Tree (PLF) obtained from LF in (A2) via rotation

$\mapsto$

and the corresponding Computation Tree

The Computation Tree in (B2) gives rise to the following general map, with $\sigma\in S_2$

=1000 =2500

(,)(,) (-1000,2100)[$\strat^{2,\sigma}_B:$]{} (500,2400)(0,-1)\[(X\_1)(X\_1X\_2)(X\_2)‘‘|\_[(1)]{},|\_[(2)]{},\_2\][600]{}[1]{}r

(500,1800)(0,-1)\[(X\_[(1)]{})(X\_[(2)]{})(X\_[1]{}X\_[2]{})‘‘1 \][600]{}[1]{}r

(500,1200)(0,-1)\[(X\_[(1)]{}X\_[(2)]{})(X\_[1]{}X\_[2]{})‘‘(\_[\^[-1]{}]{})1 \][600]{}[1]{}r (500,600)(0,-1)\[(X\_1X\_2)(X\_1X\_2)‘2‘\_[X\_[1]{}X\_2]{}\][600]{}[1]{}r

There are two such maps corresponding to the two permutations $\sigma$ of $\{ 1,2\}$ combined with $\pul$-operation (in that case, alternatively, we can use $\pul$ and $\pur$). These maps are different in general. Thus Strategy B yields two (both) asymmetric readings for a sentence with two QPs.

**Sentence with three QPs**, e.g. *Some teacher gave every student most books.*

(B3) Surface Structure Tree

(B3) Formal Structure Tree (PLF) obtained from LF in (A3) via rotation

$\mapsto$

$\mapsto$

and the corresponding Computation Tree

The Computation Tree in (B3) gives rise to the following general map, with $\sigma\in S_3$

=1000 =3100

(,)(,) (-1000,2700)[$\strat^{3,\sigma}_B:$]{}

(500,3000)(0,-1)\[(X\_1)(X\_1X\_2X\_3)(X\_2)(X\_3)‘ ‘|\_[(1)]{},|\_[(2)]{},|\_[(3)]{},\_2\][600]{}[1]{}r

(500,2400)(0,-1)\[(X\_[(1)]{})(X\_[(2)]{})(X\_[(3)]{})(X\_[1]{}X\_[2]{}X\_[3]{})‘‘1 1\][600]{}[1]{}r

(500,1800)(0,-1)\[(X\_[(1)]{})(X\_[(2)]{}X\_[(3)]{})(X\_1X\_2X\_3)‘‘ 1\][600]{}[1]{}r

(500,1200)(0,-1)\[(X\_[(1)]{}X\_[(2)]{}X\_[(3)]{})(X\_1X\_2X\_3)‘‘(\_[\^[-1]{}]{})1\][600]{}[1]{}r

(500,600)(0,-1)\[(X\_1X\_2X\_3)(X\_1X\_2X\_3)‘2‘\_[X\_[1]{}X\_2X\_3]{}\][600]{}[1]{}r

There are six such maps corresponding to six permutations $\sigma$ of $\{ 1,2,3\}$ combined with $\pul$-operation (in that case we can choose globally whether we use only $\pul$ or $\pur$ and then consequently stick to it). These maps are different in general. Thus Strategy B yields 6 asymmetric readings for a sentence with three QPs.

Strategy C
----------

In the continuation-based strategy approach (as proposed in [@barker])

-   Surface Structure Tree gets rewritten as Formal Structure Tree via

    -   no rewriting rules (Formal Structure Trees are just Surface Structure Trees - this is what is understood by in situ).

-   Relabelling Formal Structure Trees (= Surface Structure Trees) as the Computation Trees is as follows

    -   S, VP, V’ (roots of a (sub)tree with some (possibly all) arguments provided) are interpreted as suitably typed $\cps$-operations (left and right);

    -   V, Vt, Vdt (leafs of a tree) are interpreted as ‘continuized’ (1-, 2-, 3-$ary$, respectively) predicates.

**Sentence with one QP**, e.g. *Every kid (most kids) entered.*

(C1) Surface Structure Tree and the corresponding Computation Tree

The Computation Tree in (C1) gives rise to the following general map

=600 =1100

(,)(,) (-500,700)[$\strat^1_c:$]{} (300,1000)(0,-1)\[(X)(X)‘‘1\_[(X)]{}\][500]{}[1]{}r (300,500)(0,-1)\[(X)(X)‘(2)‘\^?(\_[X]{})\][500]{}[1]{}r

(300,0)(1,0)\[‘2‘ev\_[id\_2]{}\][600]{}[1]{}r

We use $\cps^?$ when it does not matter whether we apply $\cpsl$ or $\cpsr$. This is the case when one of the arguments is a lifted element (like interpretations of predicates in this strategy). Strategy C yields one reading for a sentence with one QPs.

**Sentence with two QPs**, e.g. *Every girl likes a boy.*

(C2) Surface Structure Tree and the corresponding Computation Tree

The Computation Tree in (C2) gives rise to the following general map

=1000 =1900

(,)(,) (-1000,1500)[$\strat^{2,\varepsilon}_C:$]{} (500,1800)(0,-1)\[(X\_1)(X\_1X\_2)(X\_2)‘‘1\_[(X\_1X\_2)]{}1\][600]{}[1]{}r (500,1200)(0,-1)\[(X\_1)(X\_1X\_2)(X\_2)‘‘1\^?(\_[X\_2]{})\][600]{}[1]{}r (500,600)(0,-1)\[(X\_1)(X\_1)‘(2)‘\^(\_[X\_1]{})\][600]{}[1]{}r

(500,0)(1,0)\[‘2‘ev\_[id\_2]{}\][600]{}[1]{}r

with $\varepsilon\in \{l,r\}$. Depending on whether we use $\cpsl$ or $\cpsr$, we get either one or the other of the two asymmetric readings for a sentence with two QPs. Strategy C yields two readings for a sentence with two QPs corresponding to the two $\cps$’es.

**Sentence with three QPs**, e.g. *Some teacher gave every student most books.*

(C3) Surface Structure Tree and the corresponding Computation Tree

The Computation Tree in (C3) gives rise to the following general map

=1000 =2500

(,)(,) (-1000,2100)[$\strat^{3,\varepsilon',\varepsilon}_C:$]{} (500,2400)(0,-1)\[(X\_1)(X\_1X\_2X\_3)(X\_2)(X\_3)‘ ‘1\_[(X\_1X\_2X\_3)]{}11\][600]{}[1]{}r

(500,1800)(0,-1)\[(X\_1)(X\_1X\_2X\_3)(X\_2)(X\_3)‘‘1\^?(\_[X\_2]{})1\][600]{}[1]{}r

(500,1200)(0,-1)\[(X\_1)(X\_1X\_3)(X\_3)‘‘1\^[’]{}(\_[X\_3]{})\][600]{}[1]{}r

(500,600)(0,-1)\[(X\_1)(X\_1)‘(2)‘\^(\_[X\_1]{})\][600]{}[1]{}r (500,0)(1,0)\[‘2‘ev\_[id\_2]{}\][600]{}[1]{}r

Strategy C provides four asymmetric readings for the sentence such that QP in subject position can be placed either first or last only (corresponding to the four possible combinations of the two $\cps$’es). Thus it yields four out of six readings accounted for by strategies A and B.

The tables below summarize the main features of the three approaches.\
**Passing from Surface Structure Tree Trees to Formal Structure Trees**

$$\begin{array}{|c|c|c|c|} \hline

   \textit{\textbf{Strategy}} & \textit{\textbf{A}} & \textit{\textbf{B}}  & \textit{\textbf{C}} \\ \hline
  \textit{} & \textit{}  & \textit{} & \textit{} \\

  \textit{Rewrite} & \textit{QR,}  & \textit{QR,} & \textit{No rewrite rules} \\
  \textit{rules}&  \textit{Predicate} & \textit{Predicate} & \textit{(in situ)} \\
  \textit{} & \textit{Collapsing}  & \textit{Collapsing,} & \textit{} \\
  \textit{} & \textit{}  & \textit{Rotation} & \textit{} \\ \hline
 \end{array}$$ **Passing from Formal Structure Trees to Computation Trees** $$\begin{array}{|c|c|c|c|} \hline
 \textit{\textbf{Strategy}} & \textit{\textbf{A}} & \textit{\textbf{B}}  & \textit{\textbf{C}} \\ \hline
 \textit{} & \textit{}  & \textit{} & \textit{} \\
  \textit{Relabelling} & \textit{$S^{x} \mapsto  \mos$} & \textit{$S^{\vec{x}} \mapsto  \mos$}  & \textit{} \\
  \textit{inner nodes} & \textit{}  & \textit{} & \textit{} \\
  \textit{} & \textit{} & \textit{$Polyadic \mapsto$}  & \textit{$S, V\! P, V' \mapsto$} \\
  \textit{} & \textit{} & \textit{$\pu$} & \textit{$\cps$ } \\ \hline

    \textit{} & \textit{}  & \textit{} & \textit{} \\
  \textit{Relabelling} & \textit{S $\mapsto$ relation} & \textit{S $\mapsto$ relation} & \textit{V, V\! t, V\! dt $\mapsto$}\\
   \textit{leaves} & \textit{}  & \textit{} & \textit{continuized relation} \\

  \textit{} & \textit{} & \textit{} & \textit{} \\
  \textit{ } & \textit{$QP\mapsto\; \cC$-comp.}  & \textit{$QP\mapsto\; \cC$-comp.} & \textit{$QP\mapsto\; \cC$-comp.} \\  \hline
\end{array}$$ The semantics for sentences with intransitive and transitive verbs, as defined by the strategies A, B, and C, are equivalent. The semantics for sentences with ditransitive verbs, as defined by the strategies A, B, are equivalent. They provide six asymmetric readings of the sentence. The semantics for sentences with ditransitive verbs, as defined by the strategy C, provides four asymmetric readings of the sentence such that QP in subject position can be placed either first or last only. Thus they correspond to four out of six readings accounted for by strategies A and B. The proofs are given in the Appendix.

Appendix
========

The continuation monad
----------------------

In this subsection, we gather all the basic facts (sometimes repeated from the text) of the [*continuation monad*]{} $\cC$ on $Set$. We have an adjunction

=1000 =370

(,)(,) (0,140)(1,0)\[Set‘Set\^[op]{}‘\][1000]{}[0]{}a (0,210)(1,0)\[‘‘\][1000]{}[1]{}a (0,70)(1,0)\[‘‘\^[op]{}\][1000]{}[-1]{}b

where both $\cP$ and $\cP^{op}$ are the contravariant powerset functors[^2] with the domains and codomains as displayed. In particular, for $f:X{\rightarrow}Y$, the function $\cP(f)=f^{-1} : \cP(Y){\rightarrow}\cP(X)$ is given by $$f^{-1}(h) = h\circ f$$ for $h:Y{\rightarrow}\bt$.\
Function $\eta_X : X{\rightarrow}\cC(X)$, the component at set $X$ of the unit of this adjunction $\eta : 1_{Set} {\rightarrow}\cP\cP^{op}=\cC$, is given by $$\eta_X(x)= \lambda h_{:\cP(X)}. h(x).$$ Function $\varepsilon_X : X{\rightarrow}\cC(X)$, the component at set $X$ of the counit of this adjunction $\varepsilon : 1_{Set} {\rightarrow}\cP^{op}\cP$, is given by (essentially the same formula) $$\varepsilon_X(x)= \lambda h_{:\cP^{op}(X)}. h(x)$$ for $x\in X$.\
The function $\cC(f): \cC(X){\rightarrow}\cC(Y)$, for $Q:\cP(X){\rightarrow}\bt \in \cC(X)$, is a function $\cC(f)(Q):\cP(Y){\rightarrow}\bt$ given by $$\cC(f)(Q)(h) = Q(h\circ f)$$ for $h:Y{\rightarrow}\bt$.\
The monad induced by this adjunction is the continuation monad. Its multiplication is given by the counit of the above adjunction transported back to $Set$, i.e. $\mu = \cP^{op}(\varepsilon_{\cP})$. For $X$ in $Set$, the function $$\mu_X:\cC^2(X){\rightarrow}\cC(X)$$ is given by $$\mu_X(\cR) = \cR\circ\eta_{\cP(X)}$$ for $\cR\in \cC^{2}(X)$.\
In $\lambda$-notation we write $$\mu_X(\cF)(h)=\cF({\leftarrow}D_{: \cC(X)}.D(h)).$$

The left strength for the monad $\cC$ is $$\stl : \cC(X)\times Y {\longrightarrow}\cC(X\times Y)$$ for $M\in \cC(X)$ and $y\in Y$, given by $$\stl(M,y)={\leftarrow}c_{:\cP(X\times Y)}. M({\leftarrow}x_{:X}. c(x,y)): \cP(X\times Y){\rightarrow}\bt$$ and the right strength, for $x\in X$ and $n\in \cC(Y)$, is given by $$\str(x,N)={\leftarrow}c_{: \cP(X\times Y)}. M(\lambda y_{:Y}.c(x,y)): \cP(X\times Y) {\rightarrow}\bt.$$

The left pile’up operation $$\pul : \cC(X)\times \cC(Y) {\longrightarrow}\cC(X\times Y)$$ is the following composition

=2700 =250

(,)(,) (0,50)(1,0)\[(X)(Y)‘(X(Y))‘\][900]{}[1]{}a (900,50)(1,0)\[‘\^2(XY)‘()\][900]{}[1]{}a (1800,50)(1,0)\[‘(XY)‘\_[XY]{}\][900]{}[1]{}a

where, for $Q\in \cC(X)$, $Q'\in\cC(Y)$, $c\in \cP(X\times \cC(Y))$, we have $$\stl(Q,Q')(c)= Q({\leftarrow}x_{:X} c(x,Q))$$ and, for $d\in \cC(X\times \cC(Y))$, $\cU\in \cP\cC(X\times Y)$, we have $$\cC(\str)(d)(\cU) = d(\cU\circ \str).$$

Now, using the above formulas, we can calculate $\pul$ as the composition on $Q\in \cC(X)$, $Q'\in\cC(Y)$, and $c\in \cP(X\times Y)$ as follows $$\pul(Q,Q')(c) =$$ $$=\mu_{X\times Y}(\cC(\str)(\stl(Q,Q')))(c) =$$ $$= \cC(\str)(\stl(Q,Q'))({\leftarrow}D_{:\cC(X\times Y)} D(c)) =$$ $$= \stl(Q,Q'))(({\leftarrow}D_{:\cC(X\times Y)} D(c))\circ \str) =$$ $$= Q({\leftarrow}x_{:X}(({\leftarrow}D_{:\cC(X\times Y)} D(c))\circ \str)(x,Q')) =$$ $$= Q({\leftarrow}x_{:X}(({\leftarrow}D_{:\cC(X\times Y)} D(c))(\str(x,Q')) =$$ $$= Q({\leftarrow}x_{:X} \str(x,Q')(c)) =$$ $$= Q({\leftarrow}x_{:X} Q'({\leftarrow}y_{:Y}c(x,y)))$$ Similarly, we can show that $$\pur(Q,Q')(c) = Q'({\leftarrow}y_{:Y} \Q({\leftarrow}x_{:X}c(x,y))).$$

One can easily verify that pile’ups are related by $$\pur_{X,Y} = \cC(\pi_{(2,1)})\circ \pul_{Y,X}\circ \pi_{(2,1)}.$$

Some properties of pile’up operations
-------------------------------------

\[app-pu-lem1\] $\pu$’s on pairs where one element is continuaized agree and are equal to the corresponding strength.

[*Proof.*]{} We have to show that the functions

=1400 =400

(,)(,) (0,200)(1,0)\[‘‘\_[X\_1,X\_2]{}\][1400]{}[1]{}a (0,150)(1,0)\[T(X\_1)T(X\_2)‘T(X\_1X\_2)‘\][1400]{}[0]{}a (0,100)(1,0)\[‘‘\_[X\_1,X\_2]{}\][1400]{}[1]{}b

are equalized by both

=1400 =100

(,)(,) (0,00)(1,0)\[X\_1T(X\_2)‘T(X\_1)T(X\_2)‘\_[X\_1]{}T(1\_[X\_2]{})\][1400]{}[1]{}a

and

=1400 =100

(,)(,) (0,00)(1,0)\[T(X\_1)X\_2‘T(X\_1)T(X\_2)‘T(1\_[X\_1]{})\_[X\_2]{}\][1400]{}[1]{}a

and their composition with these functions are equal to strength morphisms.

Using the diagram

=2600 =2000

(,)(,) (0,1000)\[T(X\_1)X\_2‘T(X\_1)T(X\_2)‘T(X\_1X\_2)‘T(X\_1T(X\_2));T(1\_[X\_1]{})\_[X\_2]{}‘\_[X\_1,X\_2]{}‘\_[T(X\_1),X\_2]{}‘T(1\_[X\_1]{}\_[X\_2]{})\] (1300,1000)\[‘ T(T(X\_1)X\_2)‘‘T\^2(X\_1X\_2); \_[T(X\_1),X\_2]{}“T(\_[X\_1,X\_2]{})‘T(\_[X\_1,X\_2]{})\]

(2600,1000)(0,-1)\[‘T(X\_1X\_2)‘\_[X\_1X\_2]{}\][1000]{}[1]{}r

(0,920)[(0,-1)[920]{}]{} (0,0)[(1,0)[2300]{}]{} (1100,50)[$1_{T(X_1\times X_2)}$]{}

(200,920)[(0,-1)[320]{}]{} (200,600)[(1,0)[1800]{}]{} (2000,600)[(1,1)[350]{}]{} (1100,650)[$T(\eta_{X_1\times X_2})$]{}

(100,920)[(0,-1)[520]{}]{} (100,400)[(1,0)[2100]{}]{} (2200,400)[(1,2)[270]{}]{} (1100,310)[$\eta_{T(X_1\times X_2)}$]{}

(0,1700)[(0,1)[200]{}]{} (0,1900)[(1,0)[2600]{}]{} (2600,1900)[(0,-1)[200]{}]{} (1100,1940)[$\eta_{T(X_1)\times X_2}$]{}

we shall show that $${\pur}_{X_1,X_2} \circ (T(1_{X_1})\times \eta_{X_2})= \stl_{X_1,X_2} =  {\pul}_{X_1,X_2}\circ (T(1_{X_1})\times \eta_{X_2}) .$$ The other cases are symmetric. We have

$${\pur}_{X_1,X_2} \circ (T(1_{X_1})\times \eta_{X_2}) = \;\;({\rm def\; of}\;\pur)$$ $$= \mu_{X_1,X_2}\circ T(\stl_{X_1,X_2})\circ \str_{T(X_1),X_2} \circ (T(1_{X_1})\times \eta_{X_2}) = \;\;(\eta\;{\rm strong\; w.r.t.}\; \str)$$ $$= \mu_{X_1,X_2}\circ T(\stl_{X_1,X_2})\circ \eta_{T(X_1)\times X_2} = \;\; (\eta\; {\rm nat\; transf})$$ $$= \mu_{X_1,X_2}\circ \eta_{T(X_1\times X_2)})\circ \stl_{X_1,X_2} = \;\; (T\; {\rm monad})$$ $$= \stl_{X_1,X_2}$$ To show the remaining equation, we notice that we can continue the penultimate formula above as follows $${\pur}_{X_1,X_2} \circ (T(1_{X_1})\times \eta_{X_2}) =\ldots = \mu_{X_1,X_2}\circ \eta_{T(X_1\times X_2)})\circ \stl_{X_1,X_2} = \;\; (T\; {\rm monad})$$ $$= \mu_{X_1,X_2}\circ T(\eta_{X_1\times X_2})\circ \stl_{X_1,X_2} = \;\;(\eta\;{\rm strong\; w.r.t.}\; \str)$$ $$= \mu_{X_1,X_2}\circ T(\str_{X_1,X_2})\circ   T(1_{X_1}\times \eta_{X_2})\circ \stl_{X_1,X_2} = \;\;(\stl\;{\rm nat\; transf})$$ $$= \mu_{X_1,X_2}\circ T(\str_{X_1,X_2})\circ \stl_{X_1,X_2}\circ   T(1_{X_1}\times \eta_{X_2}) = \;\;({\rm def\; of}\;\pul)$$ $$= {\pul}_{X_1,X_2} \circ (T(1_{X_1})\times \eta_{X_2})$$

$\diamondsuit$

The left and right $\cps$-operation on pairs where one element is continuized agree.

[*Proof.*]{} The corollary states that, for any sets $X$, $Y$, $Z$ and a function $f:X\times Y{\rightarrow}Z$, both morphisms

=1200 =100

(,)(,) (0,00)(1,0)\[XT(Y)‘T(X)T(Y)‘\_[X]{}1\][1200]{}[1]{}a

and

=1200 =100

(,)(,) (0,00)(1,0)\[T(X)Y‘T(X)T(Y)‘1\_[Y]{}\][1200]{}[1]{}a

equalize the pair of morphisms

=1400 =400

(,)(,) (0,200)(1,0)\[‘‘(f)\][1400]{}[1]{}a (0,150)(1,0)\[T(X)T(Y)‘Z‘\][1400]{}[0]{}a (0,100)(1,0)\[‘‘(f)\][1400]{}[1]{}b

This immediately follows from the above lemma and the definition of $\cps$’es. $\diamondsuit$

Using binary pile’up operations, we can define eight ternary pile’up operation $$T(X_1)\times  T(X_2)\times  T(X_3){\longrightarrow}T(X_1\times  X_2\times X_3)$$ out of the following diagram

=2600 =1300

(,)(,) (600,1200)[$T(X_1)\times T(X_2)\times T(X_3)$]{} (0,600)[$T^2(X_1\times X_2)\times T(X_3)$]{} (1500,600)[$T(X_1) \times T^2(X_2\times X_3)$]{} (800,0)[$T^3(X_1\times X_2\times X_3)$]{} (200,500)[(2,-1)[700]{}]{} (400,500)[(2,-1)[700]{}]{} (2000,500)[(-2,-1)[700]{}]{} (2200,500)[(-2,-1)[700]{}]{}

(150,350)[$_{\pul}$]{} (800,350)[$_{\pur}$]{}

(1350,350)[$_{\pul}$]{} (2000,350)[$_{\pur}$]{}

(1300,1100)[(2,-1)[700]{}]{} (1500,1100)[(2,-1)[700]{}]{} (900,1100)[(-2,-1)[700]{}]{} (1100,1100)[(-2,-1)[700]{}]{} (-50,850)[$_{{\pul}\times 1}$]{} (650,850)[$_{{\pur}\times 1}$]{} (1350,850)[$_{1\times {\pul}}$]{} (2050,850)[$_{1\times {\pur}}$]{}

However, both ${\pul}$ and ${\pur}$ operations are associative (Proposition \[app-pu-assoc\] below) and hence only six of them are different, in general.

\[app-pu-assoc\] Both $\pul$ and $\pur$ operations are associative on any monad on $Set$.

[*Proof.*]{} In fact, $\pul$ and $\pur$ are associative on any bi-strong monad on monoidal category. We shall show this fact for a monad $T$ on $Set$ with the canonical strength.

We need to show that $${\pur}\circ ({\pur}\times 1) = {\pur}\circ (1\times {\pur})$$ and $${\pul}\circ ({\pul}\times 1) = {\pul}\circ (1\times {\pul})$$ But as pile’up are mutually definable, either of these equalities implies easily the other. We shall show the latter equality. For sets $X_1$, $X_2$, $X_3$, using all the assumptions, we have

$$\pul_{X_1\times X_2,X_3}\circ (\pul_{X_1,X_2}\times 1_{T(X_3)}) =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ  T(\str_{X_1\times X_2, X_3}) \circ  \underline{\stl_{X_1\times X_2, T(X_3)}\circ}$$ $$\underline{\circ\, (\mu_{X_1\times X_2}\times T(1_{X_3}))}\circ (T(\str_{X_1,X_2})\times 1_{T(X_3)})\circ (\stl_{X_1,T(X_2)}\times 1_{T(X_3)}) =$$ $$= \mu_{X_1,\times X_2\times X_3} \circ  \underline{T(\str_{X_1\times X_2, X_3}) \circ  \mu_{X_1\times X_2\times T(X_3)}} \circ T(\stl_{X_1\times X_2, T(X_3)})\,\circ$$ $$\circ\, \underline{\stl_{T(X_1\times X_2), T(X_3)}\circ (T(\str_{X_1,X_2})\times T(1_{X_3}))}\circ (\stl_{X_1,T(X_2)}\times 1_{T(X_3)}) =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ  \mu_{T(X_1\times X_2\times X_3)}  \circ  T^2(\str_{X_1\times X_2, T(X_3)})\circ T(\stl_{X_1\times X_2, T(X_3)})\,\circ$$ $$\circ\, (T(\str_{X_1,X_2}\times 1_{X_3})) \circ\, \underline{\stl_{T(X_1\times X_2), T(X_3)}\circ (\stl_{X_1,T(X_2)}\times 1_{T(X_3)})} =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ  \mu_{T(X_1\times X_2\times X_3)}  \circ  T^2(\str_{X_1\times X_2, T(X_3)})
\circ \underline{T(\stl_{X_1\times X_2, T(X_3)})\,\circ }$$ $$\underline{\circ\, (T(\str_{X_1,X_2}\times 1_{T(X_3)}))} \circ\, \stl_{X_1, T(X_2)\times T(X_3)} =$$ $$= \mu_{X_1,\times X_2\times X_3} \circ  \mu_{T(X_1\times X_2\times X_3)}  \circ  T^2(\str_{X_1\times X_2, T(X_3)})\circ T(\str_{X_1, X_2\times T(X_3)})\,\circ$$ $$\circ\, \underline{T(1_{X_1}\times \stl_{X_2, T(X_3)}) \circ\, \stl_{X_1, T(X_2)\times T(X_3)}} =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ  \mu_{T(X_1\times X_2\times X_3)}  \circ  \underline{T^2(\str_{X_1\times X_2, T(X_3)})}\circ T(\str_{X_1,X_2\times T(X_3)})\,\circ$$ $$\circ\, \stl_{X_1, T(X_2\times T(X_3))} \circ (T(1_{X_1})\times \stl_{X_2,T(X_3)})  =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ  \mu_{T(X_1\times X_2\times X_3)}  \circ  T^2(\str_{X_1,T(X_2\times X_3)})\circ\underline{ T^2(1_{X_1}\times \str_{X_2,X_3})\,\circ}$$ $$\underline{\circ\, T(\str_{X_1,X_2\times T(X_3)})} \circ\, \stl_{X_1, T(X_2\times T(X_3))} \circ (T(1_{X_1})\times \stl_{X_2,T(X_3)})  =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ  \mu_{T(X_1\times X_2\times X_3)}  \circ  T^2(\str_{X_1,T(X_2\times X_3)})
\circ T(\str_{X_1,T(X_2\times X_3)})\, \circ$$ $$\circ\, \underline{T(1_{X_1}\times T(\str_{X_2,X_3}))\circ \stl_{X_1, T(X_2\times T(X_3))}} \circ (T(1_{X_1})\times \stl_{X_2,T(X_3)})  =$$

$$= \mu_{X_1,\times X_2\times X_3} \circ \underline{ \mu_{T(X_1\times X_2\times X_3)}  \circ  T^2(\str_{X_1,T(X_2\times X_3)})
\circ T(\str_{X_1,T(X_2\times X_3)})} \;\circ\,$$ $$\circ\, \stl_{X_1, T^2(X_2\times X_3)} \circ\, (T(1_{X_1})\times T(\str_{X_2,X_3})) \circ (T(1_{X_1})\times \stl_{X_2,T(X_3)})  =$$

$$= \mu_{X_1,\times X_2\times X_3} \,\circ\, T(\str_{X_1,X_2\times X_3}) \circ\,\underline{ T(1_{X_1}\times \mu_{ X_2\times X_3} ) \;\circ}$$ $$\underline{\circ\, \stl_{X_1, T^2(X_2\times X_3)}} \circ\, (T(1_{X_1})\times T(\str_{X_2,X_3})) \circ (T(1_{X_1})\times \stl_{X_2,T(X_3)})  =$$

$$= \mu_{X_1,\times X_2\times X_3} \,\circ\, T(\str_{X_1,X_2\times X_3}) \circ\, \stl_{X_1, T(X_2\times X_3)}\circ$$ $$\circ\, (T(1_{X_1})\times \mu_{ X_2\times X_3} )  \circ\, (T(1_{X_1})\times T(\str_{X_2,X_3})) \circ (T(1_{X_1})\times \stl_{X_2,T(X_3)})  =$$

$$=\pul_{X_1,X_2\times X_3}\circ (1_{T(X_3)}\times \pul_{X_2,X_3})$$ $\diamondsuit$

Arity one: intransitive verbs
-----------------------------

The semantics for sentences with intransitive verbs, as defined by the strategies A, B, and C, are equivalent.

[*Proof.*]{} In case of a sentence with an intransitive verb the semantics are defined by morphisms $\strat^1_A$, $\strat^1_B$, and $\strat^1_C$. We need to show that they are equal. We have $$\strat^1_A= \mosl_X= \strat^1_B.$$

$\strat^1_C$ is the composition of the following morphisms

=2600 =200

(,)(,) (0,50)(1,0)\[(X)(X)‘(X)(X)‘1\_[(X)]{}\][1200]{}[1]{}a (1200,50)(1,0)\[‘()‘(\_X)\][1200]{}[1]{}a (2400,50)(1,0)\[‘‘ev\_[id\_]{}\][500]{}[1]{}a

Thus we need to show that this composition is equal to $\mosl_X$. Consider the following diagram

=2000 =800

(,)(,) (0,100)\[(X)(X)‘‘(X)(X)‘();\_X‘1\_[(X)]{}‘ev\_[id\_]{}‘\]

(0,100)(1,0)\[‘(X(X))‘\_X\][1000]{}[1]{}b (1000,100)(1,0)\[‘‘(\_X\][1000]{}[1]{}b (0,650)(2,-1)\[‘‘\][1000]{}[1]{}l (1200,300)(2,1)\[‘‘ ev\_[\_X]{}\][500]{}[1]{}r

The left triangle commutes, as a consequence of Lemma \[app-pu-lem1\]. To see that the mid triangle commutes, we take $M\in \cC(X)$ and $h\in \cP(X)$, and calculate $$ev_{\epsr_X}\circ \str(Q,h) =$$ $$= ev_{\epsr_X}({\leftarrow}D_{:\cP(X\times\cP(X))}M({\leftarrow}x_{:X} D(x,h))) =$$ $$= M({\leftarrow}x_{:X} \epsr_X(x,h)) =$$ $$= M({\leftarrow}x_{:X} h(x)) =$$ $$= N(h)=\mosl(N,h).$$

Finally, to see that the right triangle commutes, we take $N\in \cC(X\times \cP(X))$ and calculate $$ev_{id_\bt}\circ\cC(\epsr_X)(N)=$$ $$= ev_{id_\bt} ({\leftarrow}c_{:\cP(\bt)} N(c\circ \epsr_X)) =$$ $$= N( \epsr_X) = ev_{\epsr_X}(N).$$ Thus the whole diagram commutes, and hence $\strat^1_C=\mosl_X$, as required. $\diamondsuit$

The above proof shows also the following technical lemma.

\[app-mos-st\] For any set $X$, the diagram

=1000 =600

(,)(,) (0,50)\[(X)(X)‘‘(X(X))‘();\_X‘‘ev\_[id\_]{}‘(\_X)\]

commutes.

Arity two: transitive verbs
---------------------------

The semantics for sentences with transitive verbs, as defined by the strategies A, B, and C, are equivalent. They provide two asymmetric readings of the sentence.

[*Proof.*]{} In case of sentences with transitive verbs the semantics are defined by morphisms $\strat^{2,\sigma}_A$, $\strat^{2,\sigma}_B$, and $\strat^{2,\varepsilon}_C$, with $\sigma\in S_2=\{id_2,\tau\}$ and $\varepsilon\in \{ l,r\}$. We need to show the equalities $$\strat^{2,\sigma}_A = \strat^{2,\sigma}_B,$$ for $\sigma\in S_2$, and $$\strat^{2,id_2}_B =\strat^{2,l}_C,\hskip 5mm     \strat^{2,\tau}_B = \strat^{2,r}_C.$$

To show the first equality, with $Q_1\in \cC(X_1)$, $Q_2\in \cC(X_2)$, and $P\in \cP(X_1\times X_2)$, we have $$\strat^{2,\sigma}_A(Q_1,Q_2,P) =$$ $$= \mosl_{X_{\sigma(1)}}(Q_{\sigma(1)},\mosl_{X_{\sigma(2)}}(Q_{\sigma(2)},P)) =$$ $$= \mosl_{X_{\sigma(1)}}(Q_{\sigma(1)},{\leftarrow}x_{\sigma(1): X_{\sigma(1)}}. Q_{\sigma(2)}({\leftarrow}x_{\sigma(2):X_{\sigma(2)}}.P(x_1,x_2))) =$$ $$= Q_{\sigma(1)}({\leftarrow}x_{\sigma(1): X_{\sigma(1)}}. Q_{\sigma(2)}({\leftarrow}x_{\sigma(2):X_{\sigma(2)}}.P(x_1,x_2))) =$$ $$= Q_{\sigma(1)}({\leftarrow}x_{\sigma(1): X_{\sigma(1)}}. Q_{\sigma(2)}({\leftarrow}x_{\sigma(2):X_{\sigma(2)}}.P(\pi_{\sigma^{-1}}(x_{\sigma(1)},x_{\sigma(2)}))) =$$ $$= \pul(Q_{\sigma(1)},Q_{\sigma(2)})(P\circ\pi^{-1}) =$$ $$\cC(\pi_{\sigma^{-1}})(\pul(Q_{\sigma(1)},Q_{\sigma(2)}))(P) =$$ $$=\strat^{2,\sigma}_B(Q_1,Q_2,P)$$

To show the remaining two equalities, let us first note that if either $\sigma=id_2$ and $\varepsilon=l$ or $\sigma=\tau$ and $\varepsilon=r$, we have $$\pu^\varepsilon= \cC(\pi_{\sigma^{-1}})\circ \pul\circ \pi_\sigma.$$ Thus we shall assume the above equation relating $\sigma$ with $\varepsilon$, and, with $Q_1\in \cC(X_1)$, $Q_2\in \cC(X_2)$, and $P\in \cP(X_1\times X_2)$, we obtain (the diagram illustrating these calculations would be too big to fit a page but the reader is encouraged to draw one)

$$\strat^{2,\varepsilon}_C =$$ $$= ev_{id_\bt} \circ \cps^\varepsilon(\epsr_{X_1})\circ (1\times\cps^?(\epsr_{X_2}))\circ (1\times 1\times \eta_{\cP(X_1\times X_2)} =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1})\circ \pu^\varepsilon\circ (\cC(1)\times\cC(\epsr_{X_2}))\circ (1\times \pu^?)\circ (1\times 1\times \eta) =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1})\circ \cC(1\times\epsr_{X_2})\circ \pu^\varepsilon\circ (1\times \pu^?)\circ (1\times 1\times \eta) =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1\times X_2})\circ \pu^\varepsilon\circ (1\times \pu^?)\circ (1\times 1\times \eta) =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1\times X_2})\circ \pu^?\circ (\pu^\varepsilon\times 1)\circ (1\times 1\times \eta) =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1\times X_2})\circ \pu^?\circ (1\times \eta)\circ (1\times \pu^\varepsilon) =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1\times X_2})\circ \stl\circ (1\times \pu^\varepsilon) =$$ $$= ev_{id_\bt} \circ  \cC(\epsr_{X_1\times X_2})\circ \stl\circ (\cC(\pi_{\sigma^{-1}})\times 1)\circ (\pul\times 1)\circ (\pi_{\sigma}\times 1) =$$ $$= \mosl_{X_1\times X_2}\circ (\cC(\pi_{\sigma^{-1}})\times 1)\circ (\pul\times 1)\circ (\pi_{\sigma}\times 1) =$$ $$= \strat^{2,\sigma}_B$$

In the above calculations we used: the definition of $\cps$’es, naturality of $\pu^\varepsilon$, relations between $\eps$ morphisms, associativity of $\pu^\varepsilon$ (Proposition \[app-pu-assoc\]), properties of product morphisms, pile’up lemma, and finally Lemma \[app-mos-st\].

Here and below $\cps^?$, $\pu^?$ stands for either $\cps^l$, $\pu^l$ or $\cps^r$, $\pu^r$ whatever is more convenient at the moment as it does not influence the end result. $\diamondsuit$

Arity three: ditransitive verbs
-------------------------------

The semantics for sentences with ditransitive verbs, as defined by the strategies A, B, are equivalent. They provide six asymmetric readings of the sentence.

[*Proof.*]{} In case of sentences with ditransitive verbs the semantics are defined by morphisms $\strat^{3,\sigma}_A$, $\strat^{3,\sigma}_B$, and $\strat^{2,\varepsilon}_C$, with $\sigma\in S_3$ and $\varepsilon\in \{ l,r\}$. We need to show the equalities $$\strat^{3,\sigma}_A = \strat^{3,\sigma}_B,$$ for $\sigma\in S_3$.

The calculations are similar to those for transitive verbs. We present them for completeness. With $Q_1\in \cC(X_1)$, $Q_2\in \cC(X_2)$, $Q_3\in \cC(X_3)$, and $P\in \cP(X_1\times X_2\times X_3)$, we have $$\strat^{3,\sigma}_A(Q_1,Q_2,Q_3,P) =$$ $$= \mosl_{X_{\sigma(1)}}(Q_{\sigma(1)},\mosl_{X_{\sigma(2)}}(Q_{\sigma(2)},\mosl_{X_{\sigma(3)}}(Q_{\sigma(3)},P)) =$$ $$= Q_{\sigma(1)}({\leftarrow}x_{\sigma(1): X_{\sigma(1)}}. Q_{\sigma(2)}({\leftarrow}x_{\sigma(2):X_{\sigma(2)}}.
Q_{\sigma(3)}({\leftarrow}x_{\sigma(3): X_{\sigma(3)}}.P(x_1,x_2,x_3))) =$$ $$= Q_{\sigma(1)}({\leftarrow}x_{\sigma(1): X_{\sigma(1)}}. Q_{\sigma(2)}({\leftarrow}x_{\sigma(2):X_{\sigma(2)}}. Q_{\sigma(3)}({\leftarrow}x_{\sigma(3): X_{\sigma(3)}}. P(\pi_{\sigma^{-1}}(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)}))) =$$ $$= \pul(Q_{\sigma(1)},\pul(Q_{\sigma(2)},Q_{\sigma(3)}))(P\circ\pi_{\sigma^{-1}}) =$$ $$\cC(\pi_{\sigma^{-1}})(\pul(Q_{\sigma(1)},\pul(Q_{\sigma(2)},Q_{\sigma(3)})))(P) =$$ $$=\strat^{2,\sigma}_B(Q_1,Q_2,Q_3,P)$$ as required. $\diamondsuit$

The semantics for sentences with ditransitive verbs, as defined by the strategy C, provides four asymmetric readings of the sentence such that QP in subject position can be placed either first or last only. Thus they correspond to four out of six readings accounted for by strategies A and B.

[*Proof.*]{} In case of sentences with ditransitive verbs the semantics, according to strategies B and C, are defined by morphisms $\strat^{3,\sigma}_B$, $\strat^{3,\varepsilon,\varepsilon'}_C$, respectively. As we shall show, these morphisms are equal whenever $\sigma\in S_3$ is related to the pair $\lk\varepsilon', \varepsilon\rk\in \{l,r\}^2$ via relation $$\pu^{\varepsilon'}\circ (1\times \pu^{\varepsilon})= \cC(\pi_{\sigma^{-1}}) \circ \pul\circ (1\times \pul) \circ \pi_{\sigma}$$

As $\pul$ leaves the order intact and $\pur$ swaps the order, we can see that we have the following correspondence

$$\begin{array}{|c|c|} \hline
    \sigma & \lk \varepsilon',\varepsilon\rk \\ \hline
    (1,2,3) & \lk l,l\rk \\
    (1,3,2) & \lk l,r\rk \\
     (2,3,1)& \lk r,l\rk \\
     (3,2,1)& \lk r,r\rk \\
     (2,1,3)& - \\
     (3,1,2)&  -\\ \hline
  \end{array}$$ Thus we shall assume the $\sigma$ is related to the pair $\lk \varepsilon,\varepsilon'\rk$, and, with $Q_1\in \cC(X_1)$, $Q_2\in \cC(X_2)$, $Q_3\in \cC(X_3)$, and $P\in \cP(X_1\times X_2\times X_3)$, we obtain (the diagram illustrating these calculations would be again too big to fit a page but the reader is encouraged to draw one)

$$\strat^{3,\varepsilon',\varepsilon}_C =$$

$$= ev_{id_\bt} \circ \cps^{\varepsilon'}(\epsr_{X_1})\circ  (1\times\cps^{\varepsilon}(\epsr_{X_2}))\circ$$ $$\circ (1\times 1\times\cps^?(\epsr_{X_3}))\circ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1})\circ \pu^{\varepsilon'}\circ  (\cC(1)\times\cC(\epsr_{X_2}))\circ (1\times \pu^\varepsilon)\circ$$ $$\circ (\cC(1)\times \cC(1)\times \cC(\epsr_{X_3}))\circ (1\times 1\times \pu^?)\circ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1})\circ  (\cC(1\times\epsr_{X_2}))\circ \pu^{\varepsilon'}\circ (\cC(1)\times \cC(1\times \epsr_{X_3}))\circ$$ $$\circ(1\times \pu^\varepsilon)\circ (1\times 1\times \pu^?)\circ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1})\circ  (\cC(1\times\epsr_{X_2}))\circ (\cC(1\times 1\times \epsr_{X_3}))\circ \pu^{\varepsilon'}\circ$$ $$\circ(1\times \pu^\varepsilon)\circ (1\times 1\times \pu^?)\circ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ \pu^{\varepsilon'}\circ$$ $$\circ(1\times \pu^\varepsilon)\circ (1\times 1\times \pu^?)\circ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ \pu^{\varepsilon'}\circ$$ $$\circ(1\times \pu^\varepsilon)\circ (1\times 1\times \pu^?)\circ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ \pu^{\varepsilon'}\circ$$ $$\circ (1\times \pu^?)\circ(1\times \pu^\varepsilon\times 1)\circ\ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ \pu^?\circ$$ $$\circ (\pu^{\varepsilon'}\times 1)\circ(1\times \pu^\varepsilon\times 1)\circ\ (1\times 1\times 1\times \eta)\stackrel{*}{=}$$

$$\stackrel{*}{=} ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ \pu^?\circ$$ $$\circ (\cC(\pi_{\sigma^{-1}})\times \cC(1)) \circ (\pul\times 1)\circ (1\times \pul \times 1) \circ (\pi_{\sigma}\times 1)\circ\ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ (\cC(\pi_{\sigma^{-1}}\times 1)\circ \pu^?\circ$$ $$\circ (\pul\times 1)\circ (1\times \pul \times 1) \circ (\pi_{\sigma}\times 1)\circ\ (1\times 1\times 1\times \eta) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ (\cC(\pi_{\sigma^{-1}}\times 1)\circ \pu^?\circ$$ $$\circ (\pul\times 1)\circ (1\times \pul \times 1) \circ\ (1\times 1\times 1\times \eta)\circ (\pi_{\sigma}\times 1) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ (\cC(\pi_{\sigma^{-1}}\times 1)\circ \pu^?\circ$$ $$\circ (\pul\times 1) \circ\ (1\times \times \eta)\circ (1\times \pul \times 1)\circ (\pi_{\sigma}\times 1) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ (\cC(\pi_{\sigma^{-1}}\times 1)\circ \pu^?\circ$$ $$= \circ (\pul\times 1) \circ\ (1\times 1\times \eta)\circ (1\times \pul \times 1)\circ (\pi_{\sigma}\times 1) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ (\cC(\pi_{\sigma^{-1}}\times 1)\circ \pu^?\circ$$ $$\circ\ (1\times \eta)\circ (\pul\times 1) \circ (1\times \pul \times 1)\circ (\pi_{\sigma}\times 1) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ (\cC(\pi_{\sigma^{-1}}\times 1)\circ \stl^l \circ$$ $$\circ (\pul\times 1) \circ (1\times \pul \times 1)\circ (\pi_{\sigma}\times 1) =$$

$$= ev_{id_\bt} \circ \cC(\epsr_{X_1\times X_2\times X_3})\circ \stl^l \circ(\cC(\pi_{\sigma^{-1}})\times \cC(1))\circ$$ $$\circ (\pul\times 1) \circ (1\times \pul \times 1)\circ (\pi_{\sigma}\times 1) =$$

$$= \mos^l_{X_1\times X_2\times X_3} \circ(\cC(\pi_{\sigma^{-1}})\times \cC(1))\circ$$ $$\circ (\pul\times 1) \circ (1\times \pul \times 1)\circ (\pi_{\sigma}\times 1) =$$

$$= \strat^{3,\sigma}_B$$

In the above calculations we used: the definition of $\cps$’es, naturality of $\pu$’s (four times in three non-consecutive steps!), relations between $\eps$ morphisms, associativity of $\pu$’s (Proposition \[app-pu-assoc\]), relations between $\sigma$ and $\lk \varepsilon',\varepsilon\rk$, properties of product morphisms (three consecutive steps), pile’up lemma, naturality of strength, and finally Lemma \[app-mos-st\]. $\diamondsuit$

Barker, C.: Continuations and the nature of quantification. Natural Language Semantics 10, 211-242 (2002).

Barker, C., Shan, C.c.: Continuations and Natural Language. Oxford University Press (2014).

Barwise, J., Cooper, R.: Generalized Quantifiers and Natural Language. Linguistics & Philosophy 4, 159-219 (1981).

Bekki, D., Assai, K.: Representing Covert Movements by Delimited Continuations In Nakakoji, K., Murakami, Y., McCready, E. (eds.) New Frontiers in Artificial Intelligence, JSAI-isAI, LNAI 6284, 161-180, (2010).

Benthem, J.: Polyadic quantifiers. Linguistics & Philosophy 12, 437-464 (1989).

Cooper, R.: Quantification and Syntactic Structure. Dordrecht: Reidel (1983).

de Groote, P.: Type raising, continuations, and classical logic. In van Rooy, R., Stokhof, M. (eds.), Proceedings of the 13th Amsterdam Colloquium, Institute for Logic, Language and Computation, Universiteit van Amsterdam 97-101 (2001).

Eilenberg, S., Kelly, M.: Closed Categories. Proc. Conf. Categorical Algebra (La Jolla 1965), Springer-Verlag 1966.

Keenan, E. L.: Unreducible n-ary quantifiers in natural language. In Gärdenfors P. (ed.), Generalized Quantifier: Linguistic and Logical Approaches, Reidel Dordrecht. 109-150 (1987).

Keenan, E. L.: Beyond the Frege Boundary. Linguistics & Philosophy 15, 199-221 (1992).

Kiselyov, O., Shan, C.c.: Continuation Hierarchy and Quantifier Scope. In McCready, E., Yabushita, K., Yoshimoto, K. (eds.), Formal Approaches to Semantics and Pragmatics: Japanese and Beyond. Studies in Linguistics and Philosophy, Springer Netherlands, 105-134 (2014).

Kock, A.: Monads on symmetric monoidal closed categories. Arch. Math. (Basel), 21:1–10 (1970).

Kock, A.: Closed categories generated by commutative monads. J. Austral. Math. Soc., 12:405–424 (1971).

Kock, A.: Strong functors and monoidal monads. Arch. Math. (Basel), 23:113–120 (1972).

Lindström, P.: First-order predicate logic with generalized quantifiers. Theoria 32, 186-95.(1966).

May, R.: The Grammar of Quantification. PhD dissertation, MIT (1977).

May, R.: Logical Form: Its Structure and Derivation. MIT Press (1985).

Moggi, E.: The notion of computation and monads. Information And Computation 93:55–92 (1991).

Montague, R.: The proper treatment of quantification in ordinary English. In: Thomason, R. (ed.), Formal Philosophy: Selected Papers of Richard Montague. New Haven and London: Yale University Press, 247-271 (1974).

Mostowski, A.: On a generalization of quantifiers. Fundamenta Mathematicae 44, 12-36 (1957).

Szabolcsi, A.: Quantification. Cambridge University Press, Cambridge (2010).

Zawadowski, M.: Formalization of the feature system in terms of pre-orders. In Bellert, I, Feature System for Quantification Structures in Natural Language, Foris Dordrecht, 155-175 (1989).

[^1]: We think of Computation Trees by analogy with mathematical expressions, e.g. $$((2-7)-8)+((12+5):7)$$ that can be represented as

    i.e. a labeled binary tree where the leaves of this tree are labeled with values and the internal nodes are labeled with operations that will be applied in the computation to the values obtained from the computations of the left and right subtrees.

[^2]: Note that this is in contrast with the functor $\cP$, where $\cP$ is the covariant power-set functor.
