The formalism defined so far will be used in this thesis in two ways. Firstly I use the formalism to define grammars with. However, I also use the formalism to define meta-interpreters in. This will become clear in the next section. To separate these two usages, I define a grammar as follows. Without loss of generality I restrict a grammar G to consist of definite clauses defining only one unary relation. Restricting grammars to consist of only one relation enables us to distinguish between truly recursive relations and relations that could (at least in principle) be compiled away by partial evaluation techniques. I assume e.g. that the usual templates known from PATR II are already compiled out in such a grammar. As an example of partial evaluation, observe that the following definite clause specification:
can automatically be compiled into the following equivalent specification, where the `effect' of the predicate q/1 is obtained in the predicate p/1 directly:
In monolingual grammars, the privileged relation will be called `sign', as I think of this relation as defining the possible (linguistic) signs.
Note that any set of ()-definite clauses can be rewritten as a grammar of (), by `reification'; for example the following example set of clauses, consisting of several relations
is rewritten into the following, using the attributes rel,arg1,arg2 to represent the relation symbol and the arguments:
Before I continue to define the procedural semantics of () in the next section, I will first introduce some notational conveniences as follows. Using the matrix representation introduced above, I often leave out the constraints in a definite clause, and instead replace the variables in the clause with the matrix notation of the equations constraining that variable. Moreover, if the predicate symbol of an atom is sign/1 then I sometimes leave the predicate symbol out; hence
may be written simply as:
where Mi are the matrices defining the constraints on Xi. For example, the rule