A Guide to cu-Prolog III

Hiroshi TSUDA Second Research Department Institute for New Generation Computer Technology (ICOT) Mita-Kokusai Bldg. 21F, 1–4–28 Mita, Minato-ku, Tokyo 108, Japan

Tel : +81-3-3456-3069 Fax : +81-3-3456-1618 E-mail : tsuda@icot.or.jp

July 7, 1994

Contents

1 Introduction 3 1.1 How to Compile cu-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Customize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 CPU time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 EUC Kanji code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Heap size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 How to start and quit cu-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Syntax of cu-Prolog 5 2.1 Constrained Horn Clause (CHC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 PST (Partially Specified Term) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Canonical form of Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 BNF description of cu-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Summary of system commands 8 3.1 Prolog commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 File I/O commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Debug commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Constraint Transformation commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Other commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

4 Built-in predicates, functors 9 4.1 Functional built-in predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 Predicative built-in predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Built-in predicates for constraint transformation . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.4 Built-in predicates for JPSG parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

5 File I/O 13 5.1 Read a program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.2 Save a program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5.3 Log file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6 Constraint Transformation 13

6.1 Use constraint transformer alone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.1.1 ‘@’ command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.1.2 unify/2 predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.2 Transformation operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.3 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

6.4.1 Symbolic and combinatorial constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.4.2 Disjunctive feature unification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

7 Program trace 17 7.1 Set spy points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.2 Set trace flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.3 Trace of constraint transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.3.1 Print traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 7.3.2 User’s input in the step trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

8 JPSG parser 18 8.1 Encoding Lexical Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.2 Encoding Structural Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 8.3 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

9 Concluding Remarks 21

1 Introduction

This is the user’s manual of cu-Prolog III[12, 11].

cu-Prolog is an experimental constraint logic programming language. Unlike most conventional CLP systems, cu-Prolog allows user-defined predicates as constraints and is suitable for implementing a natural language processing system based on the unification-based grammar[7]. As an application of cu-Prolog , we developed a JPSG (Japanese Phrase Structure Grammar [2]) parser with the JPSG Working Group (the chairman is Prof. GUNJI, Takao of Osaka University) at ICOT.

cu-Prolog is also the complete implementation of the constraint unification[5] and its name (cu) comes from the technique. cu-Prolog system is a DEC10-like Prolog interpreter with a constraint solver based on the constriant unification which uses the unfold/fold transformation techinique.

Originally, cu-Prolog is implemented in the C language of UNIX 4.2/3BSD. Later, prof.Sirai of Chukyo-University (sirai@sccs.chukyo-ac.jp) implemented cu-Prolog in Apple Macintosh and DJ’s GPP (80386/486 MS-DOS machine with the DOS extender). This document is the user’s manual of UNIX version of cu-Prolog released as an ICOT Free Software.

1.1 How to Compile cu-Prolog

The source codes of cu-Prolog consists of the following header files and program files in the C language.

• header files:

         include.h funclist.h varset.h globalv.h sysp.h

• program files concerning Prolog interpreter:

         main.c mainsub.c new.c read.c print.c refute.c unify.c

• program files concerning built-in predicates:

         defsysp.c syspred1.c syspred2.c jpsgsub.c

• program files concerning constraint transformation:

         modular.c trans.c tr sub.c tr split.c

To get the execution code of cu-Prolog , you have only to compile and link all the modules (*.c files). In UNIX for example,

     cc -o cuprolog *.c [CR]

or

     make [CR]

1.2 Customize

Before compiling, you may have to rewrite some statements in include.h in accordance with your system. 1.2.1 CPU time cu-Prolog uses system dependent functions to count process times.

1. If your system has times() function, ^{1}

         #define CPUTIME 60

1times() is the UNIX 4.2/3 BSD Library which returns CPU time in 60th of a second.

If times() in your system returns CPU time in N-th of a second,

         #define CPUTIME N

2. In Sun-4 system, clock() is supported. Then, please define SUN4 as follows instead of CPUTIME.

         #define SUN4 1

3. Otherwise, the CPU time is not printed.

         #define CPUTIME 0

1.2.2 EUC Kanji code From ver3.9(94/11/4), cu-Prolog can treat EUC Kanji-code in string system predicates such as strlen, divstr, substring, concat2, and concat.

     #define KANJI 1

allows EUC-Kanji processing in the above predicates. 1.2.3 Heap size cu-Prolog has the following data areas. system heap: stores program clauses. Its size is SHEAP SIZE (the default value is 600Kbytes) user heap: stores temporal data in the Prolog interpreter. Its size is HEAP SIZE (the default value is

500Kbytes) constraint heap: stores constraints and PSTs. Its size is CHEAP SIZE (the default value is 500Kbytes) environment stack: stores temporal environments in the Prolog interpreter. Its size is ESP SIZE (the

default value is 80KBytes) user stack: is a trail stack in the Prolog interpreter. Its size is USTACK SIZE (the default value is 30Kbytes) string heap: stores strings. Its size is NAME SIZE (the default value is 50Kbytes)

You can adjust these stack sizes with command arguments of cu-Prolog .

1.3 How to start and quit cu-Prolog

cu-Prolog allows following arguments.

   cuprolog [-Hxxx][-Sxxx][-Exxx][-Cxxx][-Uxxx][-Nxxx][filename]

• -Hxxx : xxx is the size of user heap (Kbytes).

• -Sxxx : xxx is the size of system heap (Kbytes).

• -Cxxx : xxx is the size of constraint heap (Kbytes).

• -Exxx : xxx is the size of environment stack (Kbytes).

• -Uxxx : xxx is the size of user stack (Kbytes).

• -Nxxx : xxx is the size of string heap (Kbytes).

• filename : initial program.

For example, to start cu-Prolog with 800Kbytes system heap, 600Kbytes constraint heap, and initial file ’foo.p’, type the following command.

     cuprolog -S800 -C600 foo.p

To quit cu-Prolog , type followings at the top level of cu-Prolog .

     %Q [CR] or :-halt.  [CR]

2 Syntax of cu-Prolog

term : atom, variable, complex term, or PST atom : constant, string, or number constant : sequence of characters that begins with a small letter or sequence of any characters with single

quotes. string : sequence of any characters with double quotes. number : integer, floating number. variable : sequence of characters that begins with a capital letter or . is called an anonymous variable

and any two anonymous variables are different. complex term : let p be a string and t1, t2, ⋯, tn be terms, then p(t1, t2, ⋯, tn) be a complex term.

p is called a functor or a predicate symbol. List is a special functor. PST (Partially Specified Term) : sequence of feature/value quoted by ’{’ and ’}’. A feature is a constant

and a value is a term.

2.1 Constrained Horn Clause (CHC)

The program clauses of cu-Prolog is called Constrained Horn Clause(CHC) and has the following forms: 1. H; C_{1}, ⋯, C_{n}. (Fact)

2. H : −B_{1}, ⋯, B_{m}; C_{1}, ⋯, C_{n}. (Rule)

3. : −B_{1}, ⋯, B_{n}; C_{1}, ⋯, C_{n}. (Question) H, B_{1}, ⋯, B_{n}, and C_{1}, ⋯, C_{n} are called Head, Body, and Constraint respectively. Horn clause is a special

case (null constraint) of CHC.

cu-Prolog allows a variable as an atomic formula. By the following programs, call/1 and not/1 are defined.

        call(X) :- X.
        not(X)  :- X, !, fail.
        not(_).

2.2 PST (Partially Specified Term)

cu-Prolog III supports PST (Partially Specified Term) as a data structure) to implement feature structures of unification-based grammars. PST is a term of the following form:

{l_{1}/t_{1}, l_{2}/t_{2}, …, l_{n}/t_{n}} . l_{i}, called label, is an atom and l_{i} ≠ l_{j}(i ≠ j). t_{i}, called value, is a term. Recursive PST structures are not allowed.

Unification between PSTs X and Y produces Z when:

• ∀l, l/v ∈ X, l ∉ Y → l/v ∈ Z

• ∀l, l/v ∈ Y, l ∉ X → l/v ∈ Z

• ∀l, l/v ∈ X, l/u ∈ Y → l/unify(u, v) ∈ Z

For example, the unification between {l/a,m/X} and {m/b,n/c} produces {l/a,m/b,n/c}.

When a PST occurs in plural places, it is printed with a new variable in the constraint part of CHC. For example,

     f(X) :- g1(_p1,X),g2(_p2,X); _p1={f/a,g/c}.

2.3 Canonical form of Constraint

In CHC, Constraint must be a canonical form called modular.

[Def] 1 (modular) A sequence of atomic formulas C_{1}, C_{2}, …, C_{m} is modular when

1. every argument of C_{i} is a variable (1 ≤ i ≤ m), and

2. no variable occurs in two distinct places, and

3. the predicates occurring in C_{i} are modularly defined (1 ≤ i ≤ m). □

The predicate occurring in the constraint of CHC is an ordinary Prolog predicate of the following form.

[Def] 2 (modularly defined) Predicate p is \underline{modularly defined}, when every body of its definition clause is modular or empty. □

With PST, modular is naturally extended as follows.

[Def] 3 (component) The component of an argument of a predicate is a set of labels to which the argument may bind. Here, an atom or a complex term is regarded as a PST of the label []. □

Cmp(p,n) stands for the component of the nth argument of a predicate p. Cmp(T) represents a set of labels of a PST T. In a constraint of the form X=t, variable X is regarded as taking Cmp(t).

Components can be computed by static analysis of the program [8]. Vacuous argument places[10] are arguments whose components are ϕ.

Consider the following example.

     c0({f/b},X,Y):-c1(Y,X).
     c0(X,b,_):-X={g/c},c2(X).
     c1(X,X).
     c1(X,[X|_]).
     c2({h/a}).
     c2({f/c}).

The components are computed as follows.

   Cmp(c0,1)={f,g,h}
   Cmp(c0,2)=Cmp(c1,2)={[]}
   Cmp(c0,3)=Cmp(c1,1)={}
   Cmp(c2,1)={f,h}

You can see each component with %d command of cu-Prolog. In the following example, Cmp(p3,1)={f,h}

and Cmp(p3,2)={g,h}.
_%d p3
%d +--------( p3/2 )-----[f.h|g.h]--2/2--+
p3({f/a},{g/b}).
p3({h/c},{h/d}).

[Def] 4 (dependency) A constraint has dependency when

1. a variable occurs in two distinct places where their components have common labels,

2. a variable occurs in two distinct places where one component is {[]} and another component does not contain [], or

3. the binding of an argument whose component is not ϕ. □

For example, when Cmp(p,1) = {f,g}, Cmp(q,1) = {h}, constraint p({f/b}) has a dependency, and p(X),q(X) and p({l/a,m/b}) do not have dependencies.

[Def] 5 (modular (with PST)) A constraint is modular when it contains no dependency. A Horn clause is modular when its body has no dependency. □

User-defined predicates in a constraint must be defined with modular Horn clauses

2.

2.4 BNF description of cu-Prolog

The following is a BNF description of the syntax of cu-Prolog . EUC code is available for Kanji.

< char > ::= < capital > | < small > | < digit > | < Kanji >
< charwhite > ::= < char > | < space >
< capital > ::= A|B|C| … |X|Y |Z
< small > ::= a|b|c| … |x|y|z
< digit > ::= 0|1|2|3|4|5|6|7|8|9
< series > ::= < digit > | < digit >< series >
< number > ::= < series > | < series > . < series >
< charseq > ::= < char > | < char >< charseq >
< cwseq > ::= < charwhite > | < charwhite >< cwseq >
< string > ::= ” < cwseq > ”
< smallseq > ::= < small > | < small >< charseq >
< capitalseq > ::= < capital > | < capital >< charseq >
< term > ::= < var > | < atom > | < smallseq > (< term list >)| < P ST >
< term list > ::= < term > | < term >, < term list >
< var > ::= < capitalseq > | < charseq > |
< atom > ::= < constant > | < string > | < number >
< constant > ::= < smallseq > |′ < cwseq >′
< P ST > ::= < pair list >

2For example, member/2, append/3, and finite predicates are defined with modular Horn clauses.

< pair list > ::= < pair > | < pair >, < pair list >
< pair > ::= < name > / < term >
< af > ::= < smallseq > (< term list >)| < smallseq > | < op term > | < var >
< af ist > ::= < af > | < af >, < af list >
< HORN > ::= < af > | < af >: − < af list > |?− < af list >
< CHC > ::= < horn > .| < horn >; < af list > .
< op term > ::= < op1 >< term > | < term >< op2 >< term >
< op1 > ::= not
< op2 > ::= <=> | = | = ..| > | >= | < | <= | ==

3 Summary of system commands

This section lists all the system commands from the top level of cu-Prolog . predicate represents predicate name or predicate name/arity.

3.1 Prolog commands

%h  help
# OS command execute OS command.
%d predicate  list definition clauses of a predicate
%d*  list all the program
%d/  list all predicate names include reduced predicates
%d?  list all predicate names without reduced predicates

for system predicates, +:recursive, ^:functor for user predicates, *:spied, -:reduced,+:recursive,

#: newly defined predicates during constraint transformation

%f  show free heap size
%G  static garbage collection
%Q  quit cu-Prolog
%R  reset cu-Prolog
%S  show statistics of the previous question
%c number  set maximum depth of resolution
%u  toggle switch to handle undefined predicates (ERROR/TRUE)

3.2 File I/O commands

"filename" consult file without echo back
"filename? consult file with echo back
%l filename set log file name
%l no  reset log file
%w filename write the current program to file

3.3 Debug commands

%p predicate switch (on/off) spy points on the predicate
%p *  set spy points on all the predicates
%p .  remove spy points of all the predicates
%p >  switch (set/remove) spy points on constraint transformation
%p ?  list spied predicates
%t  normal trace mode on/off switch
%s  step trace mode on/off switch

3.4 Constraint Transformation commands

%L  list derivation clauses of new predicates (in CT)
%a  all modular mode (in CT)
%o  M-Solvable mode (in CT)
%n predicate set new predicates name (in CT) (c0,c1,…)
%P predicate preprocess constraint parts
%P *  preprocess constraint parts of all the CHCs
%P ?  list predicates with non-canonical constraints

3.5 Other commands

%C redefine cat functor for JPSG parser

4 Built-in predicates, functors

This section lists built-in predicates and functors of cu-Prolog III. In the following table, + represents the input argument, - the output argument, PST the argument to take a PST.

4.1 Functional built-in predicates

These predicates work as functions.

Predicate Meaning

!/0  cut

abolish/2 abolish(P+,A+) Delete definition clauses of predicate P/A.

arg/3                arg(Pos+,T+,Arg-) Unify the Posth argument of T with Arg.
                     Eg: arg(2,test(a,b,c),X) --> X=b.
assert/1,2,3         assert(Head+),assert(Head+,Body+),assert(Head+,Body+,Cstr+)

Add Head:-Body;Cstr. in the end of the program.

asserta/1,2,3 add the clause in the beginning of the program. assertz/1,2,3 add the clause in the beginning of the program.

attach constraint/1  attach constraint(Cstr+) Add new constraint Cstr.

Cstr is a formula or list of formulas.

atom to str/2         atom to str(ATOM+,STR-)

convert an atom into a string.

close/1              close(F) close file pointer F

compare/3 compare(X+,Y+,C-) When X and Y are numbers or strings, C unifies with their relation. The relation is >,==, or <

                     Eg: compare("abc","xyz",'<')
                         compare(123,456,'<')
concat2/2            concat2(Str+,List-) List is a list of characters of the string Str
                     Eg: concat2("ab",["a","b"])

default default(X?,Y+,Z+) When PST X does not have features of PST Y, fails, otherwise, PST Z is added to X.

                     Eg: :- X={pos/p,sem/Y},default(X,{pos/p},{ajn/[],refl/[]}). makes
                     X={pos/p,ajn/[],refl/[],sem/Y}.
                         :- X={pos/n,sem/Y},default(X,{pos/p},{ajn/[],refl/[]}). fails.

divstr/4 divstr(X+,N+,Y-,Z-) Y unifies with the first N characters of string X and Z the rest. When N < 0, Y unifies with the last -N characters.

                     Eg: divstr("abcdefg",3,"abc","defg").
                         divstr("abcdefg",-2,"abcde","fg").
equal/2              equal(X,Y) unify X and Y

neq/2 neq(X,Y) fails when X and Y are unifiable eq/2 eq(X,Y) check X is equal to Y fail/0 always fails

functor/3            functor(T+,F,A) predicate name of term T is F/A.
geq/2                geq(X+,Y+) check X>=Y
greater/2            greater(X+,Y+) check X > Y

halt/0 quit cu-Prolog

leq/2                leq(X+,Y+) check X=<Y
less/2               less(X+,Y+) check X < Y

ml/2 univ. ml(T,L) is equivalent to T=..L.

L is a list of predicate name and arguments of term T.

                     Eg: ml(f(a,b,c),X) --> X=[f,a,b,c]
multiply/3           multiply(X+,Y+,Z-) is X * Y = Z

name/2(A,L) name(A+,L-) the name of the atom A is the list L

                     Eg: name(abc,[97,98,99]).

nl/0 write ‘\n’ op/3 op(P+,T+,Op+) Define operator Op as precedence P and type T.

P is a integer from 0 to 1000 and T is xf,yf,fx,fy,xfx,xfy, oryfx.

                     Eg: :-op(700,xfx,'=').
open/3               open(FileName+,Type+,FP-) Open a stream.

FileName is a file name. Type is r (read) or w (write).

FP is a corresponding file pointer.

pnames/2 pnames(PST+,FL) Unify the list of features of PST with FL.

                     Eg: pnames({l/a,m/b},[l,m]).
pvalue/3             pvalue(PST+,F+,V) Unify the value of feature F of PST with V.

When PST does not have feature F, it fails.

read/1 read(X-), read a term for the keyboard and unify it with X. read/2 read(X-,FP+) read a term form the file pointer FP and unify it with X.

When FP is the end of files, X unifies with end of file

reset timer/0  reset CPU timer(cf. timer/2)
retract/1,2,3        retract(Head+), retract(Head+,[Body+]),retract(Head+,[Body+],[Cstr+])

Delete a program clause that unifies with Head:-Body;Cstr.

Eg: retract(p(a)) deletes a unit clause p(a).

                        retract(f(X),[m(X,Y)]) deletes a rule f(X):-m(X,Y).
                        retract(f(X),[m(X,Y)],[c(Y)]) deletes a CHC f(X):-m(X,Y);c(Y).

see/1 see(F-) file F becomes the current input stream seen/0 close the current input stream strcmp/3 strcmp(X+,Y+,C-) Unify C with the relation between strings X and Y. (cf. compare/3)

C is >,==,or <

                     Eg: strcmp("abc","xyz",'<').
strlen/2             strlen(S+,L) L is the length of string S
                     Eg: strlen("abcdef",6).

substring/3 substring(X+,N+,Y-) Unify Y with more than Nth characters of string X (When N < 0, Y unifies with the last -N characters of X.)

                     Eg: substring("abcdefg",3,"defg")
                         substring("abcdefg",-3,"efg").

substring/4 substring(X+,N+,L+,Y-) Unify Y with L characters from Nth element of string X.

                     Eg: substring("abcdefg",3,2,"de")
                         substring("abcdefg",-3,2,"ef").

sum/3                sum(X,Y,Z) compute X + Y = Z

(More than one argument must be bound.)

tab/0 print tab tab/1 tab(FP+) print tab to file pointer FP tell/1 tell(T+) file T becomes the current output stream

timer/2              timer(X-,Y-) X unifies with CPU time after the last reset timer.

Y unifies with CUP time used in the constraint transformation in X

told/0 close the current output stream made by tell/1 true/0 always succeeds unbreak/0 return to the break point in the step trace. var/1 var(T) T is a free variable

write/1              write(T) write term T

4.2 Predicative built-in predicates

These predicates may have many solutions by backtracking.

PREDICATE MEANING

clause/3             clause(T+,Body-,Cstr-) There is a program clause Head:-Body;Cstr.

where Head unifies with T.

concat/3             concat(S1+,S2+,S-) or concat(S1-,S2-,S+)

string S is a concatenation of S1 and S2.

                     Eg: concat("ab","cd",S) --> S="abcd"
                         concat(X,Y,"abc") -->
                         X="",Y="abc" or X="a",Y="bc" or X="ab",Y="c" or X="abc",Y=""

count/1 count(X-) Every time, X unifies with a different number (X=0,1,2,⋯). execute/1 execute(L+) Execute goals given in a list L

                     Eg: execute([memb(X,[a,b]),memb(X,[b,c])])

gensym/1 gensym(X-) Every time, X unifies with a different string.

%n command can change the seed of the string(default value is c).

isop/3 isop(Prec,Type,OP) Prec and Type is a precedence and type of the operator OP.

                     Eg: :-isop(X,Y,Z). --> X=900, Y=xfy, Z='/' etc.
memb/2               member(Atom,List+) built-in member predicate
apnd/3               apnd(List,List,List+) or apnd(List+,List,List)

built-in append predicate (The first or third argument must be bound to a list.)

or/2,3,4,5 Execute plural goals.

                     Eg: :-or(memb(X,[a,b]),memb(X,[j,k])).
                         --> X=a,b,j,k

4.3 Built-in predicates for constraint transformation

The following are special built-in predicates for constraint transformation.

Predicate Meaning

condname/2           condname(Cstr+,PL-) Unify list of predicate names in Cstr with PL.
                     Eg: condname([f(a,b),g(c,d)],[g,f])

pcon/0 Print current constraints.

project cstr/1       project cstr(Term+) Print current constriants

which corresponds to the variables in Term.

project cstr/2       project cstr(Term+,Var-) Bind current constriants

which corresponds to the variables into Var. unify/2 unify(C+,NC-) Transform constraint C into NC.

Here, C and NC are list of atomic formulas.

                     Eg: unify([member(X,[a,b,c]),f(X,Y)],[c0(X,Y)])

4.4 Built-in predicates for JPSG parser

The followings are special built-in predicates for JPSG parser.

Predicate/Functor Meaning cat/6 Functor for the feature structure of JPSG t(M,L,R) Functor for history tree(H) Print history H in tree format

cat/6 functor is set by %C command from the top level of cu-Prolog as follows.

%C [F eature_{1},F T ype_{1},F eature_{2},F T ype_{2},…]

Here, F eature_{i} is a feature name which begin with a capital letter and be shorter than five letters. F T ype_{i} is a feature type defined as follows.

FType Meaning 2 takes one category (adjacent,slash, etc.) 3 takes set of categories (subcat, etc.) 1 otherwise

   Default value is [POS,1,FORM,1,AJA,2,AJN,2,SC,3,SEM,1], that is,

Feature PSG features POS pos FORM gr,vform,pform, and so on AJA adjacent AJN adjunct SC subcat SEM sem

By tree/3, functor cat(Arg_{1},⋯,Arg_{n}) is printed as

Arg_{1}[Arg_{2}, F eature_{3}:Arg_{3}, ⋯, F eature_{n−1}:Arg_{n−1}]:Arg_{n}

Features of null values ([]) are not printed.

[Def] 6 (History) History is defined as follows.

• A category is a history

• If C and W are categories, then t(C,W,[ ]) is a history.

• If L and R are histories and M is category, then t(M,L,R) is a history.

• If L and R are histories, and C and W are categories, then t(t(C,W,[ ]),L,R) is a history. □

   tree(t(C,W,[ ])) writes
     C--W

and tree(t(M,L,R)) writes
     ---M
      |
      |-L
      |
      |-R

5 File I/O

5.1 Read a program

• Start cu-Prolog from OS with reading an initial file:

         cuprolog filename [CR]

• Read a file in the top level of cu-Prolog without echo back: "filename" [CR]

• Read a file in the top level of cu-Prolog with echo back:

"filename? [CR]

5.2 Save a program

To save current program clauses to a file in the top level of cu-Prolog ,

%w filename [CR]

5.3 Log file

• Set log file :

%l filename [CR]

• End log file :

         %l no [CR]

6 Constraint Transformation

6.1 Use constraint transformer alone

You can use the constraint solver (transformer) of cu-Prolog alone in the following two ways. 6.1.1 ‘@’ command First, from the top level of cu-Prolog , type ‘@’ followed by a sequence of atomic formulas and a period. For example, by typing as follows,

     @ member(X,[a,b,c]),member(X,[b,c,d]).  [CR]

Then, cu-Prolog returns the equivalent modularly defined constraint and its definitions.

6.1.2 unify/2 predicate

Second, you can use the constraint transformation routine as a Prolog procedure. cu-Prolog has the predicate unify(OldCond, NewCond). unify/2 takes constraints as a list of literals as follows.

     [c0(X,Y), c1(P,Q,R), c2(Q,S)]

unify/2 succeeds iff OldCond is instantiated to a constraint and NewCond is a free variable. NewCond is instantiated to the modularly defined constraint that is equivalent to OldCond.

6.2 Transformation operations

cu-Prolog uses three sets for the constraint transformation.

DEFINITION set of derivation clauses of new predicates

NON-MODULAR set of non-modular new clauses made by unfolding

MODULAR set of modular clauses made by unfolding.

Let C be a non-modular constraint, and X_{1}, ⋯, X_{n} be different variables in C, p be a new n-ary predicate. The constraint transformer of cu-Prolog adds

     p(X_{1},· · ·,X_{n})==C.

in DEFINITION, and repeat following three basic transformation operation until DEFINITION and NON-MODULAR become empties. After that, clauses in MODULAR are newly defined program clauses and C is transformed into p(X_{1}, ⋯, X_{n}).

When transformations fail on the way, C is not transformed into the modular form.

1. unfolding Remove one clause H : −L, R. from NON-MODULAR or DEFINITION where L is a atomic formula and R is a sequence of atomic formulas. There are program clauses P_{i} : −B_{i} (P_{i}θ_{i} = Lθ_{i}, i = 1, …, n.) Add Hθ : −B_{i}θ, Rθ (i = 1, …, n) to NON-MODULAR or MODULAR in accordance with the modularity of their bodies.

2. folding Remove one clause H : −B, D. from NON-MODULAR, where

• B and D have no variable dependency.

• There is a clause P == Q in DEFINITION and Qθ = B

Then, add H : −P θ, D. in NON-MODULAR.

3. modularize Remove one clause H : −B_{1}, ⋯, B_{n}, R from NON-MODULAR. Here,

• B_{i}(i = 1, ⋯, n) and R are sequences of atomic formulas.

• B_{i} and B_{j} (i ≠ j) have no variable dependency.

• R is modular.

Let each B_{i} contains variable X_{i,1}, ⋯, X_{i,m_{i}} and p_{i} be a new m_{i}-ary predicate and P_{i} = p_{i}(X_{i,1}, ⋯, X_{i,m_{i}}) (i = 1, ⋯, n). Then, add P_{i} == B_{i}. to DEFINITION (i = 1, ⋯, n) and H : −P_{1}, ⋯, P_{n}, R to MODULAR.

6.3 Heuristics

Constraint transformation of cu-Prolog is executed in the following way.

1. If DEFINITION is not empty, remove one clause C from DEFINITION and unfold it.

2. If DEFINITION is empty, remove one clause D whose head has different variables as arguments, and unfold it.

3. Otherwise, select one clause N in NON-MODULAR and fold or modularize it.

4. repeat above until NON-MODULAR and DEFINITION are both empty.

Then, we have to consider

• how to select a clause from DEFINITION,

• how to select a clause from NON-MODULAR, and

• how to select a literal in unfolding.

As DEFINITION and NON-MODULAR are implemented as stacks in the current cu-Prolog, cu-Prolog selects the latest clause.

In unfolding, cu-Prolog selects the literal of the highest activation value which is calculated as :

AV = 3 ∗ Const + 2 ∗ F unct + V num − Defs + Units − 2 ∗ Rec + 3 ∗ F acts

. Here,

Arity = arity of the literal
Const = the number of arguments which bind to atoms
V num = sum of the occurrence of variables which occurs in the literal
F unct = the number of arguments which bind to complex terms
Rec = 1 for recursive predicate, else 0
Defs = the number of definitions of its predicate
Units = the number of unit definitions of its predicate
F acts = 1 if all definitions of its predicate are unit clauses, else 0

6.4 Example

This subsection shows some example in the constraint transformer of cu-Prolog III. 6.4.1 Symbolic and combinatorial constraint Predicates member/2 and append/3 are frequently used as a symbolic and combinatorial constraints. The following example transforms non-modular constraints into modular ones.

tsuda@icot21[5] cup3              % start cu-Prolog from UNIX
*****  cu - Prolog   Ver. III  *****
Copyright: Institute for New Generation Computer Technology,  Japan 1989-91
in Cooperation with SIRAI@sccs.chukyo-u.ac.jp
All Modular mode (help ->  %h)
_member(X,[X|Y]).                 % definition of member/2

_member(X,[Y|Z]):-member(X,Z).
_append([],X,X).                  % definition of append/3
_append([A|X],Y,[A|Z]):-append(X,Y,Z).
_@ member(X,[a,b,c]),member(X,[b,c,d]).    % User's constraint input 1
solution = c0(X_0)                % Equivalent and modular constraint
c0(b).                            % New predicates made in the transformation
c0(c).
CPU time = 0.017 sec (Constraints Handling = 0.000 sec)
_@ member(X,[a,b,c]),member(X,[j,k,l]).    % User's constraint input 2
solution = fail.                  % Transformation fails.
CPU time = 0.017 sec (Constraints Handling = 0.000 sec)
_@ member(A,X),append(X,Y,Z).            % User's constraint input 3
solution = c2(X_1, Y_2, Z_3, A_0)     % Equivalent and modular constraint
c4(V0_0, V1_1, V2_2, [V0_0 | V3_3]) :- append(V1_1, V2_2, V3_3).  % New predicates
c3(V0_0, V1_1, V2_2, [V0_0 | V3_3], V4_4) :- c2(V1_1, V2_2, V3_3, V4_4).
c2([V0_0 | V1_1], V2_2, V3_3, V0_0) :- c4(V0_0, V1_1, V2_2, V3_3).
c2([V0_0 | V1_1], V2_2, V3_3, V4_4) :- c3(V0_0, V1_1, V2_2, V3_3, V4_4).
CPU time = 0.050 sec (Constraints Handling = 0.000 sec)

6.4.2 Disjunctive feature unification

By introducing PST, cu-Prolog III can treat disjunctive feature structures which are frequently used in unification-based grammar formalisms. For example, the following disjunctive feature structures [1]:

[ a = \{ \begin{matrix}[ & \begin{matrix}b = + \\ c = − \end{matrix} & ] \\ [ & \begin{matrix}b = − \\ c = + \end{matrix} & ] \end{matrix} \} ] and [ \begin{matrix}a = [ b = < d > ] \\ d = [ ] \end{matrix} ]

These disjunctive feature structures are encoded in the two constrained PSTs, X={a/U},s(U) and Y={a/{b/V},d/V}, where

  s({b/+,c/-}).     % definition of s/1
  s({b/-,c/+}).

PST unification between X and Y is to transform the constraint X=Y={a/U,d/V},U={b/V},s(U) into the modular form as follows.

*****  cu - Prolog   Ver. III  *****
Copyright: Institute for New Generation Computer Technology,  Japan 1989-91
in Cooperation with SIRAI@sccs.chukyo-u.ac.jp
All Modular mode (help ->  %h)
_s({b/'+',c/'-'}).           % Define disjunction as predicate s/1
_s({b/'-',c/'+'}).
_@ X={a/U},s(U),X={a/{b/V},d/V}.     % Disjunctive unification (input)

solution = c0(X_0, V_2, {a/{b/V_2}, d/V_2}, U_1, {a/U_1})  % Equivalent modular form
c0(_p1, '+', _p1, {b/'+', c/'-'}, _p1);_p1={a/{b/'+', c/'-'}, d/'+'}. % new predicate
c0(_p1, '-', _p1, {b/'-', c/'+'}, _p1);_p1={a/{b/'-', c/'+'}, d/'-'}.
CPU time = 0.000 sec (Constraints Handling = 0.000 sec)
_:-c0(X,_,_,_,_).              % Solve new constraint.
  X = {a/{b/'+', c/'-'}, d/'+'};           % Solution 1
  X = {a/{b/'-', c/'+'}, d/'-'};           % Solution 2
no.
CPU time = 0.000 sec (Constraints Handling = 0.000 sec)

After the transformation, X (result of the unification) is still constrained by c0(X, , , , ). To see what value X takes, you have to solve the constraint as above. In this example, X still has a disjunction because it may bind to two PSTs {a/{b/+, c/-}, d/+} or {a/{b/-, c/+}, d/-}.

7 Program trace

7.1 Set spy points

%p *  set spy points on all the predicates.
%p .  remove spy points on all the predicates.
%p predicate switch (set/remove) the spy point on the predicate
%p >  switch (set/remove) the spy point on the unfold/fold transformation.
%p ?  list spied predicates.

7.2 Set trace flag

There are two trace modes of spied predicates.

%s switch step (interactive) trace (on/off). In this mode, the prompt is ‘>’.
%t switch normal trace (on/off). In this mode, the prompt is ‘$’.

In the step trace mode, the user suggests the next action at spy points.

INPUT ACTION

[CR] continue s skip tracing a print ancestor goals. b break. Go to cu-Prolog temporally.

By :-unbreak, user can return to this point.

f fail this goal. l leap. skip until this goal ends. z quit refutation

7.3 Trace of constraint transformation

To trace constraint transformation, first spy constraint transformation by %p >, then type %t for the normal trace and %s for the step trace.

7.3.1 Print traces

Clauses in DEFINITION (derivation clauses of new predicates) are printed as follows.

[Clause Number(Status,Number of Definitions)] Derivation Clause

     [1(d,0)] c0(X) <=> member(X,[a,b,c]). (Example)

Here, Status is:

Status Function r removed: clause (other than f and g) removed in unfolding d derivation: derivation clauses not unfolded g registered: unfolding of this clauses yields at least one unit clause. f false registered: unfolding of this clause fails

Clauses in NON-MODULAR or MODULAR are printed as follows.

<Clause Number(Status,Number of Definitions)> Clause

     <2(u)> c0(X):-member(X,[b,c]). (Example)

Here, Status is defined as follows.

Status Function r removed: clause removed by reduction or unfolding u untouched: clause in NON-MODULAR that is not unfolded m modular: clause whose body is modular i unit: unit clause

7.3.2 User’s input in the step trace

In the step trace, the user have to suggest the next action after spy points.

Input Function

[CR] continue: continue with default heuristics. u CN LN manual unfolding: CN is a clause number,

and LN suggests which literal to unfold in the body.

s stop tracing: notrace after that n stop step tracing: normal trace after that q quit transformation: assert current clauses and stop transformation. z abort transformation: delete all the new clauses and stop transformation

8 JPSG parser

In JPSG parser, CHC plays two effective roles.

8.1 Encoding Lexical Ambiguity

As an example of the disjunctive feature structures, this subsection explains lexical ambiguities in this subsection. Consider the lexicons of homonyms or polysemic words. If the lexicon of an ambiguous word is divided into plural entries in terms of its ambiguity, the parsing process may be inefficient in that it sometimes backtracks to consult the lexicon. In constraint-based natural language processing, such ambiguity is packed as a constraint in a lexicon.

Below is a sample lexicon of Japanese auxiliary verb “reru.” “reru” follows a verb whose inflection type is vs or vs1. If the adjacent verb is transitive, “reru” indicates plain passive. If the verb is intransitive, “reru” indicates affective passive ^{3}. These combinations are represented by adding constraints of reru form/1 and reru sem/4 in one lexical entry.

3For example, “Ken ga ame ni fu-ra-reru” (Ken is affected by the rain.)

%% lexical entry of ``reru''  (CHC of null body)
lex(reru,{sc/SC, sem/Sem, adjacent/{pos/v,infl/I,sc/VSC,sem/Sem}});
     reru_form(I),               % inflection (constraint)
     reru_sem(VSC,Vsem,SC,Sem).  % combination of subcat and sem (constraint)
%%%%%% definition of predicates of constraints  %%%%%%
reru_form(vs).  % inflection type of the adjacent verb
refu_form(vs1).
reru_sem([{form/ga,sem/Sbj}],Sem,   % for intransitive (affective) passive
         [{form/ga,sem/A},{form/ni,sem/Sbj}],
         affected(A,Sem)).
reru_sem([{form/ga,sem/Sbj},{form/wo,sem/Obj}], Sem,    % for transitive (normal) passive
         [{form/ga,sem/Obj},{form/ni,sem/Sbj}], Sem).

This lexicon is a representation of the following disjunctive feature structure.

[ \begin{matrix}\{ & \begin{matrix}[ & \begin{matrix}adjc = [ \begin{matrix}sc = ⟨ [ \begin{matrix}pos = ga \\ sem = S1 \end{matrix} ] ⟩ \\ sem = Sem1 \end{matrix} ] \\ sc = ⟨ [ \begin{matrix}form = ga \\ sem = A \end{matrix} ] , [ \begin{matrix}form = ni \\ sem = S1 \end{matrix} ] ⟩ \\ sem = affected(A, Sem1) \end{matrix} & ] \\ [ & \begin{matrix}adjc = [ \begin{matrix}sc = ⟨ [ \begin{matrix}pos = ga \\ sem = S2 \end{matrix} ] , [ \begin{matrix}pos = wo \\ sem = O2 \end{matrix} ] ⟩ \\ sem = Sem2 \end{matrix} ] \\ sc = ⟨ [ \begin{matrix}pos = ga \\ sem = O2 \end{matrix} ] , [ \begin{matrix}pos = ni \\ sem = S2 \end{matrix} ] ⟩ \\ sem = Sem2 \end{matrix} & ] \end{matrix} & \} \\ adjc = [ \begin{matrix}pos = v \\ infl = \{vs1, vs2\} \end{matrix} ] \end{matrix} ]

Although the lexicon is ambiguous, however, many kinds of constraints are automatically accumulated for solving during parsing. The disambiguation process in parsing is naturally realized by the constraint transformation of cu-Prolog. It has no need to write any special procedure for disambiguation.

8.2 Encoding Structural Principle

As mentioned in Section 2, the structural principles of JPSG are relations among features of three categories in a local tree. Intuitively, structure principles are encoded as constraints to a phrase structure rule:

psr(M, D, H); sp_{1}(M, D, H), …, sp_{n}(M, D, H).

Here, psr/3 is a phrase structure rule and each sp_{i}/3 is a structure principle.

In cu-Prolog, these structural principles are evaluated flexibly with heuristics. In Prolog, however, above phrase structure rule is represented as

psr(M, D, H) : −sp_{1}(M, D, H), …, sp_{n}(M, D, H).

Each principle is always evaluated sequentially. Prolog, therefore, is not well-suited for constraint based grammars because it is impossible to stipulate in advance which kind of linguistic constraints must be processed in what order.

As the first example, the principle of the sem feature in Section 2 is encoded as a constraint sfp(M,D,H), where

  sfp({sem/HS},{mod/+},{sem/HS}).
  sfp({sem/HS},{mod/+},{sem/HS}).

As the second example, the Foot Feature Principle is defined as follows[2].

The value of FOOT feature of the mother unifies with the union of those of her daughters.

It is represented as constraint ffp(M,D,H), where

 ffp({foot/MF},{foot/DF},{foot/HF}) :-
     union(DF,HF,MF).

8.3 Example

Following example of JPSG parser in cu-Prolog treats two sentences.

The following sentence is not ambiguous, so the top category does not have constraints on the sem feature.

Ken-ga Naomi-wo ai-suru. Ken-NOM Noami-DAT love-PRES ‘Ken loves Naomi.’

As the following sentence is ambiguous, that is, “Ken-ga (someone wo) ai-suru” or “Ken ga ai-suru (someone)” (relative clause), the top category has constraint (c31).

Ken-ga ai-suru. Ken-NOM love-PRES ‘Ken loves (someone).’ or ‘(Someone) whom Ken loves’

tsuda#icot21[5]% cup3 %% Start cu-Prolog
*****  cu - Prolog III  *****
Copyright: Institute for New Generation Computer Technology,  Japan 1989-91
in Cooperation with SIRAI@sccs.chukyo-u.ac.jp
M-solvable mode (help ->  %h)
_"jpsg/j4.p" %% read JPSG parser program
=== open 'jpsg/j4.p'
****** end of file *******
CPU time = 2.050 sec
%%%%% Example1. ``Ken-ga Naomi-wo ai-suru''(Ken loves Naomi.) %%%%%%
_:-p([ken,ga,naomi,wo,ai,suru]). %% Input
%% The parser returns the parse tree.
{sem/[love,ken,naomi], core/{form/Form_3670, pos/v}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[suff_p]
|
|--{sem/[love,ken,naomi], core/{form/vs2, pos/v}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[subcat_p]
|   |
|   |--{sem/ken, core/{form/ga, pos/p}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[adjacent_p]
|   |   |
|   |   |--{sem/ken, core/{form/n, pos/n}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[ken]
|   |   |
|   |   |__{sem/ken, core/{form/ga, pos/p}, sc/[], refl/[], slash/[],
   psl/[], ajn/[], ajc/[{sem/ken, core/{pos/n}, sc/[], refl/ReflAC_140}]}---[ga]
|   |
|   |__{sem/[love,ken,naomi], core/{form/vs2, pos/v}, sc/[{sem/ken, core/{form/ga, pos/p}}],
        refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[subcat_p]
|       |
|       |--{sem/naomi, core/{form/wo, pos/p}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[adjacent_p]
|       |   |
|       |   |--{sem/naomi, core/{form/n, pos/n}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[naomi]
|       |   |
|       |   |__{sem/naomi, core/{form/wo, pos/p}, sc/[], refl/[], slash/[],
  psl/[], ajn/[], ajc/[{sem/naomi, core/{pos/n}, sc/[], refl/ReflAC_960}]}---[wo]
|       |
|       |__{sem/[love,ken,naomi], core/{form/vs2, pos/v}}---[ai]
|
|__{sem/[love,ken,naomi], core/{form/Form_3670, pos/v}, sc/[],
   refl/[], slash/[], psl/[], ajn/[], ajc/[{sem/[love,ken,naomi],
   core/{form/vs2, pos/v}, sc/[], refl/ReflAC_3702}]}---[suru]

category= {sem/[love,ken,naomi], core/{form/Form_3670, pos/v},
sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]} %% Top category
constraint= syu_ren(Form_3670) %% Constraints on the top category
true.
CPU time = 0.750 sec
19%(program) 6%(pst/const) 12%(string)

%%%%% Example2. ``Ken-ga ai-suru''(Ken loves). %%%%%
_:-p([ken,ga,ai,suru]). %% Input
{sem/[love,Sbj_394,Obj_396], core/{form/Form_1056, pos/v},sc/Msc_1128,
     refl/Mref_1130, slash/Msl_1132, psl/[], ajn/[], ajc/[]}---[suff_p]
 |
 |--{sem/[love,Sbj_394,Obj_396], core/{form/vs2, pos/v}, sc/Csc_1102,
     refl/Cref_1104, slash/Csl_1106, psl/[], ajn/[], ajc/[]}---[subcat_p]
 |   |
 |   |--{sem/ken, core/{form/ga, pos/p}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[adjacent_p]
 |   |   |
 |   |   |--{sem/ken, core/{form/n, pos/n}, sc/[], refl/[], slash/[], psl/[], ajn/[], ajc/[]}---[ken]
 |   |   |
 |   |   |__{sem/ken, core/{form/ga, pos/p}, sc/[], refl/[], slash/[],
     psl/[], ajn/[], ajc/[{sem/ken, core/{pos/n}, sc/[], refl/ReflAC_140}]}---[ga]
 |   |
 |   |__{sem/[love,Sbj_394,Obj_396], core/{form/vs2, pos/v}}---[ai]
 |
 |__{sem/[love,Sbj_394,Obj_396], core/{form/Form_1056, pos/v}, sc/[],
     refl/[], slash/[], psl/[], ajn/[], ajc/[{sem/[love,Sbj_394,Obj_396],
     core/{form/vs2, pos/v}, sc/[], refl/ReflAC_1116}]}---[suru]
category= {sem/[love,Sbj_394,Obj_396], core/{form/Form_1056, pos/v},
          sc/Msc_1128, refl/Mref_1130, slash/Msl_1132, psl/[], ajn/[], ajc/[]}
constraint= c31(Cref_1104, Mref_1130, Csl_1106, Msl_1132, Csc_1102,
         Msc_1128, Obj_396, Sbj_394, HC_222, Hsl_226),syu_ren(Form_1056)
true.
CPU time = 0.367 sec
20%(program) 2%(pst/const) 13%(string)
%% solve constraints of the top category (c31)
_:-c31(_,Refl,_,Slash,_,SC,Obj,Sbj,_,_).
  Refl = []  Slash = []  SC = [{sem/V0_36, core/{form/wo, pos /p}}]
Obj = V0_36  Sbj = ken;    %% First solution: subcat remains.
  Refl = []  Slash = [{sem/V3_58}]  SC = []  Obj = V3_58  Sbj = ken;
%% Second solution: One element moves from subcat to slash.
no.
CPU time = 0.050 sec
20%(program) 0%(pst/const) 13%(string)
_

9 Concluding Remarks

UNIX version of cu-Prolog is implemented from 1989 by Hiroshi TSUDA and Kôiti HASIDA with financially supported by ICOT. Apple Macintosh version (MacCUP) and MS-DOS version (DJCUP) are implemented by Prof. Hidetosi SIRAI of Chukyo University. The author thanks to the members of PSG working group of ICOT for their comments and cooperation to the JPSG parser.

Lastly, we show references for cu-Prolog and JPSG parser.

cu-Prolog originated from the technique conditioned(constrained) unification[5, 3]. The name “cu” comes from this technique. [11, 13] discussed cu-Prolog from the viewpoint of the constraint logic programming, [12, 10] from parsing JPSG.

Dr.Hasida proposes DP(Dependency Propagation) theory [4] for further research of cu. Related paper with cu are [10, 6].

[8, 9] treat disjunctive feature structures by introducing PSG(Partially Specified Term) in cu-Prolog. We refer [2] and [7] for JPSG and general unification-based grammars respectively.

References

[1] Andreas Eisele and Jochen Dörre. Unification of Disjunctive Feature Descriptions. In Proc. of 26th Annual Meeting of ACL, pages 286–294, June 1988.

[2] Takao GUNJI. Japanese Phrase Structure Grammar. Reidel, Dordrecht, 1986.

[3] Kôiti HASIDA. Conditioned Unification for Natural Language Processing. In Proceedings of the 11th International Conference on Computational Linguistics, pages 85–87, 1986.

[4] Kôiti HASIDA. Common Heuristics for Parsing, Generation, and Whatever. In Workshop on Reversible Grammar in Natural Language Processing, Berkeley, 1991.

[5] Kôiti HASIDA and Hidetosi SIRAI. Jyokentsuki Tan’itsu-ka (Conditioned Unification). Computer Software, 3(4):28–38, 1986. (in Japanese).

[6] Kôiti HASIDA and Hiroshi TSUDA. Parsing without Parser. In Proc. of Second International Workshop on Parsing Technologies, pages 1–10. Sigparse ACL, February 1991.

[7] Stuart M. Shieber. An Introduction to Unification-Based Approach to Grammar. CSLI Lecture Notes Series No.4. Stanford:CSLI, 1986.

[8] Hiroshi TSUDA. Disjunctive feature structure in cu-prolog. In 8th Conf. Proc. Japan Soc. Softw. Sc. Japan., pages 505–508, 1991. (in Japanese).

[9] Hiroshi TSUDA. cu-Prolog for Constraint-Based Grammar. In Proceedings of Fifth Generation Computer System, 1992.

[10] Hiroshi TSUDA and Kôiti HASIDA. Parsing as Constraint Transformation – an Extension of cu-Prolog. In Proceedings of the Seoul International Conference on Natural Language Proccesing, pages 325–331, 1990.

[11] Hiroshi TSUDA, Kôiti HASIDA, and Hidetosi SIRAI. cu-Prolog and its application to a JPSG parser. In K.Furukawa, H.Tanaka, and T.Fujisaki, editors, Logic Programming ’89, pages 134–143. Springer-Verlag LNAI-485, 1989.

[12] Hiroshi TSUDA, Kôiti HASIDA, and Hidetosi SIRAI. JPSG Parser on Constraint Logic Programming. In Proc. of 4th ACL European Chapter, pages 95–102, 1989.

[13] Hiroshi TSUDA, Kôiti HASIDA, and Hidetosi SIRAI. Parsing as Constraint Satisfaction — an Application of cu-Prolog. In 6th Conf. Proc. Japan Soc. Softw. Sc. Japan., pages 257–260, 1989.