
/*********************************************************************

passive_chart_bottomup.pl

Kristina Striegnitz, 2002.
Based on code by Peter Ljunglof.

A chart-based recognizer. The chart is filled in a bottom-up fashion.

Usage: chart_recognize_bottomup(Inputsentence).

Representation of the chart:
         scan(?start node, ?end node, ?word)
         arc(?start node, ?end node, ?category)

*********************************************************************/

:- op(700, xfx, --->).

%%% uncomment the follwing line if you are using Sicstus Prolog
%%% :- use_module(library(lists), [append/3]).

%%% we have to declare the predicates scan/3 and arc/3 dynamic so that
%%% the programm can assert them to and retract them from the
%%% datatbase
:- dynamic scan/3, arc/3.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% chart_recognize_bottomup(+sentence)
%%% Clean old things out of the chart, build the complete chart for
%%% the input sentence, check whether there is an arc which is
%%% labeled with s and spanning the whole sentence.

chart_recognize_bottomup(Input) :-
	cleanup,
	initialize_chart(Input, 0),
	process_chart_bottomup,
	length(Input, N),
	arc(0, N, s).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% cleanup
%%% Deletes all scan/3 and arc/3 clauses from the database.

cleanup :- 
	retractall(scan(_,_,_)),
	retractall(arc(_,_,_)).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% initialize(+sentence, +start node)
%%% Writes entries of the form scan('start position', 'end position',
%%% 'word') into the chart for all words of the input sentence.

initialize_chart([], _).
initialize_chart([Word|Input], From) :-
	To is From + 1,
	%%% assertz -> put new word at the end of the db
	assertz(scan(From, To, Word)),
	%%% write(scan(From, To, Word)), nl,
	initialize_chart(Input, To).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% process_chart_bottomup
%%% Read one word. Look up its category. Add the arc the corresponding
%%% arc and all further arcs that can be built from it.
%%% Failure driven loop (doall) forces backtracking.

process_chart_bottomup :-
 	doall(
	      (scan(From, To, Word),
	      %%% write('read word: '), write(Word),nl,
 	      lex(Word, Cat),
 	      add_arc(arc(From, To, Cat)))
	     ).


%%% add_arc(+arc)
%%% Make sure that 'arc' is not in the chart, yet. Add it to the
%%% chart. Compute and add all arcs that can be built by combining
%%% 'arc' with arcs from the chart.

add_arc(Arc) :-
	\+ Arc,
	assertz(Arc),
	%%% write(Arc),nl,
	new_arcs(Arc).



%%% new_arcs(+arc)
%%% Find a rule such that 'Cat', the label of 'arc', is the last
%%% symbol of the right hand side. 'Before' are the symbols on the
%%% right hand side that come before that. Check that there is a path
%%% along arcs labeled with the symbols of 'Before' that ends in the
%%% starting position of 'arc'. Add a new arc that starts in the
%%% starting position of the path, ends in the ending position of
%%% 'arc' and is labeled with the symbol on the right hand side of the
%%% rule.
%%% Failure driven loop (doall) forces backtracking.

new_arcs(arc(J, K, Cat)) :-
 	doall(
	      (LHS ---> RHS,
	      append(Before, [Cat], RHS),
	      path(Before, I, J),
	      add_arc(arc(I, K, LHS)))
             ).


%%% path(+categories, ?start node, ?end node)
%%% Is there a sequence of arcs labeled with 'categories' that starts in
%%% position 'start node' and ends in position 'end node'?

path([], I, I).
path([Cat|Cats], I, K) :-
	arc(I, J, Cat),
	J =< K,
	path(Cats, J, K).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% doall(+goal)
%%% Implements a failure driven loop: Prolog backtracks until it has
%%% found all possible ways of proving the goals given as argument. 
%%% Note: The argument can be a sequence of simple Prolog goals.

doall(Goal) :- Goal, fail.
doall(_) :- true.


/**********************************************************************
                    That's all, folks!
***********************************************************************/
