The Calculation of Treebank Semantics

Alastair Butler

Hirosaki University


Treebank Semantics is an implemented grammar system that converts syntactic analysis into the structures of a formal language which is then processed against a locally constrained global calculation. Outputs of the calculation are logic based meaning representations. The calculation makes reference to a changing information state that manages the availability of collected discourse referents over a discourse. This information state holds content to resolve aspects of expression interpretation, including antecedent accessibility for pronouns, and most pervasively, valency for predicates. This paper describes the approach in detail using definitions that are executable code for Prolog systems.

1   The Approach

The approach starts with syntactically analysed input realised as ‘normalised input’. Reaching normalised input can in principle be carried out for any language starting from data in any syntactic annotation format, provided there is enough information about word class, constituency, argumenthood, modification, and anaphoric relations to discharge the requirements of lexical elements and reflect the roles of functional elements.

    Having normalised input, the idea of the approach is that sentence and discourse meaning is in the structure of the input, and that we can reach, by undertaking transformations between representations that capture the structure, alternative instantiations of the structure that can be more explicit articulations of meaning components and their comprising dependencies.

    The normalised input will be transformed into expressions of a logical language, comprised of: closure operators, discourse referents, predicate relations, and logical connectives. A logical expression is reached by undertaking a recursive calculation that receives input coded as a Prolog term. We will refer to this recursive calculation as the ‘semantic calculation’.

    The semantic calculation makes two passes over the input. The first pass collects ‘discourse referents’. Discourse referents are destined to act as either logical variables or constants of an overall resulting logical expression. As a logical variable, a discourse referent is bound by an operation of quantifier closure. Operations of closure are themselves either reflexes of quantification instructions from the input, or arise because there is discourse closure.

    During the second pass over the input, the discourse referents collected from the first pass are released as content for argument slots of predicates that populate the resulting logical expression. The exact makeup of argument slots (valencies) for a given predicate can be left unspecified by the input. At the point in the calculation when the predicate is reached, the availability of discourse referents is established. The predicate's sensitivity to what is available as a potential binding determines the arguments for the predicate.

    If the logical expression derived from a given sentence or discourse annotation corresponds to the original interpretation, then this is one kind of confirmation that the structure assigned is correct. You can see how the generation of a well-formed (and accurate) logical expression can actually be a driving principle for the creation of the initial input.

    With the sketched setup comes an emergence of a notion of ‘grammar’ as a guidance for ensuring discourse referents are accessible when they need to be and inaccessible when they should not be available. It then becomes possible for the semantic calculation as guidance system to determine how a word or construction in a certain environment will behave. But also a word or construction might have its properties sufficiently specified so as to place very clear demands on the state of the environment in which it is able to occur. Grammaticality effects arise with the possibility of a clash between the discourse referents given by the state of the calculation, and the discourse referents that need to be present and absent from the calculation state to meet the requirements for the expression that is under calculation.

    Exactly how discourse referents are released gives the kernel of the approach. Over spans of discourse, this amounts to an implementation of ‘accessibility’ from Dynamic Semantics. This implementation generalises the approach taken by the system of Predicate Logic with Anaphora (PLA; Dekker 2002, 2012), with an updated version of the formal language of Scope Control Theory (SCT; Butler 2007, 2010, 2015) as an intermediate component.

    Besides PLA and SCT, there are many other ways to achieve the relevant notion of accessibility, as found in the diverse range of systems that fall under the Dynamic Semantics umbrella, including: Discourse Representation Theory (DRT; Kamp and Reyle 1993), File Change Semantics (FCS; Heim 1982), Dynamic Predicate Logic (DPL; Groenendijk and Stokhof 1991), the DRT formulation in Zeevat (1989), Sequence Semantics (Vermeulen 1993), Compositional DRT (Muskens 1996), Incremental Dynamics (van-Eijck 2001), the translation system from DPL to a static first order language in Cresswell (2002), the DRT formulation with lambdas in Bos (2005), and Dependent Type Semantics (DTS; Yana, Mineshima and Bekki 2019).

    The standout virtue of the current approach over its alternatives is its nature of self-regulation that enables the system to calculate results from a minimum of explicit lexical input. This holds not only at the level of discourse accessibility but also feeds through to controlling the (un)availability of bindings for expression internal layers. The ability to handle subordinating dependencies involving pronouns in a manner that is uniform to the treatment of coordinating dependencies is also a notable extension over typical capabilities of systems of Dynamic Semantics.

1.1   Overview

Section 2 introduces Prolog terms that offer a level of syntactic annotation where language particulars are regularised to provide a common interface to enable further processing. This includes information about ‘fresh’ and ‘local’ parameters and integration of ‘discourse referents’ into the resulting structures. Once reached, <normalised_expr> terms are themselves processed to create expressions of the Scope Control Theory (SCT) language (<sct_expr> terms) introduced in section 3. Prolog statements that assist reaching <sct_expr> terms from <normalised_expr> terms are detailed in section 4. The transformation routine from <normalised_expr> terms to <sct_expr> terms is presented in section 5. The <sct_expr> language has a reduced inventory of Prolog structures on which the semantic calculation mechanism described in section 6 will directly operate. The semantic calculation transforms expressions into a discourse representation language (<drs_expr> terms). During this calculation, information about the allocation of accessible discourse referents is established. Such output analysis makes explicit connective, predicate, argument, and operator-binding information.

1.2   About the Prolog definitions

This section contains background for reading the definitions that are executable code for Prolog systems. The single data type of Prolog is the term. Terms are either: atoms, numbers, variables, or compound terms (structures).

1.2.1   Atoms

An atom is a general-purpose name with no inherent meaning. Atoms are usually bare words (character sequences) written with no special syntax. However, if spaces or certain other special characters (e.g. punctuation characters) are contained, then the atom must be surrounded by single quotes. Atoms beginning with a capital letter must also be quoted, to distinguish them from variables. The empty list, written [], is also an atom. Other examples of atoms include: foo, 'Bar', and 'foo bar'.

    As a built-in predicate, atom/1 tests whether its argument is an atom. For example:

| ?- atom(foo).


atom_codes/2 performs a conversion between an atom and its character list representation. For example:

| ?- atom_codes(foo, L).

L = [102,111,111];

| ?- atom_codes(A, [102,111,111]).

A = foo;


atom_concat/3 allows concatenation and splitting of atoms. For example:

| ?- atom_concat(foo, bar, A).

A = foobar;


sub_atom/5 allows for the enumeration of sub-atoms with their position and length. For example:

| ?- sub_atom('darg1', Before, Length, After, 'arg1').

Before = 1
Length = 4
After = 0;


Before is the number of characters before the sub-atom, Length is the number of characters that make up the sub-atom, and After is the number of characters that come after the sub-atom. In find_with_sub_atom/4 of (5), a successful call of sub_atom/5 provides the basis of a filter that retains atoms of an input list because they contain a given sub-atom.

find_with_sub_atom( _, [], L, L ).
find_with_sub_atom( A, [H|T0], L, [H|T] ) :-
  sub_atom( H, _, _, _, A ),
  find_with_sub_atom( A, T0, L, T ).
find_with_sub_atom( A, [_|T0], L, T ) :-
  find_with_sub_atom( A, T0, L, T ).

1.2.2   Numbers

Numbers can be integers or real numbers. The predefined infix operator is/2 unifies the first argument to the calculated number of the second argument. For example:

| ?- X is 2 + 1.

X = 3;


1.2.3   Variables

Variables are denoted by a string consisting of letters, numbers and underscore characters, and beginning with an upper-case letter or underscore. Variables closely resemble variables in logic in that they are placeholders for arbitrary terms. A variable can become instantiated (bound to equal a specific term) via unification. A single underscore (_) denotes an anonymous variable and means ‘any term’. Unlike other variables, the underscore does not represent the same value everywhere it occurs within a predicate definition.

    As a built-in predicate, var/1 tests whether its argument is a variable. For example:

| ?- var(X).

X = _h328;


1.2.4   Compound terms

A compound term is composed of an atom called a ‘functor’ and a number of ‘arguments’, which are again terms. Compound terms are ordinarily written as a functor followed by a comma-separated list of argument terms, which is contained in parentheses. The number of arguments is called the term's arity. The notation f/n is used to denote a term with functor f and arity n. Examples of compound terms are: t('arg0') and pred('', []). An atom can be regarded as a compound term with arity zero.

1.2.5   Term equivalence

Now we have some idea about what terms are, we can consider ways to relate terms. '=='/2 is a predefined infix operator that tests whether its arguments are equivalent terms. For example:

| ?- x == x.

| ?- X == x.

| ?- X = x, X == x.

X = x;


Notably, the latter equivalence test succeeds because of the prior instantiation of the variable X to the atom x.

    '\=='/2 is a predefined infix operator that tests whether its arguments are different terms.

1.2.6   Lists

Lists are a special case of compound terms. Constructors for lists are the atom [] (empty list) and the functor '.'/2, where the first argument is a term and the second argument a list. A list of N elements is the term .(a1, .( ... .(aN, []) ... )), which may also be written with square bracket notation: [a1, ..., aN]. List construction is also possible with a concatenation function ‘[_|_]/2’: [a1, ..., aN|t] is the term .(a1, .( ... .(aN, t))). With the concatenation function, a list can be processed by processing the first element(s), and then the rest of the list, in a recursive manner.

    Prolog definitions in this paper will make use of the following list manipulation predicates:

1.2.7   Incomplete lists and difference lists

Incomplete lists are a special type of list structure. Instead of ending in [], an incomplete list has a free variable as its tail. For example, L of (9) is such a structure.

| ?- L = [a,b,c|_].

L = [a,b,c|_h383];


The free variable at the end of an incomplete list can be (partially) instantiated, as (10) illustrates.

| ?- L = [1,2,3|T], T = [4,5|U].

L = [1,2,3,4,5|_h463]
T = [4,5|_h463]
U = _h463;


    A notable use for incomplete lists is as the first component of a difference list. With X as the end variable of an incomplete list, a difference list is a construct of the form [a1, ..., aN|X]-X that represents the list [a1, ..., aN]. This makes possible the efficient (constant time) method of list concatenation seen with (10) without needing to keep track of the end variables. Consider two difference lists [a1, ..., aN|X]-X and [b1, ..., bM|Y]-Y. Then their concatenation is the difference list [a1, ..., aN,b1, ..., bM|Y]-Y. This concatenation is achieved, e.g., with the single clause program of (11).

concat(X-Y, Y-Z, X-Z).

With (11), the query of (12) can be made:

| ?- concat([a,b|X]-X, [c,d|Y]-Y, U).

X = [c,d|_h443]
Y = _h443
U = [a,b,c,d|_h443] - _h443;


Here, U is instantiated to the difference list representing the list [a,b,c,d]. Instantiating the “output” argument to V-[] obtains the outcome list directly through V:

| ?- concat([a,b|X]-X, [c,d|Y]-Y, V-[]).

X = [c,d]
Y = []
V = [a,b,c,d];


1.2.8   More manipulations of incomplete lists

Incomplete lists can be traversed in the same way as complete lists, using the [H|T] pattern. However, should the end be reached, there is a free variable that will unify with anything, and so, to avoid undesired unifications, it is essential to first test for whether the end variable is reached, e.g., with: some_predicate(L, ...) :- var(L), ....

    To calculate the length of an incomplete list, we can traverse the input list element by element, incrementing a count as we go, and return the count when the end is found.

length_il(List, Length) :-                 % use auxiliary predicate ...
  length_il_acc(List, 0, Length).          % ... with count initialised to zero

length_il_acc(L, N0, N) :- var(L), !, N = N0.               % reached end, stop
length_il_acc([_|L], N, Length) :-
  N1 is N+1,
  length_il_acc(L, N1, Length).

For example:

| ?- length_il([a,b,c|_], N).

N = 3;


    A notable manipulation concerns gaining access to the last element of an incomplete list, which is the element that is just prior to the end variable for the incomplete list. This will be accomplished with last_il(Input, Output, Last), where Input is an incomplete list, Output is identical to Input, only with the last element removed, and Last is the last element of Input that is removed to create Output.

last_il([X|Xs], Ys, Z) :-                   % use auxiliary predicate ...
  last_il_lag(Xs, Ys, X, Z).                % ... which lags behind by one item

last_il_lag(X0, X, Z0, Z) :- var(X0), !, X = X0, Z = Z0.    % reached end, stop
last_il_lag([X1|Xs], [X0|Ys], X0, Z) :-
  last_il_lag(Xs, Ys, X1, Z).                               % lag behind by one

For example:

| ?- last_il([a,b,c|T], L, X).

T = _h377
L = [a,b|_h377]
X = c;


    As seen with (10) above (also (12) and (13) with difference lists), incomplete lists can be concatenated through instantiations of end variables. In section 6.4 we require the ability to concatenate incomplete list content without any instantiation of end variables. This will be accomplished with append_il/3 of (18). Notice how the stopping condition is the first clause, which corresponds to reaching the end of the input list. The second clause has the form of the standard Prolog library append/3 definition.

append_il(L, Z0, Z) :- var(L), !, Z = Z0.                   % reached end, stop
append_il([H|T], Z0, [H|Z]) :-
  append_il(T, Z0, Z).

For example:

| ?- append_il([1,2,3|T], [4,5|U], L).

T = _h377
U = _h439
L = [1,2,3,4,5|_h439];


Notably, the output shows T and U retain their state of not being further instantiated.

2   Starting with Prolog terms

Initial realisation of normalised input will give a Prolog term (<normalised_expr>) with the syntax of (20).

<normalised_expr> ::=
      |  fresh( <fresh_list>, <normalised_expr> )
      |  local( <local_list>, <normalised_expr> )
      |  closure( <quantifier_operator>, <normalised_expr> )
      |  pred( <relation_atom>, <normalised_expr_list> )
      |  some( <fresh_atom>, <discourse_referent>, <normalised_expr>,
           <local_atom>, <normalised_expr> )
      |  someClassic_rest( <fresh_atom>, <discourse_referent>,
           <normalised_expr>, <local_atom>, <normalised_expr> )
      |  someClassic( <fresh_atom>, <discourse_referent>, <local_atom>,
           <normalised_expr> )
      |  someFact( <fresh_atom>, <relation_atom>, <discourse_referent>,
           <normalised_expr>, <local_atom>, <normalised_expr> )
      |  pick( <fresh_atom>, <sort_list>, <selection_atom>, <local_atom>,
           <normalised_expr> )
      |  pick_more( <fresh_atom>, <sort_list>, <selection_atom>,
           <local_atom>, <normalised_expr> )
      |  embed( <normalised_expr> )
      |  control( <normalised_expr> )
      |  control2( <normalised_expr> )
      |  connect( <relation_atom>, <normalised_expr_list> )

<sct_structure_mapping> ::=
         t( <grammar_atom> )
      |  at( <normalised_expr>, <role_atom> )
      |  mov( <grammar_atom>, <grammar_atom>, <normalised_expr> )
      |  namely( <discourse_referent>, <fresh_atom>, <normalised_expr> )
      |  bodyClimb( <fresh_atom>, <normalised_expr> )

<fresh_list> ::=
      |  .( <fresh_atom>, <fresh_list> )

<local_list> ::=
      |  .( <local_atom>, <local_list> )

<sort_list> ::=
      |  .( <sort_atom>, <sort_list> )

<grammar_atom> ::=
      |  <local_atom>
      |  <context_atom>

<discourse_referent> ::=
         x( <sort_atom>, <integer> )
      |  c( <sort_atom>, <constant_atom> )

    These prolog terms are either direct structural mappings to the SCT language of section 3 (t/1, at/2, mov/3, namely/3, and bodyClimb/2), or ‘higher level’ structures to realise:

    Discourse referents can be either variables (x/2) or constants (c/2). A variable has an atom parameter and an integer parameter. The atom is a ‘sort’ specification, while the integer identifies the variable. For example, x('ENTITY',1) is the entity variable ‘1’, while x('EVENT',3) is the event variable ‘3’. A constant has two atom parameters: The first specifies a sort, while the second identifies the constant. Thus c('PERSON','john') denotes the person ‘John’.

2.1   Grammatical roles

A Prolog atom that is part of a <normalised_expr> has a grammatical role (i.e., is a <grammar_atom>) when it is either:

The significance of these roles will emerge when we transform to <sct_expr> terms, and still more when we undertake semantic calculations. Briefly:

What is essential is to keep atoms with differing roles distinct. Separation is achieved by listing <fresh_atom> terms with fresh/2, and <local_atom> terms with local/2. Any atom not listed by the commanding instances of fresh/2 and local/2 might be used as a <context_atom>. For a full discourse, there is at least one declaration of <fresh_atom> terms with fresh/2 typically occuring as the topmost structure of the discourse encoding.

3   Intermediate language

The Prolog terms of section 2 are easily reached as conversions from input trees, but are not sufficiently fine grained to feed the semantic calculation, and so are transformed into an intermediate language, which is a revision of the Scope Control Theory (SCT) language of Butler (2015). An intermediate language expression is an <sct_expr>, where:

<sct_expr> ::=
      |  namely( <discourse_referent>, <fresh_atom>, <sct_expr> )
      |  <sct_terminal>
      |  at( <sct_expr>, <role_atom> )
      |  rel( <fresh_list>, <context_list>, <relation_atom>, <sct_expr_list> )
      |  ifThere( <grammar_atom>, <sct_expr>, <sct_expr> )
      |  mov( <grammar_atom>, <grammar_atom>, <sct_expr> )
      |  clean( <integer>, <local_list>, <context_atom>, <sct_expr> )
      |  pick( <selection_atom>, <sct_terminal>, <sources_list>, <sort_list> )

<drs_structure_mapping> ::=
         head( <quantifier_operator>, <fresh_list>, <sct_expr> )
      |  body( <fresh_list>, <sct_expr> )
      |  headClimb( <discourse_referent>, <fresh_atom>, <sct_expr> )
      |  bodyClimb( <fresh_atom>, <sct_expr> )

<sct_terminal> ::= t( <grammar_atom> )

<sct_expr_list> ::=
      |  .( <sct_expr>, <sct_expr_list> )

<context_list> ::=
      |  .( <context_atom>, <context_list> )

<sources_list> ::=
      |  .( <local_atom>, <sources_list> )
      |  .( <context_atom>, <sources_list> )

    With semantic calculations, these language primitives assemble content for output expressions of a discourse representation language (<drs_expr> terms; see section 6.3), while possibly altering the content of an information state. The information state both (i) feeds its content to the output expression, and (ii) influences the direction taken to build the output expression (see section 6.2). The following provides an informal overview of what the various primitives contribute:

    The significance of these SCT functors will become apparent when they are used in instantiations of <sct_expr> terms, the first of which are introduced in section 4.

4   Basic grammar statements

This section defines Prolog statements to assist <sct_expr> construction in section 5.

4.1   Building predicates

First, consider build_args(L1, L2), where L1 is a list of atoms, and L2 is the same list as L1, only with the atoms converted into <sct_expr> terms, with each atom from L1 functioning as: (i) the <grammar_atom> of an <sct_terminal> and, (ii) the <role_atom> of an at/2 structure with the term embedded.

build_args( [], [] ).
build_args( [A0|As0], [at( t( A0 ), A0 )|As] ) :-
  build_args( As0, As ).

For example:

| ?- build_args([a, b, c], L).

L = [at(t(a),a),at(t(b),b),at(t(c),c)];


    Now consider build_predicate/4 as a means to create predicates from SCT primitive rel/4 together with the range of potential arguments for the predicate (via build_args/2), and the selectional criteria for choosing between the produced arguments (via ifThere/2 for the semantic calculation to check the status of assigned content).

build_predicate( [], L, S, rel( [], [], S, Args ) ) :-
  build_args( L, Args ).
build_predicate( [H|T], L, S, ifThere( H, PredA, PredB ) ) :-
  build_predicate( T, [H|L], S, PredA ),
  build_predicate( T, L, S, PredB ).

For example, (25) illustrates [b, c] as a candidate list for the construction of arguments for a 'foo' predicate that will also have a required 'a' argument:

| ?- build_predicate([b, c], [a], foo, P).

P =
ifThere( b,
         ifThere( c,
                  rel( [], [], foo, [at(t(c),c),at(t(b),b),at(t(a),a)] ),
                  rel( [], [], foo, [at(t(b),b),at(t(a),a)] )),
         ifThere( c,
                  rel( [], [], foo, [at(t(c),c),at(t(a),a)] ),
                  rel( [], [], foo, [at(t(a),a)] )));


The instantiation of P gives two layers of ifThere/3 structures that are tests to choose between four different potential realisations of the foo predicate, each with a different valency that either includes or excludes arguments constructed from 'b' and 'c'. Note that all of the possible valency options of (25) have at least an argument constructed from 'a'.

    The appeal of build_predicate/4 is that there need be nothing in a predicate specification per se to determine what its arguments are going to be. Instead, there is the creation of all potential argument options based on the candidate list, leaving it to the semantic calculation to make a final selection from the valency options on the basis of which arguments have assigned content.

    With such an outlook there is no need for reference to a dictionary or lexicon to retrieve valence information for predicates. On the other hand, given an external resource, there is the prospect of grammaticality effects emerging when what is predicted by the resource differs from what is available from the assignment state during the runtime of a semantic calculation.

4.2   Enabling subordination

Natural languages work by repeatedly (re-)using the same grammatical resources. For example, with each new clause of a sentence and in the absence of control, there is the presence of a new subject. With the semantic calculation, a subject occurrence adds a <discourse_referent> to the difference list assigned to the <local_atom> 'arg0'. Because clauses of a sentence can be embedded inside clauses, there needs to be a separation of the content assigned to 'arg0' for a higher clause from the content assigned to 'arg0' in a lower clause. Such separation will be accomplished with make_subord/6.

make_subord( N, D, Ls, Keep, E, clean( N, Remove, D, E ) ) :-
  subtract( Ls, Keep, Remove ).

This creates a clean/4 structure that takes integer N, <local_list> Remove (formed from the <local_list> Ls with any elements also contained in Keep subtracted by subtract/3; see section 1.2.6), the <context_atom> D, and <sct_expr> E. At the runtime of a semantic calculation, this will send difference list content assigned to the atoms of Remove to the difference list that is assigned to D, such that the difference lists that remain assigned to the atoms of Remove will have a resulting length of N when evaluation continues with E. When N is 0, each atom of Remove will be assigned the empty difference list going into E.

5   Transformations

This section provides the transformation for reaching SCT structures from the Prolog terms of section 2. Transformation takes place against an environment that holds information about the available <grammar_atom> terms. First, let's introduce a routine to transform a list of expressions:

transform_list( _, [], [] ).
transform_list( Env, [Norm_expr|In], [Sct_expr|Out] ) :-
  transform( Env, Norm_expr, Sct_expr ),
  transform_list( Env, In, Out ).

The simplest transformations are direct mappings onto SCT structures, that make no use of the environment:

transform( _, t( X ), t( X ) ).
transform( Env, at( Norm_expr, S ), at( Sct_expr, S ) ) :-
  transform( Env, Norm_expr, Sct_expr ).
transform( Env, mov( X, Y, Norm_expr ), mov( X, Y, Sct_expr ) ) :-
  transform( Env, Norm_expr, Sct_expr ).
transform( Env, namely( DRef, X, Norm_expr ), namely( DRef, X, Sct_expr ) ) :-
  transform( Env, Norm_expr, Sct_expr ).
transform( Env, bodyClimb( V, Norm_expr ), bodyClimb( V, Sct_expr ) ) :-
  transform( Env, Norm_expr, Sct_expr ).

In the coming subsections, we work through the other structures of section 2.

5.1   Settings for ‘fresh’ and ‘local’ parameters

As mentioned already, transformation takes place against an environment that holds information about the available <grammar_atom> terms. This has the form env(Fs, Ds, D, Ls), with D as the (never altered) <context_atom>. The other parameters are (re-)set by fresh/2 and local/2 structures. Thus, fresh/2 changes Fs (<fresh_list>) and Ds (<context_list>), with Ds a list constructed with replace/3 to consist of D instances with the length of the new Fs.

transform( env( _, _, D, Ls ), fresh( Fs, Norm_expr ), Sct_expr ) :-
  replace( Fs, D, Ds ),
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr ).

local/2 changes the Ls (<local_list>) parameter:

transform( env( Fs, Ds, D, _ ), local( Ls, Norm_expr ), Sct_expr ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr ).

5.2   Closure

Closure makes use of <fresh_atom> terms via the Fs parameter of the env/4 environment to assemble head/3 and body/2 <sct_expr> content.

transform( env( Fs, Ds, D, Ls ),
           closure( Oper, Norm_expr ),
           head( Oper, Fs, body( Fs, Sct_expr ) ) ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr ).

5.3   Predicates

Predicates are provided by (32). This transforms pred/2 to a predicate encoding via build_predicate/4 (see section 4.1) with minimally arguments for the contents of Args. The full range of valence possibilities are assembled from the content of Usable. Usable is the content of Ls (the <local_atom> terms of the environment) with any Args overlap subtracted.

transform( env( _Fs, _Ds, _D, Ls ), pred( S, Args ), P ) :-
  subtract( Ls, Args, Usable ),
  build_predicate( Usable, Args, S, P ).

5.4   Argument forming structures

This subsection discusses argument forming structures: some/5, someClassic_rest/5, someClassic/4, and someFact/6.

5.4.1   Noun phrases with restrictions

A basic noun phrase is realised with some(V, DRef, Norm_exprR, X, Norm_exprNS). After transformation, there is namely/3 to introduce <discourse_referent> DRef for a <fresh_atom> V binding, which shifts to a <local_atom> X binding for the nuclear scope E0 (i.e., the rest of the containing clause or phrase), together with a further shift to the <local_atom> 'h' for the restriction material Norm_exprR. This latter shift to 'h' is accompanied by a call to make_subord/6 of section 4.2 which removes to the discourse context D any local binding from the containing clause or phrase that is not 'h'. Also, to ensure the restriction material accompanies the quantification introduction of DRef, bodyClimb/2 surrounds the content transformed from Norm_exprR and shares the same <fresh_atom> V by which the new argument binding is introduced.

transform( env( Fs, Ds, D, Ls ),
           some( V, DRef, Norm_exprR, X, Norm_exprNS ),
           namely( DRef, V,
                   mov( V, X,
                        rel( Fs, Ds, '',
                             [ bodyClimb( V,
                                          mov( X, 'h', Sct_exprR ) )
                             , Sct_exprNS] ) ) )
         ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_exprR, Sct_exprR0 ),
  transform( env( Fs, Ds, D, Ls ), Norm_exprNS, Sct_exprNS ),
  make_subord( 0, D, Ls, ['h'], clean( 1, ['h'], D, Sct_exprR0 ), Sct_exprR ).

5.4.2   Classic arguments

someClassic_rest/5 offers a variant of some/5 with no namely/3. Instead, SCT primitive headClimb/3 is used to introduce <discourse_referent> DRef. While DRef receives closure (and thereby its semantic scope) from the commanding closure of <fresh_atom> V, it will not exhibit dynamic scope. That is, its binding scope will be over the content of the restriction (Norm_exprR) and the nuclear scope (Norm_exprNS), but not beyond.

transform( env( Fs, Ds, D, Ls ),
           someClassic_rest( V, DRef, Norm_exprR, X, Norm_exprNS ),
           headClimb( DRef, V,
                      mov( V, X,
                           rel( Fs, Ds, '',
                                [ bodyClimb( V,
                                             mov( X, 'h', Sct_exprR ) )
                                , Sct_exprNS] ) ) )
         ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_exprR, Sct_exprR0 ),
  transform( env( Fs, Ds, D, Ls ), Norm_exprNS, Sct_exprNS ),
  make_subord( 0, D, Ls, ['h'], clean( 1, ['h'], D, Sct_exprR0 ), Sct_exprR ).

As with some/5, open local bindings other than 'h' shift to the discourse context D via make_subord/6 before content from the restriction Norm_exprR is reached. Also, the restriction content is surrounded by bodyClimb/2 with V for placement in the semantic representation resulting from semantic calculation.

    someClassic/4 offers a version of someClassic_rest/5 with no restriction.

transform( env( Fs, Ds, D, Ls ),
           someClassic( V, DRef, X, Norm_expr ),
           headClimb( DRef, V, mov( V, X, Sct_expr ) )
         ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr ).

5.4.3   Propositional arguments

someFact/6 shares the property with someClassic_rest/5 of having headClimb/3 to introduce its DRef (<discourse_referent>), but differs in its treatment of the restriction, Norm_exprR, which is used to form an embedding (with 'emb' role) to a predicate with <relation_atom> S. The opened X binding for the nuclear scope E0 binds a term argument of the S predicate with 'h' role but shifts to a '' (empty atom) binding before the content of the restriction Norm_exprR occurs. This removes the X binding from having any further binding role inside Norm_exprR. In further contrast to the restrictions of some/5 and someClassic_rest/5, there are no alterations to the local bindings the restriction Norm_exprR inherits from the containing clause or phrase.

transform( env( Fs, Ds, D, Ls ),
           someFact( V, S, DRef, Norm_exprR, X, Norm_exprNS ),
           headClimb( DRef, V,
                      mov( V, X,
                           rel( Fs, Ds, '',
                                [ bodyClimb( V,
                                             rel( [], [], S,
                                                  [at( t( X ), 'h' )
                                                  at( mov( X,'',Sct_exprR ), 'emb' ) ] )
                                , Sct_exprNS] ) ) )
         ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_exprR, Sct_exprR ),
  transform( env( Fs, Ds, D, Ls ), Norm_exprNS, Sct_exprNS ).

5.5   Pronouns

The contribution of a non-reflexive pronoun is realised with pick/5 of (37), while reflexive pronoun contribution is realised with pick_more/5 of (38). The contribution of these operations is not to introduce an argument value, but rather to link an already introduced local binding to some other value of the context. Consequently they occur in combination with an argument forming operation, typically with placement directly under a someClassic/4 action that opens a local binding. In cases where there is content for a restriction, such as from parenthetical content, then these pronominal actions occur in the nuclear scope part of a someClassic_rest/5 action.

transform( env( Fs, Ds, D, Ls ),
           pick( V, Sorts, S, X, Norm_expr ),
           rel( [], [], '&', [bodyClimb( V, pick( S, t( X ), [D], Sorts )), Sct_expr] )
         ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr ).
transform( env( Fs, Ds, D, Ls ),
           pick_more( V, Sorts, S, X, Norm_expr ),
           rel( [], [], '&', [bodyClimb( V, pick( S, t( X ), Sources, Sorts )), Sct_expr] )
         ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr ),
  subtract( [D|Ls], [X], Sources ).

    A pronoun is resolved by receiving as its S antecedent a discourse referent that shares sort information with the <sort_list> Sorts. Candidates for antecedents are gathered with the SCT primitive pick/4, with Sources determined on the basis of the called action: With pick/5 (from a non-reflexive pronoun), candidates are elements of the difference list assigned to the <context_atom> D; With pick_more/5 (from a reflexive pronoun) candidates are both elements of the difference list assigned to the <context_atom> D and elements of the difference lists assigned to the <local_atom> terms of Ls minus X, the binding from the pronoun itself.

5.6   Embedding

embed/1 protects an embedding from local (Ls) bindings that would otherwise be inherited from the outside environment.

transform( env( Fs, Ds, D, Ls ), embed( Norm_expr ), Sct_expr ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr0 ),
  make_subord( 0, D, Ls, [], Sct_expr0, Sct_expr ).

5.7   Control

Having embed/1 removes all inherited local (Ls) bindings. But binding inheritance may be desirable. In particular, as obligatory dependencies, control dependencies are best captured through the preservation of a local binding of the embedding environment into the embedding. However, such preservation might include a shift to a different local binding name, and this is accomplished with control/1.

transform( env( Fs, Ds, D, Ls ), control( Norm_expr ), Sct_expr ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr0 ),
  find_with_sub_atom('arg2', Ls, [], C1),
  find_with_sub_atom('obu', Ls, C1, C2),
  find_with_sub_atom('arg1', Ls, C2, C3),
  find_with_sub_atom('arg0', Ls, C3, C4),
  intersection( ['h'], Ls, C5),
  append(C5, C4, Candidates),
  make_subord( 0, D, Ls, Candidates, clean( 1, ['arg0'], D, Sct_expr0 ), Sct_expr1 ),
  make_subord( 0, 'arg0', Candidates, [], Sct_expr1, Sct_expr ).

The transformation of control/1 leads to three steps.

These three steps have the effect that, with control/1, there is one binding that can be preserved from the embedding clause into the embedding, with the ordering of preference in (41), with 'arg2' most preferred:

'arg2' > 'obu' > 'arg1' > 'arg0'

    In deviation to control/1, control2/1 establishes its control relation by altering the first step, so that only difference list elements assigned to binding names with 'arg0' as a sub atom shift to the 'arg0' binding. With this change, it can only be the binding of a name with 'arg0' as a sub atom that is maintained into the embedding.

transform( env( Fs, Ds, D, Ls ), control2( Norm_expr ), Sct_expr ) :-
  transform( env( Fs, Ds, D, Ls ), Norm_expr, Sct_expr0 ),
  find_with_sub_atom('arg0', Ls, [], Candidates),
  make_subord( 0, D, Ls, Candidates, clean( 1, ['arg0'], D, Sct_expr0 ), Sct_expr1 ),
  make_subord( 0, 'arg0', Candidates, [], Sct_expr1, Sct_expr ).

5.8   Coordination

connect/2 integrates the conjuncts of a list under a single rel/4 structure, with the appropriate relation name supplied through the S parameter.

transform( env( Fs, Ds, D, Ls ),
           connect( S, Norm_expressions ),
           rel( Fs, Ds, S, Sct_expressions ) ) :-
  transform_list( env( Fs, Ds, D, Ls ), Norm_expressions, Sct_expressions ).

What is most notable about relations constructed with connect/2 is that they are made sensitive to the Fs parameter, which is used to list the available fresh binding names. This triggers ‘dynamic’ behaviour, with management during evaluation leading to calls of allocate/6; see section 6.2.5. The allocate/6 calls make discourse referents accessible for the conjuncts of the Es list, either as never before used values, or as values of the discourse context.

6   The calculation

We now move on to a discussion of how <sct_expr> terms can be used as input for a calculation that returns a discourse representation language expression. Discourse representation language expressions (<drs_expr> terms) include quantificational closures, discourse referents, and relations (both as predicate conditions and connectives). In addition, there are markers to carry information on where discourse referents and conditions are interpreted.

    This section is organised as follows. Section 6.1 presents a procedure for collecting the <discourse_referent> terms of an <sct_expr>. Section 6.2 introduces a storage mechanism for holding <discourse_referent> terms. Section 6.3 presents the language of <drs_expr> terms. Section 6.4 gives the calculation from <sct_expr> terms to <drs_expr> terms. Finally, section 6.5 considers an example.

6.1   Collecting <discourse_referent> terms

A key contribution of head/3 and namely/3 is their use in determining the distributions of <discourse_referent> terms. The effects of this contribution are made with discourse_refs(X, E, Ds) of (44). This is true when X is a <fresh_name>, E is an <sct_expr>, and Ds is a difference list with <discourse_referent> terms obtained from E.

discourse_refs_from_list( _, [], D-D ).
discourse_refs_from_list( X, [E|T], D-D0 ) :-
  discourse_refs( X, E, D1-D0 ),
  discourse_refs_from_list( X, T, D-D1 ).

discourse_refs( X, head( _, Vs, E ), Ds ) :-
  ( memberchk( X, Vs ) ->
    Ds = D-D
    discourse_refs( X, E, Ds )
discourse_refs( X, body( _, E ), Ds ) :-
  discourse_refs( X, E, Ds ).
discourse_refs( X, headClimb( _, _, E ), Ds ) :-
  discourse_refs( X, E, Ds ).
discourse_refs( X, bodyClimb( _, E ), Ds ) :-
  discourse_refs( X, E, Ds ).
discourse_refs( X, namely( DRef, Y, E ), Ds ) :-
  ( X == Y ->
    discourse_refs( X, E, D-D0 ),
    Ds = [DRef|D]-D0
    discourse_refs( X, E, Ds )
discourse_refs( _, t( _ ), D-D ).
discourse_refs( X, at( E, _ ), Ds ) :-
  discourse_refs( X, E, Ds ).
discourse_refs( X, rel( _, _, _, Es ), Ds ) :-
  discourse_refs_from_list( X, Es, Ds ).
discourse_refs( X, ifThere( _, E1, E2 ), Ds ) :-
  discourse_refs( X, E1, Ds ),
  discourse_refs( X, E2, Ds ).
discourse_refs( X, mov( _, _, E ), Ds ) :-
  discourse_refs( X, E, Ds ).
discourse_refs( X, clean( _, _, _, E ), Ds ) :-
  discourse_refs( X, E, Ds ).
discourse_refs( _, pick( _, _, _, _ ), D-D ).

The definition of discourse_refs/3 has patterns (including wildcards ‘_’) to match the functors that make up the <sct_expr> language. Most functors contribute only the collections from the expressions over which they scope. For rel/4, this includes collecting from a contained list of <sct_expr> terms, via discourse_refs_from_list/3.

    The real action with discourse_refs/3 happens when either namely/3 or head/3 is reached. With namely/3 if there is a match of <fresh_atom> terms then the <discourse_referent> carried by namely/3 is entered into the overall difference list, else collection continues with no addition. With head/3 if the <fresh_atom> of the collection happens to be a member of the list that instantiates the Vs parameter of head/3 then the empty list is returned as the collection result (potentially hiding <discourse_referent> terms), else the collection for the embedded <sct_expr> is returned.

    As an example of executing discourse_refs/3, consider (45):

| ?- discourse_refs(foo, namely(x(bar,1), foo, namely(x(bar,2), foo, t(foo))), Ds).

Ds = [x(bar,1),x(bar,2)|_h625] - _h625;


That is, a difference list is returned containing the <discourse_referent> terms carried by the namely/3 instances.

    When head/3 and namely/3 share the same <fresh_atom>, head/3 serves to hide the presence of namely/3, as the return of the empty difference list in (46) shows.

| ?- discourse_refs( foo,
                     head( exists, [foo],
                           namely( x(bar, 1), foo,
                                   namely(x(bar, 2), foo, t(foo)))),

Ds = _h699 - _h699;


6.2   Storing <discourse_referent> terms

This section introduces a storage mechanism capable of keeping track of the status of <discourse_referent> terms. This consists of an assignment that assigns with map/2 a (possibly empty) difference list of <discourse_referent> terms to each <grammar_atom>.

assignment_update( X, Ds, Assn0, Assn ) :-
  Assn = [map( X, Ds )|Assn0].

    First, val(Assn, X, Ds) succeeds when Ds is the (possibly empty) difference list assigned by Assn to X.

val( Assn, X, Ds ) :-
  ( memberchk( map( X, Ds0 ), Assn ) ->
    Ds = Ds0
    Ds = D-D                     % otherwise return the empty difference list

By contrast, contentful_val(Assn, X, Ds) succeeds only if Ds is a non-empty difference list assigned by Assn to X.

contentful_val( Assn, X, D-D0 ) :-
  memberchk( map( X, D-D0 ), Assn ),
  D \== D0.

Note that with val/3 of (48), Assn as the empty list ([]) is sufficient for stating the empty assignment, with all X instantiations assigned the empty difference list.

    Now we have the ability to access assigned content, we next introduce methods: push/4, pop/3, shift/4, shift_last/4, allocate/6, and dispose/5. These methods will govern the introduction, release and subsequent accessibility of assigned content.

6.2.1   push/4

Defined in (50), push/4 succeeds when Assn is a variant of assignment Assn0 differing only in that there is a new difference list assigned with map/2 to X (via assignment_update/4 of (47)) that is the concatenation New-Old of the content of the difference list New-D and the difference list D-Old, where the latter was assigned to X by Assn0.

push( New-D, X, Assn0, Assn ) :-
  val( Assn0, X, D-Old ),
  assignment_update( X, New-Old, Assn0, Assn ).

For example:

| ?- push([x(bar,2)|D]-D, foo, [map(foo, [x(bar,1)|L]-L)], P).

D = [x(bar,1)|_h534]
L = _h534
P = [map(foo,[x(bar,2),x(bar,1)|_h534] - _h534),map(foo,[x(bar,1)|_h534] - _h534)];


6.2.2   pop/3

Defined in (52), pop/3 succeeds when Assn is the same as Assn0 except with the first element of the difference list assigned to X removed.

pop( X, Assn0, Assn ) :-
  contentful_val( Assn0, X, [_|D]-D0 ),
  assignment_update( X, D-D0, Assn0, Assn ).

For example:

| ?- pop(foo, [map(foo, [x(bar,2),x(bar,1)|L]-L)], P).

L = _h482
P = [map(foo,[x(bar,1)|_h482] - _h482),map(foo,[x(bar,2),x(bar,1)|_h482] - _h482)];


6.2.3   shift/4

Defined in (54), shift/4 succeeds when Assn is the same as Assn0 except with the first difference list element assigned to X removed and made the first element of the difference list assigned to Y.

shift( X, Y, Assn0, Assn ) :-
  contentful_val( Assn0, X, [DRef|DX]-DX0 ),
  assignment_update( X, DX-DX0, Assn0, Assn1 ),
  val( Assn0, Y, DY-DY0 ),
  assignment_update( Y, [DRef|DY]-DY0, Assn1, Assn ).

For example:

| ?- shift(foo, baz, [map(foo, [x(bar,2),x(bar,1)|L]-L)], P).

L = _h496
P = [ map(baz,[x(bar,2)|_h662] - _h662),
      map(foo,[x(bar,1)|_h496] - _h496),
      map(foo,[x(bar,2),x(bar,1)|_h496] - _h496)


6.2.4   shift_last/4

Defined in (56), shift_last/4 succeeds when Assn is the same as Assn0 except with the last difference list element, DRef (found via last_il/3, see section 1.2.7), assigned to X removed (to leave DX-DX0 as the assigned value) and made the first element of the difference list assigned to Y.

shift_last( X, Y, Assn0, Assn ) :-
  contentful_val( Assn0, X, DX1-DX0 ),
  last_il( DX1, DX, DRef ),
  assignment_update( X, DX-DX0, Assn0, Assn1 ),
  val( Assn0, Y, DY-DY0 ),
  assignment_update( Y, [DRef|DY]-DY0, Assn1, Assn ).

For example:

| ?- shift_last(foo, baz, [map(foo, [x(bar,2),x(bar,1)|L]-L)], P).

L = _h496
P = [ map(baz,[x(bar,1)|_h662] - _h662),
      map(foo,[x(bar,2)|_h496] - _h496),
      map(foo,[x(bar,2),x(bar,1)|_h496] - _h496)


6.2.5   allocate/6 with expression integrity

The required manipulation for moving through the expressions of a discourse from left to right will be automated by allocate/6. Atom X is a <fresh_atom> when namely(X, _, _) occurs within an <sct_expr>. A <fresh_atom> serves as a source of <discourse_referent> terms that have not been previously accessed. Taking discourse to be a collection of ordered <sct_expr> terms (Es), and supposing X is a <fresh_atom> in Es, then, at the moment of interpreting the entire discourse Es, the assignment state will be assigning a difference list to X that contains all <discourse_referent> terms required for all the separate expressions of Es. We can think of such an assigned difference list as being formed so that <discourse_referent> terms needing to appear for the first expression of Es (that is, the start of the discourse) will appear last in the assigned difference list. Working through the remaining expressions of Es then amounts to opening up more of the difference list content assigned to X in end-to-front direction, until all <discourse_referent> terms are revealed with the last expression of Es, so that, with completion of the discourse, all <discourse_referent> terms assigned X will have been accessed. One more thing that allocate/6 does is move the <discourse_referent> terms that were accessed by prior expressions to a different <grammar_atom> serving as a <context_atom>. The different uses of <grammar_atom> terms are set out in section 2.1. Bearing these matters in mind will help in understanding how allocate/6 is defined.

    First, consider pf_split(N, List, Past, Future) of (58). This succeeds when Past is the first N-1 elements of List and Future is the elements of List from N+1 to the last element.

pf_split( 1, [_|T], [], T ) :- !.
pf_split( N, [H|T], [H|Past], Future ) :-
  M is N - 1,
  pf_split( M, T, Past, Future ).

For example:

| ?- pf_split(3, [a,b,c,d,e], Past, Future).

Past = [a,b]
Future = [d,e];


    do_pop(List, X, In, Out) changes the assignment from In to Out by performing the pop/3 operation of (52) on the different list assigned X as many times as there are elements in List.

do_pop( [], _, Assn, Assn ).
do_pop( [_|T], X, Assn0, Assn ) :-
  pop( X, Assn0, Assn1 ),
  do_pop( T, X, Assn1, Assn ).

    do_shift_last(List, X, Y, In, Out) changes the assignment from In to Out by performing the shift_last/4 operation of (56) on the difference lists assigned to X and Y as many times as there are elements in List.

do_shift_last( [], _, _, Assn, Assn ).
do_shift_last( [_|T], X, Y, Assn0, Assn ) :-
  shift_last( X, Y, Assn0, Assn1 ),
  do_shift_last( T, X, Y, Assn1, Assn ).

    Now consider allocate(N, Xs, Ys, Es, Assn0, Assn), as defined in (62). With Xs and Ys empty, Assn and Assn0 are the same assignment. Otherwise there is recursion to work through the list content of Xs and Ys. Each cycle of recursion succeeds when, relative to integer N and list Es of <sct_expr> terms, assignment Assn differs from Assn0 in regards to the content assigned to the head X of Xs and the head Y of Ys. More specifically, N is used to split Es into a list of future expressions (Future) and past expressions (Past), from which lists of <discourse_referent> terms for X are extracted (via discourse_refs/3) for the future (Future_DRefs) and past (Past_DRefs) relative to N. The Future_DRefs are then removed (via pop/3) from the assignment to X, while the Past_DRefs are relocated (via shift_last/4) to Y.

allocate( _, [], [], _, Assn, Assn ).
allocate( N, [X|FNs], [Y|CNs], Es, Assn0, Assn ) :-
  pf_split( N, Es, Past, Future ),
  % the future
  discourse_refs_from_list( X, Future, FutureDRefs-[] ),
  % the past
  discourse_refs_from_list( X, Past, PastDRefs-[] ),
  % remove the future
  do_pop( FutureDRefs, X, Assn0, Assn1 ),
  % contextualise the past
  do_shift_last( PastDRefs, X, Y, Assn1, Assn2 ),
  % move to next allocate changes
  allocate( N, FNs, CNs, Es, Assn2, Assn ).

    To see consequences of allocate/6, consider (63)–(65).

| ?- allocate( 1, [foo], [baz], [t(baz), namely(x(bar,2), foo, t(foo)), t(baz)],
               [map(baz, [x(bar,1)|L1]-L1), map(foo, [x(bar,2)|L2]-L2)], P).

L1 = _h692
L2 = _h828
P = [ map(foo,_h828 - _h828),
      map(baz,[x(bar,1)|_h692] - _h692),
      map(foo,[x(bar,2)|_h828] - _h828)

| ?- allocate( 2, [foo], [baz], [t(baz), namely(x(bar,2), foo, t(foo)), t(baz)],
               [map(baz, [x(bar,1)|L1]-L1), map(foo, [x(bar,2)|L2]-L2)], P).

L1 = _h692
L2 = _h828
P = [ map(baz,[x(bar,1)|_h692] - _h692),
      map(foo,[x(bar,2)|_h828] - _h828)

| ?- allocate( 3, [foo], [baz], [t(baz), namely(x(bar,2), foo, t(foo)), t(baz)],
               [map(baz, [x(bar,1)|L1]-L1), map(foo, [x(bar,2)|L2]-L2)], P).

L1 = _h692
L2 = _h828
P = [ map(baz,[x(bar,2),x(bar,1)|_h692] - _h692),
      map(foo,_h828 - _h828),map(baz,[x(bar,1)|_h6_h692),
      map(foo,[x(bar,2)|_h828] - _h828)


This reveals how what is assigned as difference list content can be discarded altogther, as is the case for x(bar,2) when N is 1 in (63). And if assigned content remains, then it is either: (i) present to support occurrences of namely/3, as is the case with x(bar,2) remaining assigned to foo when N is 2 in (64), or (ii) serving as content that will have been relocated as seen when N is 3 in (65) with x(bar,2) assigned as part of a difference list for baz while the difference list for foo is empty.

    When allocate/6 is called it ensures the appropriate assignment of <discourse_referent> terms to <grammar_atom> terms in an expression. The calculation is global over the full discourse, amounting to a check on the operation of the calculation and on the well-formedness of the discourse data, simultaneously.

6.2.6   dispose/5

Defined in (67) with iterations of shift_last/4, dispose(N, Xs, Y, Assn0, Assn) returns Assn as output which is the same as the input assignment Assn0, with the exception that the <discourse_referent> terms contained in the difference lists assigned by Assn0 to the <grammar_atom> terms of Xs will have become <discourse_referent> terms of the difference list assigned to the Y <grammar_atom> when the source difference lists have a length longer than N. The contribution of length_il/2 is discussed in section 1.2.7.

n_shift_last( N, _, _, Assn, Assn ) :-
  N =< 0.
n_shift_last( N, X, Y, Assn0, Assn ) :-
  N > 0,
  shift_last( X, Y, Assn0, Assn1 ),
  C is N - 1,
  n_shift_last( C, X, Y, Assn1, Assn ).
dispose( _, [], _, Assn, Assn ).
dispose( N, [X|T], Y, Assn0, Assn ) :-
  val( Assn0, X, D-_ ),
  length_il( D, M ),
  C is M - N,
  n_shift_last( C, X, Y, Assn0, Assn1 ),
  dispose( N, T, Y, Assn1, Assn ).

For example:

| ?- dispose(0, [foo], baz, [map(foo, [x(bar,2),x(bar,1)|L]-L)], P).

L = _h524
P = [ map(baz,[x(bar,2),x(bar,1)|_h701] - _h701),
      map(foo,_h524 - _h524),
      map(baz,[x(bar,1)|_h7[x(bar,2),x(bar,1)|_h524] - _h524)];


When N is 0, all <discourse_referent> terms of the difference list assigned to foo are relocated to baz.

    Like allocate/6, dispose/5 will be utilised to move <discourse_referent> terms from one <grammar_atom> to a different <grammar_atom> serving as a discourse context. A key difference is that while with allocate/6 such moves will occur as we proceed through discourse (that is, through ‘coordinate structure’ with linked units of equal status), with dispose/5 the moves are to be triggered as we enter ‘subordinate structure’ (notably, clauses which are grammatically subordinate because they are part of another clause).

6.3   The discourse representation language

This section presents the discourse representation language that is the target language of the semantic calculation. This includes <discourse_referent> terms as terminal elements. For complex expressions, there are structures to distinguish relations (rel/2) and markers of argument roles (at/2). Finally, there are structures to manipulate where discourse referents and their conditions are interpreted (head/4, body/2, headClimb/3, and bodyClimb/2).

    A discourse representation language expression is a <drs_expr>, where:

<drs_expr> ::=
      |  rel(<relation_atom>, <drs_expr_list>)
      |  at(<drs_expr>, <role_atom>)
      |  head(<quantifier_operator>, <fresh_list>, <bound_list>, <drs_expr>)
      |  body(<fresh_list>, <drs_expr>)
      |  headClimb(<discourse_referent>, <fresh_atom>, <drs_expr>)
      |  bodyClimb(<fresh_atom>, <drs_expr>)

<drs_expr_list> ::=
      |  .(<drs_expr>, <drs_expr_list>)

<bound_list> ::=
      |  .(x(<sort_atom>, <integer>), <bound_list>)

<fresh_list> ::=
      |  .(<fresh_atom>, <fresh_list>)

    <discourse_referent> terms are introduced in (20) of section 2. <bound_list> terms are lists of discourse referents that are constructed with x/2 (that is, those discourse referents that are variables).

    Relations (rel/2) comprise predications, adverbial modifications, and higher order connectives, such as negation and conjunction. The atom parameter of rel/2 identifies the predicate, modifier, connective, etc. in question, while the second parameter is either a list of the arguments built on at/2 structures (of a predicate or modifier), or a list of <drs_expr> terms (of a connective).

    Argument role markers (at/2) have a <drs_expr> parameter (typically built on <discourse_referent> terms) and an atom parameter which specifies the argument role relative to the containing relation.

    The remaining functors carry information about the placement of expression material:

In this regard, head/4 acts like the top box of a Discourse Representation Structure (DRS; Kamp and Reyle 1993), while body/2 acts as the bottom box.

6.4   From <sct_expr> terms to <drs_expr> terms

This section brings together everything seen thus far with calculate/3 which transforms <sct_expr> terms into <drs_expr> terms. Defined in (72), calculate(Assn, Sct_expr, Drs_expr) has Assn for an assignment function, Sct_expr to take the input <sct_expr>, while Drs_expr is the output discourse representation language expression. Assn assigns difference lists of <discourse_referent> terms to the <grammar_atom> terms contained in Sct_expr.

    calculate/3 contains calls to the assignment actions of section 6.2: push/4 (50), shift/4 (54), allocate/6 (62), and dispose/5 (67). When encountering occurrences of head/3, calculate/3 calls the operation of discourse_refs/3 (44). This gathers the <discourse_referent> terms made available by namely/3 for inclusion into the assignment. Thereafter the assigned content is distributed to parts of the input <sct_expr> with recursive calls of calculate/3. Such recursive calls of calculate/3 may be invoked by a match of rel/4 that through applications of allocate/6 can reposition or remove assigned content based on collections from namely/3. Note how discourse_refs/3 performs two functions: Firstly, with head/3, it collects the <discourse_referent> terms of namely/3 instances for inclusion into the assignment, and secondly, with rel/4, it is used in calls of allocate/6 to ensure that already collected <discourse_referent> terms that are parts of assigned difference lists are correctly accessible from the inherited assignment state.

change_assignment( [], _, Assn, Assn, Bds, Bds ).
change_assignment( [X|T], Sct_expr, Assn0, Assn, Bds0, Bds ) :-
  discourse_refs( X, Sct_expr, D-D0 ),
  push( D-D0, X, Assn0, Assn1 ),
  binding_filter( D, Bds0, Bds1 ),
  change_assignment( T, Sct_expr, Assn1, Assn, Bds1, Bds ).
calculate_list( _, _, _, _, _, [], [] ).
calculate_list( Assn0, N, Xs, Ys, Sct_expressions, [Sct_expr|In], [Drs_expr|Out] ) :-
  I is N + 1,
  allocate( I, Xs, Ys, Sct_expressions, Assn0, Assn ),
  calculate( Assn, Sct_expr, Drs_expr ),
  calculate_list( Assn0, I, Xs, Ys, Sct_expressions, In, Out ).
calculate( Assn0, head( Oper, Vs, Sct_expr ), head( Oper, Vs, Bds, Drs_expr ) ) :-
  change_assignment( Vs, Sct_expr, Assn0, Assn, [], Bds ),
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn, body( Vs, Sct_expr ), body( Vs, Drs_expr ) ) :-
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn0, headClimb( DRef, X, Sct_expr ), headClimb( DRef, X, Drs_expr ) ) :-
  push( [DRef|R]-R, X, Assn0, Assn ),
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn, bodyClimb( X, Sct_expr ), bodyClimb( X, Drs_expr ) ) :-
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn, namely( _, _, Sct_expr ), Drs_expr ) :-
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn, t( X ), DRef ) :-
  memberchk( map( X, [DRef|_]-_ ), Assn ).
calculate( Assn, at( Sct_expr, S ), at( Drs_expr, S ) ) :-
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn, rel( Xs, Ys, S, Sct_expressions ), rel( S, Drs_expressions ) ) :-
  calculate_list( Assn, 0, Xs, Ys, Sct_expressions, Sct_expressions, Drs_expressions ).
calculate( Assn, ifThere( X, Sct_expr1, Sct_expr2 ), Drs_expr ) :-
  ( contentful_val( Assn, X, _ ) ->
    calculate( Assn, Sct_expr1, Drs_expr )
    calculate( Assn, Sct_expr2, Drs_expr )
calculate( Assn0, mov( X, Y, Sct_expr ), Drs_expr ) :-
  shift( X, Y, Assn0, Assn ),
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn0, clean( N, Xs, Y, Sct_expr ), Drs_expr ) :-
  dispose( N, Xs, Y, Assn0, Assn ),
  calculate( Assn, Sct_expr, Drs_expr ).
calculate( Assn, pick( S, Sct_expr, Sources, Sorts ), rel( S, [DRef|Resolved] ) ) :-
  calculate( Assn, Sct_expr, DRef ),
  collect_context( Sources, Assn, [], Context ),
  antecedents( Sorts, Context, Resolved-[] ).

    The following details the consequences of all the functors with regard to direct changes made to the assignment, and content added to the returned discourse representation language expression:

binding_filter( L, Z0, Z ) :- var( L ), !, Z = Z0.      % reached end, stop
binding_filter( [X|L], Z0, Z ) :-
  ( X = x( _, _ ) ->
    Z1 = [X|Z0]
    Z1 = Z0
  binding_filter( L, Z1, Z ).

    Pronouns can offer information to limit possible antecedents. Possible antecedents are first obtained from the assignment state with collect_context/4. Defined in (75), antecedents(Sorts, Context, Rs) subsequently picks out with the difference list Rs the discourse referents from list Context that have sort information present in the list Sorts.

collect_context( [], _, Context, Context ).
collect_context( [X|Sources], Assn, Context0, Context ) :-
  val( Assn, X, D-_ ),
  append_il( D, Context0, Context1 ),
  collect_context( Sources, Assn, Context1, Context ).
antecedents( _, [], R-R ).
antecedents( Sorts, [x( S, I )|Context], [x( S, I )|R]-R0 ) :-
  memberchk( S, Sorts ), !,
  antecedents( Sorts, Context, R-R0 ).
antecedents( Sorts, [c( S, C )|Context], [c( S, C )|R]-R0 ) :-
  memberchk( S, Sorts ), !,
  antecedents( Sorts, Context, R-R0 ).
antecedents( Sorts, [_|Context], R-R0 ) :-
  antecedents( Sorts, Context, R-R0 ).

6.5   An example

For a demonstration, consider (76).

A cat entered. It purred.

The Prolog term (77) is a rendering of (76) as a <normalised_expr>. This includes an instance of discourse closure as the top level fresh/2 structure to state sources for fresh bindings that is placed above an instance of closure/2 with 'exists' quantification. The presence of '.e' with fresh/2 is needed for two reasons. First, there is the contained some/5 from A cat that has '.e' as the value for its <fresh_atom> parameter to introduce the discourse referent x('ANIMAL',2). Second, there is the contained someClassic/5 with pick/5 from It, where '.e' is the <fresh_atom> parameter value to introduce the referent x('ANIMAL',4) that lacks discourse scope but can be resolved to an accessible discourse referent of the discourse context that shares the 'ANIMAL' sort information. The presence of '.event' with fresh/2 is motivated by the contained instances of namely/3 contributed by the verbs entered and purred that have '.event' as the value for their <fresh_atom> parameter to introduce the discourse referents x('EVENT',1) and x('EVENT',3), respectively. The representation of (77) keeps the contributions of the two separate sentences of (76) distinct as conjuncts of a connect/2 structure with '&', the default connective for discourse. Each sentence contributes a single clause that introduces its own syntactic locality with local/2. Both of these clause instances of local/2 allow support for only an 'arg0' argument. The contribution of the first sentence also creates a distinct locality with another embedded instance of local/2 from A cat to capture the content of the noun phrase restriction that allows support for only a nominal head 'h' internally to the restriction.

fresh( .( '.event'
         ,.( '.e'
      ,closure( 'exists'
               ,connect( '&'
                        ,.( local( .( 'arg0'
                                  ,some( '.e'
                                        ,local( .( 'h'
                                               ,pred( 'cat'
                                                     ,.( 'h'
                                        ,namely( x('EVENT',1)
                                                ,pred( 'entered'
                                                      ,.( '.event'
                                                         ,.( 'arg0'
                           ,.( local( .( 'arg0'
                                     ,someClassic( '.e'
                                                  ,pick( '.e'
                                                        ,.( 'ANIMAL'
                                                        ,namely( x('EVENT',3)
                                                                ,pred( 'purred'
                                                                      ,.( '.event'
                                                                         ,.( 'arg0'

With transformation to an <sct_expr>, (77) becomes (78). This maintains the overall structure seen with (77), only with the higher level operations of the <normalised_expr> language replaced by the more articulated operations of the <sct_expr> language.

head( 'exists'
     ,.( '.e'
        ,.( '.event'
     ,body( .( '.e'
              ,.( '.event'
           ,rel( .( '.e'
                   ,.( '.event'
                ,.( '*'
                   ,.( '*'
                ,.( namely( x('ANIMAL',2)
                           ,mov( '.e'
                                ,rel( .( '.e'
                                        ,.( '.event'
                                     ,.( '*'
                                        ,.( '*'
                                     ,.( bodyClimb( '.e'
                                                   ,mov( 'arg0'
                                                        ,clean( 0
                                                               ,.( 'arg0'
                                                               ,clean( 1
                                                                      ,.( 'h'
                                                                      ,rel( []
                                                                           ,.( at( t( 'h')
                                        ,.( namely( x('EVENT',1)
                                                   ,rel( []
                                                        ,.( at( t( '.event')
                                                           ,.( at( t( 'arg0')
                   ,.( headClimb( x('ANIMAL',4)
                                 ,mov( '.e'
                                      ,rel( []
                                           ,.( bodyClimb( '.e'
                                                         ,pick( 'equals__It'
                                                               ,t( 'arg0')
                                                               ,.( '*'
                                                               ,.( 'ANIMAL'
                                              ,.( namely( x('EVENT',3)
                                                         ,rel( []
                                                              ,.( at( t( '.event')
                                                                 ,.( at( t( 'arg0')

With calculation to a <drs_expr>, (78) becomes (79). This reveals the reallocation of content to form the binding operations of a resolved discourse representation.

head( 'exists'
     ,.( '.event'
        ,.( '.e'
     ,.( x('ANIMAL',2)
        ,.( x('EVENT',1)
           ,.( x('EVENT',3)
     ,body( .( '.event'
              ,.( '.e'
           ,rel( '&'
                ,.( rel( ''
                        ,.( bodyClimb( '.e'
                                      ,rel( 'cat'
                                           ,.( at( x('ANIMAL',2)
                           ,.( rel( 'entered'
                                   ,.( at( x('EVENT',1)
                                      ,.( at( x('ANIMAL',2)
                   ,.( headClimb( x('ANIMAL',4)
                                 ,rel( '&'
                                      ,.( bodyClimb( '.e'
                                                    ,rel( 'equals__It'
                                                         ,.( x('ANIMAL',4)
                                                            ,.( x('ANIMAL',2)
                                         ,.( rel( 'purred'
                                                 ,.( at( x('EVENT',3)
                                                    ,.( at( x('ANIMAL',4)

As a final step, not discusssed elsewhere in this paper, we can pretty print the content of (79) as the expression (80) following TPTP syntax (Sutcliffe 2009).

  & isA(ANIMALX2,cat)
    ( ( isA(EVENTX1,entered)
      & arg0(EVENTX1) = ANIMALX2 )
    & ( isA(EVENTX3,purred)
      & arg0(EVENTX3) = ANIMALX4 ) ) )


Bos, Johan. 2005. Towards wide-coverage semantic interpretation. In Proceedings of Sixth International Workshop on Computational Semantics (IWCS-6), pages 42–53.

Butler, Alastair. 2007. Scope control and grammatical dependencies. Journal of Logic, Language and Information 16:241–264.

Butler, Alastair. 2010. The Semantics of Grammatical Dependencies, vol. 23 of Current Research in the Semantics/Pragmatics Interface. Bingley: Emerald.

Butler, Alastair. 2015. Linguistic Expressions and Semantic Processing: A Practical Approach. Heidelberg: Springer-Verlag.

Cresswell, M. J. 2002. Static semantics for dynamic discourse. Linguistics and Philosophy 25:545–571.

Dekker, Paul. 2002. Meaning and use of indefinite expressions. Journal of Logic, Language and Information 11:141–194.

Dekker, Paul. 2012. Dynamic Semantics, vol. 91 of Studies in Linguistics and Philosophy. Dordrecht: Springer Verlag.

Eijck, Jan van. 2001. Incremental dynamics. Journal of Logic, Language and Information 10:319–351.

Groenendijk, Jeroen and Martin Stokhof. 1991. Dynamic Predicate Logic. Linguistics and Philosophy 14(1):39–100.

Heim, Irene. 1982. The Semantics of Definite and Indefinite Noun Phrases. Ph.D. thesis, University of Massachusetts, Amherst.

Kamp, Hans and Uwe Reyle. 1993. From Discourse to Logic: Introduction to Model-theoretic Semantics of Natural Language, Formal Logic and Discourse Representation Theory. Dordrecht: Kluwer.

Muskens, Reinhard. 1996. Combining montague semantics and discourse representation. Linguistics and Philosophy 19:143–186.

Sutcliffe, Geoff. 2009. The TPTP Problem Library and Associated Infrastructure: The FOF and CNF Parts, v3.5.0. Journal of Automated Reasoning 43(4):337–362.

Vermeulen, C. F. M. 1993. Sequence semantics for dynamic predicate logic. Journal of Logic, Language and Information 2:217–254.

Yana, Yukiko, Koji Mineshima, and Daisuke Bekki. 2019. Variable handling and compositionality: Comparing DRT and DTS. Journal of Logic, Language and Information 28:261–285.

Zeevat, Henk. 1989. A compositional approach to discourse representation theory. Linguistics and Philosophy 12:95–131.