Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!van-bc!ubc-cs!fornax!han
From: han@fornax.UUCP (Jiawei Han)
Newsgroups: comp.lang.prolog
Subject: Re: mutual recursion query
Summary: another interesting example
Message-ID: <792@fornax.UUCP>
Date: 6 Jun 90 23:54:39 GMT
References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP> <3164@goanna.cs.rmit.oz.au>
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 83

In article <3164@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
> In article <718@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) wrote
> in response to my question about transforming mutual recursion.
> The bottom line was that transforming mutual recursion into linear
> recursion permits the use of a transitive closure algorithm.
> 
> The question is, when is this a good idea?
> 
> Consider a grammar written in Datalog.  For example,
> 	s --> np(P,N,nom), vp(P,N).
> 	np(P,N,C) --> word(X), {pronoun(X,P,N,C)}.
> 	np(3,N,_) --> word(the), word(X), {noun(X,N)}, opt_rel.
> 	opt_rel --> word(that), vp(_,_).
> 	opt_rel --> [].
> 	vp(P,N) --> word(X), {intrans(X,P,N)}.
> 	vp(P,N) --> word(X), {trans(X,P,N)}, np(_,_,acc).
> 
> Here the EDB would be the lexicon
> 	pronoun(i,  1,s,nom).
> 	pronoun(me, 1,s,acc).
> 	...
> and the input sentence
> 	word(the,0,1). word(cat,1,2). word(that,2,3). ...
> 
> The top level query might be
> 	?- s(0, X).
> 
......

This is another interesting exmaple to show the compilation method works
well.  Let me try it.  I write the grammar as follows.

	s :- np(P,N,nom), vp(P,N).

	np(P,N,C) :- pronoun(X,P,N,C).
	np(P,N,_) :- word(the), noun(X,N), opt_rel.
	opt_rel :- word(that), vp(_,_).
	opt_rel :- [].

	vp(P,N) :- intrans(X,P,N).
	vp(P,N) :- trans(X,P,N), np(_,_,acc).

The transformation can be performed as follows:

In this rule set, the mutually recursive predicates are np//3 and vp//2.
We first remove the intermediate predicate: opt_rel//0.

	s :- np(P,N,nom), vp(P,N).

	np(P,N,C) :- pronoun(X,P,N,C).
	np(P,N,_) :- word(the), noun(X,N).
	np(P,N,_) :- word(the), noun(X,N), word(that), vp(_,_).

	vp(P,N) :- intrans(X,P,N).
	vp(P,N) :- trans(X,P,N), np(_,_,acc).

Clearly, np is defined by the following rule set (with no mutual
recursion):

	np(P,N,C) :- pronoun(X,P,N,C).
	np(P,N,_) :- word(the), noun(X,N).
	np(P,N,_) :- word(the), noun(X,N), word(that), intrans(Y,P,M).
	np(P,N,_) :- word(the), noun(X,N), word(that), trans(Y,P,M), np(_,_,acc).

Then there is no difficulty to compile the rule set into a transitive 
closure:

exit-portion(C) = pronoun(X,P,N,C) U (word(the), noun(X,N)) U (word(the), noun(X,N), word(that), intrans(Y,P,M)
np(P,N,norm) = exit-portion(norm) U ((word(the), noun(X,N'), word(that), trans(Y,P',M))+ , exit-portion(acc)).

Similarly, we can derive the formula for vp.  Therefore, s can be generated
accordingly, which can be processed by transitive closure algorithms.

Actually, not all the linear mutual recursions are transformable into 
transitive closure operations although I believe more than 90% 
application examples are.  Even if they are not, they should be able 
to be transformed into relatively simple linear recursive programs 
containing no mutually recursive predicates (as I discussed in my 
technical report).  I wish that I can get a counter-example (real 
example, not those can never find semanitc explanations) to show 
that my method may have some difficulties.

-jiawei