[comp.lang.prolog] A little template matcher

ken@aiai.ed.ac.uk (Ken Johnson) (07/16/90)

% A simple template matcher. This is not likely to be of much interest to
% Prolog wizards, but some beginners might find it interesting.
% See examples for how it works. Arg1 to match/2 is a template, arg2 is
% a piece of text, and the object of the code is to instantiate variables
% in the template so that it `matches' the text.
% Ken Johnson, July 1990

test1 :-
	match([the,quick,brown,fox],[the,quick,brown,fox]).

test2(X) :-					% X = [quick]
	match([the,X,brown,fox],[the,quick,brown,fox]).

test3(X) :-					% X = [quick,brown]
	match([the,X,fox],[the,quick,brown,fox]).

test4(X) :-						% X is null
	match([the,quick,brown,X,fox],[the,quick,brown,fox]).

test5(X) :-						% X = [a,rose]
	match([X,is,X,is,X],[a,rose,is,a,rose,is,a,rose]).

test6(X) :-						% FAILS correctly
	match([X,is,X,is,X],[fat,'freddy''s',cat,is,a,rose,is,a,rose]).



match([],[]).

match([X1|T1],Text) :-
	matchv(X1,A-A,T1,Text).

match([X1|T1],[X2|T2]) :-	% The nonvar avoids extra solutions in
	nonvar(X1),		% cases like match([X,b,c],[a,b,c])
	match(T1,T2),		% by avoiding the solution X=a
	X1 = X2.		% (X=[a] is the only solution intended)


matchv(Stuff,Stuff-[],Template,Text) :-
	match(Template,Text).

matchv(X,Stuff-[Word|A],Template,[Word|Text]) :-
	matchv(X,Stuff-A,Template,Text).
-- 
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
`You can prove things and then people have to believe you, whether they
like you or not' [Hans Eysenck]

ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (07/20/90)

In article <2994@skye.ed.ac.uk>, ken@aiai.ed.ac.uk (Ken Johnson) writes:
> % A simple template matcher.

> match([], []).
> match([X1|T1], Text) :-
> 	matchv(X1, A-A, T1, Text).
> match([X1|T1], [X2|T2]) :-	% The nonvar avoids extra solutions in
> 	nonvar(X1),		% cases like match([X,b,c],[a,b,c])
> 	match(T1, T2),		% by avoiding the solution X=a
> 	X1 = X2.		% (X=[a] is the only solution intended)

> matchv(Stuff, Stuff-[], Template, Text) :-
> 	match(Template, Text).
> matchv(X, Stuff-[Word|A], Template, [Word|Text]) :-
> 	matchv(X, Stuff-A, Template, Text).

The first thing to notice about this is that it uses an explicit
"difference list" data structure.  Ugh.  There is just no point in
packaging two things up just in order to unwrap them again in the
very next instant.  We can simplify this to

match([], []).
match([X1|T1], Text) :-			% X1 is a list or a variable
	matchv(X1, A, A, T1, Text).
match([X1|T1], [X2|T2]) :-		% X1 is an atom
	nonvar(X1),
	X1 = X2,
	match(T1, T2).

matchv(Stuff, Stuff, [], Template, Text) :-
 	match(Template, Text).
matchv(X, Stuff, [Word|A], Template, [Word|Text]) :-
 	matchv(X, Stuff, A, Template, Text).

This might be more clearly expressed as

	match([], []).
	match([Item|Items], [Word|Words) :- atom(Item), Item \== [], !,
		Item = Word,
		match(Items, Words).
	match([Item|Items], Words) :-
		append(Item, RestWords, Words),
		match(Items, RestWords).

The trouble with this, of course, is that it is still rather non-logical.
See pages 150--152 of "The Craft of Prolog" for a pure (=faster) version.

-- 
Science is all about asking the right questions.  | ok@goanna.cs.rmit.oz.au
I'm afraid you just asked one of the wrong ones.  | (quote from Playfair)