AVM Description Compilation using Types as Modes

AVM Description Compilation using Types as Modes Gerald Penn Department of Computer Science University of Toronto gpenn@cs.toronto.edu Abstract This paper provides a method for generat- ing compact and efficient code to imple- ment the enforcement of a description in typed feature logic. It does so by view- ing information about types through the course of code generation as modes of in- stantiation — a generalization of the com- mon practice in logic programming of the hi nary instantiated/variable mode decl ara- tions that advanced Prolog compilers use. Section 1 introduces the description lan- guage. Sections 2 and 3 motivate the view of mode and compilation taken here, and outline a mode declaration language for typed feature logic. Sections 4 through 7 then present the compiler. An evaluation on two grammars is presented at the end. 1 Descriptions The logic of typed feature structures (Carpenter, 1992) has been widely used as a means of formal- izing and developing natural language grammars, notably in Head-driven Phrase Structure Gram- mar (Pollard and Sag, 1994). These grammars are stated using a vocabulary consisting of a fi- nite meet semi-lattice of types and a set of fea- tures that must be specified for each grammar, and this vocabulary must obey certain rules. A set of appropriateness conditions must specify, for each feature, which types of feature structures may bear it, and which types of values it may take. Unique feature introduction states that every feature has a least type that bears it, called its introducer. The effect of these rules is that typed feature structures (TFSs) can be described using a very terse descrip- tion language. A TFS that matches the description NUMBER : singular, for example, might implic- itly be of a type index, which introduces NUMBER. From that, we can deduce that the TFS also bears values for PERSON and GENDER, with particular appropriate values, because those features are in- troduced by the same type. Terse descriptions al- low us to work with very large TFSs conveniently. Given this basic vocabulary, descriptions can be used in implicational constraints that encode prin- ciples of grammar. These are often restricted to the form T 0, where T is a type, and 0 is a description. They also appear in several control strategies that are used to combine TFSs, such as extended phrase structure rules for parsing or gen- eration (Wintner, 1997; Malouf et al., 2000), or resolution with a Prolog-like relational language (Carpenter and Penn, 1996; Makino et al., 1998). While description languages vary, they are usu- ally restricted to a subset of the following: Definition: The set of descriptions over a count- able set of types, T, a finite set of features, Feat, and a countable set of variables, Var, is the small- est set Desc that contains: • Var, • zX,allX E Var, • T, • •7F : ch, all 71 E Feat * , 0 E Desc, and A V), V 11), all 0,'O E Desc. Variables are used to enforce sharing …

Content truncated to 500 words