ken@aiai.ed.ac.uk (Ken Johnson) (09/12/89)
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.'thom@sbcs.sunysb.edu (Thom Fruhwirth) (09/14/89)
This is a comment to the posting "ken@aiai.UUCP Tue Sep 12 12:54:10 1989".
Ken Johnson introduced "a phrase generator that generates phrases at random
from a DCG". I like the idea, but I could not resist simplifying the program.
I assume you have the original program, because I only present the part
that has changed. I did not take time to comment the code itself.
Ken Johnson used a 'repeat'-construction and a recursion to make the
deterministic top-level predicate indeterministic. Either the 'repeat'
or the recursion would have been sufficient, I prefer the 'repeat'-
construct, because it is more efficient. Further I renamed gen_phrase/2
into random_phrase/2.
I merged gen_1_phrase/3 into expand/3 making gen_1_phrase/3 obsolete.
The original expand/3 used two difference lists, which is a kind of
overkill, one difference list (now in the second and third argument
of expand/3) suffices.
% Phrase generator: Generate a phrase at random from a simple DCG.
% Ken Johnson 12-9-89, modified by Thom Fruehwirth 13-9-89
% This generator does not understand about arguments to non-terminals,
% the use of { }, or anything else. Don't say I didn't tell you.
% The top level phrase generator: Given a class name it will
% produce a sentence that matches the pattern defined in the DCG.
random_phrase(Class,Sentence):-
functor(Goal,Class,2),
expand(Goal,Sentence,[]).
% Expand a sequence of non-terminals
expand((P,Q),A,C) :-
!,
expand(P,A,B),
expand(Q,B,C).
expand('C'(_,Word,_),[Word|B],B) :-
!.
expand(P,A,B) :-
setof(Body_,clause(P,Body_),Bodies),
pick_one(Bodies,Body),
expand(Body,A,B).
% Pick at random from a list
% I like the code as it is in the original posting, see there
% the endok@cs.mu.oz.au (Richard O'Keefe) (09/14/89)
In article <873@skye.ed.ac.uk>, ken@aiai.ed.ac.uk (Ken Johnson) writes: > 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. The claim about DCGs is strictly false: in my programs I use DCGs to build lists far more often than I use them to parse things. What's more, I left a program at Edinburgh which generated "random plots for science fiction stories". That program was a Prolog rewrite of a C program written by David Tilbrook. I find "stories" like Giant mushrooms invade Reading, but Ronald Reagan's dog invents laser weapons, and it is the end of civilisation as we know it. _much_ more interesting than insults. If you want to generate random phrases, you had better work out what probability model you want to use (for example, do you want all phrases of length N to be equiprobable). A simple hack is just to pull maybe(+P) % succeeds with probability P out of the library and code your rules as <head> --> {maybe(P)}, <body>. If all the rules in a grammar are epsilon-free, it may be possible to enumerate all the sentences in increasing order of length. If your start symbol is s//0, the device is s(Sentence) :- length(Sentence, _dont_care_but_increasing), s(Sentence, []). This is just iterative deepening in another disguise. Here is an example: s --> monster(_), [meets], monster(_) | monster(male), [marries], monster(female). monster(Sex) --> relation(Sex), [of], monster2(_) | monster2(Sex). relation(male) --> [son] | [nephew]. relation(female) --> [daughter] | [niece]. monster2(male) --> [dr], ( [who] | [strangelove] | [death] ). monster2(female) --> [shelob] | [mrs,thatcher] | [vampirella]. monster2(_) --> [the], monster3, [from], place. monster3 --> [thing] | [blob] | [mp]. place --> [hell] | [mars] | [edinburgh]. s(X) :- length(X, _), % generate increasingly longer lists s(X, []). % fill them with words. If your length/2 is broken, use list([]). list([_|L]) :- list(L). instead. -- I hear the handwriting on the wall. -- farb(1), UofArizona 'icon' system.