Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!samsung!munnari.oz.au!bruce!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: mutual recursion query
Message-ID: <3164@goanna.cs.rmit.oz.au>
Date: 6 Jun 90 06:08:50 GMT
References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP> <3072@goanna.cs.rmit.oz.au>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 44

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).

(Note that because I used word(X) instead of [X] there are no actual
lists involved.)

Here we have a mutual recursion between np//3, opt_rel//0, and vp//2.
I have no difficulty at all in believing that some bottom-up query
evaluators might be able to handle this parsing problem efficiently.
(If someone who is really at home with magic sets would care to explain
what the magic sets method would do with this example I would be grateful.)
But I don't see how turning the example into simple linear recursion would
help.  _Would_ it?

The practical question is whether "real" mutual recursions are more like
my thinly-disguised ancestor example or more like this one.  "Parts 
explosion" is more like ancestor, but is that the most useful case?

-- 
"A 7th class of programs, correct in every way, is believed to exist by a
few computer scientists.  However, no example could be found to include here."