Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!ames!lll-winken!uunet!mcsun!ukc!edcastle!aiai!ken
From: ken@aiai.ed.ac.uk (Ken Johnson)
Newsgroups: comp.lang.prolog
Subject: A phrase generator for Prolog DCG's
Keywords: dcg prolog sentences
Message-ID: <873@skye.ed.ac.uk>
Date: 12 Sep 89 16:54:10 GMT
Reply-To: ken@aiai.UUCP (Ken Johnson)
Followup-To: comp.lang.prolog
Organization: AIAI, University of Edinburgh, Scotland
Lines: 132

I've found that the usual way of teaching about grammars with Lisp and
Logo involves generating random phrases freom a grammar whereas Prolog's
DCG mechanism does not allow you to do that: it just checks whether a
given string of non-terminals can be derived from the grammar or not. 

Here is a phrase generator that generates phrases at random from a DCG,
which may add a touch of humour to an otherwise forebodingly dull topic. 
(That's a value judgement of course and you're free to disagree with
it.) There is a simple DCG attached to this phrase generator; it should
work with other DCGs.  If anyone can find a general way to make the code
understand about arguments to non-terminals, I would be interested to
see how it is done.  (I mean rules like sentence(Number) -->
nounphrase(Number), verbphrase(Number).  where Number is `singular' or
`plural'). 

*************************************************************************
*	H. M. GOVERNMENT HEALTH WARNING...				*
*                                                                       *
*	The code ASSUMES that your Prolog stores DCG information	*
*	in the same way that Edinburgh Prolog does.  Not all		*
*	Prologs store DCG rules that way. 				*
*************************************************************************

I have tested this code with Edinburgh Prolog (the New Implementation),
version 1.5.04 dated 12 September 1988 (Happy birthday to you, happy
birthday to yooooooooooooooo! :-) and it seemed to work. 

To run the program as it stands, give the command

	?- repeat,
		gen_phrase(insult,Stuff),
		write(Stuff),
		nl,
		fail.

Share, enjoy, and good luck:

Cut here ------------ 8< ------------ cut here ------------ 8< ------------
% Phrase generator: generate a phrase at random from a simple DCG.
% Ken Johnson 12-9-89
% You may make and distribute copies of this code if you want to,
% except that if you sell them at a profit I want a share.

% The top level phrase generator: given a class name it will
% produce a sentence that matches the pattern defined in the DCG.
% Example invocation:
% gen_phrase(insult,Outcome).
% The insults grammar is given after the important bits.

% This generator does not understand about arguments to non-terminals,
% the use of { }, or anything else. Don't say I didn't tell you.

gen_phrase(Class,Outcome) :-			% This predicate serves only
	gen_1_phrase(Class,Outcome).		% to give repeated
						% instantiations of Outcome
gen_phrase(Class,Outcome) :-			% on backtracking.
	gen_phrase(Class,Outcome).

% Generate a single phrase

gen_1_phrase(Class,Outcome) :-
	gen_1_phrase(Class,X-X,Outcome-[]).	% Call with accumulator X-X

gen_1_phrase(Class,So_far,Outcome) :-		% Create a term insult(_,_)
	functor(Term,Class,2),			% which matches the clauses
	setof(Body,clause(Term,Body),Set),	% of the DCG, then pick one
	pick_one(Set,A_body),			% matching clause and
	expand(A_body,So_far,Outcome).		% expand it

% Expand a non-terminal, or sequence of non-terminals

expand((P,Q),A,C) :-				% Expand (P,Q) by expanding
	!,					% P and then appending the
	expand(P,A,B),				% expansion of Q
	expand(Q,B,C).

expand('C'(_,Word,_),U-[Word|V],U-V).		% The predicate `C' processes
						% ground atoms; for non-
expand(Term,So_far,Outcome) :-			% terminals, use gen_1_phrase
	functor(Term,Functor,_),		% recursively to expand them
	Functor \== 'C',
	gen_1_phrase(Functor,So_far,Outcome).

% Pick at random from a list

pick_one(List,Element) :-
	length(List,Length),
	random(Length,Random_int),
	nth(Random_int,List,Element).


nth(0,[X|_],X).					% n'th element of a list

nth(N,[_|T],X) :-
	N > 0,
	M is N - 1,
	nth(M,T,X).

random(Modulus,N) :-				% Pretty awful random number
	recorded(random_seed,Seed,Ref),		% generator. If no seed, it
	!,					% uses 13 so it always goes
	erase(Ref),				% through the same sequence
	random(Modulus,Seed,N).

random(Modulus,N) :-
	random(Modulus,13,N).

random(Modulus,Seed,N) :-
	New is ((125 * Seed) mod 4093),
	record(random_seed,New,_),
	N is New mod Modulus.

% ------------------------------------------------------------------------
% An Insults Grammar
% Here is an example DCG with which gen_phrase works
% I first came across this grammar in Alan Bundy's book so I think I
% ought tell you it isn't original to me.

insult --> action, [you], misname.

action --> [sod,off].
action --> [take,a,running,jump].

misname --> [cretin].
misname --> [bum].
misname --> [great,pillock].

-- 
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
`I have read your article, Mr.  Johnson, and I am no wiser than when I
started.' -- `Possibly not, sir, but far better informed.'