Next: , Previous: Types, Up: Compiler

4.4 Principles

Each dimension states which principles it uses, and their parameters. The principles are taken from the predefined principle library of the XDK. The principle library includes the definitions of the available principles. Developers can add new principles using the interface described in the developer sections.

To use a principle, you need to specify two mappings:

  1. the dimension mapping
  2. the argument mapping

4.4.1 Dimension mapping

The dimension mapping binds dimension variables to dimension identifiers. Each principle definition introduces a set of dimension variables which must be bound upon principle use. Lex and This are special dimension variables, always bound to dimensions lex and to the currently defined dimension, respectively.

4.4.2 Argument mapping

The argument mapping binds argument variables (or just arguments for short) to values. Each principle definition introduces a set of arguments, their types, and (optionally) their default values. Each argument which is not provided upon principle use gets its default value. If it does not have a default value, the XDK grammar file compiler raises an exception.

In the UL, the expression to use a principle is: 

     useprinciple <constant> {dims { <variable_1>:<constant_1>
                                     ...
                                     <variable_n>:<constant_n> }
                              args { <variable_1>:<term_1>
                                     ...
                                     <variable_m>:<term_m> }
                              }

Here, <constant> is the principle identifier. In the dims part, you specify the dimension mapping, and in the args part, you specify the argument mapping.

In the following, we give a set of example of how principles are used in our example grammar Grammars/Acl01.ul. Note that this manual contains detailed descriptions of all principles in the predefined principle library in Principles list.

4.4.3 Example (principle.graph)

Here is how the principle principle.graph is used on the id dimension of our example grammar file: 

       useprinciple "principle.graph" {
         dims {D: id}}

The identifier of the principle is principle.graph. The dimension mapping maps the dimension variable D to the dimension identifier id. The argument mapping is empty.

4.4.3.1 Graph principle

The principle.graph principle posits that the structure on the dimension bound to the dimension variable D is a graph1. It has no arguments.

In the example, the principle posits that the id dimension is a graph.

4.4.4 Example (principle.tree)

Here is how the principle principle.tree is used on the id dimension of our example grammar file: 

       useprinciple "principle.tree" {
         dims {D: id}}

The identifier of the principle is principle.tree. The dimension mapping maps the dimension variable D to the dimension identifier id. The argument mapping is empty.

4.4.4.1 Tree principle

The principle.tree principle posits that the structure on dimension D is a tree. The principle does not have any arguments.

In the example, the principle posits that the id dimension is a tree.

4.4.5 Example (principle.valency)

Here is how the principle principle.valency is used on the id dimension of our example grammar file: 

       useprinciple "principle.valency" {
         dims {D: id}
         args {In: _.D.entry.in
               Out: _.D.entry.out}}

The identifier of the principle is principle.valency. The dimension mapping maps the dimension variable D to the dimension identifier id. The argument mapping is empty.

4.4.5.1 Valency principle

The principle.valency principle constrains the incoming and outgoing edges of each node on dimension D. The In and Out arguments each specify a valency. The default values of the In and Out arguments are the feature paths _.D.entry.in and _.D.entry.out, respectively.

In the example, the values of the In and Out arguments are not provided, thus the grammar file compiler uses the default values _.D.entry.in and _.D.entry.out, respectively. That is, for each node v, In equals the the value of the field in of the entry of v on the id dimension, and Out equals the value of the field out of the entry of v.

4.4.5.2 Feature paths

Before we proceed, here is a short introduction of feature paths. Feature paths are used to access fields in the attributes or in the entry of a node. In the UL, the syntax for a feature path is: 

     <root var>.<dim var>.(attrs|entry).<field_1>.....<field_n>

Feature paths start with a root variable (<root var>) which states which node shall be accessed. The root variable is either “up” or “down” (in the UL, this corresponds to ^ or _). Each principle can bind “up” and “down” to arbitrary nodes. By convention, “up” means “mother”, and “down” means “daughter” (for constraints on edges), and “down” means “myself” (for constraints on nodes). As the valency principle states a constraint on nodes, the root variable _ in the example _.D.entry.out denotes “myself”.

The second argument of a feature path is a dimension variable (<dim var>) specifying the dimension of the value which is eventually accessed. In the example _.D.entry.out, the dimension variable is D.

The third argument of a feature path is one of the special constants attrs or entry. If you choose attrs, you access the attributes, and if you choose entry, you access the lexical entry. In the example _.D.entry.out, the lexical entry is accessed. Thus, the principle is lexicalized.

The fourth argument of a feature path is a list (separated by dots) of fields describing the path to the accessed value. In the example _.D.entry.out, the list consists only of the field out.

4.4.6 Example (principle.agr)

Here is how the principle principle.agr is used on the id dimension of our example grammar file: 

       useprinciple "principle.agr" {
         dims {D: id}
         args {Agr: _.D.attrs.agr
               Agrs: _.D.entry.agrs}}

The identifier of the principle is principle.agr. The dimension mapping maps the dimension variable D to the dimension identifier id. The argument mapping maps the argument Agr to the feature path _.D.attrs.agr, and Agrs to _.D.entry.agrs.

4.4.6.1 Agr principle

The principle.agr principle has the two arguments Agr and Agrs. The agr principle posits the constraint that for all nodes Agr is an element of Agrs.

The resulting constraint here is the following: for all nodes v, the value of the node attribute field agr is an element of the value of the lexical entry field agrs.

4.4.7 Example (principle.agreement)

Here is how the principle principle.agreement is used on the id dimension of our example grammar file: 

       useprinciple "principle.agreement" {
         dims {D: id}
         args {Agr1: ^.D.attrs.agr
               Agr2: _.D.entry.agr
               Agree: ^.D.entry.agree}}

The identifier of the principle is principle.agreement. The dimension mapping maps the dimension variable D to the dimension identifier id. The argument mapping maps the argument Agr1 to the feature path ^.D.attrs.agr, Agr2 to _.D.attrs.agr, and Agree to ^.D.entry.agree.

4.4.7.1 Agreement principle

The principle.agreement principle has the three arguments Agr1, Agr2 and Agree. It posits the constraint that for all edges from mother v to daughter v' labeled by l, if l is in the set described by Agree, Agr1 must equal Agr2.

In the example, this constraint amounts to the stipulation that for all edges from mother v to daughter v' labeled by l, if l is in the set lexically specified by the agree feature of the mother on the id dimension (feature path ^.D.entry.agree), then the node attribute agr must be equal for both the mother v (feature path ^.D.attrs.agr and the daughter v' (feature path _.D.attrs.agr.

4.4.8 Example (principle.government)

Here is how the principle principle.government is used on the id dimension of our example grammar file: 

       useprinciple "principle.government" {
         dims {D: id}
         args {Agr2: _.D.attrs.agr
               Govern: ^.D.entry.govern}}

The identifier of the principle is principle.agreement. The dimension mapping maps the dimension variable D to the dimension identifier id. The argument mapping maps the argument Agr2 to the feature path _.D.attrs.agr, and Govern to ^.D.entry.govern.

4.4.8.1 Government principle

The principle.government principle has the two arguments Agr2 and Government. It posits the constraint that for all edges from mother v to daughter v' labeled by l, Agr2 must be in the set prescribed by Govern for label l.

In the example, this constraint amounts to the stipulation that for all edges from mother v to daughter v' labeled by l, the value of the agr field of the node attributes of the daughter v' (feature path _.D.attrs.agr) must be in the set of labels prescribed by the field govern of the lexical entry of the mother v (feature path ^.D.entry.govern).

4.4.9 Example (principle.order)

Here is how the principle principle.order is used on the lp dimension of our example grammar file: 

       useprinciple "principle.order" {
         dims {D: lp}
         args {Order: [d df n mf vcf p pf v vxf]
               On: _.D.entry.on
               Yields: true}}

Here, the principle identifier is principle.order. The dimension mapping maps dimension variable D to dimension identifier lp. The argument mapping maps the argument Order to the list [d df n mf vcf p pf v vxf], On to the feature path _.D.entry.on, and Yields to true.

4.4.9.1 Order principle

The principle.order principle constrains the linear order of the nodes. In particular, it orders the yields or daughters of each node according to their edge label. The Order argument specifies a total order on a subset of the set of edge labels (as a list). The On argument specifies the set of possible node labels for each node used to position it with respect to its daughters. The domain of node labels is the same as the domain of edge labels. The Yields argument can be either true or false, depending on whether for each node, its entire subgraphs shall be ordered (true), or just its daughters (false). If the order principle is used in conjunction with the principle.projectivity, which is most frequently the case, then setting Yields to true is just an optimization for solving, but does not change the number of solutions.

The default value of the Order argument is the empty list. The default value of the On argument is the feature path _.D.entry.on. The default value of the Yields argument is false.

In the example, the total order on the set of edge labels is [d df n mf vcf p pf v vxf], i.e. all daughters with edge label (or the mother with node label) d precede all those with edge label df, and so on. The On argument is set to _.D.entry.on, i.e., for each node v, the set of possible node labels of v equals the value of the field on of the entry of v on the lp dimension. The Yields argument is set to true.

4.4.10 Example (principle.projectivity)

Here is how the principle principle.projectivity is used on the lp dimension of our example grammar file: 

       useprinciple "principle.projectivity" {
         dims {D: lp}}

Here, the principle identifier is principle.projectivity. The dimension mapping maps dimension variable D to dimension identifier lp. The argument mapping is empty.

4.4.10.1 Projectivity principle

The principle.projectivity principle constrains the analysis on the dimension D to be projective.

In the example, the principle is used on the lp dimension.

4.4.11 Example (principle.climbing)

Here is how the principle principle.climbing is used on the idlp dimension of our example grammar file: 

       useprinciple "principle.climbing" {
         dims {D1: lp
               D2: id}}

Here, the principle identifier is principle.climbing. The dimension mapping maps dimension variable D1 to dimension identifier lp, and dimension variable D2 to dimension id. The argument mapping is empty.

4.4.11.1 Climbing principle

The principle.climbing principle posits that the graph on dimension D1 must be flattening of the graph on dimension D2. It is called “climbing” since this flattening is the result of nodes “climbing up” metaphorically from the deep dimension D2 to the flat dimension D1. The principle introduces two arguments. The Subgraphs argument is either true or false, depending on whether each node is required to take its entire subgraph along when migrating upwards (true), or not (false). The MotherCards argument specifies whether for each node, the cardinalities of the sets of mothers on D1 and D2 must be equal (true), or not (false). This is an optimization for the case that both D1 and D2 are trees. If any of the two is not a tree, MotherCards should be set to false.

The default value of Subgraphs and MotherCards is true.

In the example, the principle posits that the graph on the lp dimension must be a flattening of the graph on the id dimension. By default, Subgraphs and MotherCards are set to true, i.e. each node must take its entire subgraph along when climbing up, and the cardinalities of its sets of mothers on the id and lp dimensions are equal.

4.4.12 Example (principle.barriers)

Here is how the principle principle.barriers is used on the idlp dimension of our example grammar file: 

        useprinciple "principle.barriers" {
         dims {D1: lp
               D2: id
               D3: idlp}}

Here, the principle identifier is principle.barriers. The dimension mapping maps dimension variable D1 to dimension identifier lp, D2 to dimension id and D3 to idlp. The argument mapping binds the argument variable Blocks to the feature path _.D3.entry.blocks.

4.4.12.1 Barriers principle

The principle.barriers principle is a specialization of the climbing principle. Its purpose is to “block” nodes in the “deep” dimension D2 from climbing up and appearing higher up in the “flat” dimension D1. The principle introduces an argument Blocks whose default value is _.D3.entry.blocks. The value of Blocks is a set edge labels on the “deep” dimension D2. For each node v, all nodes below v which have one of these incoming edge labels on the “deep” dimension D2 must stay below v on the “flat” dimension D1.

In the example, the “flat” dimension is the lp dimension, and the “deep” dimension is the id dimension. The value of the Blocks argument is lexicalized: for each node v, it equals the value of the blocks field of the entry of v on the idlp dimension.

4.4.13 Example (principle.linkingEnd)

Here is how the principle principle.linkingEnd is used on the idlp dimension of our example grammar file: 

        useprinciple "principle.linkingEnd" {
         dims {D1: lp
               D2: id}}

Here, the principle identifier is principle.linkingEnd. The dimension mapping maps dimension variable D1 to dimension identifier lp, and dimension variable D2 to dimension id. The argument mapping is empty.

4.4.13.1 LinkingEnd principle

The principle.linkingEnd principle constrains all outgoing edges from node v1 to node v2 labeled l on dimension D1 with respect to the incoming edge label l' of v2 on dimension D2. The principle introduces the argument End whose value is a function from the set of edge labels on D1 to sets of edge labels on D2. The default value of the End is ^.D3.entry.end.

An edge v1 to node v2 labeled l on dimension D1 is only licensed if the incoming edge label l' of v2 on dimension D2 is an element of the set specified by the applying the function in the End argument to label l.

In the example, the End argument is not provided. By default, it is lexicalized and equals for each node v_1 the value of the end field of the entry of v_1 on the idlp dimension.

4.4.14 Example (principle.entries)

Here is how the principle principle.entries is used on the lex dimension of our example grammar file: 

       %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%
       %% use principles
       useprinciple "principle.entries" {}

Here, the principle identifier is principle.entries. The dimension mapping is empty. The argument mapping is also empty.

4.4.14.1 Entries principle

The purpose of the principle.entries principle is to ensure that for each node, precisely one lexical entry is selected. If you do not use the entries principle, and there are two identical lexical entries for a word in the input, the XDK solver does not select one of the two. If you do use it, it does select one, i.e. it enumerates all possible lexical entries for a word in the input.

Footnotes

[1] Currently, the principle library includes two graph principles: principle.graph and principle.graph1. The latter leads to faster solving than the former, but it is cannot be used together with several principles of the principle library, and is thus quite obsolete.