Path: utzoo!attcan!uunet!husc6!bloom-beacon!tut.cis.ohio-state.edu!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Grammar rule translator.
Message-ID: <202@quintus.UUCP>
Date: 27 Jul 88 21:53:01 GMT
References: <196@quintus.UUCP> <4751@csli.STANFORD.EDU>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 58

In article <4751@csli.STANFORD.EDU> evan@csli.UUCP (Evan Kirshenbaum) writes:
>In article <196@quintus.UUCP> ok@quintus () writes:
>>-- the translator did not use the 'C'/3 expansion, but tried to do
>>   the terminal matching in the translator, which meant that code with
>>   cuts and ``meta-logical'' operations did not work as expected
>>   (still a problem in the 3rd edition);

>A couple of years ago, I was working on a project which involved a
>lot of dcg's.   ...
>I figured there had to be a middle ground.  I wrote my own translator
>which runs roughly as follows (this is from memory):
	...
>    'dcg body'([],true,S,S):-!.
>    'dcg body'([T|Ts],B,[T|S0],S):-!,
>	    'dcg body'(Ts,B,S0,S).
>    'dcg body'(!,(!,S0=S),S0,S):-!.
...
>This allows the terminal folding into the head,
>but treats cut (and anything which can contain cut) as explicitly
>blocking such folding.
...
>This scheme has worked quite well.  I'm kind of curious as to whether
>there's a good reason not to do it this way.

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.  I do not know whether this was the case in
DEC-10 Prolog.  Anyrate, moving the terminals into the head should
not be neceesary for efficiency.

Kirshenbaum's problem wasn't really with the translation as such, but
with what the debugger showed him.  Speaking for myself, I _like_ seeing
the calls to 'C'/3, and wish I could set a spy-point on it.  There is a
small set of built-in operations (such as ','/2) which the debugger does
not display:  if the debugger would let Kirshenbaum say "don't show me
'C'/3" he would have got pretty much the behaviour that he wanted.  

The trouble with Kirshenbaum's translator is that cut is not the only
thing which can go wrong.  Consider a stupid example:
	p --> {var(X)}, [X].
His translator will turn that into
	p(S0, S) :- var(X), S0=[X|S].
which is correct.  But now suppose it is
	p --> var(X), [X].
	var(X) --> {var(X)}.
which his translator will turn into
	p([X|S0], S) :- var(X, S0, S).
	var(X, S0, S) :- var(X), S0 = S.
This is not a correct translation.  It is only safe to move the
unifications back over pure predicates (and pure nonterminals).

I think that the grammar rule translator is not the place for
optimisations like unfolding 'C'/3 and pushing it back into the head,
but that transformations like that belong in some other tool which
can apply them to all sorts of clauses, not just former grammar rules.
NU Prolog :- pure declarations would be important for such a tool.