A CCG -Based Version of the D is C o C at Framework (2021)

Abstract: While the DisCoCat model (Coecke et al., 2010) has been proved a valuable tool for studying compositional aspects of language at the level of semantics, its strong dependency on pregroup grammars poses important restrictions: first, it prevents large-scale experimentation due to the absence of a pregroup parser; and second, it limits the expressibility of the model to context-free grammars. In this paper we solve these problems by reformulating DisCoCat as a passage from Combinatory Categorial Grammar (CCG) to a category of semantics. We start by showing that standard categorial grammars can be expressed as a biclosed category, where all rules emerge as currying/uncurrying the identity; we then proceed to model permutation-inducing rules by exploiting the symmetry of the compact closed category encoding the word meaning. We provide a proof of concept for our method, converting “Alice in Wonderland” into DisCoCat form, a corpus that we make available to the community.

## introduction the compositional model of meaning by @xcite (from now on discocat 1 ) provides a conceptual way of modelling the interactions between the words in a sentence at the level of semantics. at the core of the model lies a passage from a grammatical derivation to a mathematical expression that computes a representation of the meaning of a sentence from the meanings of its words. in its most common form, this passage is expressed as a functor from a pregroup grammar @xcite to the category of finite-dimensional vector spaces and linear maps, fdvect, where the meanings of words live in the form of vectors and tensors (kartsaklis et al., 1 distributional compositional categorical. @xcite ). the job of the functor is to take a grammatical derivation and translate it into a linear-algebraic operation between tensors of various orders, while the composition function that returns the meaning of the sentence is tensor contraction. the particular choice of using a pregroup grammar as the domain of this functor is based on the fact that a pregroup, just like the semantics category on the right-hand side, has a compact-closed structure, which simplifies the transition considerably. however, while this link between pregroup grammars and discocat is well-motivated, it has also been proved stronger than desired, imposing some important restrictions on the framework. as a motivating example for this paper we mention the absence of any robust statistical pregroup parser (at the time of writing) that would provide the derivations for any large-scale discocat experiment on sentences of arbitrary grammatical forms. as up to the time of writing (11 years after the publication of the paper that introduced discocat), all experimental work related to the model is restricted to small datasets with sentences of simple fixed grammatical structures (e.g. subject-verb-object) that are provided to the system manually. furthermore, pregroup grammars have been proved to be weakly equivalent to context-free grammars @xcite , a degree of expressiveness that it is known to be not adequate for natural language; for example @xcite and @xcite have shown that certain syntactical constructions in dutch and swiss-german give rise to cross-serial dependencies and are beyond context-freeness. while in practice these cases are quite limited, it would still be linguistically interesting to have a version of discocat that is free of any restrictions with regard to its generative power. in this paper we overcome the above problems by detailing a version of discocat whose domain is combinatory categorial grammar (ccg) (steed- ## introduction to discocat based on the mathematical framework of compactclosed categories and inspired by the categorytheoretic formulation of quantum mechanics @xcite , the compositional distributional model of @xcite computes semantic representations of sentences by composing the semantic representations of the individual words. this computation is guided by the grammatical structure of the sentence, therefore at a higher level the model can be summarised as the following transition: ## related work implementations of the discocat model have been provided by @xcite and @xcite , while @xcite detail a version of the model based on density matrices for handling lexical ambiguity. discocat has been used extensively in conceptual tasks such as textual entailment at the level of sentences, see for example @xcite . further, exploiting the formal similarity of the model with quantum mechanics, @xcite and @xcite have used it recently with success for the first implementations of nlp models on nisq computers. the connection between categorial grammars and biclosed categories is long well-known @xcite , and discussed by @xcite . more related to discocat, and in an attempt to detach the model from pregroups, @xcite detail a passage from the original lambek calculus, formed as a biclosed category, to vector spaces. in @xcite can be found a first attempt to explicitly provide categorical semantics for ccg, in the context of a functor from a closed category augmented with swaps to fdvect. in that work, though, the addition of swaps introduces an infinite family of morphisms that collapse the category and lead to an overgenerating grammar. further, the actual mapping of crossed composition rules to the monoidal diagrams has flaws, as given in diagrammatic and symbolic forms -see footnote 5. we close this section by mentioning the work by @xcite , which describes how ccg derivations can be expressed directly as tensor operations in the context of discocat, building on @xcite . ## categorial grammars we start our exposition by providing a short introduction to categorial grammars. a categorial grammar @xcite is a grammatical formalism based on the assumption that certain syntactic constituents are functions applied on lower-order arguments. for example, an intransitive verb gets the type s\np, denoting that this kind of verb is a function that expects a noun phrase on the left in order to return a sentence, while a determiner has type np/n -a function that expects a noun on the right to return a noun phrase. the direction of the slash determines the exact position of the argument with regard to the word that represents the function. in the following derivation for the sentence "alice likes bob", the noun phrases and the transitive verb are assigned types np and (s\np)/np respectively. as the diagram shows, a term with type x/y takes a term of type y on the right in order to return a term of type x. similarly, a term with type x\y takes a term of type y on the left, in order to return a term of type x. in this paper we adopt a slightly different and hopefully more intuitive notation for categorial types: x/y becomes x y while for x\y we will use y x. using the new notation, the above diagram takes the form shown in figure 1 . the two rules described above are called forward and backward application, respectively, and formally can be defined as below: categorial grammars restricted to application rules are known as basic categorial grammars (bcg) @xcite , and have been proved to be equivalent to context-free grammars @xcite and pregroup grammars @xcite . interestingly, although all grammars mentioned above are equivalent in terms of theoretical expressiveness, bcgs are restrictive on the order of the reductions in a sentence. in the derivation of figure 1 , we see for example that a transitive verb must always first compose with its object, and then with the subject. to address this problem, some categorial grammars (including ccg) contain type-raising and composition rules which, although they do not affect grammar's theoretical power, allow some additional flexibility in the order of composition. these rules can be seen of as a form of currying, and are discussed in more depth in section 6. in figure 2 we see how type-raising (t) and composition (b) can be used to change the order of reductions in our example sentence, in a version that the verb is first composed with the subject and then with the object. finally, in ccg composition has also a generalized version, where additional arguments (denoted below as $ 1 ) are allowed to the right of the z category. the rule can be seen as "ignoring the brackets" in the right-hand type: the generalized composition rules have special significance, since it is argued to be the reason for the beyond context-free generative capacity of ccg -see for example @xcite . ## categorial grammars as biclosed categories categorial grammars can be seen as a proof system, and form a biclosed category b whose objects are the categorial types while the arrows @xmath0. a word with categorial type x lives in this category as an axiom, that is, as an arrow of type @xmath1. below we show the biclosed diagram for the ccg derivation of the sentence "alice likes bob": we remind the reader that a biclosed category is both left-closed and right-closed, meaning that it is equipped with the following two isomorphisms: a key observation for the work in this paper is that all basic categorial rules exist naturally in any biclosed category and can emerge solely by currying and uncurrying identity morphisms; this is shown in figure 3 . hence any ccg derivation using the rules we have met so far foot_1 exists in a biclosed category freely generated over atomic types and word arrows. ## from biclosed to compact-closed we will now define a monoidal functor from a grammar expressed as a biclosed category to dis-cocat diagrams. discocat diagrams exist in a compact-closed category c, where every object is left-and right-dualisable and the left and right internal hom-objects between objects x and y are isomorphic to x r ⊗ y and y ⊗ x l respectively. thus we can directly define the left and right currying isomorphisms using the dual objects: which allows us to functorially convert all categorial grammar rules into string diagrams, as in figure 4 . definition 6.1. f is a closed monoidal functor from the biclosed category b of ccg derivations to the compact-closed category c of discocat diagrams. let {np, s, pp} be a set of atomic ccg types, indicating a noun phrase, a sentence, and a prepositional phrase, respectively, and t a lexical type. we define the following mapping: as a closed monoidal functor, f : @xmath2: as an example, below you can see how the backward application rule, derived by uncurrying an identity morphism, is converted into a string diagram in c. one advantage of representing parse trees using compact-closed categories over biclosed categories and categorial grammars is that the rewriting rules of string diagrams enable us to show more clearly the equivalence between two parse trees. take for example the phrase "big bad wolf", which in biclosed form has two different derivations: however, when these derivations are sent to a compact-closed category, they become equivalent to the following diagram which is agnostic with regard to composition order: another example of this is in the use of the typeraising rule in ccg, which is analogous to expansion in pregroups, and in discocat can be represented using a "cap" (∩). therefore, the derivations in figures 1 and 2 , when expressed as discocat diagrams, are equal up to planar isotopy (figure 5 ). ## crossed composition all rules we have met so far are order-preserving, in the sense that they expect all words or textual constituents in a sentence to be found at their canonical positions. this is not always the case though, since language can be also used quite informally. to handle those cases without introducing additional types per word, ccg is equipped with the rule of crossed composition @xcite , the definition of which is the following: in biclosed form, the crossed composition rules are expressed as below: crossed composition comes also in a generalized form as the standard (or harmonic) composition, and allows treatment of cross-serial dependencies, similar to those met in dutch and swiss-german (figure 6 ). in english the rule is used in a restricted form foot_2 , mainly to allow a certain degree of word associativity and permutativity when this is required. for example, such a case is heavy np-shift, where the adverb comes between the verb and its direct object @xcite . consider the sentence "john passed successfully his exam", the ccg derivation of which is shown below: note that the rule introduces a crossing between the involved types, which is not representable in pregroups. however, we remind the reader that the compact closed category where the discocat diagrams live is a symmetric monoidal category, which means that for any two objects a and b it holds that a ⊗ b ∼ = b ⊗ a. in diagrammatic form this corresponds to a swap of the wires, as below: in the case of fdvect, the state above would correspond to a matrix @xmath3, while its swap (b) is nothing more than the transposition of that matrix, m t . thus, by exploiting the symmetry of the semantics category, the discocat diagrams for the two crossed composition rules take the form shown in figure 7 . we are now in position to revisit the functorial passage described in section 6 in order to include crossed composition. in contrast to other categorial rules, crossed composition does not occur naturally in a biclosed setting, so we have to explicitly add the corresponding boxes in the generating set of category b, which is the domain of our functor. the mapping of these special boxes to compactclosed diagrams is defined in figure 7 . deriving 5 the idea of representing crossing rules using swaps also appears in @xcite ; however the mapping provided there is incorrect, since there is a swap clearly missing before the last evaluation in the monoidal diagrams (p. 142, fig. 7 .7) as well as from the symbolic representations of the morphisms (p. 145). the generalized versions of the rules in biclosed and compact-closed form similarly to the harmonic cases is a straightforward exercise. based on the above, our np-shift case gets the following diagrammatic representation: interestingly, this diagram can be made planar by relocating the state of the object in its canonical (from a grammar perspective) position: we would like to close this section with a comment on the presence of swaps in the discocat category, and what exactly the implications of this are. obviously, an unrestricted use of swaps in the semantics category would allow every possible arbitrary permutation of the words, resulting in an overgenerating model that is useless for any practical application. however, as explained in section 2, discocat is not a grammar, but a mapping from a grammar to a semantics. hence it is always responsibility of the grammar to pose certain restrictions in how the semantic form is generated. in the formulation we detailed in sections 6 and 7, we have carefully defined a biclosed category as to not introduce extra morphisms to ccg, and a functor that maps to a subcategory of a compact-closed category such that the rigid structure of traditional discocat is preserved. ## putting everything together at this point we have the means to represent as a discocat diagram every sentence in english language. in the following example, we consider a derivation that includes type-raising, harmonic composition, and crossed composition: bruce puts on his hat np (np s) np (np s) (np s) @xmath4 the corresponding discocat diagram is given below: on bruce put as before, relocating the object and yanking the wires produces a planar version of the diagram: on bruce put ## adhering to planarity we have seen in sections 7 and 8 how diagrams for sentences that feature crossed composition can be rearranged to equivalent diagrams that show a planar derivation. it is in fact always possible to rearrange the diagram of a derivation containing crossed composition into a planar diagram, since every instance of crossed composition between two subtrees α and β is subject to the following transformation: by performing this rearrangement recursively on the subtrees, we obtain a planar monoidal diagram for the whole derivation. for example, a sentence containing a phrasal verb gets the following diagram: note how the two constituents of the phrasal verb are grouped together in a single state with type n r • s • n l , forming a proper transitive verb, and how the diagram is planar by construction without the need of any rearrangement. being able to express the diagrams without swaps is not only linguistically interesting, but also computationally advantageous. as mentioned before, on classical hardware swaps correspond to transpositions of usually large tensors; on quantum hardware, since a decomposition of a swap gate contains entangling gates, by reducing the number of swaps in a diagram we reduce the currently expensive entangling gates (such as cnots) required to synthesise the diagram. ## a discocat version of "alice in wonderland" we demonstrate the theory of this paper by converting lewis carroll's "alice in wonderland" foot_4 in discocat form. our experiment is based on the following steps: the depccg parser failed to parse 18 of the 3059 total sentences in the book, resulting in a set of 3041 valid ccg derivations, all of which were successfully converted into discocat diagrams based on the methodology of this paper. the new corpus is now publicly available to further facilitate research in discocat foot_6 , and is provided in three formats: biclosed, monoidal, and discocat, while pdf versions of the diagrams are also available. for the representation of the diagrams we used dis-copy foot_7 (de felice et al., 2020), a python library for working with monoidal categories. further, a web tool that allows the conversion of any sentence to discocat diagram providing various configuration and output options, including l a t e x code for rendering the diagram in a l a t e x document, is available at cqc's website foot_8 . in the appendix we show the first few paragraphs of the book in discocat form by using this option. ## some practical considerations for the sake of a self-contained manuscript, in this section we discuss a few important technicalities related to ccg parsers that cannot be covered by the theory. the most important is the concept of unary rules, where a type is changed in an ad-hoc way at some point of the derivation in order to make an outcome possible. in the following ccg diagram, we see unary rules (u) changing np s to np np and n to np at a later point of the derivation. we address this problem by employing an indexing system that links the categorial types with their corresponding arguments in a way that is always possible to traverse the tree backwards and make appropriate replacements when a unary rule is met. for the above example, we get: finally, we discuss conjunctions, which in ccg parsers take the special type conj. we essentially treat these cases as unary rules, constructing the destination type by the types of the two conjuncts: in this paper we showed how ccg derivations can be expressed in discocat, paving the way for largescale applications of the model. in fact, presenting a large-scale experiment based on discocat is a natural next step and one of our goals for the near future. creating more discocat-related resources, similar to the corpus introduced in this paper, is an important direction with obvious benefits to the community.