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

active_chart_bottomup.pl

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

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

Usage: active_chart_recognize(Inputsentence).

Representation of the chart:
         scan(?start node, ?end node, ?word)
         arc(?start node, ?end node, ?LHS, ?Found, ?ToFind)
    
         LHS is a category, Found and ToFind are lists of categories.
         LHS, Found, and ToFind represent the followin dotted rule:
         LHS ---> Found' . ToFind 
         where Found is Found' in reversed order.

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

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

%%% :- use_module(library(lists), [append/3]).

%%% scan(?start node, ?end node, ?word)
%%% arc(?start node, ?end node, ?category, 
%%%     ?list of categories already found, 
%%%     ?list of categories still to find)
:- dynamic scan/3, arc/5.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% active_chart_recognize(+sentence)
%%% Clean the chart, initialize chart and agenda (step 1 of the
%%% general algorithm), build the chart (step 2), and check whether
%%% there is an arc spanning the whole sentence (step 3).

active_chart_recognize(Input) :-
	cleanup,
	initialize_chart_bottomup(Input, 0),
	initialize_agenda_bottomup(Agenda),
	process_agenda(Agenda),
	length(Input, N),
	arc(0, N, s, _, []).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% cleanup
%%% Cleans the database of chart entries.

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% initialize_chart_bottomup(+sentence, +start node)

%%% Produces an empty chart: i.e., a chart that only contains
%%% scan entries recording the words and their position.
initialize_chart_bottomup([], _).
initialize_chart_bottomup([Word|Input], From) :-
	To is From + 1,
	assert(scan(From, To, Word)),
	initialize_chart_bottomup(Input, To).


%%% initialize_agenda_bottomup(-agenda)
%%% Make passive arcs recoding the categories of the words and
%%% add them to the agenda.
initialize_agenda_bottomup(Agenda) :-
	findall(arc(From, To, Cat, [Word], []),
	        (
	         scan(From, To, Word),
	         lex(Word, Cat)
	        ),
	        Agenda
	       ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% process_agenda(+agenda)
%%% 'agenda' is a list of arcs that have to be processed.
%%% Takes the first arc off the agenda (step 2a of the general 
%%% algorithm). Checks whether it is already in the chart and adds it
%%% if not (step 2b). Builds all new arcs and adds them to the agenda 
%%% (steps 2c and 2d). And finally makes a recursive call with the
%%% new agenda.
%%% If the first arc is already on the chart, it goes on processing 
%%% the rest of the agenda.
%%% Stops when the agenda is empty.

process_agenda([]).
process_agenda([Arc|Agenda]) :-
	\+ Arc,!,
	assert(Arc),
	%%% nl,write('New arc on chart: '), write(Arc), nl,
	make_new_arcs_bottomup(Arc, NewArcs),
	append(NewArcs, Agenda, NewAgenda),
	%%% write('New arcs on agenda: '), write(NewArcs), nl,
	process_agenda(NewAgenda).
process_agenda([_|Agenda]) :-
        process_agenda(Agenda).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% make_new_arcs_bottomup(+arc, -list of arcs) 

%%% 'arc' is active -> only step 2c applies.
make_new_arcs_bottomup(Arc, NewArcs) :-
	Arc = arc(_,_,_,_,[_|_]),
	apply_fundamental_rule(Arc, NewArcs).

%%% 'arc' is passive -> steps 2c and 2d apply
make_new_arcs_bottomup(Arc, NewArcs) :-
	Arc = arc(_,_,_,_,[]),
	apply_fundamental_rule(Arc, NewArcs1),
	predict_new_arcs_bottomup(Arc, NewArcs2),
	append(NewArcs1, NewArcs2, NewArcs).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% apply_fundamental_rule(+arc, -list of arcs)
%%% Applies the fundamental rule to 'arc' and returns all arcs that
%%% can be built that way in a list.
%%% Uses findall/3 to collect all solutions.

%%% We have an active arc; we are looking for a passive one that
%%% follows it.
apply_fundamental_rule(arc(I, J, Cat, Done, [SubCat|SubCats]), NewArcs) :-
	findall(arc(I, K, Cat, [SubCat|Done], SubCats),
	        arc(J, K, SubCat, _, []),
	        NewArcs
	       ).	

%%% We have a passive arc; we are looking for an active one that
%%% precedes it.
apply_fundamental_rule(arc(J, K, Cat, _, []), NewArcs) :-
	findall(arc(I, K, SuperCat, [Cat|Done], Cats),
	        arc(I, J, SuperCat, Done, [Cat|Cats]),
	        NewArcs
	    ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% predict_new_arcs_bottomup(+arc, -list of arcs)
%%% If 'arc' is a passive arc, then find a rule which has the LHS of
%%% the arc (here: Cat) as first category on RHS.
%%% Uses findall/3 to collect all solutions.

predict_new_arcs_bottomup(arc(J, _, Cat, _, []), NewArcs) :-
	findall(arc(J, J, SuperCat, [], [Cat|Cats]),
	        SuperCat ---> [Cat|Cats],
	        NewArcs
	    ).


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