Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!vsi1!altnet!uunet!munnari!mulga!lee
From: lee@mulga.oz (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: Grammar rule translator.
Message-ID: <2924@mulga.oz>
Date: 28 Jul 88 23:35:43 GMT
References: <196@quintus.UUCP> <4751@csli.STANFORD.EDU> <202@quintus.UUCP>
Reply-To: lee@mulga.UUCP (Lee Naish)
Organization: Comp Sci, Melbourne Uni, Australia
Lines: 39

In article <202@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
>When compiled with the current Quintus Prolog compiler,
>	p(..., S0, S) :- 'C'(S0, X, S1), ...
>and
>	p(..., [X|S1], S) :- ...
>run at the same speed.

That is because (correct me if I am wrong) Quintus currently indexes
only on the top level functor of the first argument.

This has several consequences:
	1) there is no point is pushing back 'C'
	2) the most naturally written grammars are not efficient
	3) grammars are rewritten so that simple indexing is effective
		p --> "+"...
		p --> "-"...
	   is rewritten
		p --> [X], p1(X).
		p1(0'+) --> ...
		p1(0'-) --> ...
	4) it is best to put S0 (and S) after other arguments

In NU-Prolog 'C' is pushed back (when its definitely safe to do so) and
it is possible to do indexing on subterms of any argument:
	?- p(..., [X|S1], S) when X.
will cause indexing on X (it also delays calls to p until X is
instantiated, so the grammar cannot be used as a generator).  It would
seem like a good idea to do that kind of indexing on DCG rules by
default.

Anyway, the fact that most Prolog systems currently don't have good
indexing and some people write INELEGANT grammars (:-) is not a good
reason for a standard DGC translator to convert decent grammars into
code which decent compilers can't take advantage of, though, if you can
understand this sentence without backtracking, you probably don't need
the advantage of simpler grammars so you can write grammars which don't
backtrack using Quintus Prolog DGCs.

	lee