Subject: RE: UNDERSTANDING LISTS

From: "Richard A. O'Keefe" <[email-masked]>
Date: Thu, 4 May 2000 13:55:54 +1200 (NZST)

1) NL reasoning
	
There is no actual *natural language* reasoning here at all.

		%Goal:
	where is new york? in R..             	
	
		% Inference rules:
	who is X? R :- X is R..
	where is X? in R :- X is situated in R..     		            
	
		% Factual knowledge:
	joe is son of maria and peter..
	julia is daughter of maria and peter..                        
	peter 2 is son of maria and peter 1..                         
	jack 2 is son of julia and jack 1..                           
	new york is situated in america..                             
	st.petersburg is situated in russia..                         
	a book is situated on a table..                               
	
		% Output:
	where is new york? in america..
	
I'm having some trouble reading this.  I'm assuming here that all variables
are segment variables and that ? is just another word.  One thing is
extremely clear:  this kind of ersatz English only works for toy problems.

A fairly direct Prolog translation is

	?- where_is([new,york], R).
	who_is(X, R) :- list_fact(( lit(X), [is], lit(R) )).
	where_is(X, R) :- list_fact(( lit(X), [is,situated,in], lit(R) )).
	list_fact(NT) :- fact(F), phrase(NT, F, []).
	fact([joe,is,son,of,maria,and,peter]).
	fact([julia,is,son,of,maria,and,peter]).	
	fact([peter,2,is,son,of,maria,and,peter,1]).
	fact([jack,2,is,son,of,julia,and,jack,1]).
	fact([new,york,is,situated,in,america]).
	fact([st,petersburg,is,situated,in,russia]).
	fact([a,book,is,situated,on,a,table]).
	
Transcript:

	?- where_is([new,york], R).
	R = [america] 

Here I am making use of two Quintus innovations:
- phrase/3 can accept an arbitrary grammar rule body as first
  argument, not just a non-terminal.  I have no idea why SWI
  Prolog doesn't support this; it should be fixed at once.
  (I had to define ','/4 to patch around this SWI bug.)
- the library predicate lit//1 is append/3 with its arguments
  reordered to be useful in grammar rules.  It's tiny.
These features date back to the mid 80s.  it took 3 lines to patch
them into SWI Prolog, but they're *library* code shared with *all*
Prolog programs, so don't count here.

The output isn't identical, but the *problem* (finding out where New York
is) is solved by the same highly unnatural and error prone method.
Why do i say error prone?

	?- who_is([new,york], R).
	R = [situated, in, america] 

That's the right answer according to the program, but it isn't at all
a meaningful answer to a "who is" question in English.

	2) Logic Formula Transformation
	
		%Goal:
	according to the rule R, the result of shifting quantifiers in formula 
	( for-all x 0 ) [a ( x 0 , y )] or ( for-all x 0 ) [b ( x 0 , t )] 
	is formula W..
	
		% Program. Main clause:
	according to the rule 2a from chapter 5, the result of shifting quantifiers
	in formula 
	( Q X ) [F] or ( Q X ) [H] 
	is formula ( Q X ) ( Q Z ) ( [F] or [G] ) :- 
		X is notation for variables ,, 
		Z is notation for variables ,, 
		formula F does not contain variable Z ,, 
		the result of replacing X by Z in formula [ H ] is formula [ G ] ..

		% Definition of the variables for this  logic calculus
	x 0 is notation for variables ..
	X 1 0 is notation for variables :- 
		X 0 is notation for variables ..

		% Strighforward explanation what is 
		% "does not contain" and "contains" :
	formula F does not contain variable Z :- ~~word F contains word Z ..
	word _ X _ contains word X ..

		% Definition of the algorithm for replacing variables 
		% in logic formulae:
	the result of replacing X by Y in formula [ A X M ]
				       is formula [ A Y N ] :-
		the result of replacing X by Y in formula [ M ] is formula [ N ] ..
	
	the result of replacing X by Y in formula [ A ] is formula [ A ] :-
		formula A does not contain variable X..
	
		% Output:
	according to the rule 2a from chapter 5, 
	the result of shifting quantifiers in formula 
	( for-all x 0 ) [a ( x 0 , y )] or ( for-all x 0 ) [b ( x 0 , t )] 
	is formula 
	( for-all x 0 ) ( for-all x 1 0 ) ( [a ( x 0 , y )] or [b ( x 1 0 , t )] )
	
The key problem here is that while a logical formula may be *represented by*	
a list of symbols, it *is* a tree.  In fact, it's *two* kinds of trees; a
type of formulas and a type of terms.  Any representation which hides that
is unnatural.  Any representation which treats things as flat lists is going
to have trouble with nesting brackets, or else use highly specific rules for
matching them.

I also have a problem with the definition
of "formula F does not contain variable Z".  The right concept here is
"formula F does not contain any free references to variable Z", and a
simple scan for the string Z will not do that job properly.  Again, to
the extent that I understand it, ``the result of replacing...'' treats
the formula as a string and ignores embedded quantifiers.

	:- type term --> x(integer) | f(atom,list(term)).
	:- type quant --> forall | exists.
	:- type form --> quant(quant,term,form) | p(atom,list(term))
		      |  and(form,form) | or(form,form) | not(form).
		      
	:- pred rule(atom, atom, form, form).

	rule('quantifier shift', '5.2a',
	     or( quant(Q,X,F), quant(Q,X,H) ),
	     quant(Q,X,quant(Q,Z, or(F,G)))
	) :-
	%   is_variable(X),		% type check means not needed
	    is_variable(Z),		% has infinitely many solutions;
	    free_of(F, Z),		% in practice use next highest var
	    substitute(X, Z, H, G).
	
	:- pred is_variable(term).
	is_variable(x(N)) :- at_least(0, N).	% library(between).

	:- pred free_of(form, term).
	free_of(quant(_,V,F), Z) :-
	    ( V == Z -> true ; free_of(F, Z) ).
	free_of(and(A,B), Z) :- free_of(A, Z), free_of(B, Z).
	free_of(or(A,B), Z) :- free_of(A, Z), free_of(B, Z).	
	free_of(not(A), Z) :- free_of(A, Z).
	free_of(p(_,L), Z) :- \+ some(contained_in(Z), L).

	:- pred contained_in(term, term).  % is bidirectional
	contained_in(Z, Z).
	contained_in(Z, f(_,L)) :- some(contained_in(Z), L).

	:- pred substitute(term, term, form, form).
	substitute(X, Y, quant(Q,V,F), quant(Q,V,G)) :-
	    ( V == X -> G = F ; substitute(X, Y, F, G) ).
	substitute(X, Y, and(A,B), and(F,G)) :-
	    substitute(X, Y, A, F),
	    substitute(X, Y, B, G).
	substitute(X, Y, or(A,B), or(F,G)) :-
	    substitute(X, Y, A, F),
	    substitute(X, Y, B, G).
	substitute(X, Y, not(A), not(F)) :-
	    substitute(X, Y, A, F).
	substitute(X, Y, p(F,L), p(F,R)) :-
	    maplist(termsubst(X, Y), L, R).

	:- pred termsubst(term, term, term, term).
	termsubst(X, Y, X, Y).
	termsubst(X, Y, f(F,L), f(F,R)) :-
	    maplist(termsubst(X, Y), L, R).

Here I've used
    maplist/3		from library(maplist); provided in SWI
    some/2		from library(maplist); *NOT* in SWI
    at_least/2		from library(between); *NOT* in SWI.

Transcript:
	?- rule('quantifier shift', R,
		or( quant(forall, x(0), p(a,[x(0),f(y,[])])),
		    quant(forall, x(0), p(b,[x(0),f(t,[])])) ),
		W).
	R = '5.2a'
	W = quant(forall,x(0),quant(forall,x(1),
	    or(p(a,[x(0),f(y,[])]),p(b,[x(1),f(t,[])])))) 

The notation is different, but the output is the same.
In fact the rule as stated as wrong:
	or(quant(Q,X,F), quant(Q,X,G))
should be replaced by quant(Q,X,or(F,G)); there is no point at all
in introducing a new quantifier.  Better rules would be something like
	rule('quantifier fusion',
	    or(quant(Q,X,F), quant(Q,X,G)),
	    quant(Q,X,or(F,G))).
	rule('quantifier fusion',
	    and(quand(Q,X,F), quant(Q,X,G)),
	    quant(Q,X,and(F,G)).

The interesting thing here is that by working with trees whenever that
made sense, I was able to state type rules that can be checked by the
DEC-10 Prolog type checker (one of the three type checkers available for
NU Prolog, and the ancestor of the type checkers in Goedel and Mercury).

	3) Logic formula transformation (another version of (2))
	
Omitted because it adds nothing to what we found in (2).
	
	All 3 examples are working programs built from LISTS
	(formed from real reasoning examples).
	
And one of them used lists purely for cuteness value,
and the other two should never have used lists in the first place.

	1) They are (to a reasonable extent) in Prolog style.

Agreed (with reservations).

	2) They contain THOROUGH definitions of the corresponding
	algorithms (of parsing, inference, logic calculus etc) and data

False.  Here's a specific example.  To program 1, make this the only fact:

	henk is a boy who is fond of fishing.

Now try this query.

	who is X? R..

If the program "contain[ed a] THOROUGH definition..." of the
parsing algorithm, it would tell us whether we'd get
X = [henk], R = [a,boy,who,is,fond,of,fishing],
or
X = [henk,is,a,boy,who], R = [fond,of,fishing],
or both of them, and in that case, which we'd get first.

In fact it's *good* that the program doesn't contain any definition
of the parsing algorithm.  In Prolog, a DCG may be parsed using
recursive descent, left corner parsing, or some flavour of chart
parser (when I had an NLP course at RMIT, I used to demonstrate that).

	3) Adding additional facts (in NL or other relevant form)
	and new reasoning rules is very easy: just take an example,
	generalize it, and include.
	
	I guess that Prolog equivalents of such programs would be
	at least 10 times longer:

You guessed wrong.
		SampleTalk	Prolog		Typed		Ratio
Program 1	11 lines	11 lines			1.0
Program 2	26 lines	31 lines	41 lines	1.2

And the Prolog version of Program 2 is longer, not because of any
difficulty dealing with lists, but because it includes *correct*
definitions of free_of/2 and substitute/4 that don't mistake bound
occurrences for free ones.  (Well, I could have cheated.  The
DEC-10 Prolog library already contained predicates for substitution
and testing whether one term occurred inside another.)

	you can not define interaction 
	of these objecs (here: lists) without numerous append/3's
	or other tricks.
	
The Prolog version of program 1 uses DCG notation.
Years ago, in order to simplify the transcription of SNOBOL into Prolog,
I added lit//1 to the Quintus Prolog library.  lit(X), where X is unknown,
acts like SNOBOL's (ARB $ X).  lit(X), where X is known, acts like X.
phrase(X) is supposed to act like *X.  (If you don't know SNOBOL, don't
worry, the point is that the behaviour of phrase//1 and lit//1 were
developed years ago inspired by SNOBOL, one of the oldest string processing
languages around.  They weren't invented for this problem; they are part of
every QP programmer's toolkit.)

I get the feeling that calling _any_ built-in or library predicate would
be dismissed as "a trick".  I don't see it like that.

	Moreover, I am not sure properties (2) and (3) can be implemented
	-together- in ANY language without MATCHING LISTS

I'd like to see some evidence for that claim.	
I'd also like to know whether Sampletalk has a type checker, even an
optional one.  (It's optional in DEC-10 Prolog, required in Mercury.)