Modul Chart

Jan Burse, erstellt 01. Nov 2018
/**
* This Jekejeke Minlog module allows executing definite clause grammars
* (DCGs) in a forward manner. The ordinary DCG rules of Jekejeke Prolog
* are not suitable for this purpose since they model terminals by
* [T|O] = I. We therefore provide special chart DCG rules as part of
* which model terminals by ‘D’(T,I,O). Chart DCG rules are identified
* by the (==:)/2 operator:
*
* P ==: Q. % chart DCG rule.
*
* Chart DCG rules do currently not allow for push backs. The term
* expansion augments the head and body by two additional parameters
* that are to represent the sentence position before and after the
* parsing. A predicate identifier p/n will thus be turned into a
* predicate identifier p/n+2. Further the DCG chart operator (==:)/2
* is replaced by the forward chaining operator (<=)/2:
*
* chart_post(P, I, O) <= chart_posted(Q, I, O).
*
* The expansion will then go to work and tackle the head and the body.
* Compared to ordinary DCG rules, the chart DCG rules support fewer
* constructs. For example we do not yet support the conditional (->)/2
* and the higher order calls call/n. On the other hand the look-ahead
* negation (\+) is already supported.
*
* Let us consider the following example chart DCG rule:
*
* p(X) ==: "a", q(X), {r(X)}. % chart DCG rule
*
* As an intermediate results the chart DCG rule will be turned into:
*
* post(p(X, I, O)) <= posted('D'(97, I, H)), q(X, H, O), r(X).
*
* The above rule will then be turned into a delta computation for the
* predicate ’D’/3. In general only the first literal of a DCG chart rule
* will be translated into a delta computation rule, improving efficiency.
* The words/3 construct can be used to generate the ‘D’/3 facts and the
* chart/3 construct can be used to query the result of parsing. See the
* palindrom example for more details.
*
* Warranty & Liability
* To the extent permitted by applicable law and unless explicitly
* otherwise agreed upon, XLOG Technologies GmbH makes no warranties
* regarding the provided information. XLOG Technologies GmbH assumes
* no liability that any problems might be solved with the information
* provided by XLOG Technologies GmbH.
*
* Rights & License
* All industrial property rights regarding the information - copyright
* and patent rights in particular - are the sole property of XLOG
* Technologies GmbH. If the company was not the originator of some
* excerpts, XLOG Technologies GmbH has at least obtained the right to
* reproduce, change and translate the information.
*
* Reproduction is restricted to the whole unaltered document. Reproduction
* of the information is only allowed for non-commercial uses. Selling,
* giving away or letting of the execution of the library is prohibited.
* The library can be distributed as part of your applications and libraries
* for execution provided this comment remains unchanged.
*
* Restrictions
* Only to be distributed with programs that add significant and primary
* functionality to the library. Not to be distributed with additional
* software intended to replace any components of the library.
*
* Trademarks
* Jekejeke is a registered trademark of XLOG Technologies GmbH.
*/
:- package(library(jekmin/reference/minimal)).
:- module(chart, []).
:- reexport(library(minimal/delta)).
:- public infix(==:).
:- op(1200, xfx, ==:).
/**********************************************************/
/* Word Posting */
/**********************************************************/
/**
* words([A1, ..., An], I, O):
* words([A1, ..., An], I, O, G):
* Post the words A1,..,An from index I to index O before further solving.
*/
% words(+List, +Integer, -Integer)
:- public words/3.
words(L, _, _) :-
var(L),
throw(error(instantiation_error,_)).
words(L, I, O) :-
expand_goal(words(L, I, O), Q),
call(Q).
% words(+List, +Integer, -Integer, +Goal)
:- public words/4.
words(L, _, _, _) :-
var(L),
throw(error(instantiation_error,_)).
words(L, I, O, G) :-
expand_goal(words(L, I, O), Q),
call(Q, G).
% user:goal_expansion(+Goal, -Goal)
:- public user:goal_expansion/2.
:- multifile user:goal_expansion/2.
:- meta_predicate user:goal_expansion(0,0).
:- discontiguous user:goal_expansion/2.
user:goal_expansion(words(L, _, _), _) :-
var(L), !, fail.
user:goal_expansion(words([], I, I), true).
user:goal_expansion(words(U, I, O), ( words(B, H, O), G)) :-
U = [A|B],
H is I+1,
sys_replace_site(Q, U, 'D'(A,I,H)),
sys_replace_site(G, Q, post(Q)).
/**********************************************************/
/* Chart Checking */
/**********************************************************/
/**
* chart(A, I, O):
* Succeeds when there is a phrase A from index I to index O.
*/
% chart(+Phrase, +Integer, -Integer)
:- public chart/3.
:- meta_predicate chart(2,?,?).
chart(P, _, _) :-
throw(error(instantiation_error,_)).
chart(P, I, O) :-
expand_goal(chart(P, I, O), Q),
call(Q).
/**********************************************************/
/* Goal Rewriting Steadfast */
/**********************************************************/
/**
* P:
* The non-terminal P is checked.
*/
user:goal_expansion(chart(P, I, O), chart(P, I, O)) :-
sys_var(P).
user:goal_expansion(chart(P, I, O), R) :-
chart_expansion(P, I, O, R).
user:goal_expansion(chart(P, I, O), Q) :-
sys_modext_args(P, I, O, Q).
/**
* chart_expansion(A, I, O, G)
* Succeeds when the phrase A extended by the input I and the
* output O results in the steadfast goal G.
*/
% chart_expansion(+Phrase, +List, -List, -Goal)
:- private chart_expansion/4.
:- meta_predicate chart_expansion(2,?,?,0).
:- discontiguous chart_expansion/4.
:- set_predicate_property(chart_expansion/4, sys_noexpand).
/**
* fail:
* The grammar fails.
*/
chart_expansion(P, _, _, P) :-
P = fail.
/**
* A, B:
* The output of A is conjoined with the input of B.
*/
chart_expansion(( A, B), I, O, ( chart(A, I, H),
sys_chart(B, H, O))) :-
sys_var(A).
chart_expansion(( U, B), I, O, ( P,
chart(B, I, O))) :-
chart_barrier(U, I, P).
chart_expansion(( A, B), I, O, ( chart(A, I, H),
sys_chart(B, H, O))).
/**
* A; B:
* The grammar succeeds when A succeeds or when B succeeds.
*/
chart_expansion(( A; B), I, O, ( chart(A, I, O)
; chart(B, I, O))).
/**
* [A1, ..., An]:
* The terminals A1, ..., An are checked.
*/
chart_expansion(U, I, O, Q) :-
U = [],
sys_replace_site(Q, U, I=O).
chart_expansion(U, I, O, ( Q,
sys_chart(B, H, O))) :-
U = [A|B],
sys_replace_site(Q, U, 'D'(A,I,H)).
chart_expansion(U, I, O, ( P, Q)) :-
chart_barrier(U, I, P),
sys_replace_site(Q, U, I=O).
:- private chart_barrier/3.
:- meta_predicate chart_barrier(2,?,0).
:- discontiguous chart_barrier/3.
:- set_predicate_property(chart_barrier/3, sys_noexpand).
/**
* !:
* The choice points are removed.
*/
chart_barrier(U, _, U) :-
U = !.
/**
* {A}:
* The auxiliary condition is checked.
*/
chart_barrier({A}, _, A).
/**
* \+ A:
* The negation of A is checked. The output of A is left loose.
*/
chart_barrier(U, I, Q) :-
U = (\+A),
sys_replace_site(Q, U, {\+chart(A,I,_)}).
/**********************************************************/
/* Goal Rewriting Non-Steadfast */
/**********************************************************/
:- private sys_chart/3.
:- meta_predicate sys_chart(2,?,?).
sys_chart(_, _, _) :-
throw(error(existence_error(body,sys_chart/3),_)).
user:goal_expansion(sys_chart(P, I, O), chart(P, I, O)) :-
sys_var(P).
user:goal_expansion(sys_chart(P, I, O), R) :-
sys_chart_expansion(P, I, O, R).
user:goal_expansion(sys_chart(P, I, O), Q) :-
sys_modext_args(P, I, O, Q).
/**
* sys_chart_expansion(A, I, O, G)
* Succeeds when the phrase A extended by the input I and the
* output O results in the not-necessarily steadfast goal G.
*/
% sys_chart_expansion(+Grammar, +List, -List, -Goal)
:- private sys_chart_expansion/4.
:- meta_predicate sys_chart_expansion(2,?,?,0).
:- set_predicate_property(sys_chart_expansion/4, sys_noexpand).
P = fail.
sys_chart_expansion(( A, B), I, O, ( sys_chart(A, I, H),
sys_chart(B, H, O))) :-
sys_var(A).
sys_chart_expansion(( U, B), I, O, ( P,
chart(B, I, O))) :-
chart_barrier(U, I, P).
sys_chart_expansion(( A, B), I, O, ( sys_chart(A, I, H),
sys_chart(B, H, O))).
sys_chart_expansion(( A; B), I, O, ( chart(A, I, O)
; chart(B, I, O))).
U = [],
sys_replace_site(Q, U, true).
sys_chart(B, H, O))) :-
U = [A|B],
sys_replace_site(Q, U, 'D'(A,I,H)).
sys_chart_expansion(U, I, O, ( P, Q)) :-
chart_barrier(U, I, P),
sys_replace_site(Q, U, I=O).
/**********************************************************/
/* Chart DCG Rule */
/**********************************************************/
% user:term_expansion(+Term, -Term)
:- public user:term_expansion/2.
:- multifile user:term_expansion/2.
:- meta_predicate user:term_expansion(-1,-1).
:- discontiguous user:term_expansion/2.
/**
* H ==: B:
* Chart DCG rule with chart head H and chart body B.
*/
:- public ==: /2.
:- meta_predicate (-3==: -3).
(_ ==: _) :-
throw(error(existence_error(body,==: /2),_)).
user:term_expansion((P ==: A), (chart_post(P, I, O) <=
chart_posted(A, I, O))).
/**
* chart_post(H, I, O):
* This predicate cannot be executed. It only serves as a goal
* expansion wrapper, that generates the post head of a chart rule.
*/
:- private chart_post/3.
:- meta_predicate chart_post(2,?,?).
chart_post(_, _, _) :-
throw(error(existence_error(body,chart_post/3),_)).
user:goal_expansion(chart_post(P, I, O), H) :-
sys_modext_args(P, I, O, Q),
sys_replace_site(H, Q, post(Q)).
/**
* chart_posted(B, I, O):
* This predicate cannot be executed. It only serves as a goal
* expansion wrapper, that generates the posted body of a chart rule.
*/
:- private chart_posted/3.
:- meta_predicate chart_posted(2,?,?).
chart_posted(_, _, _) :-
throw(error(existence_error(body,chart_posted/3),_)).
throw(error(instantiation_error,_)).
user:goal_expansion(chart_posted(( A, B), I, O), ( chart_posted(A, I, H),
sys_chart(B, H, O))).
user:goal_expansion(chart_posted(( A; B), I, O), ( chart_posted(A, I, O)
; chart_posted(B, I, O))).
sys_chart(B, H, O))) :-
U = [A|B],
sys_replace_site(Q, U, 'D'(A,I,H)).
sys_modext_args(P, I, O, Q).

Kommentare