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

active_chart_topdown.pl

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

An active chart-based recognizer. The chart is filled in a top-down 
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_topdown(Input, 0),
	initialize_agenda_topdown(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_topdown(+sentence, +start node)

%%% Add passive arcs giving the categories of the words of the 
%%% input sentence to the chart.
initialize_chart_topdown([], _).
initialize_chart_topdown([Word|Input], From) :-
	To is From + 1,
	assert(scan(From, To, Word)),
	doall(
	     (lex(Word,Cat), assert(arc(From,To,Cat,[Word],[]))
              %%% ,write('New arc on chart: '), write(arc(From,To,Cat,[Word],[])), nl
             )
	),
	initialize_chart_topdown(Input, To).


%%% initialize_agenda_topdown(-agenda)
%%% Active edges for all s-rules in the grammar.
initialize_agenda_topdown(Agenda) :-
	findall(arc(0, 0, s, [], RHS), s ---> RHS, 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 (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_topdown(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_topdown(+arc, -list of arcs) 

%%% 'arc' is active -> steps 2c and 2d apply.
make_new_arcs_topdown(Arc, NewArcs) :-
	Arc = arc(_,_,_,_,[_|_]),
	apply_fundamental_rule(Arc, NewArcs1),
	predict_new_arcs_topdown(Arc, NewArcs2),
	append(NewArcs1,NewArcs2,NewArcs).

%%% 'arc' is passive -> only step 2c applies.
make_new_arcs_topdown(Arc, NewArcs) :-
	Arc = arc(_,_,_,_,[]),
	apply_fundamental_rule(Arc, 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_topdown(+arc, -list of arcs)
%%% If 'arc' is an active arc, then find a rule which has the next
%%% category on the ToFind list (here: ToFindCat) as its left
%%% hand side.
%%% Uses findall/3 to collect all solutions.

predict_new_arcs_topdown(arc(_, J, _, _, [ToFindCat|_]), NewArcs) :-
	findall(arc(J, J, ToFindCat, [], RHS),
	        ToFindCat ---> RHS,
	        NewArcs
	    ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 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!
***********************************************************************/