L in PP : a Python-friendly algorithm for Linear Pregroup Parsing (2021)

Abstract: We define a linear pregroup parser, by applying some key modifications to the minimal parser defined in (Preller, 2007). These include handling words as separate blocks, and thus respecting their syntactic role in the sentence. We prove correctness of our algorithm with respect to parsing sentences in a subclass of pregroup grammars. The algorithm was specifically designed for a seamless implementation in Python. This facilitates its integration within the DisCopy module for QNLP and vastly increases the applicability of pregroup grammars to parsing real-world text data.

## introduction pregroup grammars (pg), firstly introduced by j. lambek in @xcite , are becoming popular tools for modelling syntactic structures of natural language. in compositional models of meaning, such as discocat @xcite and disco-circ @xcite , grammatical composition is used to build sentence meanings from words meanings. pregroup types mediate this composition by indicating how words connect to each other, according to their grammatical role in the sentence. in discocat compositional sentence embeddings are represented diagrammatically; these are used as a language model for qnlp, by translating diagrams into quantum circuits via the z-x formalism @xcite @xcite . discopy, a python implementation of most elements of discocat, is due to giovanni defelice, alexis toumi and bob coecke @xcite ). an essential ingredient for a full implementation of the discocat model, as well as any syntactic model based on pregroups, is a correct and efficient pregroup parser. pregroup grammars are weakly equivalent to context-free grammars @xcite . thus, general pregroup parsers based on this equivalence are poly-time, see e.g. @xcite . examples of cubic pregroup parsers exist by preller @xcite and @xcite . the latter have been implemented in python and java. a faster minimal parsing algorithm, with linear computational time, was theorised by anne preller in @xcite . this parser is correct for the subclass of pregroup grammars characterised by guarded dictionaries. the notion of guarded is defined by preller to identify dictionaries, whose criticalities satisfy certain properties @xcite . in this paper we define linpp, a new linear pregroup parser, obtained generalising preller's definition of guards and applying some key modifications to the minimal parsing algorithm. linpp was specifically designed with the aim of a python implementation. such implementation is currently being integrated in the discopy package (github:oxford-quantum-group/discopy). the need for a linear pregroup parser originated from the goal of constructing a grammar inference machine learning model for pregroup types, i.e. a pregroup tagger. training and evaluation of such model is likely to involve parsing of several thousand sentences. thus, linpp will positively affect the overall efficiency and performance of the tagger. the tagger will enable us to process real world data and test the discocat pregroup model against the state-of-the-art with respect to extensive tasks involving real-world language data. ## pregroup grammars we recall the concepts of monoid, preordered monoid and pregroup. definition 2.1. a monoid p, •, 1 is a set p together with binary operation • and an element 1, such that for any x, @xmath0. we refer to • as monoidal product, and we often omit it, by simply writing xy in place of of x • y. definition 2.2. a preordered monoid is a monoid together with a reflexive transitive relation @xmath1: definition 2.3. a pregroup is a preordered monoid p, •, 1 , in which every object x has a left and a right adjoint, respectively written as x l and x r , such that: adjoints are unique for each object. in the context of natural language, pregroups are used to model grammatical types. this approach was pioneered by j. lambek, who introduced the notion of pregroup grammars @xcite . these grammars are constructed over a set of basic types, which represent basic grammatical roles. for example, {n, s} is a set consisting of the noun type and the sentence type. definition 2.4. let b be a set of basic types. the free pregroup over b, written p b , is the free pregroup generated by the set b ∪ σ, where σ is the set of iterated adjonts of the types in b. in order to easily write iterated adjoints, we define the following notation. definition 2.5. given a basic type t, we write t l n to indicate its n-fold left adjoint, and t r n for its n-fold right adjoint.e.g. we write t l 2 to indicate (t l ) l . thanks to the uniqueness of pregroup adjoints we can mix the right and left notation. e.g. (t r 2 ) l is simply t r . we write t l 0 = @xmath2. we now define pregroup grammars, following the notation of @xcite . definition 2.6. a pregroup grammar is a tuple p @xmath3, b, d, p b , s} where: example 2.7. consider the grammar given by @xmath4, loves, bob}, @xmath5, s} and a dictionary with the following type assignments: note that the grammatical types for alice and bob are so-called simple types, i.e basic types or their adjoints. on the other hand, the type of the transitive verb is a monoidal product. the type of this verb encodes the recipe for creating a sentence: it says give me a noun type on the left and a noun type on the right and i will output a sentence type. in other words, by applying iterated contraction rules on nn r sn l n we obtain the type s. diagrammatically we represent the string as then, after applying the contraction rules, we obtain a sentence diagram: this diagram is used to embed the sentence meaning. this framework -introduced by coecke et al. in 2010 -is referred to as discocat and provides a mean to equip distributional semantics with compositionality. the composition is mediated by the sentence's pregroup contractions, as seen in the example above. @xcite . the iterated application of contraction rules yields a reduction. definition 2.8. let s := t 1 ....t n be a string of simple types, and let t s := t j 1 ....t jp with j @xmath6, n] for all i. we say that r : @xmath7. we say that t s is a reduced form of s. if t s cannot be contracted any further, we say that it is irreducible and we often write r : @xmath8. note that neither reductions nor irreducible forms are unique, as often we are presented with different options on where to apply contraction rules. in the context of pregroup grammars, we are interested in reducing strings to the sentence type s, whenever this is possible. thus, we give such reduction a special name @xcite ): definition 2.9. a reduction r : @xmath9, if t s is the simple type s. a string s is a sentence if there exists a parsing. often, we want to keep track of the types as they get parsed: definition 2.10. the set of reductions of r : @xmath10, j} such that t i t j is the domain of a contraction in r. these pairs are referred to as underlinks, or links @xcite . ## linear vs critical we now discuss critical and linear types in a pregroup grammar. we first need to introduce the notion of complexity @xcite , definition 5) @xcite . definition 3.1. a pregoup grammar with dictionary d has complexity k if, for every type @xmath11, any left (right complexity 1 indicates a trivial grammar that contains only basic types (no adjoints). complexity 2 allows for dictionaries containing at most basic types and their 1-fold left and right adjoints, e.g. n l and n r . as proven in @xcite , every pregroup grammar is strongly equivalent to a pregroup grammar with complexity 2. this means that the subclass of complexity 2 pregroup grammars has the same expressive power of the whole class of pregroup grammars. we now introduce critical types @xcite . definition 3.2. a type c is critical, if there exists types a, @xmath12. a type is linear if it is not critical. we say that a grammar is linear if all types in the dictionary are linear types. given a string from a linear grammar, its reduction links are unique @xcite . in fact, a very simple algorithm can be used to determine whether a linear string is a sentence or not. ## m inp p : minimal parsing algorithm in this section we define m inip p , a minimal parsing algorithm complexity 2 pregroup grammars. minpp pseudo-code. let sentence : t 1 ....t m be a string of types from a dictionary with complexity 2. we associate each processing step of the algorithm with a stage s n . let s 0 be the initial stage, and s n := {a, n} with @xmath13. let r n and st n be respectively the set of reductions and the reduced stack at stage s n . let us write (st n ) for the function returning the top element of the stack at stage n and pop(st n ) for the function popping the stack. the steps of the algorithms are defined as follows. at stage s 0 , we have r 0 = ∅ and st 0 = ∅. at stage s 1 , r 1 = ∅ and st 1 = t 1 . at stages s n , @xmath14, let t @xmath15. we define the following cases. ## linp p : linear pregroup parsing algorithm certain words are typically assigned compound types by the dictionary, e.g. t := n r sn l for transitive verbs. it might be the case that a compound type t w of a word w , is not irreducible. both m inp p and the parsers mentioned in the introduction will read types in t w and reduce t w to an irreducible form. however, the main purpose of grammatical pregroup types is to tell us how to connect different words. reducing words internally defeats this purpose. we want to overcome this limitation and construct an algorithm that ignores intra-word reductions. given a word w 1 let t 1 be its corresponding type (simple or compound). in m inp p we defined stages s n corresponding to each simple type t n being read. let us write z 1 for the super stage corresponding to word w 1 being read. z 1 contains one or more s n corresponding to each simple type in t 1 . we modify m inp p as follows. in other words, linp p follows the same computational steps of m inp p , while only checking reductions between types of separate words. by assuming dictionaries whose sentences do not involve intra-word reductions, the above proof of correctness can be adapted to hold for linp p . modifications are trivial. we previously highlighted the importance of a linear parser; up to this point linp p computes parsing in quadratic time. below we impose some further restrictions on the input data, which enable linear computational time. definition 5.1. we say that a dictionary of complexity 2 is critically bounded if, given a constant @xmath16, for each critical type t c in a string, exactly one of the following is true: in other words, critical underlinks cannot exceed lenght k. lemma 5.2. assume the restrictions of section 4.1, no-intra word reductions, and critically bounded dictionaries. then linp p parses strings in linear computational time. proof. assume a string of length n . linp p forward processing involves reading each type at most once. thus it happens at most in time dn , with d as in section 4.1. moreover, when a critical fan is read, the string is parsed backward, reading at most k types. this process takes dk time per critical fan. thus it takes overall times dkn . finally there is an extra linear term, cn , given by the time spent to correct the stack and reduction set. summing up those terms, we obtain overall computational time cn , with @xmath17. ## conclusion in this paper we first defined a quadratic pregroup parser, m inp p , inspired by preller's minimal parser. we proved its correctness with respect to reducing strings to irreducible forms, and in particular to parse sentences to the sentence type, in the class of pregroup grammar charactorised by complexity 2 and guarded critical types. note that our definition of guards differs from the one given in @xcite . we then modified m inp p in order to remove intra-words links. we proved that the obtained algorithm, linp p , is linear, given that the dictionaries are critically bounded. linp p was implemented in python and it's soon to be integrated in the discopy package. the reader can find it at github:oxford-quantum-group/discopy. linp p is an important step towards the implementation of a supervised pregroup tagger, which will enable extensive testing of the discocat model on task involving larger data-sets. future theoretical work and implementations will involve researching a probabilistic pregroup parser based on linp p . future work might also involve investigation the connection between pregroup parsers and compositional dynamical networks.